Эффективно перебрать все ключи соответствия в хэш-карте?

Question

У меня есть HashMap с миллионами записей.

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

Какой самый быстрый и эффективный способ перебора всех таких ключей?

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

Answer 1

HashMap не является эффективной структурой данных для поиска ключей, которые находятся в определенном диапазоне. Как правило, единственными ключами, которые вы можете эффективно найти в хэш-карте, являются ключи с таким же хешем, что и у вас (т.е. равные ключи).

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

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

Answer 2

Вот решение с использованием 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;
        }
    }
}

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

Если 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) вызов для получения действительных ключей.

Answer 7

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

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