Wie macht ein Wörterbuch eine schnelle Suche

Question

Ich suche die Item[TKey] Quelle von Dictionary<TKey,TValue> versuchen, den Mechanismus der Speicherung/Abruf in einem Wörterbuch zu verstehen, und warum es schneller ist, als nur jeden Eintrag einzeln zu überprüfen.

Wo ich verwirrt bin ist in der Benutzer von Primzahlen in buckets Feld und das Zusammenspiel mit Entry<TKey,TValue>.next.

Kann mir jemand die Logik erklären oder auf eine Referenz zeigen, wo ich sie verstehen kann.

Danke.

Answer 1

Hash Tables See und möglicherweise this article about using prime numbers in hash table implementations.

Answer 2

Blick in Hashcodes, sie erlauben es dem Wörterbuch zu 'Eimer' die Tasten:

http://msdn.microsoft.com/en-us/library/4yh14awz%28VS.80%29.aspx

Colin E.

Answer 3

Schauen Sie sich das Wikipedia-Artikel: Hashtable

Ein Wörterbuch ist nur ein starker Typ d Implementierung einer Hashtabelle. Es hat eine Reihe von "Eimern", wo es die Gegenstände mit ihren Schlüsseln legt.

Wenn Sie ein Element zur Hashtabelle hinzufügen, verwendet es den Hashcode des Schlüssels, um zu entscheiden, in welchen Bucket es eingefügt wird (normalerweise ein sehr schneller Vorgang, rufen Sie einfach GetHashCode an und wenden Sie einen Modulo darauf an). Sobald es den Bucket hat (was eine Art Liste ist), prüft es, ob der Bucket bereits ein Element mit dem gleichen Schlüssel enthält, und fügt es hinzu, wenn es nicht der Fall ist. Dies ist auch ziemlich schnell, da jeder Bucket nur eine kleine Teilmenge aller Elemente in der Hashtabelle enthält.

Wenn Sie ein Element basierend auf seinem Schlüssel abrufen möchten, bestimmt es den Bucket basierend auf dem Hashcode des Schlüssels und sucht nach einem Element mit diesem Schlüssel im Bucket.

Natürlich ist dies eine sehr einfache Beschreibung ... siehe den Wikipedia-Artikel für weitere Details.