前言

对于C#中的Dictionary类相信大家都不陌生，这是一个Collection(集合)类型，可以通过Key/Value(键值对的形式来存放数据；该类最大的优点就是它查找元素的时间复杂度接近O(1)，实际项目中常被用来做一些数据的本地缓存，提升整体效率。

那么是什么样的设计能使得Dictionary类能实现O(1)的时间复杂度呢？

理论知识

对于Dictionary的实现原理，其中有两个关键的算法，

• Hash算法
• 用于应对Hash碰撞冲突解决算法

Hash算法

Hash算法是一种 数字摘要 算法，它能 将不定长度的二进制数据集给映射到一个较短的二进制长度数据集，常见的MD5算法就是一种Hash算法，通过MD5算法可对任何数据生成数字摘要。而实现了Hash算法的函数我们叫它Hash函数。

Hash函数有以下几点特征:

• 相同的数据进行Hash运算，得到的结果一定相同。HashFunc(key1) == HashFunc(key1)
• 不同的数据进行Hash运算，其结果也可能会相同，(Hash会产生碰撞)。key1 != key2 => HashFunc(key1) == HashFunc(key2)
• Hash运算是不可逆的.

任意长度的数据通过HashFunc映射到一个较短的数据集中,如下图所示:

关于Hash碰撞下图很清晰的就解释了，可从图中得知Sandra Dee 和 John Smith通过hash运算后都落到了02的位置，产生了碰撞和冲突。

常见的构造Hash函数的算法有以下几种。

1. 直接寻址法
   • 取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，当中a和b为常数（这样的散列函数叫做自身函数）
   1. 数字分析法
   • 分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
   1. 平方取中法
   • 取keyword平方后的中间几位作为散列地址。
   1. 折叠法
   • 将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。
   1. 随机数法
   • 选择一随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度不同的场合。
   1. 除留余数法
   • 取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD 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映射到具体的哪个桶中。

大家可以看出来，通过hash桶这种形式来进行映射，所以会加剧hash的冲突。

解决冲突算法

对于一个hash算法，不可避免的会产生冲突，那么产生冲突以后如何处理，是一个很关键的地方，目前常见的冲突解决算法有

• 拉链法(Dictionary实现采用的单链表)
  • 这种方法的思路是将产生冲突的元素建立一个单链表，并将头指针地址存储至Hash表对应桶的位置。这样定位到Hash表桶的位置后可通过遍历单链表的形式来查找元素。

• 开放定址法
• 再Hash法
  • 顾名思义就是将key使用其它的Hash函数再次Hash，直到找到不冲突的位置为止。
• 公共溢出分区法

本文只介绍拉链法与再Hash法，对于其它算法感兴趣的同学可参考文章最后的参考文献。

Dictionary实现

对照源码的版本是.Net Framwork 4.7

Entry结构体

先我们引入Entry这样一个结构体，它的定义如下代码所示。这是Dictionary种存放数据的最小单位，调用Add(Key,Value)方法添加的元素都会被封装在这样的一个结构体中。

private struct Entry
{
    public int hashCode;    // 31位散列值，32最高位表示符号位，-1表示未使用
    public int next;        // 下一个元素的下标索引，-1表示结尾
    public TKey key;        // 存放元素的键
    public TValue value;    // 存放元素的值
}

其它关键私有变量

除了Entry结构体外，还有几个关键的私有变量，其定义和解释如下代码所示。

//
private int[] buckets;      // Hash桶,内部维护的数据地址
private Entry[] entries;    // 元素数组，用于维护哈希表中的数据
private int count;          // 元素数量
private int version;        // 当前版本，防止迭代过程中集合被更改
private int freeList;       // 指向一个空闲的链表
private int freeCount;      // 空闲列表元素数量
private IEqualityComparer<TKey> comparer;   // 哈希表中的比较函数
private KeyCollection keys;     // 存放Key的集合
private ValueCollection values;     // 存放Value的集合

上面代码中，需要注意的是buckets、entries这两个数组，这是实现Dictionary的关键。

Dictionary – 初始化

private void Initialize(int capacity)
{
    //根据构造函数设定的初始容量，获取一个近似的素数
    int size = HashHelpers.GetPrime(capacity);
    buckets = new int[size];
    for (int i = 0; i < buckets.Length; i++)
        buckets[i] = -1; // buckets 中的节点值，-1表示空值。
    entries = new Entry[size];
    // freeList 为-1表示没有空链表。
    freeList = -1;
}

buckets 和 freeList 所值指向的数据其实全是存储于一块连续的内存空间（entries ）之中。

Dictionary – Add操作

经过上面的分析，相信大家还不是特别明白为什么需要这么设计，需要这么做。那我们现在来走一遍Dictionary的Add流程，来体会一下。

首先我们用图的形式来描述一个Dictionary的数据结构，其中只画出了关键的地方。桶大小为4 以及 Entry大小也为4 的一个数据结构。

// 假设需要执行一个Add操作，dictionary.Add("a","b")，其中key = "a",value = "b"。
private void Insert(TKey key, TValue value, bool add)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    // 初始化桶
    if (buckets == null) Initialize(0);

    // 整个整数 0x7FFFFFFF 的二进制表示就是除了首位是 0，其余都是1
    // 就是说，这是最大的整型数 int（因为第一位是符号位，0 表示他是正数）
    // 获取HashCode，忽略符号位
    int hashCode     = comparer.GetHashCode(key) & 0x7FFFFFFF;

    // 计算出目标bucket下标
    // 通过对hashCode取余运算，计算出该hashCode落在哪一个buckets桶中。
    // 假设现在桶的长度（buckets.Length）为4，那么就是6 % 4最后落在index为2的桶中，也就是buckets[2]。
    int targetBucket = hashCode % buckets.Length;

#if FEATURE_RANDOMIZED_STRING_HASHING
    // 记录碰撞
    int collisionCount = 0;
#endif

    // 目标桶已经存在相同的key的情况:
    // 从目标哈希桶的地址开始遍历
    // entries[i].next下一个元素的下标索引，如果没有下一个就为-1
    for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next)
    {
        // 判断桶内是否存在相同的key
        if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
        {
            if (add)
            {
                // 如果是增加操作，遍历到了相同的元素，那么抛出异常
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
            }
            // 存在则覆盖旧的值, 重新写入
            // 如果不是增加操作，那可能是索引赋值操作 dictionary["foo"] = "foo"
            entries[i].value = value;
            // 只有增加、替换和删除元素才会更新版本
            version++;
            return;
        }

#if FEATURE_RANDOMIZED_STRING_HASHING
        // 每遍历一个元素，都是一次碰撞, 用于计算是否超过碰撞阈值
        collisionCount++;
#endif
    }

    int index;
    // 如果有被删除的元素，那么将元素放到被删除元素的空闲位置
    if (freeCount > 0)
    {
        // 将新Add的元素优先使用因删除而空闲出来的地址
        index    = freeList;
        // 并将entries[index]的next指针赋值给freeList, 如果链表中没有下一个被删除的元素
        // entries[index].next就是默认的-1, 如果还有空闲的位置, 则用于下一次add使用
        freeList = entries[index].next;
        freeCount--;
    }
    else
    {
        // 判断是否需要扩容
        if (count == entries.Length)
        {
            // 扩容：取大于count * 2的最小素数作为entries和bucket的新容量（即数组长度.Length）
            Resize();
            targetBucket = hashCode % buckets.Length;
        }

        index = count;
        count++;
    }
    // 将hashCode、key、value等信息存入entries[index]中，
    entries[index].hashCode = hashCode;
    // 指向桶中原先的第一个entries[0], 做成单链表, 对应的桶指向这个新加的entries[index]
    entries[index].next     = buckets[targetBucket];
    entries[index].key      = key;
    entries[index].value    = value;
    // 对应的桶指向这个新加的entries[index]
    buckets[targetBucket]   = index;
    // 最后version++，集合发生了变化，所以版本需要+1。只有增加、替换和删除元素才会更新版本
    version++;

#if FEATURE_RANDOMIZED_STRING_HASHING
#if FEATURE_CORECLR
    // In case we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
    // in this case will be EqualityComparer<string>.Default.
    // Note, randomized string hashing is turned on by default on coreclr so EqualityComparer<string>.Default will
    // be using randomized string hashing

    if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default)
    {
        comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default;
        Resize(entries.Length, true);
    }
#else
    if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer))
    {
        // 如果碰撞次数（单链表长度）大于设置的最大碰撞阈值, 那么触发Hash碰撞扩容
        comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
        Resize(entries.Length, true);
    }
#endif // FEATURE_CORECLR

#endif
}

完成上面Add操作后，数据结构更新成了下图这样的形式。

这样是理想情况下的操作，一个bucket中只有一个hashCode没有碰撞的产生，但是实际上是会经常产生碰撞；那么Dictionary类中又是如何解决碰撞的呢。

我们继续执行一个Add操作，dictionary.Add("c","d")，假设GetHashCode(“c”)=6，最后6 % 4 = 2。最后桶的index也是2，按照之前的步骤1~3是没有问题的，执行完后数据结构如下图所示。

如果继续执行步骤4那么buckets[2] = 1，然后原来的buckets[2]=>entries[0]的关系就会丢失，这是我们不愿意看到的。现在Entry中的next就发挥大作用了。

如果对应的buckets[index]有其它元素已经存在，那么会执行以下两条语句，让新的entry.next指向之前的元素，让buckets[index]指向现在的新的元素，就构成了一个单链表。

// ② 下图的二操作
entries[index].next     = buckets[targetBucket];
...;
// ① 下图的一操作
buckets[targetBucket]   = index;

实际上步骤4也就是做一个这样的操作，并不会去判断是不是有其它元素，因为buckets中桶初始值就是-1，不会造成问题。经过上面的步骤以后，数据结构就更新成了下图这个样子。

Dictionary – 再谈Add操作

在我们之前的Add操作步骤中，提到了这样一段话，这里提到会有一种其它的情况，那就是有元素被删除的情况。

避开一种其它情况不谈，接下来它会将hashCode、key、value等信息存入entries[count]中，因为count位置是空闲的；继续count++指向下一个空闲位置。上图中第一个位置，index=0就是空闲的，所以就存放在entries[0]的位置。

因为count是通过自增的方式来指向entries[]下一个空闲的entry，如果有元素被删除了，那么在count之前的位置就会出现一个空闲的entry；如果不处理，会有很多空间被浪费。

这就是为什么Remove操作会记录freeList、freeCount，就是为了将删除的空间利用起来。实际上Add操作会优先使用freeList的空闲entry位置.

Dictionary – Find操作

为了方便演示如何查找，我们继续Add一个元素dictionary.Add("e","f")，GetHashCode(“e”) = 7; 7% buckets.Length=3,数据结构如下所示。

假设我们现在执行这样一条语句dictionary.GetValueOrDefault("a")，会执行以下步骤.

1. 获取key的hashCode，计算出所在的桶位置。我们之前提到，”a”的hashCode=6，所以最后计算出来targetBucket=2。
2. 通过buckets[2]=1找到entries[1],比较key的值是否相等，相等就返回entryIndex
   • 不相等就继续entries[next]查找，直到找到key相等元素或者next == -1的时候。这里我们找到了key == “a”的元素，返回entryIndex=0。
3. 如果entryIndex >= 0那么返回对应的entries[entryIndex]元素，否则返回default(TValue)。这里我们直接返回entries[0].value。

private int FindEntry(TKey key)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null)
    {
        // 获取HashCode，忽略符号位
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        // 计算hashCode存在哪个哈希桶中, buckets[hashCode % buckets.Length]找到对应桶
        // 遍历entries[i].next直到key相等位置
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)
        {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
        }
    }
    // -1表示没找到
    return -1;
}

public bool TryGetValue(TKey key, out TValue value)
{
    // 大于等于0代表找到了元素位置，直接返回value
    // 否则返回该类型的默认值
    int i = FindEntry(key);
    if (i >= 0)
    {
        value = entries[i].value;
        return true;
    }

    value = default(TValue);
    return false;
}

Dictionary – Remove操作

前面已经向大家介绍了增加、查找，接下来向大家介绍Dictionary如何执行删除操作。我们沿用之前的Dictionary数据结构。

public bool Remove(TKey key)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null)
    {
        // 忽略符号位获取hashcode
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        // 找到对应桶
        int bucket   = hashCode % buckets.Length;    
        // last用于确定是否当前bucket的单链表中最后一个元素
        int last     = -1;
        // 遍历桶的单链表
        for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)
        {
            // 遍历找到桶中对应的entries
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
            {
                // 找到元素后，如果last< 0，代表当前是bucket中最后一个元素，
                // 那么直接让bucket内下标赋值为 entries[i].next即可(值为-1)
                if (last < 0)
                {
                    // 将桶中的第一个
                    buckets[bucket] = entries[i].next;
                }
                else
                {
                    // last不小于0，代表当前元素处于bucket单链表中间位置，
                    // 需要将该元素的头结点和尾节点相连起来,防止链表中断
                    entries[last].next = entries[i].next;
                }

                entries[i].hashCode = -1;
                entries[i].next     = freeList;
                entries[i].key      = default(TKey);
                entries[i].value    = default(TValue);
                // 关键的代码，freeList等于当前的entry位置，下一次Add元素会优先Add到该位置
                freeList            = i;
                freeCount++;
                version++;
                return true;
            }
        }
    }

    return false;
}

执行完上面代码后，数据结构就更新成了下图所示。需要注意varsion、freeList、freeCount的值都被更新了。

Dictionary – Resize操作(扩容)

有细心的小伙伴可能看过了Add操作以后就想问了，buckets、entries不就是两个数组么，那万一数组放满了怎么办？接下来就是我所要介绍的Resize（扩容）这样一种操作，对我们的buckets、entries进行扩容。

首先我们需要知道在什么情况下，会发生扩容操作；

第一种情况自然就是数组已经满了，没有办法继续存放新的元素。如下图所示的情况。

从上文中大家都知道，Hash运算会不可避免的产生冲突，Dictionary中使用拉链法来解决冲突的问题，但是大家看下图中的这种情况。

所有的元素都刚好落在buckets[3]上面，结果就是导致了时间复杂度O(n)，查找性能会下降；

所以第二种，Dictionary中发生的碰撞次数太多，会严重影响性能，也会触发扩容操作。

目前.Net Framwork 4.7中设置的碰撞次数阈值为100. public const int HashCollisionThreshold = 100;

为了给大家演示的清楚，模拟了以下这种数据结构，大小为2的Dictionary，假设碰撞的阈值为2；现在触发Hash碰撞扩容。

开始扩容操作。

1. 申请两倍于现在大小的buckets、entries
2. 将现有的元素拷贝到新的entries

1. 如果是Hash碰撞扩容，使用新HashCode函数重新计算Hash值

上文提到了，这是发生了Hash碰撞扩容，所以需要使用新的Hash函数计算Hash值。新的Hash函数并一定能解决碰撞的问题，有可能会更糟，像下图中一样的还是会落在同一个bucket上。

1. 对entries每个元素bucket = newEntries[i].hashCode % newSize确定新buckets位置

2. 重建hash链，newEntries[i].next=buckets[bucket]; buckets[bucket]=i;

因为buckets也扩充为两倍大小了，所以需要重新确定hashCode在哪个bucket中；最后重新建立hash单链表.

这就完成了扩容的操作，如果是达到Hash碰撞阈值触发的扩容可能扩容后结果会更差。

在JDK中，HashMap如果碰撞的次数太多了，那么会将单链表转换为红黑树提升查找性能。目前.Net Framwork中还没有这样的优化，.Net Core中已经有了类似的优化，以后有时间在分享.Net Core的一些集合实现。

每次扩容操作都需要遍历所有元素，会影响性能。所以创建Dictionary实例时最好设置一个预估的初始大小

private void Resize(int newSize, bool forceNewHashCodes)
{
    Contract.Assert(newSize >= entries.Length);

    // 1. 申请新的Buckets和entries
    int[] newBuckets                                          = new int[newSize];
    for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
    Entry[] newEntries                                        = new Entry[newSize];

    // 2. 将entries内元素拷贝到新的entries中
    Array.Copy(entries, 0, newEntries, 0, count);
    // 3. 如果是Hash碰撞扩容，使用新HashCode函数重新计算Hash值
    if (forceNewHashCodes)
    {
        for (int i = 0; i < count; i++)
        {
            if (newEntries[i].hashCode != -1)
            {
                // 重新计算hashcode
                newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
            }
        }
    }
    // 4. 确定新的bucket位置
    // 5. 重建Hahs单链表
    for (int i = 0; i < count; i++)
    {
        if (newEntries[i].hashCode >= 0)
        {
            int bucket = newEntries[i].hashCode % newSize;
            newEntries[i].next = newBuckets[bucket];
            newBuckets[bucket] = i;
        }
    }

    buckets = newBuckets;
    entries = newEntries;
}

Collection版本控制

在上文中一直提到了version这个变量，在每一次新增、修改和删除操作时，都会使version++；那么这个version存在的意义是什么呢？

首先我们来看一段代码，这段代码中首先实例化了一个Dictionary实例，然后通过foreach遍历该实例，在foreach代码块中使用dic.Remove(kv.Key)删除元素。

结果就是抛出了System.InvalidOperationException:"Collection was modified..."这样的异常，迭代过程中不允许集合出现变化。如果在Java中遍历直接删除元素，会出现诡异的问题，所以.Net中就使用了version来实现版本控制。

那么如何在迭代过程中实现版本控制的呢？我们看一看源码就很清楚的知道

在迭代器初始化时，就会记录dictionary.version版本号，之后每一次迭代过程都会检查版本号是否一致，如果不一致将抛出异常。这样就避免了在迭代过程中修改了集合，造成很多诡异的问题。

最后

Dictionary内部实现结构比Hashtable复杂，因为具有单链表的特性，效率也比Hashtable高。