Dynamisch perfektes Hashing und universelle Hashfunktionen - Erklärung bitte?

Question

Also lese ich über Hash-Tabellen, Hash-Funktionen usw. Ich war fasziniert zu lesen auf Wikipedia darüber, wie "dynamische perfekte Hashing" beinhaltet eine zweite Hash-Tabelle als Datenstruktur zu speichern mehrere Werte in einem bestimmten Eimer.

Wohin ich jedoch verloren gehe, ist, wenn es darum geht, wie eine universelle Hash-Funktion ausgewählt wird, um das Hashing für diese zweite Hash-Tabelle durchzuführen. Kann jemand erklären, wie diese universelle Hash-Funktion aus den im Bucket gespeicherten Werten bestimmt wird? Ich folge vage der Argumentation und Logik auf der "universal hash function" -Seite von wikipedia, kämpfe aber um eine Intuition. Insbesondere, wie garantieren diese Funktionen keine Kollisionen? Oder zumindest, wenn sie entsorgt werden und eine neue generiert wird, wenn ein Konflikt entdeckt wird, woher wissen wir, ob dies in einer realistischen Zeitspanne überhaupt möglich ist?

Marienkäfer Buch Erklärung bitte?

Answer 1

Perfektes Hashing bedeutet, dass Lesezugriff auch im schlimmsten Fall konstante Zeit benötigt.

Für das Einfügen von Schlüsseln gibt es keine Worst-Case-Garantien, die Zeitgrenzen sind nur im Durchschnitt richtig (oder amortisiert).

Um das Einfügen schnell genug zu machen, wird die Hash-Tabelle der zweiten Ebene für die Anzahl der Schlüssel (k) sehr groß gewählt, groß genug, dass Kollisionen ausreichend unwahrscheinlich werden. Dies ist kein Problem w.r.t. Größe, weil der Hash der ersten Ebene die Schlüssel gleichmäßig verteilt, so dass Hashtabellen der zweiten Ebene im Durchschnitt immer noch klein sind.

Die Hash-Funktion für die Tabellen der zweiten Ebene wird zufällig aus einer Menge parametrisierter Hash-Funktionen ausgewählt.

Answer 2

Wie wäre es mit einigen MIT-Vorlesungen? :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing