146
правок
Изменения
Нет описания правки
== Основная идея ==
Идеальное хеширование используется в задачах со статическим множеством ключей (т.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется) для обеспечения хорошей асимптотики даже в худшем случае. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно.
В таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций (одной или нескольких), что делает данный подход наибыстрейшим для доступа к статическим данным. Данная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
Тогда <tex>P \left \{\displaystyle \sum_{j=0}^{m-1} m_j \geqslant 4n \right \} \leqslant E\left[\displaystyle\sum_{j=0}^{m-1} mj\right]</tex> <tex dpi="150"> {1 \over 4n} < </tex> <tex dpi="150">{2n \over 4n} = {1 \over 2}</tex>, ч.т.д.
}}
==См. также==
* [[Хеширование]]
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563
* [http://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia — Perfect hash function]
* [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 Универсальное хэширование. Идеальное хэширование]
