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

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

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

Приложение

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

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

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

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

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

Выполнение

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

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

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

Смотрите также

• Функция хэширования
• Динамическое идеальное хеширование

Ссылки

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