第分析C#Dictionary的實現(xiàn)原理目錄一、理論知識1.1、Hash算法1.2、Hash桶算法1.3、解決沖突算法二、Dictionary實現(xiàn)2.1、Entry結(jié)構(gòu)體2.2、其它關(guān)鍵私有變量2.3、Dictionary-Add操作2.4、Dictionary-Find操作2.5、Dictionary-Remove操作2.6、Dictionary-Resize操作(擴(kuò)容)2.6.1、擴(kuò)容操作的觸發(fā)條件2.6.2、擴(kuò)容操作如何進(jìn)行2.7、Dictionary-再談Add操作2.8、Collection版本控制

一、理論知識

對于Dictionary的實現(xiàn)原理，其中有兩個關(guān)鍵的算法，一個是Hash算法，一個是用于應(yīng)對Hash碰撞沖突解決算法。

1.1、Hash算法

Hash算法是一種數(shù)字摘要算法，它能將不定長度的二進(jìn)制數(shù)據(jù)集給映射到一個較短的二進(jìn)制長度數(shù)據(jù)集，常見的MD5算法就是一種Hash算法，通過MD5算法可對任何數(shù)據(jù)生成數(shù)字摘要。而實現(xiàn)了Hash算法的函數(shù)我們叫她Hash函數(shù)。Hash函數(shù)有以下幾點特征。

相同的數(shù)據(jù)進(jìn)行Hash運算，得到的結(jié)果一定相同。HashFunc(key1)==HashFunc(key1)

不同的數(shù)據(jù)進(jìn)行Hash運算，其結(jié)果也可能會相同，(Hash會產(chǎn)生碰撞)。key1!=key2=HashFunc(key1)==HashFunc(key2).

Hash運算時不可逆的，不能由key獲取原始的數(shù)據(jù)。key1=hashCode但是hashCode=\=key1。

下圖就是Hash函數(shù)的一個簡單說明，任意長度的數(shù)據(jù)通過HashFunc映射到一個較短的數(shù)據(jù)集中。

關(guān)于Hash碰撞下圖很清晰的就解釋了，可從圖中得知SandraDee和JohnSmith通過hash運算后都落到了02的位置，產(chǎn)生了碰撞和沖突。

常見的構(gòu)造Hash函數(shù)的算法有以下幾種：

1.直接尋址法：取keyword或keyword的某個線性函數(shù)值為散列地址。即H(key)=key或H(key)=akey+b，當(dāng)中a和b為常數(shù)（這樣的散列函數(shù)叫做自身函數(shù)）

2.數(shù)字分析法：分析一組數(shù)據(jù)，比方一組員工的出生年月日，這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體同樣，這種話，出現(xiàn)沖突的幾率就會非常大，可是我們發(fā)現(xiàn)年月日的后幾位表示月份和詳細(xì)日期的數(shù)字區(qū)別非常大，假設(shè)用后面的數(shù)字來構(gòu)成散列地址，則沖突的幾率會明顯減少。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。

3.平方取中法：取keyword平方后的中間幾位作為散列地址。

4.折疊法：將keyword切割成位數(shù)同樣的幾部分，最后一部分位數(shù)能夠不同，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。

5.隨機(jī)數(shù)法：選擇一隨機(jī)函數(shù)，取keyword的隨機(jī)值作為散列地址，通經(jīng)常使用于keyword長度不同的場合。

6.除留余數(shù)法：取keyword被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即H(key)=keyMODp,p=m。不僅能夠?qū)eyword直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇非常重要，一般取素數(shù)或m，若p選的不好，容易產(chǎn)生碰撞.

1.2、Hash桶算法

說到Hash算法大家就會想到Hash表，一個Key通過Hash函數(shù)運算后可快速的得到hashCode，通過hashCode的映射可直接Get到Value，但是hashCode一般取值都是非常大的，經(jīng)常是2^32以上，不可能對每個hashCode都指定一個映射。

因為這樣的一個問題，所以人們就將生成的HashCode以分段的形式來映射，把每一段稱之為一個Bucket（桶），一般常見的Hash桶就是直接對結(jié)果取余。

假設(shè)將生成的hashCode可能取值有2^32個，然后將其切分成一段一段，使用8個桶來映射，那么就可以通過bucketIndex=HashFunc(key1)%8這樣一個算法來確定這個hashCode映射到具體的哪個桶中。

大家可以看出來，通過hash桶這種形式來進(jìn)行映射，所以會加劇hash的沖突。

1.3、解決沖突算法

對于一個hash算法，不可避免的會產(chǎn)生沖突，那么產(chǎn)生沖突以后如何處理，是一個很關(guān)鍵的地方，目前常見的沖突解決算法有拉鏈法(Dictionary實現(xiàn)采用的)、開放定址法、再Hash法、公共溢出分區(qū)法，本文只介紹拉鏈法與再Hash法，對于其它算法感興趣的同學(xué)可參考文章最后的參考文獻(xiàn)。

1.拉鏈法：這種方法的思路是將產(chǎn)生沖突的元素建立一個單鏈表，并將頭指針地址存儲至Hash表對應(yīng)桶的位置。這樣定位到Hash表桶的位置后可通過遍歷單鏈表的形式來查找元素。

2.再Hash法：顧名思義就是將key使用其它的Hash函數(shù)再次Hash，直到找到不沖突的位置為止。

對于拉鏈法有一張圖來描述，通過在沖突位置建立單鏈表，來解決沖突。

二、Dictionary實現(xiàn)

Dictionary實現(xiàn)我們主要對照源碼來解析，目前對照源碼的版本是.NetFramwork4.7。地址可戳一戳這個鏈接源碼地址：Link

這一章節(jié)中主要介紹Dictionary中幾個比較關(guān)鍵的類和對象，然后跟著代碼來走一遍插入、刪除和擴(kuò)容的流程，相信大家就能理解它的設(shè)計原理。

2.1、Entry結(jié)構(gòu)體

首先我們引入Entry這樣一個結(jié)構(gòu)體，它的定義如下代碼所示。這是Dictionary種存放數(shù)據(jù)的最小單位，調(diào)用Add(Key,Value)方法添加的元素都會被封裝在這樣的一個結(jié)構(gòu)體中。

privatestructEntry{

publicinthashCode;//除符號位以外的31位hashCode值,如果該Entry沒有被使用，那么為-1

publicintnext;//下一個元素的下標(biāo)索引，如果沒有下一個就為-1

publicTKeykey;//存放元素的鍵

publicTValuevalue;//存放元素的值

}

2.2、其它關(guān)鍵私有變量

除了Entry結(jié)構(gòu)體外，還有幾個關(guān)鍵的私有變量，其定義和解釋如下代碼所示。

privateint[]buckets;//Hash桶

privateEntry[]entries;//Entry數(shù)組，存放元素

privateintcount;//當(dāng)前entries的index位置

privateintversion;//當(dāng)前版本，防止迭代過程中集合被更改

privateintfreeList;//被刪除Entry在entries中的下標(biāo)index，這個位置是空閑的

privateintfreeCount;//有多少個被刪除的Entry，有多少個空閑的位置

privateIEqualityComparerTKeycomparer;//比較器

privateKeyCollectionkeys;//存放Key的集合

privateValueCollectionvalues;//存放Value的集合

上面代碼中，需要注意的是buckets、entries這兩個數(shù)組，這是實現(xiàn)Dictionary的關(guān)鍵。

2.3、Dictionary-Add操作

經(jīng)過上面的分析，相信大家還不是特別明白為什么需要這么設(shè)計，需要這么做。那我們現(xiàn)在來走一遍Dictionary的Add流程，來體會一下。

首先我們用圖的形式來描述一個Dictionary的數(shù)據(jù)結(jié)構(gòu)，其中只畫出了關(guān)鍵的地方。桶大小為4以及Entry大小也為4的一個數(shù)據(jù)結(jié)構(gòu)。

然后我們假設(shè)需要執(zhí)行一個Add操作，dictionary.Add("a","b")，其中key="a",value="b"。

1.根據(jù)key的值，計算出它的hashCode。我們假設(shè)"a"的hash值為6（GetHashCode("a")=6）。

2.通過對hashCode取余運算，計算出該hashCode落在哪一個buckets桶中?，F(xiàn)在桶的長度（buckets.Length）為4，那么就是6%4最后落在index為2的桶中，也就是buckets[2]。

3.避開一種其它情況不談，接下來它會將hashCode、key、value等信息存入entries[count]中，因為count位置是空閑的；繼續(xù)count++指向下一個空閑位置。上圖中第一個位置，index=0就是空閑的，所以就存放在entries[0]的位置。

4.將Entry的下標(biāo)entryIndex賦值給buckets中對應(yīng)下標(biāo)的bucket。步驟3中是存放在entries[0]的位置，所以buckets[2]=0。

5.最后version++，集合發(fā)生了變化，所以版本需要+1。只有增加、替換和刪除元素才會更新版本

上文中的步驟1~5只是方便大家理解，實際上有一些偏差，后文再談Add操作小節(jié)中會補(bǔ)充。

完成上面Add操作后，數(shù)據(jù)結(jié)構(gòu)更新成了下圖這樣的形式。

這樣是理想情況下的操作，一個bucket中只有一個hashCode沒有碰撞的產(chǎn)生，但是實際上是會經(jīng)常產(chǎn)生碰撞；那么Dictionary類中又是如何解決碰撞的呢。

我們繼續(xù)執(zhí)行一個Add操作，dictionary.Add("c","d")，假設(shè)GetHashCode(“c”)=6，最后6%4=2。最后桶的index也是2，按照之前的步驟1~3是沒有問題的，執(zhí)行完后數(shù)據(jù)結(jié)構(gòu)如下圖所示。

如果繼續(xù)執(zhí)行步驟4那么buckets[2]=1，然后原來的buckets[2]=entries[0]的關(guān)系就會丟失，這是我們不愿意看到的?，F(xiàn)在Entry中的next就發(fā)揮大作用了。

如果對應(yīng)的buckets[index]有其它元素已經(jīng)存在，那么會執(zhí)行以下兩條語句，讓新的entry.next指向之前的元素，讓buckets[index]指向現(xiàn)在的新的元素，就構(gòu)成了一個單鏈表。

entries[index].next=buckets[targetBucket];

buckets[targetBucket]=index;

實際上步驟4也就是做一個這樣的操作，并不會去判斷是不是有其它元素，因為buckets中桶初始值就是-1，不會造成問題。

經(jīng)過上面的步驟以后，數(shù)據(jù)結(jié)構(gòu)就更新成了下圖這個樣子。

2.4、Dictionary-Find操作

為了方便演示如何查找，我們繼續(xù)Add一個元素dictionary.Add("e","f")，GetHashCode(“e”)=7;7%buckets.Length=3,數(shù)據(jù)結(jié)構(gòu)如下所示。

假設(shè)我們現(xiàn)在執(zhí)行這樣一條語句dictionary.GetValueOrDefault("a")，會執(zhí)行以下步驟.

1.獲取key的hashCode，計算出所在的桶位置。我們之前提到，"a"的hashCode=6，所以最后計算出來targetBucket=2。

2.通過buckets[2]=1找到entries[1],比較key的值是否相等，相等就返回entryIndex，不想等就繼續(xù)entries[next]查找，直到找到key相等元素或者next==-1的時候。這里我們找到了key=="a"的元素，返回entryIndex=0。

3.如果entryIndex=0那么返回對應(yīng)的entries[entryIndex]元素，否則返回default(TValue)。這里我們直接返回entries[0].value。

整個查找的過程如下圖所示.

將查找的代碼摘錄下來，如下所示。

//尋找Entry元素的位置

privateintFindEntry(TKeykey){

if(key==null){

ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);

if(buckets!=null){

inthashCode=comparer.GetHashCode(key)0x7FFFFFFF;//獲取HashCode，忽略符號位

//inti=buckets[hashCode%buckets.Length]找到對應(yīng)桶，然后獲取entry在entries中位置

//ii=entries[i].next遍歷單鏈表

for(inti=buckets[hashCode%buckets.Length];ii=entries[i].next){

//找到就返回了

if(entries[i].hashCode==hashCodecomparer.Equals(entries[i].key,key))returni;

return-1;

internalTValueGetValueOrDefault(TKeykey){

inti=FindEntry(key);

//大于等于0代表找到了元素位置，直接返回value

//否則返回該類型的默認(rèn)值

if(i=0){

returnentries[i].value;

returndefault(TValue);

}

2.5、Dictionary-Remove操作

前面已經(jīng)向大家介紹了增加、查找，接下來向大家介紹Dictionary如何執(zhí)行刪除操作。我們沿用之前的Dictionary數(shù)據(jù)結(jié)構(gòu)。

刪除前面步驟和查找類似，也是需要找到元素的位置，然后再進(jìn)行刪除的操作。

我們現(xiàn)在執(zhí)行這樣一條語句dictionary.Remove("a")，hashFunc運算結(jié)果和上文中一致。步驟大部分與查找類似，我們直接看摘錄的代碼，如下所示。

publicboolRemove(TKeykey){

if(key==null){

ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);

if(buckets!=null){

//1.通過key獲取hashCode

inthashCode=comparer.GetHashCode(key)0x7FFFFFFF;

//2.取余獲取bucket位置

intbucket=hashCode%buckets.Length;

//last用于確定是否當(dāng)前bucket的單鏈表中最后一個元素

intlast=-1;

//3.遍歷bucket對應(yīng)的單鏈表

for(inti=buckets[bucket];ilast=i,i=entries[i].next){

if(entries[i].hashCode==hashCodecomparer.Equals(entries[i].key,key)){

//4.找到元素后，如果last0，代表當(dāng)前是bucket中最后一個元素，那么直接讓bucket內(nèi)下標(biāo)賦值為entries[i].next即可

if(last0){

buckets[bucket]=entries[i].next;

else{

//4.1last不小于0，代表當(dāng)前元素處于bucket單鏈表中間位置，需要將該元素的頭結(jié)點和尾節(jié)點相連起來,防止鏈表中斷

entries[last].next=entries[i].next;

//5.將Entry結(jié)構(gòu)體內(nèi)數(shù)據(jù)初始化

entries[i].hashCode=-1;

//5.1建立freeList單鏈表

entries[i].next=freeList;

entries[i].key=default(TKey);

entries[i].value=default(TValue);

//*6.關(guān)鍵的代碼，freeList等于當(dāng)前的entry位置，下一次Add元素會優(yōu)先Add到該位置

freeList=i;

freeCount++;

//7.版本號+1

version++;

returntrue;

returnfalse;

}

執(zhí)行完上面代碼后，數(shù)據(jù)結(jié)構(gòu)就更新成了下圖所示。需要注意varsion、freeList、freeCount的值都被更新了。

2.6、Dictionary-Resize操作(擴(kuò)容)

有細(xì)心的小伙伴可能看過了Add操作以后就想問了，buckets、entries不就是兩個數(shù)組么，那萬一數(shù)組放滿了怎么辦？接下來就是我所要介紹的Resize（擴(kuò)容）這樣一種操作，對我們的buckets、entries進(jìn)行擴(kuò)容。

2.6.1、擴(kuò)容操作的觸發(fā)條件

首先我們需要知道在什么情況下，會發(fā)生擴(kuò)容操作；第一種情況自然就是數(shù)組已經(jīng)滿了，沒有辦法繼續(xù)存放新的元素。如下圖所示的情況。

從上文中大家都知道，Hash運算會不可避免的產(chǎn)生沖突，Dictionary中使用拉鏈法來解決沖突的問題，但是大家看下圖中的這種情況。

所有的元素都剛好落在buckets[3]上面，結(jié)果就是導(dǎo)致了時間復(fù)雜度O(n)，查找性能會下降；所以第二種，Dictionary中發(fā)生的碰撞次數(shù)太多，會嚴(yán)重影響性能，也會觸發(fā)擴(kuò)容操作。

目前.NetFramwork4.7中設(shè)置的碰撞次數(shù)閾值為100.

publicconstintHashCollisionThreshold=100;

2.6.2、擴(kuò)容操作如何進(jìn)行

為了給大家演示的清楚，模擬了以下這種數(shù)據(jù)結(jié)構(gòu)，大小為2的Dictionary，假設(shè)碰撞的閾值為2；現(xiàn)在觸發(fā)Hash碰撞擴(kuò)容。

開始擴(kuò)容操作。

1.申請兩倍于現(xiàn)在大小的buckets、entries

2.將現(xiàn)有的元素拷貝到新的entries

完成上面兩步操作后，新數(shù)據(jù)結(jié)構(gòu)如下所示。

3、如果是Hash碰撞擴(kuò)容，使用新HashCode函數(shù)重新計算Hash值

上文提到了，這是發(fā)生了Hash碰撞擴(kuò)容，所以需要使用新的Hash函數(shù)計算Hash值。新的Hash函數(shù)并一定能解決碰撞的問題，有可能會更糟，像下圖中一樣的還是會落在同一個bucket上。

4、對entries每個元素bucket=newEntries[i].hashCode%newSize確定新buckets位置

**5、重建hash鏈，newEntries[i].next=buckets[bucket];buckets[bucket]=i;**

因為buckets也擴(kuò)充為兩倍大小了，所以需要重新確定hashCode在哪個bucket中；最后重新建立hash單鏈表.

這就完成了擴(kuò)容的操作，如果是達(dá)到Hash碰撞閾值觸發(fā)的擴(kuò)容可能擴(kuò)容后結(jié)果會更差。

在JDK中，HashMap如果碰撞的次數(shù)太多了，那么會將單鏈表轉(zhuǎn)換為紅黑樹提升查找性能。目前.NetFramwork中還沒有這樣的優(yōu)化，.NetCore中已經(jīng)有了類似的優(yōu)化，以后有時間在分享.NetCore的一些集合實現(xiàn)。

每次擴(kuò)容操作都需要遍歷所有元素，會影響性能。所以創(chuàng)建Dictionary實例時最好設(shè)置一個預(yù)估的初始大小。

privatevoidResize(intnewSize,boolforceNewHashCodes){

Contract.Assert(newSize=entries.Length);

//1.申請新的Buckets和entries

int[]newBuckets=newint[newSize];

for(inti=0;inewBuckets.Length;i++)newBuckets[i]=-1;

Entry[]newEntries=newEntry[newSize];

//2.將entries內(nèi)元素拷貝到新的entries總

Array.Copy(entries,0,newEntries,0,count);

//3.如果是Hash碰撞擴(kuò)容，使用新HashCode函數(shù)重新計算Hash值

if(forceNewHashCodes){

for(inti=0;icount;i++){

if(newEntries[i].hashCode!=-1){

newEntries[i].hashCode=(comparer.GetHashCode(newEntries[i].key)0x7FFFFFFF);

//4.確定新的bucket位置

//5.重建Hahs單鏈表

for(inti=0;icount;i++){

if(newEntries[i].hashCode=0){

intbucket=newEntries[i].hashCode%newSize;

newEntries[i].next=newBuckets[bucket];

newBuckets[bucket]=i;

buckets=newBuckets;

entries=newEntries;

}

2.7、Dictionary-再談Add操作

在我們之前的Add操作步驟中，提到了這樣一段話，這里提到會有一種其它的情況，那就是有元素被刪除的情況。

避開一種其它情況不談，接下來它會將hashCode、key、value等信息存入entries[count]中，因為count位置是空閑的；繼續(xù)count++指向下一個空閑位置。上圖中第一個位置，index=0就是空閑的，所以就存放在entries[0]的位置。

因為count是通過自增的方式來指向entries[]下一個空閑的entry，如果有元素被刪除了，那么在count之前的位置就會出現(xiàn)一個空閑的entry；如果不處理，會有很多空間被浪費。

這就是為什么Remove操作會記錄freeList、freeCount，就是為了將刪除的空間利用起來。實際上Add操作會優(yōu)先使用freeList的空閑entry位置，摘錄代碼如下。

privatevoidInsert(TKeykey,TValuevalue,booladd){

if(key==null){

ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);

if(buckets==null)Initialize(0);

//通過key獲取hashCode

inthashCode=comparer.GetHashCode(key)0x7FFFFFFF;

//計算出目標(biāo)bucket下標(biāo)

inttargetBucket=hashCode%buckets.Length;

//碰撞次數(shù)

intcollisionCount=0;

for(inti=buckets[targetBucket];ii=entries[i].next){

if(entries[i].hashCode==hashCodecomparer.Equals(entries[i].key,key)){

//如果是增加操作，遍歷到了相同的元素，那么拋出異常

if(add){

ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);

//如果不是增加操作，那可能是索引賦值操作dictionary["foo"]="foo"

//那么賦值后版本++，退出

entries[i].value=value;

version++;

return;

//每遍歷一個元素，都是一次碰撞

collisionCount++;

intindex;

//如果有被刪除的元素，那么將元素放到被刪除元素的空閑位置

if(freeCount0){

index=freeList;

freeList=entries[index].next;

freeCount--;

else{

//如果當(dāng)前entries已滿，那么觸發(fā)擴(kuò)容