HashMap get/put сложность
Мы привыкли говорить, что операции HashMap
get/put
- это O (1). Однако это зависит от реализации хэша. Хэш-объект по умолчанию - это фактически внутренний адрес в куче JVM. Мы уверены, что достаточно хорошо утверждать, что get/put
являются O (1)?
Доступная память - еще одна проблема. Как я понимаю из javadocs, HashMap
load factor
должен быть 0,75. Что делать, если у нас недостаточно памяти в JVM, а load factor
превышает лимит?
Итак, похоже, что O (1) не гарантируется. Это имеет смысл или я что-то упускаю?
Ответы
Ответ 1
Это зависит от многих вещей. Обычно это O (1), с приличным хешем, который сам по себе является постоянным временем... но у вас может быть хэш, который занимает много времени, и если в хэш-карте есть несколько элементов, которые возвращают один и тот же хеш-код, get
придется перебирать по ним вызов equals
для каждого из них, чтобы найти совпадение.
В худшем случае a HashMap
имеет поиск O (n) из-за прохождения через все записи в том же ведро хэша (например, если все они имеют одинаковый хеш-код). К счастью, этот худший сценарий не возникает очень часто в реальной жизни, по моему опыту. Поэтому нет, O (1), конечно, не гарантируется, но обычно это то, что вы должны учитывать при рассмотрении того, какие алгоритмы и структуры данных использовать.
В JDK 8 была изменена HashMap
, поэтому, если ключи можно сравнить для упорядочения, то любое заполненное жиром ведро реализуется как дерево, так что даже если есть много записей с одним и тем же хеш-кодом, сложность O (log n). Это может вызвать проблемы, если у вас есть тип ключа, в котором равенство и порядок различаются, конечно.
И да, если у вас недостаточно памяти для хэш-карты, у вас будут проблемы... но это будет правда, какая структура данных вы используете.
Ответ 2
Я не уверен, что хэш-код по умолчанию - это адрес. Я читал источник OpenJDK для генерации hashcode некоторое время назад, и я помню, что это было что-то более сложное. По-видимому, это не то, что гарантирует хорошее распределение. Тем не менее, это в некоторой степени спорным, так как несколько классов, которые вы будете использовать в качестве ключей в HashMap использовать хэш-код по умолчанию -. Они предоставляют свои собственные реализации, которые должны быть хорошо
Кроме того, то, что вы, возможно, не знаете (опять же, это основано на источнике чтения - это не гарантировано) заключается в том, что HashMap перемешивает хэш перед его использованием, смешивая энтропию из всего слова в нижние биты, что где это необходимо для всех, кроме самых больших хэшмапов. Это помогает справиться с хэшами, которые специально не делают этого сами, хотя я не могу придумать какие-либо распространенные случаи, когда вы это увидите.
Наконец, то, что происходит, когда таблица перегружена, состоит в том, что она вырождается в набор параллельных связанных списков - производительность становится O (n). В частности, количество пройденных каналов будет в среднем составлять половину коэффициента нагрузки.
Ответ 3
Уже упоминалось, что hashmaps O(n/m)
в среднем, если n
- количество элементов, а m
- размер. Также было упомянуто, что в принципе все это может рухнуть в односвязный список с временем O(n)
запроса. (Все это предполагает, что вычисление хеша является постоянным временем).
Однако то, что не часто упоминается, заключается в том, что с вероятностью не менее 1-1/n
(так что для 1000 предметов с вероятностью 99,9%) наибольшее количество ковша не будет заполнено больше, чем O(logn)
! Следовательно, соответствие средней сложности двоичных деревьев поиска. (И константа хороша, более жесткая граница (log n)*(m/n) + O(1)
).
Все, что требуется для этой теоретической оценки, состоит в том, что вы используете достаточно хорошую хеш-функцию (см. Wikipedia: Universal Hashing. Это может быть как просто как a*x>>m
). И, конечно, человек, дающий вам значения хэшу, не знает, как вы выбрали свои случайные константы.
TL; DR: с очень высокой вероятностью худший случай get/put сложности хэш-карты O(logn)
.
Ответ 4
Операция HashMap является зависимым фактором реализации hashCode. Для идеального сценария можно сказать, что хорошая хэш-реализация, которая предоставляет уникальный хеш-код для каждого объекта (отсутствие хеш-коллизии), тогда лучшим, худшим и средним сценарием будет O (1).
Давайте рассмотрим сценарий, когда плохая реализация hashCode всегда возвращает 1 или такой хэш, который имеет хеш-коллизию. В этом случае временной сложностью будет O (n).
Теперь, перейдя ко второй части вопроса о памяти, тогда да, ограничение памяти будет зависеть от JVM.
Ответ 5
На практике это O (1), но на самом деле это ужасное и математически бессмысленное упрощение. Запись O() говорит о том, как алгоритм ведет себя, когда размер задачи стремится к бесконечности. Hashmap get/put работает как алгоритм O (1) для ограниченного размера. Предел достаточно велик для памяти компьютера и с точки зрения адресации, но далеко от бесконечности.
Когда кто-то говорит, что hashmap get/put равен 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.
Ответ 6
Я согласен с:
- общая амортизированная сложность O (1)
- неудачная
hashCode()
может привести к нескольким столкновениям, что означает, что в худшем случае каждый объект переходит в одно и то же ведро, таким образом, O (N), если каждый ковш поддерживается List
. - поскольку Java 8
HashMap
динамически заменяет узлы (связанные списки), используемые в каждом ведре с TreeNodes (красно-черное дерево, когда список превышает 8 элементов), что приводит к худшей производительности O (logN).
Но, это НЕ полная правда, если мы хотим быть на 100% точнее. Реализация hashCode()
, тип ключевого Object
(неизменяемый/кэшированный или являющийся коллекцией) может также влиять на реальную сложность в строгих терминах.
Предположим следующие три случая:
-
HashMap<Integer, V>
-
HashMap<String, V>
-
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
Но вышеупомянутое также имеет свой худший случай, потому что реализация Java String.hashCode()
проверяет, hash == 0
перед вычислением hashCode
. Но, эй, есть непустые строки, которые выводят hashcode
нуля, например "f5a5a608", см. Здесь, и в этом случае memoization может оказаться нецелесообразным.