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

Question

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

В этом случае поиск будет O(n), а не O(1).

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

Answer 1

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

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

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

O (n) = O (k * n)

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

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

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

Answer 6

O(1+n/k), где k - количество сегментов.

Если реализация устанавливает k = n/alpha, то это O(1+alpha) = O(1), поскольку alpha является константой.

Answer 7

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

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

Answer 8

Элементы внутри HashMap хранятся в виде массива связанного списка (узла), каждый связанный список в массиве представляет собой корзину для уникального хеш-значения одного или нескольких ключей.
При добавлении записи в 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 корзина со связанным списком заменяется на TreeMap, если размер увеличивается до более чем 8, это снижает эффективность поиска в худшем случае до O (log n).

Answer 9

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

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

Answer 10

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

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

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