Pourquoi le dictionnaire est-il préféré à Hashtable en C #?

1396

Dans la plupart des langages de programmation, les dictionnaires sont préférés aux tables de hachage. Quelles en sont les raisons?

Nakul Chaudhary
la source
21
> Ce n'est pas nécessairement vrai. Une table de hachage est une implémentation d'un dictionnaire. Un exemple typique à cela, et il peut être celui par défaut dans .NET, mais ce n'est pas par définition le seul. Je ne suis pas sûr que cela soit requis par la norme ECMA, mais la documentation MSDN l' appelle très clairement comme étant implémentée comme une table de hachage. Ils fournissent même la classe SortedList pour les moments où une alternative est plus raisonnable.
Promit
15
@Promit J'ai toujours pensé que Dictionaryc'était une implémentation du Hashtable.
b1nary.atr0phy
2
Je pense que la raison en est que, dans un dictionnaire, vous pouvez définir le type de clé et la valeur de votre selfe. la table de hachage ne peut prendre que des objets et enregistre les paires en fonction du hachage (depuis object.GetHashCode ()).
Radinator
2
@Dan Votre affirmation est tout à fait erronée ... une table de hachage ne contient qu'une seule instance de chaque clé, et une recherche ne produit jamais plusieurs entrées; si vous souhaitez associer plusieurs valeurs à chaque clé, faites de la valeur de la table de hachage une liste de valeurs. Il n'y a pas de structure de données comme "un dictionnaire" ... Le dictionnaire est simplement le nom que certaines bibliothèques utilisent pour leur table de hachage. par exemple, la table de hachage non générique de C # est appelée HashTable. Quand ils ont ajouté des génériques au langage, ils ont appelé la version générique Dictionary. Les deux sont des tables de hachage.
Jim Balter
3
@Dan Votre affirmation est erronée ... une table de hachage ( en.wikipedia.org/wiki/Hash_table ) est une implémentation particulière d'un dictionnaire, alias un tableau associatif ( en.wikipedia.org/wiki/Associative_array ), et, étant un dictionnaire, ne contient qu'une seule instance de chaque clé, et une recherche ne produit jamais plusieurs entrées; si vous souhaitez associer plusieurs valeurs à chaque clé, faites de la valeur de la table de hachage une liste de valeurs. Et les classes .NET Dictionary et Hashtable sont toutes deux des tables de hachage.
Jim Balter

Réponses:

1568

Pour ce qu'il vaut, un dictionnaire est (conceptuellement) une table de hachage.

Si vous vouliez dire "pourquoi utilisons-nous Dictionary<TKey, TValue> classe au lieu de la Hashtableclasse?", Alors c'est une réponse simple: Dictionary<TKey, TValue>est un type générique, Hashtablenon. Cela signifie que vous obtenez une sécurité de type avec Dictionary<TKey, TValue>, car vous ne pouvez pas insérer d'objet aléatoire dans celui-ci, et vous n'avez pas à transtyper les valeurs que vous supprimez.

Fait intéressant, l' Dictionary<TKey, TValue>implémentation dans le .NET Framework est basée sur le Hashtable, comme vous pouvez le voir dans ce commentaire dans son code source:

Le dictionnaire générique a été copié à partir de la source de Hashtable

La source

Michael Madsen
la source
393
Et les collections génériques sont également beaucoup plus rapides car il n'y a pas de boxe / unboxing
Chris S
6
Pas sûr d'une table de hachage avec la déclaration ci-dessus, mais pour ArrayList vs List <t> c'est vrai
Chris S
36
Hashtable utilise Object pour conserver les choses en interne (seule façon non générique de le faire), il devrait donc également cocher / décompresser.
Guvante
16
@BrianJ: Une "table de hachage" (deux mots) est le terme informatique pour ce type de structure; Le dictionnaire est une implémentation spécifique. Un HashTable correspond à peu près à un Dictionary <objet, objet> (bien qu'avec des interfaces légèrement différentes), mais les deux sont des implémentations du concept de table de hachage. Et bien sûr, juste pour confondre les choses, certaines langues appellent leurs tables de hachage "dictionnaires" (par exemple Python) - mais le terme CS approprié est toujours table de hachage.
Michael Madsen
32
@BrianJ: HashTable(class) et Dictionary(class) sont des tables de hachage (concept), mais a HashTablen'est pas un Dictionary, ni un Dictionarya HashTable. Ils sont utilisés de façon très similaire et Dictionary<Object,Object>peuvent agir de la même manière non typée que l'a HashTable, mais ils ne partagent pas directement de code (bien que les parties soient susceptibles d'être implémentées de manière très similaire).
Michael Madsen
625

Dictionary<<< >>> Hashtabledifférences:

  • Générique <<< >>> Non générique
  • Nécessite une synchronisation des threads <<< >>> Offre une version thread-safe par la Synchronized()méthode
  • Article KeyValuePairénuméré : <<< >>> Article énuméré:DictionaryEntry
  • Plus récent (> .NET 2.0 ) <<< >>> Plus ancien (depuis .NET 1.0 )
  • est dans System.Collections.Generic <<< >>> est dans System.Collections
  • La requête vers une clé non existante renvoie une exception <<< >>> La requête vers une clé non existante renvoie null
  • potentiellement un peu plus rapide pour les types de valeur <<< >>> bit plus lent (nécessite de la boxe / unboxing) pour les types de valeur

Dictionary/ Hashtablesimilitudes:

  • Les deux sont des tables de hachage internes == accès rapide aux données à plusieurs éléments selon la clé
  • Les deux ont besoin de clés immuables et uniques
  • Les clés des deux nécessitent leur propre GetHashCode()méthode

Collections .NET similaires (candidats à utiliser à la place de Dictionary et Hashtable):

  • ConcurrentDictionary- thread safe (accessible en toute sécurité à partir de plusieurs threads simultanément)
  • HybridDictionary- performances optimisées (pour quelques articles et aussi pour de nombreux articles)
  • OrderedDictionary- les valeurs sont accessibles via int index (par ordre dans lequel les éléments ont été ajoutés)
  • SortedDictionary- articles triés automatiquement
  • StringDictionary- fortement typé et optimisé pour les chaînes
Marcel Toth
la source
11
@ Guillaume86, c'est pourquoi vous utilisez TryGetValue à la place msdn.microsoft.com/en-us/library/bb347013.aspx
Trident D'Gao
2
+1 pour StringDictionary... btw StringDictionaryn'est pas le même que Dictionary<string, string>lorsque vous utilisez le constructeur par défaut.
Cheng Chen
ParallelExtensionsExtras @ code.msdn.microsoft.com/windowsdesktop/… contient un ObservableConcurrentDictionary qui est une excellente liaison sapin ainsi qu'une concurrence.
VoteCoffee
3
géniale explication, c'est vraiment sympa vous avez également énuméré les similitudes pour réduire les questions qui pourraient vous venir à l'esprit
mkb
178

Parce que Dictionaryc'est une classe générique ( Dictionary<TKey, TValue>), de sorte que l'accès à son contenu est de type sécurisé (c'est-à-dire que vous n'avez pas besoin de caster à partir de Object, comme vous le faites avec a Hashtable).

Comparer

var customers = new Dictionary<string, Customer>();
...
Customer customer = customers["Ali G"];

à

var customers = new Hashtable();
...
Customer customer = customers["Ali G"] as Customer;

Cependant, Dictionaryest implémenté en tant que table de hachage en interne, donc techniquement, cela fonctionne de la même manière.

gius
la source
88

FYI: Dans .NET, Hashtableest thread-safe pour une utilisation par plusieurs threads de lecture et un seul thread d'écriture, tandis que dans Dictionaryles membres statiques publics sont thread-safe, mais tous les membres d'instance ne sont pas garantis pour être thread-safe.

Nous avons dû changer tous nos dictionnaires à Hashtablecause de cela.

user38902
la source
10
Amusement. Le code source Dictionary <T> semble beaucoup plus propre et plus rapide. Il peut être préférable d'utiliser Dictionary et d'implémenter votre propre synchronisation. Si le dictionnaire doit absolument être à jour, il vous suffira alors de synchroniser l'accès aux méthodes de lecture / écriture du dictionnaire. Ce serait beaucoup de verrouillage, mais ce serait correct.
Triynko
10
Alternativement, si vos lectures ne doivent pas être absolument à jour, vous pouvez traiter le dictionnaire comme immuable. Vous pouvez ensuite saisir une référence au dictionnaire et gagner en performances en ne synchronisant pas du tout les lectures (car il est immuable et intrinsèquement thread-safe). Pour le mettre à jour, vous construisez une copie mise à jour complète du dictionnaire en arrière-plan, puis échangez simplement la référence avec Interlocked.CompareExchange (en supposant un seul thread d'écriture; plusieurs threads d'écriture nécessiteraient la synchronisation des mises à jour).
Triynko
38
.Net 4.0 a ajouté la ConcurrentDictionaryclasse qui a toutes les méthodes publiques / protégées implémentées pour être thread-safe. Si vous n'avez pas besoin de prendre en charge les plates-formes héritées, cela vous permettrait de remplacer le Hashtablecode multithread: msdn.microsoft.com/en-us/library/dd287191.aspx
Dan Is Fiddling By Firelight
anonyme à la rescousse. Cool réponse.
unkulunkulu
5
Je me souviens d'avoir lu que HashTable est uniquement compatible avec les threads de lecture-écriture dans le scénario où les informations ne sont jamais supprimées de la table. Si un lecteur demande un élément qui se trouve dans le tableau alors qu'un autre élément est supprimé, et que le lecteur doit rechercher l'élément à plusieurs endroits, il est possible que pendant la recherche du lecteur, le rédacteur déplace cet élément. d'un endroit qui n'a pas été examiné à un autre, ce qui entraîne un faux rapport selon lequel l'article n'existe pas.
supercat
68

Dans .NET, la différence entre Dictionary<,>et HashTableest principalement que le premier est un type générique, donc vous obtenez tous les avantages des génériques en termes de vérification de type statique (et de boxe réduite, mais ce n'est pas aussi grand que les gens ont tendance à penser termes de performances - il y a un coût de mémoire certain pour la boxe, cependant).

Marc Gravell
la source
34

Les gens disent qu'un dictionnaire est identique à une table de hachage.

Ce n'est pas nécessairement vrai. Une table de hachage est un moyen d' implémenter un dictionnaire. Un exemple typique à cela, et il peut être celui par défaut dans .NET dans la Dictionaryclasse, mais ce n'est pas par définition le seul.

Vous pourriez tout aussi bien implémenter un dictionnaire en utilisant une liste chaînée ou un arbre de recherche, ce ne serait tout simplement pas aussi efficace (pour une métrique d'efficacité).

rix0rrr
la source
4
Les documents MS indiquent: "La récupération d'une valeur à l'aide de sa clé est très rapide, proche de O (1), car la classe Dictionary <(Of <(TKey, TValue>)>) est implémentée en tant que table de hachage." - vous devriez donc être assuré d'avoir une table de hachage lorsque vous traitez Dictionary<K,V>. IDictionary<K,V>pourrait être n'importe quoi, cependant :)
snemarch
13
@ rix0rrr - Je pense que vous avez cela à l'envers, un dictionnaire utilise un HashTable pas un HashTable utilise un dictionnaire.
Joseph Hamilton
8
@JosephHamilton - rix0rrr a bien compris: "Une table de hachage est une implémentation d'un dictionnaire ." Il signifie le concept "dictionnaire", pas la classe (notez les minuscules). Conceptuellement, une table de hachage implémente une interface de dictionnaire. Dans .NET, Dictionary utilise une table de hachage pour implémenter IDictionary. C'est désordonné;)
Robert Hensing
Je parlais dans .NET, car c'est ce qu'il a mentionné dans sa réponse.
Joseph Hamilton
2
@JosephHamilton: implements (ou implémentation de ) ne signifie même pas à distance la même chose que uses . Plutôt l'inverse. Peut-être aurait-il été plus clair s'il l'avait dit légèrement différemment (mais avec le même sens): "une table de hachage est un moyen d'implémenter un dictionnaire". Autrement dit, si vous voulez la fonctionnalité d'un dictionnaire, une façon de le faire (pour implémenter le dictionnaire), est d'utiliser une table de hachage.
ToolmakerSteve
21

Collections& Genericssont utiles pour gérer un groupe d'objets. Dans .NET, tous les objets de collections relèvent de l'interface IEnumerable, qui à son tour a ArrayList(Index-Value))& HashTable(Key-Value). Après .NET Framework 2.0, ArrayList& a HashTableété remplacé par List& Dictionary. Maintenant, le Arraylist& HashTablen'est plus utilisé dans les projets de nos jours.

Venant à la différence entre HashTable& Dictionary, Dictionaryest générique alors que as Hastablen'est pas générique. Nous pouvons ajouter n'importe quel type d'objet HashTable, mais lors de la récupération, nous devons le convertir en le type requis. Donc, ce n'est pas un type sûr. Mais dictionary, tout en se déclarant, nous pouvons spécifier le type de clé et de valeur, il n'est donc pas nécessaire de transtyper lors de la récupération.

Regardons un exemple:

HashTable

class HashTableProgram
{
    static void Main(string[] args)
    {
        Hashtable ht = new Hashtable();
        ht.Add(1, "One");
        ht.Add(2, "Two");
        ht.Add(3, "Three");
        foreach (DictionaryEntry de in ht)
        {
            int Key = (int)de.Key; //Casting
            string value = de.Value.ToString(); //Casting
            Console.WriteLine(Key + " " + value);
        }

    }
}

Dictionnaire,

class DictionaryProgram
{
    static void Main(string[] args)
    {
        Dictionary<int, string> dt = new Dictionary<int, string>();
        dt.Add(1, "One");
        dt.Add(2, "Two");
        dt.Add(3, "Three");
        foreach (KeyValuePair<int, String> kv in dt)
        {
            Console.WriteLine(kv.Key + " " + kv.Value);
        }
    }
}
Sujit
la source
2
au lieu d'affecter explicitement le type de données pour KeyValuePair, nous pourrions utiliser var. Donc, cela réduirait la frappe - foreach (var kv en dt) ... juste une suggestion.
Ron
16

Dictionnaire:

  • Il retourne / lève une exception si nous essayons de trouver une clé qui n'existe pas.

  • Il est plus rapide qu'un Hashtable car il n'y a ni boxe ni déballage.

  • Seuls les membres statiques publics sont thread-safe.

  • Le dictionnaire est un type générique, ce qui signifie que nous pouvons l'utiliser avec n'importe quel type de données (lors de la création, doit spécifier les types de données pour les clés et les valeurs).

    Exemple: Dictionary<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();

  • Dictionay est une implémentation sécurisée de Hashtable Keyset Valuesest fortement typé.

Table de hachage:

  • Il renvoie null si nous essayons de trouver une clé qui n'existe pas.

  • Il est plus lent que le dictionnaire car il nécessite la boxe et le déballage.

  • Tous les membres d'une table de hachage sont thread-safe,

  • Hashtable n'est pas un type générique,

  • Hashtable est une structure de données de type lâche, nous pouvons ajouter des clés et des valeurs de tout type.

Altaf Patel
la source
"Il retourne / lève une exception si nous essayons de trouver une clé qui n'existe pas." Pas si vous utilisezDictionary.TryGetValue
Jim Balter
16

L'article Examen approfondi des structures de données à l'aide de C # sur MSDN indique qu'il existe également une différence dans la stratégie de résolution des collisions :

La classe Hashtable utilise une technique appelée rehachage .

Le rehachage fonctionne comme suit: il existe un ensemble de fonctions de hachage différentes, H 1 ... H n , et lors de l'insertion ou de la récupération d'un élément de la table de hachage, la fonction de hachage H 1 est initialement utilisée. Si cela conduit à une collision, H 2 est essayé à la place et jusqu'à H n si nécessaire.

Le dictionnaire utilise une technique appelée chaînage .

Avec le rehachage, en cas de collision, le hachage est recalculé et le nouvel emplacement correspondant à un hachage est essayé. Avec le chaînage, cependant, une structure de données secondaire est utilisée pour contenir les collisions . Plus précisément, chaque emplacement du dictionnaire possède un tableau d'éléments qui correspondent à ce compartiment. En cas de collision, l'élément en collision est ajouté à la liste du compartiment.

alexandrekow
la source
16

Depuis .NET Framework 3.5, il existe également un HashSet<T>qui fournit tous les avantages de laDictionary<TKey, TValue> si vous n'avez besoin que des clés et pas de valeurs.

Donc, si vous utilisez un Dictionary<MyType, object>et définissez toujours la valeur sur nullpour simuler la table de hachage sécurisée de type, vous devriez peut-être envisager de basculer vers le HashSet<T>.

Oliver
la source
14

La Hashtablestructure de données est typée de manière lâche, vous pouvez donc ajouter des clés et des valeurs de tout type à la Hashtable. La Dictionaryclasse est une Hashtableimplémentation de type sécurisé , et les clés et les valeurs sont fortement typées. Lors de la création d'une Dictionaryinstance, vous devez spécifier les types de données pour la clé et la valeur.

la chair
la source
11

Notez que MSDN dit: "La classe Dictionary <(Of <(TKey, TValue>)>) est implémentée en tant que table de hachage ", et non la classe "Dictionary <(Of <(TKey, TValue>)>) est implémentée en tant que HashTable "

Le dictionnaire n'est PAS implémenté en tant que HashTable, mais il est implémenté suivant le concept d'une table de hachage. L'implémentation n'est pas liée à la classe HashTable en raison de l'utilisation de génériques, bien qu'en interne Microsoft aurait pu utiliser le même code et remplacer les symboles de type Object par TKey et TValue.

Dans .NET 1.0, les génériques n'existaient pas; c'est là que HashTable et ArrayList ont commencé à l'origine.

Brant
la source
Pouvez-vous corriger ce devis MSDN? Quelque chose manque ou est incorrect; ce n'est pas grammatical et quelque peu incompréhensible.
Peter Mortensen
10

HashTable:

La clé / valeur sera convertie en un type d'objet (boxe) lors du stockage dans le tas.

La clé / valeur doit être convertie dans le type souhaité lors de la lecture à partir du tas.

Ces opérations sont très coûteuses. Nous devons éviter autant que possible la boxe / le déballage.

Dictionnaire: variante générique de HashTable.

Pas de boxe / déballage. Aucune conversion requise.

Siva Sankar Gorantla
la source
8

Un objet Hashtable se compose de compartiments qui contiennent les éléments de la collection. Un compartiment est un sous-groupe virtuel d'éléments dans la table de hachage, ce qui rend la recherche et la récupération plus faciles et plus rapides que dans la plupart des collections .

La classe Dictionary a les mêmes fonctionnalités que la classe Hashtable. Un dictionnaire d'un type spécifique (autre que Object) a de meilleures performances qu'une table de hachage pour les types de valeur car les éléments de la table de hachage sont de type objet et, par conséquent, la mise en boîte et la décompression se produisent généralement lors du stockage ou de la récupération d'un type de valeur.

Pour en savoir plus: Hashtable et Dictionary Collection Types

mparkuk
la source
7

Une autre différence importante est que Hashtable est thread-safe. Hashtable a une sécurité de thread intégrée pour plusieurs lecteurs / écrivain unique (MR / SW), ce qui signifie que Hashtable permet à UN écrivain avec plusieurs lecteurs sans verrouillage.

Dans le cas de Dictionary, il n'y a pas de sécurité des threads; si vous avez besoin de la sécurité des threads, vous devez implémenter votre propre synchronisation.

Pour développer davantage:

Hashtable offre une certaine sécurité des threads via le Synchronized propriété, 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 aucune synchronisation de thread; 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 besoin de la sécurité des types ainsi que de la sécurité des threads, utilisez des classes de collections simultanées dans le .NET Framework. Plus de lecture ici .

Une différence supplémentaire est que lorsque nous ajoutons les entrées multiples dans Dictionnaire, l'ordre dans lequel les entrées sont ajoutées est conservé. Lorsque nous récupérons les éléments du dictionnaire, nous obtenons les enregistrements dans le même ordre que nous les avons insérés. Tandis que Hashtable ne conserve pas l'ordre d'insertion.

NullReference
la source
D'après ce que je comprends, les Hashsetgaranties de sécurité des threads MR / SW dans les scénarios d'utilisation qui n'impliquent pas de suppressions . Je pense qu'il a peut-être été conçu pour être entièrement sûr pour MR / SW, mais la manipulation des suppressions en toute sécurité augmente considérablement les frais de sécurité pour MR / SW. Alors que la conception de Dictionaryaurait pu offrir une sécurité MR / SW à un coût minimal dans les scénarios sans suppression, je pense que MS voulait éviter de traiter les scénarios sans suppression comme "spéciaux".
supercat
5

Une autre différence que je peux comprendre est:

Nous ne pouvons pas utiliser Dictionary <KT, VT> (génériques) avec les services Web. La raison en est qu'aucune norme de service Web ne prend en charge la norme générique.

Peter Mortensen
la source
Nous pouvons utiliser des listes génériques (List <string>) dans un service Web à base de savon. Mais, nous ne pouvons pas utiliser de dictionnaire (ou de table de hachage) dans un service Web. Je pense que la raison en est que le xmlserializer .net ne peut pas gérer l'objet dictionnaire.
Siddharth
5

Dictionary<> est un type générique et il est donc sûr de type.

Vous pouvez insérer n'importe quel type de valeur dans HashTable et cela peut parfois lever une exception. Mais Dictionary<int>n'acceptera que les valeurs entières et Dictionary<string>n'acceptera que les chaînes.

Il est donc préférable d'utiliser Dictionary<>au lieu de HashTable.

Kishore Kumar
la source
0

Dans la plupart des langages de programmation, les dictionnaires sont préférés aux tables de hachage

Je ne pense pas que ce soit nécessairement vrai, la plupart des langues ont l'une ou l'autre, selon la terminologie qu'elles préfèrent .

En C #, cependant, la raison claire (pour moi) est que les tables de hachage C # et les autres membres de l'espace de noms System.Collections sont largement obsolètes. Ils étaient présents dans c # V1.1. Ils ont été remplacés à partir de C # 2.0 par les classes génériques dans l'espace de noms System.Collections.Generic.

kristianp
la source
L'un des avantages d'une table de hachage par rapport à un dictionnaire est que si une clé n'existe pas dans un dictionnaire, elle générera une erreur. Si une clé n'existe pas dans une table de hachage, elle renvoie simplement null.
Bill Norman
En C #, j'éviterais toujours d'utiliser System.Collections.Hashtable car ils n'ont pas l'avantage des génériques. Vous pouvez utiliser TryGetValue ou HasKey du dictionnaire si vous ne savez pas si la clé existera.
kristianp
Oups, pas HasKey, ce devrait être ContainsKey.
kristianp
-3

Selon ce que je vois en utilisant .NET Reflector :

[Serializable, ComVisible(true)]
public abstract class DictionaryBase : IDictionary, ICollection, IEnumerable
{
    // Fields
    private Hashtable hashtable;

    // Methods
    protected DictionaryBase();
    public void Clear();
.
.
.
}
Take note of these lines
// Fields
private Hashtable hashtable;

Nous pouvons donc être sûrs que DictionaryBase utilise un HashTable en interne.

Peter Mortensen
la source
16
System.Collections.Generic.Dictionary <TKey, TValue> ne dérive pas de DictionaryBase.
snemarch
"Nous pouvons donc être sûrs que DictionaryBase utilise un HashTable en interne." - C'est bien, mais ça n'a rien à voir avec la question.
Jim Balter