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

. NET имеет много сложных структур данных. К сожалению, некоторые из них очень похожи, и я не всегда уверен, когда использовать один, а когда использовать другой. Большинство моих книг по C # и Visual Basic в некоторой степени говорят о них, но они никогда не вдавались в подробности.

В чем разница между Array, ArrayList, List, Hashtable, Dictionary, SortedList и SortedDictionary?

Какие из них перечислимы (IList - может делать циклы 'foreach')? Какие из них используют пары ключ / значение (IDict)?

А как насчет памяти? Скорость вставки? Скорость поиска?

Существуют ли другие структуры данных, о которых стоит упомянуть?

Я все еще ищу дополнительную информацию об использовании памяти и скорости (обозначение Big-O).

вопрос задан 24.09.2008
Pretzel
3887 репутация

14 ответов


  • 137 рейтинг

    С макушки головы:

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

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

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

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

    • Dictionary - то же самое, что и выше, только строго типизировано через дженерики, например Dictionary

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

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

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

    ответ дан Sam Schutte, с репутацией 4210, 24.09.2008
  • 25 рейтинг

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

    • Список вместо ArrayList
    • Словарь вместо HashTable
    ответ дан Adam Tegen, с репутацией 13556, 24.09.2008
  • 19 рейтинг

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

    Во-вторых, многие коллекции являются дубликатами, потому что дженерики были добавлены в версии 2. 0 рамок.

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

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

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

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

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

    Еще одна коллекция, которая была добавлена ​​в. NET 3. 5 - это хэшсет. Это коллекция, которая поддерживает операции над множествами.

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

    ответ дан Abe Heidebrecht, с репутацией 25645, 24.09.2008
  • 17 рейтинг

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

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

    • Array, ArrayList и List - все орудия IList. Dictionary, SortedDictionary и Hashtable реализуют IDictionary.

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

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

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

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

    ответ дан blackwing, с репутацией 2164, 24.09.2008
  • 16 рейтинг

    Хорошая шпаргалка , в которой упоминаются сложности для структур данных, алгоритмов и т. Д.

    ответ дан Krishna, с репутацией 1042, 17.06.2013
  • 5 рейтинг

    . NET структуры данных:

    Еще к разговору о том, почему ArrayList и List на самом деле разные

    Массивы

    Как утверждает один пользователь, массивы являются коллекцией «старой школы» (да, массивы считаются коллекцией, хотя и не являются частью System.Collections). Но что такое «старая школа» о массивах по сравнению с другими коллекциями, т.е. те, которые вы перечислили в своем заголовке (здесь ArrayList и List (Of T))? Давайте начнем с основ, посмотрев на массивы.

    Для начала Массивы в Microsoft. NET - это «механизмы, которые позволяют вам рассматривать несколько [логически связанных] элементов как одну коллекцию» (см. Связанную статью). Что это значит? Массивы хранят отдельные элементы (элементы) последовательно, один за другим в памяти с начальным адресом. Используя массив, мы можем легко получить доступ к последовательно сохраненным элементам, начиная с этого адреса.

    Помимо этого и вопреки программированию 101 общая концепция, массивы действительно могут быть довольно сложными:

    Массивы могут быть одномерными, многомерными или с зазубринами (о зубчатых массивах стоит прочитать). Сами массивы не являются динамическими: после инициализации массив размером n резервирует достаточно места для хранения n количества объектов. Количество элементов в массиве не может увеличиваться или уменьшаться. Dim _array As Int32() = New Int32(100) резервирует достаточно места в блоке памяти для массива, чтобы он содержал 100 объектов примитивного типа Int32 (в этом случае массив инициализируется, чтобы содержать 0 с). Адрес этого блока возвращается к _array.

    Согласно статье, Спецификация общего языка (CLS) требует, чтобы все массивы основывались на нулях. Массивы в. NET поддерживает ненулевые массивы; однако, это менее распространено. В результате "общности" массивов с нулями Microsoft потратила много времени на оптимизацию их производительности ; следовательно, одномерные массивы, основанные на нулях (SZ), являются «особыми» - и действительно лучшая реализация массива (в отличие от многомерных и т. д.). ) - потому что у СЗ есть специальные инструкции на промежуточном языке для их манипулирования.

    Массивы всегда передаются по ссылке (как адрес памяти) - важная часть головоломки Массив, которую нужно знать. Хотя они выполняют проверку границ (выдаст ошибку), проверка границ также может быть отключена для массивов.

    Опять же, самым большим препятствием для массивов является то, что они не могут быть изменены. Они имеют «фиксированную» емкость. Представляем ArrayList и List (Of T) в нашей истории:

    ArrayList - неуниверсальный список

    ArrayList (наряду с List(Of T) - хотя здесь есть некоторые критические различия, объясненные позже) - возможно, лучше всего рассматривать как следующее дополнение к коллекциям (в широком смысле). ArrayList наследуется от интерфейса IList (потомок ICollection). ArrayLists сами по себе являются на более громоздкими, чем - что требует дополнительных служебных данных - чем списки.

    IList действительно позволяет реализации обрабатывать списки массивов как списки фиксированного размера (например, массивы); однако, помимо дополнительной функциональности, добавленной ArrayLists, нет никаких реальных преимуществ использования ArrayLists фиксированного размера, поскольку ArrayLists (по сравнению с Arrays) в этом случае заметно медленнее.

    Из моего чтения ArrayLists не может быть зубчатым: «Использование многомерных массивов в качестве элементов. , , не поддерживается". Снова еще один гвоздь в гроб ArrayLists. Списки ArrayList также не являются «типизированными» - это означает, что ArrayList, под всем, представляет собой просто динамический массив объектов: Object[]. Это требует много коробок (неявных) и распаковок (явных) при реализации ArrayLists, что снова увеличивает их накладные расходы.

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

    Список (Of T): каким ArrayList стал (и надеялся)

    Разница в использовании памяти достаточно значительна для того, чтобы List (Of Int32) занимал на 56% меньше памяти, чем ArrayList, содержащий тот же тип примитива (8 МБ против 19 МБ в приведенной выше демонстрации, связанной с джентльменом: опять же, связано , здесь ) - хотя это результат, составленный 64-битной машиной. Это различие действительно демонстрирует две вещи: во-первых (1) «объект» в виде типа Int32 (ArrayList) в штучной упаковке намного больше, чем чистый тип примитива Int32 (List); во-вторых (2), разница является экспоненциальной в результате внутренней работы 64-битной машины.

    Итак, в чем разница и что такое список (T) ? MSDN определяет List(Of T) как ". , , строго типизированный список объектов, к которым можно получить доступ по индексу. «Здесь важен бит« строго типизированный »: List (Of T)« распознает »типы и сохраняет объекты как их типы. Таким образом, Int32 хранится как Int32, а не как Object. Это устраняет проблемы, вызванные боксом и распаковкой.

    MSDN указывает, что это различие вступает в действие только при хранении примитивных типов, а не ссылочных типов. Кроме того, разница действительно возникает в больших масштабах: более 500 элементов. Более интересно то, что документация MSDN гласит: «В ваших интересах использовать реализацию класса List (Of T) для конкретного типа вместо использования класса ArrayList. , , , "

    По сути, List (Of T) является ArrayList, но лучше. Это «универсальный эквивалент» ArrayList. Как и ArrayList, сортировка не гарантируется, пока не будет отсортирована (см. Рисунок). Список (Of T) также имеет некоторые дополнительные функции.

    ответ дан Thomas, с репутацией 1852, 13.10.2014
  • 5 рейтинг

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

    ответ дан Andy Brown, с репутацией 2604, 11.11.2011
  • 3 рейтинг

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

    ответ дан Russ Cam, с репутацией 100305, 28.09.2008
  • 3 рейтинг

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

    РЕДАКТИРОВАТЬ: На практике средняя сложность времени для Hashtable / Dictionary & lt; & gt; поиски O (1).

    ответ дан Chris, с репутацией 2094, 24.09.2008
  • 3 рейтинг

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

    ответ дан Joel Coehoorn, с репутацией 299287, 24.09.2008
  • 2 рейтинг

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

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

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

    ответ дан Rob, с репутацией 94, 27.08.2011
  • 2 рейтинг

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

    ответ дан Scott, с репутацией 106, 24.09.2008
  • 1 рейтинг

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

    ответ дан Ilya Ryzhenkov, с репутацией 9170, 24.09.2008
  • 0 рейтинг

    Наиболее популярные структуры данных и коллекции данных 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]
    

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

    ответ дан leonidaa, с репутацией 30, 9.05.2018