Guida C# interattiva: HashSet

Q: Che cos'è un HashSet in C#?

HashSet è una collezione di elementi unici senza un ordine definito. Aggiungere un elemento già presente non fa nulla, e Contains risponde in un tempo più o meno costante, per quanto grande sia il set, perché gli elementi sono memorizzati per hash code come le chiavi di un Dictionary.

Q: Cosa restituisce HashSet.Add?

Add restituisce true quando l'elemento è stato aggiunto e false quando era già nel set. Questo rende if (!seen.Add(x)) un controllo dei duplicati in una riga: aggiunge gli elementi nuovi e ti segnala quelli ripetuti con la stessa chiamata.

Q: Come rimuovo i duplicati da una List in C#?

list.Distinct().ToList() restituisce una nuova lista senza duplicati e conserva la prima occorrenza di ogni elemento nel suo ordine originale. Anche new HashSet (list) rimuove i duplicati, ma un set non ha un ordine garantito. Per eliminare i duplicati sul posto, usa var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));.

Q: Quando conviene usare un HashSet invece di una List?

Usa un HashSet quando chiedi soprattutto "questo elemento è nella collezione?" o quando gli elementi devono essere unici. List .Contains scorre ogni elemento, quindi rallenta man mano che la lista cresce, mentre HashSet .Contains no. Usa una List quando contano l'ordine, i duplicati o l'accesso per indice.

Q: Perché il mio HashSet contiene oggetti duplicati?

La tua classe non sovrascrive Equals e GetHashCode, quindi il set confronta i riferimenti e due oggetti con gli stessi valori nei campi risultano diversi. Sovrascrivi entrambi i metodi (sempre insieme), oppure passa un IEqualityComparer al costruttore del set.

Un HashSet<T> è una collezione in cui ogni elemento compare al massimo una volta. Non ha un indice né un ordine garantito, e in cambio verifica l'appartenenza in un tempo più o meno costante: trovare un tag tra un milione richiede all'incirca lo stesso tempo che trovarlo tra dieci.

Aggiungere elementi: Add restituisce 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);
    }
}

Output:

True
False
3
True
True
False
2

Aggiungere un duplicato non è un errore; Add restituisce semplicemente false e il set resta invariato. Quel valore di ritorno è la cosa più utile del metodo. Unisce "l'ho già visto?" e "ricordatelo" in una sola chiamata:

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

Output:

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

Perché Contains è veloce

List<T>.Contains confronta il valore con ogni elemento a turno, quindi il suo costo cresce con la lista. Un HashSet<T> calcola l'hash code dell'elemento, salta al bucket di quel codice e confronta solo i pochi elementi che vi sono memorizzati. Per un test di appartenenza dentro un ciclo, questo trasforma un passo O(n) in un passo O(1), e un ciclo annidato su due liste in un unico passaggio:

// 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));

Costruire il set costa un passaggio sulla lista, quindi conviene solo quando fai più di qualche ricerca.

Rimuovere i duplicati da una lista

Ci sono tre modi comuni, e differiscono per cosa succede all'ordine:

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

Output:

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

Distinct è la scelta predefinita giusta quando vuoi ottenere una lista. La versione sul posto funziona perché RemoveAll chiama il predicato una volta per elemento, in ordine: seen.Add restituisce false per la seconda copia e le successive, quindi vengono rimosse esattamente quelle.

Operazioni sugli insiemi: unione, intersezione, differenza

HashSet<T> ha le operazioni della teoria degli insiemi. I metodi ...With modificano il set su cui vengono chiamati e non restituiscono nulla.

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

Output:

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

L'argomento può essere qualsiasi IEnumerable<T>: un array, una lista o un altro set. SetEquals ignora l'ordine e i duplicati nell'argomento. L'helper Show ordina prima di stampare perché l'ordine di enumerazione di un set non è qualcosa su cui fare affidamento.

LINQ ha metodi corrispondenti che restituiscono una nuova sequenza e lasciano invariati gli input: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Usali quando non vuoi modificare un set, o quando gli input sono liste.

Uguaglianza personalizzata per le tue classi

Un set decide se due elementi sono "lo stesso" con GetHashCode ed Equals. Per una classe che non li sovrascrive, entrambi si basano sull'identità dell'oggetto, quindi due oggetti con campi uguali sono due elementi diversi:

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

Output:

2
1
True

La regola: oggetti che sono Equals devono restituire lo stesso GetHashCode. Se sovrascrivi solo Equals, il set cerca nel bucket sbagliato e segnala ancora duplicati. Su .NET Core 2.1 e successivi, HashCode.Combine(X, Y) costruisce un buon hash code senza l'aritmetica scritta a mano.

Quando non puoi modificare la classe, o ti serve una nozione diversa di "stesso" per un solo set, passa un IEqualityComparer<T> al costruttore. Le stringhe hanno comparer già pronti:

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

Output:

True
False
2

In C# 9 e successivi, un record genera per te Equals e GetHashCode basati sul valore, quindi record Point(int X, int Y); funziona in un set senza codice aggiuntivo.

Non cambiare mai un campo che contribuisce a GetHashCode mentre l'oggetto è in un set. L'oggetto resta nel bucket del suo vecchio hash, quindi Contains e Remove non lo trovano più.

Ordine e SortedSet

Un HashSet<T> enumera in un ordine che devi considerare arbitrario. Se ti servono gli elementi ordinati, ordinali quando stampi (set.OrderBy(x => x)) oppure usa SortedSet<T>, che mantiene sempre gli elementi in ordine e aggiunge Min, Max e query per intervallo a O(log n) per operazione:

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

HashSet, List o Dictionary

Esigenza	Usa
Elementi unici, "c'è?" veloce	`HashSet<T>`
Elementi unici, sempre ordinati	`SortedSet<T>`
Ordine, duplicati, accesso per indice	`List<T>`
Un valore memorizzato sotto ogni chiave	`Dictionary<TKey, TValue>`

Un set è un dizionario con le chiavi e senza valori. Se ti ritrovi a scrivere Dictionary<string, bool> solo per tenere traccia dell'appartenenza, un HashSet<string> dice la stessa cosa in modo più chiaro.

Errori comuni

Aspettarsi un ordine. Un set non ne ha uno su cui contare; ordina, oppure usa SortedSet<T>.
Classi personalizzate senza Equals e GetHashCode. Oggetti che sembrano uguali diventano elementi separati.
Sovrascrivere solo Equals. Sovrascrivi sempre anche GetHashCode.
Modificare un elemento dopo averlo aggiunto. Il set non riesce più a trovarlo.
Accedere a un set per indice. set[0] non compila; non c'è un indice. Converti con ToList() se ti servono le posizioni.

Domande frequenti

Che cos'è un HashSet in C#?

HashSet<T> è una collezione di elementi unici senza un ordine definito. Aggiungere un elemento già presente non fa nulla, e Contains risponde in un tempo più o meno costante, per quanto grande sia il set, perché gli elementi sono memorizzati per hash code come le chiavi di un Dictionary.

Cosa restituisce HashSet.Add?

Add restituisce true quando l'elemento è stato aggiunto e false quando era già nel set. Questo rende if (!seen.Add(x)) un controllo dei duplicati in una riga: aggiunge gli elementi nuovi e ti segnala quelli ripetuti con la stessa chiamata.

Come rimuovo i duplicati da una List in C#?

list.Distinct().ToList() restituisce una nuova lista senza duplicati e conserva la prima occorrenza di ogni elemento nel suo ordine originale. Anche new HashSet<T>(list) rimuove i duplicati, ma un set non ha un ordine garantito. Per eliminare i duplicati sul posto, usa var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));.

Quando conviene usare un HashSet invece di una List?

Usa un HashSet<T> quando chiedi soprattutto "questo elemento è nella collezione?" o quando gli elementi devono essere unici. List<T>.Contains scorre ogni elemento, quindi rallenta man mano che la lista cresce, mentre HashSet<T>.Contains no. Usa una List<T> quando contano l'ordine, i duplicati o l'accesso per indice.

Perché il mio HashSet contiene oggetti duplicati?

La tua classe non sovrascrive Equals e GetHashCode, quindi il set confronta i riferimenti e due oggetti con gli stessi valori nei campi risultano diversi. Sovrascrivi entrambi i metodi (sempre insieme), oppure passa un IEqualityComparer<T> al costruttore del set.

Concetti correlati