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

Question

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

Peut-être pouvez-vous expliquer avec un exemple dans quels cas HashSet<T> doit être préféré à List<T> ?

Answer 1

Contrairement à une liste<> ...

1. Un HashSet est une liste dont les membres ne sont pas en double.

2. Comme 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) - elle est considérablement plus rapide.

3. L'ajout à un HashSet renvoie un booléen - false si l'ajout échoue parce qu'il existe déjà dans l'ensemble.

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

5. HashSet ne met pas en œuvre IList, mais seulement ICollection.

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

La principale raison d'utiliser un HashSet est que 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 );

s'envole par rapport à une opération équivalente utilisant LINQ. C'est aussi plus facile à écrire !

Answer 2

Pour être plus précis, prenons 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 des éléments dupliqués à HashSet alors que List vous permet de le faire et lorsque 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 possède quelques fonctions utiles comme IntersectWith , UnionWith , IsProperSubsetOf , ExceptWith , SymmetricExceptWith etc.

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 préservé dans les HashSets. Dans l'exemple, nous avons ajouté l'élément "2" en dernier, mais il est dans le deuxième 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

Answer 3

A HashSet<T> est un cours conçu pour vous donner O(1) recherche de contenu (c'est-à-dire, est-ce que cette collection contient un objet particulier, et donnez-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 à un tableau dynamique). Vous pouvez tester le confinement dans O(n) (sauf si la liste est triée, auquel cas vous pouvez effectuer une recherche binaire dans le temps). O(log n) temps).

Peut-être pouvez-vous expliquer avec un exemple dans quels cas HashSet<T> doit être préférée à List<T>

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

Answer 4

Utilisez un List<T> quand vous le voulez :

• Stocker une collection d'éléments dans un certain ordre.

Si vous connaissez l'indice de l'élément que vous voulez (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, trouver l'élément prend plus de temps, O(n) pour une collection non triée.

Utilisez un Hashset<T> quand vous le voulez :

• 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 d'ordre comme le fait le List<T> et vous ne pouvez pas stocker les doublons (l'ajout d'un doublon n'a aucun effet, c'est la partie "Set").

Un exemple d'utilisation d'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 construire un service web qui serait utilisé par toutes les instances d'une version en ligne d'un tel jeu.

A List<T> serait une bonne structure de données pour créer le tableau d'affichage des scores des joueurs.

Answer 5

La liste est une liste ordonnée. Elle est

• accessible par un indice 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 éléments de l'ensemble.
• Il comporte les opérations que l'on peut attendre d'un poste, 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 pouvez ajouter, insérer et supprimer des éléments. HashSet est un meilleur choix si vous voulez traiter votre collection comme un "sac" d'éléments dans lequel l'ordre n'est pas important ou si vous voulez la comparer avec d'autres ensembles en utilisant des opérations telles que IntersectWith ou UnionWith.