418
правок
Изменения
Нет описания правки
== Постановка задачи ==
== Основная идея ==
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
=== Первый уровень ===
Используется тот же принцип, что и в случае хеширования с цепочками: <tex>n</tex> ключей хешируются в <tex>m</tex> ячеек с использованием хеш-функции <tex>h(k) = ((a\cdot k+b) \bmod p)</tex>, тщательно выбранной из [[Универсальное_семейство_хеш-функций | семейства универсальных хеш-функций]].Сама хеш-функция будет иметь вид <tex>h(k) = ((a\cdot k+b) \bmod H_{p,m}</tex>, где <tex>p)</tex>- простое число, превышающее значение любого из ключей.
=== Второй уровень ===
На данном уровне вместо создания списка ключей будем использовать вторичную хеш-таблицу <tex>S_j</tex> со своей функций <tex>h_j</tex>. , хранящей все ключи, хешированные функцией <tex>S_jh</tex> будет хранить все ключи, хешированные в ячейку <tex>j</tex>. Соответственно, хеш-функция будет вида со своей функцией <tex>h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j</tex>, выбранной из множества <tex>H_{p,m_j}</tex>. Путем точного выбора хеш-функции <tex>h_j</tex> мы можем гарантировать отсутствие коллизий на этом уровне. Для этого требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных функцией <tex>h</tex> в ячейку <tex>j</tex>.
== Необходимые условия ==
Для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных функцией <tex>h</tex> в ячейку <tex>j</tex>. Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе.
== Теоретическое обоснование ==
