閱讀英文

共用方式為


集合和資料結構

使用集合進行儲存與管理時,通常可以更有效率地處理類似的資料。 您可以使用 System.Array 類別或 System.CollectionsSystem.Collections.GenericSystem.Collections.ConcurrentSystem.Collections.Immutable 命名空間中的類別,新增、移除和修改個別元素,或集合中的元素範圍。

有兩種主要的集合類型;泛型集合和非泛型集合。 泛型集合在編譯時間具有型別安全。 因此,泛型集合通常會有較佳的效能。 泛型集合在建構時便接受型別參數。 從集合新增或移除項目時,它們不需要往返 Object 型別轉換。 此外,大部分的泛型集合都可在 Windows 市集應用程式中支援。 非泛型集合會將項目儲存為 Object,而這需要進行轉型,且 Windows 市集應用程式開發也不支援大多數的項目。 但您可能會在較舊的程式碼中看到非泛型集合。

在 .NET Framework 4 和更新版本中,System.Collections.Concurrent 命名空間中的集合提供了有效率的安全執行緒作業,可從多個執行緒存取集合項目。 System.Collections.Immutable 命名空間 (NuGet 封裝) 中不可變的集合類別,原本就是安全執行緒,因為作業會執行於原始集合的複本上,且不能修改原始集合。

常見集合功能

所有集合都提供加入、移除或尋找集合中項目的方法。 此外,直接或間接實作 ICollection 介面或 ICollection<T> 介面的所有集合,都可共用這些功能:

此外,許多集合類別包含下列功能:

  • 容量和計數屬性

    集合的容量是它可以包含的元素數目。 集合的計數是它實際包含的元素數目。 某些集合會隱藏容量或計數,或同時隱藏兩者。

    達到目前的容量時,大多數集合會自動擴大容量。 將會重新配置記憶體,並從舊集合將元素複製到新的集合。 此設計會減少使用集合所需的程式碼。 不過,集合的效能可能會受負面影響。 例如,針對 List<T>,如果 Count 小於 Capacity,則新增項目的作業為 O(1)。 如果需要增加容量以容納新的元素,則新增元素的作業會變成 O(n),其中 nCount。 避免多次重新配置造成的效能不佳之最佳方式,是將初始容量設定為集合的預估大小。

    BitArray 是特殊的情況;它的容量等同於長度,計數也是。

  • 一致的下限

    集合的下限是其第一個元素的索引。 System.Collections 命名空間中的所有索引集合下限皆為零,表示它們為 0 索引。 根據預設,Array 下限為零,但使用 Array.CreateInstance 建立 Array 類別的執行個體時,可以定義其他下限。

  • 從多個執行緒存取的同步處理 (僅限 System.Collections 類別)。

    System.Collections 命名空間中的非泛型集合型別,提供一些同步處理的執行緒安全性;通常會透過 SyncRootIsSynchronized 成員公開。 這些集合預設不是安全執行緒。 如果您需要可調整且有效地以多執行緒存取集合,請使用 System.Collections.Concurrent 命名空間中的其中一個類別,或考慮使用不可變的集合。 如需詳細資訊,請參閱安全執行緒集合

選擇集合

一般情況下,您應該使用泛型集合。 下表說明一些常見的集合案例,以及您可以為這些案例使用的集合類別。 如果您是泛型集合的新使用者,下列表格可協助您選擇最適合您工作的泛型集合:

我想要… 泛型集合的選項 非泛型集合的選項 安全執行緒或固定集合的選項
儲存項目為成對的索引鍵/值,以供依據索引鍵快速查詢 Dictionary<TKey,TValue> Hashtable

(成對的機碼/值之集合,依據機碼的雜湊碼加以組織)。
ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

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

ArrayList
ImmutableList<T>

ImmutableArray
先進先出 (FIFO) 地使用項目 Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
後進先出 (LIFO) 地使用資料 Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
循序存取項目 LinkedList<T> 不推薦 不推薦
當集合中有項目移除或加入時,收到通知。 (實作 INotifyPropertyChangedINotifyCollectionChanged) ObservableCollection<T> 不推薦 不推薦
排序的集合 SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
數學函式的集合 HashSet<T>

SortedSet<T>
不推薦 ImmutableHashSet<T>

ImmutableSortedSet<T>

集合的演算法複雜度

選擇集合類別時,值得考量效能的潛在取捨。 使用下表來參考就演算法複雜度到其對應的不可變對應項目方面,如何比較各種可變的集合型別。 不可變的集合型別通常效能較低,但提供不變性,這通常是有效的相對優點。

可變動 分攤 最差情況 固定 複雜度
Stack<T>.Push O(1) O(n) ImmutableStack<T>.Push O(1)
Queue<T>.Enqueue O(1) O(n) ImmutableQueue<T>.Enqueue O(1)
List<T>.Add O(1) O(n) ImmutableList<T>.Add O(log n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(log n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.Add, lookup O(1) O(n) ImmutableHashSet<T>.Add O(log n)
SortedSet<T>.Add O(log n) O(n) ImmutableSortedSet<T>.Add O(log n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(log n)
Dictionary<T> lookup O(1) O(1) - 或嚴格 O(n) ImmutableDictionary<T> lookup O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

List<T> 可以使用 for 迴圈或 foreach 迴圈有效率地列舉。 不過,由於其索引子的 O(log n) 時間,ImmutableList<T>for 迴圈內執行作業不佳。 使用 foreach 迴圈列舉 ImmutableList<T> 會有效率,因為 ImmutableList<T> 使用二進位樹狀結構來儲存其資料,而不是像 List<T> 使用的陣列。 可以對陣列快速編製索引,而二進位樹狀結構必須逐步執行,直到找到具有所需索引的節點為止。

此外,SortedSet<T> 具有與 ImmutableSortedSet<T> 相同的複雜度,因為它們都使用二進位樹狀結構。 顯著差異在於 ImmutableSortedSet<T> 使用不可變的二進位樹狀結構。 由於 ImmutableSortedSet<T> 也提供允許變異的 System.Collections.Immutable.ImmutableSortedSet<T>.Builder 類別,因此您可以同時擁有不變性和效能。

標題 描述
選取集合類別 說明不同的集合,並協助您選取用於您案例的集合。
常用的集合類型 描述常用的泛型與非泛型集合型別,例如 System.ArraySystem.Collections.Generic.List<T>System.Collections.Generic.Dictionary<TKey,TValue>
何時使用泛型集合 說明泛型集合類型的用法。
在集合內比較和排序 討論在集合中使用相等比較和排序比較。
排序集合類型 描述經過排序之集合的效能與特性。
Hashtable 和 Dictionary 集合類型 說明泛型和非泛型雜湊字典類型的功能。
安全執行緒集合 說明如 System.Collections.Concurrent.BlockingCollection<T>System.Collections.Concurrent.ConcurrentBag<T> 這類集合類型,這類類型支援從多個執行緒進行安全有效率的並行存取。
System.Collections.Immutable 介紹不可變的集合並提供集合類型的連結。

參考