Pourquoi n'y a-t-il pas de Dictionary.TrimExcess()?

Question

Dans .NET, il existe un constructeur pour Dictionary<TKey, TValue> qui prend un paramètre, int capacity. Ceci est le même que pour de nombreuses autres collections telles que List<T>, Queue<T> et Stack<T>; en outre, selon the MSDN documentation:

La capacité d'un dictionnaire est le nombre d'éléments qui peuvent être ajoutés au dictionnaire avant que le redimensionnement soit nécessaire. Au fur et à mesure que des éléments sont ajoutés à un dictionnaire, la capacité est automatiquement augmentée si nécessaire en réallouant le tableau interne.

Cela me semble à peu près la même chose que d'autres collections comme List<T>, etc. Étant donné que ces collections comportent le redimensionnement automatique des comportements en cas de besoin et sont donc susceptibles d'avoir une plus grande capacité que nécessaire, la plupart d'entre eux disposent d'un TrimExcess méthode. C'est pratique si, par exemple, vous ajoutez un nombre inconnu d'éléments à la collection en même temps, et après cela vous n'ajouterez aucun élément supplémentaire.

Pourquoi Dictionary<TKey, TValue> n'a pas la même méthode TrimExcess?

(Disclaimer: Je connais très bien la réponse « caractéristiques n'existent pas par défaut », je suppose que je suis surtout me demandais s'il y a une raison particulière pour laquelle TrimExcess pour une Dictionary n'a pas de sens, ou pourquoi il serait plus difficile à mettre en œuvre que pour des collections plus simples comme List.)

Answer 1

Par dictionnaire MSDN est implémenté comme table de hachage. Si vous réduisiez l'excès, vous auriez à trouver un algorithme qui fournirait encore près de O (1) temps de recherche dans ce qui serait effectivement une liste triée au hasard.

Answer 2

Je suppose que dans ce cas, l'argument capacité permet de définir la fonction de hachage ainsi que le nombre de segments; redimensionner/rogner une collecte de données éparse nécessiterait de recalculer les hachages de tous les éléments stockés restants.

Answer 3

Ceci est partiellement une supposition: un dictionnaire est "ordonné" comme une table de hachage. La capacité réservée n'est pas simplement un tas d'adresses mémoire libres au-dessus de votre dictionnaire. Au lieu de cela, il se compose de la pièce vide dans tout le dictionnaire. Ceci est fait pour rendre l'ajout/déplacement/suppression etc. très efficace. Si vous aviez une méthode TrimExcess pour le dictionnaire, le dictionnaire entier devrait tout copier à un nouvel emplacement sans aucun espace entre les éléments.

En fait: les espaces doivent rester sinon l'avantage d'une table de hachage devient vide, la taille (TrimExcess), si elle est implémentée, ne doit couper que les ValueCollection internes.

Mise à jour: Agrandi et changé mes mots mal choisis
Mise à jour:the BCL team says TrimExcess for Dictionaries "could be useful".
Mise à jour: la demande de fonctionnalité résolue que ne fixerai pas: « Malheureusement, nous ne serons pas en mesure d'arriver à cela pour la prochaine version de .NET, donc je résoudre ce que ne fixerai pas "

Answer 4

En fait, j'étais celui qui a demandé à Microsoft d'implémenter TrimExcess. J'ai déjà présenté plus d'un article traitant des dictionnaires et dans tous les cas j'ai implémenté TrimExcess.En fait, le redimensionnement utilisé lorsque les godets sont trop petits peut être invoqué lors de l'augmentation ou de la réduction de la taille des godets.

Aujourd'hui, je viens de publier un autre article, il est un C++ mise en œuvre d'un dictionnaire, qui soutient TrimExcess: http://www.codeproject.com/Articles/761040/A-NET-like-Dictionary-in-Cplusplus

Une autre implémentation (.NET) se trouve dans cet article: http://www.codeproject.com/Articles/548406/Dictionary-plus-Locking-versus-ConcurrentDictionar