(Когда) поиск по хеш-таблице O (1)?

Часто говорят, что поиск в хеш-таблице работает в постоянное время: вы вычисляете значение хеш-функции, которое дает вам индекс для поиска в массиве. Все же это игнорирует столкновения; в худшем случае каждый предмет попадает в одно и то же ведро, и время поиска становится линейным ( ).$\Theta(n)$

Существуют ли условия для данных, которые могут сделать поиск в хэш-таблице действительно ? Это только в среднем, или хеш-таблица может иметь поиск в худшем случае?O ( 1 $O(1)$$O(1)$

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

PS Последующие действия: для каких типов данных используются операции с хэш-таблицами O (1)?

Есть две настройки, при которых вы можете получить худшее время.$O(1)$

1. Если ваша установка статична, то хеширование FKS даст вам гарантии худшем случае . Но, как вы указали, ваши настройки не являются статичными.$O(1)$

2. Если вы используете Кукушка хэширования, то запросы и удалений являются в худшем случае, но вставка только ожидается. Хеширование с кукушкой работает довольно хорошо, если у вас есть верхняя граница для общего числа вставок и вы установите размер таблицы примерно на 25% больше.O ( 1 $O(1)$$O(1)$

Там больше информации здесь .

Этот ответ суммирует части TAoCP Vol 3, гл. 6.4.

Предположим, у нас есть набор значений , из которых мы хотим сохранить в массиве размером . Мы используем хеш-функцию ; как правило,, Мы называем коэффициент нагрузки по . Здесь мы примем натуральное ; в практических сценариях у нас есть , и мы должны отобразить самостоятельно.n A m h : V → [ 0 .. M ) M ≪ | V | α = $V$$n$$A$$m$$h : V \to [0..M)$$M \ll |V|$ Am=Mm≪M$\alpha = \frac{n}{m}$$A$$m=M$$m \ll M$$m$

Первое наблюдение состоит в том, что даже если имеет одинаковые характеристики, вероятность того, что два значения имеют одинаковое значение хеш-функции, высока; по сути, это пример печально известного парадокса дня рождения . Поэтому нам обычно приходится иметь дело с конфликтами, и мы можем отказаться от надежды на время доступа в худшем случае.O ( 1 $h$$\mathcal{O}(1)$

А как насчет среднего случая, хотя? Предположим, что каждый ключ из встречается с одинаковой вероятностью. Среднее количество проверенных записей (успешный поиск) соотв. (неудачный поиск) зависит от используемого метода разрешения конфликтов.C S n C U $[0..M)$$C_n^S$$C_n^U$

Цепной

Каждая запись массива содержит (указатель на начало) связанных списков. Это хорошая идея, потому что ожидаемая длина списка мала ( ), даже если вероятность возникновения коллизий высока. В конце мы получаем Это можно немного улучшить, сохранив списки (частично или полностью) внутри таблицы. C S n ≈1+$\frac{n}{m}$

$$C_n^S \approx 1 + \frac{\alpha}{2} \quad \text{ and } \quad C_n^U \approx 1 + \frac{\alpha^2}{2} .$$

Линейное зондирование

При вставке (соответственно поиске значения) проверяйте позиции в этом порядке до пустой позиции (соотв. ) найдено. Преимущество в том, что мы работаем локально и без вторичных структур данных; тем не менее, число средних обращений расходится для : Однако для производительность сопоставима с цепочкой².$v$

$$h(v), h(v)-1,\dots,0,m-1,\dots,h(v)+1$$ $v$$\alpha \to 1$ $$C_n^S \approx \frac{1}{2}\left(1 +\frac{1}{1-\alpha}\right) \quad \text{ and } \quad C_n^U \approx \frac{1}{2}\left(1 +\left(\frac{1}{1-\alpha}\right)^2\right).$$ $\alpha < 0.75$

Двойное хеширование

Подобно линейным зондированием , но размер шага поиска управляется с помощью второго хеш - функции , которая является взаимно простое с . Формальный вывод не приводится, но эмпирические наблюдения показывают, что Этот метод был адаптирован Брентом; его вариант амортизирует повышенные затраты на вставку с помощью более дешевых поисков.$M$

$$C_n^S \approx \frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\quad \text{ and } \quad C_n^U \approx \frac{1}{1-\alpha} .$$

Обратите внимание, что удаление элементов из таблиц и их расширение имеет различную степень сложности для соответствующих методов.

В итоге, вы должны выбрать реализацию, которая хорошо адаптируется к вашим типичным случаям использования. Ожидаемое время доступа в возможно, если не всегда гарантировано. В зависимости от используемого метода поддержание низком уровне имеет важное значение; Вы должны обменять (ожидаемое) время доступа на пространство над головой. Хороший выбор для также центральный, очевидно.$\mathcal{O}(1)$$\alpha$$h$

---

1] Поскольку произвольно тупые неосведомленные программисты могут предоставить , любое предположение относительно его качества является натяжкой на практике. 2] Обратите внимание, что это совпадает с рекомендациями по использованию Java .$h$
Hashtable

Совершенная хэш - функция может быть определена как инъективная функция из множества на подмножество целых чисел . Если для ваших данных и хранилищ существует идеальная хеш-функция, вы можете легко получить поведение . Например, вы можете получить производительность из хэш - таблицы для следующей задачи: даны массив целых чисел и множество целых чисел, определить , является ли содержит для каждого . Этап предварительной обработки будет включать создание хэш-таблицы в последующей проверкой каждого элемента на соответствие$S$$\{0, 1, 2, ..., n\}$$O(1)$$O(1)$$l$$S$$l$$x$$x \in S$$O(|l|)$$S$$O(|S|)$ . В целом это . Наивной реализацией, использующей линейный поиск, может быть ; используя бинарный поиск, вы можете выполнить (обратите внимание, что это решение - пространство , так как хеш-таблица должна отображать различные целые числа в в различные элементы).$O(|l| + |S|)$$O(|l||S|)$$O(\log(|l|)|S|)$$O(|l|)$$l$

РЕДАКТИРОВАТЬ: Чтобы уточнить, как генерируется хэш-таблица в :$O(|l|)$

Список содержит целые числа от конечного множества , возможно , с повторами и . Мы хотим определить, находится ли в . Для этого мы предварительно вычисляем хеш-таблицу для элементов : справочную таблицу. Хеш-таблица будет кодировать функцию . Для того, чтобы определить , сначала предположим для всех . Затем линейно сканируйте элементы of , задав . Это занимает время и$l$$U \subset \mathbb{N}$$S \subseteq U$$x \in S$$l$$l$$h: U \rightarrow \{true, false\}$$h$$h(x) = false$$x \in U$$y$$l$$h(y) = true$$O(|l|)$$O(|U|)$ пространство.

Обратите внимание, что мой первоначальный анализ предполагал, что содержит как минимум различных элементов. Если он содержит меньше различных элементов (скажем, ), требования к пространству могут быть выше (хотя это не более ).$l$$O(|U|)$$O(|1|)$$O(|U|)$

EDIT2: хэш-таблица может быть сохранена в виде простого массива. Хэш - функция может быть тождественной функции на . Обратите внимание, что единичная функция является тривиальной идеальной хеш-функцией. является хеш-таблицей и кодирует отдельную функцию. Я неуклюжий / запутанный в некоторых из вышеупомянутых, но постараюсь улучшить это в ближайшее время.$U$$h$

Идеальная хеш-функция приведет к поиску в худшем случае.$\cal{O}(1)$

Более того, если максимальное возможное число коллизий равно , то в худшем случае можно найти поиска в хеш-таблице . Если ожидаемое количество столкновений равно , то можно сказать, что поиск в хэш-таблице в среднем случае равен .O ( 1 ) O ( 1 ) O ( 1 $\cal{O}(1)$$\cal{O}(1)$$\cal{O}(1)$$\cal{O}(1)$