帶你看懂Dictionary的內(nèi)部實現(xiàn)

了解Dictionary的開發(fā)人員都了解，和List相比，字典添加會慢，但是查找會比較快，那么Dictionary是如何實現(xiàn)的呢？

Dictionary的構造

下面的代碼我看看Dictionary在構造時都做了什么：

        PRivate void Initialize(int capacity)        {            int prime = HashHelpers.GetPrime(capacity);            this.buckets = new int[prime];            for (int i = 0; i < this.buckets.Length; i++)            {                this.buckets[i] = -1;            }            this.entries = new Entry<TKey, TValue>[prime];            this.freeList = -1;        } 

我們看到，Dictionary在構造的時候做了以下幾件事：

1. 初始化一個this.buckets = new int[prime]
2. 初始化一個this.entries = new Entry<TKey, TValue>[prime]
3. Bucket和entries的容量都為大于字典容量的一個最小的質(zhì)數(shù)

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

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

首先，我們構造一個:

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

初始化后：

添加元素時，集合內(nèi)部Bucket和entries的變化

Test.Add(4,"4")后：

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

Test.Add(11,"11")

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

Test.Add(18,"18")

我們添加18，讓HashCode再次碰撞到Buckets中下標為4的槽上，這個時候新元素添加到count+1的位置，并且Bucket槽指向新元素，新元素的Next指向Entries中下標為1的元素。此時你會發(fā)現(xiàn)所有hashcode相同的元素都形成了一個鏈表，如果元素碰撞次數(shù)越多，鏈表越長。所花費的時間也相對較多。

Test.Add(19,"19")

再次添加元素19，此時Hash碰撞到另外一個槽上，但是元素仍然添加到count+1的位置。

刪除元素時集合內(nèi)部的變化

Test.Remove(4)

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

Test.Remove(18)

刪除Key為18的元素，仍然通過一次碰撞，并且沿著鏈表尋找2次，找到當前元素，刪除當前元素，并且讓FreeList指向當前元素，當前元素的Next指向上一個FreeList元素。

此時你會發(fā)現(xiàn)FreeList指向了一個鏈表，鏈表里面不包含任何元素，F(xiàn)reeCount表示不包含元素的鏈表的長度。

Test.Add(20,"20")

再添加一個元素，此時由于FreeList鏈表不為空，因此字典會優(yōu)先添加到FreeList鏈表所指向的位置，添加后FreeCount減1，F(xiàn)reeList鏈表長度變?yōu)?

總結：

通過以上試驗，我們可以發(fā)現(xiàn)Dictionary在添加，刪除元素按照如下方法進行：

1. 通過Hash算法來碰撞到指定的Bucket上，碰撞到同一個Bucket槽上所有數(shù)據(jù)形成一個單鏈表
2. 默認情況Entries槽中的數(shù)據(jù)按照添加順序排列
3. 刪除的數(shù)據(jù)會形成一個FreeList的鏈表，添加數(shù)據(jù)的時候，優(yōu)先向FreeList鏈表中添加數(shù)據(jù)，F(xiàn)reeList為空則按照count依次排列
4. 字典查詢及其的效率取決于碰撞的次數(shù)，這也解釋了為什么Dictionary的查找會很快。

好吧，熬了半宿，今天先寫到這了，如果看了有所收獲就幫忙頂一下，有問題歡迎拍磚。