Сложность получения / ввода HashMap

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

Доступная память - еще одна проблема. Как я понимаю из javadocs, HashMap load factorдолжно быть 0,75. Что делать, если у нас недостаточно памяти в JVM и load factorпредел превышает лимит?

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

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

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

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

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

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

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

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

Операция HashMap зависит от реализации hashCode. Для идеального сценария, допустим, хорошая реализация хеширования, которая предоставляет уникальный хеш-код для каждого объекта (без хеш-коллизии), тогда наилучшим, худшим и средним сценарием будет O (1). Давайте рассмотрим сценарий, в котором плохая реализация hashCode всегда возвращает 1 или такой хэш, который имеет конфликт хешей. В этом случае временная сложность будет O (n).

Теперь, переходя ко второй части вопроса о памяти, тогда да, JVM позаботится об ограничении памяти.

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

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

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

1. HashMap<Integer, V>
2. HashMap<String, V>
3. HashMap<List<E>, V>

У них такая же сложность? Ну, амортизированная сложность 1-го, как и ожидалось, 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», см. Здесь , и в этом случае мемоизация может быть бесполезной.

На практике это O (1), но на самом деле это ужасное и математически бессмысленное упрощение. Обозначение O () говорит о том, как алгоритм ведет себя, когда размер проблемы стремится к бесконечности. Получение / размещение Hashmap работает как алгоритм O (1) для ограниченного размера. Предел довольно велик с точки зрения памяти компьютера и с точки зрения адресации, но далеко не бесконечен.

Когда кто-то говорит, что получение / размещение хэш-карты равно O (1), на самом деле следует сказать, что время, необходимое для получения / размещения, является более или менее постоянным и не зависит от количества элементов в хэш-карте, если хэш-карта может быть представлен на реальной вычислительной системе. Если проблема выходит за пределы этого размера, и нам нужны более крупные хэш-карты, то через некоторое время, безусловно, количество битов, описывающих один элемент, также увеличится, поскольку у нас закончатся возможные описываемые различные элементы. Например, если мы использовали хэш-карту для хранения 32-битных чисел, а затем увеличили размер проблемы, чтобы у нас было более 2 ^ 32-битных элементов в хэш-карте, тогда отдельные элементы будут описаны более чем 32-битными.

Количество битов, необходимых для описания отдельных элементов, равно log (N), где N - максимальное количество элементов, поэтому операции get и put на самом деле равны O (log N).

Если вы сравните его с древовидным набором, который равен O (log n), тогда хэш-набор будет O (long (max (n)), и мы просто чувствуем, что это O (1), потому что в определенной реализации max (n) фиксирован, не меняется (размер хранимых нами объектов измеряется в битах), а алгоритм вычисления хэш-кода работает быстро.

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