In .NET gibt es einen Konstruktor für Dictionary<TKey, TValue> , der einen Parameter, int capacity , enthält. Dies ist das gleiche wie bei vielen anderen Sammlungen wie List<T> , Queue<T> und Stack<T> ; außerdem laut der MSDN-Dokumentation :
Die Kapazität eines Dictionarys ist die Anzahl der Elemente, die zum Dictionary hinzugefügt werden können, bevor eine Größenänderung erforderlich ist. Wenn einem Dictionary Elemente hinzugefügt werden, wird die Kapazität automatisch durch die Neuzuweisung des internen Arrays erhöht.
Das klingt für mich fast genauso wie bei anderen Sammlungen wie List<T> usw. Da diese Sammlungen bei Bedarf automatisch skalieren und daher wahrscheinlich eine größere Kapazität haben als erforderlich, verfügen die meisten über eine TrimExcess Methode. Dies ist praktisch, wenn Sie beispielsweise der Sammlung eine unbekannte Anzahl von Elementen gleichzeitig hinzufügen und danach keine zusätzlichen Elemente hinzufügen.
Warum hat Dictionary<TKey, TValue> nicht dieselbe TrimExcess Methode?
(Disclaimer: Ich bin ziemlich vertraut mit der Antwort "Funktionen existieren nicht standardmäßig"; ich denke, ich frage mich meistens, ob es einen bestimmten Grund gibt, warum TrimExcess für ein Dictionary keinen Sinn ergibt, oder warum es wesentlich schwieriger zu implementieren wäre als für einfachere Sammlungen wie List .)
Per MSDN-Wörterbuch ist als Hash-Tabelle implementiert. Wenn Sie den Überschuss bereinigen, müssten Sie einen Algorithmus entwickeln, der immer noch nahe bei (1) Nachschlagzeiten in einer nach dem Zufallsprinzip sortierten Liste besteht.
Dies ist teilweise eine Vermutung: ein Dictionary ist als Hash-Tabelle "geordnet". Die Kapazität, die reserviert wird, ist nicht einfach eine Reihe von freien Speicheradressen auf Ihrem Wörterbuch. Stattdessen besteht es aus einem leeren Raum im gesamten Wörterbuch. Dies geschieht, um das Hinzufügen / Verschieben / Entfernen usw. sehr effizient zu machen. Wenn Sie eine TrimExcess -Methode für Dictionary hätten, müsste das gesamte Dictionary alles an einen neuen Ort kopieren, ohne dass zwischen den Elementen Lücken entstehen.
Eigentlich sollten die Lücken bleiben, sonst wird der Vorteil einer Hash-Tabelle ungültig, trimming ( TrimExcess ) sollte, falls implementiert, nur die interne ValueCollection trimmen.
Update: erweitert und änderte meine falsch gewählten Wörter
Update: .
Aktualisieren: die Feature-Anfrage als Wird nicht behoben : "Leider werden wir dies für die nächste Version von .NET nicht erreichen können. Daher behebe ich das Problem als nicht behoben."
Ich würde annehmen, dass in diesem Fall das Kapazitätsargument hilft, die Hashfunktion sowie die Anzahl der Buckets zu definieren; Die Größenanpassung / das Zuschneiden einer spärlichen Datensammlung würde die Neuberechnung von Hashwerten aller verbleibenden gespeicherten Elemente erfordern.
Eigentlich war ich derjenige, der Microsoft gebeten hat, TrimExcess zu implementieren. Ich habe bereits mehr als einen Artikel vorgestellt, der sich mit Wörterbüchern beschäftigt, und in allen Fällen habe ich TrimExcess implementiert. Tatsächlich kann die Größe, die verwendet wird, wenn die Buckets zu klein sind, aufgerufen werden, wenn die Größe der Buckets erhöht oder verringert wird.
Heute habe ich einen anderen Artikel veröffentlicht, es ist eine C ++ - Implementierung eines Wörterbuchs, das TrimExcess unterstützt: Ссылка
Eine andere Implementierung (.NET) kann in diesem Artikel gefunden werden: Ссылка
Tags und Links .net dictionary collections