Эффективно перебирать все СОВПАДАЮЩИЕ ключи в хэш-карте?

Вот решение с использованием 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 не является эффективной структурой данных для поиска ключей, лежащих в определенном диапазоне. Как правило, единственные ключи, которые вы можете эффективно найти в хэш-карте, — это ключи с тем же хешем, что и у вас (т. е. равными ключами).

Для поиска ключей, лежащих в определенном диапазоне, лучше использовать SortedMap какого-либо вида, например TreeMap, который затем можно просмотреть с помощью метода просмотра SortedMap.subMap(low, high).

Что касается поиска ключа по двум ключам, это еще сложнее. Лучше всего, вероятно, выполнить итерацию по подкарте диапазона первого целого числа, а затем проверить для каждого, попадает ли второе целое число в указанный диапазон. Это, по крайней мере, ограничивает сканирование ключами, которые имеют одно из целых чисел в пределах диапазона. Попробуйте отсортировать карту на основе целого числа, которое имеет более естественное распределение значений в возможных диапазонах, которые вам, возможно, придется искать.

Вы не можете сделать это без повторения всего набора ключей.

Вы можете использовать TreeMap с критериями сортировки, которые будут сортироваться по некоторой комбинации двух целочисленных свойств, если вы уверены, что у вас не будет других записей с тем же значением этих целочисленных свойств, и тогда вы можете найти первый совпадение напрямую, а затем просто итерации оттуда до первого несовпадения. Но маловероятно, что вы сможете достичь таких условий.

Поскольку у коллекций довольно низкие накладные расходы (все хранится по ссылке), я бы подумал о создании двух отсортированных коллекций, возможно, TreeSets, отсортированных по первому свойству и отсортированных по второму, а затем выбрать все значения, которые соответствуют критериям из обе коллекции и объединить их вместе.

Решение, предложенное Бруно Конде, является хорошим началом. Однако то, как я прочитал исходный вопрос, заключается в том, что ключевой объект содержит два целых числа, и что вопрос касался самого быстрого способа получения всех пар ключ/значение, которые соответствуют одному диапазону для первого целого числа и соответствуют второму диапазону для второго целое число. Решение Бруно предполагает, что ключи имеют естественный порядок, при котором первое целое число всегда имеет приоритет над вторым целым числом. Также предполагается, что существует только один диапазон.

Для этого более общего случая я бы: вставил ключ/значения в TreeMap, используя компаратор, который поддерживает целое число1, вставил тот же ключ/значение во второй TreeMap, используя компаратор, который поддерживает целое число2

Затем вы можете использовать subMap() для каждой TreeMap, используя диапазон, чтобы получить упорядоченное представление базовой TreeMap. Затем вы можете создать новый результирующий TreeSet на основе пересечения (retainAll()) keySet() этих подкарт.

Скорее всего, не будет более быстрого решения, чем что-то вроде:

for (final KeyObj key : map.keySet()) {
    // do work
}

Если победил TreeSet по какой-то причине не работает, стандартный способ итерации - с набором записей.

for (Map.Entry<MyKeyType, MyValueType> entry : myMap.entrySet()) {
    MyKeyType key = entry.getKey();
    if (isValid(key)) {
        // do whatever
        validList.add(entry.getValue());
    }
}

Таким образом, вам не нужно делать дополнительный вызов myMap.get(key) для действительных ключей.

Возможно, вы захотите рассмотреть какую-то базу данных SQL, например, в памяти, например Derby или H2. Многое зависит от того, насколько это важно и насколько важно, чтобы это было быстро. Затем вы можете сделать это в SQL и позволить движку выполнить всю работу по оптимизации.