可以将一系列键映射到值的数据结构
我试图找到一个数据结构，从一系列值中获取特定值并将其映射到一个键。
例如，我有以下条件：
- 从1到2.9，我想将它映射到A.
- 从4到6，我想将它映射到B.
- 从6.5到10，我想将它映射到C.
我的值为5，我想将其映射到一个键。 所以基于上述条件，我应该把它映射到B.
Java中是否有任何人可以向我推荐解决问题的数据结构？
目前我使用的哈希表只能将值映射到键。 我尝试将值范围映射到哈希表中存在的特定值。 但是，我陷入了将值范围映射到特定值的问题。 所以现在我试图用另一种方法将值范围映射到键。 有谁知道如何解决这个问题？
编辑：
感谢Martin Ellis，我决定使用TreeMap来解决这个问题。
你的范围是否不重叠？ 如果是这样，您可以使用TreeMap：
TreeMap m = new TreeMap(); 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 V mappedValue(TreeMap map, K key) { Entry 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
这似乎是使用树结构的自然情况。
不幸的是，实现java.util.Map接口是不切实际的，因为它指定了一个返回所有键的方法，在你的情况下，理论上你有一个不切实际的大量键。
树的每个节点都应该有一个最小键，一个最大键和一个与该范围相关的值。 然后，您可以链接到表示下一个较高范围和下一个较低范围的节点（如果存在）。 就像是：
public class RangeMap, V> { protected boolean empty; protected K lower, upper; protected V value; protected RangeMap left, right; public V get(K key) { if (empty) { return null; } if (key.compareTo(lower) < 0) { return left.get(key); } if (key.compareTo(upper) > 0) { return right.get(key); } /* if we get here it is in the range */ return value; } public void put(K from, K to, V val) { if (empty) { lower = from; upper = to; value = val; empty = false; left = new RangeMap(); right = new RangeMap(); return; } if (from.compareTo(lower) < 0) { left.put(from, to, val); return; } if (to.compareTo(upper) > 0) { right.put(from, to, val); return; } /* here you'd have to put the code to deal with adding an overlapping range, however you want to handle that. */ } public RangeMap() { empty = true; } }
如果您需要比树可以提供的更快的查找，您可能希望查看类似跳过列表或开发自己的哈希函数。
除非您找到一种方法来为匹配的范围和单个值生成哈希码，否则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 entries = new ArrayList (); 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
它不是非常有效，因为它只是迭代一个列表，如果你在那里放置冲突范围，它将在该状态下不会抱怨。 只会返回它找到的第一个。
PS：像这样的映射会将一系列键映射到一个值
这种类型的数据结构称为间隔树 。 （维基百科页面仅显示间隔可能重叠的情况，但可以想象在您添加新间隔时要删除任何重叠间隔的映射的情况。执行Google搜索实施并查看是否符合您的需要。
Guava RangeMap 提供开箱即用的专业解决方案：
RangeMap 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"
只需将List作为Map中的值即可。
Map> map = new HashMap>();
还有一个Suggustion ：
除非您想要同步访问，否则不要使用Hashtable。
编辑：
Hashtable方法是同步的，即，没有两个线程可以在单个时间点访问这些方法。 HashMap menthods未同步。 如果你使用Hashtable会有性能损失。 使用HashMap获得更好的性能。
其中一种方法是，使用list实现之一作为key的值。
map.put("A", ArrayList);