前言

創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括威信網(wǎng)站建設(shè)、威信網(wǎng)站制作、威信網(wǎng)頁(yè)制作以及威信網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，威信網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到威信省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

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

這篇文章討論的主題是集合，重點(diǎn)在于分析集合的區(qū)別和聯(lián)系，加深對(duì)集合的認(rèn)知與使用，熟悉常用C#類庫(kù)有關(guān)集合類的組織結(jié)構(gòu)。

  數(shù)組

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

int[] intArray = new int[10]; 　　　　//整型數(shù)組string[] stringArray = new string[10]; //字符串?dāng)?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ù)自身的需求實(shí)現(xiàn)了左邊接口中的一個(gè)或多個(gè)，按照實(shí)現(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);
}

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

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

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

IDictionary接口也繼承了ICollection接口，實(shí)現(xiàn)了IDicionary接口的集合類可以通過(guò)下標(biāo)key訪問(wèn)的訪問(wèn)方式訪問(wèn)集合元素。

3. ArrayList

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

//聲明ArrayListArrayList 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的底層實(shí)現(xiàn)，可以看到動(dòng)態(tài)數(shù)組其實(shí)是由一個(gè)object[] _items維系著的，這就解釋了為什么集合的元素可以為值類型也可以為引用類型。這樣的底層實(shí)現(xiàn)貌似靈活性很高，集合可以容納異構(gòu)類型，然而卻帶來(lái)了性能上的問(wèn)題，因?yàn)楫?dāng)插入值類型的時(shí)候，就存在隱式裝箱操作，而當(dāng)把元素還原為值類型變量的時(shí)候，又發(fā)生了一次顯式拆箱操作，如果這種裝箱拆箱存在上千萬(wàn)次，那么程序的性能是要大打折扣的。同時(shí)要注意一點(diǎn)的是object類型可以強(qiáng)制轉(zhuǎn)化為任何類型，這是說(shuō)編譯器不會(huì)檢查object強(qiáng)制轉(zhuǎn)換的類型，如果無(wú)法轉(zhuǎn)換的話，這必須等到運(yùn)行時(shí)才能確定出錯(cuò)，這就是類型安全問(wèn)題。

所以應(yīng)該盡量避免使用ArrayList。

4. Stack 和 Queue

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

5. HashTable

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

//創(chuàng)建一個(gè)HashTable實(shí)例Hashtable hashDict = new Hashtable();

//往容器中加入key-valuehashDict.Add("a", "hello");
hashDict.Add("b", "hello");
hashDict.Add("c", "go");
hashDict.Add(4, 300);

//通過(guò)下標(biāo)key獲取valuestring str1 = hashDict["a"].ToString();
string str2 = (string)hashDict["b"];
int i4 = (int)hashDict[4];

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

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

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

6. SortedList

　在控制臺(tái)應(yīng)用程序下運(yùn)行以下代碼并觀察結(jié)果：

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]);
}

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

//創(chuàng)建一個(gè)SortedList實(shí)例SortedList sortList = new SortedList();

//往容器中加入元素sortList.Add("key1", 1);
sortList.Add("key2", 2);
sortList.Add("key3", 3);
sortList.Add("key4", 4);

//獲取按照key排序的第index個(gè)Keystring str1 = sortList.GetKey(0).ToString();
Console.WriteLine(str1);
//獲取按照key排序的第index個(gè)Valueint i1 = (int)sortList.GetByIndex(0);
Console.WriteLine(i1.ToString());
//下標(biāo)key訪問(wèn)string str2 = sortList["key2"].ToString();
Console.WriteLine(str2);

//遍歷sortListforeach (DictionaryEntry item in sortList)
{
    Console.WriteLine(item.Key);
    Console.WriteLine(item.Value);
}

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

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

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

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

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

 SortedList也并沒(méi)有走出裝箱拆箱性能和類型安全的圈子，所以應(yīng)該盡量避免直接使用它。

 System.Collections.Generic

 1. System.Collections.Generic 組織空間

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

 2. 何為集合泛型

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

泛型即解決了裝箱拆箱的性能問(wèn)題，又解決了潛在的類型轉(zhuǎn)換安全問(wèn)題，所以在實(shí)際應(yīng)用中，推薦使用泛型集合代替非泛型集合。

 3. 泛型集合與非泛型集合的對(duì)應(yīng)

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

Stack，Queue => Stack，Queue

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

SortedList => SortedList | SortedDictionary

 如何區(qū)分SortedList 和 SortedDictionary？

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

  原文連接：http://www.cnblogs.com/teroy/p/3134666.html
網(wǎng)頁(yè)題目：C#集合-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)于：http://weahome.cn/article/dcsgse.html