Définir: qu'est-ce qu'un HashSet?

420

HashSet La structure de données C # HashSet a été introduite dans le .NET Framework 3.5. Une liste complète des membres implémentés se trouve sur la page HashSet MSDN .

  1. Où est-il utilisé?
  2. Pourquoi voudriez-vous l'utiliser?
c# hashset 001
la source
4
en.wikipedia.org/wiki/Set_(computer_science)
Claus Jørgensen
3
doublon possible de Quand dois-je utiliser le type HashSet <T>?
nawfal
Il utilise une table de hachage en interne. si vous avez une bonne implémentation de table de hachage (par exemple Dictionary <T>), vous pouvez implémenter HashSet vous-même facilement.
Raz Megrelidze

Réponses:

614

    1. A HashSetcontient un ensemble d'objets, mais d'une manière qui vous permet de déterminer facilement et rapidement si un objet est déjà dans l'ensemble ou non. Pour ce faire, il gère en interne un tableau et stocke l'objet à l'aide d'un index calculé à partir du code de hachage de l'objet. Jetez un oeil ici

    2. HashSetest une collection non ordonnée contenant des éléments uniques. Il a les opérations de collecte standard Ajouter, Supprimer, Contient, mais comme il utilise une implémentation basée sur le hachage, ces opérations sont O (1). (Par opposition à List par exemple, qui est O (n) pour Contient et Remove.) HashSetFournit également des opérations d'ensemble standard telles que l' union , l' intersection et la différence symétrique . Jetez un oeil ici

  2. Il existe différentes implémentations de Sets. Certains rendent les opérations d'insertion et de recherche super rapides en hachant les éléments. Cependant, cela signifie que l'ordre dans lequel les éléments ont été ajoutés est perdu. D'autres implémentations préservent l'ordre ajouté au prix de temps d'exécution plus lents.

La HashSetclasse en C # opte pour la première approche, ne préservant ainsi pas l'ordre des éléments. C'est beaucoup plus rapide qu'un habitué List. Certains benchmarks de base ont montré que HashSet est décemment plus rapide lorsqu'il s'agit de types primaires (int, double, bool, etc.). C'est beaucoup plus rapide lorsque vous travaillez avec des objets de classe. Donc, ce point est que HashSet est rapide.

Le seul hic, HashSetc'est qu'il n'y a pas d'accès par les indices. Pour accéder aux éléments, vous pouvez soit utiliser un énumérateur, soit utiliser la fonction intégrée pour convertir le HashSeten a Listet le parcourir. Jetez un oeil ici

kamaci
la source
13
Deux choses, hashset et similaires sont des .NET, pas des C #. HashSet ne préserve pas non plus l'ordre. Essayez d'ajouter et de supprimer des éléments d'un ensemble de hachage, vous saurez si vous itérez plus tard ..
nawfal
13

A HashSetpossède une structure interne (hachage), où les éléments peuvent être recherchés et identifiés rapidement. L'inconvénient est que l'itération à travers un HashSet(ou l'obtention d'un élément par index) est plutôt lente.

Alors, pourquoi voudrait-on savoir si une entrée existe déjà dans un ensemble?

Une situation où a HashSetest utile consiste à obtenir des valeurs distinctes à partir d'une liste où des doublons peuvent exister. Une fois qu'un élément est ajouté à, HashSetil est rapide de déterminer s'il existe ( Containsopérateur).

D' autres avantages du HashSetsont les opérations Set: IntersectWith, IsSubsetOf, IsSupersetOf, Overlaps, SymmetricExceptWith, UnionWith.

Si vous connaissez le langage de contrainte d'objet, vous identifierez ces opérations d'ensemble. Vous verrez également qu'il s'agit d'un pas de plus vers une implémentation d'UML exécutable.

k rey
la source
20
Re: inconvénient. Non, l'itération via un HashSet est parfaitement rapide. Deuxièmement, il n'est pas possible d'obtenir un élément par index. En fait, les éléments sont stockés sans ordre.
Nigel Touch
@Nigel Touch. L'itération est rapide si vous ne vous souciez pas de l'index (ordre dans lequel ils ont été ajoutés). Cependant, si vous êtes préoccupé par l'index, alors l'index doit être stocké avec chaque clé de hachage et il peut donc être assez lent car la liste doit être recherchée de manière exhaustive pour récupérer l'élément correct. Ce comportement est très différent d'une liste dans laquelle les éléments sont indexés par l'ordre dans lequel ils sont ajoutés.
k rey
Il est logique de savoir pourquoi ce serait rapide, car il n'y a pas deux hachages identiques. Permettre à la requête de bénéficier d'une approche «court-circuit», excluant rapidement certains critères.
Chef_Code
8

En termes simples et sans révéler les secrets de la cuisine: un ensemble en général, est une collection qui ne contient aucun élément en double et dont les éléments ne sont pas dans un ordre particulier. Ainsi, A HashSet<T>est similaire à un générique List<T>, mais est optimisé pour des recherches rapides (via des tables de hachage, comme son nom l'indique) au prix de la perte de commande.

Empilés
la source
1
Mais un HashSet <T> peut-il stocker deux objets qui ont les mêmes données, comme deux classes Product qui ont chacune les mêmes propriétés avec le même contenu?
Johan Herstad
Je suppose que nous ne saurons jamais
Denny
@JohanHerstad En supposant que EqualityComparer pour votre classe se soucie de ces propriétés ou que vous construisez le HashSet avec un IEqualityComparer qui se soucie de ces propriétés, je ne vois pas pourquoi il ne le ferait pas. La documentation de HashSet indique clairement qu'il s'appuie sur l'un ou l'autre pour déterminer l'unicité.
Bacon Bits
2

Du point de vue de l'application, si l'on a seulement besoin d'éviter les doublons, HashSetc'est ce que vous recherchez car sa complexité de recherche, d'insertion et de suppression est O (1) - constante . Cela signifie que peu importe le nombre d'éléments, HashSetil faudra autant de temps pour vérifier s'il y a un tel élément ou non, et comme vous insérez également des éléments à O (1), cela le rend parfait pour ce genre de chose.

Matas Vaitkevicius
la source