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

159

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

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

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

paxdiablo
источник
1
Я знаю, что это может быть не ответ, но я помню, что в Википедии есть очень хорошая статья об этом. Не пропустите раздел анализа производительности
Виктор Гюго
28
Обозначение Big O дает верхнюю границу для конкретного типа анализа, который вы делаете. Вам все равно следует указать, интересуетесь ли вы наихудшим, средним и т. Д.
Дэн Хомерик,

Ответы:

127

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

р столкновение = н / емкость

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

O (n) = O (k * n)

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

р столкновение х 2 = (н / вместимость) 2

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

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

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

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

SingleNegationElimination
источник
Даже с HTML я все еще не очень доволен дробями. Очистите их, если вы можете придумать хороший способ сделать это.
SingleNegationElimination
4
На самом деле, сказанное выше говорит о том, что эффекты O (log N) скрываются для неэкстремальных значений N с помощью фиксированных накладных расходов.
Hot Licks
Технически, это число, которое вы дали, является ожидаемым значением числа столкновений, которое может равняться вероятности одного столкновения.
Саймон Куанг
1
Это похоже на амортизированный анализ?
lostsoul29
1
@ OleV.V. Хорошая производительность HashMap всегда зависит от хорошего распределения вашей хеш-функции. Вы можете обменять лучшее качество хэша на скорость хэширования, используя криптографическую функцию хэширования на своем входе.
SingleNegationElimination
38

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

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

Конрад Рудольф
источник
6
Я всегда думал, что верхняя граница - это худший случай, но, похоже, я ошибся - верхнюю границу можно получить для среднего случая. Таким образом, похоже, что люди, претендующие на О (1), должны были дать понять, что это для среднего случая. Худший случай - это набор данных, где есть много коллизий, делающих его O (n). Это имеет смысл сейчас.
paxdiablo
2
Вы, вероятно, должны прояснить, что когда вы используете большие обозначения O для среднего случая, вы говорите о верхней границе ожидаемой функции времени выполнения, которая является четко определенной математической функцией. В противном случае ваш ответ не имеет большого смысла.
ldog
1
gmatt: я не уверен, что понимаю ваше возражение: нотация big-O является верхней границей функции по определению . Что еще я мог иметь в виду?
Конрад Рудольф
3
ну, обычно в компьютерной литературе вы видите большие обозначения O, представляющие верхнюю границу функций времени выполнения или пространственной сложности алгоритма. В этом случае верхняя граница фактически соответствует ожиданию, которое само по себе является не функцией, а оператором функций (случайных величин) и фактически является интегралом (lebesgue). Не следует принимать тот факт, что вы можете связать такую ​​вещь. как должное и не тривиально.
ldog
31

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

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

FogleBird
источник
11
Ну, поскольку big-O должен указывать пределы, не имеет значения, приближается ли он к O (1) или нет. Четный O (n / 10 ^ 100) все еще O (n). Я понимаю вашу точку зрения о снижении эффективности, но это все равно ставит алгоритм на уровне O (n).
paxdiablo
4
Анализ хэш-карт обычно выполняется в среднем случае, который составляет O (1) (со сговорами). В худшем случае вы можете иметь O (n), но обычно это не так. относительно разницы - O (1) означает, что вы получаете одно и то же время доступа независимо от количества элементов на графике, и это обычно имеет место (при условии, что есть хорошая пропорция между размером таблицы и 'n ')
Лиран Ореви
4
Стоит также отметить, что это все еще точно O (1), даже если сканирование контейнера занимает некоторое время, потому что в нем уже есть некоторые элементы. Пока корзины имеют фиксированный максимальный размер, это просто постоянный коэффициент, не относящийся к классификации O (). Но, конечно, может быть добавлено еще больше элементов с «похожими» ключами, так что эти сегменты переполняются, и вы больше не можете гарантировать постоянство.
STH
@sth Почему у ведер будет фиксированный максимальный размер?
Навин
31

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

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

Дэниел Джеймс
источник
16

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

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

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

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

AJB
источник
4

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

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

IJ Кеннеди
источник
4

O(1+n/k)где kколичество ведер

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

Сатьянараяна Каколлу
источник
1
Что означает постоянная альфа ?
Прахалад Дешпанде
2

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

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

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

JTB
источник
2

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

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

Антти Уима
источник
2

Элементы внутри 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).

Ramprabhu
источник
1

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

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

Тобиас Свенссон
источник
1
Это предполагает, что время выполнения ограничено временем поиска. На практике вы найдете много ситуаций, когда хеш-функция обеспечивает границу (String)
Стефан Эггермонт
1

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

Низар Грира
источник
1

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

Райан Эмерл
источник
4
Не в практических приложениях. Как только вы используете строку в качестве ключа, вы заметите, что не все хеш-функции идеальны, а некоторые действительно медленны.
Стефан Эггермонт
1

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

sn.anurag
источник
0

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

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

Серая пантера
источник
«это в большинстве случаев». Более конкретно, общее время будет стремиться к K умноженному на N (где K является постоянным), когда N стремится к бесконечности.
ChrisW
7
Это не верно. Индекс в хеш-таблице будет определяться с помощью hashCode % tableSizeчего, безусловно, могут быть коллизии. Вы не в полной мере используете 32-битные. В этом вся суть хеш-таблиц ... вы уменьшаете большое пространство индексации до небольшого.
FogleBird
1
«вам гарантировано, что столкновений не будет» Нет, вы не потому, что размер карты меньше размера хеша: например, если размер карты равен двум, тогда гарантируется столкновение (не имеет значения какой хэш) если / когда я пытаюсь вставить три элемента.
ChrisW
Но как преобразовать ключ в адрес памяти в O (1)? Я имею в виду, как х = массив ["ключ"]. Ключ не является адресом памяти, поэтому он все равно должен быть поиском O (n).
paxdiablo
1
«Я считаю, что если вы не реализуете hashCode, он будет использовать адрес памяти объекта». Это можно использовать, но по умолчанию hashCode для стандартного Oracle Java на самом деле представляет собой 25-битное случайное число, хранящееся в заголовке объекта, поэтому 64/32-битный не имеет значения.
Boann