有效地遍历hashmap中的所有MATCHING键？ [英] Efficiently iterate through all MATCHING keys in a hashmap?

问题描述

我有一个带有数百万条目的 HashMap 。

需要检索所有与特定关键字匹配的条目（在这种情况下，每个键是一个具有两个整数属性的对象;我需要检索所有这些整数都在指定范围内的键）。

什么是最快，最有效的方法遍历所有这些键？

更新：
在这种特殊情况下我没有在前面指定它，键中的第一个整数优先于第二个整数。

解决方案

解决方案使用 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; （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 =新Foo（高，高）; 
 
 Foo fromKey = map.ceilingKey（key1）; 
 Foo toKey = map.floorKey（key2）; 
 
 if（fromKey！= null&& toKey！= null&& fromKey.compareTo（toKey）< 0）
返回新的ArrayList< Foo>（map.subMap （fromKey，true，toKey，true）.keySet（））; 
返回新的ArrayList< Foo>（）; 
} 
 
 public static class Foo implements Comparable< Foo> {
 private int i; 
 private int j; 
 
私人Foo（int i，int j）{
 super（）; 
 this.i = i; 
 this.j = j; 
 
 
 public int min（）{
 if（i  return i; 
 else 
 return j; 
 
 
 public int max（）{
 if（i> j）
 return i; 
 else 
 return j; 
} 
 
 @Override 
 public String toString（）{
 returnI =+ i +J =+ j; 
} 
 
 @Override 
 public int compareTo（Foo o）{
 if（this.min（）> o.min（））{
返回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; 
} 
} 
} 
  

I have a HashMap with millions of entries.

Need to retrieve all entries whose keys match a specific set of criteria (in this case, each key is an object with two integer properties; I need to retrieve all keys where each of these integers fall within a specified range).

What is the fastest, most efficient way to iterate through all such keys?

UPDATE: In this particular case, though I didn't specify it up front, the first integer in the key has a natural precedence over the second integer.

解决方案

Here's a solution using 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;
        }
    }
}

这篇关于有效地遍历hashmap中的所有MATCHING键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！