引子：

事情的起因我已經(jīng)記不清了，但是事情的根本原因在于，我們要遍歷一個(gè)集合，是用字典來存儲(chǔ)還是用數(shù)組鏈表來存儲(chǔ)。

1.?????? 把基本概念說清

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

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

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

首先很多人都認(rèn)同一個(gè)觀點(diǎn)，說Dictionary<T1,T2>是HashTable的泛型版本，這一點(diǎn)在大致上是正確的，可是當(dāng)我們運(yùn)行這樣一段代碼時(shí)，便可看出他們的不同：

代碼?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>是根據(jù)插入的順序來遍歷，但是Hashtable在插入時(shí)會(huì)打亂其位置。

并且我們在用Reflector看源碼的時(shí)候也會(huì)發(fā)現(xiàn)

代碼?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>的存儲(chǔ)原理

說到字典，我們就不能不說其存儲(chǔ)結(jié)構(gòu)，他會(huì)根據(jù)Key通過Hash計(jì)算來得到其應(yīng)存放的虛擬內(nèi)存地址，這也是在哈希表中Key必須唯一的原因，當(dāng)我們按照Key進(jìn)行查找時(shí)，首先就是根據(jù)Key計(jì)算出其所存放的虛擬內(nèi)存地址，去對(duì)應(yīng)的內(nèi)存地址找數(shù)據(jù)，得到其Value。

這一點(diǎn)HashTable與其相同。

4.?????? 問題提出

我們?yōu)榱擞懻摫闅v時(shí)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花費(fèi)的時(shí)間:");
17?????????????Console.WriteLine(sw.ElapsedTicks.ToString());
18?????????????GC.Collect();
19?
20?????????????List<string>?list?=?new?List<string>();
21?????????????for?(int?i?=?0;?i?<?100000;?i++)
22?????????????{
23?????????????????list.Add(r.Next().ToString());
24?????????????}
25?
26?????????????sb?=?new?StringBuilder(10000000);
27?????????????sw.Reset();
28?????????????sw.Start();
29?
30?????????????foreach?(string?s?in?list)
31?????????????{
32?????????????????sb.Append(s);
33?????????????}
34?
35?????????????sw.Stop();
36?????????????Console.WriteLine("List花費(fèi)的時(shí)間:");
37?????????????Console.WriteLine(sw.ElapsedTicks.ToString());

?

?

這段代碼產(chǎn)生的測試結(jié)果如下：

?

5.?????? 問題剖析

同樣是集合，為什么性能會(huì)有這樣的差距。我們要從存儲(chǔ)結(jié)構(gòu)和操作系統(tǒng)的原理談起。

首先我們清楚List<T>是對(duì)數(shù)組做了一層包裝，我們在數(shù)據(jù)結(jié)構(gòu)上稱之為線性表，而線性表的概念是，在內(nèi)存中的連續(xù)區(qū)域，除了首節(jié)點(diǎn)和尾節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都有著其唯一的前驅(qū)結(jié)點(diǎn)和后續(xù)節(jié)點(diǎn)。我們在這里關(guān)注的是連續(xù)這個(gè)概念。

而HashTable或者Dictionary，他是根據(jù)Key而根據(jù)Hash算法分析產(chǎn)生的內(nèi)存地址，因此在宏觀上是不連續(xù)的，雖然微軟對(duì)其算法也進(jìn)行了很大的優(yōu)化。

由于這樣的不連續(xù)，在遍歷時(shí)，Dictionary必然會(huì)產(chǎn)生大量的內(nèi)存換頁操作，而List只需要進(jìn)行最少的內(nèi)存換頁即可，這就是List和Dictionary在遍歷時(shí)效率差異的根本原因。

6.?????? 再談Dictionary

也許很多人說，既然Dictionary如此強(qiáng)大，那么我們?yōu)槭裁床挥?/span>Dictionary來代替一切集合呢？

在這里我們除了剛才的遍歷問題，還要提到Dictionary的存儲(chǔ)空間問題，在Dictionary中，除了要存儲(chǔ)我們實(shí)際需要的Value外，還需要一個(gè)輔助變量Key，這就造成了內(nèi)存空間的雙重浪費(fèi)。

而且在尾部插入時(shí)，List只需要在其原有的地址基礎(chǔ)上向后延續(xù)存儲(chǔ)即可，而Dictionary卻需要經(jīng)過復(fù)雜的Hash計(jì)算，這也是性能損耗的地方。

7.?????? 任何方法都要合理使用

我在之前的文章中，如:從Dynamic到特性誤用.曾無數(shù)次強(qiáng)調(diào)過，方法可以用，但每個(gè)方法都有著其存在的意義，我們調(diào)用這個(gè)方法，或者使用某個(gè)類，數(shù)據(jù)結(jié)構(gòu)前，一定要搞清其存在的意義，其優(yōu)點(diǎn)和缺點(diǎn)，這樣我們才能寫出最好的代碼。

8.?????? 尾聲

中午匆匆忙忙寫完這篇文章，也是09年最后一篇文章，最后也在這里祝大家新年快樂吧！

轉(zhuǎn)載于:https://www.cnblogs.com/kym/archive/2009/12/31/1636768.html

總結(jié)

以上是生活随笔為你收集整理的谈谈DictionaryT1,T2和ListT的问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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