Структуры данных .NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - скорость, память и когда их использовать?

По возможности используйте дженерики. Сюда входят:

• Список вместо ArrayList
• Словарь вместо HashTable

Они довольно хорошо прописаны в intellisense. Просто введите System.Collections. или System.Collections.Generics (предпочтительно), и вы получите список и краткое описание того, что доступно.

Во-первых, все коллекции в .NET реализуют IEnumerable.

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

Итак, хотя общие коллекции, вероятно, добавляют функции, по большей части:

• Список - это общая реализация ArrayList.
• Словарь - это общая реализация Hashtable

Массивы - это коллекция фиксированного размера, в которой вы можете изменять значение, хранящееся в заданном индексе.

SortedDictionary - это IDictionary, который сортируется на основе ключей. SortedList - это IDictionary, который отсортирован на основе требуемого IComparer.

Итак, реализации IDictionary (поддерживающие KeyValuePairs): * Хеш-таблица * Словарь * SortedList * SortedDictionary

Еще одна коллекция, добавленная в .NET 3.5, - это Hashset. Это коллекция, которая поддерживает операции над наборами.

Кроме того, LinkedList - это стандартная реализация связанного списка (List - это список-массив для более быстрого поиска).

С верхней части моей головы:

• Array * - представляет собой массив памяти старой школы - своего рода псевдоним для обычного массива type[]. Могу перечислить. Не может расти автоматически. Я бы предположил очень быструю скорость вставки и возврата.

• ArrayList - автоматически растущий массив. Добавляет больше накладных расходов. Может enum., Вероятно, медленнее, чем обычный массив, но все же довольно быстро. Они часто используются в .NET.

• List - один из моих любимых - можно использовать с дженериками, поэтому у вас может быть строго типизированный массив, например List<string>. В остальном действует очень похоже на ArrayList.

• Hashtable - старая обычная хеш-таблица. От O (1) до O (n) в худшем случае. Может перечислять свойства значений и ключей, а также создавать пары ключ / значение

• Dictionary - то же, что и выше, только строго типизированный с помощью универсальных шаблонов, таких как Dictionary<string, string>

• SortedList - отсортированный общий список. Замедляется при вставке, так как он должен выяснить, куда положить вещи. Может enum., Вероятно, то же самое при извлечении, поскольку к нему не нужно прибегать, но удаление будет медленнее, чем простой старый список.

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

Есть также много других структур данных - есть KeyValuePair, который вы можете использовать для некоторых интересных вещей, есть SortedDictionary, который также может быть полезен.

Вот несколько общих советов:

• foreach можно использовать для типов, реализующих IEnumerable. IList - это, по сути, IEnumberable со свойствами Count и Item (доступ к элементам с использованием индекса, начинающегося с нуля). IDictionary, с другой стороны, означает, что вы можете получить доступ к элементам по любому хешируемому индексу.

• Array, ArrayList и List реализуют IList. Dictionary, SortedDictionary и Hashtable реализуют IDictionary.

• Если вы используете .NET 2.0 или выше, рекомендуется использовать общие аналоги упомянутых типов.

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

• Структуры данных .NET находятся в пространстве имен System.Collections. Существуют библиотеки типов, такие как PowerCollections, которые предлагают дополнительные структуры данных.

• Чтобы получить полное представление о структурах данных, обратитесь к таким ресурсам, как CLRS.

Хеш-таблицы / словари имеют производительность O (1), что означает, что производительность не зависит от размера. Это важно знать.

Обновлено: на практике средняя временная сложность для поиска Hashtable / Dictionary <> составляет O (1).

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

Универсальные коллекции будут работать лучше, чем их неуниверсальные аналоги, особенно при итерации по многим элементам. Это потому, что упаковки и распаковки больше не происходит.

Важное замечание о Hashtable vs Dictionary для высокочастотной систематической торговли: проблема безопасности потоков

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

Таким образом, Hashtable остается «стандартным» выбором в этом отношении.

Я сочувствую этому вопросу - я тоже нашел (нашел?) Выбор в недоумении, поэтому я решил с научной точки зрения посмотреть, какая структура данных самая быстрая (я проводил тест с использованием VB, но я полагаю, что C# будет одинаковым, поскольку оба языка сделайте то же самое на уровне CLR). Вы можете увидеть некоторые результаты тестирования, проведенного мной здесь (там также обсуждается, какой тип данных лучше всего использовать в каких обстоятельствах).

Самые популярные структуры и коллекции данных C#

• Множество
• ArrayList
• Список
• LinkedList
• Словарь
• HashSet
• Куча
• Очередь
• SortedList

C# .NET имеет множество различных структур данных, например, одна из самых распространенных - это массив. Однако C# имеет гораздо больше базовых структур данных. Выбор правильной структуры данных для использования - это часть написания хорошо структурированной и эффективной программы.

В этой статье я рассмотрю встроенные структуры данных C#, включая новые, представленные в C# .NET 3.5. Обратите внимание, что многие из этих структур данных применимы для других языков программирования.

Множество

Возможно, самая простая и распространенная структура данных - это массив. Массив C# - это в основном список объектов. Его отличительной чертой является то, что все объекты относятся к одному типу (в большинстве случаев) и их определенное количество. Природа массива обеспечивает очень быстрый доступ к элементам в зависимости от их положения в списке (также известном как индекс). Массив C# определяется следующим образом:

[object type][] myArray = new [object type][number of elements]

Некоторые примеры:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

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

ArrayList

Структура данных C# ArrayList - это динамический массив. Это означает, что ArrayList может содержать любое количество объектов и любого типа. Эта структура данных была разработана для упрощения процессов добавления новых элементов в массив. Под капотом ArrayList - это массив, размер которого удваивается каждый раз, когда в нем заканчивается место. Удвоение размера внутреннего массива - очень эффективная стратегия, которая в конечном итоге сокращает объем копирования элементов. Мы не будем здесь приводить доказательства этого. Структура данных очень проста в использовании:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

Обратной стороной структуры данных ArrayList является приведение извлеченных значений обратно к их исходному типу:

int arrayListValue = (int)myArrayList[0]

Источники и дополнительную информацию вы можете найти здесь:

• Структуры данных C#
• Коллекции и структуры данных
• Список против IEnumerable против IQueryable против ICollection против IDictionary
• System.Collections.Generic пространство имен
• System.Collections пространство имен

Я нашел раздел «Выбрать коллекцию» на странице документов Microsoft на странице «Коллекция и структура данных» действительно полезным.

Коллекции и структуры данных C#: выберите коллекцию

А также следующая матрица для сравнения некоторых других функций