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

Попробуйте jsPerf . Это онлайн-инструмент для работы с javascript для сравнения и сравнения фрагментов кода. Я использую его все время.

148
задан UmNyobe 23 October 2014 в 07:46
поделиться

11 ответов

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

p collision = n / capacity

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

O (n) = O (k * n)

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

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

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

p collision xk = (n / capacity) k

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

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

122
ответ дан 23 November 2019 в 22:06
поделиться

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

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

1
ответ дан 23 November 2019 в 22:06
поделиться

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

1
ответ дан 23 November 2019 в 22:06
поделиться

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

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

28
ответ дан 23 November 2019 в 22:06
поделиться

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

1
ответ дан 23 November 2019 в 22:06
поделиться

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

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

4
ответ дан 23 November 2019 в 22:06
поделиться

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

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

0
ответ дан 23 November 2019 в 22:06
поделиться

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

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

36
ответ дан 23 November 2019 в 22:06
поделиться

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

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

29
ответ дан 23 November 2019 в 22:06
поделиться

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2
ответ дан 23 November 2019 в 22:06
поделиться

It is O(1) only if your hashing function is very good. The Java hash table implementation does not protect against bad hash functions.

Whether you need to grow the table when you add items or not is not relevant to the question because it is about lookup time.

2
ответ дан 23 November 2019 в 22:06
поделиться
Другие вопросы по тегам:

Похожие вопросы: