Hallo,
während einer längeren Debugging-Session ist mir etwas aufgefallen. Bekannt ist:
- man kann ein TDictionary<K,V> mit einer bestimmten Kapazität über den Konstruktor erzeugen (siehe
TDictionary.Create)
- ein Dictionary hat immer einen gewissen Füllgrad
- die Einträge des Dictionaries werden in ein Array aus Buckets einsortiert
- ist der Füllgrad erreicht, dann muss das Bucket-Array vergrößert werden, ansonsten wird der Lookup im Dictionary ineffizient
In der Implementierung von TDictionary wurde das so umgesetzt:
- die Kapazität ist immer die nächstgrößere Zweierpotenz, aber mindestens 4 Buckets
- der Füllgrad wird berechnet: (Kapazität shr 1) + (Kapazität shr 2)
Das führt aber dazu, dass bei manchen Kapazitätswerten nicht mehr alle Einträge ins Dictionary passen und das Dictionary beim Hinzufügen von Elementen vergrößert werden muss, obwohl man eine ausreichende Kapazität angegeben hat:
| Kapazität / Konstruktor | verwendete Kapazität | Max. Füllgrad | |
| 4 | 4 | 3 | Kapazität im Konstruktor nicht ausreichend |
| 20 | 32 | 24 | Kapazität ausreichend |
| 29 | 32 | 24 | Kapazität wieder nicht ausreichend |
Mein Fazit: falls man Reallokationen vermeiden will, sollte man die Kapazität des Dictionaries größer angeben als die Anzahl der Elemente, weil der Füllgrad bei der Kapazitätsberechnung nicht einbezogen wird.
Ist das auch schon mal jemand aufgefallen? Oder habe ich hier ein Verständnisproblem?
