HashSet и SortedSet в C#: множества, операции и сложность

HashSet — это структура данных из System.Collections.Generic, которая хранит уникальные элементы без определенного порядка. SortedSet тоже хранит уникальные элементы, но всегда в отсортированном порядке. Обе реализуют интерфейс ISet<T> и дают одинаковый набор операций над множествами — объединение, пересечение, разность. Дальше разберем, чем они отличаются от List<T>, какие методы использовать и какая у них сложность.

HashSet, SortedSet и List: в чем разница

Все три — обобщенные коллекции для хранения набора элементов одного типа, но с разными гарантиями.

List<T> хранит элементы в порядке добавления и допускает дубликаты. Поиск и проверка на существование элемента — линейный перебор.

HashSet<T> хранит элементы во внутренней хеш-таблице. Порядок не гарантирован (не совпадает ни с порядком добавления, ни с сортировкой) и может измениться после удаления элементов. Дубликаты запрещены: повторное добавление существующего значения просто ничего не меняет.

SortedSet<T> хранит элементы в сбалансированном дереве (в реализации BCL — красно-черное дерево). Дубликаты тоже запрещены, но при переборе элементы всегда идут в отсортированном порядке.

Создание множества и базовые операции

Конструктор принимает IEnumerable<T> — дубликаты из исходной коллекции схлопнутся сами.

using System;
using System.Collections.Generic;

var numbers = new HashSet<int> { 3, 1, 4, 1, 5 };
Console.WriteLine(numbers.Count);       // 4 - дубликат 1 не добавился повторно
Console.WriteLine(numbers.Contains(4)); // True
numbers.Remove(4);
Console.WriteLine(numbers.Contains(4)); // False

Вывод:

4
True
False

Add, Remove и Contains у HashSet<T> в среднем работают за O(1) — хеш-таблица сразу вычисляет ячейку по значению. В худшем случае, при большом числе хеш-коллизий, сложность деградирует до O(n), но на практике для разумно реализованного GetHashCode это редкий случай.

Add не бросает исключение на дубликате

Частая ошибка — решить, что повторное добавление существующего элемента приведет к исключению, и обернуть Add в try/catch.

var seen = new HashSet<int> { 1, 2, 3 };
try
{
    seen.Add(2);
    Console.WriteLine("добавлено");
}
catch (InvalidOperationException)
{
    Console.WriteLine("дубликат, элемент уже есть");
}

Фактический результат: в консоль всегда попадает «добавлено» — исключение не бросается ни разу, метод Add на дубликате просто молча возвращает false и ничего не меняет в множестве.

Исправление — проверять возвращаемое значение Add, оно типа bool:

bool added = seen.Add(2);
Console.WriteLine(added ? "добавлено" : "дубликат, элемент уже есть");

То же самое верно для SortedSet<T>.Add — сигнатура и поведение при дубликате одинаковые.

Операции над множествами: UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith

Эти методы меняют множество, на котором вызваны, «на месте» — если исходные наборы нужно сохранить, сначала копируют их через конструктор.

using System;
using System.Collections.Generic;
using System.Linq;

var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5, 6 };

var union = new HashSet<int>(a);
union.UnionWith(b);
Console.WriteLine(string.Join(", ", union.OrderBy(x => x)));

var intersection = new HashSet<int>(a);
intersection.IntersectWith(b);
Console.WriteLine(string.Join(", ", intersection.OrderBy(x => x)));

var difference = new HashSet<int>(a);
difference.ExceptWith(b);
Console.WriteLine(string.Join(", ", difference.OrderBy(x => x)));

var symmetric = new HashSet<int>(a);
symmetric.SymmetricExceptWith(b);
Console.WriteLine(string.Join(", ", symmetric.OrderBy(x => x)));

Вывод (элементы отсортированы через OrderBy специально для примера — сам HashSet<T> порядок не гарантирует):

1, 2, 3, 4, 5, 6
3, 4
1, 2
1, 2, 5, 6

UnionWith — объединение (все элементы хотя бы одного набора). IntersectWith — пересечение (элементы, общие для обоих). ExceptWith — разность (элементы a, которых нет в b; операция несимметричная, порядок вызова важен). SymmetricExceptWith — симметрическая разность: элементы, которые есть только в одном из двух наборов.

Проверка отношений между множествами

IsSubsetOf, IsSupersetOf, Overlaps и SetEquals ничего не меняют в множестве — только возвращают bool.

var small = new HashSet<int> { 1, 2 };
var big = new HashSet<int> { 1, 2, 3, 4 };

Console.WriteLine(small.IsSubsetOf(big));           // True
Console.WriteLine(big.IsSupersetOf(small));         // True
Console.WriteLine(small.Overlaps(new[] { 2, 99 })); // True, общий элемент - 2
Console.WriteLine(small.SetEquals(new[] { 2, 1 })); // True, порядок аргумента не важен

SetEquals сравнивает содержимое, а не порядок и не тип коллекции — HashSet<int> может быть равен обычному массиву по составу элементов.

Сложность операций

Граница у HashSet: O(1) — это средний случай при равномерном распределении хешей. Если у типа плохо реализован GetHashCode (например, он всегда возвращает одно и то же значение), операции деградируют до O(n) — все элементы попадают в одну ячейку.

SortedSet: требование к элементам

SortedSet<T> нужно знать, как сравнивать два элемента, чтобы держать порядок. Если тип элементов реализует IComparable<T> (как встроенные int, string, DateTime), можно создавать множество без дополнительных настроек. Если нет — нужно передать IComparer<T> в конструктор явно.

public class Point
{
    public int X, Y;
    public Point(int x, int y) { X = x; Y = y; }
}

var points = new SortedSet<Point>();
points.Add(new Point(1, 1));
points.Add(new Point(2, 2));

Фактический результат: второй Add завершится исключением ArgumentException (сообщение о том, что сравниваемые объекты должны реализовывать IComparable) — Point не реализует IComparable<Point>, и компаратор по умолчанию Comparer<T>.Default не может определить порядок двух объектов.

Исправление — передать компаратор в конструктор:

var points = new SortedSet<Point>(Comparer<Point>.Create((p1, p2) =>
{
    int byX = p1.X.CompareTo(p2.X);
    return byX != 0 ? byX : p1.Y.CompareTo(p2.Y);
}));

points.Add(new Point(1, 1));
points.Add(new Point(2, 2));
Console.WriteLine(points.Count); // 2

Выводы

• HashSet<T> и SortedSet<T> хранят только уникальные элементы; повторное добавление не бросает исключение, а возвращает false из Add.
• Разница между ними — в порядке перебора и внутреннем устройстве: хеш-таблица у HashSet<T> (O(1) в среднем) против дерева у SortedSet<T> (O(log n), но всегда отсортировано).
• Операции над множествами — UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith — меняют коллекцию на месте; чтобы сохранить исходные наборы, сначала копируют их в новый HashSet<T>.
• SortedSet<T> требует, чтобы элементы реализовывали IComparable<T>, либо явно переданного IComparer<T> — иначе Add бросит исключение при первом сравнении двух элементов.
• Если нужен порядок вставки и уникальность одновременно, ни HashSet<T>, ни SortedSet<T> не подходят напрямую — нужна комбинация List<T> и HashSet<T> (см. FAQ).

Где применяется / связь с практикой

Множества применяются везде, где важна уникальность, а не порядок: дедупликация email или id, быстрая проверка «встречался ли элемент» в потоке данных, пересечение сегментов пользователей, фильтр посещенных узлов в обходе графа. SortedSet<T> дополнительно удобен, когда нужен упорядоченный уникальный набор — например, список уникальных дат без ручной сортировки после каждого добавления.

FAQ

Можно ли хранить null в HashSet и SortedSet?
Для типов значений (int, struct) null невозможен по определению языка. Для ссылочных типов HashSet<T> допускает ровно один null-элемент. Поведение SortedSet<T> с null зависит от компаратора — со своим IComparer<T> нужно явно предусмотреть обработку null, иначе возможно исключение при сравнении.

Что будет, если добавить в SortedSet объект, у которого тип не реализует IComparable?
Множество создается без ошибок, но при первом же Add второго элемента вызывается сравнение — и если сравнивать нечем, вылетает ArgumentException. Решение — передать IComparer<T> в конструктор SortedSet<T>.

Как получить уникальные элементы, но в порядке добавления?
Ни HashSet<T>, ни SortedSet<T> порядок вставки не хранят. Практическое решение — вести List<T> для порядка и параллельно HashSet<T> для быстрой O(1) проверки «уже добавлен ли элемент» перед вставкой в список.