談談Dictionary<T1,T2>和List<T>的問題

引子：

事情的起因我已經記不清了，但是事情的根本原因在於，我們要遍歷一個集合，是用字典來存儲還是用數組鏈表來存儲。

1.把基本概念說清

對List<T>的闡述，我在http://www.cnblogs.com/kym/archive/2009/03/09/1406657.html一文中已經有過相應的解釋，再此不再贅述。

Dictionary<T1,T2>，我們俗稱其為字典，他包含一個Key和與之對應的Value，其目的是能夠根據Key迅速地找到Value，算法復雜度為O(1)。

2.Dictionary<T1,T2>和Hashtable的異同

首先很多人都認同一個觀點，說Dictionary<T1,T2>是HashTable的泛型版本，這一點在大致上是正確的，可是當我們運行這樣一段代碼時，便可看出他們的不同：

代碼

1　　　　　　　　　　　　　Dictionary<int,　int>　dic　=　new　Dictionary<int,　int>();
2　　　　　　　　　　　　　dic.Add(1,　5);
3　　　　　　　　　　　　　dic.Add(10,　3);
4　　　　　　　　　　　　　dic.Add(2,　5);
5　　　　　　　　　　　　　foreach　(int　key　in　dic.Keys)
6　　　　　　　　　　　　　{
7　　　　　　　　　　　　　　　　　Console.WriteLine(key);
8　　　　　　　　　　　　　}
9
10　　　　　　　　　　　　　Hashtable　hashtable　=　new　Hashtable();
11　　　　　　　　　　　　　hashtable.Add(1,　5);
12　　　　　　　　　　　　　hashtable.Add(10,　3);
13　　　　　　　　　　　　　hashtable.Add(2,　5);
14　　　　　　　　　　　　　foreach　(object　key　in　hashtable.Keys)
15　　　　　　　　　　　　　{
16　　　　　　　　　　　　　　　　　Console.WriteLine(key.ToString());
17　　　　　　　　　　　　　}

Dictionary<T1,T2>是根據插入的順序來遍歷，但是Hashtable在插入時會打亂其位置。

並且我們在用Reflector看源碼的時候也會發現

代碼

1　if　((this.buckets[num6].key　==　null)　||　((this.buckets[num6].key　==　this.buckets)　&&　((this.buckets[num6].hash_coll　&　0x80000000L)　==　0L)))
2　　　　　{
3　　　　　　　　　if　(index　!=　-1)
4　　　　　　　　　{
5　　　　　　　　　　　　　num6　=　index;
6　　　　　　　　　}
7　　　　　　　　　Thread.BeginCriticalRegion();
8　　　　　　　　　this.isWriterInProgress　=　true;
9　　　　　　　　　this.buckets[num6].val　=　nvalue;
10　　　　　　　　　this.buckets[num6].key　=　key;
11　　　　　　　　　this.buckets[num6].hash_coll　|=　(int)　num3;
12　　　　　　　　　this.count++;
13　　　　　　　　　this.UpdateVersion();
14　　　　　　　　　this.isWriterInProgress　=　false;
15　　　　　　　　　Thread.EndCriticalRegion();
16　　　　　}
17

Hashtable是線程安全的，而Dictionary明顯不具備如此特性。

3.Dictionary<T1,T2>的存儲原理

說到字典，我們就不能不說其存儲結構，他會根據Key通過Hash計算來得到其應存放的虛擬內存地址，這也是在哈希表中Key必須唯一的原因，當我們按照Key進行查找時，首先就是根據Key計算出其所存放的虛擬內存地址，去對應的內存地址找數據，得到其Value。

這一點HashTable與其相同。

4.問題提出

我們為了討論遍歷時Dictionary和List的效率，我寫了這樣一段測試代碼：

代碼

1　　　　　　　　　　　　　Dictionary<string,　string>　dic　=　new　Dictionary<string,　string>();
2　　　　　　　　　　　　　Random　r　=　new　Random();
3　　　　　　　　　　　　　for　(int　i　=　0;　i　<　100000;　i++)
4　　　　　　　　　　　　　{
5　　　　　　　　　　　　　　　　　int　random　=　r.Next(10);
6　　　　　　　　　　　　　　　　　dic.Add(i.ToString(),　random.ToString());
7　　　　　　　　　　　　　}
8　　　　　　　　　　　　　StringBuilder　sb　=　new　StringBuilder(10000000);
9　　　　　　　　　　　　　Stopwatch　sw　=　new　Stopwatch();
10　　　　　　　　　　　　　sw.Start();
11　　　　　　　　　　　　　foreach　(string　key　in　dic.Keys)
12　　　　　　　　　　　　　{
13　　　　　　　　　　　　　　　　　sb.Append(dic[key]);
14　　　　　　　　　　　　　}
15　　　　　　　　　　　　　sw.Stop();
16　　　　　　　　　　　　　Console.WriteLine("Dic花費的