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

134

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?

Joan Venge
la source

Réponses:

228

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.

Robert Rossney
la source
1
Le fait que le cadre fournisse une SortedSetstructure de données contredit ce que vous dites sur l'ordre n'étant pas une propriété d'un ensemble - ou indique un malentendu de l'équipe de développement.
Veverke
10
Je pense qu'il est plus correct de dire que l'ordre des éléments dans le HashSetn'est pas défini, alors ne vous fiez pas à l'ordre de l'itérateur. Si vous parcourez l'ensemble parce que vous faites quelque chose contre les éléments de l'ensemble, ce n'est pas dangereux à moins que vous ne vous fiez à quelque chose lié à l'ordre. A SortedSeta toutes les propriétés de l' ordre HashSet plus , mais SortedSetne dérive pas de HashSet; reformulé, un SortedSet est une collection ordonnée d'objets distincts .
Kit du
110

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.
Sam Harwell
la source
24

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

Kenan EK
la source
14

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.

Carl Manaster
la source
21
Performance would be a bad reason to choose HashSet over List: Je ne suis tout simplement pas d'accord avec vous. C'est en quelque sorte dire que choisir un Dictionray au lieu de deux listes n'aide pas les performances. Jetez un œil à l'article suivant
Oscar Mederos
11
@Oscar: Je n'ai pas dit que les sets n'étaient pas plus rapides - j'ai dit que ce serait une mauvaise base pour les choisir. Si vous essayez de représenter une collection ordonnée, un ensemble ne fonctionnera tout simplement pas et ce serait une erreur d'essayer de le faire entrer; si la collection que vous voulez n'a pas de commande, un ensemble est parfait - et rapide. Mais ce qui est important, c'est la première question: qu'essayez-vous de représenter?
Carl Manaster
2
Mais pensez-y. Si vous voulez continuer à vérifier si des chaînes données sont membres d'une collection de 10 000 chaînes, techniquement, string[].Containset HashSet<string>.Containsexprimez également bien votre intention; la raison de choisir le HashSet est qu'il fonctionnera beaucoup plus rapidement.
Casey
12

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.

comte
la source
Mais Set ne permet pas la récupération d'éléments uniques? Comme ensemble [45]?
Joan Venge
2
Pour cela, vous itérez sur les membres de l'ensemble. D'autres opérations typiques consistent à vérifier si l'ensemble contient un élément ou à obtenir la taille de l'ensemble.
Earl
11

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"};

Thomas.Benz
la source
6

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.

sepp2k
la source
Si vous les parcourez uniquement, la méthode HashSet ajoute un peu d'utilisation de la mémoire par rapport à la liste.
SamuelWarren
5

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.

Noldorin
la source
1
L'ajout d'un élément existant à un ensemble ne lèvera pas d'exception. Add renverra simplement faux. Aussi: techniquement, la recherche de hachage est O (n), pas O (1), sauf si vous avez une fonction de hachage parfaite. Bien sûr, dans la pratique, vous vous en sortirez en supposant que c'est O (1) à moins que la fonction de hachage soit vraiment mauvaise.
sepp2k
1
@ sepp2k: Ouais, donc il renvoie un booléen ... Le fait est qu'il vous avertit. Et la recherche de hachage est le pire des cas O (n) si vous faites un seau est terrible - c'est beaucoup plus proche de O (1) en général.
Noldorin
4

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.

Steve Guidi
la source
2
Autre mise en garde: les ensembles ne permettent généralement qu'une seule occurrence d'un élément.
Steve Guidi
1

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)

Addys
la source
5
À moins que vous ne vous souciez de la clé, vous devez utiliser le dictionnaire.
Hardwareguy
1

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.

c_buk
la source