C#中Dictionary的內部實現剖析

2015-07-28 10:06:03

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

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

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

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

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

首先，我們構造一個:

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

初始化后：

添加元素時，集合內部Bucket和entries的變化

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″)

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