可以将一系列键映射到值的数据结构

Question

我试图找到一种数据结构，它从一系列值中获取特定值并将其映射到键。

例如，我有以下条件：

1. 从1到2.9，我想把它映射到A.
2. 从4到6，我要把它映射到B.
3. 从6.5到10，我想把它映射到C.

我的值为 5，我想将其映射到一个键。所以基于上述条件，我应该将其映射到B。

Java中有什么数据结构可以推荐给我来解决这个问题吗？

目前我正在使用一个只能将值映射到键的哈希表。我尝试将值的范围映射到哈希表中存在的特定值。但是，我陷入了将值范围映射到特定值的映射中。所以现在我正在尝试做另一种将值范围映射到键的方法。有人知道我如何解决这个问题吗？

编辑：

感谢马丁·埃利斯，我决定用TreeMap来解决这个问题。

Answer 1

HashMap不适用于将范围映射到值，除非您找到一种方法来为范围和其中匹配的单个值生成哈希码。但是下面的方法可能是您正在寻找的

public class RangeMap {
    static class RangeEntry {
        private final double lower;
        private final double upper;
        private final Object value;
        public RangeEntry(double lower, double upper, Object mappedValue) {
            this.lower = lower;
            this.upper = upper;
            this.value = mappedValue;
        }
        public boolean matches(double value) {
            return value >= lower && value <= upper;
        }
        public Object getValue() { return value; }
    }

    private final List<RangeEntry> entries = new ArrayList<RangeEntry>();
    public void put(double lower, double upper, Object mappedValue) {
        entries.add(new RangeEntry(lower, upper, mappedValue));
    }
    public Object getValueFor(double key) {
        for (RangeEntry entry : entries) {
            if (entry.matches(key))
                return entry.getValue();
        }
        return null;
    }
}

你可以的

RangeMap map = new RangeMap();
map.put(1, 2.9, "A");
map.put(4, 6, "B");

map.getValueFor(1.5); // = "A"
map.getValueFor(3.5); // = null

它不是很有效，因为它只是迭代一个列表，如果你在其中放置冲突的范围，它不会在那种状态下抱怨。将只返回它找到的第一个。

P.S.：这样的映射就是将一系列键映射到一个值

Answer 2

Guava RangeMap提供现成的专业解决方案：

RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
rangeMap.put(Range.closed(1, 100), "foo"); // {[1, 100] => "foo"}
rangeMap.put(Range.open(3, 6), "bar"); // {[1, 3] => "foo", (3, 6) => "bar", [6, 100] => "foo"}

rangeMap.get(42); // returns "foo"

Answer 3

您的范围不重叠吗？如果是这样，您可以使用树形图:

TreeMap<Double, Character> m = new TreeMap<Double, Character>();
m.put(1.0, 'A');
m.put(2.9, null);
m.put(4.0, 'B');
m.put(6.0, null);
m.put(6.5, 'C');
m.put(10.0, null);

查找逻辑有点复杂，因为您可能需要一个包含性的查找(即2.9映射到‘A’，而不是未定义的):

private static <K, V> V mappedValue(TreeMap<K, V> map, K key) {
    Entry<K, V> e = map.floorEntry(key);
    if (e != null && e.getValue() == null) {
        e = map.lowerEntry(key);
    }
    return e == null ? null : e.getValue();
}

例：

mappedValue(m, 5) == 'B'

更多结果包括：

0.9 null
1.0 A
1.1 A
2.8 A
2.9 A
3.0 null
6.4 null
6.5 C
6.6 C
9.9 C
10.0 C
10.1 null