Изменения
→Второй уровень
=== Второй уровень ===
На данном уровне будет использовать вторичную хеш-таблицу <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 bmod p) \mod bmod m_j</tex>.<br>
Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе. Но для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных в ячейку <tex>j</tex>.
== Метод №1 ==
Будем использовать <tex>O(n^2)</tex> памяти.
