Статическое хеширование

Статическое хеширование — это форма хеширования , при которой поиск выполняется по окончательному набору словарей (все объекты в словаре являются окончательными и неизменяемыми).

Использование ^[1]

Приложение

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

Идеальное хеширование

Идеальное хеширование — это модель хеширования, в которой любой набор $n$ элементы могут храниться в хеш-таблице одинакового размера, и поиск может выполняться за постоянное время. Он был специально открыт и обсуждался Фредманом, Комлосом и Семереди (1984) и поэтому получил название «FKS-хеширование». ^[2]

FKS-хеширование

Хеширование FKS использует хеш-таблицу с двумя уровнями, верхний уровень которых содержит $n$ сегменты, каждый из которых содержит свою собственную хеш-таблицу. Хеширование FKS требует, чтобы в случае возникновения коллизий они происходили только на верхнем уровне.

Выполнение

Верхний уровень содержит случайно созданную хеш-функцию. $h(x)$ , которая соответствует ограничениям хеш-функции Картера и Вегмана из универсального хеширования . После этого верхний уровень должен содержать $n$ ведра с маркировкой $k_{1},k_{2},k_{3},...,k_{n}$ . Следуя этому шаблону, все сегменты содержат хеш-таблицу размером $s_{i}$ и соответствующая хэш-функция $h_{i}(x)$ . Хэш-функция будет определена путем установки $s_{i}$ к $k_{i}^{2}$ и случайным образом перебирать функции до тех пор, пока не будет никаких коллизий. Это можно сделать за постоянное время.

Производительность

Потому что есть $n \choose 2$ пары элементов, вероятность столкновения которых равна $1/n$ , хеширование FKS может рассчитывать на строго меньше, чем $n/2$ столкновения. На основании этого факта и того, что каждый $h(x)$ выбиралось так, чтобы количество столкновений было не более $n/2$ , размер каждой таблицы нижнего уровня будет не больше, чем $2n$ .

См. также

Ссылки

^ Дэниел Рош (2013). SI486D: Случайность в вычислениях, блок хеширования . Военно-морская академия США, факультет компьютерных наук.
^ Майкл Фредман; Янош Комлос; Эндре Семереди (1984). Сохранение разреженной таблицы со временем доступа в худшем случае O(1) . Журнал АКМ (Том 31, Выпуск 3).

[Roche2013-1] Дэниел Рош (2013). SI486D: Случайность в вычислениях, блок хеширования . Военно-морская академия США, факультет компьютерных наук.

[FKS1984-2] Майкл Фредман; Янош Комлос; Эндре Семереди (1984). Сохранение разреженной таблицы со временем доступа в худшем случае O(1) . Журнал АКМ (Том 31, Выпуск 3).

[1]

[2]

Использование [1]