Множество HashSet

Представьте список гостей у входа на праздник. Охранник проверяет имя: если его в списке нет, вписывает, а если есть — второй раз не пишет. Сколько бы раз человек ни подходил к двери, его имя в списке одно.

Такой набор в .NET называется множеством: это набор значений, где каждое значение встречается не больше одного раза. Его тип — HashSet<T>. Любое значение либо есть в множестве, либо его там нет:

var guests = new HashSet<string>();
Console.WriteLine(guests.Add("Ann")); // True
Console.WriteLine(guests.Add("Bob")); // True
Console.WriteLine(guests.Add("Ann")); // False
Console.WriteLine(guests.Count);      // 2
Console.WriteLine(guests.Contains("Bob")); // True
Console.WriteLine(guests.Remove("Bob"));   // True
Console.WriteLine(guests.Contains("Bob")); // False

Давайте разберём программу по строкам:

1. Add("Ann") добавляет имя и возвращает true.
2. Add("Bob") тоже добавляет и тоже возвращает true.
3. Повторный Add("Ann") ничего не добавляет и возвращает false: имя уже есть.
4. Count равен 2: Ann записана один раз.
5. Contains("Bob") отвечает, есть ли значение: true.
6. Remove("Bob") удаляет значение и возвращает true, потому что оно было. После этого Contains даёт false.

Сравните со словарём. Add словаря с уже существующим ключом останавливает программу исключением. А Add множества при повторе возвращает false и ничего не меняет.

Убрать повторы

Множество можно создать из списка или массива: new HashSet<int>(nums) берёт все элементы и оставляет каждое значение один раз. Подойдут и значения в квадратных скобках:

List<int> nums = [3, 1, 3, 2, 1];
var unique = new HashSet<int>(nums);
Console.WriteLine(nums.Count);   // 5
Console.WriteLine(unique.Count); // 3
HashSet<string> tags = ["go", "cs", "go"];
Console.WriteLine(tags.Count);   // 2

Из пяти чисел остались три разных: 1, 2 и 3. Сам список nums не изменился: множество хранит свою копию значений. И в tags значение go попало только один раз.

Быстрая проверка «уже было?»

Contains у множества работает как поиск ключа в словаре: по хешу, без перебора. А Contains у списка проверяет элементы по одному. Поэтому на собеседовании задачу «найти первый повтор в массиве» решают множеством:

int[] ids = [4, 8, 15, 8, 16];
var seen = new HashSet<int>();
foreach (int id in ids)
{
    if (!seen.Add(id))
    {
        Console.WriteLine(id); // 8
        break;
    }
}

Разберём цикл:

1. seen хранит числа, которые уже встречались.
2. seen.Add(id) добавляет новое число и возвращает true.
3. Если число уже было, Add возвращает false, и ! превращает этот false в true.
4. Тогда цикл печатает первый повтор, 8, и выходит через break.

Это один проход по массиву. Решение с двумя вложенными циклами сравнивало бы каждый элемент с каждым.

Порядка нет

У множества нет индексов, и порядок значений в нём не гарантирован: оно отвечает только на вопрос «есть или нет». Если важен порядок или нужны повторы, берите список.

Здесь листок охранника и множество расходятся. На листке имена записаны в том порядке, в каком приходили гости. Множество этот порядок не хранит: foreach по нему выдаёт значения в последовательности, на которую нельзя полагаться.

Частая ошибка

Значение множества попробовали прочитать по индексу:

var guests = new HashSet<string>();
guests.Add("Ann");
Console.WriteLine(guests[0]); // ✗

error CS0021: Cannot apply indexing with [] to an expression of type 'HashSet<string>'

Программа не компилируется: у HashSet нет индексатора, ведь у его значений нет индексов. Чтобы узнать, есть ли значение, вызывайте Contains. Если нужен элемент по индексу, храните значения в списке.

Главное

• HashSet<T> хранит каждое значение один раз: повторный Add возвращает false и ничего не добавляет.
• Contains у множества ищет по хешу, без перебора, поэтому множество подходит для проверки «уже встречалось?».
• new HashSet<int>(nums) оставляет из списка или массива только разные значения.
• У множества нет индексов и гарантированного порядка: guests[0] не компилируется.