Является ли хэш-карта Java действительно O (1)?

Question

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

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

Answer 1

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

р _{столкновений} = п/емкость

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

О (п) = О (к * п)

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

р _{столкновения х 2} = (п/емкость)

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

р _{столкновений ок} = (п/емкость) ^K

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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

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

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

Answer 9

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

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

Answer 10

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

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

Answer 11

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

Answer 12

O(1+n/k) где k является количеством ковшей.

Если наборы для внедрения k = n/alpha, то это O(1+alpha) = O(1) с alpha является постоянной.

Answer 13

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

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

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

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

Answer 14

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

Answer 15

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

location = (arraylength - 1) & keyhashcode 

Здесь & представляет поразрядный оператор.

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

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

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

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