C#中Dictionary的内部实现剖析

了解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主要用来进行Hash碰撞，this.entries用来存储字典的内容，并且标识下一个元素的位置。

我们以Dictionary int,string 为例，来展示一下Dictionary如何添加元素：

首先，我们构造一个:

Dictionary int, string test = new Dictionary int, string

初始化后：

添加元素时，集合内部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相同的元素都形成了一个链表，如果元素碰撞次数越多，链 表越长。所花费的时间也相对较多。

Test.Add(19,”19″)

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

删除元素时集合内部的变化

Test.Remove(4)

我们删除元素时，通过一次碰撞，并且沿着链表寻找3次，找到key为4的元素所在的位置，删除当前元素。并且把FreeList的位置指向当前删除元素的位置，FreeCount置为1

Test.Remove(18)

删除Key为18的元素，仍然通过一次碰撞，并且沿着链表寻找2次，找到当前元素，删除当前元素，并且让FreeList指向当前元素，当前元素的Next指向上一个FreeList元素。

此时你会发现FreeList指向了一个链表，链表里面不包含任何元素，FreeCount表示不包含元素的链表的长度。

Test.Add(20,”20″)

再添加一个元素，此时由于FreeList链表不为空，因此字典会优先添加到FreeList链表所指向的位置，添加后FreeCount减1，FreeList链表长度变为1

总结：

通过以上试验，我们可以发现Dictionary在添加，删除元素按照如下方法进行：

通过Hash算法来碰撞到指定的Bucket上，碰撞到同一个Bucket槽上所有数据形成一个单链表

删除的数据会形成一个FreeList的链表，添加数据的时候，优先向FreeList链表中添加数据，FreeList为空则按照count依次排列

好吧，熬了半宿，今天先写到这了，如果看了有所收获就帮忙顶一下，有问题欢迎拍砖。

来源：51CTO

基础篇：Object对象 内存对齐区是什么? HotSpot VM的自动内存管理系统要求对象起始地址必须是8字节的整数倍，换句话说就是对象的大小必须是8字节的整数倍。因此当对象实例数据部分没有对齐的话，就需要通过对齐填充来补全
List以特定索引来存取元素，可以有重复元素。Set不能存放重复元素（用对象的equals()方法来区分元素是否重复）。Map保存键值对（key-value pair）映射，映射关系可以是一对一或多对一。