概述

數組和Array類。數組的大小是固定的。如果元素個數是動態的，就應該使用集合類。
List和ArrayList是與數組相當的集合類。還有其他類型的集合：隊列、棧、鏈表和字典。
集合：

• 集合接口和類型
• 列表
• 隊列
• 棧
• 鏈表
• 有序表
• 字典
• Lookup
• HashSet
• 位數組
• 性能

集合接口和類型

集合類可以組合為集合，存儲 Object 類型的元素和泛型集合類。在 CLR 2.0 之前，不存在泛型。現在泛型集合類通常是集合的首選類型。泛型集合類是類型安全的，如果使用值類型，是不需要裝箱操作的。如果要在集合中添加不同類型的對象，且這些對象不是相互派生的，例如在集合中添加 int和 string 對象，就只需基于對象的集合類。另一組集合類是專用于特定類型的集合，例如
StringCollection 類專用于 string 類型。

列表(ArrayList, List)

.NET Framework 為動態列表提供了類 ArrayList 和 List。System.Collections.Generic 命名空間中的類 List的用法非常類似于System.Collections 命名空間中的 ArrayList 類。這個類實現了 IList、ICollection 和 IEnumerable 接口。

• 調用默認的構造函數，就可以創建列表對象。在泛型類 List中，必須在聲明中為列表的值指定類型。下面的代碼說明了如何聲明一個包含 int 的 List和一個包含 Racer 元素的列表。ArrayList是一個非泛型列表，可以將任意 Object 類型作為其元素。
• 使用默認的構造函數創建一個空列表。元素添加到列表中后，列表的容量就會擴大為可接納 4 個元素。如果添加了第 5 個元素，列表的大小就重新設置為包含 8 個元素。如果 8 個元素還不夠，列表的大小就重新設置為 16。每次都會將列表的容量重新設置為原來的 2 倍。

ArrayList objectList = new ArrayList();
List<int> intList = new List<int>();
List<Racer> racers = new List<Racer>();

創建了一個容量為 10 個元素的集合。如果該容量不足以容納要添加的元素，就把集合的大小重新設置為 20，或 40，每次都是原來的 2 倍。

ArrayList objectList = new ArrayList(10);
List<int> intList = new List<int>(10);

使用Capacity屬性可以獲取和設置集合的容量：

objectList.Capacity = 20;
intList.Capactity = 20;

容量與集合中的個數不同。集合中元素個數可以用Count屬性讀取。當然，容量總是大于元素個數。只要不把元素添加到列表中，元素個數就是 0。

Console.WriteLine(intList.Count); // 輸出元素個數

如果已經將元素添加到列表中，且不希望添加更多的元素，就可以調用TrimExcess()方法，去除不需要的容量。但是，重新定位是需要時間的，所以如果元素個數超過了容量的 90%，TrimExcess()方法將什么也不做。

intList.TrimExcess(); // 去除不需要的容量。

ArrayList arrayList = new ArrayList();
arrayList.Add(1);
arrayList.Add(2);
arrayList.Add("Hello");
arrayList.Add(3);
arrayList.Add(4);
arrayList.Add("World");
arrayList.Add(5);// TODO:變量數組列表 
Debug.WriteLine("遍歷數組列表："); 
foreach (var item in arrayList)
{ Debug.WriteLine(item);
}Debug.WriteLine("下標訪問數組列表：");
Debug.WriteLine(arrayList[0]);
Debug.WriteLine(arrayList[1]);
Debug.WriteLine(arrayList[2]);
Debug.WriteLine(arrayList[3]);
Debug.WriteLine(arrayList[4]);arrayList.Remove(3);    // 移除元素3            
arrayList.RemoveAt(3);  // 移除第3個元素
Debug.WriteLine("移除元素3，移除第3個元素");
foreach (var item in arrayList)
{Debug.WriteLine(item);
}arrayList.AddRange(new int[] { 10, 11, 12, 13, 14, 15 });
arrayList.RemoveRange(3, 2);int[] ints = new int[] { 34, 54, 43, 21, 66 };
arrayList.InsertRange(2, ints); // 第2個位置插入數組
foreach (var item in arrayList)
{Debug.WriteLine(item);
}//arrayList.Sort();       // 排序
//arrayList.Reverse();    // 反序foreach (var item in arrayList)
{Debug.WriteLine(item);
}//arrayList.Clear();  // 清空
//arrayList.Capacity = 10;
//Debug.WriteLine(arrayList.Count);

隊列(Queue)

隊列是其元素以先進先出(FIFO)的方式來處理的集合。先放在隊列中的元素會先讀取。隊列的例子有在機場排的隊、人力資源部中等待處理求職信的隊列、打印隊列中等待處理的打印任務、以循環方式等待 CPU 處理的線程。另外，還常常有元素根據其優先級來處理的隊列。例如，在機場的隊列中，商務艙乘客的處理要優先于經濟艙的乘客。這里可以使用多個隊列，一個隊列對應一個優先級。在機場，這是很常見的，因為商務艙乘客和經濟艙乘客有不同的登記隊列。打印隊列和線程也是這樣。可以為一組隊列建立一個數組，數組中的一項代表一個優先級。在每個數組項中，都有一個隊列，其處理按照 FIFO 的方式進行。

Queue<string> queueStr = new Queue<string>();
Queue<int> queueInt = new Queue<int>(10);queueStr.Enqueue("Hi");
queueStr.Enqueue("Hello");
queueStr.Enqueue("World");
Debug.WriteLine(queueStr.Peek());
Debug.WriteLine(queueStr.Dequeue());
Debug.WriteLine(queueStr.First());
Debug.WriteLine(queueStr.Last());             
queueStr.Clear();queueInt.Enqueue(12);
queueInt.Enqueue(23);
queueInt.Enqueue(25);
queueInt.Enqueue(65);
foreach (var item in queueInt)
{Debug.WriteLine(item);
}for (int i = 0; i < queueInt.Count; i++)
{Debug.WriteLine(queueInt.Dequeue());                
}Debug.WriteLine(queueInt.Count);

棧(Statck)

棧是與隊列非常類似的另一個容器，只是要使用不同的方法訪問棧。最后添加到棧中的元素會最先讀取。棧是一個后進先出(LIFO)容器。

 Stack<char> alphabet = new Stack<char>();alphabet.Push('A');alphabet.Push('B');alphabet.Push('C');            foreach (char c in alphabet){Debug.Write(c+",");}Debug.WriteLine(alphabet.Pop());foreach (char c in alphabet){Debug.Write(c + ",");}

鏈表(LinkedList)

• LinkedList 集合類沒有非泛型集合的類似版本。LinkedList 是一個雙向鏈表，其元素指向它前面和后面的元素。
• 鏈表的優點是，如果將元素插入列表的中間位置，使用鏈表會非常快。在插入一個元素時，只需修改上一個元素的 Next 引用和下一個元素的 Previous 引用，使它們引用所插入的元素。在 List 和ArrayList 類中，插入一個元素，需要移動該元素后面的所有元素。
• 當然，鏈表也有缺點。鏈表的元素只能一個接一個地訪問，這需要較長的時間來查找位于鏈表中間或尾部的元素。
• 鏈表不僅能在列表中存儲元素，還可以給每個元素存儲下一個元素和上一個元素的信息。這就是LinkedList 包含 LinkedListNode 類型的元素的原因。使用 LinkedListNode 類，可以獲得列表中的下一個元素和上一個元素。表 10-5 描述了 LinkedListNode 的屬性。
  

 LinkedList<string> linkedList = new LinkedList<string>();linkedList.AddLast("Apple");linkedList.AddLast("Huawei");linkedList.AddFirst("Xiaomi");linkedList.AddLast("Huawei");foreach (var item in linkedList){Debug.WriteLine(item);}var node = linkedList.Find("Apple");        // 查找元素linkedList.AddAfter(node, "Apple After");   // 在指定節點后添加元素linkedList.AddBefore(node, "Apple Before"); // 在指定節點前添加元素foreach (var item in linkedList){Debug.WriteLine(item);}Debug.WriteLine(linkedList.ElementAt(0));   // 訪問第0個元素Debug.WriteLine(linkedList.ElementAt(3));   // 訪問第3個元素

有序表(SortedList)

• 如果需要排好序的表，可以使用 SortedList<TKey, TValue>。這個類按照鍵給元素排序。
  
  

SortedList<string, int> sortedList = new SortedList<string, int>();
sortedList.Add("one", 111);
sortedList.Add("two", 222);
sortedList.Add("three", 333);
sortedList.Add("four", 444);
sortedList.Add("five", 555);
foreach (KeyValuePair<string, int> kvp in sortedList)
{Debug.WriteLine($"key:{kvp.Key}, value:{ kvp.Value}");
}// 通過key獲取值
int value_one = sortedList["one"];// 通過索引獲取Key
int value = sortedList.Values[2];
string key_two = sortedList.Keys[2];Debug.WriteLine(value_one);
Debug.WriteLine(key_two);sortedList.Remove("one");   //  刪除鍵值對

字典

• 字典表示一種非常復雜的數據結構，這種數據結構允許按照某個鍵來訪問元素。字典也稱為映射或散列表。字典的主要特性是能根據鍵快速查找值。也可以自由添加和刪除元素，這有點像 List，但沒有在內存中移動后續元素的性能開銷。
• 鍵的類型：用作字典中鍵的類型必須重寫 Object 類的 GetHashCode()方法。只要字典類需要確定元素的位置，就要調用 GetHashCode()方法。GetHashCode()方法返回的 int 由字典用于計算放置元素的索引。這里不介紹這個算法。我們只需知道，它涉及到素數，所以字典的容量是一個素數。

GetHashCode()方法的實現代碼必須滿足如下要求：
● 相同的對象應總是返回相同的值。
● 不同的對象可以返回相同的值。
● 應執行得比較快，計算的開銷不大。
● 不能拋出異常。
● 應至少使用一個實例字段。
● 散列碼值應平均分布在 int 可以存儲的整個數字區域上。
● 散列碼最好在對象的生存期中不發生變化。
提示：
字典的性能取決于 GetHashCode()方法的實現代碼。

Lookup類

Dictionary<TKey, TValue>只為每個鍵支持一個值。新類 Lookup<TKey, TElement>是.NET 3.5 中新增的，它類似于 Dictionary<TKey, TValue>，但把鍵映射到一個值集上。這個類在程序集 System.Core中實現，用 System.Linq 命名空間定義。

其他字典類

Dictionary<TKey, TValue>是 Framework 中的一個主要字典類，還有其他一些類，當然也有一些非泛型的字典類。

HashSet(不重復項的無序列表)

.NET 3.5 在 System.Collections.Generic 命名空間中包含一個新的集合類：HashSet。這個集合類包含不重復項的無序列表。這種集合稱為"集(set)"。集是一個保留字，所以該類有另一個名稱HashSet。這個名稱很容易理解，因為這個集合基于散列值，插入元素的操作非常快，不需要像List類那樣重排集合。

位數組

BitArray

• 如果需要處理許多位，就可以使用類 BitArray 和結構 BitVector32。BitArray 位于命名空間System.Collections，BitVector32 位于命名空間 System.Collections.Specialized。這兩種類型最重要的區別是，BitArray 可以重新設置大小，如果事先不知道需要的位數，就可以使用 BitArray，它可以包含非常多的位。BitVector32 是基于棧的，因此比較快。BitVector32 僅包含 32位，存儲在一個整數中。

• 類 BitArray 是一個引用類型，包含一個 int 數組，每 32 位使用一個新整數。
  

BitVector32

如果事先知道需要的位數，就可以使用 BitVector32 結構替代 BitArray。BitVector32 效率較高，因為它是一個值類型，在整數棧上存儲位。一個整數可以存儲 32 位。如果需要更多的位，就可以使用多個 BitVector32 值或 BitArray。BitArray 可以根據需要增大，但 BitVector32 不能。

性能

許多集合類都提供了相同的功能，例如，SortedList 與 SortedDictionary 的功能幾乎完全相同。但是，其性能常常有很大區別。一個集合使用的內存少，另一個集合的元素檢索速度快。在 MSDN 文檔中，集合的方法常常有性能提示，給出了以大 O 記號表示的操作時間：

• O(1):表示無論集合中有多少數據項，這個操作需要的時間都不變。
• O(n):表示對于集合中的每個元素，需要增加的時間量都是相同的。
• O(log n):表示操作需要的時間隨集合中元素的增加而增加，但每個元素需要增加的時間不是線性的，而是呈對數曲線。