Сопоставление большого набора ключей с небольшим набором значений

Question

Если у вас было 1 000 000 ключей (целых), которые сопоставлены с 10 000 значений (целых).Какой самый эффективный способ (производительность поиска и использование памяти) реализовать.

Предположим, что значения случайные.т. е. не существует диапазона ключей, которые сопоставляются одному значению.

Самый простой подход, который я могу придумать, - это HashMap, но я задаюсь вопросом, можно ли добиться большего успеха, сгруппировав ключи, которые соответствуют одному значению.

Map<Integer,Integer> largeMap = Maps.newHashMap();
largeMap.put(1,4);
largeMap.put(2,232);
...
largeMap.put(1000000, 4);

Answer 1

HashMap - худшее решение.Хеш целого числа сам по себе.Я бы сказал, TreeMap, если вы хотите легко доступное решение.Вы можете написать свою собственную специализированную древовидную карту, например, разделив ключи на две шорты и имея TreeMap внутри Treemap.

Answer 2

Я не уверен, что вы можете многое оптимизировать, группируя что-нибудь.«Обратное» отображение может дать вам немного лучшую производительность, если вы хотите выполнить поиск по значениям, а не по ключу (т.е. получить все ключи с определенным значением), но поскольку вы явно не сказали, что хотите это сделать, я бы не стал »t пойти с этим подходом.

Для оптимизации вы можете использовать массив int вместо карты, если ключи находятся в фиксированном диапазоне.Поиск массива - это O (1), а примитивные массивы используют меньше памяти, чем карты.

int offset = -1;
int[] values = new int[1000000];
values[1 + offset] = 4;
values[2 + offset] = 232;
// ...
values[1000000 + offset] = 4;

Если диапазон не начинается с 1, вы можете адаптировать смещение.

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

Answer 3

Если известно, что набор ключей находится в заданном диапазоне (как показано в вашем примере 1-1000000), то самым простым является использование массива.Проблема заключается в том, что вам нужно искать значения по ключу, и это ограничивает вас либо картой, либо массивом.

Далее используется карта значений для значений просто для того, чтобы избежать дублирования экземпляров объектов с одинаковыми значениями (может быть лучший способ сделать это, но я не могу думать ни о каком).Массив просто служит для поиска значений по индексу:

private static void addToArray(Integer[] array, int key, 
        Integer value, Map<Integer, Integer> map) {

    array[key] = map.putIfAbsent(value, value);
}

И затем значения могут быть добавлены с помощью:

Map<Integer, Integer> keys = new HashMap<>();
Integer[] largeArray = new Integer[1000001];

addToArray(largeArray, 1, 4, keys);
addToArray(largeArray, 2, 232, keys);
...
addToArray(largeArray, 1000000, 4, keys);

Если new Integer[1000001] кажется хаком, вы все равно можете сохранитьсвоего рода «смещение индекса» для указания фактического ключа, связанного с индексом 0 в массиве.

---

И я бы поместил это в класс:

class LargeMap {

    private Map<Integer, Integer> keys = new HashMap<>();
    private Integer[] keyArray;

    public LargeMap(int size) {
        this.keyArray = new Integer[size];
    }

    public void put(int key, Integer value) {
        this.keyArray[key] = this.keys.putIfAbsent(value, value);
    }

    public Integer get(int key) {
        return this.keyArray[key];
    }
}

И:

public static void main(String[] args) {
    LargeMap myMap = new LargeMap(1000_000);

    myMap.put(1, 4);
    myMap.put(2, 232);
    myMap.put(1000_000, 4);
}