Dynamische perfekte Hashing und universelle Hash-Funktionen - Erklärung bitte?

Question

So lese ich, um über die Hash-Tabellen, Hash-Funktionen etc. Ich war fasziniert auf Wikipedia über zu lesen, wie „dynamic perfektes Hashing“ beinhaltet eine zweite Hash-Tabelle als Datenstruktur mehr Werte innerhalb eines bestimmten Eimers zu speichern.

Wo ich aber verloren gehe, ist, wenn es darum geht, wie eine universelle Hash-Funktion ausgewählt wird, um das Hashing für die zweite Hash-Tabelle auszuführen. Kann mir jemand erklären, wie diese universelle Hash-Funktion von den Werten gespeichert werden in den Eimer bestimmt wird? Ich folgende vage die Vernunft und Logik in Wikipedias „universelle Hash-Funktion“ Seite, aber ich kämpfen, um auf sie jede Intuition haben. Insbesondere wie garantieren diese Funktionen keine Auseinandersetzungen? Oder atleast, wenn sie, und ein neues erzeugt angeordnet sind, wenn ein Zusammenstoß erfasst wird, wie können wir wissen, kann dies in einer realistischen Zeitspanne, wenn überhaupt?

Marienkäfer Buch Erklärung bitte?

Answer 1

Perfect Hashing-Mittel, die den Zugriff benötigt konstante Zeit selbst im schlimmsten Fall lesen.

Für Tasten gibt es keine Worst-Case-Garantien, die Zeitgrenzen sind nur wahr im Durchschnitt (oder vielleicht abgeschrieben) eingefügt wird.

Um das Einsetzen schnell genug die zweite Ebene Hashtabelle zu machen, ist sehr groß für die Anzahl der Schlüssel gewählt (k ² ), groß genug, so dass Kollisionen ausreichend unwahrscheinlich geworden. Dies ist kein Problem w.r.t. Größe, weil die erste Ebene Hash verteilt Schlüssel gleichmäßig, so dass im Durchschnitt der zweiten Ebene Hash-Tabellen noch klein sind.

Die Hash-Funktion für die zweite Ebene Tabellen zufällig aus einem Satz von Hash-Funktionen parametrisiert ausgewählt ist.

Answer 2

Wie wäre es mit MIT Vorlesungen gern? :)
des MIT Introduction to Algorithms, Vorträge 7 und 8: Hashing