Dynamiczne doskonałe funkcje haszowania i uniwersalne - wyjaśnienie, proszę?

Question

Więc czytam o tabelach mieszających, funkcjach skrótu itd. Zaintrygowałem się czytaniem na wikipedii o tym, jak "dynamiczne perfekcyjne mieszanie" wymaga użycia drugiej tablicy mieszającej jako struktury danych do przechowywania wielu wartości w danym wiadrze.

Miejsce, w którym się zgubiłem, to jednak, w jaki sposób została wybrana funkcja mieszania uniwersalnego, aby wykonać mieszanie dla tego drugiego stołu mieszającego. Czy ktoś może wyjaśnić, w jaki sposób ta funkcja mieszania uniwersalnego jest określana na podstawie wartości przechowywanych w wiadrze? Mimowolnie podążam za rozumowaniem i logiką w "uniwersalnej funkcji skrótu" Wikipedii, ale staram się mieć jakąkolwiek intuicję. W szczególności, w jaki sposób te funkcje gwarantują brak konfliktów? Lub przynajmniej, jeśli są one usuwane i generowane po wykryciu konfliktu, skąd wiemy, że można to zrobić w realistycznym czasie, jeśli w ogóle?

Proszę o wyjaśnienie książki dla ladybirdów?

Answer 1

Idealne hashing oznacza, że ​​dostęp do odczytu zajmuje stały czas nawet w najgorszym przypadku.

Przy wstawianiu kluczy nie ma gwarancji najgorszego przypadku, ograniczenia czasowe są prawdziwe tylko w średniej cenie (lub mogą być zamortyzowane).

Aby wstawienie było wystarczająco szybkie, stół mieszający drugiego poziomu został wybrany jako bardzo duży dla liczby kluczy (k), wystarczająco duży, aby kolizje stały się wystarczająco mało prawdopodobne. To nie jest problem w.r.t. rozmiar, ponieważ hash pierwszego poziomu dystrybuuje klucze równomiernie, tak że średnie tabele mieszania drugiego poziomu są wciąż małe.

Funkcja mieszania dla tabel drugiego poziomu wybierana losowo z zestawu sparametryzowanych funkcji skrótu.

Answer 2

Co powiesz na oglądanie wykładów MIT? :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing