135 votes

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

J'explore le type 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> est meilleure, mais je ne pouvais pas voir un accès individuel à ses éléments.

Est-ce seulement pour l'énumération?

228voto

Robert Rossney Points 43767

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

Demander si vous pouvez récupérer un seul élément (par exemple, set[45]) est la mauvaise compréhension du concept de la série. Il n'y a pas une telle chose comme la 45e élément d'un ensemble. Les éléments dans un ensemble n'ont aucune commande. Les ensembles de {1, 2, 3} et {2, 3, 1} sont identiques à tous les égards, car ils ont la même composition, et l'adhésion est tout ce qui compte.

C'est un peu dangereux pour effectuer une itération sur un HashSet<T> , car cela impose un ordre 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 l'ordre des éléments dans une collection qui est important pour vous, cette collection n'est pas un ensemble.

Les ensembles sont vraiment limitées. D'autre part, ils sont vraiment rapide.

110voto

280Z28 Points 49515

Voici un exemple réel d'où je utiliser un HashSet<string>:

Une partie de ma syntaxe surligneur pour UnrealScript fichiers est une nouvelle fonctionnalité qui souligne Doxygen-les commentaires de style. J'ai besoin d'être en mesure de dire si un @ ou \ commande est valide pour déterminer si pour l'afficher en gris (valide) ou rouge (non valide). J'ai un HashSet<string> de toutes les commandes valides, donc à chaque fois que j'ai frappé un @xxx token dans l'analyseur lexical, j'utilise validCommands.Contains(tokenText) que mon O(1) un contrôle de validité. J'ai vraiment ne se soucient pas de tout, sauf de l'existence de la commande dans le jeu de commandes valides. Permet de regarder les solutions de rechange que je face:

  • Dictionary<string, ?>: Quel type dois-je utiliser pour la valeur? La valeur est vide de sens puisque je vais juste utiliser ContainsKey. Remarque: Avant D' .NET 3.0, c'était le seul choix pour O(1) recherches - HashSet<T> a été ajouté pour la 3.0 et étendu à mettre en oeuvre ISet<T> pour la version 4.0.
  • List<string>: Si je continue la liste triée, je peux utiliser BinarySearch, ce qui est O(log n) (ne pas voir ce fait mentionné ci-dessus). Cependant, depuis ma liste de commandes valides est une liste fixe qui ne change jamais, ce ne sera jamais plus approprié que de simplement...
  • string[]: Encore une fois, Array.BinarySearch donne O(log n) la performance. Si la liste est courte, cela pourrait être la meilleure option. Il y en a toujours moins d'espace de ressources que l' HashSet, Dictionaryou List. Même avec BinarySearch, il n'est pas plus rapide pour les grands ensembles, mais pour de petits ensembles, il serait intéressant d'expérimenter. Le mien a plusieurs centaines d'articles, donc je suis passé sur le présent.

24voto

Kenan E. K. Points 8497

Un 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> implémente IList<T>, qui s'étend de l' 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; }
}

Un 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 les éléments en double, et dont les éléments sont dans aucun ordre particulier.

Quel est le HashSet gain, si elle perd de l'indice de position//de la liste de comportement?

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

Un HashSet de comportement pourrait être comparé à l'utilisation d'un Dictionary<TKey,TValue> seulement par ajout/suppression de clés, de valeurs, et en ignorant dictionnaire valeurs elles-mêmes. Vous attendez clés dans un dictionnaire de ne pas avoir de doublons, et c'est le point de la partie.

14voto

Carl Manaster Points 23696

Les performances seraient une mauvaise raison de choisir HashSet plutôt que Liste. Au lieu de cela, quoi de mieux traduit votre intention? Si l'ordre est important, Set (ou HashSet) est désactivé. 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 quand vous voulez un Set.

12voto

earl Points 10428

HashSet est mis en œuvre par le malaxage. Un ensemble est une collection de valeurs contenant pas les éléments en double. Les valeurs dans un ensemble sont aussi généralement non ordonnée. Donc non, un jeu ne peut pas être utilisé pour remplacer une liste (à moins que vous devez avoir l'utilisation d'un ensemble en premier lieu).

Si vous vous demandez ce qu'est un jeu peut être bon pour l': n'importe où vous voulez vous débarrasser des doublons, évidemment. Comme un peu artificiel exemple, disons que vous avez une liste de 10.000 révisions d'un logiciel projets, et voulez-vous savoir comment beaucoup de personnes ont contribué à ce projet. Vous pouvez utiliser un Set<string> et itérer sur la liste des révisions et de l'ajout de chaque révision de l'auteur à l'ensemble. Une fois que vous avez terminé l'itération, la taille de la série est à la réponse que vous recherchez.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X