Dokumentacja C# z przykładami: HashSet

Q: Czym jest HashSet w C#?

HashSet to kolekcja unikalnych elementów bez określonej kolejności. Dodanie elementu, który już jest w zbiorze, nic nie robi, a Contains odpowiada w mniej więcej stałym czasie niezależnie od rozmiaru zbioru, bo elementy są przechowywane według kodu skrótu, tak jak klucze w Dictionary.

Q: Co zwraca HashSet.Add?

Add zwraca true, gdy element został dodany, i false, gdy już był w zbiorze. Dzięki temu if (!seen.Add(x)) to jednolinijkowe sprawdzenie duplikatów: w jednym wywołaniu dodaje nowe elementy i informuje o powtórzonych.

Q: Jak usunąć duplikaty z List w C#?

list.Distinct().ToList() zwraca nową listę bez duplikatów i zachowuje pierwsze wystąpienie każdego elementu w pierwotnej kolejności. new HashSet (list) też usuwa duplikaty, ale zbiór nie ma gwarantowanej kolejności. Aby usunąć duplikaty w miejscu, użyj var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));.

Q: Kiedy użyć HashSet zamiast List?

Użyj HashSet , gdy najczęściej pytasz "czy ten element jest w kolekcji?" albo potrzebujesz, by elementy były unikalne. List .Contains przegląda każdy element, więc zwalnia wraz ze wzrostem listy, a HashSet .Contains nie. Użyj List , gdy liczy się kolejność, duplikaty lub dostęp przez indeks.

Q: Dlaczego mój HashSet zawiera zduplikowane obiekty?

Twoja klasa nie nadpisuje Equals i GetHashCode, więc zbiór porównuje referencje, a dwa obiekty o tych samych wartościach pól liczą się jako różne. Nadpisz obie metody (zawsze razem) albo przekaż IEqualityComparer do konstruktora zbioru.

HashSet<T> to kolekcja, w której każdy element występuje najwyżej raz. Nie ma indeksu ani gwarantowanej kolejności, a w zamian sprawdza przynależność w mniej więcej stałym czasie: znalezienie jednego tagu wśród miliona trwa mniej więcej tyle samo, co wśród dziesięciu.

Dodawanie elementów: Add zwraca 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);
    }
}

Wynik:

True
False
3
True
True
False
2

Dodanie duplikatu nie jest błędem; Add po prostu zwraca false, a zbiór się nie zmienia. Ta zwracana wartość to najbardziej przydatna cecha tej metody. Łączy "czy to już było?" i "zapamiętaj to" w jedno wywołanie:

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

Wynik:

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

Dlaczego Contains jest szybkie

List<T>.Contains porównuje wartość po kolei z każdym elementem, więc koszt rośnie wraz z listą. HashSet<T> oblicza kod skrótu elementu, przeskakuje do kubełka dla tego kodu i porównuje tylko kilka przechowywanych tam elementów. Przy sprawdzaniu przynależności w pętli zamienia to krok O(n) w krok O(1), a zagnieżdżoną pętlę po dwóch listach w jedno przejście:

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

Zbudowanie zbioru kosztuje jedno przejście po liście, więc opłaca się dopiero wtedy, gdy wyszukujesz więcej niż kilka razy.

Usuwanie duplikatów z listy

Są trzy typowe sposoby i różnią się tym, co dzieje się z kolejnością:

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

Wynik:

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

Distinct to właściwy wybór domyślny, gdy chcesz z powrotem listę. Wersja w miejscu działa, bo RemoveAll wywołuje predykat raz dla każdego elementu, po kolei: seen.Add zwraca false dla drugiej i kolejnych kopii, więc usuwane są dokładnie one.

Operacje na zbiorach: suma, część wspólna, różnica

HashSet<T> ma operacje znane z teorii zbiorów. Metody ...With zmieniają zbiór, na którym je wywołano, i nic nie zwracają.

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

Wynik:

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

Argumentem może być dowolny IEnumerable<T>: tablica, lista albo inny zbiór. SetEquals ignoruje kolejność i duplikaty w argumencie. Pomocnik Show sortuje przed wypisaniem, bo na kolejności wyliczania zbioru nie należy polegać.

LINQ ma odpowiadające metody, które zwracają nową sekwencję i nie ruszają danych wejściowych: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Używaj ich, gdy nie chcesz modyfikować zbioru albo gdy dane wejściowe to listy.

Własna równość dla twoich klas

Zbiór rozstrzyga, czy to "ten sam element", przez GetHashCode i Equals. W klasie, która ich nie nadpisuje, obie opierają się na tożsamości obiektu, więc dwa obiekty o równych polach to dwa różne elementy:

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

Wynik:

2
1
True

Zasada: obiekty, które są równe według Equals, muszą zwracać ten sam GetHashCode. Jeśli nadpiszesz tylko Equals, zbiór szuka w złym kubełku i nadal zgłasza duplikaty. W .NET Core 2.1 i nowszych HashCode.Combine(X, Y) buduje dobry kod skrótu bez ręcznej arytmetyki.

Gdy nie możesz zmienić klasy albo potrzebujesz innego pojęcia "tego samego" dla jednego zbioru, przekaż IEqualityComparer<T> do konstruktora. Stringi mają gotowe comparery:

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

Wynik:

True
False
2

W C# 9 i nowszych record generuje za ciebie Equals i GetHashCode oparte na wartościach, więc record Point(int X, int Y); działa w zbiorze bez dodatkowego kodu.

Nigdy nie zmieniaj pola, z którego korzysta GetHashCode, gdy obiekt jest w zbiorze. Obiekt zostaje w kubełku dla starego kodu skrótu, więc Contains i Remove przestają go znajdować.

Kolejność i SortedSet

HashSet<T> wylicza elementy w kolejności, którą należy traktować jako przypadkową. Jeśli potrzebujesz posortowanych elementów, sortuj przy wypisywaniu (set.OrderBy(x => x)) albo użyj SortedSet<T>, który cały czas trzyma elementy w porządku i dodaje Min, Max oraz zapytania o zakres, w czasie O(log n) na operację:

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

HashSet a List a Dictionary

Potrzeba	Użyj
Unikalne elementy, szybkie "czy jest?"	`HashSet<T>`
Unikalne elementy, zawsze posortowane	`SortedSet<T>`
Kolejność, duplikaty, dostęp przez indeks	`List<T>`
Wartość przechowywana pod każdym kluczem	`Dictionary<TKey, TValue>`

Zbiór to słownik z kluczami bez wartości. Jeśli piszesz Dictionary<string, bool> tylko po to, żeby śledzić przynależność, HashSet<string> wyraża to samo czytelniej.

Typowe błędy

Oczekiwanie kolejności. Zbiór nie ma kolejności, na której można polegać; sortuj albo użyj SortedSet<T>.
Własne klasy bez Equals i GetHashCode. Obiekty, które wyglądają tak samo, stają się osobnymi elementami.
Nadpisanie samego Equals. Zawsze nadpisuj razem z nim GetHashCode.
Zmiana elementu po dodaniu go. Zbiór nie może go już znaleźć.
Indeksowanie zbioru. set[0] się nie kompiluje; nie ma indeksu. Jeśli potrzebujesz pozycji, skonwertuj przez ToList().

Najczęściej zadawane pytania

Czym jest HashSet w C#?

HashSet<T> to kolekcja unikalnych elementów bez określonej kolejności. Dodanie elementu, który już jest w zbiorze, nic nie robi, a Contains odpowiada w mniej więcej stałym czasie niezależnie od rozmiaru zbioru, bo elementy są przechowywane według kodu skrótu, tak jak klucze w Dictionary.

Co zwraca HashSet.Add?

Add zwraca true, gdy element został dodany, i false, gdy już był w zbiorze. Dzięki temu if (!seen.Add(x)) to jednolinijkowe sprawdzenie duplikatów: w jednym wywołaniu dodaje nowe elementy i informuje o powtórzonych.

Jak usunąć duplikaty z List w C#?

list.Distinct().ToList() zwraca nową listę bez duplikatów i zachowuje pierwsze wystąpienie każdego elementu w pierwotnej kolejności. new HashSet<T>(list) też usuwa duplikaty, ale zbiór nie ma gwarantowanej kolejności. Aby usunąć duplikaty w miejscu, użyj var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));.

Kiedy użyć HashSet zamiast List?

Użyj HashSet<T>, gdy najczęściej pytasz "czy ten element jest w kolekcji?" albo potrzebujesz, by elementy były unikalne. List<T>.Contains przegląda każdy element, więc zwalnia wraz ze wzrostem listy, a HashSet<T>.Contains nie. Użyj List<T>, gdy liczy się kolejność, duplikaty lub dostęp przez indeks.

Dlaczego mój HashSet zawiera zduplikowane obiekty?

Twoja klasa nie nadpisuje Equals i GetHashCode, więc zbiór porównuje referencje, a dwa obiekty o tych samych wartościach pól liczą się jako różne. Nadpisz obie metody (zawsze razem) albo przekaż IEqualityComparer<T> do konstruktora zbioru.

Powiązane zagadnienia