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

71

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

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

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

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

Жиль "ТАК - перестань быть злым"
источник
3
Можете ли вы жить с амортизированным временем доступа? В общем, производительность хеш-таблицы будет сильно зависеть от того, сколько накладных расходов на разреженные хеш-таблицы вы готовы терпеть, и от того, как распределяются фактические значения хеш-таблиц. O(1)
Рафаэль
5
О, кстати: вы можете избежать линейного поведения в худшем случае, используя (сбалансированные) деревья поиска вместо списков.
Рафаэль
1
@ Рафаэль Меня очень заинтересовал бы ответ, который объясняет (в общих чертах), когда я могу рассчитывать на амортизацию а когда - нет. Что касается того, как распределяются значения хешей, это действительно часть моего вопроса: как я могу знать? Я знаю, что хеш-функции должны хорошо распределять значения; но если бы они всегда делали, худший случай никогда не был бы достигнут, что не имеет смысла. O(1)
Жиль "ТАК - перестань быть злым"
1
Также будьте осторожны с преждевременной оптимизацией; для небольших данных (несколько тысяч элементов) я часто видел, как сбалансированные двоичные деревья превосходят хеш-таблицы из-за меньших издержек (сравнение строк значительно дешевле, чем хэши строк). O(logn)
isturdy

Ответы:

41

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

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

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

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

Суреш
источник
3
Не могли бы вы расширить FKS и Cuckoo? Оба условия являются новыми для меня.
Жиль "ТАК - перестань быть злым"
1
Как насчет динамического идеального хеширования? Он имеет поиск в худшем случае и амортизированные вставки и удаления. ( citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8165 )O ( 1 )O(1)O(1)
Джо
2
FKS являются инициалами (Фредман, Komlós, Szemerédi), а Cuckoo - название вида бридов. Это использование для этого типа перемешивания, потому что птенцы кукушки выталкивают яйца сибилингов из гнезда. Это напоминает то, как функционирует этот метод хэширования.
Ули
1
@Suresh: Действительно? Я думал, что вам нужны -независимые функции, которые я всегда ассоциировал с необходимостью расширений. Я стою исправлено. Немного удалим мой комментарий. logn
Луи
1
Чтобы сделать более полезный комментарий к этому ответу, как отмечает @Suresh, хеширование кукушки будет хорошо работать без причудливых (и больших) хеш-функций, используемых для теоретического анализа.
Луи
21

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

Предположим, у нас есть набор значений , из которых мы хотим сохранить в массиве размером . Мы используем хеш-функцию ; как правило,, Мы называем коэффициент нагрузки по . Здесь мы примем натуральное ; в практических сценариях у нас есть , и мы должны отобразить самостоятельно.n A m h : V [ 0 .. M ) M | V | α = nVnAmh:V[0..M)M|V| Am=MmMmα=nmAm=MmMm

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

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

Цепной

Каждая запись массива содержит (указатель на начало) связанных списков. Это хорошая идея, потому что ожидаемая длина списка мала ( ), даже если вероятность возникновения коллизий высока. В конце мы получаем Это можно немного улучшить, сохранив списки (частично или полностью) внутри таблицы. C S n1+αnm

CnS1+α2 and CnU1+α22.

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

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

h(v),h(v)1,,0,m1,,h(v)+1
vα1
CnS12(1+11α) and CnU12(1+(11α)2).
α<0.75

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

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

CnS1αln(11α) and CnU11α.

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

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


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

Рафаэль
источник
10

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

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

Список содержит целые числа от конечного множества , возможно , с повторами и . Мы хотим определить, находится ли в . Для этого мы предварительно вычисляем хеш-таблицу для элементов : справочную таблицу. Хеш-таблица будет кодировать функцию . Для того, чтобы определить , сначала предположим для всех . Затем линейно сканируйте элементы of , задав . Это занимает время иlUNSUxSllh:U{true,false}hh(x)=falsexUylh(y)=trueO(|l|)O(|U|) пространство.

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

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

Patrick87
источник
Не могли бы вы расширить часть, где вы делаете хеш-таблицу в ? Я могу понять, как это сделать, если вы не беспокоитесь о столкновениях, но это означает, что последующие поиски могут занять больше, чем , вплоть до . O(|l|)O(|S|)O(|l||S|)
Жиль "ТАК - перестань быть злым"
Я не понимаю определение . Вы определяете функцию, но не объясняете, как она представлена; не могли бы вы написать несколько строк псевдокода? Есть также проблема обозначений; и bijective не подходят друг другу. hh:U{false,true}h
Жиль "ТАК - перестань быть злым"
@Gilles В основном это просто таблица поиска для членства в списке. Когда у вас есть идеальная хеш-функция с известным и дешевым обратным преобразованием, вместо того, чтобы хранить саму вещь, вам нужно хранить только 1 бит (независимо от того, была ли добавлена ​​вещь с уникальным хешем). Если возможны коллизии, я думаю, что это называется фильтром Блума, но в любом случае может дать определенное «нет» вопросу о членстве, что все еще полезно во многих сценариях.
Patrick87
9

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

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

Николас Мейер
источник
Идеальная хеш-функция была бы идеальной, но как мне ее получить? Сколько это будет стоить мне? И как мне узнать, какое максимальное или ожидаемое количество столкновений?
Жиль "ТАК - перестань быть злым"
2
@ Gilles идеальная хеш-функция - это любая функция, которая создаст уникальный хеш для всех возможных входных данных. Если ваши возможные входные данные конечны (и уникальны), это легко сделать.
Rafe Kettler
1
@RafeKettler Мои входные данные обычно являются строками или составными структурами данных, и я обычно добавляю и удаляю записи по мере развития моих данных. Как мне сделать идеальный хеш для этого?
Жиль "ТАК - перестань быть злым"
4
Да, но в этом все дело. Детерминированная совершенная хеш-функция не существует, если домен больше диапазона.
Суреш
@Suresh: если вам разрешено выбирать новую хеш-функцию и увеличивать размер таблицы при возникновении коллизии, вы всегда можете найти (детерминированную) хеш-функцию, которая - для данных, уже находящихся в таблице, плюс одна новая элемент, который вы пытаетесь вставить - не имеет коллизий («идеально»). Вот почему динамическое идеальное хеширование периодически выбирает случайную новую хеш-функцию.
Дэвид Кэри