Sollte ein .NET-generic-Wörterbuch mit einer Kapazität auf die Anzahl der Elemente gleich initialisiert werden sie enthalten?

Question

Wenn ich, sagen wir, 100 Elemente, die in einem Wörterbuch gespeichert werde, sollte ich es also initialisieren?

var myDictionary = new Dictionary<Key, Value>(100);

Mein Verständnis ist, dass der .NET-Wörterbuch selbst intern ändert die Größe, wenn es um eine gegebene Belastung erreicht, und dass die Ladeschwelle wird als Verhältnis der Kapazität definiert.

Das würde vorschlagen, dass wenn 100 Elemente der obigen Wörterbuch hinzugefügt wurden, dann wäre es selbst die Größe, wenn eines der Elemente hinzugefügt wurde. Ändern der Größe eines Wörterbuch ist etwas, Ich mag würde zu vermeiden, da es eine Performance-Einbußen und ist eine Verschwendung von Speicher.

Die Wahrscheinlichkeit von Kollisionen von Hashing ist zum Laden in einem Wörterbuch proportional. Selbst wenn also das Wörterbuch nicht selbst die Größe (und nutzt alle seine Slots) muss die Leistung aufgrund dieser Kollisionen verschlechtern.

Wie sollte man am besten entscheiden, welche Kapazitäten das Wörterbuch, initialisieren vorausgesetzt, Sie wissen, wie viele Elemente in dem Wörterbuch sein?

Answer 1

Was sollten Sie die Wörterbuch Kapazität initialisieren auf zwei Faktoren abhängt: (1) Die Verteilung der GetHashCode-Funktion, und (2) Wie viele Elemente, die Sie haben einzufügen.

Ihre Hash-Funktion entweder zufällig verteilt werden soll, oder es sollte für den Satz von Eingang speziell formuliert werden. Lassen Sie uns das erste übernehmen, aber wenn man in der zweiten aufblicken perfekte Hash-Funktionen interessiert sind.

Wenn Sie 100 Elemente haben in das Wörterbuch einzufügen, eine zufällig verteilte Hash-Funktion, und stellen Sie die Kapazität auf 100, dann, wenn Sie das i-te Element in die Hash-Tabelle einfügen haben Sie eine (i-1) / 100 Wahrscheinlichkeit dass das i-te Element mit einem anderen Elemente beim Einsetzen kollidieren. Wenn Sie diese Wahrscheinlichkeit einer Kollision senken wollen, erhöhen die Kapazität. Eine Verdoppelung der erwarteten Kapazität halbiert die Chance einer Kollision.

Außerdem, wenn Sie wissen, wie häufig werden werden Sie jedes Element im Wörterbuch zugreifen können Sie die Elemente in der Reihenfolge abnehmender Frequenz, da die Elemente eingefügt werden sollen, die Sie zuerst im Durchschnitt wird Einsatz schneller zu erreichen.

Answer 2

Ich habe einen schnellen Test, wahrscheinlich nicht wissenschaftlich, aber wenn ich die Größe eingestellt dauerte es 1.2207780 Sekunden, um eine Million Artikel hinzufügen und es dauerte 1.5024960 Sekunden hinzufügen, wenn ich nicht das Wörterbuch eine Größe gegeben hat ... das scheint vernachlässigbar zu mir.

Hier ist mein Testcode ist, vielleicht kann jemand einen strengeren Test machen, aber ich bezweifle es wichtig ist.

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; i++)
                dict1.Add(i.ToString(), i.ToString());

            DateTime stop1 = DateTime.Now;

            DateTime start2 = DateTime.Now;
            var dict2 = new Dictionary<string, string>();

            for (int i = 0; i < 1000000; i++)
                dict2.Add(i.ToString(), i.ToString());

            DateTime stop2 = DateTime.Now;

            Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
            Console.ReadLine();
        }

Answer 3

Ich glaube, du bist Angelegenheiten zu verkomplizieren. Wenn Sie wissen, wie viele Elemente in Ihrem Wörterbuch sein wird, dann mit allen Mitteln festzulegen, dass auf dem Bau. Dadurch wird das Wörterbuch helfen, den notwendigen Platz in den internen Datenstrukturen zuzuweisen Daten zu vermeiden Neuzuweisung und Umbildung.

Answer 4

Die Angabe der Anfangskapazität an den Dictionary Konstruktor erhöht die Leistung, weil es weniger Anzahl von Größenänderungen auf die internen Strukturen, die die Wörterbuchwerte während der ADD-Operationen speichern sein wird.

In Anbetracht, dass Sie eine Anfangskapazität von k zum Dictionary Konstruktor angeben dann:

1. Die Dictionary wird die Menge an Speicher notwendig zum Speichern von k Elemente behalten;
2. QUERY Leistung gegen das Wörterbuch nicht betroffen ist, und es wird nicht schneller oder langsamer sein;
3. ADD-Operationen werden nicht mehr Speicherzuordnungen (vielleicht teuer) erfordern und damit schneller werden.

MSDN :

  

Die Kapazität eines Dictionary (TKey,   TValue) ist die Anzahl von Elementen, die   kann den Dictionary (TKey hinzugefügt werden,   TValue) vor Redimensionierung notwendig.   Als Elemente A zugegeben   Dictionary (TKey, TValue), die Kapazität   wird automatisch nach Bedarf erhöht   durch das interne Array Neuzuweisung.

     

Wenn die Größe der Sammlung sein kann   geschätzte Angabe des anfänglichen   Kapazität entfällt die Notwendigkeit,   führt eine Anzahl von Größenänderung   Operationen beim Hinzufügen von Elementen   das Dictionary (TKey, TValue).

Answer 5

Ja, in HashTable Gegenteil, die als Methode verwendet Wiederkäuen Kollisionen zu lösen, wird Dictionary Verkettungs verwenden. Also ja, es ist gut, die Zählung zu verwenden. Für eine HashTable möchten Sie wahrscheinlich count * (1/fillfactor) verwenden

Answer 6

Die Anfangsgröße ist nur ein Vorschlag. Zum Beispiel, wie die meisten Größen Hash-Tabellen haben, die Primzahlen oder eine Potenz von 2 sind.