Изменения

Перейти к: навигация, поиск

Идеальное хеширование

582 байта добавлено, 11:01, 13 июня 2013
Нет описания правки
Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе. Но для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных в ячейку <tex>j</tex>.
 
Хеш-функция первого уровня выбирается из множества <tex>H_{p,m}</tex>, где <tex>p</tex> - простое число, превышающее значение любого из ключей. Ключи, хешированные в ячейку <tex>j</tex>, затем повторно хешируются во вторичную хеш-таблицу <tex>S_j</tex> размером <tex>m_j</tex> с использованием хеш-функции <tex>h_j</tex> , выбранной из множества <tex>H_{p,m_j}</tex>.
== Метод №1 ==
Анонимный участник

Навигация