Идеальное хеширование
| Определение: |
| Идеальная хеш-функция — хеш-функция, которая без коллизий отображает различные элементы из множества объектов на множество ключей за времени. |
Основная идея
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
Первый уровень
Используется тот же принцип, что и в случае хеширования с цепочками: 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.
| Теорема: |
Если n ключей сохраняются в хеш-таблице размеров m=n^2 c использованием хеш-функции h, случайно выбранный из универсального множества хеш-функций, то вероятность возникновения коллизий не превыщает 1/2. |
