Wenn ich sage
%Vor%ist äquivalent zu zwei verschiedenen Arrays wie:
%Vor%Das ist nicht zu weit weg. Beim Betrachten des Quellcodes in Reflector werden drei interne Sammlungen verwendet:
%Vor% Beachten Sie, dass es auch eine int[] buckets Variable gibt, um die Buckets zu verwalten, die in der Fall von Hash-Code-Kollisionen.
Die Zwecke dieser Variablen sollten alle ziemlich selbsterklärend sein. Dies ist jedoch nicht besonders überraschend, da die Klasse Dictionary bekannt und dokumentiert ist, um (idealerweise mit einem Element pro Bucket) O(1) Nachschlagezeit bereitzustellen.
Es ist Hashtable. Für jeden Schlüssel berechnet das Dictionary seinen Hash-Code und verwendet diesen als Zeiger, an dem sich der Wert befinden soll. Wenn es zwei Schlüssel gibt, die mit dem gleichen Hash-Code übereinstimmen, wird eine solche Situation Kollision genannt, und intern wird für diesen Spezialfall das Dictionary einen Binärbaum verwendet.
Algorithmische Komplexität des Dictionary (Hashtable) ist O (1) und im schlimmsten Fall O (Log (N)) (Worst Case bedeutet, dass wir nur mit Kollisionen arbeiten), wobei N eine Anzahl von Elementen im Dictionary ist.
Es ist alles klar auf MSDN geschrieben:
Die generische Klasse Dictionary (Of TKey, TValue) bietet eine Zuordnung von einer Menge von Schlüsseln zu einer Menge von Werten. Jeder Zusatz zum Wörterbuch besteht aus einem Wert und dem zugehörigen Schlüssel. Das Abrufen eines Werts mithilfe seines Schlüssels ist sehr schnell und liegt nahe an O (1), da die Dictionary-Klasse (Of TKey, TValue) als Hashtabelle implementiert ist.
Tags und Links c# dictionary