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

Ответ 1

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

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

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

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

Ответ 2

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

Часть моего синтаксического ярлыка для файлов UnrealScript - это новая функция, которая выделяет комментарии в стиле Doxygen. Мне нужно узнать, действительна ли команда @ или \, чтобы определить, показывать ли ее серым (действительным) или красным (недействительным). У меня есть HashSet<string> всех допустимых команд, поэтому всякий раз, когда я нажимаю токен @xxx в lexer, я использую 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 он не быстрее для больших наборов, но для небольших наборов стоит поэкспериментировать. У меня есть несколько сотен предметов, поэтому я передал это.

Ответ 3

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

A 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 is O (1) add, O (1) retrieve by index, O ( n) найти/удалить).

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

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

Ответ 7

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

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

после выполнения этих кодов, уникальныеStrings содержат { "abc", "ghjr", "yre", "obm", "qwrt", "vyeu" };

Ответ 8

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

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

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

Ответ 9

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

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

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

Ответ 10

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