共用方式為


集合和數據結構

當儲存和作為集合時,通常可以更有效率地處理類似的數據。 您可以使用 System.ArraySystem.CollectionsSystem.Collections.GenericSystem.Collections.Concurrent 命名空間中的 System.Collections.Immutable類別,來新增、移除和修改集合中的個別項目或項目範圍。

集合有兩種主要類型:泛型集合和非泛型集合。 泛型集合在編譯時期是型別安全的。 因此,一般集合通常會提供更好的效能。 泛型集合在建構時接受類型參數。 當您在集合中新增或移除項目時,不需要進行到 Object 類別的類型轉換。 此外,Windows 市集應用程式中支援大部分的泛型集合。 非泛型集合會將項目儲存為Object,需要進行類型轉換,而且大多數不支援 Windows Store 應用程式開發。 不過,您可能會在舊版程序代碼中看到非泛型集合。

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

常見的集合特性

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

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

  • 容量和計數屬性

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

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

    BitArray是特殊案例;其容量、長度及計數均相同。

  • 一致的下限

    集合的下界是其第一個元素的索引。 命名空間中的所有 System.Collections 索引集合都有零的下限,這表示其為0索引。 Array默認會有零的下限,但使用 建立Array.CreateInstance類別的實例時,可以定義不同的下限。

  • 多線程存取的同步(僅限於類別)。

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

選擇集合

一般而言,您應該使用泛型集合。 下表說明一些常見的集合案例,以及可用於這些案例的集合類別。 如果您不熟悉泛型集合,下表將協助您選擇最適合工作的泛型集合:

我想。。。 一般集合選項 非泛型集合選項 線程安全或不可變的集合選項
將專案儲存為索引鍵/值組,以便依索引鍵快速查閱 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>
使用資料後進先出First-Out(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>迴圈或for迴圈來有效率地列舉foreach。 不過,ImmutableList<T>for迴圈中,由於索引器的時間為O(log n),表現不佳。 列舉 ImmutableList<T> 使用 foreach 迴圈是有效率的,因為 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>
何時使用泛型集合 討論泛型集合類型的用法。
集合內的比較和排序 討論在集合中使用相等比較和排序比較。
已排序的集合類型 描述已排序的集合效能和特性。
哈希表和字典集合類型 描述泛型和非泛型哈希型字典類型的功能。
Thread-Safe 合集 描述集合類型,例如 System.Collections.Concurrent.BlockingCollection<T>System.Collections.Concurrent.ConcurrentBag<T>,這些類型支援從多個線程以安全且高效的方式並行存取。
System.Collections.Immutable 介紹不可變的集合,並提供集合類型的連結。

參考文獻