Коллекции и структуры данныхCollections and Data Structures

Связанные данные могут обрабатываться более эффективно, если они объединены в коллекцию.Similar data can often be handled more efficiently when stored and manipulated as a collection. Для добавления, удаления и изменения отдельных элементов или диапазона элементов коллекции можно использовать класс System.Array или классы в пространствах имен System.Collections, System.Collections.Generic, System.Collections.Concurrent и System.Collections.Immutable.You can use the System.Array class or the classes in the System.Collections, System.Collections.Generic, System.Collections.Concurrent, and System.Collections.Immutable namespaces to add, remove, and modify either individual elements or a range of elements in a collection.

Существует два основных типа коллекций — универсальные и неуниверсальные коллекции.There are two main types of collections; generic collections and non-generic collections. Универсальные коллекции являются строго типизированными во время компиляции.Generic collections are type-safe at compile time. Таким образом, универсальные коллекции обычно обеспечивают более высокую производительность.Because of this, generic collections typically offer better performance. Универсальные коллекции принимают параметр типа во время создания и не требуют приведение в тип Object и из него при добавлении или удалении элементов.Generic collections accept a type parameter when they are constructed and do not require that you cast to and from the Object type when you add or remove items from the collection. Кроме того, большая часть универсальных коллекций поддерживается в приложениях Microsoft Store.In addition, most generic collections are supported in Windows Store apps. Неуниверсальные коллекции хранят такие элементы, как Object, требуют приведения. Большая их часть не поддерживается для разработки приложений Microsoft Store.Non-generic collections store items as Object, require casting, and most are not supported for Windows Store app development. Однако неуниверсальные коллекции можно наблюдать в старом коде.However, you may see non-generic collections in older code.

Начиная с .NET Framework 4, коллекции пространства имен System.Collections.Concurrent предоставляют эффективные потокобезопасные операции для доступа к элементам коллекции из нескольких потоков.Starting with .NET Framework 4, the collections in the System.Collections.Concurrent namespace provide efficient thread-safe operations for accessing collection items from multiple threads. Неизменяемые классы коллекций в пространстве имен System.Collections.Immutable (пакет NuGet) являются потокобезопасными, так как операции выполняются с копией исходной коллекции, а исходная коллекция неизменяемая.The immutable collection classes in the System.Collections.Immutable namespace (NuGet package) are inherently thread-safe because operations are performed on a copy of the original collection and the original collection cannot be modified.

Общие возможности коллекцийCommon collection features

Все коллекции предоставляют методы для добавления, удаления или поиска элементов в коллекции.All collections provide methods for adding, removing, or finding items in the collection. Кроме того, все коллекции прямо или косвенно реализуют интерфейс ICollection или интерфейс ICollection<T> с совместным использованием следующих функций.In addition, all collections that directly or indirectly implement the ICollection interface or the ICollection<T> interface share these features:

  • Возможность перечисления коллекцииThe ability to enumerate the collection

    Чтобы обеспечить итерацию по коллекции, коллекции .NET реализуют System.Collections.IEnumerable или System.Collections.Generic.IEnumerable<T>..NET collections either implement System.Collections.IEnumerable or System.Collections.Generic.IEnumerable<T> to enable the collection to be iterated through. Перечислитель может рассматриваться как перемещаемый указатель на любой элемент в коллекции.An enumerator can be thought of as a movable pointer to any element in the collection. Оператор foreach, in и For Each...Next Statement использует итератор, предоставляемый методом GetEnumerator, и скрывает сложность работы с итератором.The foreach, in statement and the For Each...Next Statement use the enumerator exposed by the GetEnumerator method and hide the complexity of manipulating the enumerator. Кроме того, любая коллекция, реализующая System.Collections.Generic.IEnumerable<T>, считается запрашиваемым типом, и к ней можно создавать запросы LINQ.In addition, any collection that implements System.Collections.Generic.IEnumerable<T> is considered a queryable type and can be queried with LINQ. Запросы LINQ предоставляют общий шаблон для доступа к данным.LINQ queries provide a common pattern for accessing data. Обычно они являются более четкими и удобочитаемыми, чем стандартные циклы foreach, и предлагают возможности фильтрации, упорядочения и группировки.They are typically more concise and readable than standard foreach loops, and provide filtering, ordering and grouping capabilities. LINQ запросы также могут повысить производительность.LINQ queries can also improve performance. Дополнительные сведения см. в разделах LINQ to Objects (C#), LINQ to Objects (Visual Basic), Parallel LINQ (PLINQ), Введение в запросы LINQ (C#) и Базовые операции с запросами (Visual Basic).For more information, see LINQ to Objects (C#), LINQ to Objects (Visual Basic), Parallel LINQ (PLINQ), Introduction to LINQ Queries (C#), and Basic Query Operations (Visual Basic).

  • Возможность копирования содержимого коллекции в массивThe ability to copy the collection contents to an array

    Все коллекции могут быть скопированы в массив с помощью метода CopyTo. Однако порядок элементов в новом массиве зависит от того, в какой последовательности их возвращает перечислитель.All collections can be copied to an array using the CopyTo method; however, the order of the elements in the new array is based on the sequence in which the enumerator returns them. Результирующий массив всегда является одномерным массивом с нижней границей, равной нулю.The resulting array is always one-dimensional with a lower bound of zero.

Кроме того, во многих классах коллекций реализованы следующие возможности.In addition, many collection classes contain the following features:

  • Свойства "Емкость и количество элементов"Capacity and Count properties

    Емкость коллекции — это число элементов, которое она может содержать.The capacity of a collection is the number of elements it can contain. Количество элементов коллекции — это число элементов, которое она реально содержит.The count of a collection is the number of elements it actually contains. В некоторых коллекциях емкость или количество элементов скрыты.Some collections hide the capacity or the count or both.

    Большинство коллекции автоматически увеличивают емкость, если количество элементов достигает предела.Most collections automatically expand in capacity when the current capacity is reached. Происходит перераспределение памяти, и элементы копируются из старой коллекции в новую.The memory is reallocated, and the elements are copied from the old collection to the new one. Это уменьшает объем кода, необходимого для использования коллекции. Однако производительность при работе с такой коллекцией может ухудшиться.This reduces the code required to use the collection; however, the performance of the collection might be negatively affected. Например, если Count меньше Capacity, для List<T> добавление элемента является операцией O(1).For example, for List<T>, if Count is less than Capacity, adding an item is an O(1) operation. Если емкость нужно увеличить для размещения нового элемента, добавление элемента становится операцией O(n), где n — это Count.If the capacity needs to be increased to accommodate the new element, adding an item becomes an O(n) operation, where n is Count. Наилучший способ избежать потерь производительности, вызванных множественными перераспределениями, — это установить начальную вместимость, равную предполагаемому размеру коллекции.The best way to avoid poor performance caused by multiple reallocations is to set the initial capacity to be the estimated size of the collection.

    BitArray является особым случаем; его емкость совпадает с его длиной, которая совпадает с количеством элементов.A BitArray is a special case; its capacity is the same as its length, which is the same as its count.

  • Согласованная нижняя границаA consistent lower bound

    Нижняя граница коллекции — это индекс ее первого элемента.The lower bound of a collection is the index of its first element. Все индексированные коллекции в пространствах имен System.Collections имеют нижнюю границу, равную нулю.All indexed collections in the System.Collections namespaces have a lower bound of zero, meaning they are 0-indexed. Класс Array по умолчанию имеет нижнюю границу, равную нулю, но при создании экземпляра класса Array с помощью Array.CreateInstance может быть задана другая нижняя граница.Array has a lower bound of zero by default, but a different lower bound can be defined when creating an instance of the Array class using Array.CreateInstance.

  • Синхронизация для доступа из нескольких потоков (только классы System.Collections).Synchronization for access from multiple threads (System.Collections classes only).

    Для типов неуниверсальных коллекций в пространстве имен System.Collections синхронизация обеспечивает определенную степень потокобезопасности. Обычно для выполнения синхронизации используются члены SyncRoot и IsSynchronized.Non-generic collection types in the System.Collections namespace provide some thread safety with synchronization; typically exposed through the SyncRoot and IsSynchronized members. Эти коллекции не являются потокобезопасными по умолчанию.These collections are not thread-safe by default. Если требуется масштабируемый и эффективный многопотоковый доступ к коллекции, используйте один из классов в пространстве имен System.Collections.Concurrent или рассмотрите возможность использования неизменяемой коллекции.If you require scalable and efficient multi-threaded access to a collection, use one of the classes in the System.Collections.Concurrent namespace or consider using an immutable collection. Дополнительные сведения см. в разделе Потокобезопасные коллекции.For more information, see Thread-Safe Collections.

Выбор коллекцииChoose a collection

Как правило, следует использовать универсальные коллекции.In general, you should use generic collections. В следующей таблице описаны некоторые основные сценарии использования коллекций и классы коллекций, которые можно использовать для этих сценариев.The following table describes some common collection scenarios and the collection classes you can use for those scenarios. Если вы не работали с универсальными коллекциями, сведения в этой таблице помогут выбрать универсальную коллекцию, лучше всего подходящую для решения ваших задач.If you are new to generic collections, this table will help you choose the generic collection that works the best for your task.

ДействиеI want to… Возможности универсальной коллекцииGeneric collection options Возможности неуниверсальной коллекцииNon-generic collection options Возможности потокобезопасной или неизменяемой коллекцииThread-safe or immutable collection options
Хранение элементов в виде пар "ключ-значение" для быстрого поиска по ключуStore items as key/value pairs for quick look-up by key Dictionary<TKey,TValue> Hashtable

(Коллекция пар "ключ-значение", которые упорядочены по хэш-коду ключа.)(A collection of key/value pairs that are organized based on the hash code of the key.)
ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Доступ к элементам по индексуAccess items by index List<T> Array

ArrayList
ImmutableList<T>

ImmutableArray
Использование элементов по принципу FIFOUse items first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Использование данных по принципу LIFOUse data Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Последовательный доступ к элементамAccess items sequentially LinkedList<T> Рекомендации отсутствуютNo recommendation Рекомендации отсутствуютNo recommendation
Получение уведомлений при удалении элементов из коллекции или добавлении элементов в коллекцию.Receive notifications when items are removed or added to the collection. (реализует INotifyPropertyChanged и INotifyCollectionChanged)(implements INotifyPropertyChanged and INotifyCollectionChanged) ObservableCollection<T> Рекомендации отсутствуютNo recommendation Рекомендации отсутствуютNo recommendation
Отсортированная коллекцияA sorted collection SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Набор для математических функцийA set for mathematical functions HashSet<T>

SortedSet<T>
Рекомендации отсутствуютNo recommendation ImmutableHashSet<T>

ImmutableSortedSet<T>

Алгоритмическая сложность коллекцийAlgorithmic complexity of collections

При выборе класса коллекции нужно учитывать возможное влияние на производительность.When choosing a collection class, it is worth considering potential tradeoffs in performance. В следующей таблице сравнивается алгоритмическая сложность разных изменяемых типов коллекций и их соответствующих неизменяемых аналогов.Use the following table to reference how various mutable collection types compare in algorithmic complexity to their corresponding immutable counterparts. Как правило, последние являются менее производительными, но их неизменяемость часто является преимуществом.Often immutable collection types are less performant but provide immutability - which is often a valid comparative benefit.

ИзменяемыйMutable Амортизационный анализAmortized Худший случайWorst Case НеизменяемыеImmutable СложностьComplexity
Stack<T>.Push O(1)O(1) O(n)O(n) ImmutableStack<T>.Push O(1)O(1)
Queue<T>.Enqueue O(1)O(1) O(n)O(n) ImmutableQueue<T>.Enqueue O(1)O(1)
List<T>.Add O(1)O(1) O(n)O(n) ImmutableList<T>.Add O(log n)O(log n)
List<T>.Item[Int32] O(1)O(1) O(1)O(1) ImmutableList<T>.Item[Int32] O(log n)O(log n)
List<T>.Enumerator O(n)O(n) O(n)O(n) ImmutableList<T>.Enumerator O(n)O(n)
HashSet<T>.Add, поискHashSet<T>.Add, lookup O(1)O(1) O(n)O(n) ImmutableHashSet<T>.Add O(log n)O(log n)
SortedSet<T>.Add O(log n)O(log n) O(n)O(n) ImmutableSortedSet<T>.Add O(log n)O(log n)
Dictionary<T>.Add O(1)O(1) O(n)O(n) ImmutableDictionary<T>.Add O(log n)O(log n)
Dictionary<T>, поискDictionary<T> lookup O(1)O(1) O(1) — или строго O(n)O(1) – or strictly O(n) ImmutableDictionary<T>, поискImmutableDictionary<T> lookup O(log n)O(log n)
SortedDictionary<T>.Add O(log n)O(log n) O(n log n)O(n log n) ImmutableSortedDictionary<T>.Add O(log n)O(log n)

List<T> можно эффективно перечислить с помощью цикла for или foreach.A List<T> can be efficiently enumerated using either a for loop or a foreach loop. Но в случае с ImmutableList<T> использовать цикл for неэффективно, так как время для индексатора составляет O(log n).An ImmutableList<T>, however, does a poor job inside a for loop, due to the O(log n) time for its indexer. Перечисление ImmutableList<T> с помощью цикла foreach является эффективным, так как ImmutableList<T> использует двоичное дерево для хранения своих данных вместо простого массива, который использует List<T>.Enumerating an ImmutableList<T> using a foreach loop is efficient because ImmutableList<T> uses a binary tree to store its data instead of a simple array like List<T> uses. Массив можно быстро проиндексировать, тогда как двоичное дерево обрабатывается до тех пор, пока не будет найден узел с нужным индексом.An array can be very quickly indexed into, whereas a binary tree must be walked down until the node with the desired index is found.

Кроме того, SortedSet<T> имеет ту же сложность, что и ImmutableSortedSet<T>.Additionally, SortedSet<T> has the same complexity as ImmutableSortedSet<T>. Это обусловлено тем, что в обоих случаях используются двоичные деревья.That's because they both use binary trees. Существенная разница заключается в том, что ImmutableSortedSet<T> использует неизменяемое двоичное дерево.The significant difference, of course, is that ImmutableSortedSet<T> uses an immutable binary tree. Так как ImmutableSortedSet<T> также предлагает класс System.Collections.Immutable.ImmutableSortedSet<T>.Builder, который допускает изменения, обеспечивается как неизменяемость, так и производительность.Since ImmutableSortedSet<T> also offers a System.Collections.Immutable.ImmutableSortedSet<T>.Builder class that allows mutation, you can have both immutability and performance.

ЗаголовокTitle ОписаниеDescription
Выбор класса коллекцииSelecting a Collection Class Описывает различные коллекций и содержит сведения по выбору коллекции, соответствующей сценарию пользователя.Describes the different collections and helps you select one for your scenario.
Часто используемые типы коллекцийCommonly Used Collection Types Описывает часто используемые типы универсальных и неуниверсальных коллекций, таких как System.Array, System.Collections.Generic.List<T> и System.Collections.Generic.Dictionary<TKey,TValue>.Describes commonly used generic and nongeneric collection types such as System.Array, System.Collections.Generic.List<T>, and System.Collections.Generic.Dictionary<TKey,TValue>.
Когда следует использовать универсальные коллекцииWhen to Use Generic Collections Рассматривает использование типов универсальных коллекций.Discusses the use of generic collection types.
Сравнение и сортировка в коллекцияхComparisons and Sorts Within Collections Описывает использование проверок равенства и сортировки в коллекциях.Discusses the use of equality comparisons and sorting comparisons in collections.
Отсортированные типы коллекцийSorted Collection Types Описывает производительность и характеристики отсортированных коллекций.Describes sorted collections performance and characteristics
Типы коллекций Hashtable и DictionaryHashtable and Dictionary Collection Types Описывает возможности универсальных и неуниверсальных типов словарей на основе хэша.Describes the features of generic and non-generic hash-based dictionary types.
Потокобезопасные коллекцииThread-Safe Collections Описывает типы коллекций, такие как System.Collections.Concurrent.BlockingCollection<T> и System.Collections.Concurrent.ConcurrentBag<T>, поддерживающие безопасный и эффективный одновременный доступ из нескольких потоков.Describes collection types such as System.Collections.Concurrent.BlockingCollection<T> and System.Collections.Concurrent.ConcurrentBag<T> that support safe and efficient concurrent access from multiple threads.
System.Collections.ImmutableSystem.Collections.Immutable Приводятся вводные сведения о неизменяемых коллекциях и ссылки на типы коллекций.Introduces the immutable collections and provides links to the collection types.

СправочникReference

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable