Действительно ли Java hashmap - это O(1)?

https://stackoverflow.com/questions/1055243

20-08-2019
|

Вопрос

Я видел несколько интересных утверждений о SO re Java hashmaps и их O(1) время поиска.Кто-нибудь может объяснить, почему это так?Если только эти хэш-карты сильно не отличаются от любого из алгоритмов хеширования, на которые я купился, всегда должен существовать набор данных, содержащий коллизии.

В этом случае поиск будет следующим O(n) вместо того , чтобы O(1).

Может ли кто-нибудь объяснить, являются ли они являются O(1) и, если да, то как они этого добиваются?

Решение

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

p_{столкновение} = n / вместимость

Таким образом, хэш-карта даже с небольшим количеством элементов, скорее всего, столкнется по крайней мере с одним столкновением.Обозначение Big O позволяет нам сделать что-то более убедительное.Заметим, что для любой произвольной фиксированной константы k.

O(n) = O(k * n)

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

p_{столкновение x 2} = (н / вместимость)²

Это намного ниже.Поскольку стоимость обработки одного дополнительного столкновения не имеет отношения к производительности Big O, мы нашли способ повысить производительность без фактического изменения алгоритма!Мы можем обобщить это, чтобы

p_{столкновение x k} = (н / вместимость)^k

И теперь мы можем пренебречь некоторым произвольным числом столкновений и в итоге получить исчезающе малую вероятность большего количества столкновений, чем мы учитываем.Вы могли бы довести вероятность до сколь угодно малого уровня, выбрав правильное k, и все это без изменения фактической реализации алгоритма.

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

Другие советы

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

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

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

Таким образом, иногда его придется сравнивать с несколькими элементами, но обычно он намного ближе к 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), относится к среднему ожидаемому времени, а не к строгой производительности в наихудшем случае.Для хэш-таблицы, разрешающей коллизии с помощью цепочки (например, Java hashmap), технически это O (1+ α) с хорошая хэш-функция, где α - коэффициент загрузки таблицы.Остается постоянным до тех пор, пока количество объектов, которые вы сохраняете, не более чем на постоянный коэффициент, превышающий размер таблицы.

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

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

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

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

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

location = (arraylength - 1) & keyhashcode

Здесь & представляет побитовый оператор AND .

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow