Когда я должен использовать тип HashSet <T>?

A HashSet реализует интерфейс ICollection :

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    // Methods
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);

    // Properties
   int Count { get; }
   bool IsReadOnly { get; }
}

A List реализует IList , который расширяет ICollection

public interface IList<T> : ICollection<T>
{
    // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);

    // Properties
    T this[int index] { get; set; }
}

A HashSet имеет семантику набора, реализованную с помощью внутренней хэш-таблицы:

Набор - это коллекция, которая не содержит повторяющиеся элементы, и чьи элементы не находятся в определенном порядке.

Что получает HashSet, если он теряет поведение индекса / позиции / списка?

Добавление и извлечение элементов из HashSet всегда осуществляется самим объектом, а не через индексатор, и близко к операция O (1) (список - это O (1) добавить, O (1) получить по индексу, O (n) найти / удалить).

Поведение HashSet можно сравнить с использованием Dictionary только добавлением / удалением ключей как значений и игнорированием самих значений словаря. Можно было бы ожидать, что ключи в словаре не будут иметь повторяющихся значений, и в этом суть части «Установить».

Производительность была бы плохой причиной для выбора HashSet вместо List. Вместо этого, что лучше отражает ваше намерение? Если порядок важен, то Set (или HashSet) отсутствует. Аналогично, если разрешены дубликаты. Но есть множество обстоятельств, когда нас не волнует порядок, и мы не хотели бы иметь дубликатов - и именно тогда вам нужен набор.

HashSet - это набор , реализованный посредством хеширования. Набор - это набор значений, не содержащий повторяющихся элементов. Значения в наборе также обычно неупорядочены. Итак, нет, набор не может использоваться для замены списка (если только вы не должны использовать набор в первую очередь).

Если вам интересно, для чего может быть полезен набор: везде, где вы хотите избавиться дубликатов, очевидно. В качестве слегка надуманного примера предположим, что у вас есть список из 10.000 редакций программного проекта, и вы хотите узнать, сколько людей внесли свой вклад в этот проект. Вы можете использовать Set и перебирать список ревизий и добавлять автора каждой ревизии в набор. Когда вы закончите итерацию, размер набора будет тем ответом, который вы искали.

Вероятно, наиболее распространенное использование хэш-наборов - это увидеть, содержат ли они определенный элемент, что близко к операции O (1) для них (при условии достаточно сильной хеш-функции), в отличие от для списков, для которых проверка на включение составляет O (n) (и отсортированных наборов, для которых это O (log n)). Поэтому, если вы много проверяете, содержится ли элемент в каком-либо списке, hahssets может улучшить производительность. Если вы будете выполнять итерацию только по ним, особой разницы не будет (итерация по всему набору - O (n), так же, как со списками и хэш-наборами, при добавлении элементов немного больше накладных расходов).

И нет, вы можете 'не индексировать набор, что в любом случае не имеет смысла, потому что наборы не упорядочены. Если вы добавите какие-то элементы, набор не запомнит, какой из них был первым, а какой вторым и т. Д.

Список используется для хранения упорядоченных наборов информации. Если вы знаете относительный порядок элементов списка, вы можете получить к ним доступ в постоянное время. Однако, чтобы определить, где находится элемент в списке, или проверить, существует ли он в списке, время поиска является линейным. С другой стороны, HashedSet не гарантирует порядка хранимых данных и, следовательно, обеспечивает постоянное время доступа для своих элементов.

Как следует из названия, HashedSet - это структура данных, которая реализует семантику набора . Структура данных оптимизирована для реализации операций над наборами (например, Union, Difference, Intersect), что не может быть выполнено так эффективно с традиционной реализацией List.

Итак, выбор того, какой тип данных использовать, действительно зависит от того, что вы пытаетесь сделать с вашим приложением. Если вас не волнует, как ваши элементы упорядочены в коллекции, и вы хотите только перечислить или проверить наличие, используйте HashSet . В противном случае рассмотрите возможность использования List или другой подходящей структуры данных.

Вкратце - каждый раз, когда у вас возникает соблазн использовать Словарь (или Словарь, где S является свойством T), вам следует рассмотреть HashSet (или HashSet +, реализующий IEquatable на T, что приравнивается к S)

Здесь реальный пример того, где я использую HashSet :

Часть моей подсветки синтаксиса для файлов UnrealScript - это новая функция, которая выделяет комментарии в стиле Doxygen . Мне нужно знать, допустима ли команда @ или \ , чтобы определить, отображать ли ее серым (допустимый) или красным (недопустимый). У меня есть HashSet всех допустимых команд, поэтому всякий раз, когда я нажимаю токен @xxx в лексере, я использую validCommands.Contains (tokenText) ] в качестве проверки действительности O (1). Я действительно не Меня не волнует ничего, кроме существования команды в наборе допустимых команд. Давайте посмотрим на альтернативы, с которыми я столкнулся:

• Dictionary : Какой тип использовать для значения? Значение не имеет смысла, поскольку я просто собираюсь использовать ContainsKey . Примечание. До .NET 3.0 это был единственный выбор для поиска O (1) - HashSet был добавлен для 3.0 и расширен для реализации ISet для 4.0. 1239] List : Если я сохраню список отсортированным, я могу использовать BinarySearch , который равен O (log n) (не видел этого факта, упомянутого выше). Однако, поскольку мой список допустимых команд - это фиксированный список, который никогда не изменяется, он никогда не будет более подходящим, чем просто ...
• строка [] : Опять же, Массив. BinarySearch дает производительность O (log n). Если список короткий, это может быть лучший вариант. У него всегда меньше места, чем у HashSet , Dictionary или List . Даже с BinarySearch он не быстрее для больших наборов, но для небольших наборов стоит поэкспериментировать. У меня есть несколько сотен элементов, поэтому я передал это.

HashSet - это структура данных в платформе .NET, способная представлять математический набор в виде объекта. В этом случае он использует хэш-коды (результат GetHashCode для каждого элемента) для сравнения равенства элементов набора.

Набор отличается от списка тем, что допускает только одно вхождение одного и того же содержащегося элемента внутри. HashSet просто вернет false , если вы попытаетесь добавить второй идентичный элемент. Действительно, поиск элементов выполняется очень быстро ( O (1) раз), поскольку внутренняя структура данных представляет собой просто хеш-таблицу.

Если вам интересно, что использовать, обратите внимание, что использование ] List , где HashSet является подходящим, не является самой большой ошибкой, хотя это может потенциально позволить проблемы, когда у вас есть нежелательные повторяющиеся элементы в вашей коллекции. Более того, поиск (поиск элемента) намного эффективнее - в идеале O (1) (для идеального группирования) вместо O (n) времени, что очень важно во многих сценарии.