集合和資料結構

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

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

從 .NET Framework 4 開始,命名空間中的 System.Collections.Concurrent 集合提供有效率的執行緒安全作業,以便從多個執行緒存取集合專案。 命名空間中的 System.Collections.Immutable 不可變集合類別 (NuGet封裝) 原本就安全線程,因為作業是在原創組合的複本上執行,而且無法修改原創組合。

常見集合功能

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

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

  • 容量和計數屬性

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

    達到目前的容量時,大多數集合會自動擴大容量。 將會重新配置記憶體,並從舊集合將元素複製到新的集合。 這樣可以減少使用集合所需的程式碼;不過,可能會對集合效能產生負面的影響。 例如,如果 List<T> 小於 CapacityCount 則加入專案是 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 (記錄 n)
List<T>.Item[Int32] O (1) O (1) ImmutableList<T>.Item[Int32] O (記錄 n)
List<T>.Enumerator O (n) O (n) ImmutableList<T>.Enumerator O (n)
HashSet<T>.Add查找 O (1) O (n) ImmutableHashSet<T>.Add O (記錄 n)
SortedSet<T>.Add O (記錄 n) O (n) ImmutableSortedSet<T>.Add O (記錄 n)
Dictionary<T>.Add O (1) O (n) ImmutableDictionary<T>.Add O (記錄 n)
Dictionary<T> 查找 O (1) O (1) – 或嚴格 O () n ImmutableDictionary<T> 查找 O (記錄 n)
SortedDictionary<T>.Add O (記錄 n) O (n 記錄 n) ImmutableSortedDictionary<T>.Add O (記錄 n)

List<T>可以使用迴圈或 foreach 迴圈有效率地 for 列舉 。 不過,由於 ImmutableList<T> 索引子的 O (記錄 n) 時間,所以在迴圈內 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 介紹不可變的集合並提供集合類型的連結。

參考

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