Динамическое идеальное хеширование и универсальные хэш-функции – поясните, пожалуйста?

Question

Итак, я читаю о хеш-таблицах, хэш-функциях и т. д.Я был заинтригован, прочитав в Википедии о том, как «динамическое идеальное хеширование» предполагает использование второй хэш-таблицы в качестве структуры данных для хранения нескольких значений в определенном сегменте.

Однако я теряюсь, когда дело доходит до того, как выбирается универсальная хеш-функция для выполнения хеширования для этой второй хеш-таблицы.Может ли кто-нибудь объяснить, как эта универсальная хэш-функция определяется на основе значений, хранящихся в корзине?Я смутно следую рассуждениям и логике на странице «универсальной хеш-функции» в Википедии, но изо всех сил пытаюсь понять это.В частности, как эти функции гарантируют отсутствие конфликтов?Или, по крайней мере, если они удаляются и создается новый в случае обнаружения конфликта, как мы узнаем, что это можно сделать в реалистичные сроки, если вообще?

Объяснение книги «Божья коровка», пожалуйста?

Answer 1

Идеальное хеширование означает, что доступ для чтения занимает постоянное время даже в худшем случае.

Для вставки ключей нет никаких гарантий наихудшего случая, временные ограничения верны только в среднем (или, возможно, амортизируются).

Чтобы вставка была достаточно быстрой, хеш-таблица второго уровня выбирается очень большой по числу ключей (k²), достаточно большой, чтобы столкновения стали достаточно маловероятными.Это не проблема.размер, потому что хэш первого уровня распределяет ключи равномерно, так что в среднем хеш-таблицы второго уровня все еще малы.

Хэш-функция для таблиц второго уровня выбирается случайным образом из набора параметризованных хеш-функций.

Answer 2

Как насчет того, чтобы посмотреть лекции MIT?:)
Введение в алгоритмы Массачусетского технологического института, лекции 7 и 8:Хеширование