Efficiently iterate through all MATCHING keys in a hashmap?

Question

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.

Answer 1

A HashMap is not an efficient data structure for finding keys that lie within a certain range. Generally the only keys you can find efficiently in a hash map are keys with the same hash as what you have (i.e. equal keys).

For finding keys that lie within a certain range, you are better off using a SortedMap of some kind, such as a TreeMap, which can then be viewed with the SortedMap.subMap(low, high) view method.

As for finding a key based on two keys, that is even more difficult. Your best bet is probably to iterate over the subMap of the range of the first integer, and then to check for each one if the second integer falls within the specified range. This at least limits the scan to the keys which have one of the integers within the range. Try to sort the map based on the integer that has a more natural distribution of values over the possible ranges you might have to search for.

Answer 2

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;
        }
    }
}