我HashMap有数百万个条目。
需要检索其键与一组特定条件匹配的所有条目（在这种情况下，每个键都是具有两个整数属性的对象；我需要检索其中每个整数都在指定范围内的所有键）。
迭代所有这些键的最快、最有效的方法是什么？
更新： 在这种特殊情况下，虽然我没有预先指定它，但键中的第一个整数自然优先于第二个整数。
DanM
问问题
6066 次
7 回答
7
HashMap 不是用于查找位于特定范围内的键的有效数据结构。通常，您可以在散列映射中有效找到的唯一键是与您拥有的具有相同散列的键（即相等键）。
要查找位于某个范围内的键，最好使用某种类型的SortedMap，例如 TreeMap，然后可以使用 SortedMap.subMap(low, high) 视图方法查看。
至于根据两把钥匙找一把钥匙，那就更难了。您最好的选择可能是遍历第一个整数范围的 subMap，然后检查每个整数是否在指定范围内。这至少将扫描限制在范围内具有整数之一的键。尝试根据整数对地图进行排序，该整数在您可能必须搜索的可能范围内具有更自然的值分布。
于 2009-02-11T17:50:33.847 回答
3
这是使用TreeMap的解决方案：
public static void main(String[] args) {
Comparator<Foo> fooComparator = new Comparator<Foo>() {
@Override
public int compare(Foo o1, Foo o2) {
return o1.compareTo(o2);
}
};
TreeMap<Foo, String> map = new TreeMap<Foo, String>(fooComparator);
map.put(new Foo(1, 4), "");
map.put(new Foo(1, 3), "");
map.put(new Foo(2, 4), "");
map.put(new Foo(3, 4), "");
map.put(new Foo(8, 10), "");
map.put(new Foo(8, 17), "");
map.put(new Foo(10, 10), "");
int a = 2;
int b = 5;
for (Foo f : getKeysInRange(map, a, b)) {
System.out.println(f);
}
}
public static List<Foo> getKeysInRange(TreeMap<Foo, String> map, int low, int high) {
Foo key1 = new Foo(low, low);
Foo key2 = new Foo(high, high);
Foo fromKey = map.ceilingKey(key1);
Foo toKey = map.floorKey(key2);
if (fromKey != null && toKey != null && fromKey.compareTo(toKey) < 0)
return new ArrayList<Foo>(map.subMap(fromKey, true, toKey, true).keySet());
return new ArrayList<Foo>();
}
public static class Foo implements Comparable<Foo> {
private int i;
private int j;
private Foo(int i, int j) {
super();
this.i = i;
this.j = j;
}
public int min() {
if (i < j)
return i;
else
return j;
}
public int max() {
if (i > j)
return i;
else
return j;
}
@Override
public String toString() {
return "I=" + i + "J=" + j;
}
@Override
public int compareTo(Foo o) {
if (this.min() > o.min()) {
return 1;
} else if (this.min() < o.min())
return -1;
else {
if (this.max() > o.max())
return 1;
else if (this.max() < o.max())
return -1;
else
return 0;
}
}
}
于 2009-02-11T18:49:13.067 回答
1
如果不遍历整个 keySet，您将无法做到这一点。
如果您确定不会有其他条目具有与这些整数属性相同的值，则可以使用带有排序条件的 TreeMap，该条件将按两个整数属性的某种组合进行排序，然后您可以找到第一个直接匹配，然后从那里迭代到第一个不匹配。但您似乎不太可能达到这些条件。
因为集合的开销非常低（所有内容都通过引用存储），我会考虑制作两个排序集合，可能是 TreeSet，一个按第一个属性排序，一个按第二个属性排序，然后从两个集合并将它们结合在一起。
于 2009-02-11T17:50:30.010 回答
1
bruno conde 提供的解决方案是一个好的开始。但是，我阅读原始问题的方式是 key Object 包含两个整数，问题是关于检索与第一个整数的一个范围匹配并与第二个整数匹配第二个范围的所有键/值对的最快方法整数。布鲁诺解决方案假设键具有自然顺序，其中第一个整数始终优先于第二个整数。它还假设只有一个范围。
对于这种更一般的情况，我会： 使用有利于 integer1 的比较器将键/值插入到 TreeMap 使用有利于 integer2 的比较器将相同的键/值插入到第二个 TreeMap
然后，您可以使用范围在每个 TreeMap 上使用 subMap() 来获取底层 TreeMap 的有序视图。然后，您可以根据这些 subMap 的 keySet() 的交集 (retainAll()) 创建一个新的结果 TreeSet。
于 2009-02-11T20:24:32.210 回答
0
可能不会有比以下更快的解决方案：
for (final KeyObj key : map.keySet()) {
// do work
}
于 2009-02-11T17:49:35.363 回答
0
如果TreeSet由于某种原因 a 不起作用，则迭代的标准方法是使用条目集。
for (Map.Entry<MyKeyType, MyValueType> entry : myMap.entrySet()) {
MyKeyType key = entry.getKey();
if (isValid(key)) {
// do whatever
validList.add(entry.getValue());
}
}
这样，您不必额外myMap.get(key)调用有效密钥。
于 2009-02-11T17:49:55.190 回答