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