Временная сложность операции Hashmap get () и put () - это O (1) во все времена [дублировать]

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

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

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

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

Уже упоминалось, что hashmaps являются 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: С очень высокой вероятностью худший случай get / put сложность хэш-карты O(logn).

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

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

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