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 doList<T>.Contains(), które jest O(n). Kluczowy warunek poprawnego działania to spójna implementacjaEquals/GetHashCodena przechowywanym typie (albo dostarczenie własnegoIEqualityComparer<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)naO(n+m)- to jest jeden z najbardziej praktycznych, "darmowych" usprawnień wydajnościowych, jakie można wprowadzić do kodu.