Исполняемые доки C#: HashSet

Q: Что такое HashSet в C#?

HashSet это коллекция уникальных элементов без определённого порядка. Добавление элемента, который уже есть, ничего не делает, а Contains отвечает примерно за постоянное время, каким бы большим ни было множество, потому что элементы хранятся по хеш-коду, как ключи Dictionary.

Q: Что возвращает HashSet.Add?

Add возвращает true, когда элемент добавлен, и false, когда он уже был в множестве. Поэтому if (!seen.Add(x)) это проверка на дубликат в одну строку: один и тот же вызов добавляет новые элементы и сообщает о повторных.

Q: Как удалить дубликаты из List в C#?

list.Distinct().ToList() возвращает новый список без дубликатов и сохраняет первое вхождение каждого элемента в исходном порядке. new HashSet (list) тоже убирает дубликаты, но у множества нет гарантированного порядка. Чтобы убрать дубликаты на месте, используйте var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));.

Q: Когда использовать HashSet вместо List?

Используйте HashSet , когда вы в основном спрашиваете «есть ли этот элемент в коллекции?» или когда элементы должны быть уникальными. List .Contains просматривает все элементы, поэтому замедляется по мере роста списка, а HashSet .Contains нет. Используйте List , когда важны порядок, дубликаты или доступ по индексу.

Q: Почему мой HashSet содержит одинаковые объекты?

Ваш класс не переопределяет Equals и GetHashCode, поэтому множество сравнивает ссылки, и два объекта с одинаковыми значениями полей считаются разными. Переопределите оба метода (всегда вместе) или передайте IEqualityComparer в конструктор множества.

HashSet<T> это коллекция, в которой каждый элемент встречается не больше одного раза. У неё нет индекса и гарантированного порядка, а взамен она проверяет принадлежность примерно за постоянное время: найти один тег среди миллиона занимает примерно столько же времени, сколько среди десяти.

Добавление элементов: Add возвращает bool

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tags = new HashSet<string> { "sale", "new" };

        Console.WriteLine(tags.Add("gift"));  // added
        Console.WriteLine(tags.Add("sale"));  // already present
        Console.WriteLine(tags.Count);

        Console.WriteLine(tags.Contains("new"));
        Console.WriteLine(tags.Remove("new"));
        Console.WriteLine(tags.Remove("used")); // not there: false, no exception
        Console.WriteLine(tags.Count);
    }
}

Вывод:

True
False
3
True
True
False
2

Добавление дубликата не является ошибкой; Add просто возвращает false, а множество не меняется. Это возвращаемое значение самое полезное в методе. Оно объединяет «видел ли я это?» и «запомни это» в один вызов:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] signups = { "ana@x.com", "ben@x.com", "ana@x.com", "cy@x.com", "ben@x.com" };
        var seen = new HashSet<string>();

        foreach (string email in signups)
        {
            if (!seen.Add(email))
            {
                Console.WriteLine("Duplicate: " + email);
            }
        }
        Console.WriteLine(seen.Count + " unique");
    }
}

Вывод:

Duplicate: ana@x.com
Duplicate: ben@x.com
3 unique

Почему Contains быстрый

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

// Slow on large inputs: Contains scans bannedList for every order.
var flagged = orders.Where(o => bannedList.Contains(o.CustomerId));

// Fast: build the set once, then each lookup is constant time.
var banned = new HashSet<int>(bannedList);
var flagged2 = orders.Where(o => banned.Contains(o.CustomerId));

Построение множества стоит одного прохода по списку, поэтому оно окупается, только если вы ищете больше нескольких раз.

Удаление дубликатов из списка

Есть три распространённых способа, и они различаются тем, что происходит с порядком:

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

class Program
{
    static void Main()
    {
        var cities = new List<string> { "Lima", "Oslo", "Lima", "Pune", "Oslo", "Kyiv" };

        // 1. LINQ Distinct: new list, first occurrences in original order
        List<string> unique = cities.Distinct().ToList();
        Console.WriteLine(string.Join(", ", unique));

        // 2. A set: unique, but a set has no guaranteed order
        var set = new HashSet<string>(cities);
        Console.WriteLine(set.Count);

        // 3. In place, keeping order: RemoveAll with a seen-set
        var seen = new HashSet<string>();
        cities.RemoveAll(c => !seen.Add(c));
        Console.WriteLine(string.Join(", ", cities));
    }
}

Вывод:

Lima, Oslo, Pune, Kyiv
4
Lima, Oslo, Pune, Kyiv

Distinct это правильный выбор по умолчанию, когда на выходе нужен список. Вариант на месте работает, потому что RemoveAll вызывает предикат по одному разу для каждого элемента по порядку: seen.Add возвращает false для второй и последующих копий, и удаляются ровно они.

Операции над множествами: объединение, пересечение, разность

У HashSet<T> есть операции из теории множеств. Методы ...With изменяют множество, у которого вызваны, и ничего не возвращают.

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

class Program
{
    static string Show(HashSet<string> s)
    {
        return string.Join(", ", s.OrderBy(x => x));
    }

    static void Main()
    {
        string[] monday = { "Ana", "Ben", "Chloe" };
        string[] tuesday = { "Ben", "Chloe", "Dev" };

        var either = new HashSet<string>(monday);
        either.UnionWith(tuesday);             // in either list
        Console.WriteLine("Union:     " + Show(either));

        var both = new HashSet<string>(monday);
        both.IntersectWith(tuesday);           // in both
        Console.WriteLine("Intersect: " + Show(both));

        var onlyMonday = new HashSet<string>(monday);
        onlyMonday.ExceptWith(tuesday);        // in monday, not tuesday
        Console.WriteLine("Except:    " + Show(onlyMonday));

        var oneDay = new HashSet<string>(monday);
        oneDay.SymmetricExceptWith(tuesday);   // in exactly one
        Console.WriteLine("Symmetric: " + Show(oneDay));

        Console.WriteLine(both.IsSubsetOf(monday));
        Console.WriteLine(either.IsSupersetOf(tuesday));
        Console.WriteLine(onlyMonday.Overlaps(tuesday));
        Console.WriteLine(new HashSet<int> { 1, 2 }.SetEquals(new[] { 2, 1, 1 }));
    }
}

Вывод:

Union:     Ana, Ben, Chloe, Dev
Intersect: Ben, Chloe
Except:    Ana
Symmetric: Ana, Dev
True
True
False
True

Аргументом может быть любой IEnumerable<T>: массив, список или другое множество. SetEquals не учитывает порядок и дубликаты в аргументе. Вспомогательный метод Show сортирует перед выводом, потому что на порядок перебора множества нельзя полагаться.

У LINQ есть соответствующие методы, которые возвращают новую последовательность и не трогают входные данные: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Используйте их, когда не хотите изменять множество или когда на входе списки.

Собственное равенство для ваших классов

Множество решает, «тот же ли это элемент», через GetHashCode и Equals. У класса, который их не переопределяет, оба метода основаны на идентичности объекта, поэтому два объекта с равными полями это два разных элемента:

using System;
using System.Collections.Generic;

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

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

    public override bool Equals(object obj)
    {
        var other = obj as Coord;
        return other != null && other.X == X && other.Y == Y;
    }

    public override int GetHashCode()
    {
        unchecked { return X * 397 ^ Y; }
    }
}

class Program
{
    static void Main()
    {
        var points = new HashSet<Point> { new Point(1, 2), new Point(1, 2) };
        Console.WriteLine(points.Count); // 2: compared by reference

        var coords = new HashSet<Coord> { new Coord(1, 2), new Coord(1, 2) };
        Console.WriteLine(coords.Count); // 1: compared by value
        Console.WriteLine(coords.Contains(new Coord(1, 2)));
    }
}

Вывод:

2
1
True

Правило: объекты, равные по Equals, должны возвращать одинаковый GetHashCode. Переопределите только Equals, и множество будет искать не в той корзине и по-прежнему показывать дубликаты. В .NET Core 2.1 и новее HashCode.Combine(X, Y) строит хороший хеш-код без ручной арифметики.

Когда класс изменить нельзя или для одного множества нужно другое понятие «одинаковости», передайте IEqualityComparer<T> в конструктор. Для строк есть готовые компараторы:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var extensions = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { ".jpg", ".png" };
        Console.WriteLine(extensions.Contains(".JPG"));
        Console.WriteLine(extensions.Add(".PNG"));
        Console.WriteLine(extensions.Count);
    }
}

Вывод:

True
False
2

В C# 9 и новее record сам генерирует Equals и GetHashCode на основе значений, поэтому record Point(int X, int Y); работает в множестве без дополнительного кода.

Никогда не меняйте поле, участвующее в GetHashCode, пока объект находится в множестве. Объект остаётся в корзине своего старого хеша, поэтому Contains и Remove перестают его находить.

Порядок и SortedSet

HashSet<T> перебирается в порядке, который следует считать произвольным. Если нужны отсортированные элементы, сортируйте при выводе (set.OrderBy(x => x)) или используйте SortedSet<T>, который всегда держит элементы упорядоченными и добавляет Min, Max и запросы по диапазону за O(log n) на операцию:

var ranks = new SortedSet<int> { 30, 10, 20 };
Console.WriteLine(string.Join(", ", ranks)); // 10, 20, 30
Console.WriteLine(ranks.Min);                // 10

HashSet, List или Dictionary

Что нужно	Что использовать
Уникальные элементы, быстрая проверка «есть ли?»	`HashSet<T>`
Уникальные элементы, всегда отсортированные	`SortedSet<T>`
Порядок, дубликаты, доступ по индексу	`List<T>`
Значение под каждым ключом	`Dictionary<TKey, TValue>`

Множество это словарь с ключами и без значений. Если вы пишете Dictionary<string, bool> только чтобы отслеживать принадлежность, HashSet<string> скажет то же самое понятнее.

Частые ошибки

Ожидание порядка. У множества нет порядка, на который можно полагаться; сортируйте или используйте SortedSet<T>.
Собственные классы без Equals и GetHashCode. Одинаково выглядящие объекты становятся отдельными элементами.
Переопределение одного Equals. Всегда переопределяйте вместе с ним GetHashCode.
Изменение элемента после добавления. Множество больше не может его найти.
Обращение к множеству по индексу. set[0] не компилируется; индекса нет. Если нужны позиции, преобразуйте через ToList().

Часто задаваемые вопросы

Что такое HashSet в C#?

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

Что возвращает HashSet.Add?

Add возвращает true, когда элемент добавлен, и false, когда он уже был в множестве. Поэтому if (!seen.Add(x)) это проверка на дубликат в одну строку: один и тот же вызов добавляет новые элементы и сообщает о повторных.

Как удалить дубликаты из List в C#?

list.Distinct().ToList() возвращает новый список без дубликатов и сохраняет первое вхождение каждого элемента в исходном порядке. new HashSet<T>(list) тоже убирает дубликаты, но у множества нет гарантированного порядка. Чтобы убрать дубликаты на месте, используйте var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));.

Когда использовать HashSet вместо List?

Используйте HashSet<T>, когда вы в основном спрашиваете «есть ли этот элемент в коллекции?» или когда элементы должны быть уникальными. List<T>.Contains просматривает все элементы, поэтому замедляется по мере роста списка, а HashSet<T>.Contains нет. Используйте List<T>, когда важны порядок, дубликаты или доступ по индексу.

Почему мой HashSet содержит одинаковые объекты?

Ваш класс не переопределяет Equals и GetHashCode, поэтому множество сравнивает ссылки, и два объекта с одинаковыми значениями полей считаются разными. Переопределите оба метода (всегда вместе) или передайте IEqualityComparer<T> в конструктор множества.

Связанные концепции

HashSet в C#: уникальные элементы, Contains и операции над множествами

Добавление элементов: Add возвращает bool

Почему Contains быстрый

Удаление дубликатов из списка

Операции над множествами: объединение, пересечение, разность

Собственное равенство для ваших классов

Порядок и SortedSet

HashSet, List или Dictionary

Частые ошибки

Часто задаваемые вопросы

Учитесь программировать с Coddy