in .NET, il existe un constructeur pour La capacité d'un dictionnaire est le nombre d'éléments pouvant être ajoutés au dictionnaire avant que le redimensionnement soit nécessaire. Comme des éléments sont ajoutés à un dictionnaire, la capacité est automatiquement augmentée selon les besoins en réaffectant la matrice interne.
Cela me semble à peu près le même que avec d'autres collections telles que Pourquoi (Disclaimer: Je connais bien les "fonctionnalités n'existent pas par défaut". Je suppose que je me demandais principalement s'il y a une raison particulière pour laquelle Dictionnaire int capacité . C'est la même chose que de nombreuses autres collections telles que Liste file d'attente pile
Liste Dictionnaire trimexcess méthode?
trimexcess pour un pour un Dictionnaire n'a pas de sens ou pourquoi il serait significativement plus difficile à mettre en œuvre que pour des collections simples telles que la liste .)
5 Réponses :
Je suppose que dans ce cas, l'argument de la capacité aide à définir la fonction de hachage ainsi que le nombre de godets; Redimensionner / couper une collecte de données clairsemé nécessiterait de recalculer des hachages de tous les éléments stockés restants.
En fait, ils utilisent le hashcode de l'objet clé via gethascode () et supprimez le bit le plus significatif. Ensuite, ils le stockent dans un emplacement dans la matrice par le reste de longueur% hachage (jusqu'à ce qu'une entreprise libre soit trouvée). Bien sûr, le calcul des hashcodes est dépendant de la classe clé.
En plus de détail technique, le dictionnaire choisit quel godet pour placer un élément à l'aide de "godets [Key.GetHashCode ()% gaux.Length] = valeur". La modification de la longueur de la liste des godets nécessite de déplacer toutes les valeurs sur de nouveaux godets.
@Juliet: presque. Le godet est redimensionné en cas de besoin et toute la liste des entrées est copiée dans le processus et les index sont recalculés et donc les objets repositionnés.
Ceci est partiellement une supposition: un dictionnaire est "commandé" comme une table de hachage. La capacité réservée, n'est pas simplement un groupe d'adresses de mémoire gratuites sur votre dictionnaire. Au lieu de cela, il consiste en une pièce vide tout au long du dictionnaire. Ceci est fait pour faire ajouter / déplacer / supprimer, etc., très efficace. Si vous aviez une méthode méthode de trimexcess pour le dictionnaire, tout le dictionnaire devra tout copier sur un nouvel emplacement sans aucune lacune entre les éléments.
En réalité: les lacunes doivent rester sinon l'avantage d'une table de hachage devient avenue, coupe ( trimexcess ), si implémentée, ne doit que couper le ValueCollection interne .
Mise à jour: L'équipe BCL Dit Trimexcess pour les dictionnaires "pourrait être utile" .
Mise à jour: La requête de fonctionnalité résolue comme ne réparera pas : "Malheureusement, nous ne pourrons pas y arriver pour la prochaine version de .NET, donc je ' m résolution de cela comme ne résout pas. "
Le dictionnaire n'est pas commandé - il est implémenté comme une table de hachage. L'équivalent commandé est sortidictionnaire.
Je sais, il n'est pas ordonné de cette façon, il est ordonné comme un hachage. Désolé si cela n'était pas clair
par dictionnaire MSDN est implémenté comme une table de hachage. Si vous avez coupé l'excès, vous devrez proposer un algorithme qui est toujours fourni près de O (1) des temps de recherche dans ce qui serait effectivement une liste triée au hasard.
Qu'est-ce que o (1) recherche a à la trimexess? Hashset.trimexess à O (n).
En fait, j'étais celui qui a demandé à Microsoft de mettre en œuvre la trimexcess. J'ai déjà présenté plus d'un article qui traite des dictionnaires et dans tous les cas, j'ai mis en œuvre la trimexcess. En fait, le redimensionnement utilisé lorsque les godets sont trop petits peuvent être invoqués lors de l'augmentation ou de la diminution de la taille des godets.
Aujourd'hui, je viens de publier un autre article, il s'agit d'une mise en œuvre C ++ d'un dictionnaire, qui prend en charge la trimexcess: http://www.codeproject.com/articles/761040 / A-Net-Like-Dictionary-in-Cplusplus
Une autre implémentation (.NET) peut être trouvée dans cet article: http://www.codeproject.com/articles/548406/dictionary -PLUS-Verrouillage-Versus-ConcurrentDictiondiction
d'ici 2019, .NET Standard 2.1+ et .NET CORE 2.1+ Mise en œuvre .NET Framework ne le met pas en œuvre dans aucune version. Dictionnaire
Etant donné que
hashset a une méthode trimexcess pourpourDictionnaire . Ils disent même dans la documentation qu'unhashset est comme un dictionnairesans valeurs.semble être lié à la mise en œuvre car .net core 2.1 a trimexcess () docs.microsoft.com/en-us/dotnet/api/...
I supposons Microsoft n'a pas intentionnellement ajourné d'ajoutez un
méthode de àDictionnaire quand il a débuté dans .NET Framework 2.0 parce que .net Framework 1.1's System.Collections.hashable n'a pas non plus une méthode similaire. Redimensionner une liste / vecteur ou t [] array est trivial (comme les index d'élément existant restent constants, donc un simple Allouer et copier fonctionne bien), mais la redimensionnement d'une hache est plus difficile car les touches de hachage réelles doivent être recintées en fonction du facteur de charge. Cultiver une matrice de seau interne de HASHTABLE est beaucoup plus sûr que de la rétrécir (en raison de la résolution de collision).... Donc, je pense que les développeurs de Microsoft Convu pour "rétrécir" un dictionnaire en remplaçant-and-repeuplant l'ensemble du dictionnaire
< / code> objet plutôt que de permettre le redimensionnement du gréchage à l'intérieur.