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

Я исследую HashSet<T>тип, но я не понимаю, где он стоит в коллекциях.

Можно ли использовать его для замены List<T>? Я думаю, что производительность a HashSet<T>будет лучше, но я не вижу индивидуального доступа к его элементам.

Это только для перечисления?

Важная вещь HashSet<T>в названии прямо здесь: это набор . Единственное, что вы можете сделать с одним набором, - это определить, каковы его члены, и проверить, является ли элемент членом.

Запрос о том, можете ли вы извлечь отдельный элемент (например set[45]), неправильно понимает концепцию набора. Нет 45-го элемента набора. Предметы в наборе не имеют упорядочивания. Наборы {1, 2, 3} и {2, 3, 1} идентичны во всех отношениях, потому что они имеют одинаковое членство, и членство - это все, что имеет значение.

Несколько опасно перебирать объект, HashSet<T>потому что это накладывает порядок на элементы в наборе. Этот порядок на самом деле не является свойством множества. Вы не должны полагаться на это. Если вам важно упорядочить элементы в коллекции, эта коллекция не является набором.

Наборы действительно ограничены и с уникальными членами. С другой стороны, они действительно быстрые.

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

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

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

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

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; }
}

А List<T>орудия IList<T>, который расширяетICollection<T>

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; }
}

У HashSet есть заданная семантика, внутренне реализованная через хэш-таблицу:

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

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

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

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

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

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

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

HashSet будет использоваться для удаления повторяющихся элементов в коллекции IEnumerable. Например,

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

после запуска этих кодов uniqueStrings содержит {"abc", "ghjr", "yre", "obm", "qwrt", "vyeu"};

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

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

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

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

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

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

Как следует из названия, HashedSet<T>это структура данных, которая реализует семантику набора . Структура данных оптимизирована для реализации операций над множествами (т. Е. Объединение, Разница, Пересечение), что невозможно сделать так же эффективно, как при традиционной реализации List.

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

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

В основном предполагаемом сценарии HashSet<T>следует использовать, когда вы хотите более конкретные операции над множествами для двух коллекций, чем предоставляет LINQ. Методы LINQ хотели Distinct, Union, Intersectи Exceptдостаточно в большинстве случаев, но иногда могут потребоваться больше операций мелкозернистых, и HashSet<T>обеспечивают:

• UnionWith
• IntersectWith
• ExceptWith
• SymmetricExceptWith
• Overlaps
• IsSubsetOf
• IsProperSubsetOf
• IsSupersetOf
• IsProperSubsetOf
• SetEquals

Еще одно различие между LINQ и HashSet<T>«перекрывающимися» методами заключается в том, что LINQ всегда возвращает новый IEnumerable<T>, а HashSet<T>методы изменяют исходную коллекцию.