Динамическое идеальное хеширование и универсальные хеш-функции - объясните, пожалуйста?
Итак, я читаю о хеш-таблицах, хеш-функциях и т. Д. Я был заинтригован, чтобы прочитать в википедии о том, как "динамическое идеальное хеширование" предполагает использование второй хеш-таблицы в качестве структуры данных для хранения нескольких значений в конкретном сегменте.
Однако, где я теряюсь, это когда выбирается универсальная хеш-функция для выполнения хэширования для этой второй хеш-таблицы. Кто-нибудь может объяснить, как эта универсальная хеш-функция определяется из значений, хранящихся в корзине? Я смутно следую рассуждениям и логике на странице "универсальной хэш-функции" в Википедии, но изо всех сил пытаюсь получить хоть какую-то интуицию. В частности, как эти функции гарантируют отсутствие конфликтов? Или, по крайней мере, если они удаляются и генерируется новый, если обнаруживается конфликт, как мы узнаем, что это можно сделать за реалистичное количество времени, если вообще?
Объяснение книги божьей коровки, пожалуйста?
2 ответа
Идеальное хеширование означает, что доступ для чтения занимает постоянное время даже в худшем случае.
Для вставки ключей нет гарантий наихудшего случая, временные рамки в среднем верны (или могут быть амортизированы).
Чтобы сделать вставку достаточно быстрой, хеш-таблица второго уровня выбрана очень большой для количества ключей (k2), достаточно большой, чтобы коллизии стали достаточно маловероятными. Это не проблема по размеру, поскольку хэш-таблица первого уровня распределяет ключи равномерно, так что в среднем хеш-таблицы второго уровня все еще невелики.
Хеш-функция для таблиц второго уровня выбирается случайным образом из набора параметризованных хеш-функций.
Как насчет просмотра лекций MIT?:)
Введение в алгоритмы MIT, лекции 7 и 8: хеширование