使用C#已經(jīng)有好多年頭了，然后突然有一天被問到C#Dictionary的基本實(shí)現(xiàn)，這讓我反思到我一直處于拿來(lái)主義，能用就好，根本沒有去考慮和學(xué)習(xí)一些底層架構(gòu)，想想令人頭皮發(fā)麻。下面開始學(xué)習(xí)一些我平時(shí)用得理所當(dāng)然的東西，今天先學(xué)習(xí)一下字典，Dictionary

一、Dictionary源碼學(xué)習(xí)

Dictionary實(shí)現(xiàn)我們主要對(duì)照源碼來(lái)解析，目前對(duì)照的源碼版本是.Net Framwork4.8，源碼地址。

這邊主要介紹Dictionary中幾個(gè)比較關(guān)鍵的類和對(duì)象，然后跟著代碼來(lái)走一遍插入、刪除和擴(kuò)容的流程。

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

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

1         private struct Entry 
2         {
3             public int hashCode;    // Lower 31 bits of hash code, -1 if unused
4             public int next;        // Index of next entry, -1 if last
5             public TKey key;           // Key of entry
6             public TValue value;         // Value of entry
7         }

2、其他關(guān)鍵私有變量

1 private int[] buckets; // Hash桶
2 private Entry[] entries; // Entry數(shù)組，存放元素
3 private int count; // 當(dāng)前entries的index位置
4 private int version; // 當(dāng)前版本，防止迭代過程中集合被更改
5 private int freeList; // 被刪除Entry在entries中的下標(biāo)index，這個(gè)位置是空閑的
6 private int freeCount; // 有多少個(gè)被刪除的Entry，有多少個(gè)空閑的位置
7 private IEqualityComparer<TKey> comparer; // 比較器
8 private KeyCollection keys; // 存放Key的集合
9 private ValueCollection values; // 存放Value的集合

3、Dictionary的構(gòu)造

 1         private void Initialize(int capacity)
 2         {
 3             int prime = HashHelpers.GetPrime(capacity);
 4             this.buckets = new int[prime];
 5             for (int i = 0; i < this.buckets.Length; i++)
 6             {
 7                 this.buckets[i] = -1;
 8             }
 9             this.entries = new Entry<TKey, TValue>[prime];
10             this.freeList = -1;
11         }

我們看到，Dictionary在構(gòu)造的時(shí)候做了以下幾件事：

1、初始化一個(gè)this.buchkets=new int[prime]

2、初始化一個(gè)this.entries=new Entry<TKey,TValue>[prime]

3、Bucket和entries的容量都為大于字典容量的一個(gè)最小的質(zhì)數(shù)

其中this.buckets主要用來(lái)進(jìn)行Hash碰撞，this.entries用來(lái)存儲(chǔ)字典的內(nèi)容，并且標(biāo)識(shí)下一個(gè)元素的位置。

4、Dictionary——Add操作

我們以Dictionary<int,string>為例，來(lái)展示一下Dictinoary如何添加元素：

首先，我們構(gòu)造一個(gè)，容量為6：

Dictionary<int, string> test = new Dictionary<int, string>(6);

Test.Add(4,"4")

根據(jù)Hash算法：4.GetHashCode()%7=4，因此碰撞到buckets中下表為4的槽上，此時(shí)由于Count為0，因此元素放在Entries中第0個(gè)元素上，添加后，Count變?yōu)?

Test.Add(11,"11")

 根據(jù)Hash算法，11.GetHashCode()%7=4，因此再次碰撞到Buckets中下標(biāo)為4的槽上，由于此槽上的值已經(jīng)不是-1，此時(shí)Count=1，因此把這個(gè)新加的元素放到entries中下標(biāo)為1的數(shù)組中，并且讓Buckets槽指向下表為1的entries中，下標(biāo)為1的entry之下下表為0的entries。

Test.Add(18,"18")
Test.Add(19,"19")

 5、Dictionary——Remove操作

Test.Remove(4)

我們刪除元素時(shí)，通過一次碰撞，并且沿著鏈表尋找3次，找到key為4的元素所在的位置，刪除當(dāng)前元素，并且把FreeList的位置指向當(dāng)前刪除元素的位置，F(xiàn)reeCount置為1。

 刪除的數(shù)據(jù)會(huì)形成一個(gè)FreeList的鏈表，添加數(shù)據(jù)的時(shí)候，優(yōu)先向FreeList鏈表中添加數(shù)據(jù)，F(xiàn)reeList為空則按照count一次排序。

6、Dictionary——Resize操作（擴(kuò)容）

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

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

首先我們需要直到在什么情況下，會(huì)發(fā)生擴(kuò)容操作：

第一種情況自然就是數(shù)組已經(jīng)滿了，沒有辦法繼續(xù)存放新的元素，如下圖所示。

 第二種，Dictionary中發(fā)生的碰撞次數(shù)太多，會(huì)嚴(yán)重影響性能，也會(huì)出發(fā)擴(kuò)容操作。

Hash運(yùn)算會(huì)不可避免的產(chǎn)生沖突，Dictionary中使用拉鏈發(fā)來(lái)解決沖突的問題，但是，大家看下圖中的這種情況，所有的元素都剛好落在buckets[3]上面，結(jié)果就導(dǎo)致了時(shí)間復(fù)雜度O(n)，查找性能會(huì)下降：

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

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

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

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

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

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

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

關(guān)注點(diǎn)

對(duì)于Dictionary的實(shí)現(xiàn)原理，其中有兩個(gè)關(guān)鍵的算法，1、Hash算法。2、用于對(duì)應(yīng)Hash碰撞沖突解決算法。

二、Hash算法

Hash算法是一種術(shù)宇摘要算法，它將能不定長(zhǎng)度的二進(jìn)制數(shù)據(jù)集給映射到一個(gè)較短的二進(jìn)制長(zhǎng)度數(shù)據(jù)集。

實(shí)現(xiàn)了Hash算法的函數(shù)我們叫它Hash函數(shù)，Hash函數(shù)有以下幾點(diǎn)特征。

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

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

3、Hash運(yùn)算是不可逆的，不能由key獲取原始的數(shù)據(jù)，key1=>hashCode但是hashCode==>key1

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

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

1、直接尋址法：取keyword或者keyword的某個(gè)線性函數(shù)值為散列地址，即H(key)=key或者H(key)=a·key+b，當(dāng)中a和b為常數(shù)（這樣的散列函數(shù)叫做自身函數(shù)）。這個(gè)的應(yīng)用就是，比如我們世界地圖的掩碼，直接用坐標(biāo)x*1000+坐標(biāo)y，得到key。

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

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

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

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

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

三、Hash桶算法

說到Hash算法大家就會(huì)想到Hash表，一個(gè)Key通過Hash函數(shù)運(yùn)算后可快速的得到hashCode，通過hashCode的映射可以直接Get到Value。但是hashCode一般取值都是非常大的。經(jīng)常是2^32以上，不可能對(duì)每個(gè)hashCode都指定一個(gè)映射。因?yàn)檫@樣的一個(gè)問題，所以人們就將生成的HashCode以分段的形式來(lái)映射，把每一段稱之為一個(gè)Bucket(桶)，一般常見的Hash桶就是直接對(duì)結(jié)果取余。

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

Dictionary就是這用的哈希桶算法。

int hashCode =comparer.GetHashCode(key)&0x7FFFFFFF;
int targetBucket = hashCode %buckets.Length;

四、Hash碰撞沖突解決算法

對(duì)于一個(gè)hash算法，不可避免地會(huì)產(chǎn)生沖突，那么產(chǎn)生沖突以后如何處理，是一個(gè)很關(guān)鍵的地方，目前常見的沖突解決算法有拉鏈法(Dictionary實(shí)現(xiàn)采用的)、開放定址法、再Hash法、公共溢出分區(qū)法。

1、拉鏈法（開散列）：將產(chǎn)生沖突的元素建立一個(gè)單鏈表，并將頭指針地址存儲(chǔ)之Hash表對(duì)應(yīng)桶的位置，這樣定位到Hash表桶的位置后通過遍歷單鏈表的形式來(lái)查找元素。

2、開放定址法（閉散列）：當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被裝滿，說明再哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個(gè)”空位置中去。

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

拉鏈法：

 開放地址法：

假設(shè)現(xiàn)在有一個(gè)關(guān)鍵碼集合（1、4、5、6、7、9），哈希結(jié)構(gòu)的容量為10，哈希函數(shù)為Hash(key)=key%10。將所有關(guān)鍵碼插入到該哈希結(jié)構(gòu)中，如圖：

 假如仙子啊有一個(gè)關(guān)鍵碼24要插入該結(jié)構(gòu)中，使用哈希函數(shù)求得哈希地址為24，但是該地址已經(jīng)存放了元素，此時(shí)發(fā)生哈希沖突。

線性探測(cè)：從發(fā)生哈希沖突的位置開始，一次向后探測(cè)，直到找到下一個(gè)空位置為止，例如上面的地址，插入關(guān)鍵碼24時(shí)，進(jìn)行線性探測(cè)，插入后如下圖：

 限制：

1、用該方法需要關(guān)鍵碼必須為整形才能被模，所以我們需要實(shí)現(xiàn)將非整形轉(zhuǎn)化為整形。

2、模的數(shù)值最好為素?cái)?shù)，需要我們創(chuàng)建一個(gè)素?cái)?shù)表。

3、增容問題。

好了，關(guān)于Dictionary的相關(guān)知識(shí)，就先介紹到這里了。