1. Введение
Представьте себе ситуацию: вы разрабатываете систему для интернет-магазина, и вам нужно хранить список всех уникальных кодов товаров, которые когда-либо были проданы. Или, еще лучше, вы пишете приложение для социальной сети, и нужно быстро проверить, есть ли уже такое имя пользователя. А что, если вы хотите посчитать, сколько уникальных слов в большом тексте?
Во всех этих сценариях нам нужен набор элементов, где каждый элемент встречается только один раз. И вот тут на сцену выходит HashSet<T>.
HashSet<T> — это коллекция, которая хранит неупорядоченный набор уникальных элементов. Главное слово здесь – уникальных. Если вы попытаетесь добавить элемент, который уже есть в HashSet, он просто проигнорирует вашу попытку и не добавит дубликат. Это как клуб "только для уникальных людей": если ты уже внутри, тебя второй раз не пустят.
Ключевые особенности HashSet<T>:
- Уникальность: Гарантирует, что каждый элемент в коллекции присутствует только один раз.
- Производительность: Очень быстро проверяет наличие элемента, добавляет и удаляет его. В среднем эти операции выполняются за константное время (O(1)), независимо от количества элементов! Это достигается благодаря механизму, который называется хешированием.
- Отсутствие порядка: В отличие от List<T>, элементы в HashSet<T> не хранятся в каком-либо определенном порядке. Вы не можете получить элемент по индексу (например, "пятый элемент").
- На основе хеш-таблицы: Внутри HashSet<T> использует хеш-таблицу для хранения элементов, что и обеспечивает его высокую производительность. Мы не будем сейчас глубоко погружаться в то, как работают хеш-таблицы (это тема для отдельной, более продвинутой лекции), но представьте, что каждый элемент "превращается" в специальный числовой код (хеш), по которому его потом очень быстро находят.
Давайте сравним это с тем, как если бы вы использовали List<T> для хранения уникальных элементов: вам бы каждый раз пришлось перебирать весь список, чтобы убедиться, что элемента там нет, прежде чем добавить его. Это было бы очень медленно для больших списков. HashSet<T> делает это мгновенно!
2. Зачем нужен HashSet<T> программисту?
Тайна уникальных коллекций
В программировании часто бывает задача: нужно хранить элементы без повторений. Например, вы парсите список email-адресов пользователей приложения и хотите убедиться, что нет дубликатов. Или собираете уникальные имена файлов, считанные из папки. Самое простое решение — коллекция, в которую нельзя добавить второй раз то, что уже есть.
Конечно, можно попытаться решить задачу с помощью List<T>, вручную проверяя, есть ли элемент в списке перед добавлением:
var users = new List<string>();
if (!users.Contains("vasya@example.com"))
users.Add("vasya@example.com");
Но это решение работает плохо на больших объёмах — проверка Contains у List требует просмотра всех элементов, а если пользователей тысячи, программа становится медленной, как старый компьютер на Windows XP.
Что делает HashSet<T>
HashSet<T>, напротив, гарантирует, что каждый элемент будет храниться только один раз. Он реализован на базе хеш-таблицы (как и словарь), а значит операции добавления, поиска и удаления выполняются очень быстро — обычно за постоянное время, без просмотра всех элементов.
3. Основы работы с HashSet<T>
Объявление и создание
Чтобы начать, нам не нужно подключать никаких дополнительных библиотек — класс уже есть в пространстве имён System.Collections.Generic.
using System.Collections.Generic;
var emails = new HashSet<string>();
Можно сразу заполнить коллекцию начальными значениями, передав их в конструктор:
var fruits = new HashSet<string> { "яблоко", "банан", "груша", "банан" };
// "банан" встречается дважды, но будет храниться только один раз!
Добавление элементов
Добавление элементов производится методом Add. Если такого элемента ещё не было, метод возвращает true. Если элемент уже есть — просто ничего не происходит, и метод возвращает false.
bool added = emails.Add("vasya@example.com"); // true, элемент добавлен
added = emails.Add("vasya@example.com"); // false, уже есть, не добавлен
Забавно: Можно смело звать Add хоть сто раз с одним и тем же значением — HashSet не обидится, просто вежливо проигнорирует повторы.
Проверка наличия: Contains
Для проверки, хранится ли элемент, используйте метод Contains:
if (emails.Contains("vasya@example.com"))
Console.WriteLine("Такой email уже есть!");
Удаление элементов
Удаление — тоже быстрое:
emails.Remove("vasya@example.com");
Если элемента не было — ничего страшного, метод просто вернёт false.
4. Практический пример
Давайте чуть усложним нашу студенческую CRM, которую мы развиваем на протяжении курса.
Требование
Допустим, по условиям нашей системы, каждый пользователь должен иметь уникальное имя пользователя (логин). Перед добавлением нового пользователя нужно проверить уникальность, а если что — сообщить об этом.
Пример кода
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Коллекция для хранения уникальных логинов
var userNames = new HashSet<string>();
while (true)
{
Console.Write("Введите имя пользователя (или leave для выхода): ");
string name = Console.ReadLine();
if (name == "leave")
break;
if (userNames.Add(name))
{
Console.WriteLine("Имя успешно добавлено!");
}
else
{
Console.WriteLine("Ошибка: это имя уже занято, попробуйте другое.");
}
}
Console.WriteLine("Список пользователей:");
foreach (var user in userNames)
Console.WriteLine($"- {user}");
// Внимание! Порядок вывода может быть произвольным.
}
}
Вот так просто мы обеспечили уникальность. Не нужно вручную проверять наличие — HashSet всё сделает сам.
5. Как устроен HashSet<T> внутри? Зачем нужен хеш-код
Аналогия: ячейки для хранения
Представьте, что у вас огромная стопка карточек с логинами, и стол с ячейками от 0 до 1000. Каждый логин вы кладёте в ячейку, номер которой вычисляет функция (GetHashCode). Если карточки совпадают — они окажутся в одной ячейке, и вы быстро узнаёте, что логин уже есть.
Функция GetHashCode
HashSet<T> сравнивает элементы не просто по значению, а сначала вычисляет их хеш-код с помощью метода GetHashCode(). Для большинства встроенных типов (int, string, double и др.) это уже реализовано оптимально.
Интересный факт: Если вы будете создавать свои типы классов и захотите хранить их в HashSet<T>, обязательно реализуйте у этих классов корректные методы для сравнения на равенство и получения уникального кода (методы Equals и GetHashCode), чтобы уникальность работала правильно. Но об этом — в следующих лекциях.
Некоторые типичные ошибки при работе с HashSet<T>
Когда люди только учатся использовать коллекцию уникальных значений, часто встречается такая ловушка: считают, что HashSet<T> хранит элементы в том порядке, в каком их добавили. Это не так! Хеш-наборы не гарантируют никакой очередности, всё может оказаться в случайном порядке. Если важен порядок — нужен другой тип коллекции, например, SortedSet<T>, но это уже другая история.
Вторая популярная ошибка — попытка воспользоваться индексом:
string name = userNames[0]; // Ошибка! У HashSet<T> нет индексов.
В отличие от массива или списка, здесь нельзя обратиться к элементу по номеру. Перебор элементов возможен только с помощью foreach.
Третья распространённая путаница возникает при сериализации или сохранении хеш-набора в файл — из-за неопределённого порядка элементы между запусками программы могут оказываться в разной последовательности.
6. Операции над множествами: объединение, пересечение, разность
HashSet<T> предлагает целую коллекцию методов, которые делают работу с ним похожей на манипуляции с математическими множествами. Такие как: объединение, пересечение, разность и симметрическая разность.
Вот основные из них:
| Метод | Что делает |
|---|---|
|
Добавляет в хеш-набор все элементы из other. |
|
Оставляет только элементы, есть и здесь, и в other. |
|
Удаляет из текущего набора элементы из other. |
|
Оставляет только те элементы, которые есть либо здесь, либо в other, но не в обоих. |
Пример: пересечение и объединение
Давайте на примере. Пусть есть два набора имен:
var groupA = new HashSet<string> { "Аня", "Борис", "Вера" };
var groupB = new HashSet<string> { "Вера", "Глеб", "Даша" };
// Найдём, кто есть в обеих группах
var common = new HashSet<string>(groupA); // копируем содержимое, иначе groupA изменится!
common.IntersectWith(groupB);
Console.WriteLine("В обеих группах:");
foreach (var name in common)
Console.WriteLine(name); // Выведет "Вера"
// Объединить всех студентов обеих групп, чтоб никто не потерялся:
var all = new HashSet<string>(groupA);
all.UnionWith(groupB);
Console.WriteLine("Все студенты:");
foreach (var name in all)
Console.WriteLine(name); // "Аня", "Борис", "Вера", "Глеб", "Даша"
7. Дополнительные методы и свойства
Count — узнаем, сколько всего элементов в наборе:
Console.WriteLine(userNames.Count);
Clear — удалить всё (как CTRL+A, DELETE в жизни):
userNames.Clear();
SetEquals, IsSubsetOf, IsSupersetOf — проверки, совпадают ли множества, одно ли внутри другого и так далее. Это помогает, если вы играете (или программируете) что-то типа "математик — кто круче".
if (groupA.IsSubsetOf(groupB))
Console.WriteLine("Все из группы A есть в группе B");
8. Хранение собственных объектов в HashSet<T>
Как уже вскользь упоминалось выше, стандартные типы уже умеют правильно считать хеши и сравниваться на равенство.
Но если мы решим хранить, например, пользователей как объекты, то потребуется обеспечить сравнение по какому-то признаку (например, логину):
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();
}
}
// Теперь можно:
var users = new HashSet<User>();
users.Add(new User { Login = "vasya" });
users.Add(new User { Login = "petya" });
users.Add(new User { Login = "vasya" }); // Не добавится!
Без override-ов методов Equals и GetHashCode HashSet будет считать все экземпляры разными (даже если логин совпадает), потому что по умолчанию сравнивает адреса в памяти.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ