Коллекции – структуры данных для работы с наборами однотипных объектов.

Когда решается, какую именно структуру использовать для хранения или передачи коллекции, стоит подумать о следующем:

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

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

Стандартные generic-коллекции (.NET 2.0)

System.Collections.Generic.List<T>

Реализует динамический массив: содержит массив T[] и текущее количество элементов в нём. Если в момент операции добавления элемента массив уже заполнен, происходит выделение массива большего размера и копирование содержимого старого массива в новый.

Динамический массив – структура данных, оптимизированная для добавления и удаления элементов из конца коллекции. Эти операции имеют амортизированную сложность O(1) – одна конкретная операция может вызвать перевыделение массива и оказаться долгой (O(n)), но в последовательности выполняемых операций такие долгие операции гарантированно редки.

Добавление и удаление элементов из середины коллекции приводят к копированию хвоста и, соответственно, имеют сложность O(n).

Поддерживаемые классом операции:

[] получение, запись элемента по индексу O(1)
Add добавление элемента в конец O(1) аморт.
Insert добавление элемента в середину O(n)
RemoveAt(Count — 1) удаление элемента с конца O(1)
RemoveAt удаление элемента из середины O(n)
Find поиск заданного элемента O(n)
Contains поиск заданного элемента O(n)
Remove удаление заданного элемента O(n)
Clear удаление всех элементов O(n)
Sort упорядочение O(n log n)
BinarySearch поиск элемента в упорядоченном списке O(log n)

Особенности использования:

  • Имеется конструктор, в который передаётся начальный размер внутреннего массива – его следует использовать для предотвращения пересоздания массивов, если известно, что в List будет сразу добавлено большое количество элементов. Также с этой целью можно выставить свойство Capacity, равное текущей длине массива.
  • Нельзя одновременно перечислять List и изменять его – после изменения списка созданные до этого изменения перечислители-IEnumerator-ы выбрасывают InvalidOperationException. Например, это исключение будет наблюдаться в следующем коде:
    var list = new List { 1, 2 };
    foreach (int i in list)
    {
        list.Add(i * 2);
    }
    

    Такое поведение присуще всем коллекциям из System.Collections.Generic.

  • Предоставляет методы BinarySearch для бинарного поиска в упорядоченной коллекции, которые работают за O(log n). Для их использования, однако, требуется поддерживать упорядоченность, добавляя новые элементы в нужное место согласно их порядку – если коллекция часто изменяется, накладные расходы на такие вставки оказываются больше выгоды от быстрого поиска.

Особенности текущей реализации:

  • Конструктор по умолчанию вообще не создаёт массив, при добавлении первого элемента создаётся массив размером 4.
  • Конструктор с параметром IEnumerable<T> пытается привести переданное перечисление к ICollection<T> и при успехе создаёт массив размера, который вернул метод ICollection<T>.Count.
  • При небольшом переполнении массива новый создаётся в 2 раза больше прежнего. Например, при создании List<T> конструктором по умолчанию и добавлении туда по одному 33 элементов перевыделение массива будет производиться 5 раз (сначала массив размером 4, потом 8, 16, 32 и 64).
  • Если переполнение происходит при вызове метода AddRange и увеличения в два раза недостаточно, то массив увеличивается ровно настолько, чтобы вместить добавленные объекты. Например, при создании List<T> конструктором по умолчанию и добавлении туда 33 элементов из другого List<T> выделение массива будет произведено 1 раз.
  • Перечислитель, возвращаемый методом List<T>.GetEnumerator, является struct-ом. Это может привести к неожиданным эффектам из-за боксинга структуры, если этот перечислитель записывается в переменную, объявленную с помощью var, а потом передаётся в метод, ожидающий IEnumerator (см., например, https://codeblog.jonskeet.uk/2010/07/27/iterate-damn-you/).
  • Уменьшение размера массива происходит только при вызове метода TrimExcess или установке свойства Capacity. В частности, удаление элементов не приводит к уменьшению массива. Например, если добавить в List<T> миллион объектов, а потом их все удалить, то объект-коллекция будет содержать массив размером 1048576, занимающий место в large object heap.
  • Таким образом, если из List не производится удаление элементов, то он обеспечивает не более, чем двукратный перерасход памяти. Если же удаление производится, то перерасход может быть сколь угодно большим.

List<T> – единственная коллекция наряду с массивом T[], для которой в методах LINQ есть оптимизации:

  • метод Where без параметра-индекса при передаче туда List возвращает WhereListIterator, который не создаёт IEnumerator-ов для List<T>, а получает доступ к элементам непосредственно через свойство List<T>. При дальнейшем применении к нему Where без параметра-индекса опять получается WhereListIterator, при вызове Select без параметра-индекса – WhereSelectListIterator.
  • метод Select без параметра-индекса при передаче List возвращает WhereSelectListIterator, который также не создаёт IEnumerator-ов для List<T>. При применении к нему Select без параметра-индекса результат – WhereSelectListIterator.

Остальные методы LINQ, обходящие перечисление, не содержат специальных оптимизаций для List. Методы Where и Select с параметром-индексом, SelectMany, Concat, Take, TakeWhile, Skip, SkipWhile, Zip, DefaultIfEmpty, OfType всегда перечисляют аргумент обычным образом и работают через yield, метод Cast сначала пытается привести перечисление к нужному типу, при неудаче создаётся осуществляющий приведение поэлементно итератор с yield. Методы First, FirstOrDefault, Single, SingleOrDefault, Last, LastOrDefault, ElementAt, ElementAtOrDefault без параметра возвращают элемент с нужным индексом для объектов, реализующих IList<T>, осуществляя перечисление для остальных. Методы Any, All, LongCount, Count с фильтром всегда создают итераторы, Count без фильтра пытается привести перечисление к ICollection<T> и ICollection перед итерацией. Наконец, метод Contains с заданным сравнителем всегда создаёт итератор, Contains со сравнителем по умолчанию пытается привести перечисление к ICollection<T>.

Методы LINQ Reverse и ToArray работают через создание internal-структуры Buffer<T> (похожей на List<T>), которая пытается привести исходное перечисление к ICollection<T> для определения размера массива, при неудаче начинается итерация и создаётся временный массив размера 4, удваивающийся при переполнении. Таким образом, например, если применить к List<T> с 33 элементами методы Select и ToArray, то будет создано 6 массивов размером 4, 8, 16, 32, 64 и, наконец, 33. Метод OrderBy также работает через сохранение элементов исходного перечисления в Buffer<T>. Ключи, по которым происходит сортировка, при этом вычисляются один раз и сохраняются в отдельном массиве.

List<T> – самая простая и часто используемая коллекция.
Стоит использовать, если:

  • требуется только создать и/или передать коллекцию объектов, не заботясь об их внутреннем устройстве и порядке внутри коллекции
  • в коллекции нужно сохранить порядок добавления элементов и требуется только быстрое перечисление по порядку или получение по индексу

Не стоит использовать, если:

  • от коллекции требуется поиск элемента (по ключу или по какому-либо сложному критерию). Использование List<T> в таких случаях обычно приводит к нечитаемым строкам-монстрам типа
    list1.Where(l1 => list2.Any(l2 => l2.Key == l1.Key))

    Вообще, если при работе с List<T> приходится писать вызовы LINQ внутри вызовов LINQ, стоит задуматься об использовании более специализированного класса.

  • в коллекцию больших размеров требуется добавлять элементы в середину
  • коллекция будет использоваться и изменяться несколькими потоками

System.Collections.Generic.Queue<T>

Очередь с использованием динамического массива – содержит массив, индекс текущего начала и конца очереди. Позволяет добавлять элементы в конец очереди и просматривать/удалять элементы из начала очереди.

Операции:

Peek получение элемента из головы очереди O(1)
Dequeue получение+удаление элемента из головы очереди O(1)
Enqueue добавление элемента в хвост очереди O(1) аморт.
Clear удаление всех элементов O(n)

Особенности текущей реализации:

  • Устроен аналогично List<T>: конструктор по умолчанию не создаёт массив, начальный размер массива – 4, когда количество элементов в очереди превышает длину массива, его размер удваивается, а уменьшается – только при вызове TrimExcess.
  • Реализует IEnumerable<T>, перечисление идёт от головы к хвосту, перечислитель также является struct-ом

Стоит использовать, если по логике приложения коллекция является FIFO-очередью.

System.Collections.Generic.Stack<T>

Стек с использованием динамического массива – содержит массив и индекс текущей вершины стека. Позволяет добавлять элементы и просматривать/удалять элементы с вершины.

Операции:

Peek получение элемента из вершины стека O(1)
Pop получение+удаление элемента из вершины стека O(1)
Push добавление элемента на вершину стека O(1) аморт.
Clear удаление всех элементов O(n)

Особенности текущей реализации:

  • Устроен аналогично List<T> и Queue<T>: конструктор по умолчанию не создаёт массив, начальный размер массива – 4, при переполнении размер удваивается, а уменьшается – только при вызове TrimExcess.
  • Перечислитель является struct-ом, перечисление начинается с вершины и идёт от последнего добавленного элемента к первому.

Стоит использовать, если по логике приложения коллекция является LIFO-стеком.

System.Collections.Generic.Dictionary<TKey, TValue>

Коллекция пар ключ-значение на основе хэш-таблицы, то есть массива, индексы элементов в котором зависят от их хэша. Работает такая структура следующим образом: при добавлении или получении элемента вычисляется хэш ключа, который определяет, в каком месте массива следует искать данный ключ. Далее оттуда извлекаются хранимые там значения и производятся сравнения ключей на равенство.

Словарь, созданный конструктором по умолчанию, будет использовать EqualityComparer<TKey>.Default для вычисления хэшей и сравнения ключей. Этот экземпляр работает следующим образом:

  • у типов, реализующих IEquatable<T> (среди которых примитивы вроде int), используется object.GetHashCode и IEquatable<T>.Equals;
  • в частности, для строк используется посимвольное сравнение без учёта культур;
  • для Nullable<T> и enum-типов используется сравнитель для их базовых типов;
  • для остальных типов используется object.GetHashCode и object.Equals.

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

Dictionary очень любит бросаться исключениями:

  • при поиске с помощью индексера по ключу, которого в словаре нет, выбрасывается KeyNotFoundException (такое поведение предписывается интерфейсом IDictionary<TKey, TValue>). Если такая ситуация возможна, следует использовать метод TryGetValue.
  • при добавлении элемента с существующим ключом методом Add выбрасывается ArgumentException.
  • при добавлении ключа null выбрасывается ArgumentNullException, даже если указанный для ключей IEqualityComparer способен обработать null.

Производительность хэш-таблицы зависит от качества хэш-функции. Если хэш-функция не даёт равномерного разброса, выдавая одинаковые значения для разных ключей, то эти ключи будут получать один индекс в хэш-таблице, и при поиске элемента по таким ключам придётся осуществлять линейный поиск. Такая ситуация вполне может сложиться, например, если использовать в качестве ключа struct со стандартным GetHashCode, который в .NET возвращает хэш первого поля типа. Например, рассмотрим такую структуру:

struct BadKey
{
    SomeEnum Type;
    string RealKey;
}

Хэш этой структуры равен хэшу Type, и поскольку типичный enum содержит небольшое число значений, разброс хэша будет совершенно неудовлетворительным, поднимая все оценки на сложность операций до сложности линейного поиска O(n). При использовании такой структуры в качестве ключа словаря необходимо либо использовать свой экземпляр сравнителя, либо переопределить её метод GetHashCode, например, так:

struct BetterKey
{
    SomeEnum Type;
    string RealKey;
    
    public override int GetHashCode() =>
      Type.GetHashCode() * 397 ^ (RealKey?.GetHashCode() ?? 0);
}

Ещё один способ прострелить себе ногу словарём – использование в качестве ключа мутабельного класса с переопределённым сравнением. Хэш ключа в словаре вычисляется только один раз – при добавлении пары в словарь. Если у уже добавленной пары изменить ключ, то он окажется в неправильной части хэш-таблицы, и соответственно этот элемент невозможно будет обнаружить. Например:

class MutableKey : IEquatable<MutableKey>
{
    public int Key;

    public bool Equals(MutableKey key) => Key == key?.Key;
    public override int GetHashCode() => Key;
}

void BadDictionary()
{
    var dict = new Dictionary<MutableKey, int>();

    var key = new MutableKey { Key = 1 };
    dict.Add(key, 1);

    key.Key = 2;
    var res = dict[key]; // <=== KeyNotFoundException
}

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

Dictionary можно создать из перечисления с помощью метода LINQ ToDictionary, внутри которого для наполнения словаря используется метод Add, и соответственно, этот метод бросает исключение при повторном вхождении ключа.

Также в LINQ имеется сходный метод ToLookup, который возвращает интерфейс ILookup<TKey, TValue>, ставящий в соответствие ключу не один объект, а коллекцию объектов. Внутри этот метод создаёт объект internal-класса Lookup<TKey, TValue>, поведение которого практически аналогично Dictionary<TKey, TValue[]>, отличаясь только поддержкой ключа null, возвратом пустой коллекции для отсутствующего ключа вместо выбрасывания исключения и удвоением размера хранилища вместо поиска простого числа при переполнении. Методы LINQ GroupBy, Join и GroupJoin также работают через Lookup<TKey, TValue>: GroupBy создаёт его после начала перечисления результата, а Join и GroupJoin создают Lookup из второго аргумента для быстрого поиска соответствий для элементов первого аргумента.

Операции:

[], TryGetValue получение значения по ключу O(1)
ContainsKey проверка наличия ключа O(1)
ContainsValue проверка наличия значения O(n)
[], Add добавление пары ключ-значение O(1) аморт.
Remove удаление пары ключ-значение O(1)
Clear удаление всех элементов O(n)

Значения O(1) в этой таблице достигаются только при хорошей хэш-функции, если хэш-функция допускает большое число коллизий, то эта оценка ухудшается до O(кол-во коллизий).

Особенности текущей реализации:

  • Пустой конструктор не создаёт массива.
  • Имеются конструкторы, в который передаётся начальный размер, но отсутствует свойство c текущим размером массива вроде List<T>.Capacity.
  • Для разрешения коллизий при совпадении хэшей различных ключей в Dictionary используется метод цепочек. Кроме основного массива с элементами словарь содержит массив чисел-«вёдер» того же размера, которые содержат -1, если «ведро» для данного хэша ещё не занято, и индекс элемента в основном массиве, если оно занято. Основной массив заполняется подряд от начала, то есть первая добавленная пара ключ-значение получает в нём индекс 0, вторая – 1, и т.д. Вместе с собственно ключом и значением основной массив содержит также хэш ключа (чтобы не перевычислять при перевыделении массива) и ссылку на следующее «ведро» с тем же хэшем ключа. Таким образом, по хэшу можно однозначно определить «ведро» (его номер определяется как остаток от деления хэша на число вёдер), которое хранит ссылку на один из элементов в основном массиве, а эти элементы, в свою очередь, образуют цепочки для одинаковых значений хэша.
  • Индексы удаляемых элементов выстраиваются в отдельную «свободную» цепочку, и если она непуста, то новые элементы добавляются на места удалённых.
  • При переполнении массива следующий размер выбирается как простое число, большее текущего размера как минимум в 2 раза. Некоторые простые числа до 7199369 зашиты в код, большие простые числа ищутся на лету каждый раз при расширении.
  • Размер массивов никогда не уменьшается – если создать Dictionary с миллионом объектов, а потом удалить их, то потребление словарём памяти останется значительным. Таким образом, если из словаря не производится удаление, максимальный перерасход памяти является линейным: с каждым элементом хранится его 3 значения типа int: «ведро», хэш и ссылка на следующий элемент, и размеры динамических массивов могут превышать количество элементов более, чем в два раза. Если же удаление производится, перерасход может оказаться сколь угодно большим.
  • В словарях с ключами-строками с одним из встроенных сравнителей (StringComparer.X) используется рандомизация хэшей для предотвращения искусственного создания коллизий хэшей при DoS-атаках, и при переполнении счётчика коллизий рандомизатор пересоздаётся.
  • Перечислитель является struct-ом, перечисление идёт в порядке хранения пар в основном массиве. Таким образом, в текущей реализации, если из словаря не производилось удаления элементов, перечисление будет выполнено в порядке добавления, однако это не описано в контракте, и вообще говоря, следует полагать, что порядок произволен.
  • Свойства Keys и Values возвращают коллекции ключей и значений соответственно, которые также перечисляются в порядке хранения в основном массиве и имеют struct-перечислители, которые игнорируют Dispose и возвращают default(TValue) до начала и после завершения перечисления.

Стоит использовать, если основное назначение коллекции – поиск в ней объектов по ключу, когда ключ однозначно задаёт объект. Не стоит использовать:

  • если коллекция будет изменяться из нескольких потоков – для этого есть ConcurrentDictionary, а с Dictionary легко получить одновременное пересоздание вёдер двумя потоками, и NullReferenceException или бесконечный цикл как последствие.
  • если ключу соответствует не один объект, а целая коллекция – для таких случаев предназначен интерфейс ILookup<TKey, TValue> и метод LINQ ToLookup.

System.Collections.Generic.SortedDictionary<TKey, TValue>

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

Конструктор по умолчанию создаёт словарь, сравнивающий ключи с помощью Comparer<T>.Default, который работает следующим образом:

  • у типов, реализующих IComparable<T> (среди которых примитивы вроде int), используется IComparable<T>.CompareTo;
  • у типов, реализующих IComparable, используется IComparable.CompareTo;
  • для Nullable<T> и enum-типов используется сравнитель для их базовых типов;
  • использование других типов приводит к ArgumentException.

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

Операции:

[], TryGetValue получение значения по ключу O(log n)
ContainsKey проверка наличия ключа O(log n)
ContainsValue проверка наличия значения O(n)
[], Add добавление пары ключ-значение O(log n)
Remove удаление пары ключ-значение O(log n)
Clear удаление всех элементов O(1)

Особенности текущей реализации:

  • Метод балансировки дерева – красно-чёрное дерево.
  • Перечислитель – struct, перечисляет элементы по возрастанию ключа.
  • При добавлении ключа null выбрасывается ArgumentNullException, даже если указанный для ключей IComparer способен обработать null.
  • Каждый узел дерева содержит кроме элемента две ссылки и флаг красный/чёрный, так что перерасход памяти составляет на 64-битных машинах 20 байт на элемент.

Стоит использовать, если от коллекции требуется не только поиск по ключу, но и извлечение элементов, упорядоченных по ключу.

System.Collections.Generic.SortedList<TKey, TValue>

Коллекция пар ключ-значение на основе динамического массива. Вставляет новые элементы в нужное место, поддерживая упорядоченность по ключу, и изменения этой коллекции медленны. При нахождении элементов используется бинарный поиск. Конструктор по умолчанию создаёт словарь, сравнивающий ключи с помощью Comparer<T>.Default, имеется конструктор с заданным экземпляром сравнителя.

Операции:

[], TryGetValue получение значения по ключу O(log n)
ContainsKey проверка наличия ключа O(log n)
ContainsValue проверка наличия значения O(n)
[], Add добавление пары ключ-значение O(n)
Remove удаление пары ключ-значение O(n)
Clear удаление всех элементов O(n)

Особенности текущей реализации:

  • Внутри содержит два отдельных массива для ключей и значений.
  • Конструктор по умолчанию не создаёт массивы, имеется конструктор с явным заданием начального размера и свойство Capacity.
  • При переполнении размер массива удваивается, уменьшается только при установке Capacity или вызове TrimExcess – соответственно, если из коллекции не производится удаление, перерасход памяти не более, чем двукратный.
  • Перечислитель – struct.

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

System.Collections.Generic.HashSet<T>

Множество на основе хэш-таблицы. После добавлении нескольких равных элементов в множестве содержится только один экземпляр, добавленный первым. Поддерживает быстрые множественные операции IntersectWith, UnionWith, ExceptWith, SymmetricExceptWith, которые изменяют множество. Появилось в .NET 3.5.

При создании конструктором по умолчанию будет использовать EqualityComparer<TKey>.Default для вычисления хэшей и сравнения элементов. HashSet<T> реализует ICollection<T>, и поэтому вызов метода LINQ Contains без указания сравнителя использует сравнитель для множества.

В отличие от Dictionary, никогда не выбрасывает исключение при добавлении в множество null, считая хэш null-а равным 0 независимо от того, как реализован используемый IEqualityComparer.

Методы LINQ Distinct и Union используют структуру данных, похожую на HashSet<T>. Для обеспечения единственности равных элементов эти методы создают internal-класс Set<T>, поведение которого практически аналогично HashSet<T>, отличаясь только удвоением размера хранилища вместо поиска простого числа при переполнении. Методы Intersect, Except также создают Set<T> из второго аргумента для проверки наличия там элементов из перечисляемого затем первого.

Операции:

Add добавление элемента O(1)
Remove удаление элемента O(1)
Contains поиск элемента O(1)
IntersectWith пересечение O(n)
UnionWith объединение O(n)
ExceptWith разность O(n)
Clear удаление всех элементов O(n)

Особенности текущей реализации:

  • Использует ту же стратегию разрешения коллизий, что и Dictionary<TKey, TValue>: массив «вёдер», которые соответствуют остаткам хэш-кода, ссылающихся на основной массив с элементами, в котором находятся цепочки элементов с одним хэшем.
  • При переполнении массива следующий размер выбирается как простое число, большее текущего размера как минимум в 2 раза, аналогично Dictionary.
  • Так же, как Dictionary, рандомизирует хэши строк при переполнении счётчика коллизий.
  • IntersectWith при пересечении с пустой коллекцией сразу очищает множество.
  • Не уменьшает размер массивов автоматически, содержит метод TrimExcess.
  • Перечислитель – struct.

Стоит использовать, если от коллекции в первую очередь требуется проверка наличия в ней элементов (а не, к примеру, их упорядоченность), или множественные операции.

System.Collections.Generic.SortedSet<T>

Множество на основе бинарного дерева поиска. В отличие от HashSet<T> поддерживает порядок элементов. Появилось в .NET 4.0.

При создании конструктором по умолчанию будет использовать Comparer<TKey>.Default для сравнения элементов. Пары элементов, для которых CompareTo возвращает 0, считаются равными – из таких в множестве может находиться только один.

Операции:

Add добавление элемента O(log n)
Remove удаление элемента O(log n)
Contains поиск элемента O(log n)
IntersectWith пересечение O(n log n)
UnionWith объединение O(n log n)
ExceptWith разность O(n log n)
Clear удаление всех элементов O(1)

Особенности текущей реализации:

  • Метод балансировки дерева – красно-чёрное дерево.
  • Перечислитель – struct, перечисляет элементы по возрастанию ключа. Внутри себя создаёт Stack<Node> для обхода дерева в глубину.

Стоит использовать, если от коллекции требуется не только семантика множества – уникальность элементов и быстрые проверки наличия элемента в коллекции, но и упорядоченность элементов.

System.Collections.Generic.LinkedList<T>

Двусвязный список – элементы хранятся в узлах LinkedListNode<T> вместе со ссылками на предыдущий и следующий элементы. Такая структура в отличие от динамического массива List<T> не позволяет получить элемент по индексу, однако позволяет быстро вставить элемент в начало коллекции или рядом с другим элементом.

List<T> обычно предпочитают LinkedList<T>, так как элементы динамического массива хранятся в одном массиве – рядом, в одной области памяти, которая может быть целиком загружена в кэш процессора. Соседние же элементы списка могут храниться на произвольном удалении друг от друга, в связи с чем их перечисление может вызывать cache miss на каждом шагу и быть значительно медленнее. Однако стоит заметить, что если T – ссылочный тип (класс или интерфейс), то в List<T> рядом хранятся не сами объекты, а лишь ссылки на них, и соображения о cache miss применимы и к List, если требуется не только перечислить объекты, но и обратиться к их свойствам.

Операции:

AddAfter, AddBefore, AddFirst, AddLast добавление элемента O(1)
RemoveFirst, RemoveLast удаление крайнего элемента O(1)
Remove(T) поиск + удаление элемента O(n)
Remove(LinkedListNode<T>) удаление элемента O(1)
Contains проверка наличия элемента O(n)
Find, FindLast поиск элемента O(n)
Clear удаление всех элементов O(n)

Особенности текущей реализации:

  • Используется двусвязный кольцевой список, объект коллекции хранит ссылку на голову списка, а голова и хвост ссылаются друг на друга.
  • Перечислитель – struct.
  • Время работы Clear зависит от размера коллекции, потому что LinkedListNode<T> содержат ссылки на список, и при удалении их нужно обнулять.

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

Потокобезопасные коллекции из .NET 4.0

System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue>

Потокобезопасная коллекция пар ключ-значение на основе хэш-таблицы. Поведение в основном сходно с Dictionary<TKey, TValue>; генерация хэша и сравнение ключей производятся с помощью экземпляра IEqualityComparer<TKey>, по умолчанию EqualityComparer<TKey>.Default. Предоставляет атомарные операции:

  • получение значения по ключу + добавление значения, если ключ отсутствует – GetOrAdd
  • получение и обновление значения по ключу + добавление значения, если ключ отсутствует – AddOrUpdate

Операция GetOrAdd гарантирует, что при её одновременном вызове из нескольких потоков в словарь добавится только одно значение, и оно будет возвращено из метода всем потокам. Однако делегат, передаваемый в GetOrAdd, может выполниться несколько раз в нескольких потоках. Если это недопустимо (например, делегат совершает опасное или долгое побочное действие вроде записи в базу), то следует использовать ConcurrentDictionary<TKey, Lazy<TValue>>. Вообще говоря, ConcurrentDictionary работает эффективнее обёрнутого блокировками Dictionary, потому что в специальном классе блокировщики привязаны к «вёдрам», и обращение к одному «ведру» может не блокировать обращение к другому. Однако методы CopyTo, ToArray, Clear и свойства Keys, Values, Count, IsEmpty читают из всех «вёдер» и поэтому блокируют весь словарь. Перечисление элементов в начале метода GetEnumerator сохраняет ссылки на текущие вёдра, поэтому не требует глобальной блокировки и не выбрасывает исключение при изменении коллекции. В конструктор можно передать предполагаемое количество потоков, могущих одновременно редактировать словарь.

Операции:

[], TryGetValue получение значения по ключу O(1)
ContainsKey проверка наличия ключа O(1)
ContainsValue проверка наличия значения O(n)
[], TryAdd добавление пары ключ-значение O(1) аморт.
GetOrAdd атомарное получение с добавлением, если ключ отсутствует O(1)
AddOrUpdate атомарное обновление с добавлением, если ключ отсутствует O(1)
TryUpdate атомарная проверка с обновлением O(1)
TryRemove удаление пары ключ-значение O(1)
Clear удаление всех элементов O(n)

Особенности текущей реализации:

  • У ConcurrentDictionary нет «пустого» состояния – массивы «вёдер» создаются сразу при создании словаря.
  • Для разрешения коллизий применяется метод цепочек, но в отличие от Dictionary цепочки хранятся не в общем массиве, а каждая в своём односвязном списке.
  • Размер массива «вёдер» здесь может быть составным числом, но не может делиться на 2, 3, 5 и 7. Каждое увеличение также происходит минимум в 2 раза.
  • Увеличения происходят, когда одна из цепочек становится слишком длинной по сравнению с количеством «вёдер».
  • Стратегия рандомизации хэшей строк при переполнении счётчика коллизий аналогична Dictionary<TKey, TValue>.
  • Перечислитель-класс написан через yield.

Следует использовать, если требуется словарь, который может одновременно редактироваться несколькими потоками. Часто такая необходимость возникает при ленивой инициализации некоторого кэша, которая может происходить при обработке web-запросов.

System.Collections.Concurrent.ConcurrentBag<T>

Потокобезопасный набор объектов, в котором не поддерживается никакой порядок. Вообще говоря, работает эффективнее List<T> с блокировками при вызовах методов, так как в этой коллекции блокировки разделяются между частями коллекции. Методы CopyTo, ToArray, перечисление элементов, свойства Count, IsEmpty обращаются сразу ко всем элементам и приводят к глобальной блокировке.

Операции:

Add добавление объекта в коллекцию O(1)
TryTake получение и удаление произвольного объекта из коллекции O(1)
TryPeek получение произвольного объекта из коллекции O(1)
Count подсчёт числа элементов O(кол-во потоков-писателей)

Особенности текущей реализации:

  • Каждый поток при добавлении объекта в коллекцию создаёт собственный двусвязный список объектов, которые в свою очередь хранятся в общем.
  • Поток добавляет объекты только в собственный список и по возможности получает и удаляет элементы из собственного списка, если собственный список пуст, тогда производится обращение к чужому непустому списку.
  • Если имеется непустой список завершённого потока, то он переиспользуется другим потоком.
  • При перечислении создаётся List<T>, в который копируется содержимое, и пробрасывается его перечислитель, завёрнутый в box-интерфейс.

Следует использовать, если коллекция объектов может наполняться и обрабатываться несколькими потоками.

System.Collections.Concurrent.ConcurrentQueue<T>

Потокобезопасная очередь на основе односвязного списка массивов, так называемого развёрнутого связного списка. Вообще говоря, работает эффективнее Queue<T> c блокировками, так как в этой коллекции блокировки разделяются, и удаление элемента из очереди практически всегда может происходить одновременно с добавлением.

Операции:

TryPeek получение элемента из головы очереди O(1)
TryDequeue получение+удаление элемента из головы очереди O(1)
Enqueue добавление элемента в хвост очереди O(1)
Count подсчёт числа элементов O(n)

Особенности текущей реализации:

  • Добавляемые в очередь объекты упаковываются в массивы длиной 32, в основной структуре хранятся ссылки на головной и хвостовой массивы.
  • Потокобезопасность удаления обеспечивается атомарными изменениями указателей на голову и хвост с помощью Interlocked.
  • Добавление элемента в массив находится в блоке finally и не может быть прервано, остальные потоки ждут окончания выполнения блока через System.Threading.SpinWait.
  • Перечислитель-класс написан с помощью yield.

Следует использовать, если нужна очередь, одновременно используемая несколькими потоками.

System.Collections.Concurrent.ConcurrentStack<T>

Потокобезопасный стек на основе односвязного списка. Вообще говоря, работает эффективнее Stack<T> c блокировками за счёт разделения блокировок между частями коллекции.

Предоставляет атомарные операции для добавления и снятия с вершины нескольких элементов PushRange и PopRange.

Операции:

TryPeek получение элемента из вершины стека O(1)
TryPop получение+удаление элемента из вершины стека O(1)
Push добавление элемента на вершину стека O(1)
Clear удаление всех элементов из стека O(1)
Count подсчёт числа элементов O(n)

Особенности текущей реализации:

  • Потокобезопасность обеспечивается атомарными изменениями указателей с помощью Interlocked и ожиданиями через SpinWait.
  • Перечислитель-класс написан с помощью yield.

Cледует использовать, если нужен стек, одновременно используемый несколькими потоками.

System.Collections.Concurrent.BlockingCollection<T>

Обёртка над объектом, реализующим интерфейс IProducerConsumerCollection<T>, при создании конструктором по умолчанию – ConcurrentQueue<T>. Позволяет осуществлять операции с таймаутами.

Иммутабельные коллекции из nuget-пакета System.Collections.Immutable (.NET 4.5)

Иммутабельные коллекции – коллекции, экземпляры которых нельзя изменить после создания. Пользователи такой коллекции могут полагаться на то, что их экземпляр никогда не изменится, при этом этот экземпляр может быть общим для многих пользователей, в том числе в разных потоках. Если требуется изменить такую коллекцию, то нужно создавать новый экземпляр – предоставляемые классами из System.Collections.Immutable изменяющие методы возвращают новую коллекцию. Большинство из предоставляемых стандартной библиотекой классов при этом переиспользует структуры исходной коллекции, стремясь минимизировать перерасход памяти.

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

System.Collections.Immutable.ImmutableArray<T>

struct-обёртка для массива, не имеющая методов, изменяющих исходный массив. Таким образом, коллекция представляет из себя массив, который нельзя изменить после создания. Перерасход памяти по сравнению с обычным массивом нулевой. Методы Add, AddRange, Insert, InsertRange, SetItem, Replace, Remove, RemoveRange, Clear, Sort возвращают новый экземпляр ImmutableArray. Для построения можно использовать ImmutableArray<T>.Builder.

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

Операции в исходной коллекции:

[] получение элемента по индексу O(1)
Contains проверка содержания элемента O(n)
IndexOf, LastIndexOf поиск элемента O(n)

Операции, возвращающие новую коллекцию с изменениями:

Add, Insert добавление элемента O(n)
Remove поиск и удаление элемента O(n)
RemoveAt удаление элемента по индексу O(n)
Replace поиск и замена элемента O(n)
SetItem замена элемента O(n)
Clear получение пустой коллекции O(1)
Sort сортировка O(n log n)

Особенности текущей реализации:

  • Различные перечислители для обычного метода GetEnumerator (struct) и для реализации IEnumerable<T>.GetEnumerator (класс).
  • Перечислитель-struct пробрасывает из массива IndexOutOfBoundsException при обращении к Current до вызова MoveNext или после завершения перечисления, не имеет Dispose.
  • Класс бросает InvalidOperationException при обращении к Current до вызова MoveNext или после завершения перечисления, на Dispose не реагирует.

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

System.Collections.Immutable.ImmutableList<T>

Иммутабельная упорядоченная коллекция объектов, реализованная с помощью бинарного дерева. Изменяющие методы вместо изменения текущей коллекции возвращают новую коллекцию, в которой возможны переиспользования частей старой. Публичного конструктора нет, пустой список создаётся с помощью ImmutableList<T>.Empty; для построения можно использовать ImmutableList<T>.Builder, который содержит ImmutableList<T> и скрывает присваивания после изменений.

Операции в исходной коллекции:

[] получение элемента по индексу O(log n)
Contains проверка содержания элемента O(n)
IndexOf, LastIndexOf поиск элемента O(n)

Операции, возвращающие новую коллекцию с изменениями:

Add, Insert добавление элемента O(log n)
Remove поиск и удаление элемента O(n)
RemoveAt удаление элемента по индексу O(log n)
Replace поиск и замена элемента O(n)
SetItem замена элемента O(log n)
Clear получение пустой коллекции O(1)
Sort сортировка O(n log n)
BinarySearch поиск в упорядоченной коллекции O(log n)
Reverse смена порядка элементов на противоположный O(n log n)

Особенности текущей реализации:

  • Метод балансировки дерева – АВЛ.
  • Перечислитель – struct, создаёт стек для обхода дерева в глубину, объекты стеков берутся из пула. Выбрасывает ObjectDisposedException при обращении к Current перед первым вызовом MoveNext или после Dispose, InvalidOperationException – при обращении к Current после завершения перечисления.

Стоит использовать, если нужна иммутабельная коллекция, у которой часто вызываются изменяющие методы.

System.Collections.Immutable.ImmutableStack<T>

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

Операции в исходной коллекции:

Peek получение элемента с вершины стека O(1)

Операции, возвращающие новую коллекцию с изменениями:

Push добавление элемента на вершину стека O(1)
Pop получение + удаление элемента с вершины стека O(1)
Clear получение пустого стека O(1)
Reverse обращение порядка элементов O(n)

Особенности текущей реализации:

  • Различные перечислители для обычного метода GetEnumerator (struct) и для реализации IEnumerable<T>.GetEnumerator (класс);
  • Struct бросает InvalidOperationException при обращении к Current до вызова MoveNext или после завершения перечисления, не имеет Dispose;
  • Класс бросает InvalidOperationException при обращении к Current до вызова MoveNext или после завершения перечисления, ObjectDisposedException – после Dispose;
  • Метод Reverse не может переиспользовать односвязный список и производит O(n) выделений памяти в куче.

System.Collections.Immutable.ImmutableQueue<T>

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

Операции в исходной коллекции:

Peek получение элемента из головы очереди O(1)

Операции, возвращающие новую коллекцию с изменениями:

Enqueue добавление элемента в хвост очереди O(1)
Dequeue получение + удаление элемента из хвоста очереди O(1)

Особенности текущей реализации:

  • Добавляемые в очередь элементы добавляются в один стек, удаляемые – получаются из другого; при этом при удалении возвращаемая очередь переворачивает стек для добавления и делает его стеком для удаления.
  • Различные перечислители для обычного метода GetEnumerator (struct) и для реализации IEnumerable<T>.GetEnumerator (класс).
  • struct бросает InvalidOperationException при обращении к Current до вызова MoveNext или после завершения перечисления, не имеет Dispose.
  • Класс бросает InvalidOperationException при обращении к Current до вызова MoveNext или после завершения перечисления, ObjectDisposedException – после Dispose.

System.Collections.Immutable.ImmutableDictionary<TKey, TValue>

Иммутабельная коллекция пар ключ-значение, реализованная с помощью хэш-таблицы, «вёдра» которой хранятся в бинарном дереве поиска, упорядоченном по хэшу.

Операции в исходной коллекции:

[], TryGetValue получение значения по ключу O(log n)
ContainsKey проверка наличия ключа O(log n)
ContainsValue проверка наличия значения O(n)

Операции, возвращающие новую коллекцию с изменениями:

Add добавление пары ключ-значение O(log n)
Remove удаление пары ключ-значение O(log n)
SetItem замена значения для ключа O(log n)
Clear получение пустой коллекции O(1)

Особенности текущей реализации:

  • Коллизии разрешаются с помощью метода цепочек, которые хранятся в виде пары из первого элемента и ImmutableList остальных элементов.
  • Предоставляет коллекции ключей и значений Keys, Values через yield.
  • Метод Add не выбрасывает исключение при повторном ключе, если добавляемое значение совпадает с имеющимся.
  • Перечислитель – struct, бросает исключение при обращении к Current до MoveNext, после Dispose или завершения перечисления.

System.Collections.Immutable.ImmutableSortedDictionary<TKey, TValue>

Иммутабельная коллекция пар ключ-значение, реализованная с помощью бинарного дерева поиска.

Операции в исходной коллекции:

[], TryGetValue получение значения по ключу O(log n)
ContainsKey проверка наличия ключа O(log n)
ContainsValue проверка наличия значения O(n)

Операции, возвращающие новую коллекцию с изменениями:

Add добавление пары ключ-значение O(log n)
Remove удаление пары ключ-значение O(log n)
SetItem замена значения для ключа O(log n)
Clear получение пустой коллекции O(1)

Особенности текущей реализации:

  • Перечислитель – struct, бросает исключение при обращении к Current до MoveNext, после Dispose или завершения перечисления.

System.Collections.Immutable.ImmutableHashSet<T>

Иммутабельное множество на основе хэш-таблицы, «вёдра» которой хранятся в бинарном дереве поиска, упорядоченном по хэшу.

Операции в исходной коллекции:

TryGetValue проверка наличия элемента O(log n)

Операции, возвращающие новую коллекцию с изменениями:

Add добавление элемента O(log n)
Remove удаление элемента O(log n)
Union объединение O(n log n)
Intersect пересечение O(n log n)
Except разность O(n log n)
Clear получение пустой коллекции O(1)

Особенности текущей реализации:

  • Коллизии разрешаются аналогично ImmutableDictionary, с помощью метода цепочек, которые хранятся в виде пары из первого элемента и ImmutableList остальных элементов.
  • Перечислитель – struct, бросает исключение при обращении к Current до MoveNext, после Dispose или завершения перечисления.

System.Collections.Immutable.ImmutableSortedSet<T>

Иммутабельное множество на основе бинарного дерева поиска.

Операции в исходной коллекции:

TryGetValue проверка наличия элемента O(log n)

Операции, возвращающие новую коллекцию с изменениями:

Add добавление элемента O(log n)
Remove удаление элемента O(log n)
Union объединение O(n log n)
Intersect пересечение O(n log n)
Except разность O(n log n)
Clear получение пустой коллекции O(1)

Особенности текущей реализации:

  • При объединении двух коллекций этого типа производится оптимизация – меньшая коллекция вливается в большую.
  • Перечислитель – struct, бросает исключение при обращении к Current до MoveNext, после Dispose или завершения перечисления.
  • Имеется быстрый метод Reverse, позволяющий обойти дерево справа налево, т.е. от больших элементов к меньшим.

Коллекции из .NET 1.0

System.Collections.Hashtable

Nongeneric-аналог Dictionary<TKey, TValue> – коллекция пар ключ-значение на основе хэш-таблицы. Cтандартный класс для словарей в PowerShell: конструкция

@{}

создаёт Hashtable с нечувствительным к регистру сравнителем строк.

Хэш и проверка на равенство по умолчанию осуществляются через object.GetHashCode и object.Equals, можно передать в конструктор свой экземпляр IEqualityComparer.

Операции:

[] получение значения по ключу O(1)
Contains, ContainsKey проверка наличия ключа O(1)
ContainsValue проверка наличия значения O(n)
[], Add добавление пары ключ-значение O(1) аморт.
Remove удаление пары ключ-значение O(1)
Clear удаление всех элементов O(n)

Особенности текущей реализации:

  • Метод разрешения коллизий отличается от Dictionary, в Hashtable используется открытая адресация с линейным сдвигом при коллизиях. Объекты хранятся прямо в массиве «вёдер».
  • Содержит конструктор с float-параметром с допустимыми значениями от 0.1 до 1, определяющим, при каком наполнении массива следует его увеличить. Переданный параметр, умноженный на 0.72, становится максимально допустимой плотностью элементов в массиве.
  • Логика увеличения размера массива такая же, как в Dictionary – последовательность простых чисел, каждое из которых как минимум в 2 раза больше предыдущего.

System.Collections.ArrayList

Nongeneric-аналог List<T> – динамический массив.

Особенности текущей реализации:

  • Полный аналог List<T> в стратегии изменения размера массива: при переполнении размер удваивается, никогда не уменьшается, если явно не вызвать TrimToSize.
  • Перечислитель – класс.

System.Collections.Queue

Nongeneric-аналог Queue<T> – очередь на основе динамического массива.
Особенности текущей реализации:

  • Полный аналог Queue<T> в стратегии изменения размера массива.
  • Перечислитель – класс.

System.Collections.Stack

Nongeneric-аналог Stack<T> – стек на основе динамического массива.
Особенности текущей реализации:

  • Полный аналог Stack<T> в стратегии изменения размера массива;
  • Перечислитель – класс.

System.Collections.SortedList

Nongeneric-аналог SortedList<TKey, TValue> – коллекция пар ключ-значение на основе упорядоченного динамического массива. При создании конструктором по умолчанию сравнивает ключи, приводя их к IComparable и вызывая CompareTo, при неудачном приведении двух сравниваемых ключей бросается исключение.
Особенности текущей реализации:

  • Полный аналог SortedList<TKey, TValue> в стратегии изменения размера массива;
  • По умолчанию размер массива при добавлении первого элемента – 16, а не 4;
  • Перечислитель – класс.

System.Collections.BitArray

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

Имеет свойство Length с сеттером для динамического изменения размера. Массовые побитовые операции изменяют исходную коллекцию и возвращают BitArray. Реализует только IEnumerable, но не IEnumerable<bool>, соответственно, любые методы LINQ для этой коллекции неэффективны.

Операции:

[] получение, установка значения O(1)
And, Or, Xor, Not логические операции над массивом O(n)

Особенности текущей реализации:

  • внутри содержит int[]
  • уменьшает размер внутреннего массива при изменении длины, только если старая длина int[] превосходит требуемую больше, чем на 256

Хранит значения эффективнее и работает быстрее bool[] при массовых булевых операциях.

Остальные классы из стандартной библиотеки

System.Collections.Specialized.ListDictionary

Реализация словаря на основе односвязного списка. Класс появился в .NET 1.0.

System.Collections.Specialized.HybridDictionary

Словарь-обёртка для ListDictionary и Hashtable. Переключается с первой реализации на вторую, когда число элементов превышает 9, или когда создаётся конструктором с начальным размером больше 5. Класс появился в .NET 1.0.

System.Collections.Specialized.OrderedDictionary

Обёртка над Hashtable и ArrayList. Поддерживает как выдачу элементов по ключу из Hashtable, так и по индексу в порядке добавления из ArrayList. Класс появился в .NET 2.0.

System.Collections.Specialized.StringDictionary

Nongeneric-вариант для Dictionary<string, string> – обёртка для Hashtable, скрывающая приведения типов. Класс появился в .NET 1.0.

System.Collections.Specialized.StringCollection

Nongeneric-вариант для List<string> – обёртка для ArrayList, скрывающая приведения типов. Класс появился в .NET 1.0.

System.Collections.Specialized.NameValueCollection

Nongeneric-вариант для Dictionary<string, List<string>>. Обёртка над Hashtable, скрывающая приведения типов и добавления в таблицу пустых списков значений. Наряду с обычными методами GetValues, возвращающими коллекцию значений по ключу, предоставляет методы Get, которые конкатенируют значения для ключа через запятую. При отсутствии ключа методы получения возвращают null вместо выбрасывания исключения. Часто встречается в интерфейсах стандартных библиотек – например, в ASP.NET MVC используется для AppSettings, строки запроса и заголовков HTTP. Класс появился в .NET 1.1.

System.Collections.Specialized.BitVector32

struct-обёртка над int-ом, позволяющая обращаться с ним как с массивом из 32 логических значений. Массовые побитовые операции не поддерживаются. Появилась в .NET 1.0.

System.Collections.ObjectModel.Collection<T>

Обёртка над объектом, реализующим IList<T> (при создании конструктором по умолчанию – List<T>). Все внутренние методы, меняющие коллекцию – виртуальные, что позволяет наследникам этого класса отслеживать изменения. Использование этого класса напрямую бессмысленно, следует непосредственно использовать List<T>. Класс появился в .NET 2.0.

System.Collections.ObjectModel.ObservableCollection<T>

Наследник Collection<T>, поднимающий событие CollectionChanged при изменении коллекции. Класс появился в .NET 3.0.

System.Collections.ObjectModel.ReadOnlyCollection<T>

Обёртка над объектом, реализующим IList<T>, не имеющая методов, изменяющих коллекцию. Может применяться для передачи коллекции, которую нельзя изменять, ненадёжному пользователю, например, пользователю библиотеки – для изменения такой коллекции злоумышленнику не обойтись приведением типов и придётся заняться рефлексией. Заметим, что сам внутренний объект может изменяться даже после того, как его обернули в ReadOnlyCollection<T>, и поэтому пользователь такой коллекции не может полагаться на её неизменность – это гарантируют только иммутабельные коллекции. Класс появился в .NET 2.0.

System.Collections.ObjectModel.ReadOnlyDictionary<TKey, TValue>

Обёртка над объектом, реализующим IDictionary<TKey, TValue>, не имеющая методов, изменяющих коллекцию. Также может применяться для некоторой гарантии неизменности коллекции в руках ненадёжных пользователей. Класс появился в .NET 4.5.

System.Collections.ObjectModel.ReadOnlyObservableCollection<T>

Наследник ReadOnlyCollection<T>, поднимающий событие CollectionChanged при изменении обёрнутой коллекции. Класс появился в .NET 3.0.

System.Collections.Generic.KeyedByTypeCollection<TItem>

Обёртка для Dictionary<System.Type, TItem> с generic-методами для получения, добавления и удаления объектов по ключу-типу. Класс появился в .NET 3.0.

System.Collections.Generic.SynchronizedReadOnlyCollection<T>

Коллекция, позволяющая в каждый момент читать объекты коллекции только одному потоку. Класс появился в .NET 3.0.

Некоторые коллекции, реализации которых отсутствуют в стандартной библиотеке

Мультимножество – коллекция, которая поддерживает множественные операции вроде объединения и пересечения, при этом отличая однократное добавление объекта от многократного. Как и обычное множество, может быть реализовано через хэш-таблицу или через бинарное дерево поиска, как реализация из стандартной библиотеки C++ std::multiset.

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

Развёрнутый список – связный список, в узлах которого хранятся массивы элементов, а не одиночные элементы. Использование такой структуры для коллекций с большим числом элементов позволяет с одной стороны, использовать кэш процессора – большинство соседних элементов хранятся рядом, а с другой, избавиться от недостатка больших List<T> – выделения огромных массивов, затрудняющих сборку мусора и фрагментирующих large object heap. В стандартной библиотеке есть класс на развёрнутом списке – ConcurrentQueue<T>, но этот класс заточен именно под потокобезопасную очередь и не предоставляет полного функционала, например, List<T>.

Deque – очередь с равноправными концами, в которые можно и добавлять, и удалять элементы, на основе динамического массива. Дек на основе связного списка нетрудно соорудить из LinkedList, а дек в стиле Java – на динамическом массиве – в стандартной библиотеке .NET отсутствует.

Trie – дерево, обеспечивающее быстрые операции со строками, например, позволяющее быстро отыскать для строки префикс среди заданных. Направленные рёбра этого дерева помечены подстроками, а каждой вершине сопоставляется строка, полученная конкатенацией подстрок на пути к ней от корня дерева.