當前位置：首頁 > 编程语言 > C# >内容正文

C#

C#集合通论

發(fā)布時間：2025/3/15 C# 20 豆豆

生活随笔收集整理的這篇文章主要介紹了 C#集合通论小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

前言

　　寫這篇文章的最初動力是來自于一次筆試經(jīng)歷。有一道筆試題大概是這樣的：程序使用一個txt文件來存儲操作記錄。存儲記錄是多行字符串，每一行代表一次操作記錄，格式如下：用戶名+操作事項名稱+操作時間。現(xiàn)在假設這個txt文件已經(jīng)非常大了，要求對這個文件做一些處理（具體記不太清了，接近于一些邏輯處理和增刪改）。毫無疑問，對于txt文件來說，要對之中的數(shù)據(jù)進行處理，首先要把數(shù)據(jù)讀入內(nèi)存，這就涉及到選擇何種數(shù)據(jù)結構的問題了。基于自己的常規(guī)思維，我不加思索就選擇了自定義類的List泛型存儲數(shù)據(jù)。之后再與面試官交流的時候，他給出了用Dictionary泛型的解決方案。由于自己的認知局限，當時沒聽明白面試官的具體解釋，導致這道問題的討論就成了單方面的闡述，失去了雙方的交流。面試也是發(fā)現(xiàn)問題的一種途徑。對于集合知識，自身確實存在認知匱乏的問題，而在許多程序中，選擇合適的數(shù)據(jù)結構往往是決定整個算法或代碼是否簡潔優(yōu)雅的關鍵所在，如果對集合都不熟悉的話，那么談何選擇合適的數(shù)據(jù)結構呢？如果你也存在和我一樣的問題，可以嘗試著繼續(xù)讀這篇文章，或許能給你帶來幫助。

　　這篇文章討論的主題是集合，重點在于分析集合的區(qū)別和聯(lián)系，加深對集合的認知與使用，熟悉常用C#類庫有關集合類的組織結構。

數(shù)組

　　論集合，不得不談的第一項就是數(shù)組。C#數(shù)組需要聲明元素類型，元素類型可以是值類型也可以是引用類型，數(shù)組是靜態(tài)類型，初始化必須指定個數(shù)大小，且創(chuàng)建后的數(shù)組是連續(xù)存放在內(nèi)存中的。聲明方式如下所示：

int[] intArray = new int[10]; 　　　　 //整型數(shù)組 string[] stringArray = new string[10]; //字符串數(shù)組 Random[] randArray = new Random[10]; //類數(shù)組

　　數(shù)組是從Array隱式派生的，這是由編譯器完成的，Array類被組織在System命名空間下。

Array myArray1 = new int[10]; Array myArray2 = new string[10]; Array myArray3 = new Random[10];

?數(shù)組是引用類型，初始化后分配在堆上。

System.Collections

　　1. System.Collections 組織空間

? ? ??

?集合類型根據(jù)自身的需求實現(xiàn)了左邊接口中的一個或多個，按照實現(xiàn)接口大概可以分為三種：有序集合（ICollection），索引集合（IList），鍵式集合（IDictionary）。

　　2. 通用接口

public interface IEnumerator {bool MoveNext();object Current { get; }void Reset(); }public interface IEnumerable { IEnumerator GetEnumerator(); }public interface ICollection : IEnumerable {int Count { get; }bool IsSynchronized { get; }object SyncRoot { get; }void CopyTo(Array array, int index); }public interface IList : ICollection, IEnumerable {bool IsFixedSize { get; }bool IsReadOnly { get; }object this[int index] { get; set; }int Add(object value);void Clear();bool Contains(object value);int IndexOf(object value);void Insert(int index, object value);void Remove(object value);void RemoveAt(int index); }public interface IDictionary : ICollection, IEnumerable {bool IsFixedSize { get; }bool IsReadOnly { get; }object this[object key] { get; set; }ICollection Keys { get; }ICollection Values { get; }void Add(object key, object value);void Clear();bool Contains(object key);IDictionaryEnumerator GetEnumerator();void Remove(object key); } Collections常用接口實現(xiàn)

?　　集合類型都實現(xiàn)了IEnumerable接口，從而可以使用foreach迭代。

　　實現(xiàn)了ICollectoin接口的集合類表明集合中的元素是有先后順序的。

　　 IList接口繼承了ICollection接口，實現(xiàn)了IList接口的集合類不止表明集合中的元素是有先后順序，而且表明集合類可以通過下標訪問的方式訪問集合元素。

　　 IDictionary接口也繼承了ICollection接口，實現(xiàn)了IDicionary接口的集合類可以通過下標key訪問的訪問方式訪問集合元素。

　　3. ArrayList

　　Array是靜態(tài)分配的，意味著創(chuàng)建數(shù)組后的大小不能改變，然而實際應用中，我們很多時候無法在一開始確定數(shù)組的大小，這樣便需要一種能動態(tài)分配的數(shù)組類型，ArrayList就是為此而生的。ArrayList主要實現(xiàn)的接口有IList，所以這是一個索引集合。

//聲明ArrayList ArrayList myArray = new ArrayList();//插入元素可以為值類型也可以為引用類型 myArray.Add(1); myArray.Add("hello"); myArray.Add(new Random());int i = (int)myArray[0]; string str = (string)myArray[1]; Random rand = (Random)myArray[2];

　　使用Reflector查看ArrayList的底層實現(xiàn)，可以看到動態(tài)數(shù)組其實是由一個object[] _items維系著的，這就解釋了為什么集合的元素可以為值類型也可以為引用類型。這樣的底層實現(xiàn)貌似靈活性很高，集合可以容納異構類型，然而卻帶來了性能上的問題，因為當插入值類型的時候，就存在隱式裝箱操作，而當把元素還原為值類型變量的時候，又發(fā)生了一次顯式拆箱操作，如果這種裝箱拆箱存在上千萬次，那么程序的性能是要大打折扣的。同時要注意一點的是object類型可以強制轉化為任何類型，這是說編譯器不會檢查object強制轉換的類型，如果無法轉換的話，這必須等到運行時才能確定出錯，這就是類型安全問題。

　　所以應該盡量避免使用ArrayList。

　　4. Stack 和 Queue

　　對于棧和隊列這兩種經(jīng)典的數(shù)據(jù)結構，C#也將它們組織在System.Collections命名空間中。Stack是后進先出的結構，Queue是先進先出的結構，這兩者主要實現(xiàn)的接口有ICollection，表示它們都是有序集合，應注意到這兩者都不可以使用下標訪問集合元素。這兩者的底層實現(xiàn)都是由一個object[] _array維系著，都存在著裝箱拆箱的性能問題和類型安全問題，所以應該盡量避免直接使用它們。

　　5. HashTable

?　 ?前面我們提到的集合類都屬于單元素集合類，實際應用中我們需要一種鍵值對的形式存儲數(shù)據(jù)，即集合類中存儲的不再是單個元素，而是key-value兩個元素，HashTable就是為此而生的。HashTable實現(xiàn)了IDictionary接口。

//創(chuàng)建一個HashTable實例 Hashtable hashDict = new Hashtable();//往容器中加入key-value hashDict.Add("a", "hello"); hashDict.Add("b", "hello"); hashDict.Add("c", "go"); hashDict.Add(4, 300);//通過下標key獲取value string str1 = hashDict["a"].ToString(); string str2 = (string)hashDict["b"]; int i4 = (int)hashDict[4];

?　　HashTable中的key關鍵字必須唯一，不能重復。如果深入到HashTable的底層實現(xiàn)，應該可以清楚的看到key和value是結構體bucket數(shù)組維護著，bucket中key和value的實現(xiàn)也是object，所以存在著與ArrayList，Stack，Queue同樣的問題，應該盡量避免使用HashTable。

?為什么鍵值集合類要命名為HashTable？

? ? ?從HashTable的命名來看，我們可以斷定說鍵值集合跟Hash必定存在某種聯(lián)系。哈希又稱為散列，散列技術是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使得每個關鍵字key對應一個存儲位置f（key），f又稱為散列函數(shù)。HashTable實現(xiàn)了IDictionary接口，表明HashTable可以通過下標key訪問的方式獲取數(shù)組元素，即 ? ? HashTable[key]，這與實現(xiàn)了IList接口的集合類的數(shù)字下標訪問存在著明顯的不同。那么如何通過key快速定位得到value呢？我相信通過前面的鋪墊大伙都知道是什么回事了，對，就是哈希函數(shù)的運用。具體可以參考文章http://www.cnblogs.com/abatei/archive/2009/06/23/1509790.html。

　　6. SortedList

　　在控制臺應用程序下運行以下代碼并觀察結果：

Hashtable hashDict = new Hashtable(); hashDict.Add("key1", "1"); hashDict.Add("key2", "2"); hashDict.Add("key3", "3"); hashDict.Add("key4", "4");foreach (string key in hashDict.Keys) {Console.WriteLine(hashDict[key]); }

? ? ? 我們可以看到這里并沒有按照預期的Key順序輸出Value。也就是說HashTable是不按照key順序排序的，具體原理可以參考HashTable的源碼。SortedList很好地解決了鍵值集合順序輸出的問題。

//創(chuàng)建一個SortedList實例 SortedList sortList = new SortedList();//往容器中加入元素 sortList.Add("key1", 1); sortList.Add("key2", 2); sortList.Add("key3", 3); sortList.Add("key4", 4);//獲取按照key排序的第index個Key string str1 = sortList.GetKey(0).ToString(); Console.WriteLine(str1); //獲取按照key排序的第index個Value int i1 = (int)sortList.GetByIndex(0); Console.WriteLine(i1.ToString()); //下標key訪問 string str2 = sortList["key2"].ToString(); Console.WriteLine(str2);//遍歷sortList foreach (DictionaryEntry item in sortList) {Console.WriteLine(item.Key);Console.WriteLine(item.Value); }

?　　SortedList實現(xiàn)了IDictionary接口，所以可以使用下標key訪問元素的形式，同時要求key必須唯一。

?我們知道HashTable通過使用哈希函數(shù)通過key快速找到存儲位置，那么SortedList又是如何實現(xiàn)下標key訪問元素?

　　SortedList的底層實現(xiàn)與HashTable有著本質(zhì)的區(qū)別。SortedList中使用object[] keys 和 object[] values 兩個對象數(shù)組分別來存儲key和value，要求實現(xiàn)能按照key有序輸出，在下標key訪問的時候就無法使用Hash函數(shù)了，所以SortedList雖然也是鍵值集合，但與Hash卻沒有任何聯(lián)系。通過查看SortedList的底層代碼，原來它的實現(xiàn)是二分查找(BinarySearch)，也就是說要求key是有序排列的，在查找的時候進行二分比較搜索，找到對應的index，從而返回values[index]。

?那么如何在HashTable和SortedList中做出選擇?

　　如果需要實現(xiàn)按照key有序輸出，那么毫無疑問就要選擇SortedList了。如果不需要按照key有序輸出，在小數(shù)據(jù)量的情況下，兩者選擇任何一個性能都應該差不多，但大數(shù)據(jù)量的情況下，則更應該選擇HashTable。為什么呢？理由有兩點。1.HashTable的key下標訪問更直接更快。通過上面分析我們知道SortedList的key下標訪問是由二分查找實現(xiàn)的，實現(xiàn)的時間復雜度為O（log n），而Hash函數(shù)的時間復雜度為O（1），HashTable的實現(xiàn)更優(yōu)。2.SortedList要求key有序，這意味著在插入的時候必須適當?shù)匾苿訑?shù)組，從而達到有序的目的，所以存在性能上的消耗，HashTable的實現(xiàn)更優(yōu)。

　　?SortedList也并沒有走出裝箱拆箱性能和類型安全的圈子，所以應該盡量避免直接使用它。

System.Collections.Generic

　　1. System.Collections.Generic 組織空間

System.Collections.Generic是.NET 2.0新增的一個命名空間。C#1中的集合類型都存在著裝箱拆箱的性能問題以及潛在的類型安全問題，丑陋的設計必須得到改進，于是C#2就引入了泛型這個概念。

　　2. 何為集合泛型

　　新的命名空間下，可以看到接口或集合類后都攜帶了<T>或<TKey,TValue>。很明顯，攜帶<T>對應的是單元素集合，攜帶<TKey,TValue>對應的是鍵值集合。那么泛型又是如何工作的呢？來看一下其編譯過程吧：初次編譯時，首先生成IL代碼和元數(shù)據(jù)，T（TKey，TValue）只是作為類型占位符，不進行泛型類型的實例化；在進行JIT編譯時，將以實際類型替換IL代碼和元數(shù)據(jù)中的T占位符，并將其轉換為本地代碼，下一次對該泛型類型的引用將使用相同的本地代碼。

　　泛型即解決了裝箱拆箱的性能問題，又解決了潛在的類型轉換安全問題，所以在實際應用中，推薦使用泛型集合代替非泛型集合。

　　3. 泛型集合與非泛型集合的對應?

　　ArrayList => List<T> ?新的泛型集合去掉了Array前綴。

　　Stack，Queue => Stack<T>，Queue<T>

　　HashTable => Dictionary<TKey，TValue> 新的泛型鍵值集合的命名放棄了HashTable，但其內(nèi)部實現(xiàn)原理還是和HashTable有很大相似的。

　　SortedList => SortedList<TKey，TValue> | SortedDictionary<TKey，TValue>

?如何區(qū)分SortedList<TKey，TValue> 和?SortedDictionary<TKey，TValue>？

　 ?SortedList<TKey，TValue>的底層實現(xiàn)基本是按照SortedList，下標key訪問是二分查找的O（log n），插入和移除運算復雜度是O（n）。而SortedDictionary<TKey，TValue> 底層實現(xiàn)是二叉搜索樹，下標key訪問也為O（log n），插入和移除運算復雜度是O（log n）。所以SortedList<TKey，TValue>使用的內(nèi)存會比SortedDictionary<TKey，TValue>小，SortedDictionary<TKey，TValue>在插入和移除元素的時候更快。

轉載于:https://www.cnblogs.com/teroy/p/3134666.html

總結

以上是生活随笔為你收集整理的C#集合通论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

通论

上一篇： Standard Driver Rout
下一篇： Android Audio Play O