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

Question

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

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

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

Answer 1

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

Demander si l'on peut récupérer un seul élément (par ex. set[45] ) est une mauvaise compréhension du concept de l'ensemble. Le 45e élément d'un ensemble n'existe pas. Les éléments d'un ensemble ne sont pas ordonné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 une 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 comportent des membres uniques. D'un autre côté, ils sont très rapides.

Answer 2

Voici un exemple concret où j'utilise une HashSet<string> :

Une partie de mon surligneur syntaxique pour les fichiers UnrealScript est une nouvelle fonctionnalité qui met en évidence les commentaires de style Doxygen . Je dois être capable de dire si un @ ou \ est valide pour déterminer s'il faut l'afficher en gris (valide) ou en rouge (invalide). J'ai un HashSet<string> de toutes les commandes valides, donc à chaque fois que j'atteins une @xxx dans le lexer, j'utilise validCommands.Contains(tokenText) comme mon contrôle de validité O(1). Je ne me soucie vraiment de rien, sauf existence de la commande dans le set de commandes valides. Voyons 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 utiliser ContainsKey . Remarque : avant .NET 3.0, c'était le seul choix possible pour les recherches en O(1). HashSet<T> a été ajouté pour la version 3.0 et étendu afin d'implémenter l'option ISet<T> pour 4.0.
• List<string> : Si je garde la liste triée, je peux utiliser BinarySearch ce 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 de simplement...
• string[] : Encore, Array.BinarySearch donne des performances O(log n). Si la liste est courte, cela peut être l'option la plus performante. Elle a toujours moins d'encombrement que HashSet , Dictionary ou List . Même avec BinarySearch Il n'est pas plus rapide pour les grands ensembles, mais pour les petits ensembles, cela vaut la peine d'expérimenter. Le mien comporte plusieurs centaines d'éléments, alors j'ai laissé tomber.

Answer 3

A HashSet<T> met en œuvre la 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; }
}

A List<T> met en œuvre IList<T> qui étend le 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 une sémantique d'ensemble, implémentée via une table de hachage en interne :

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

Qu'est-ce que le HashSet gagne, s'il perd le comportement index/position/liste ?

L'ajout et la récupération d'éléments dans le HashSet se fait toujours par l'objet lui-même, sans passer par un indexeur, et est proche d'une opération O(1) (List est O(1) add, O(1) retrieve by index, O(n) find/remove).

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

Answer 4

La performance serait une mauvaise raison de choisir HashSet plutôt que List. À la place, qu'est-ce qui correspond le mieux à votre intention ? Si l'ordre est important, alors Set (ou HashSet) est à proscrire. Si les doublons sont autorisés, il en va de même. Mais il existe de nombreuses circonstances où l'ordre n'est pas important, et où nous préférons ne pas avoir de doublons - et c'est là que vous voulez un Set.

Answer 5

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

Si vous vous demandez à quoi peut servir un jeu de documents, c'est évidemment partout où vous voulez vous débarrasser des doublons. Pour prendre un exemple un peu tiré par les cheveux, 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 pourriez 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 fini d'itérer, la taille de l'ensemble est la réponse que vous cherchiez.