Comment le dictionnaire c#/.net 3.5 est-il implémenté ?

Question

Je suis en train d'utiliser une application qui utilise un certain nombre de grands dictionnaires (jusqu'à 10^6 éléments), dont la taille est inconnue à l'avance, (bien que je puisse deviner dans certains cas). Je me demande comment le dictionnaire est implémenté, c'est-à-dire quel est l'effet si je ne donne pas une estimation initiale de la taille du dictionnaire. Est-ce qu'il utilise internalement un tableau (qui peut grandir automatiquement) de la même manière que List le fait? Auquel cas, laisser les dictionnaires grandir pourrait laisser beaucoup de grands tableaux non référencés sur le LOH.

Answer 1

En utilisant Reflector, j'ai trouvé ce qui suit : Le Dictionnaire garde les données dans un tableau de structures. Il maintient un compte sur combien de places vides restent dans ce tableau. Lorsque vous ajoutez un élément et qu'il ne reste aucune place vide, il augmente la taille du tableau interne (voir ci-dessous) et copie les données de l'ancien tableau vers le nouveau.

Je vous suggérerais donc d'utiliser le constructeur dans lequel vous définissez la taille initiale si vous savez qu'il y aura de nombreuses entrées.

ÉDIT: La logique est en réalité assez intéressante : Il existe une classe interne appelée HashHelpers pour trouver des nombres premiers. Pour accélérer cela, elle a également stocké certains nombres premiers dans un tableau statique de 3 à 7199369 (certains sont manquants; pour la raison, voir ci-dessous). Lorsque vous fournissez une capacité, il trouve le prochain nombre premier (même valeur ou plus grand) à partir du tableau, et utilise cela comme capacité initiale. Si vous lui donnez un nombre plus grand que celui de son tableau, il commencera à vérifier manuellement.

Donc si aucune valeur n'est passée comme capacité au Dictionnaire, la capacité de départ est trois.

Une fois la capacité dépassée, il multiplie la capacité actuelle par deux, puis trouve le prochain plus grand nombre premier en utilisant la classe d'aide. C'est pourquoi dans le tableau, chaque premier n'est pas nécessaire, car les premiers "trop proches" ne sont pas vraiment nécessaires.

Donc si nous ne passons aucune valeur initiale, nous obtiendrions (j'ai vérifié le tableau interne):

1. 3
2. 7
3. 17
4. 37
5. 71
6. 163
7. 353
8. 761
9. 1597
10. 3371
11. 7013
12. 14591
13. 30293
14. 62851
15. 130363
16. 270371
17. 560689
18. 1162687
19. 2411033
20. 4999559

Une fois que nous dépassons cette taille, l'étape suivante sort du tableau interne et il recherchera manuellement des nombres premiers plus grands. Cela sera assez lent. Vous pourriez initialiser avec 7199369 (la plus grande valeur dans le tableau), ou envisager si avoir plus de environ 5 millions d'entrées dans un Dictionnaire signifierait que vous devriez reconsidérer votre conception.

Answer 2

MSDN dit : "Récupérer une valeur en utilisant sa clé est très rapide, proche de O(1), car la classe Dictionary est implémentée comme une table de hachage." et plus loin "la capacité est automatiquement augmentée en fonction des besoins en réallouant le tableau interne."

Mais vous obtenez moins de réallocations si vous donnez une estimation initiale. Si vous avez tous les éléments dès le début, la méthode LINQ ToDictionary peut s'avérer pratique.

Answer 3

Les tables de hachage ont normalement quelque chose appelé un facteur de charge, qui augmentera le magasin de compartiments de sauvegarde si ce seuil est atteint. De mémoire, la valeur par défaut est d'environ 0,72. Si vous aviez un hachage parfait, cela pourrait être augmenté à 1,0.

Aussi, lorsque la table de hachage a besoin de plus de compartiments, l'ensemble de la collection doit être rehaché.

Answer 4

La meilleure façon pour moi serait d'utiliser le .NET Reflector.

http://www.red-gate.com/products/reflector/

Utilisez le code désassemblé pour voir l'implémentation.

Answer 5

• JSON comme un dictionnaire

  { "Détails": { "CléApi": 50125 } }

• Le modèle doit contenir une propriété de type Dictionnaire.

  public Dictionary Détails { get; set; }

• Implémenter la boucle foreach() avec le type de données "KeyValue"

     foreach(KeyValuePair dict in Détails)
              {
                  switch (dict.Key)
                  {
                    case nameof(settings.CléApi):
                    int.TryParse(kv.Value, out int CléApi);
                    settings.CléApi = CléApi;
                          break;
                      default:
                          break;
                     }
                 }