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

276

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ë).

Jon
la source
5
Je ne veux pas voter contre cela, mais votre karma est de 7777 et je ne veux pas être le gars qui gâche ça pour vous.
CaptainMarvel

Réponses:

298

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>.

Mehrdad Afshari
la source
21
@ Jon- Le chaînage et le remaniement sont discutés en profondeur ici
RichardOD
Merci à vous deux. Je viens de trouver cette page telle que Richard l'a publiée ... J'allais poser des questions sur le chaînage, mais le site MSDN est en fait utile!
Jon
6
@Mehrdad - Ce qui n'est pas clair pour moi sur la façon dont les collisions sont résolues est la suivante: si plusieurs clés peuvent entraîner le même hachage, alors comment vous assurer d'obtenir la bonne valeur lors des recherches, c'est-à-dire comment la fonction sait-elle quel élément revenir? Dans msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx, il est indiqué: "Plutôt que de réessayer en cas de collision, comme c'est le cas avec la classe Hashtable, le dictionnaire enchaîne simplement les collisions sur la liste du seau. " Cela signifie-t-il que lors de l'utilisation de Dictionary, les collisions ne doivent pas inquiéter le développeur?
Howiecamp
6
@Howiecamp: Ce n'est pas vraiment très différent de Hashtable. Les tables de hachage stockent 3 informations dans une entrée: hachage de clé, clé elle-même et valeur. Pour les éléments avec un hachage égal, il devra parcourir la liste pour trouver l'élément avec une clé égale et retourner sa valeur. C'est à peu près vrai Hashtableaussi. En tant que développeur utilisant Dictionarynormalement, vous n'avez pas à vous en préoccuper.
Mehrdad Afshari
@Mehrdad Juste pour être clair, les objets Hashtable et Dictionary stockent la clé elle-même, et cachent également les collisions au développeur?
Howiecamp
111

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:

Test de performance d'utilisation de la mémoire

Temps utilisé pour l'insertion:

Temps utilisé pour l'insertion

Temps de recherche d'un article:

Temps pour rechercher un article

Abdul Munim
la source
Très intéressant, cette liste triée a une recherche PLUS RAPIDE que la table de hachage. Je pensais que la table de hachage est O (1) vs la liste triée O (logn). Apparemment, la table de hachage craint. Je ne l'utiliserai jamais.
John Henckel
@JohnHenckel non, la liste triée a une recherche plus lente. Un coefficient de performance plus élevé signifie de meilleures performances et une meilleure utilisation de la mémoire. Ainsi, la liste triée a la meilleure utilisation de la mémoire selon les graphiques, mais elle aspire dans d'autres domaines tels que l'insertion et la recherche.
C0DEF52
31

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,
user2771704
la source
24

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.

Steven
la source
8
Concurrent Dictionary prendra en charge (.Net 4.0)
Tamilmaran
1
Je ne sais pas si je comprends cette réponse. En regardant ici msdn.microsoft.com/en-us/library/… il dit "Pour prendre en charge plusieurs écrivains, toutes les opérations sur la table de hachage doivent être effectuées via le wrapper renvoyé par la méthode synchronisée, à condition qu'il n'y ait pas de threads lisant l'objet table de hachage . " Cela semble rendre la fonctionnalité "plusieurs lecteurs sans verrouillage" assez inutile, nous sommes donc de retour à devoir verrouiller tous les accès à la table de hachage, tout comme avec Dictionary.
RenniePet
16

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

Juan Camilo Caro J.
la source
11

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.

Adam Luter
la source
8

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.

NullReference
la source
3

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).

janeon
la source
1

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

ToXinE
la source
0

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.

jitendra mahaapatro
la source
2
phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx plz lire les commentaires ci-dessous l'article
Arvand
4
@Arvand Link broken - domaine à vendre.
RenniePet