使用C#已經有好多年頭了，然後突然有一天被問到C#Dictionary的基本實現，這讓我反思到我一直處於拿來主義，能用就好，根本沒有去考慮和學習一些底層架構，想想令人頭皮發麻。下麵開始學習一些我平時用得理所當然的東西，今天先學習一下字典，Dictionary 一、Dictionary源碼學習 Dic ...
使用C#已經有好多年頭了，然後突然有一天被問到C#Dictionary的基本實現，這讓我反思到我一直處於拿來主義，能用就好，根本沒有去考慮和學習一些底層架構，想想令人頭皮發麻。下麵開始學習一些我平時用得理所當然的東西，今天先學習一下字典，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變為1
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的鏈表，添加數據的時候，優先向FreeList鏈表中添加數據，FreeList為空則按照count一次排序。
6、Dictionary——Resize操作（擴容）
有細心的小伙伴可能看過Add操作後就想問了，buckets、entries不就是兩個數組麽，那萬一數組放滿了怎麼辦？接下來就是我要介紹的Resize（擴容）這樣一種操作，對我們的buckets、entries進行擴容。
6.1 擴容操作的觸發條件
首先我們需要直到在什麼情況下，會發生擴容操作：
第一種情況自然就是數組已經滿了，沒有辦法繼續存放新的元素，如下圖所示。
第二種，Dictionary中發生的碰撞次數太多，會嚴重影響性能，也會出發擴容操作。
Hash運算會不可避免的產生衝突，Dictionary中使用拉鏈發來解決衝突的問題，但是，大家看下圖中的這種情況，所有的元素都剛好落在buckets[3]上面，結果就導致了時間複雜度O(n)，查找性能會下降：
6.2 擴容操作如何進行
為了給大家演示清楚，模擬了以下這種數據結構，大小為2的Dictionary，假設碰撞的閾值為2；現在出發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、數字分析法：找出數字的規律，儘可能利用這些數據來構造衝突幾率較低的散列地址。分析一組數據，比方一組員工的出生年月日，這時，我們發現出生年月日的前幾位數字大體相同，這種話，出現衝突的幾率就會非常大，可是我們發現年月日的後幾位表示月份和詳細日期的數字區別非常大，假設用後面的數字來構造散列地址，則衝突幾率就會明顯減少。
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法、公共溢出分區法。
1、拉鏈法（開散列）：將產生衝突的元素建立一個單鏈表，並將頭指針地址存儲之Hash表對應桶的位置，這樣定位到Hash表桶的位置後通過遍歷單鏈表的形式來查找元素。
2、開放定址法（閉散列）：當發生哈希衝突時，如果哈希表未被裝滿，說明再哈希表中必然還有空位置，那麼可以把key存放到衝突位置中的“下一個”空位置中去。
3、再Hash法：顧名思義就是將key使用其他的Hash函數再次Hash，直到找到不衝突的位置為止。
拉鏈法：
開放地址法：
假設現在有一個關鍵碼集合（1、4、5、6、7、9），哈希結構的容量為10，哈希函數為Hash(key)=key%10。將所有關鍵碼插入到該哈希結構中，如圖：
假如仙子啊有一個關鍵碼24要插入該結構中，使用哈希函數求得哈希地址為24，但是該地址已經存放了元素，此時發生哈希衝突。
線性探測：從發生哈希衝突的位置開始，一次向後探測，直到找到下一個空位置為止，例如上面的地址，插入關鍵碼24時，進行線性探測，插入後如下圖：
限制：
1、用該方法需要關鍵碼必須為整形才能被模，所以我們需要實現將非整形轉化為整形。
2、模的數值最好為素數，需要我們創建一個素數表。
3、增容問題。
好了，關於Dictionary的相關知識，就先介紹到這裡了。
