Я видел несколько интересных утверждений о SO хэш-картах Java и времени их O(1)
поиска. Может кто-нибудь объяснить, почему это так? Если эти хеш-карты не сильно отличаются от любого из алгоритмов хэширования, на которые я был куплен, всегда должен существовать набор данных, содержащий коллизии.
В этом случае поиск будет, O(n)
а не O(1)
.
Может кто-нибудь объяснить, являются ли они О (1) и, если да, то как они этого добиваются?
java
hashmap
big-o
time-complexity
paxdiablo
источник
источник
Ответы:
Особенностью HashMap является то, что в отличие, скажем, от сбалансированных деревьев, его поведение является вероятностным. В этих случаях обычно наиболее полезно говорить о сложности с точки зрения вероятности возникновения события в худшем случае. Для хэш-карты это, конечно, случай столкновения с точки зрения того, насколько полной является карта. Столкновение довольно легко оценить.
Таким образом, хэш-карта с даже небольшим количеством элементов может столкнуться хотя бы с одним столкновением. Обозначение Big O позволяет нам делать что-то более убедительное. Заметим, что для любой произвольной фиксированной константы k.
Мы можем использовать эту функцию для улучшения производительности хэш-карты. Вместо этого мы могли бы думать о вероятности не более двух столкновений.
Это намного ниже. Поскольку стоимость обработки одного дополнительного столкновения не имеет отношения к производительности Big O, мы нашли способ повысить производительность без фактического изменения алгоритма! Мы можем обобщить это
И теперь мы можем игнорировать произвольное количество столкновений и в конечном итоге с крошечной вероятностью возникновения большего числа столкновений, чем мы учитываем. Вы можете получить вероятность до сколь угодно крошечного уровня, выбрав правильный k, и все это без изменения фактической реализации алгоритма.
Мы говорим об этом, говоря, что хэш-карта имеет O (1) доступ с высокой вероятностью
источник
Вы, кажется, смешиваете поведение наихудшего случая со средним (ожидаемым) временем выполнения. Первый действительно O (n) для хеш-таблиц в целом (т.е. не использует идеальное хеширование), но на практике это редко актуально.
Любая надежная реализация хеш-таблицы в сочетании с наполовину приличным хеш-кодом имеет производительность извлечения O (1) с очень небольшим коэффициентом (фактически 2) в ожидаемом случае в пределах очень узкой границы дисперсии.
источник
В Java HashMap работает, используя hashCode для поиска сегмента. Каждое ведро - это список предметов, находящихся в этом ведре. Элементы сканируются с использованием равных для сравнения. При добавлении элементов размер HashMap изменяется после достижения определенного процента загрузки.
Поэтому иногда приходится сравнивать несколько элементов, но обычно это намного ближе к O (1), чем к O (n). Для практических целей это все, что вам нужно знать.
источник
Помните, что o (1) не означает, что каждый поиск проверяет только один элемент - это означает, что среднее количество проверенных элементов остается постоянным по отношению к количеству элементов в контейнере. Таким образом, если в среднем требуется 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), это технически O (1 + α) с хорошей хеш-функцией , где α - коэффициент загрузки таблицы. Все еще остается неизменным, пока количество сохраняемых вами объектов не более чем на постоянный коэффициент, превышающий размер таблицы.
Также было объяснено, что, строго говоря, возможно построить входные данные, которые требуют O ( n ) поиска для любой детерминированной хэш-функции. Но также интересно рассмотреть наихудшее ожидаемое время, которое отличается от среднего времени поиска. При использовании цепочки это O (1 + длина самой длинной цепочки), например, log (log n / log log n ), когда α = 1.
Если вам интересны теоретические способы достижения ожидаемого поиска в худшем случае с постоянным временем, вы можете прочитать о динамическом совершенном хешировании, которое рекурсивно разрешает коллизии с другой хеш-таблицей!
источник
Это O (1), только если ваша функция хеширования очень хорошая. Реализация хеш-таблицы Java не защищает от неправильных хеш-функций.
Нужно ли увеличивать таблицу, когда вы добавляете элементы, или нет, это не имеет отношения к вопросу, потому что это время поиска.
источник
Элементы внутри HashMap хранятся в виде массива связанного списка (узла), каждый связанный список в массиве представляет собой корзину для уникального хеш-значения одного или нескольких ключей.
При добавлении записи в HashMap хеш-код ключа используется для определения местоположения сегмента в массиве, например:
Здесь & представляет побитовый оператор AND.
Например:
100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")
Во время операции get он использует тот же способ, чтобы определить местоположение корзины для ключа. В лучшем случае каждый ключ имеет уникальный хэш-код и приводит к уникальному сегменту для каждого ключа, в этом случае метод get тратит время только на определение местоположения сегмента и получение значения, которое является постоянным O (1).
В худшем случае все ключи имеют одинаковый хэш-код и хранятся в одном и том же сегменте, что приводит к обходу всего списка, что приводит к O (n).
В случае java 8 корзина со связанным списком заменяется на TreeMap, если размер увеличивается до более чем 8, это снижает эффективность поиска в худшем случае до O (log n).
источник
Это в основном относится к большинству реализаций хеш-таблиц в большинстве языков программирования, поскольку сам алгоритм на самом деле не меняется.
Если в таблице нет коллизий, вам нужно выполнить только один просмотр, поэтому время выполнения O (1). Если присутствуют коллизии, вам нужно выполнить более одного поиска, что снижает производительность в сторону O (n).
источник
Это зависит от алгоритма, который вы выбираете, чтобы избежать столкновений. Если ваша реализация использует отдельную цепочку, то в худшем случае происходит, когда каждый элемент данных хэшируется с одинаковым значением (например, плохой выбор хеш-функции). В этом случае поиск данных ничем не отличается от линейного поиска в связанном списке, т.е. O (n). Тем не менее, вероятность того, что это произойдет, незначительна, и поиск лучших и средних случаев остается постоянным, т.е. O (1).
источник
Помимо академических соображений, с практической точки зрения HashMaps следует воспринимать как несущественное влияние на производительность (если ваш профилировщик не скажет вам иначе).
источник
Только в теоретическом случае, когда хеш-коды всегда различны, и корзина для каждого хеш-кода также различна, O (1) будет существовать. В противном случае он имеет постоянный порядок, то есть при увеличении hashmap порядок поиска остается постоянным.
источник
Конечно, производительность hashmap будет зависеть от качества функции hashCode () для данного объекта. Однако, если функция реализована так, что вероятность столкновений очень мала, она будет иметь очень хорошую производительность (это не строго O (1) в каждом возможном случае, но в большинстве случаев).
Например, реализация по умолчанию в Oracle JRE заключается в использовании случайного числа (которое хранится в экземпляре объекта, чтобы оно не менялось - но оно также отключает смещенную блокировку, но это другое обсуждение), поэтому вероятность коллизий очень низкий.
источник
hashCode % tableSize
чего, безусловно, могут быть коллизии. Вы не в полной мере используете 32-битные. В этом вся суть хеш-таблиц ... вы уменьшаете большое пространство индексации до небольшого.