HashMap получить / поставить сложность

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

Уже упоминалось, что хеш-карты в среднем равны 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).

Answer 4

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

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

Answer 5

Я согласен с:

• общая амортизируемая сложность O (1)
• плохая hashCode() реализация может привести к множественным коллизиям, что означает, что в худшем случаекаждый объект отправляется в одно и то же ведро, то есть O ( N ), если каждое ведение поддерживается List.
• , поскольку Java 8 HashMap динамически заменяет узлы (связанный список), используемые в каждом сегменте, на TreeNodes (красно-черное дерево, когда список становится больше 8 элементов), что приводит к худшей производительности O (* 1013)* logN ).

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

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

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

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

Предположим, что размер всех вышеперечисленных массивов / списков равен 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", см. здесь , в этом случае запоминание может быть бесполезным.

Answer 6

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

Когда кто-то говорит, что get / put hashmap равен O (1), он должен действительно сказать, что время, необходимое для get / put, является более или менее постоянным и не зависит от количества элементов в hashmap, поскольку hashmap может быть представлен на реальной вычислительной системе. Если проблема выходит за рамки этого размера, и нам нужны большие хэш-карты, то через некоторое время количество битов, описывающих один элемент, безусловно, также увеличится, когда у нас закончатся возможные описываемые различные элементы. Например, если мы использовали хэш-карту для хранения 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 различными способами. С этим я могу закодировать информацию бита log (n). Если я могу закодировать это в нулевом бите (это означает, что O (1)), то я создал бесконечно сжатый алгоритм ZIP.