418
правок
Изменения
Нет описания правки
=== Второй уровень ===
На данном уровне вместо создания списка ключей будем использовать вторичную хеш-таблицу <tex>S_j</tex>, хранящей хранящую все ключи, хешированные функцией <tex>h</tex> в ячейку <tex>j</tex>, со своей функцией <tex>h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j</tex>, выбранной из множества <tex>H_{p,m_j}</tex>. Путем точного выбора хеш-функции <tex>h_j</tex> мы можем гарантировать отсутствие коллизий на этом уровне. Для этого требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных функцией <tex>h</tex> в ячейку <tex>j</tex>.
Не смотря на квадратичную зависимость, ниже будет показано, что при корректном выборе хеш-функции первого уровня ожидаемое количество требуемой для хеш-таблицы памяти будет <tex>O(n)</tex>.
== Теоретическое обоснование ==
