418
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Идеальная хеш-функция''' {{---}} [[Хеш-таблица#Хеширование|хеш-функция]], которая без [[Разрешение коллизий|коллизий]] отображает различные элементы из множества объектов на множество ключей за <tex>O(1)</tex> времени.
}}
== Основная идея ==
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
=== Первый уровень ===
Используется тот же принцип, что и в случае хеширования с цепочками: n ключей хешируются в m ячеек с использованием хеш-функции h, выбранной из семейста универсальных хеш-функций.
Сама хеш-функция будет иметь вид h(k) = ((a*k+b) mod p).
=== Второй уровень ===
На данном уровне будет использовать вторичную хеш-таблицу S_j со своей функций h_j. S_j будет хранить все ключи, хешированные в ячейку j. Соответственно, хеш-функция будет вида h_j((a_j*k+b_j) mod p) mod m_j.
Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе. Но для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер m_j хеш-таблицы S_j был равен квадрату числа n_j ключей, хешированных в ячейку j.
{{Теорема
|statement=
Если n ключей сохраняются в хеш-таблице размеров m=n^2 c использованием хеш-функции h, случайно выбранный из универсального множества хеш-функций, то вероятность возникновения коллизий не превыщает 1/2.
|proof=
}}
==См. также==
* [[Хеширование]]
