Множина: HashSet<T>

1. Вступ

Уявіть собі ситуацію: ви створюєте систему для інтернет-магазину й маєте зберігати список усіх унікальних кодів товарів, які будь-коли продавалися. Або ще краще — пишете застосунок для соцмережі й хочете швидко перевірити, чи вже є таке імʼя користувача. А якщо потрібно порахувати, скільки унікальних слів у великому тексті?

У всіх цих сценаріях потрібен набір елементів, де кожен трапляється лише раз. І тут на сцену виходить HashSet<T>.

HashSet<T> — це колекція, яка зберігає неупорядкований набір унікальних елементів. Головне слово тут — унікальних. Якщо ви спробуєте додати елемент, який уже є в HashSet, колекція просто проігнорує вашу спробу й не додасть дублікат. Це як клуб «лише для унікальних»: якщо ви вже всередині, вдруге вас не пустять.

Ключові особливості HashSet<T>:

• Унікальність: Гарантує, що кожен елемент у колекції є лише один раз.
• Продуктивність: Дуже швидко перевіряє наявність елемента, додає й видаляє його. У середньому ці операції виконуються за константний час (O(1)), незалежно від кількості елементів. Це забезпечується завдяки механізму, що зветься хешуванням.
• Відсутність порядку: На відміну від List<T>, елементи в HashSet<T> не зберігаються в жодному певному порядку. Ви не можете отримати елемент за індексом (на кшталт «пʼятий елемент»).
• На основі хеш-таблиці: Усередині HashSet<T> використовує хеш-таблицю для зберігання елементів, що й дає йому таку швидкість. Ми зараз не занурюватимемося глибоко в роботу хеш-таблиць (це тема окремої, більш просунутої лекції), але уявіть, що кожен елемент «перетворюється» на спеціальний числовий код (хеш), за яким його потім дуже швидко знаходять.

Порівняймо це з тим, якби ви використовували List<T> для зберігання унікальних елементів: щоразу довелося б перебирати весь список, аби переконатися, що елемента там немає, перш ніж додати його. Це було б дуже повільно для великих списків. HashSet<T> робить це миттєво!

2. Навіщо потрібен HashSet<T> програмісту?

Таємниця унікальних колекцій

У програмуванні часто постає завдання: треба зберігати елементи без повторів. Наприклад, ви аналізуєте список адрес електронної пошти користувачів застосунку й хочете переконатися, що немає дублікатів. Або збираєте унікальні імена файлів, зчитані з каталогу. Найпростіше рішення — колекція, до якої неможливо вдруге додати те, що вже є.

Звісно, можна спробувати розв’язати завдання через List<T>, вручну перевіряючи, чи є елемент у списку перед додаванням:

var users = new List<string>();
if (!users.Contains("vasya@example.com"))
    users.Add("vasya@example.com");

Але це рішення погано масштабується — перевірка Contains у List вимагає перегляду всіх елементів; якщо користувачів тисячі, програма суттєво сповільнюється.

Що робить 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("Така адреса вже є!");

Видалення елементів

Видалення — теж швидке:

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> пропонує низку методів, що роблять роботу з ним схожою на маніпуляції з математичними множинами: об’єднання, перетин, різниця і симетрична різниця.

Ось основні з них:

UnionWith(other)

IntersectWith(other)

ExceptWith(other)

SymmetricExceptWith(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 — вилучити всі елементи:

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" }); // Не додасться!

Без перевизначення методів Equals і GetHashCode HashSet вважатиме всі екземпляри різними (навіть якщо логін збігається), адже за замовчуванням порівнює адреси в памʼяті.

1

Опитування

Огляд основних колекцій, рівень 27, лекція 4

Недоступний

Огляд основних колекцій

Типи колекцій та generics

Відкрити