集合和資料結構Collections and Data Structures

使用集合進行儲存與管理時,通常可以更有效率地處理類似的資料。Similar data can often be handled more efficiently when stored and manipulated as a collection. 您可以使用 System.Array 類別或 System.CollectionsSystem.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. 泛型集合已加入.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 Store 應用程式也支援大部分的泛型集合。In addition, most generic collections are supported in Windows Store apps. 非泛型集合會將專案儲存為 Object 、需要轉型,而且大部分都不支援 Windows 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 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> 如果小於,則 Count Capacity 新增專案為 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類別的實例時,可以定義不同的下限 Array.CreateInstanceArray 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.)
ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
依索引存取項目Access items by index List<T> Array

ArrayList
ImmutableList<T>

ImmutableArray
先進先出 (FIFO) 地使用項目Use items first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
後進先出 (LIFO) 地使用資料Use 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. (實作 INotifyPropertyChangedINotifyCollectionChanged)(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 ( nO(n) ImmutableStack<T>.Push O (1)O(1)
Queue<T>.Enqueue O (1)O(1) O ( nO(n) ImmutableQueue<T>.Enqueue O (1)O(1)
List<T>.Add O (1)O(1) O ( nO(n) ImmutableList<T>.Add O (log nO(log n)
List<T>.Item[Int32] O (1)O(1) O (1)O(1) ImmutableList<T>.Item[Int32] O (log nO(log n)
List<T>.Enumerator O ( nO(n) O ( nO(n) ImmutableList<T>.Enumerator O ( nO(n)
HashSet<T>.Add,lookupHashSet<T>.Add, lookup O (1)O(1) O ( nO(n) ImmutableHashSet<T>.Add O (log nO(log n)
SortedSet<T>.Add O (log nO(log n) O ( nO(n) ImmutableSortedSet<T>.Add O (log nO(log n)
Dictionary<T>.Add O (1)O(1) O ( nO(n) ImmutableDictionary<T>.Add O (log nO(log n)
Dictionary<T>反向Dictionary<T> lookup O (1)O(1) O (1)-或嚴格的 O ( nO(1) – or strictly O(n) ImmutableDictionary<T>反向ImmutableDictionary<T> lookup O (log nO(log n)
SortedDictionary<T>.Add O (log nO(log n) O ( n log nO(n log n) ImmutableSortedDictionary<T>.Add O (log nO(log n)

List<T>可以使用 for 迴圈或迴圈來有效率地列舉 foreachA 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.

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 和 Dictionary 集合類型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.

參考Reference

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