146
правок
Изменения
Нет описания правки
}}
==Постановка задачиОсновная идея =={{Задача|definition=Иногда возникают задачи не с динамическим, а Идеальное хеширование используется в задачах со статическим множеством ключей, (т.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется) для обеспечения хорошей асимптотики даже в худшем случае. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно. Тогда мы можем использовать идеальное хеширование для обеспечения хорошей асимптотики даже в худшем случае.}}
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
=== Первый уровень ===
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 11.5, стр. 308
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563
* [http://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia — 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 Универсальное хэширование. Идеальное хэширование]
