转载

带你看懂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 = 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);

初始化后：

带你看懂Dictionary的内部实现

（查看大图）

添加元素时，集合内部Bucket和entries的变化

Test.Add(4,”4″)后：

根据Hash算法： 4.GetHashCode()%7= 4,因此碰撞到buckets中下标为4的槽上，此时由于Count为0，因此元素放在Entries中第0个元素上，添加后Count变为1

带你看懂Dictionary的内部实现

（查看大图）

Test.Add(11,”11″)

根据Hash算法 11.GetHashCode()%7=4,因此再次碰撞到Buckets中下标为4的槽上，由于此槽上的值已经不为-1，此时Count=1，因此把这个新加的元素放到entries中下标为1的数组中，并且让Buckets槽指向下标为1的entries中，下标为1的entry之下下标为0的entries。

带你看懂Dictionary的内部实现

（查看大图）

Test.Add(18,”18″)

我们添加18，让HashCode再次碰撞到Buckets中下标为4的槽上，这个时候新元素添加到count+1的位置，并且Bucket槽指向新元素，新元素的Next指向Entries中下标为1的元素。此时你会发现所有hashcode相同的元素都形成了一个链表，如果元素碰撞次数越多，链表越长。所花费的时间也相对较多。

带你看懂Dictionary的内部实现