集合和数据结构Collections and Data Structures

类似的数据在作为集合而存储和操作时通常可以得到更高效地处理。Similar data can often be handled more efficiently when stored and manipulated as a collection. 可以使用 System.Array 类或 System.CollectionsSystem.Collections.GenericSystem.Collections.ConcurrentSystem.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. 泛型集合被添加在 .NET Framework 2.0 中,并提供编译时类型安全的集合。Generic collections were added in the .NET Framework 2.0 and provide collections that 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. 此外,Windows 应用商店应用支持大多数泛型集合。In addition, most generic collections are supported in Windows Store apps. 非泛型集合将项存储为 Object,需要强制转换,并且大多数不支持 Windows 应用商店应用开发。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 the .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:

此外,许多集合类包含下列功能: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. 例如,对 List<T> 来说,如果 CountCapacity 少,那么添加项就是一项 O(1) 操作。For example, for List<T>, if Count is less than Capacity, adding an item is an O(1) operation. 如需增加容量以容纳新元素,则添加项成为 O(n) 操作,其中 nCountIf 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 命名空间中的所有索引集合的下限均为零,这表示它们从 0 开始建立索引。All indexed collections in the System.Collections namespaces have a lower bound of zero, meaning they are 0-indexed. Array 默认下限为零,但使用 Array.CreateInstance 创建 Array 类的实例时可定义其他下限 。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 命名空间中的非泛型集合类型通过同步提供一些线程安全性;通常通过 SyncRootIsSynchronized 成员公开。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.)


按索引访问项Access items by index List<T> Array


使用项先进先出 (FIFO)Use items first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

使用数据后进先出 (LIFO)Use data Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

按顺序访问项Access items sequentially LinkedList<T> 无建议No recommendation 无建议No recommendation
删除集合中的项或向集合添加项时接收通知。Receive notifications when items are removed or added to the collection. (实现 INotifyPropertyChangedINotifyCollectionChanged(implements INotifyPropertyChanged and INotifyCollectionChanged) ObservableCollection<T> 无建议No recommendation 无建议No recommendation
已排序的集合A sorted collection SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

数学函数的一个集A set for mathematical functions HashSet<T>

无建议No recommendation ImmutableHashSet<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, lookupHashSet<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> lookupDictionary<T> lookup O(1)O(1) O(1) - 或者从严格意义上说,O(n)O(1) – or strictly O(n) ImmutableDictionary<T> lookupImmutableDictionary<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)

可以使用 for 循环或 foreach 循环来有效地枚举 List<T>A List<T> can be efficiently enumerated using either a for loop or a foreach loop. 但是,由于其索引器的 O(log n) 时间,ImmutableList<T>for 循环内的效果较差。An ImmutableList<T>, however, does a poor job inside a for loop, due to the O(log n) time for its indexer. 使用 foreach 循环枚举 ImmutableList<T> 很有效,因为 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.

TitleTitle 描述Description
选择集合类Selecting a Collection Class 描述不同的集合并帮助你为你的方案选择一个集合。Describes the different collections and helps you select one for your scenario.
常用的集合类型Commonly Used Collection Types 描述诸如 System.ArraySystem.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 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.


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