418
правок
Изменения
м
→Первый уровень
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
=== Первый уровень ===
Используется тот же принцип, что и в случае хеширования с цепочками: <tex>n</tex> ключей хешируются в <tex>m</tex> ячеек с использованием хеш-функции <tex>h</tex>, выбранной из [[Универсальное_семейство_хеш-функций | семейства универсальных хеш-функций]].
Сама хеш-функция будет иметь вид <tex>h(k) = ((a*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*k + b_j) \mod p) \mod m_j</tex>.<br>
