Изменения
→Второй уровень
На данном уровне будемльзовать вторичную хеш-таблицу <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>h</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>.
