Quand dois-je utiliser le type HashSet <T>?

J'explore le HashSet<T>type, mais je ne comprends pas où il se situe dans les collections.

Peut-on l'utiliser pour remplacer un List<T>? J'imagine que les performances de a HashSet<T>sont meilleures, mais je ne voyais pas l'accès individuel à ses éléments.

Est-ce uniquement pour le dénombrement?

L'important HashSet<T>est juste là dans le nom: c'est un ensemble . La seule chose que vous pouvez faire avec un seul ensemble est d'établir quels sont ses membres et de vérifier si un élément est un membre.

Demander si vous pouvez récupérer un seul élément (par exemple set[45]), c'est mal comprendre le concept de l'ensemble. Le 45e élément d'un ensemble n'existe pas. Les articles d'un ensemble ne sont pas classés. Les ensembles {1, 2, 3} et {2, 3, 1} sont identiques à tous égards car ils ont la même appartenance, et l'appartenance est tout ce qui compte.

Il est quelque peu dangereux d'itérer sur un HashSet<T>car cela impose un ordre aux éléments de l'ensemble. Cet ordre n'est pas vraiment une propriété de l'ensemble. Vous ne devriez pas vous y fier. Si l'ordre des éléments d'une collection est important pour vous, cette collection n'est pas un ensemble.

Les ensembles sont vraiment limités et avec des membres uniques. D'un autre côté, ils sont vraiment rapides.

Voici un exemple réel où j'utilise un HashSet<string>:

Une partie de mon surligneur de syntaxe pour les fichiers UnrealScript est une nouvelle fonctionnalité qui met en évidence les commentaires de style Doxygen . Je dois être en mesure de dire si une commande @ou \est valide pour déterminer s'il faut l'afficher en gris (valide) ou en rouge (invalide). J'ai une HashSet<string>de toutes les commandes valides, donc chaque fois que je frappe un @xxxjeton dans le lexer, je l'utilise validCommands.Contains(tokenText)comme contrôle de validité O (1). Je ne me soucie vraiment de rien sauf de l' existence de la commande dans l' ensemble des commandes valides. Regardons les alternatives auxquelles j'ai été confronté:

• Dictionary<string, ?>: Quel type dois-je utiliser pour la valeur? La valeur n'a pas de sens puisque je vais juste l'utiliser ContainsKey. Remarque: Avant .NET 3.0, c'était le seul choix pour les recherches O (1) - a HashSet<T>été ajouté pour 3.0 et étendu pour implémenter ISet<T>pour 4.0.
• List<string>: Si je garde la liste triée, je peux utiliser BinarySearch, qui est O (log n) ( je n'ai pas vu ce fait mentionné ci-dessus). Cependant, puisque ma liste de commandes valides est une liste fixe qui ne change jamais, cela ne sera jamais plus approprié que simplement ...
• string[]: Encore une fois, Array.BinarySearchdonne les performances O (log n). Si la liste est courte, cela pourrait être l'option la plus performante. Il a toujours moins de frais généraux de l' espace que HashSet, Dictionaryou List. Même avec BinarySearch, ce n'est pas plus rapide pour les grands ensembles, mais pour les petits ensembles, cela vaut la peine d'essayer. Le mien a plusieurs centaines d'articles, alors je l'ai transmis.

A HashSet<T>implémente l' ICollection<T>interface:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    // Methods
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);

    // Properties
   int Count { get; }
   bool IsReadOnly { get; }
}

Un List<T>outil IList<T>, qui prolonge laICollection<T>

public interface IList<T> : ICollection<T>
{
    // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);

    // Properties
    T this[int index] { get; set; }
}

Un HashSet a défini une sémantique, implémentée via une table de hachage en interne:

Un ensemble est une collection qui ne contient aucun élément en double et dont les éléments ne sont pas dans un ordre particulier.

Que gagne le HashSet s'il perd son comportement d'index / position / liste?

L'ajout et la récupération d'éléments à partir du HashSet se font toujours par l'objet lui-même, pas via un indexeur, et à proximité d'une opération O (1) (List is O (1) add, O (1) retrieve by index, O (n) find /retirer).

Le comportement d'un HashSet pourrait être comparé à l'utilisation de a Dictionary<TKey,TValue>en ajoutant / supprimant uniquement des clés en tant que valeurs et en ignorant les valeurs du dictionnaire elles-mêmes. Vous vous attendriez à ce que les clés d'un dictionnaire n'aient pas de valeurs en double, et c'est le but de la partie "Set".

Les performances seraient une mauvaise raison de choisir HashSet sur List. Au lieu de cela, qu'est-ce qui capture mieux votre intention? Si l'ordre est important, alors Set (ou HashSet) est sorti. Si les doublons sont autorisés, de même. Mais il y a beaucoup de circonstances où nous ne nous soucions pas de l'ordre, et nous préférons ne pas avoir de doublons - et c'est là que vous voulez un ensemble.

HashSet est un ensemble implémenté par hachage. Un ensemble est une collection de valeurs ne contenant aucun élément en double. Les valeurs d'un ensemble sont également généralement non ordonnées. Donc non, un ensemble ne peut pas être utilisé pour remplacer une liste (sauf si vous auriez dû utiliser un ensemble en premier lieu).

Si vous vous demandez à quoi sert un ensemble: partout où vous voulez vous débarrasser des doublons, évidemment. À titre d'exemple légèrement artificiel, disons que vous avez une liste de 10.000 révisions d'un projet logiciel, et que vous voulez savoir combien de personnes ont contribué à ce projet. Vous pouvez utiliser a Set<string>et parcourir la liste des révisions et ajouter l'auteur de chaque révision à l'ensemble. Une fois que vous avez terminé l'itération, la taille de l'ensemble est la réponse que vous recherchiez.

HashSet serait utilisé pour supprimer les éléments en double dans une collection IEnumerable. Par exemple,

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

après l'exécution de ces codes, uniqueStrings contient {"abc", "ghjr", "yre", "obm", "qwrt", "vyeu"};

L'utilisation la plus courante des ensembles de hachage est probablement de voir s'ils contiennent un certain élément, qui est proche d'une opération O (1) pour eux (en supposant une fonction de hachage suffisamment forte), par opposition aux listes pour lesquelles le contrôle d'inclusion est O ( n) (et les ensembles triés pour lesquels il est O (log n)). Donc, si vous faites beaucoup de vérifications pour savoir si un élément est contenu dans une liste, les hahssets peuvent améliorer les performances. Si vous ne les parcourez que jamais, il n'y aura pas beaucoup de différence (l'itération sur l'ensemble complet est O (n), comme avec les listes et les hachages ont un peu plus de surcharge lors de l'ajout d'éléments).

Et non, vous ne pouvez pas indexer un ensemble, ce qui n'aurait pas de sens de toute façon, car les ensembles ne sont pas ordonnés. Si vous ajoutez des éléments, l'ensemble ne se souviendra pas lequel était le premier, et quel second etc.

HashSet<T>est une structure de données dans le framework .NET capable de représenter un ensemble mathématique en tant qu'objet. Dans ce cas, il utilise des codes de hachage (le GetHashCoderésultat de chaque élément) pour comparer l'égalité des éléments d'ensemble.

Un ensemble diffère d'une liste en ce qu'il n'autorise qu'une seule occurrence du même élément qu'il contient. HashSet<T>reviendra simplement falsesi vous essayez d'ajouter un deuxième élément identique. En effet, la recherche des éléments est très rapide ( O(1)temps), puisque la structure de données interne est simplement une table de hachage.

Si vous vous demandez lequel utiliser, notez que l'utilisation d'un List<T>where HashSet<T>est approprié n'est pas la plus grande erreur, bien que cela puisse potentiellement entraîner des problèmes où vous avez des éléments en double indésirables dans votre collection. De plus, la recherche (récupération des éléments) est beaucoup plus efficace - idéalement O(1)(pour un compartimentage parfait) au lieu du O(n)temps - ce qui est assez important dans de nombreux scénarios.

List<T>est utilisé pour stocker des ensembles d'informations ordonnés. Si vous connaissez l'ordre relatif des éléments de la liste, vous pouvez y accéder en temps constant. Cependant, pour déterminer où se trouve un élément dans la liste ou pour vérifier s'il existe dans la liste, le temps de recherche est linéaire. En revanche, HashedSet<T>ne donne aucune garantie sur l'ordre des données stockées et fournit par conséquent un temps d'accès constant à ses éléments.

Comme son nom l'indique, HashedSet<T>est une structure de données qui implémente une sémantique d'ensemble . La structure des données est optimisée pour mettre en œuvre des opérations d'ensemble (c'est-à-dire Union, Différence, Intersection), ce qui ne peut pas être fait aussi efficacement avec la mise en œuvre de liste traditionnelle.

Ainsi, le choix du type de données à utiliser dépend vraiment de ce que vous essayez de faire avec votre application. Si vous ne vous souciez pas de la façon dont vos éléments sont classés dans une collection et que vous souhaitez uniquement énumérer ou vérifier leur existence, utilisez HashSet<T>. Sinon, envisagez d'utiliser List<T>ou une autre structure de données appropriée.

En bref - chaque fois que vous êtes tenté d'utiliser un dictionnaire (ou un dictionnaire où S est une propriété de T), vous devriez envisager un HashSet (ou HashSet + implémentant IEquatable sur T qui équivaut à S)

Dans le scénario de base prévu, HashSet<T>vous devez utiliser lorsque vous souhaitez des opérations d'ensemble plus spécifiques sur deux collections que celles fournies par LINQ. Méthodes de LINQ aiment Distinct, Union, Intersectet Exceptsont assez dans la plupart des situations, mais parfois vous pourriez avoir besoin plus d' opérations grains fins et HashSet<T>fournit:

• UnionWith
• IntersectWith
• ExceptWith
• SymmetricExceptWith
• Overlaps
• IsSubsetOf
• IsProperSubsetOf
• IsSupersetOf
• IsProperSubsetOf
• SetEquals

Une autre différence entre HashSet<T>les méthodes LINQ et «qui se chevauchent» est que LINQ renvoie toujours un nouveau IEnumerable<T>et que les HashSet<T>méthodes modifient la collection source.