Ich versuche zu verstehen, wie Hashtables in C # funktionieren. Ich lese den MSDN-Artikel und ich verstehe, dass C # Hashtables 'rehashing' für Kollisionen verwenden, dh wenn ich versuche, ein Schlüssel / Wert-Paar in die Hashtabelle einzufügen, wenn HashFunction H1 zu einer Kollision führt, wird es HashFunction H2, H3 versuchen usw., bis keine Kollisionen gefunden werden.
MSDN Zitat:
Die Hashtable-Klasse verwendet eine andere Technik, die als bezeichnet wird Rehasing. (Einige Quellen beziehen sich auf das Wiederhashing als doppeltes Hashing.)
Das Umstellen funktioniert wie folgt: Es gibt verschiedene Hash-Werte Funktionen, H1 ... Hn, und beim Einfügen oder Abrufen eines Elements aus In der Hash-Tabelle wird zunächst die H1-Hash-Funktion verwendet. Wenn das dazu führt Bei einer Kollision wird stattdessen H2 und bei Bedarf bis zu Hn versucht. Der vorherige Abschnitt zeigte nur eine Hash-Funktion, nämlich die Anfangs-Hash-Funktion (H1). Die anderen Hash-Funktionen sind sehr ähnlich zu dieser Funktion, nur differenzierend um einen multiplikativen Faktor. Im Allgemein wird die Hash-Funktion Hk wie folgt definiert:
Hk (Schlüssel) = [GetHash (Schlüssel) + k * (1 + (((GetHash (Schlüssel) & gt; & gt; 5) + 1)% (hashsize - 1)))]% hashsize
Nehmen Sie jedoch das Beispiel von der MSDN-Site1:
%Vor%Nehmen wir an, dass das Hinzufügen des zweiten Schlüssels zu einer Kollision führt, also muss H2 verwendet werden. Wenn ich jedoch Mitarbeiter anrufe ["222-33-4444"], wie kann die Hashtabelle H2 verwenden? Gibt es eine separate Zuordnung? Danke.
Hash-Tabellen speichern sowohl den Schlüssel als auch den Wert in der Hash-Tabelle selbst. Auf diese Weise kann später während Operationen wie Hash-Table-Look-Ups garantiert werden, dass der gefundene Wert derjenige ist, der mit dem für die Suche verwendeten Index übereinstimmt. Hash-Tabellen verwenden eine einfache "versuchen Sie die grundlegende Methode der Suche nach Erfolg bis zum Erfolg" -Methode. In diesem Fall ist die Methode der Suche "Verwenden Sie die Hash-Funktion X", wobei sich X bei einem Fehler ändert.
In anderen Schemata ist das Nachschlageverfahren "schaue auf den Tabelleneintrag X" (wie durch eine Hash-Funktion bestimmt), wobei X jeden Fehler einfach um eins erhöht.
Die quälende Frage ist nun, was passiert, wenn der Wert NICHT in der Tabelle ist? Nun, das kann ziemlich hässlich sein: Wenn Sie entweder einen Eintrag in der Tabelle, der fehlt, getroffen haben oder, noch schlimmer, wenn Sie so viele Einträge durchlaufen haben, wie in der Tabelle gespeichert sind, können Sie sicher sein, dass der Eintrag isn ist 't there - aber das kann im schlimmsten Fall "eine Weile" dauern.
Beachten Sie, dass nur ein Wert mit einem Schlüssel verknüpft werden kann. Sobald Sie den Schlüssel gefunden haben, haben Sie den Wert gefunden. Das Schlimmste, was eine Hash-Tabelle tun kann, ist das Äquivalent einer cache-unfreundlichen linearen Suche über alle Werte in der Hash-Tabelle selbst ... aber schließlich findet sie den Wert, wenn sie da ist, weil sie den gespeicherten Schlüssel vergleicht der angeforderte Schlüssel, um zu testen, ob es da ist. Die einzige Optimierung geschlossen Hash-Tabellen machen ist, wo zuerst - in diesem Fall, wo Hash-Funktion 1 sagt, und dann 2, und dann 3 ...
Ich glaube, du verstehst das Missverständnis falsch. Es gibt nur eine Hash-Funktion: das virtuelle object.GetHashCode() (oder, wenn Sie einen IHashCodeProvider oder IEqualityComparer angeben, verwendet es dieses Objekt, um den Hash-Code zu berechnen). Wenn die Hash-Tabelle voll ist, erweitert sie ihre Kapazität und verteilt die Elemente neu über die neuen, größeren Arrays. Die private Methode, die dies tut, heißt Rehash() , berechnet aber Hash-Codes nicht neu.
KORREKTUR
Das Umladen verwendet keine neue Funktion, sondern arbeitet mit dem vorhergehenden Wert des Hash-Codes; Dies hat den Effekt, dass nachfolgende Slots durchsucht werden, bis ein leeres gefunden wird (für insert / set) oder bis alle Schlüssel mit dem gleichen (initialen) Hash-Code auf Gleichheit mit dem Index-Schlüssel überprüft wurden (zum Abrufen).
BEARBEITEN
Um Ihre Frage direkt zu beantworten:
Nehmen wir an, dass das Hinzufügen des zweiten Schlüssels zu einer Kollision führt, also muss H2 verwendet werden. Wenn ich jedoch Mitarbeiter anrufe ["222-33-4444"], wie kann die Hashtabelle H2 verwenden? Gibt es eine separate Zuordnung? Danke.