Quand dois-je utiliser le HashSet type?

Question

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

Peut-on l'utiliser pour remplacer un List<T>? J'imagine que la performance d'un HashSet<T> pour être mieux, mais je ne pouvais pas voir l'accès individuel à ses éléments.

Est-il seulement pour le dénombrement?

Answer 1

La chose importante à propos HashSet<T> est là dans le nom: il est set . Les seules choses que vous pouvez faire avec un ensemble unique est d'établir quels sont ses membres, et de vérifier si un élément est membre.

demandé si vous pouvez récupérer un seul élément (par exemple set[45]) est conception erronée de la l'ensemble. Il n'y a pas une telle chose comme l'élément 45e d'un ensemble. Les éléments d'un ensemble ne sont pas ordonnés. Les ensembles {1, 2, 3} et {2, 3, 1} sont identiques à tous égards parce qu'ils ont les mêmes membres, et l'adhésion est tout ce qui compte.

Il est un peu dangereux pour itérer sur un HashSet<T> car cela impose donc une commande sur les éléments de l'ensemble. Cet ordre n'est pas vraiment une propriété de l'ensemble. Vous ne devriez pas compter sur elle. Si la commande des éléments d'une collection est importante pour vous, cette collection est pas un ensemble.

Les ensembles sont vraiment limités et avec les membres uniques. D'autre part, ils sont très vite.

Answer 2

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

Une partie de ma coloration syntaxique pour les fichiers UnrealScript est une nouvelle fonctionnalité qui Faits saillants commentaires de style Doxygen . Je dois être en mesure de dire si une commande @ ou \ est valide pour déterminer si pour les afficher en gris (valide) ou rouge (invalide). J'ai un HashSet<string> de toutes les commandes valides, donc chaque fois que je frappe un jeton @xxx dans le lexer, j'utilise validCommands.Contains(tokenText) comme mon O (1) contrôle de validité. Je ne me soucie pas vraiment de rien, sauf existence de la commande dans le set de commandes valides. Permet de regarder les alternatives que j'ai rencontrés:

• Dictionary<string, ?>: Quel type dois-je utiliser pour la valeur? La valeur n'a pas de sens que je vais juste utiliser ContainsKey. Remarque:. Avant .NET 3.0 c'était le seul choix pour O (1) lookups - HashSet<T> a été ajouté pour 3.0 et étendu à mettre en œuvre pour ISet<T> 4.0
• List<string>: Si je garde la liste triée, je peux utiliser BinarySearch, qui est O (log n) (n'a pas vu ce fait mentionné ci-dessus). Cependant, étant donné que ma liste des commandes valides est une liste fixe qui ne change jamais, ce ne sera jamais plus approprié que simplement ...
• string[]: Encore une fois, Array.BinarySearch donne O (log n) performance. Si la liste est courte, cela pourrait être la meilleure option performante. Il a toujours moins de frais généraux de l'espace que HashSet, Dictionary ou List. Même avec BinarySearch, ce n'est pas plus rapide pour les grands ensembles, mais pour les petits ensembles, il serait utile d'expérimenter. Le mien a plusieurs centaines de points, donc je passé à ce sujet.

Answer 3

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

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

A List<T> implémente IList<T>, qui étend la ICollection<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; }
}

A HashSet a mis en sémantique, mis en œuvre par l'intermédiaire d'une table de hachage en interne:

  

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

Qu'est-ce que le gain de HashSet, si elle perd index / position / comportement de la liste?

Ajout et récupération d'éléments de la HashSet est toujours par l'objet lui-même, non pas par un indexeur, et à proximité d'un O (1) opération (liste est O (1) ajouter, O (1) récupérer par index, O ( n) trouver / supprimer).

Le comportement d'un HashSet pourrait être comparé à l'aide d'un Dictionary<TKey,TValue> que par l'ajout / suppression des clés sous forme de valeurs, et en ignorant le dictionnaire eux-mêmes valeurs. Vous attendez clés dans un dictionnaire de ne pas avoir des valeurs en double, et c'est le point de la partie « Set ».

Answer 4

La performance serait une mauvaise raison de choisir HashSet sur la liste. Au lieu de cela, ce qui permet de mieux saisir votre intention? Si l'ordre est important, puis sertis (ou HashSet) est sorti. Si les doublons sont autorisés, de même. Mais il y a beaucoup de circonstances où nous ne se soucient pas de l'ordre, et nous préférons ne pas avoir des doublons - et c'est quand vous voulez un ensemble

.

Answer 5

HashSet est set mis en œuvre en hachant. Un ensemble est un ensemble de valeurs ne contenant pas d'éléments en double. Les valeurs dans un ensemble sont aussi généralement non ordonnée. Donc non, un ensemble ne peut pas être utilisé pour remplacer une liste (à moins que vous auriez dû utiliser un ensemble en premier lieu).

Si vous vous demandez ce qu'est un jeu pourrait être bon pour: partout où vous voulez vous débarrasser des doublons, évidemment. A titre d'exemple légèrement artificiel, disons que vous avez une liste de 10.000 révisions d'un des projets logiciels, et que vous voulez savoir combien de personnes ont contribué à ce projet. Vous pouvez utiliser un Set<string> et itérer sur la liste des révisions et ajouter l'auteur de chaque révision à l'ensemble. Une fois que vous avez terminé itérer, la taille de l'ensemble est la réponse que vous recherchez.

Answer 6

HashSet serait utilisé pour supprimer les doublons dans une collection IEnumerble. 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 ces codes sont exécutés, uniqueStrings détient { "abc", "ghjr", "MCs", "OBM", "qwrt", "vyeu"};

Answer 7

L'utilisation la plus courante pour HashSet est de voir si elles contiennent un certain élément, qui est proche d'un O (1) opération pour eux (en supposant une fonction de hachage suffisamment forte), par opposition aux listes pour lesquelles vérifient l'inclusion est O (n) (et triées ensembles pour lesquels il est en O (log n)). Donc, si vous faites beaucoup de contrôles, si un élément est contenu dans une liste, hahssets pourrait être une amélioration de la performance. Si vous ne jamais itérer sur eux, il n'y aura pas beaucoup de différence (itérer sur l'ensemble est O (n), même que des listes et HashSet ont un peu plus frais généraux lors de l'ajout d'éléments).

Et non, vous ne pouvez pas indexer un ensemble, ce qui ne serait pas logique de toute façon, parce que les ensembles ne sont pas ordonnés. Si vous ajoutez des éléments, l'ensemble ne se souviendra que l'on était d'abord, et qui seconde etc.

Answer 8

List<T> est utilisé pour stocker des ensembles d'informations commandés. Si vous connaissez l'ordre relatif des éléments de la liste, vous pouvez y accéder à temps constant. Toutefois, pour déterminer où se trouve un élément dans la liste ou pour vérifier si elle existe dans la liste, la durée de consultation est linéaire. D'autre part, HashedSet<T> fait aucune garantie de l'ordre des données stockées et fournit par conséquent le temps d'accès constant pour ses éléments.

Comme son nom l'indique, HashedSet<T> est une structure de données qui implémente définir la sémantique . La structure de données est optimisé pour la mise en œuvre des opérations ensemble (à savoir l'Union, différence, Intersection), qui ne peut se faire de manière aussi efficace avec la mise en œuvre de la liste traditionnelle.

Alors, pour choisir le type de données à utiliser dépend vraiment de ce que vous êtes tenter de le faire avec votre application. Si vous ne se soucient pas de la façon dont vos éléments sont ordonnés dans une collection, et ne veulent que enumarate ou vérifier l'existence, l'utilisation HashSet<T>. Sinon, pensez à utiliser List<T> ou d'une autre structure de données appropriée.

Answer 9

HashSet<T> est une strucutre de données dans le cadre .NET qui est capable de représenter un mathématique définir comme un objet. Dans ce cas, il utilise des codes de hachage (le résultat de GetHashCode de chaque élément) pour comparer l'égalité des éléments de l'ensemble.

Un ensemble diffère d'une liste en ce qu 'il ne permet qu'une seule occurrence du même élément qu'il contient. HashSet<T> va simplement revenir false si vous essayez d'ajouter un deuxième élément identique. En effet, la recherche d'éléments est très rapide (temps de O(1)), étant donné que la structure interne des données est tout simplement un Hashtable.

Si vous vous demandez qui à utiliser, notez que l'utilisation d'un List<T> où HashSet<T> est est pas la correspond le plus grosse erreur, mais elle peut potentiellement permettre à des problèmes où vous avez des éléments indésirables en double dans votre collection. Qui plus est, la recherche (récupération des éléments) est beaucoup plus efficace - idéalement O(1) (pour héliporté parfait) au lieu du temps de O(n) -. Ce qui est assez important dans de nombreux scénarios

Answer 10

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

Answer 11

Dans le HashSet<T> scénario prévu de base doit être utilisé lorsque vous souhaitez des opérations plus spécifiques sur ensemble deux collections que LINQ fournit. méthodes LINQ comme Distinct, Union, Intersect et Except suffisent dans la plupart des situations, mais parfois vous pouvez avoir besoin de plus des opérations à grains fins et HashSet<T> fournit:

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

Une autre différence entre LINQ et HashSet<T> méthodes « chevauchant » est que LINQ renvoie toujours une nouvelle IEnumerable<T>, et les méthodes de HashSet<T> modifier la collection source.