Hashtable- Reashing
Mir wurde gesagt, dass Hashtable in .NET eine Umwertung verwendet, um Kollisionen zu reduzieren / vermeiden.
Dh. "Rehasing funktioniert wie folgt: Angenommen, wir haben eine Reihe von Hash-Funktionen, H1 ... Hn, und beim Einfügen oder Abrufen eines Elements aus der Hash-Tabelle wird zunächst die H1-Hash-Funktion verwendet. Wenn dies zu einer Kollision führt, wird H2 stattdessen bis Hn probiert, um eine Kollision in Hashtable zu vermeiden. "
Annahme: Wir haben eine Hashtabelle mit n (wobei n & supmin; unendlich ist), wo die asymptotische Zeitkomplexität o (1) ist; Wir (CLR) haben dies erreicht, während wir eine Hashing-Funktion anwenden (Hn-1-Hash-Funktion, wobei n & gt; 1).
Frage: Kann mir jemand erklären, wie CLR den Schlüssel zum Hash-Code abbildet, wenn wir irgendein Element suchen (abrufen) (wenn unterschiedliche Hash-Funktionen verwendet werden)? Wie CLR verfolgen (wenn es) die Hash-Funktion eines Live-Objekts (Hash-Tabelle)?
Vielen Dank im Voraus
1 Antwort
Die zufällige Auswahl einer Hash-Funktion ist als Universal Hashing bekannt. AFAIK Die Hash-Funktion wird einmal pro Initialisierungsprozess ausgewählt. Dies ist kein echter Fall, wenn im Bereich einer einzelnen Hash-Tabelle mehrere Hash-Funktionen verwendet wurden.
BEARBEITEN: Weitere Details
Gerade wieder zu Hause, öffnete "Einführung in Algorithmen" T. Cormen Buch und fand im folgenden Abschnitt 11.3.3 Universal Hashing :
Der Grundgedanke hinter universellem Hashing ist die Auswahl der Hash-Funktion zufällig aus einer sorgfältig gestalteten Klasse von Funktionen an der Beginn der Ausführung
Sie können weitere Informationen lesen, indem Sie das Buch auf der Google Books-Website ansehen hier
Tags und Links c# hashtable universal-hashing