Quelle est la différence entre HashSet <T> et List <T>?

156

Pouvez-vous expliquer quelle est la différence entre HashSet<T>et List<T>dans .NET?

Peut-être pouvez-vous expliquer par un exemple dans quels cas HashSet<T>il faut préférer List<T>?

crayonGâteau
la source
22
Quelques lectures sur le sujet: C # /. NET Fundamentals: Choosing the Right Collection Class
Fredrik Mörk
Je vous suggère de consulter les articles Wikipedia sur en.wikipedia.org/wiki/Hash_table et en.wikipedia.org/wiki/Dynamic_array .
mqp
Pour les performances, voir hashset-vs-list-performance
nawfal

Réponses:

213

Contrairement à une liste <> ...

  1. Un HashSet est une liste sans membres en double.

  2. Parce qu'un HashSet est contraint de ne contenir que des entrées uniques, la structure interne est optimisée pour la recherche (par rapport à une liste) - c'est considérablement plus rapide

  3. L'ajout à un HashSet renvoie un booléen - false si l'ajout échoue en raison de l'existence déjà dans l'ensemble

  4. Peut effectuer des opérations d'ensemble mathématiques sur un ensemble: Union / Intersection / IsSubsetOf etc.

  5. HashSet n'implémente pas IList uniquement ICollection

  6. Vous ne pouvez pas utiliser d'index avec un HashSet, uniquement des énumérateurs.

La principale raison d'utiliser un HashSet serait si vous souhaitez effectuer des opérations Set.

Étant donné 2 ensembles: hashSet1 et hashSet2

 //returns a list of distinct items in both sets
 HashSet set3 = set1.Union( set2 );

vole en comparaison avec une opération équivalente utilisant LINQ. C'est aussi plus soigné à écrire!

BonyT
la source
IDK, j'ai eu des problèmes de Unionméthode. J'avais utilisé à la UnionWithplace.
utilisateur
2
+1 pour "La principale raison d'utiliser un HashedSet serait si vous souhaitez effectuer des opérations Set."
LCJ
12
En fait, je préfère la réponse qui souligne que les HashSets conviennent dans les cas où vous pouvez traiter votre collection comme des «articles de sac». Les opérations de pose ne sont pas aussi fréquentes que les contrôles de confinement. À tout moment où vous avez un ensemble d'éléments uniques (par exemple des codes) et que vous devez vérifier le confinement, un HashSet est pratique.
ThunderGr
Bonne réponse. Je suis tenté d'ajouter également quelques différences de caractéristiques de performance.
nawfal
1
Question: la raison principale est de ne pas avoir la certitude de ne pas avoir d'articles en double?
Andrea Scarafoni
54

Pour être plus précis, démontrons avec des exemples,

Vous ne pouvez pas utiliser HashSet comme dans l'exemple suivant.

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"};
for (int i = 0; i < hashSet1.Count; i++)
    Console.WriteLine(hashSet1[i]);

hashSet1[i] produirait une erreur:

Impossible d'appliquer l'indexation avec [] à une expression de type "System.Collections.Generic.HashSet"

Vous pouvez utiliser l'instruction foreach:

foreach (var item in hashSet1)
    Console.WriteLine(item);

Vous ne pouvez pas ajouter d'éléments dupliqués à HashSet alors que List vous permet de le faire et pendant que vous ajoutez un élément à HashSet, vous pouvez vérifier s'il contient l'élément ou non.

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"};
if (hashSet1.Add("1"))
   Console.WriteLine("'1' is successfully added to hashSet1!");
else
   Console.WriteLine("'1' could not be added to hashSet1, because it contains '1'");

HashSet a quelques fonctions utiles comme IntersectWith, UnionWith, IsProperSubsetOf, ExceptWith, SymmetricExceptWithetc.

IsProperSubsetOf:

HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "4" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" };
HashSet<string> hashSet3 = new HashSet<string>() { "1", "2", "3", "4", "5" };
if (hashSet1.IsProperSubsetOf(hashSet3))
    Console.WriteLine("hashSet3 contains all elements of hashSet1.");
if (!hashSet1.IsProperSubsetOf(hashSet2))
    Console.WriteLine("hashSet2 does not contains all elements of hashSet1.");

UnionWith:

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" };
hashSet1.UnionWith(hashSet2); //hashSet1 -> 3, 2, 4, 6, 8

IntersectWith:

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" }
hashSet1.IntersectWith(hashSet2);//hashSet1 -> 4, 8

ExceptWith :

 HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" };
 HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" };
 hashSet1.ExceptWith(hashSet2);//hashSet1 -> 5, 6

SymmetricExceptWith :

 HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" };
 HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" };
 hashSet1.SymmetricExceptWith(hashSet2);//hashSet1 -> 4, 5, 6

À propos, l'ordre n'est pas conservé dans les HashSets. Dans l'exemple, nous avons ajouté l'élément "2" en dernier mais il est dans le second ordre:

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" };
hashSet1.Add("1");    // 3, 4, 8, 1
hashSet1.Remove("4"); // 3, 8, 1
hashSet1.Add("2");    // 3, 2 ,8, 1
GorkemHalulu
la source
51

A HashSet<T>est une classe conçue pour vous donner une O(1)recherche de confinement (c'est-à-dire, cette collection contient-elle un objet particulier et dites-moi la réponse rapidement).

A List<T>est une classe conçue pour vous donner une collection avec O(1)un accès aléatoire qui peut croître dynamiquement (pensez tableau dynamique). Vous pouvez tester le confinement dans le O(n)temps (à moins que la liste ne soit triée, vous pouvez alors effectuer une recherche binaire dans le O(log n)temps).

Peut-être pouvez-vous expliquer avec un exemple dans quels cas HashSet<T>il faut préférerList<T>

Lorsque vous souhaitez tester le confinement dans O(1).

Jason
la source
Sauf que c'est O (log n) si la liste est triée; c'est, après tout, plus rapide que la recherche dans une liste non triée.
Andrei
20

Utilisez un List<T>lorsque vous souhaitez:

  • Stockez une collection d'articles dans un certain ordre.

Si vous connaissez l'index de l'élément souhaité (plutôt que la valeur de l'élément lui-même), la récupération est O(1). Si vous ne connaissez pas l'index, la recherche de l'élément prend plus de temps, O(n)pour une collection non triée.

Utilisez un Hashset<T>lorsque vous souhaitez:

  • Découvrez rapidement si un certain objet est contenu dans une collection.

Si vous connaissez le nom de la chose que vous voulez trouver, Lookup est O(1)(c'est la partie 'Hash'). Il ne maintient pas un ordre comme le List<T>fait et vous ne pouvez pas stocker de doublons (l'ajout d'un doublon n'a aucun effet, c'est la partie 'Set').

Un exemple de quand utiliser un Hashset<T>serait si vous voulez savoir si un mot joué dans une partie de Scrabble est un mot valide en anglais (ou dans une autre langue). Ce serait encore mieux si vous vouliez créer un service Web à utiliser par toutes les instances d'une version en ligne d'un tel jeu.

Un List<T>serait une bonne structure de données pour créer le tableau de bord pour suivre les scores des joueurs.

Waylon Flinn
la source
15

La liste est une liste ordonnée. C'est

  • accessible par un index entier
  • peut contenir des doublons
  • a un ordre prévisible

HashSet est un ensemble. Il:

  • Peut bloquer les éléments en double (voir Ajouter (T) )
  • Ne garantit pas l'ordre des articles de l'ensemble
  • A des opérations que vous attendez sur un ensemble, par exemple , IntersectWith, IsProperSubsetOf, UnionWith.

La liste est plus appropriée lorsque vous souhaitez accéder à votre collection comme s'il s'agissait d'un tableau auquel vous pourriez ajouter, insérer et supprimer des éléments. HashSet est un meilleur choix si vous voulez traiter votre collection comme un "sac" d'articles dans lequel l'ordre n'est pas important ou lorsque vous voulez le comparer avec d'autres ensembles en utilisant les opérations telles que IntersectWith ou UnionWith.

dgvid
la source
3

La liste n'est pas nécessairement unique, tandis que hashset l'est, pour un.

les connecteurs
la source
3

Une liste est une collection ordonnée d'objets de type T qui, contrairement à un tableau, vous pouvez ajouter et supprimer des entrées.

Vous utiliseriez une liste dans laquelle vous souhaitez référencer les membres dans l'ordre dans lequel vous les avez stockés et vous y accédez par une position plutôt que par l'élément lui-même.

Un HashSet est comme un dictionnaire que l'élément lui-même est la clé ainsi que la valeur, le classement n'est pas garanti.

Vous utiliseriez un HashSet où vous voulez vérifier qu'un objet est dans la collection

Bob Vale
la source
1
Pour clarifier, au cas où quelqu'un d'autre lirait mal à première vue - Listmaintient un ordre (c'est-à-dire quand les choses ont été ajoutées), mais ne trie pas automatiquement les éléments. Vous devrez appeler .Sortou utiliser un SortedList.
drzaus
1

Si vous décidez d'appliquer ces structures de données à l'utilisation réelle dans le développement piloté par les données, un HashSet est TRÈS utile pour tester la réplication par rapport aux sources d'adaptateur de données, pour le nettoyage et la migration des données.

De plus, si vous utilisez la classe DataAnnotations, vous pouvez implémenter la logique de clé sur les propriétés de classe et contrôler efficacement un index naturel (en cluster ou non) avec un HashSet, où cela serait très difficile dans une implémentation List.

Une option intéressante pour utiliser une liste consiste à implémenter des génériques pour plusieurs supports sur un modèle de vue, comme l'envoi d'une liste de classes à une vue MVC pour un assistant DropDownList, et également pour l'envoi en tant que construction JSON via WebApi. La liste permet une logique de collecte de classe typique, et conserve la flexibilité pour une approche plus «interface» pour calculer un modèle de vue unique sur différents supports.

Nathan Teague
la source