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

一、Dictionary源碼學習

Dictionary實現我們主要對照源碼來解析，目前對照的源碼版本是.Net Framwork4.8，源碼地址。

這邊主要介紹Dictionary中幾個比較關鍵的類和對象，然后跟著代碼來走一遍插入、刪除和擴容的流程。

1、Entry結構體

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

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、其他關鍵私有變量

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

3、Dictionary的構造

 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在構造的時候做了以下幾件事：

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

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

3、Bucket和entries的容量都為大于字典容量的一個最小的質數

其中this.buckets主要用來進行Hash碰撞，this.entries用來存儲字典的內容，并且標識下一個元素的位置。

4、Dictionary——Add操作

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

首先，我們構造一個，容量為6：

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

Test.Add(4,"4")

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

Test.Add(11,"11")

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

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

 5、Dictionary——Remove操作

Test.Remove(4)

我們刪除元素時，通過一次碰撞，并且沿著鏈表尋找3次，找到key為4的元素所在的位置，刪除當前元素，并且把FreeList的位置指向當前刪除元素的位置，FreeCount置為1。

 刪除的數據會形成一個FreeList的鏈表，添加數據的時候，優(yōu)先向FreeList鏈表中添加數據，FreeList為空則按照count一次排序。

6、Dictionary——Resize操作（擴容）

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

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

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

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

 第二種，Dictionary中發(fā)生的碰撞次數太多，會嚴重影響性能，也會出發(fā)擴容操作。

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

 6.2 擴容操作如何進行

為了給大家演示清楚，模擬了以下這種數據結構，大小為2的Dictionary，假設碰撞的閾值為2；現在出發(fā)Hash碰撞擴容。

1、申請兩倍于現在大小的buckets、entries

2、將現有的元素拷貝到新的entries

3、如果時Hash碰撞擴容，使用新HashCode函數重新計算Hash值

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

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

關注點

對于Dictionary的實現原理，其中有兩個關鍵的算法，1、Hash算法。2、用于對應Hash碰撞沖突解決算法。

二、Hash算法

Hash算法是一種術宇摘要算法，它將能不定長度的二進制數據集給映射到一個較短的二進制長度數據集。

實現了Hash算法的函數我們叫它Hash函數，Hash函數有以下幾點特征。

1、相同的數據進行Hash運算，得到的結果一定是相同的，HashFunc(key1)==HashFunc(key1)

2、不同的數據進行Hash運算，其結果也可能會相同，（Hash會產生碰撞）。key1!=key2=>HashFunc(key1)==HashFunc(key2)。

3、Hash運算是不可逆的，不能由key獲取原始的數據，key1=>hashCode但是hashCode==>key1

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

 常見的構造Hash函數的算法有以下幾種。

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

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

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

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

5、隨機數法：選擇一隨機函數，取keyword的隨機值作為散列地址，通常適用于keyword長度不同的場合。

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

三、Hash桶算法

說到Hash算法大家就會想到Hash表，一個Key通過Hash函數運算后可快速的得到hashCode，通過hashCode的映射可以直接Get到Value。但是hashCode一般取值都是非常大的。經常是2^32以上，不可能對每個hashCode都指定一個映射。因為這樣的一個問題，所以人們就將生成的HashCode以分段的形式來映射，把每一段稱之為一個Bucket(桶)，一般常見的Hash桶就是直接對結果取余。

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

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

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

四、Hash碰撞沖突解決算法

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

1、拉鏈法（開散列）：將產生沖突的元素建立一個單鏈表，并將頭指針地址存儲之Hash表對應桶的位置，這樣定位到Hash表桶的位置后通過遍歷單鏈表的形式來查找元素。

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

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

拉鏈法：

 開放地址法：

假設現在有一個關鍵碼集合（1、4、5、6、7、9），哈希結構的容量為10，哈希函數為Hash(key)=key%10。將所有關鍵碼插入到該哈希結構中，如圖：

 假如仙子啊有一個關鍵碼24要插入該結構中，使用哈希函數求得哈希地址為24，但是該地址已經存放了元素，此時發(fā)生哈希沖突。

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

 限制：

1、用該方法需要關鍵碼必須為整形才能被模，所以我們需要實現將非整形轉化為整形。

2、模的數值最好為素數，需要我們創(chuàng)建一個素數表。

3、增容問題。

好了，關于Dictionary的相關知識，就先介紹到這里了。