Является ли Java hashmap действительно O (1)?

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

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

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

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

помните, что o (1) не означает, что каждый поиск проверяет только один элемент - это означает, что среднее количество проверенных элементов остается постоянным w.r.t. количество элементов в контейнере. Поэтому, если требуется в среднем 4 сравнения, чтобы найти элемент в контейнере с 100 элементами, он также должен взять в среднем 4 сравнения, чтобы найти элемент в контейнере с 10000 элементами и для любого другого количества элементов (всегда есть немного дисперсии, особенно вокруг точек, в которых хэш-таблица перефразирует, и когда есть очень небольшое количество элементов).

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

Я знаю, это старый вопрос, но есть новый ответ.

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

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

на самом деле, Java 8 реализует ведра как TreeMaps Как только они превышают порог, который делает фактическое время O(log n).

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

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

O(1+n/k) здесь k количество ведер.

если реализация устанавливает k = n/alpha затем O(1+alpha) = O(1) С alpha - константа.

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

Это также было объяснено, что, строго говоря, можно построить вход, который требует O (n) поиск любой детерминированной хэш-функции. Но также интересно рассмотреть наихудший случай ожидается времени, которое отличается от среднего времени поиска. Используя цепочку Это O (1 + Длина самой длинной цепи), например Θ (log n / log log n) при α=1.

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

Это O (1) только если ваша функция хэширования очень хороша. Реализация хэш-таблицы Java не защищает от плохих хэш-функций.

нужно ли выращивать в таблице при добавлении элементов или нет не имеет отношения к вопросу, потому что речь идет о времени просмотра.

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

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

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

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

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

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

location = (arraylength - 1) & keyhashcode

здесь & представляет побитовое и оператор.

например: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

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

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

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

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

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