C# / .NET Kompendium PLEN
.NET / C# / Algorytmy, struktury danych

HashSet\<T> w C

Co to jest i jak działa "pod spodem"

HashSet<T> to kolekcja przechowująca unikalne elementy, oparta na tablicy haszującej (hash table) - dokładnie ten sam mechanizm co Dictionary<K,V>, tylko bez wartości, tylko klucze.

var uniqueIds = new HashSet<int>();
uniqueIds.Add(1); // true - dodano
uniqueIds.Add(2); // true - dodano
uniqueIds.Add(1); // false - JUŻ ISTNIEJE, nie dodano duplikatu

Console.WriteLine(uniqueIds.Count); // 2, nie 3

Jak działa hashowanie - dlaczego O(1)

public class Order
{
    public int Id { get; set; }
    public override int GetHashCode() => Id.GetHashCode(); // KLUCZOWE dla HashSet<Order>
    public override bool Equals(object obj) => obj is Order o && o.Id == Id;
}

Kiedy wywołujesz hashSet.Add(order), HashSet<T> wywołuje GetHashCode() na obiekcie, żeby obliczyć, do którego "kubełka" (bucket) wewnętrznej tablicy element powinien trafić. Sprawdzenie "czy element już istnieje" polega na: obliczeniu hasha (O(1)), znalezieniu odpowiedniego kubełka (O(1)), i porównaniu (Equals) z elementami w tym jednym kubełku (zwykle 0-1 elementów, nie cała kolekcja) - stąd średnio O(1), w przeciwieństwie do List<T>.Contains(), które musi przeszukać wszystkie elementy liniowo, O(n).

To nawiązuje wprost do wcześniejszej rozmowy o Equals/GetHashCode - jeśli nadpiszesz Equals bez GetHashCode, HashSet<T> będzie działać błędnie (dwa "logicznie równe" obiekty mogą trafić do różnych kubełków i HashSet uzna je za różne elementy), dokładnie tak, jak to opisywałem przy tamtym przykładzie.

Operacje na zbiorach - matematyczna teoria mnogości w praktyce

var setA = new HashSet<int> { 1, 2, 3, 4 };
var setB = new HashSet<int> { 3, 4, 5, 6 };

var union = new HashSet<int>(setA);
union.UnionWith(setB); // {1,2,3,4,5,6} - suma zbiorów

var intersection = new HashSet<int>(setA);
intersection.IntersectWith(setB); // {3,4} - przecięcie (elementy WSPÓLNE)

var difference = new HashSet<int>(setA);
difference.ExceptWith(setB); // {1,2} - różnica (elementy TYLKO w A)

var symmetricDiff = new HashSet<int>(setA);
symmetricDiff.SymmetricExceptWith(setB); // {1,2,5,6} - elementy w A LUB B, ale NIE w obu

Praktyczne zastosowanie #1 - eliminacja duplikatów

List<int> withDuplicates = new() { 1, 2, 2, 3, 3, 3, 4 };
var unique = new HashSet<int>(withDuplicates); // {1, 2, 3, 4}

// Alternatywnie przez LINQ (wewnętrznie też używa HashSet)
var uniqueLinq = withDuplicates.Distinct().ToList();

Praktyczne zastosowanie #2 - szybkie sprawdzanie przynależności (bezpośrednie nawiązanie do Big-O)

// ❌ O(n) dla KAŻDEGO sprawdzenia - przy dużej liście, bardzo kosztowne w pętli
List<int> blockedUserIds = GetBlockedUserIds(); // powiedzmy, 10 000 elementów
foreach (var user in allUsers) // 100 000 elementów
{
    if (blockedUserIds.Contains(user.Id)) // O(n) - PRZESZUKUJE listę liniowo!
    {
        // ...
    }
} // Całość: O(n * m) = 100 000 * 10 000 = 1 MILIARD operacji!

// ✅ O(1) per sprawdzenie
HashSet<int> blockedUserIds = GetBlockedUserIds().ToHashSet(); // JEDNORAZOWA konwersja O(m)
foreach (var user in allUsers) // 100 000 elementów
{
    if (blockedUserIds.Contains(user.Id)) // O(1) - natychmiastowe sprawdzenie!
    {
        // ...
    }
} // Całość: O(n + m) = 110 000 operacji

To jest dokładnie ten sam wzorzec optymalizacji, o którym mówiłem przy Big-O z Dictionary - HashSet<T> to naturalny wybór, gdy interesuje Cię tylko "czy element istnieje", bez potrzeby przechowywania dodatkowej wartości powiązanej z kluczem (do tego służy Dictionary<K,V>).

HashSet<T> vs Dictionary<K,V> - kiedy który

HashSet<T> Dictionary<K,V>
Przechowuje Tylko elementy (klucze) Pary klucz-wartość
Kiedy używać "Czy X istnieje w zbiorze?" "Jaka wartość odpowiada kluczowi X?"
Przykład Zbiór zablokowanych ID, unikalne tagi Mapowanie ID → obiekt, cache

Custom IEqualityComparer<T> - niestandardowa logika porównania

public class OrderByIdComparer : IEqualityComparer<Order>
{
    public bool Equals(Order x, Order y) => x?.Id == y?.Id;
    public int GetHashCode(Order obj) => obj.Id.GetHashCode();
}

var orders = new HashSet<Order>(new OrderByIdComparer()); // porównanie TYLKO po Id, niezależnie od Equals na Order

To dokładnie ten mechanizm IEqualityComparer<T>, o którym mówiliśmy przy porównywaniu record/class - działa identycznie z HashSet<T> jak z każdą inną kolekcją.

Podsumowanie

HashSet<T> to struktura oparta na tablicy haszującej, dająca średnio O(1) dla dodawania, usuwania i sprawdzania przynależności - w przeciwieństwie do List<T>.Contains(), które jest O(n). Kluczowy warunek poprawnego działania to spójna implementacja Equals/GetHashCode na przechowywanym typie (albo dostarczenie własnego IEqualityComparer<T>). Najczęstsze praktyczne zastosowanie to eliminacja duplikatów i szybkie sprawdzanie przynależności w pętli, co zamienia złożoność O(n*m) na O(n+m) - to jest jeden z najbardziej praktycznych, "darmowych" usprawnień wydajnościowych, jakie można wprowadzić do kodu.

Postaw mi kawę