HashSet w C# — unikalne elementy i szybkość

HashSet<T> reprezentuje zbiór unikalnych elementów, podobnie jak zbiór matematyczny — { 1, 2, 3, 4, 5 } i { 5, 4, 3, 2, 1 } to dokładnie ten sam zbiór, bo kolejność elementów nie ma znaczenia, a duplikaty są niemożliwe. To odróżnia go od List<T>, która pozwala na duplikaty i pamięta kolejność wstawiania.

Jeśli zależy Ci nie tylko na unikalności, ale też na automatycznym sortowaniu elementów, zobacz osobny artykuł o SortedSet<T> — kolekcji opartej na drzewie czerwono-czarnym, która utrzymuje elementy w porządku posortowanym kosztem wolniejszych operacji.

Kiedy używać HashSet

Sięgaj po HashSet<T>, gdy potrzebujesz bardzo szybkiego sprawdzania przynależności elementu do zbioru — np. przetwarzasz listę zamówień i dla każdego musisz błyskawicznie zweryfikować, czy kod dostawcy znajduje się na liście dozwolonych kodów. Przy dużych zbiorach różnica względem List.Contains() jest ogromna.

Jak działa pod maską

HashSet<T> jest, podobnie jak Dictionary<TKey, TValue>, kolekcją opartą na haszowaniu (tablica haszująca) — dlatego wyszukiwanie, dodawanie i usuwanie są średnio O(1), niezależnie od liczby elementów. W przeciwieństwie do słownika nie przechowuje par klucz/wartość — przechowuje tylko wartości, a “kluczem” wewnętrznym każdej wartości jest jej własny hash.

To oznacza, że unikalność elementu zależy bezpośrednio od tego, co zwraca jego metoda GetHashCode() (do znalezienia właściwego “kubełka” w tablicy) oraz Equals() (do rozstrzygnięcia kolizji hashów). Jeśli chcesz przechowywać w zbiorze własny typ (klasę lub strukturę), musisz nadpisać obie te metody — inaczej HashSet porówna obiekty domyślnie po referencji, i dwa obiekty o identycznych danych zostaną potraktowane jako różne.

public class Punkt
{
    public int X { get; set; }
    public int Y { get; set; }

    public override bool Equals(object? obj)
        => obj is Punkt other && X == other.X && Y == other.Y;

    public override int GetHashCode()
        => HashCode.Combine(X, Y);
}

Podstawowe operacje

// Zainicjuj zbiór przy użyciu składni inicjalizacji obiektu
var hashSet = new HashSet<int>() { 1, 2, 3, 4, 5 };

// Dodaj element — zwraca false, jeśli element już istnieje w zbiorze
bool dodano = hashSet.Add(6);

// Usuń element
hashSet.Remove(4);

// Usuń wszystkie elementy
hashSet.Clear();

// Sprawdź, czy zbiór zawiera element — O(1) średnio
var contains = hashSet.Contains(3);

// Zwróć liczbę elementów w zbiorze
var count = hashSet.Count;

Zwróć uwagę na różnicę względem List<T>.Add(): metoda HashSet<T>.Add() zwraca bool — true, jeśli element został faktycznie dodany, false, jeśli już tam był. To wygodny sposób na wykrycie duplikatu bez dodatkowego wywołania Contains() przed dodaniem.

Operacje na zbiorach matematycznych

To, co naprawdę wyróżnia HashSet<T> na tle innych kolekcji, to gotowe metody realizujące klasyczne operacje teorii zbiorów:

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

// Przecięcie: zmodyfikuj a, tak aby zawierał tylko elementy obecne w a i w b
a.IntersectWith(b);        // a = { 3, 4 }

var c = new HashSet<int> { 1, 2, 3, 4 };
// Różnica: usuń z c wszystkie elementy obecne w b
c.ExceptWith(b);           // c = { 1, 2 }

var d = new HashSet<int> { 1, 2, 3, 4 };
// Suma: dołącz do d wszystkie elementy z b
d.UnionWith(b);             // d = { 1, 2, 3, 4, 5, 6 }

var isSupersetOf = d.IsSupersetOf(b);
var isSubsetOf = a.IsSubsetOf(d);
var equals = a.SetEquals(new HashSet<int> { 4, 3 }); // true — kolejność nie ma znaczenia

Odtworzenie tej logiki ręcznie na List<T> (pętle zagnieżdżone, Contains w każdej iteracji) byłoby zarówno dłuższe w kodzie, jak i znacznie wolniejsze — O(n×m) zamiast O(n).

HashSet vs List vs Dictionary vs SortedSet

• HashSet<T> — unikalne elementy, brak kolejności, O(1) dla Contains/Add/Remove. Wybierz, gdy liczy się szybkie sprawdzanie przynależności.
• List<T> — dopuszcza duplikaty, zachowuje kolejność wstawiania, dostęp po indeksie. Contains() to O(n).
• Dictionary<TKey, TValue> — jak HashSet, ale przechowuje pary klucz/wartość zamiast samych wartości. Wybierz, gdy każdemu unikalnemu elementowi musisz przypisać dodatkowe dane.
• SortedSet<T> — jak HashSet, ale elementy są zawsze posortowane, kosztem O(log n) zamiast O(1) dla operacji podstawowych.

Częste pułapki

• Własny typ bez nadpisanego GetHashCode/Equals — dwa obiekty o identycznych danych trafią do zbioru jako dwa osobne elementy, bo domyślne porównanie odbywa się po referencji.
• Mutowanie obiektu już dodanego do HashSet — jeśli zmienisz pola, od których zależy GetHashCode(), po dodaniu obiektu do zbioru, kolekcja “zgubi” go — hash obliczony przy dodaniu wskazuje już na zły kubełek, więc kolejne Contains() może zwrócić false mimo że obiekt fizycznie tam jest.
• HashSet<T> nie jest bezpieczny wątkowo — do scenariuszy wielowątkowych rozważ zewnętrzną synchronizację (nie ma gotowego ConcurrentHashSet w standardowej bibliotece — najbliższym odpowiednikiem jest ConcurrentDictionary<T, byte> z ignorowaną wartością).
• Brak gwarancji kolejności iteracji — mimo że w praktyce kolejność bywa stabilna dla danego zestawu operacji, nie jest to kontrakt API. Nie polegaj na niej.

Potrzebujesz szybkiego dostępu po kluczu, nie tylko sprawdzania unikalności? Zobacz Dictionary w C#. A gdy elementy mają dodatkowo być posortowane, sprawdź SortedSet w C#.

FAQ

Czym różni się HashSet od Dictionary?
HashSet przechowuje same wartości, Dictionary przechowuje pary klucz/wartość. Oba są zbudowane na tej samej strukturze haszującej i mają podobną złożoność O(1).

Dlaczego Add() zwraca bool zamiast void?
Żeby jednym wywołaniem sprawdzić i dodać element — false oznacza, że element już był w zbiorze i nic się nie zmieniło.

Czy HashSet zachowuje kolejność dodawania?
Nie ma na to gwarancji w kontrakcie API, mimo że w praktyce implementacja bywa przewidywalna dla prostych scenariuszy. Jeśli potrzebujesz deterministycznej kolejności, użyj List<T> (kolejność wstawiania) albo SortedSet<T> (kolejność sortowania).