Какие структуры данных используются в .NET

Я собрал некоторую информацию о временной сложности и о базовых структурах данных лежащих в основе простых коллекций и словарей в .NET. Было сложно найти эту информацию как в официальных источниках, таких как MSDN так и на не официальных источниках, так как информация отличалась, поэтому я использовал Reflector и фактически использовал реализацию классов для подтверждения информации.

Простые коллекции

Тип	Структура данных	Пояснение
List<T>	Массив	Обычный список использующий динамический массив
SortedSet<T>	Красно-черное дерево	Список использующий красно-черное дерево

Временная сложность

Тип	Получить i - элемент	Поиск	Добавление в конец	Вставка	Удаление
List<T>	O(1)	O(n)	O(1)*	O(n)	O(n)
SortedSet<T>	Не доступно	O(log n)	O(log n)	O(log n)	O(log n)

* Сложность метода List.Add является линейной O(n) когда добавление элемента требует увеличение размера массива лежащего в основе списка.

Словари

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

Тип	Структура данных	Пояснение
HashSet<T>	Хеш таблица	Хеш таблица ключом которой является сам объект
Dictionary<TKey, TValue>	Хеш таблица	Хеш таблица у которой ключ не обязательно является хранящимся объектом
SortedList<TKey, TValue>	Массив	Тоже самое, что и Dictionary за исключением того, что элементы и их ключи хранятся в отсортированных массивах
SortedDictionary<TKey, TValue>	Красно-черное дерево	Тоже самое, что и Dictionary за исключением того, что элементы и их ключи хранятся в красно-черных деревьях. Внутри себя использует SortedSet

Временная сложность

Тип	Поиск по ключу	Удаление элемента	Добавление элемента
HashSet	O(1)*	O(1)*	O(1)**
Dictionary	O(1)*	O(1)*	O(1)**
SortedList	O(log n)	O(n)	O(n)
SortedDictionary	O(log n)	O(log n)	O(log n)

* O(n) с коллизиями
** O(n) с коллизиями или когда добавление элемента требует увеличение размера массива лежащего в основе.

SortedList против SortedDictionary

SortedList и SortedDictionary лучше всего подходят когда вам необходимо хранить элементы в отсортированном порядке. Вот сравнение этих классов от Microsoft:

SortedList<TKey, TValue> - обобщенный класс состоящий из массивов пар ключ/значение c временной сложностью поиска равной O(logn), где n - количество элементов в словаре. В этом он похож на обобщенный класс SortedDictionary<TKey, TValue> . Эти два класса имеют похожую объектную модель, и сложность поиска у обоих равна O(logn). Однако эти классы различаются в количестве используемой памяти и скорости вставки и удаления элементов:

• SortedList<TKey, TValue> использует меньше памяти чем SortedDictionary<TKey, TValue>;
• SortedDictionary<TKey, TValue> выполняет быстрее операции удаления и вставки для не отсортированных данных, O(logn) против O(n) для SortedList<TKey, TValue>;
• Если список состоит из отсортированных данных то SortedList<TKey, TValue> быстрее чем SortedDictionary<TKey, TValue>.

Другое отличие между классами SortedList<TKey, TValue> и SortedDictionary<TKey, TValue> заключается в том, что класс SortedList<TKey, TValue> обеспечивает эффективное индексирование ключей и значений возвращенных через свойства Keys и Values. Открытых свойств не достаточно для изменения списков, так как они являются просто обертками для внутренних массивов ключей и значений.