集合和資料結構

  • 發行項

使用集合進行儲存與管理時，通常可以更有效率地處理類似的資料。 您可以使用 System.Array 類別或 System.Collections、System.Collections.Generic、System.Collections.Concurrent 和 System.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)，其中 n 是 Count。 避免多次重新配置造成的效能不佳之最佳方式，是將初始容量設定為集合的預估大小。

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

  • 一致的下限

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

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

    System.Collections 命名空間中的非泛型集合型別，提供一些同步處理的執行緒安全性；通常會透過 SyncRoot 和 IsSynchronized 成員公開。 這些集合預設不是安全執行緒。 如果您需要可調整且有效地以多執行緒存取集合，請使用 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> 不推薦 不推薦
當集合中有項目移除或加入時，收到通知。 (實作 INotifyPropertyChanged 和 INotifyCollectionChanged) 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.Array、System.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 介紹不可變的集合並提供集合類型的連結。

參考