HashMap vs Array search Сложность времени

Question

Итак, у меня есть карта HashMap, содержащая ~ 120 000 записей. Каждый раз, когда появляется новая запись, я проверяю, существует ли уже запись в HashMap (if (! Map.containsKey (hashcode))), и если это не так, я создаю новый объект и помещаю его в HashMap.

Теперь мой вопрос: было бы лучше создать логический массив NxN (с N = 6.000) и каждый раз проверять, является ли элемент массива в [n1] [n2] ложным (еще не в hashmap) или истинным ( пара находится в HashMap) вместо использования .containsKey ()?

Answer 1

Map имеет computeIfAbsent() метод, который делает именно то, что вам нужно:

• Если указанный ключ еще не связан со значением (или сопоставлен
• to {@code null}), пытается вычислить его значение, используя заданное отображение
• функция и вводит ее в эту карту, если {@code null}. *

• Если функция возвращает {@code null}, отображение не записывается. Если

• сама функция выдает (непроверенное) исключение,
• исключение перебрасывается, и отображение не записывается. Самый
• Обычное использование - это создание нового объекта, служащего начальным
• сопоставленное значение или запомненный результат

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

Answer 2

Нет, containsKey - прекрасный способ. HashMaps имеют обычный поиск O (1), поэтому это не должно быть проблемой, если только хранимые объекты не имеют плохо реализованного алгоритма хеширования. Единственный вопрос может быть, почему у вас так много записей в HashMap?

Answer 3

Видите ли, HashMap имеет временную сложность O (1), поэтому проверка с помощью containsKey - лучшее решение в вашем случае.