HashMap get/put complexity

Мы привыкли говорить, что HashMap get/put операции равны O (1). Однако это зависит от реализации хэша. Хэш объекта по умолчанию на самом деле является внутренним адресом в куче JVM. Мы уверены, что это достаточно хорошо, чтобы утверждать, что get/put равно O(1)?

Еще одна проблема - доступная память. Насколько я понимаю из javadocs, HashMap коэффициент загрузки должен быть 0,75. Что делать, если у нас недостаточно памяти в JVM и коэффициент загрузки превышает предельный?

Итак, похоже, что O (1) не гарантируется. Имеет ли это смысл или я что-то упускаю?

Это зависит от многих факторов. Это обычно O (1) с приличным хэшем, который сам по себе является постоянным временем... но у вас может быть хэш, вычисление которого занимает много времени, и если в хэш-карте есть несколько элементов, которые возвращают один и тот же хэш-код, get придется перебирать их, вызывая equals для каждого из них, чтобы найти соответствие.

В худшем случае a HashMap выполняет поиск O (n) из-за обхода всех записей в одной и той же корзине хэшей (например, если все они имеют одинаковый хэш-код). К счастью, по моему опыту, такой наихудший сценарий не очень часто встречается в реальной жизни. Итак, нет, O (1), конечно, не гарантируется, но обычно это то, что вы должны предполагать, рассматривая, какие алгоритмы и структуры данных использовать.

В JDK 8, HashMap был изменен таким образом, что если ключи можно сравнивать для упорядочивания, то любая густонаселенная корзина реализуется в виде дерева, так что даже если есть много записей с одинаковым хэш-кодом, сложность равна O (log n). Это может вызвать проблемы, если у вас есть тип ключа, в котором равенство и порядок отличаются, конечно.

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

Уже упоминалось, что хэш-карты имеют O(n/m) среднее значение, если n - количество элементов и m - размер. Также упоминалось, что в принципе все это может свернуться в односвязный список со O(n) временем запроса. (Все это предполагает, что вычисление хэша занимает постоянное время).

Однако, что не часто упоминается, так это то, что с вероятностью не менее 1-1/n (так что для 1000 элементов это вероятность 99,9%) самая большая корзина не будет заполнена больше, чем O(logn)! Следовательно, соответствует средней сложности бинарных деревьев поиска. (И константа хорошая, более жесткая граница (log n)*(m/n) + O(1)).

Все, что требуется для этой теоретической оценки, это использование достаточно хорошей хэш-функции (см. Википедия: Универсальное хэширование. Это может быть так же просто, как a*x>>m). И, конечно, человек, который дает вам значения для хэша, не знает, как вы выбрали свои случайные константы.

TL; DR: С очень высокой вероятностью сложность получения / размещения хэш-карты в наихудшем случае равна O(logn).

Я согласен с:

• общая амортизированная сложность O (1)


• плохая hashCode() реализация может привести к множественным конфликтам, что означает, что в худшем случае каждый объект попадает в один и тот же сегмент, таким образом, O (N), если каждый сегмент поддерживается a List.


• начиная с Java 8, HashMap узлы (связанный список), используемые в каждом сегменте, динамически заменяются TreeNodes (красно-черное дерево, когда список становится больше 8 элементов), что приводит к худшей производительности O (logN).

Но это не полная правда, если мы хотим быть на 100% точными. Реализация hashCode() и тип ключа Object (неизменяемый / кэшированный или являющийся коллекцией) также могут строго влиять на сложность в реальном времени.

Давайте предположим следующие три случая:

1. HashMap<Integer, V>


2. HashMap<String, V>


3. HashMap<List<E>, V>

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

Предположим, что размер всех вышеупомянутых массивов / списков равен k. Тогда HashMap<String, V> и HashMap<List<E>, V> будут иметь O (k) амортизированную сложность и, аналогично, O (k + logN) наихудший случай в Java8.

* Обратите внимание, что использование String ключа является более сложным случаем, потому что он неизменяем, а Java кэширует результат hashCode() в закрытой переменной hash, поэтому он вычисляется только один раз.

/** Cache the hash code for the string */
    private int hash; // Default to 0

Но в приведенном выше примере также есть свой наихудший случай, потому что String.hashCode() реализация Java проверяет, является ли это hash == 0 перед вычислением hashCode. Но, эй, есть непустые строки, которые выводят значение, равное hashcode нулю, например "f5a5a608", смотрите Здесь, и в этом случае запоминание может оказаться бесполезным.

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

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

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