Изменения

== Практический смысл Постановка задачи ==Задача идеального хеширования возникает тогда, когда возникает необходимость Необходимо проверять наличие элемента (скажем, слова из словаря) за гарантировано константное время. При этом подразумевается, что набор данных в таблице статичен либо изменяется очень редко.

На данном уровне будет использовать будемльзовать вторичную хеш-таблицу <tex>S_j</tex> со своей функций <tex>h_j</tex>. <tex>S_j</tex> будет хранить все ключи, хешированные в ячейку <tex>j</tex>. Соответственно, хеш-функция будет вида <tex>h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j</tex>.<br>

Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе. Но для Для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных в ячейку <tex>j</tex>. Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе.

Хеш-функция первого уровня выбирается из множества <tex>H_{p,m}</tex>, где <tex>p</tex> - простое число, превышающее значение любого из ключей. Ключи, хешированные функцией <tex>h</tex> в ячейку <tex>j</tex>, затем повторно хешируются во вторичную хеш-таблицу <tex>S_j</tex> размером <tex>m_j</tex> с использованием хеш-функции <tex>h_j</tex> , выбранной из множества <tex>H_{p,m_j}</tex>. == Теоретическое обоснование ==