.NET HashTable Vs Dictionary - Le dictionnaire peut-il être aussi rapide?

J'essaie de comprendre quand et pourquoi utiliser un dictionnaire ou un HashTable. J'ai fait un peu de recherche ici et j'ai trouvé des gens qui parlaient des avantages génériques du dictionnaire avec lesquels je suis totalement d'accord, ce qui mène à l'avantage de la boxe et du déballage pour un léger gain de performances.

Mais j'ai également lu que le dictionnaire ne retournera pas toujours les objets dans l'ordre où ils sont insérés, chose qu'il est trié. Où comme HashTable le fera. Si je comprends bien, cela conduit à la table de hachage étant beaucoup plus rapide dans certaines situations.

Ma question est vraiment, quelles pourraient être ces situations? Suis-je juste dans mes hypothèses ci-dessus? Quelles situations pourriez-vous utiliser pour choisir l'une au-dessus de l'autre (oui, la dernière est un peu ambiguë).

System.Collections.Generic.Dictionary<TKey, TValue>et les System.Collections.Hashtableclasses conservent toutes les deux une structure de données de table de hachage en interne. Aucun d'eux ne garantit le maintien de l'ordre des articles.

Laissant de côté les problèmes de boxe / déballage, la plupart du temps, ils devraient avoir des performances très similaires.

La principale différence structurelle entre eux est qu'elle Dictionaryrepose sur le chaînage (en conservant une liste d'éléments pour chaque compartiment de table de hachage) pour résoudre les collisions alors qu'elle Hashtableutilise le ressassement pour la résolution des collisions (lorsqu'une collision se produit, essaie une autre fonction de hachage pour mapper la clé sur un compartiment) .

Il y a peu d'avantages à utiliser la Hashtableclasse si vous ciblez .NET Framework 2.0+. Il est effectivement rendu obsolète par Dictionary<TKey, TValue>.

Je suppose que cela ne signifie plus rien pour vous maintenant. Mais juste pour référence pour les gens qui passent

Test de performance - SortedList vs SortedDictionary vs Dictionary vs Hashtable

Allocation de mémoire:

Temps utilisé pour l'insertion:

Temps de recherche d'un article:

Différences entre Hashtable et Dictionary

Dictionnaire:

• Le dictionnaire renvoie une erreur si nous essayons de trouver une clé qui n'existe pas.
• Dictionnaire plus rapide qu'un Hashtable car il n'y a ni boxe ni déballage.
• Le dictionnaire est un type générique, ce qui signifie que nous pouvons l'utiliser avec n'importe quel type de données.

Table de hachage:

• Hashtable renvoie null si nous essayons de trouver une clé qui n'existe pas.
• Hashtable plus lent que le dictionnaire car il nécessite la boxe et le déballage.
• Hashtable n'est pas un type générique,

Une autre différence importante est que le type Hashtable prend en charge simultanément plusieurs lecteurs sans verrou et un seul écrivain, contrairement à Dictionary.

Article MSDN: "La Dictionary<TKey, TValue>classe a les mêmes fonctionnalités que la Hashtableclasse. Un Dictionary<TKey, TValue> type spécifique (autre que Object) a de meilleures performances qu'un type Hashtablede valeur car les éléments de Hashtablesont de type Objectet, par conséquent, la mise en boîte et le déballage se produisent généralement si le stockage ou récupération d'un type de valeur ".

Lien: http://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.90).aspx

Les deux sont en fait la même classe (vous pouvez regarder le démontage). HashTable a été créé avant que .Net n'ait des génériques. Le dictionnaire est cependant une classe générique et vous offre de forts avantages de frappe. Je n'utiliserais jamais HashTable car Dictionary ne vous coûte rien à utiliser.

Une autre différence importante Hashtableest la sécurité des threads. Hashtablea intégré la sécurité des threads à plusieurs lecteurs / écrivains uniques (MR / SW), ce qui signifie Hashtableautorise UN écrivain avec plusieurs lecteurs sans verrouillage. Dans le cas où Dictionaryil n'y a pas de sécurité de thread, si vous avez besoin de sécurité de thread, vous devez implémenter votre propre synchronisation.

Pour développer davantage:

Hashtable, assurent une certaine sécurité des threads via la propriété Synchronized, qui renvoie un wrapper thread-safe autour de la collection. L'encapsuleur fonctionne en verrouillant la collection entière à chaque opération d'ajout ou de suppression. Par conséquent, chaque thread qui tente d'accéder à la collection doit attendre son tour pour prendre le verrou. Ce n'est pas évolutif et peut entraîner une dégradation significative des performances pour les grandes collections. De plus, le design n'est pas complètement protégé des conditions de course.

Les classes de collection .NET Framework 2.0 comme List<T>, Dictionary<TKey, TValue>, etc ne fournissent pas la synchronisation des threads; le code utilisateur doit fournir toute la synchronisation lorsque des éléments sont ajoutés ou supprimés simultanément sur plusieurs threads. Si vous avez également besoin de la sécurité des types, de la sécurité des threads, utilisez des classes de collections simultanées dans le .NET Framework. Plus de lecture ici.

Les dictionnaires ont l'avantage d'être de type générique, ce qui le rend sûr et un peu plus rapide en raison du manque de besoin de boxe. Le tableau de comparaison suivant (construit à partir des réponses trouvées dans un poste de question SO similaire ) illustre certaines des autres raisons qui prennent en charge les dictionnaires sur les tables de hachage (ou vice versa).

Si vous vous souciez de la lecture qui renverra toujours les objets dans l'ordre où ils sont insérés dans un dictionnaire, vous pouvez jeter un œil à

OrderedDictionary - les valeurs sont accessibles via un index entier (par ordre dans lequel les éléments ont été ajoutés) SortedDictionary - les éléments sont automatiquement triés

Le dictionnaire est plus rapide que la table de hachage car le dictionnaire est un type générique fort. Hashtable est plus lent car il prend l'objet comme type de données, ce qui conduit à la boxe et au déballage.