Docs C# exécutables : HashSet

Q: Qu'est-ce qu'un HashSet en C# ?

HashSet est une collection d'éléments uniques sans ordre défini. Ajouter un élément déjà présent ne fait rien, et Contains répond en un temps à peu près constant quelle que soit la taille de l'ensemble, car les éléments sont stockés par code de hachage comme les clés d'un Dictionary.

Q: Que renvoie HashSet.Add ?

Add renvoie true quand l'élément a été ajouté et false quand il était déjà dans l'ensemble. Cela fait de if (!seen.Add(x)) un test de doublon en une ligne : il ajoute les nouveaux éléments et vous signale les répétitions dans le même appel.

Q: Comment supprimer les doublons d'une List en C# ?

list.Distinct().ToList() renvoie une nouvelle liste sans doublons et garde la première occurrence de chaque élément dans son ordre d'origine. new HashSet (list) supprime aussi les doublons, mais un ensemble n'a pas d'ordre garanti. Pour dédoublonner sur place, utilisez var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));.

Q: Quand utiliser un HashSet plutôt qu'une List ?

Utilisez un HashSet quand vous demandez surtout « cet élément est-il dans la collection ? » ou que les éléments doivent être uniques. List .Contains parcourt chaque élément, donc ralentit à mesure que la liste grandit, alors que HashSet .Contains non. Utilisez une List quand l'ordre, les doublons ou l'accès par index comptent.

Q: Pourquoi mon HashSet contient-il des objets en double ?

Votre classe ne redéfinit pas Equals et GetHashCode, donc l'ensemble compare des références et deux objets aux mêmes valeurs de champs comptent comme différents. Redéfinissez les deux méthodes (toujours ensemble), ou passez un IEqualityComparer au constructeur de l'ensemble.

Un HashSet<T> est une collection dans laquelle chaque élément apparaît au plus une fois. Il n'a ni index ni ordre garanti, et en échange il teste l'appartenance en un temps à peu près constant : trouver une étiquette parmi un million prend à peu près autant de temps que parmi dix.

Ajouter des éléments : Add renvoie un bool

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tags = new HashSet<string> { "sale", "new" };

        Console.WriteLine(tags.Add("gift"));  // added
        Console.WriteLine(tags.Add("sale"));  // already present
        Console.WriteLine(tags.Count);

        Console.WriteLine(tags.Contains("new"));
        Console.WriteLine(tags.Remove("new"));
        Console.WriteLine(tags.Remove("used")); // not there: false, no exception
        Console.WriteLine(tags.Count);
    }
}

Sortie :

True
False
3
True
True
False
2

Ajouter un doublon n'est pas une erreur ; Add renvoie simplement false et l'ensemble reste inchangé. Cette valeur de retour est ce que la méthode a de plus utile. Elle combine « l'ai-je déjà vu ? » et « retiens-le » en un seul appel :

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] signups = { "ana@x.com", "ben@x.com", "ana@x.com", "cy@x.com", "ben@x.com" };
        var seen = new HashSet<string>();

        foreach (string email in signups)
        {
            if (!seen.Add(email))
            {
                Console.WriteLine("Duplicate: " + email);
            }
        }
        Console.WriteLine(seen.Count + " unique");
    }
}

Sortie :

Duplicate: ana@x.com
Duplicate: ben@x.com
3 unique

Pourquoi Contains est rapide

List<T>.Contains compare la valeur à chaque élément tour à tour, donc son coût augmente avec la liste. Un HashSet<T> calcule le code de hachage de l'élément, saute au compartiment correspondant et ne compare que les quelques éléments qui y sont stockés. Pour un test d'appartenance dans une boucle, cela transforme une étape en O(n) en une étape en O(1), et une boucle imbriquée sur deux listes en un seul passage :

// Slow on large inputs: Contains scans bannedList for every order.
var flagged = orders.Where(o => bannedList.Contains(o.CustomerId));

// Fast: build the set once, then each lookup is constant time.
var banned = new HashSet<int>(bannedList);
var flagged2 = orders.Where(o => banned.Contains(o.CustomerId));

Construire l'ensemble coûte un passage sur la liste, ce n'est donc rentable que si vous faites plus que quelques recherches.

Supprimer les doublons d'une liste

Il existe trois façons courantes, qui diffèrent par ce qu'elles font de l'ordre :

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var cities = new List<string> { "Lima", "Oslo", "Lima", "Pune", "Oslo", "Kyiv" };

        // 1. LINQ Distinct: new list, first occurrences in original order
        List<string> unique = cities.Distinct().ToList();
        Console.WriteLine(string.Join(", ", unique));

        // 2. A set: unique, but a set has no guaranteed order
        var set = new HashSet<string>(cities);
        Console.WriteLine(set.Count);

        // 3. In place, keeping order: RemoveAll with a seen-set
        var seen = new HashSet<string>();
        cities.RemoveAll(c => !seen.Add(c));
        Console.WriteLine(string.Join(", ", cities));
    }
}

Sortie :

Lima, Oslo, Pune, Kyiv
4
Lima, Oslo, Pune, Kyiv

Distinct est le bon choix par défaut quand vous voulez récupérer une liste. La version sur place fonctionne parce que RemoveAll appelle le prédicat une fois par élément, dans l'ordre : seen.Add renvoie false pour la deuxième copie et les suivantes, et ce sont exactement celles-là qui sont supprimées.

Opérations ensemblistes : union, intersection, différence

HashSet<T> dispose des opérations de la théorie des ensembles. Les méthodes ...With modifient l'ensemble sur lequel elles sont appelées et ne renvoient rien.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string Show(HashSet<string> s)
    {
        return string.Join(", ", s.OrderBy(x => x));
    }

    static void Main()
    {
        string[] monday = { "Ana", "Ben", "Chloe" };
        string[] tuesday = { "Ben", "Chloe", "Dev" };

        var either = new HashSet<string>(monday);
        either.UnionWith(tuesday);             // in either list
        Console.WriteLine("Union:     " + Show(either));

        var both = new HashSet<string>(monday);
        both.IntersectWith(tuesday);           // in both
        Console.WriteLine("Intersect: " + Show(both));

        var onlyMonday = new HashSet<string>(monday);
        onlyMonday.ExceptWith(tuesday);        // in monday, not tuesday
        Console.WriteLine("Except:    " + Show(onlyMonday));

        var oneDay = new HashSet<string>(monday);
        oneDay.SymmetricExceptWith(tuesday);   // in exactly one
        Console.WriteLine("Symmetric: " + Show(oneDay));

        Console.WriteLine(both.IsSubsetOf(monday));
        Console.WriteLine(either.IsSupersetOf(tuesday));
        Console.WriteLine(onlyMonday.Overlaps(tuesday));
        Console.WriteLine(new HashSet<int> { 1, 2 }.SetEquals(new[] { 2, 1, 1 }));
    }
}

Sortie :

Union:     Ana, Ben, Chloe, Dev
Intersect: Ben, Chloe
Except:    Ana
Symmetric: Ana, Dev
True
True
False
True

L'argument peut être n'importe quel IEnumerable<T> : un tableau, une liste ou un autre ensemble. SetEquals ignore l'ordre et les doublons de l'argument. La fonction Show trie avant d'afficher, car l'ordre d'énumération d'un ensemble n'est pas fiable.

LINQ a des méthodes correspondantes qui renvoient une nouvelle séquence et laissent les entrées intactes : monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Utilisez-les quand vous ne voulez pas modifier un ensemble, ou quand les entrées sont des listes.

Égalité personnalisée pour vos propres classes

Un ensemble décide qu'il s'agit du « même élément » avec GetHashCode et Equals. Pour une classe qui ne les redéfinit pas, les deux reposent sur l'identité de l'objet, donc deux objets aux champs égaux sont deux éléments différents :

using System;
using System.Collections.Generic;

class Point
{
    public int X, Y;
    public Point(int x, int y) { X = x; Y = y; }
}

class Coord
{
    public int X, Y;
    public Coord(int x, int y) { X = x; Y = y; }

    public override bool Equals(object obj)
    {
        var other = obj as Coord;
        return other != null && other.X == X && other.Y == Y;
    }

    public override int GetHashCode()
    {
        unchecked { return X * 397 ^ Y; }
    }
}

class Program
{
    static void Main()
    {
        var points = new HashSet<Point> { new Point(1, 2), new Point(1, 2) };
        Console.WriteLine(points.Count); // 2: compared by reference

        var coords = new HashSet<Coord> { new Coord(1, 2), new Coord(1, 2) };
        Console.WriteLine(coords.Count); // 1: compared by value
        Console.WriteLine(coords.Contains(new Coord(1, 2)));
    }
}

Sortie :

2
1
True

La règle : des objets égaux selon Equals doivent renvoyer le même GetHashCode. Redéfinissez seulement Equals et l'ensemble cherche dans le mauvais compartiment et signale toujours des doublons. Sur .NET Core 2.1 et plus, HashCode.Combine(X, Y) construit un bon code de hachage sans arithmétique écrite à la main.

Quand vous ne pouvez pas modifier la classe, ou qu'il vous faut une autre notion de « même » pour un ensemble donné, passez un IEqualityComparer<T> au constructeur. Les chaînes ont des comparateurs tout prêts :

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var extensions = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { ".jpg", ".png" };
        Console.WriteLine(extensions.Contains(".JPG"));
        Console.WriteLine(extensions.Add(".PNG"));
        Console.WriteLine(extensions.Count);
    }
}

Sortie :

True
False
2

Depuis C# 9, un record génère pour vous Equals et GetHashCode basés sur les valeurs, donc record Point(int X, int Y); fonctionne dans un ensemble sans code supplémentaire.

Ne modifiez jamais un champ qui entre dans GetHashCode pendant que l'objet est dans un ensemble. L'objet reste dans le compartiment de son ancien hachage, donc Contains et Remove ne le trouvent plus.

Ordre et SortedSet

Un HashSet<T> s'énumère dans un ordre que vous devez considérer comme arbitraire. Si vous avez besoin d'éléments triés, triez à l'affichage (set.OrderBy(x => x)) ou utilisez SortedSet<T>, qui garde les éléments ordonnés en permanence et ajoute Min, Max et des requêtes par plage, en O(log n) par opération :

var ranks = new SortedSet<int> { 30, 10, 20 };
Console.WriteLine(string.Join(", ", ranks)); // 10, 20, 30
Console.WriteLine(ranks.Min);                // 10

HashSet, List ou Dictionary

Besoin	Utiliser
Éléments uniques, « est-il présent ? » rapide	`HashSet<T>`
Éléments uniques, toujours triés	`SortedSet<T>`
Ordre, doublons, accès par index	`List<T>`
Une valeur stockée sous chaque clé	`Dictionary<TKey, TValue>`

Un ensemble est un dictionnaire avec des clés et sans valeurs. Si vous vous surprenez à écrire Dictionary<string, bool> juste pour suivre l'appartenance, un HashSet<string> dit la même chose plus clairement.

Erreurs courantes

S'attendre à un ordre. Un ensemble n'en a aucun sur lequel compter ; triez, ou utilisez SortedSet<T>.
Des classes personnalisées sans Equals ni GetHashCode. Des objets qui semblent égaux deviennent des éléments distincts.
Redéfinir Equals seul. Redéfinissez toujours GetHashCode avec.
Modifier un élément après l'avoir ajouté. L'ensemble ne peut plus le trouver.
Indexer un ensemble. set[0] ne compile pas ; il n'y a pas d'index. Convertissez avec ToList() si vous avez besoin de positions.

Questions fréquentes

Qu'est-ce qu'un HashSet en C# ?

HashSet<T> est une collection d'éléments uniques sans ordre défini. Ajouter un élément déjà présent ne fait rien, et Contains répond en un temps à peu près constant quelle que soit la taille de l'ensemble, car les éléments sont stockés par code de hachage comme les clés d'un Dictionary.

Que renvoie HashSet.Add ?

Add renvoie true quand l'élément a été ajouté et false quand il était déjà dans l'ensemble. Cela fait de if (!seen.Add(x)) un test de doublon en une ligne : il ajoute les nouveaux éléments et vous signale les répétitions dans le même appel.

Comment supprimer les doublons d'une List en C# ?

list.Distinct().ToList() renvoie une nouvelle liste sans doublons et garde la première occurrence de chaque élément dans son ordre d'origine. new HashSet<T>(list) supprime aussi les doublons, mais un ensemble n'a pas d'ordre garanti. Pour dédoublonner sur place, utilisez var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));.

Quand utiliser un HashSet plutôt qu'une List ?

Utilisez un HashSet<T> quand vous demandez surtout « cet élément est-il dans la collection ? » ou que les éléments doivent être uniques. List<T>.Contains parcourt chaque élément, donc ralentit à mesure que la liste grandit, alors que HashSet<T>.Contains non. Utilisez une List<T> quand l'ordre, les doublons ou l'accès par index comptent.

Pourquoi mon HashSet contient-il des objets en double ?

Votre classe ne redéfinit pas Equals et GetHashCode, donc l'ensemble compare des références et deux objets aux mêmes valeurs de champs comptent comme différents. Redéfinissez les deux méthodes (toujours ensemble), ou passez un IEqualityComparer<T> au constructeur de l'ensemble.

Concepts liés