418
правок
Изменения
Нет описания правки
'''Идеальная хеш-функция''' {{---}} [[Хеш-таблица#Хеширование|хеш-функция]], которая без [[Разрешение коллизий|коллизий]] отображает различные элементы из множества объектов на множество ключей за <tex>O(1)</tex> времени.
}}
== Практический смысл ==
Задача идеального хеширования возникает тогда, когда возникает необходимость проверять наличие элемента (скажем, слова из словаря) за гарантировано константное время. При этом подразумевается, что набор данных в таблице статичен либо изменяется очень редко.
== Основная идея ==
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
=== Первый уровень ===
Используется тот же принцип, что и в случае хеширования с цепочками: <tex>n </tex> ключей хешируются в <tex>m </tex> ячеек с использованием хеш-функции <tex>h</tex>, выбранной из семейста семейства универсальных хеш-функций.Сама хеш-функция будет иметь вид <tex>h(k) = ((a*k+b) \mod p)</tex>.
=== Второй уровень ===
На данном уровне будет использовать вторичную хеш-таблицу <tex>S_j </tex> со своей функций <tex>h_j</tex>. <tex>S_j </tex> будет хранить все ключи, хешированные в ячейку <tex>j</tex>. Соответственно, хеш-функция будет вида <tex>h_j((a_j*k+b_j) \mod p) \mod 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> памяти.{{Теорема|statement=Если <tex>n</tex> ключей сохраняются в хеш-таблице размером <tex>m=n^2</tex> c использованием хеш-функции <tex>h</tex>, случайно выбранный из универсального множества хеш-функций, то вероятность возникновения коллизий не превышает <tex dpi="180">{1 \over 2}</tex>.|proof=Всего имеется <tex>\dbinom{n}{2}</tex> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из универсального семейства хеш-функций H, то для каждой пары вероятность возникновения коллизии равна <tex dpi="180">{1 \over m}</tex>. Пусть <tex>X</tex> - случайная величина, которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то математическое ожидание числа коллизий равно<tex>E[X] = </tex> <tex dpi="180"> \binom{n}{2} * {1 \over n^2} = {n^2-n \over n} * {1 \over n^2} < {1 \over 2}</tex>Это является очень хорошим результатом, если хотя бы вспомнить на примере [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#.D0.92.D0.B2.D0.B5.D0.B4.D0.B5.D0.BD.D0.B8.D0.B5 парадокса дней рождения] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.}}Как видно вероятность возникновения коллизий== Метод №2 ==Будем использовать <tex>O(n)</tex> памяти.
{{Теорема
|statement=
Если мы сохраняем <tex>n </tex> ключей сохраняются в хеш-таблице в хеш-таблице размеров <tex>m=n^2 </tex> c использованием хеш-функции <tex>h</tex>, случайно выбранный выбираемой случайным образом из универсального множества хеш-функций, то вероятность возникновения коллизий не превыщает <tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex>, где <tex>n_j</2tex> - количество ключей, хешированных в ячейку <tex>j</tex>.
|proof=
<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] = E\left[ \displaystyle \sum_{j=0}^{m-1} (n_j + 2 \dbinom{n_j}{2})\right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} n_j\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} (n_j 2)\right]= E\left[n\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] = n + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2} \right]</tex><br>
Очевидно, что <tex>\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}</tex> - просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает
<tex dpi="180">\binom{n}{2}{1 \over m} = {n(n-1) \over 2m} = {n-1 \over 2}</tex>
А так как <tex>m = n</tex>, то
<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] \leqslant n + 2*{n-1 \over 2} = 2n - 1 < 2n</tex>, ч.т.д.
}}
==См. также==
* [[Хеширование]]
* [http://en.wikipedia.org/wiki/Perfect_hash_function Perfect hash function {{---}} Wikipedia]
* [http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0215.pdf Universal and Perfect Hashing]
* [http://nord.org.ua/static/course/algo_2009/lecture8.pdf Универсальное хэширование. Идеальное хэширование]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Хеширование]]
