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

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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