C # Установить коллекцию? - PullRequest
445 голосов
/ 08 октября 2008

Кто-нибудь знает, есть ли хороший эквивалент коллекции Java Set в C #? Я знаю, что вы можете несколько имитировать набор, используя Dictionary или HashTable, заполняя, но игнорируя значения, но это не очень элегантный способ.

Ответы [ 9 ]

402 голосов
/ 08 октября 2008

Если вы используете .NET 3.5, вы можете использовать HashSet<T>. Это правда, что .NET не обслуживает наборы так же хорошо, как Java.

Wintellect PowerCollections также может помочь.

115 голосов
/ 24 мая 2012

Структура данных HashSet<T>:

Структура данных библиотеки классов Framework HashSet<T> была представлена ​​в .NET Framework 3.5. Полный список его членов можно найти на справочной странице MSDN для HashSet<T>.

HashSet<T> более или менее моделируется после математического набора , что означает, что:

  1. Может не содержать повторяющихся значений.

  2. Его элементы не имеют определенного порядка; поэтому тип не реализует интерфейс IList<T>, но более базовый ICollection<T>. Как следствие, элементы внутри хеш-набора не могут быть доступны случайным образом через индексы; они могут повторяться только через перечислитель.

  3. Доступны некоторые установленные функции, такие как Union, Intersection, IsSubsetOf, IsSupersetOf. Они могут пригодиться при работе с несколькими наборами.

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

Почему бы не List<T>?

Поскольку HashSet<T> - это просто набор уникальных объектов, вы можете задаться вопросом, почему это должна быть структура данных. Обычный List<T> может иметь такое же поведение, проверяя, найден ли объект в списке, прежде чем добавлять его.

Короткий ответ - скорость. Поиск по обычному List<T> становится очень медленным и очень быстрым, так как добавляется больше элементов. Для HashSet<T> требуется структура, которая обеспечит быструю скорость поиска и вставки.

Тесты:

Давайте сравним быстродействие HashSet<T> с List<T>.

Каждое испытание состояло из добавления целых чисел от 0 до 9999 к каждой коллекции. Однако мод 25 был применен к каждому целому числу. Мод 25 создает максимальное количество типов элементов 25. Поскольку было добавлено 10000 элементов, это вызвало 400 столкновений, что позволило структурам данных использовать свои алгоритмы поиска. Время измерялось 3 раза после 10000 испытаний и усреднялось.

Не обращайте слишком много внимания на конкретные времена выполнения тестов, поскольку они зависят от моего оборудования, но посмотрите, как они сравниваются друг с другом.

           Average time [ms]
----------------------------
HashSet<T>             2,290
List<T>                5,505

Теперь давайте сделаем объекты элементами вместо примитивных типов. Я написал быстрый Person класс с тремя полями: Name, LastName и ID. Поскольку я не включил какой-либо конкретный способ сравнения объектов, все элементы будут добавлены без коллизий. На этот раз 1000 Person объектов были добавлены в каждую коллекцию для одного испытания. Общее время 3 серии из 1000 испытаний было усреднено.

           Average time [ms]
----------------------------
HashSet<Person>          201
List<Person>           3,000

Как вы видите, разница во времени выполнения становится астрономической при использовании объектов, что делает HashSet<T> выгодным.

107 голосов
/ 08 октября 2008

Попробуйте HashSet :

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

Емкость объекта HashSet (Of T) - это количество элементов, которые объект может содержать. Емкость объекта HashSet (Of T) автоматически увеличивается при добавлении элементов к объекту.

Класс HashSet (Of T) основан на модели математических множеств и обеспечивает высокопроизводительные операции над множествами, аналогичные доступу к клавишам словаря (Of TKey, TValue) или Hashtable коллекции. Проще говоря, класс HashSet (Of T) можно представить как словарь (Of TKey, TValue) коллекция без значений.

Коллекция HashSet (Of T) не отсортирована и не может содержать повторяющиеся элементы ...

18 голосов
/ 31 августа 2013

Если вы используете .NET 4.0 или более позднюю версию:

Если вам нужна сортировка, используйте SortedSet<T>. В противном случае, если вы этого не сделаете, используйте HashSet<T>, поскольку это O(1) для операций поиска и манипулирования. Принимая во внимание, что SortedSet<T> - это O(log n) для операций поиска и манипулирования.

14 голосов
/ 08 октября 2008

Я использую Iesi.Collections http://www.codeproject.com/KB/recipes/sets.aspx

Он используется во многих проектах OSS, я впервые столкнулся с ним в NHibernate

12 голосов
/ 26 ноября 2009

Я использую обертку вокруг Dictionary<T, object>, сохраняя в значениях нули. Это дает O (1) добавление, поиск и удаление ключей, и для всех намерений и целей действует как набор.

11 голосов
/ 08 октября 2008

Посмотрите на PowerCollections на CodePlex. Помимо Set и OrderedSet у него есть несколько других полезных типов коллекций, таких как Deque, MultiDictionary, Bag, OrderedBag, OrderedDictionary и OrderedMultiDictionary.

Для большего количества коллекций есть также C5 Generic Collection Library .

0 голосов
/ 05 февраля 2012

Я знаю, что это старый поток, но я столкнулся с той же проблемой и обнаружил, что HashSet очень ненадежен, потому что при одном и том же семени GetHashCode () возвращал разные коды. Итак, я подумал, почему бы просто не использовать List и скрыть метод add, как этот

public class UniqueList<T> : List<T>
{
    public new void Add(T obj)
    {
        if(!Contains(obj))
        {
            base.Add(obj);
        }
    }
}

Поскольку List использует метод Equals исключительно для определения равенства, вы можете определить метод Equals для вашего типа T, чтобы убедиться, что вы получите желаемые результаты.

0 голосов
/ 08 октября 2008

Вы можете реализовать свою собственную работоспособную реализацию набора за пару часов. Я использовал это, когда мне пришлось это сделать (извините, у меня нет удобного кода): http://java.sun.com/j2se/1.4.2/docs/api/java/util/Set.html

...