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

data-structures dictionary java range-map

2022-09-01 14:07:36

我正在尝试找到一个数据结构，该结构从一系列值中获取特定值并将其映射到键。

例如，我有以下条件：

从1到2.9，我想把它映射到A。
从4到6，我想把它映射到B。
从6.5到10，我想把它映射到C。

我的值为5，我想将其映射到键。因此，基于上述条件，我应该将其映射到B。

Java中是否有任何数据结构可以推荐给我来解决问题？

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

编辑：

多亏了Martin Ellis，我决定使用TreeMap来解决这个问题。

答案 1

您的范围是否不重叠？如果是这样，您可以使用树状图：

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

答案 2

番石榴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"