Es ist alles in diesem Papier auf der MSDN beschrieben: Eine ausführliche Untersuchung von Datenstrukturen mit C # 2.0
%Vor%... Kollisionsauflösung Technik namens Rehasing, das ist die Technik, die von der Hashtable-Klasse von .NET Framework verwendet wird. Im Finale In diesem Abschnitt betrachten wir die Dictionary-Klasse, die eine Kollision verwendet Auflösungstechnik kennt die Verkettung. ....
... Die Wiederherstellung funktioniert folgendermaßen: 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:
Die Dictionary-Klasse unterscheidet sich in vielerlei Hinsicht von der Hashtable-Klasse als eines. Zusätzlich zu stark typisiert, das Wörterbuch auch verwendet eine andere Kollisionsauflösungsstrategie als die Hashtable Klasse, unter Verwendung einer Technik, die als Verkettung bezeichnet wird. Daran erinnern, dass mit Sondieren, im Falle einer Kollision ein weiterer Slot in der Liste von Eimer wird ausprobiert. (Beim erneuten Hashing wird der Hash neu berechnet neuer Slot wird versucht.) Mit Verkettung jedoch eine sekundäre Datenstruktur wird verwendet, um Kollisionen zu halten. Genauer gesagt, jeder Slot in der Das Wörterbuch hat ein Array von Elementen, die diesem Bucket zugeordnet sind. In dem Bei einer Kollision wird das kollidierende Element dem Bucket-Liste.
Denken Sie daran, nur der erste Satz ist mein eigener: -)
Das ist eigentlich eine wirklich interessante Frage; Ich habe gerade einen Blogeintrag gemacht, wie es geht Dictionary wird hinter den Kulissen implementiert. Ich kann Hashtable in einem späteren Teil abdecken.