1. Wprowadzenie
Wyobraź sobie sytuację: tworzysz system dla sklepu internetowego i musisz przechowywać listę wszystkich unikalnych kodów produktów, które kiedykolwiek zostały sprzedane. Albo jeszcze lepiej — piszesz aplikację społecznościową i musisz szybko sprawdzić, czy taka nazwa użytkownika już istnieje. A co, jeśli chcesz policzyć, ile unikalnych słów jest w dużym tekście?
We wszystkich tych scenariuszach potrzebujemy zbioru elementów, gdzie każdy występuje tylko raz. I tu na scenę wchodzi HashSet<T>.
HashSet<T> — to kolekcja, która przechowuje nieuporządkowany zbiór unikalnych elementów. Najważniejsze słowo tutaj to unikalnych. Jeśli spróbujesz dodać element, który już jest w HashSet, po prostu zignoruje twoją próbę i nie doda duplikatu. To jak klub "tylko dla wyjątkowych ludzi": jeśli już jesteś w środku, drugi raz cię nie wpuszczą.
Kluczowe cechy HashSet<T>:
- Unikalność: Gwarantuje, że każdy element w kolekcji występuje tylko raz.
- Wydajność: Bardzo szybko sprawdza obecność elementu, dodaje i usuwa go. Średnio te operacje są wykonywane w czasie stałym (O(1)), niezależnie od liczby elementów! To dzięki mechanizmowi, który nazywa się hashowaniem.
- Brak kolejności: W przeciwieństwie do List<T>, elementy w HashSet<T> nie są przechowywane w żadnej określonej kolejności. Nie możesz pobrać elementu po indeksie (np. "piąty element").
- Na bazie hash-table: W środku HashSet<T> używa hash-table do przechowywania elementów, co zapewnia mu wysoką wydajność. Nie będziemy teraz głęboko wchodzić w to, jak działają hash-table (to temat na osobny, bardziej zaawansowany wykład), ale wyobraź sobie, że każdy element "zamienia się" w specjalny kod liczbowy (hash), po którym potem bardzo szybko go znajdują.
Porównajmy to z sytuacją, gdybyś użył List<T> do przechowywania unikalnych elementów: za każdym razem musiałbyś przeszukać całą listę, żeby upewnić się, że elementu tam nie ma, zanim go dodasz. To byłoby bardzo wolne przy dużych listach. HashSet<T> robi to natychmiast!
2. Po co programiście HashSet<T>?
Tajemnica unikalnych kolekcji
W programowaniu często pojawia się zadanie: trzeba przechowywać elementy bez powtórzeń. Na przykład parsujesz listę adresów email użytkowników aplikacji i chcesz mieć pewność, że nie ma duplikatów. Albo zbierasz unikalne nazwy plików odczytane z folderu. Najprostsze rozwiązanie — kolekcja, do której nie można dodać drugi raz tego, co już jest.
Oczywiście można próbować rozwiązać to za pomocą List<T>, ręcznie sprawdzając, czy element jest na liście przed dodaniem:
var users = new List<string>();
if (!users.Contains("alice@example.com"))
users.Add("alice@example.com");
Ale to rozwiązanie działa słabo przy dużych ilościach — sprawdzenie Contains w List wymaga przejrzenia wszystkich elementów, a jeśli użytkowników są tysiące, program staje się wolny jak stary komputer na Windows XP.
Co robi HashSet<T>
HashSet<T> natomiast gwarantuje, że każdy element będzie przechowywany tylko raz. Jest zaimplementowany na bazie hash-table (tak jak słownik), więc operacje dodawania, wyszukiwania i usuwania są bardzo szybkie — zwykle w czasie stałym, bez przeglądania wszystkich elementów.
3. Podstawy pracy z HashSet<T>
Deklaracja i tworzenie
Żeby zacząć, nie musisz dołączać żadnych dodatkowych bibliotek — klasa już jest w przestrzeni nazw System.Collections.Generic.
using System.Collections.Generic;
var emails = new HashSet<string>();
Możesz od razu wypełnić kolekcję wartościami początkowymi, przekazując je do konstruktora:
var fruits = new HashSet<string> { "jabłko", "banan", "gruszka", "banan" };
// "banan" pojawia się dwa razy, ale będzie przechowywany tylko raz!
Dodawanie elementów
Dodawanie elementów odbywa się metodą Add. Jeśli takiego elementu jeszcze nie było, metoda zwraca true. Jeśli element już jest — po prostu nic się nie dzieje i metoda zwraca false.
bool added = emails.Add("alice@example.com"); // true, element dodany
added = emails.Add("alice@example.com"); // false, już jest, nie dodany
Śmieszne: Możesz spokojnie wołać Add nawet sto razy z tą samą wartością — HashSet się nie obrazi, po prostu grzecznie zignoruje powtórzenia.
Sprawdzanie obecności: Contains
Aby sprawdzić, czy element jest przechowywany, użyj metody Contains:
if (emails.Contains("alice@example.com"))
Console.WriteLine("Taki email już istnieje!");
Usuwanie elementów
Usuwanie — też szybkie:
emails.Remove("alice@example.com");
Jeśli elementu nie było — nic się nie dzieje, metoda po prostu zwróci false.
4. Praktyczny przykład
Trochę utrudnijmy nasz studencki CRM, który rozwijamy w trakcie kursu.
Wymaganie
Załóżmy, że według zasad naszego systemu każdy użytkownik musi mieć unikalną nazwę użytkownika (login). Przed dodaniem nowego użytkownika trzeba sprawdzić unikalność, a jeśli coś — poinformować o tym.
Przykład kodu
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Kolekcja do przechowywania unikalnych loginów
var userNames = new HashSet<string>();
while (true)
{
Console.Write("Podaj nazwę użytkownika (albo leave żeby wyjść): ");
string name = Console.ReadLine();
if (name == "leave")
break;
if (userNames.Add(name))
{
Console.WriteLine("Nazwa została dodana!");
}
else
{
Console.WriteLine("Błąd: ta nazwa jest już zajęta, spróbuj inną.");
}
}
Console.WriteLine("Lista użytkowników:");
foreach (var user in userNames)
Console.WriteLine($"- {user}");
// Uwaga! Kolejność wyświetlania może być dowolna.
}
}
Tak po prostu zapewniliśmy unikalność. Nie trzeba ręcznie sprawdzać obecności — HashSet zrobi to za ciebie.
5. Jak działa HashSet<T> w środku? Po co hash-code
Analogia: przegródki do przechowywania
Wyobraź sobie, że masz ogromny stos karteczek z loginami i stół z przegródkami od 0 do 1000. Każdy login wkładasz do przegródki, której numer wylicza funkcja (GetHashCode). Jeśli karteczki się powtarzają — trafią do tej samej przegródki i szybko dowiesz się, że login już istnieje.
Funkcja GetHashCode
HashSet<T> porównuje elementy nie tylko po wartości, ale najpierw wylicza ich hash-code za pomocą metody GetHashCode(). Dla większości wbudowanych typów (int, string, double itd.) jest to już zrobione optymalnie.
Ciekawostka: Jeśli będziesz tworzyć własne klasy i chcesz je przechowywać w HashSet<T>, koniecznie zaimplementuj w tych klasach poprawne metody porównywania równości i uzyskiwania unikalnego kodu (metody Equals i GetHashCode), żeby unikalność działała poprawnie. Ale o tym — w kolejnych wykładach.
Typowe błędy przy pracy z HashSet<T>
Gdy ludzie dopiero uczą się używać kolekcji unikalnych wartości, często wpadają w taką pułapkę: myślą, że HashSet<T> przechowuje elementy w kolejności, w jakiej zostały dodane. To nieprawda! Hash-sety nie gwarantują żadnej kolejności, wszystko może być w przypadkowej kolejności. Jeśli zależy ci na kolejności — potrzebujesz innego typu kolekcji, np. SortedSet<T>, ale to już inna historia.
Drugi popularny błąd — próba użycia indeksu:
string name = userNames[0]; // Błąd! HashSet<T> nie ma indeksów.
W przeciwieństwie do tablicy czy listy, tutaj nie możesz odwołać się do elementu po numerze. Przeglądanie elementów możliwe jest tylko przez foreach.
Trzecie częste zamieszanie pojawia się przy serializacji lub zapisywaniu hash-setu do pliku — przez nieokreśloną kolejność elementy między uruchomieniami programu mogą być w innej kolejności.
6. Operacje na zbiorach: union, intersection, difference
HashSet<T> oferuje całą kolekcję metod, które sprawiają, że praca z nim przypomina manipulacje na matematycznych zbiorach. Takie jak: union, intersection, difference i symmetric difference.
Oto najważniejsze z nich:
| Metoda | Co robi |
|---|---|
|
Dodaje do hash-setu wszystkie elementy z other. |
|
Zostawia tylko elementy, które są tu i w other. |
|
Usuwa z bieżącego zbioru elementy z other. |
|
Zostawia tylko te elementy, które są albo tu, albo w other, ale nie w obu. |
Przykład: intersection i union
Na przykładzie. Załóżmy, że są dwa zbiory imion:
var groupA = new HashSet<string> { "Ania", "Borys", "Wera" };
var groupB = new HashSet<string> { "Wera", "Gleb", "Daria" };
// Znajdźmy, kto jest w obu grupach
var common = new HashSet<string>(groupA); // kopiujemy zawartość, inaczej groupA się zmieni!
common.IntersectWith(groupB);
Console.WriteLine("W obu grupach:");
foreach (var name in common)
Console.WriteLine(name); // Wypisze "Wera"
// Połącz wszystkich studentów obu grup, żeby nikt się nie zgubił:
var all = new HashSet<string>(groupA);
all.UnionWith(groupB);
Console.WriteLine("Wszyscy studenci:");
foreach (var name in all)
Console.WriteLine(name); // "Ania", "Borys", "Wera", "Gleb", "Daria"
7. Dodatkowe metody i właściwości
Count — sprawdzisz, ile jest elementów w zbiorze:
Console.WriteLine(userNames.Count);
Clear — usuń wszystko (jak CTRL+A, DELETE w życiu):
userNames.Clear();
SetEquals, IsSubsetOf, IsSupersetOf — sprawdzają, czy zbiory są takie same, czy jeden jest podzbiorem drugiego itd. Przydaje się, jeśli grasz (albo programujesz) coś w stylu "matematyk — kto lepszy".
if (groupA.IsSubsetOf(groupB))
Console.WriteLine("Wszyscy z grupy A są w grupie B");
8. Przechowywanie własnych obiektów w HashSet<T>
Jak już wspomniano wyżej, standardowe typy już potrafią poprawnie liczyć hashe i porównywać się na równość.
Ale jeśli zdecydujemy się przechowywać np. użytkowników jako obiekty, trzeba zapewnić porównywanie po jakiejś właściwości (np. loginie):
class User
{
public string Login { get; set; }
public override bool Equals(object obj)
{
if (obj is User other)
return Login == other.Login;
return false;
}
public override int GetHashCode()
{
return Login.GetHashCode();
}
}
// Teraz można:
var users = new HashSet<User>();
users.Add(new User { Login = "alice" });
users.Add(new User { Login = "peter" });
users.Add(new User { Login = "alice" }); // Nie zostanie dodany!
Bez override'ów metod Equals i GetHashCode HashSet uzna wszystkie instancje za różne (nawet jeśli login się zgadza), bo domyślnie porównuje adresy w pamięci.
GO TO FULL VERSION