分析C# Dictionary的实现原理

private int[] buckets;		// Hash桶
private Entry[] entries;	// Entry数组，存放元素
private int count;			// 当前entries的index位置
private int version;		// 当前版本，防止迭代过程中集合被更改
private int freeList;		// 被删除Entry在entries中的下标index，这个位置是空闲的
private int freeCount;		// 有多少个被删除的Entry，有多少个空闲的位置
private IEqualityComparer<TKey> comparer;	// 比较器
private KeyCollection keys;		// 存放Key的集合
private ValueCollection values;		// 存放Value的集合

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

2.3、Dictionary - Add操作

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

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

，其中key = "a",value = "b"。

1.根据key的值，计算出它的hashCode。我们假设"a"的hash值为6（GetHashCode("a") = 6）。

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

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

4.将Entry的下标entryIndex赋值给buckets中对应下标的bucket。步骤3中是存放在entries[0]的位置，所以buckets[2]=0。

5.最后version++，集合发生了变化，所以版本需要+1。只有增加、替换和删除元素才会更新版本

上文中的步骤1~5只是方便大家理解，实际上有一些偏差，后文再谈Add操作小节中会补充。

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

，假设GetHashCode(“c”)=6，最后6 % 4 = 2。最后桶的index也是2，按照之前的步骤1~3是没有问题的，执行完后数据结构如下图所示。

entries[index].next = buckets[targetBucket];
...
buckets[targetBucket] = index;

实际上步骤4也就是做一个这样的操作，并不会去判断是不是有其它元素，因为buckets中桶初始值就是-1，不会造成问题。

经过上面的步骤以后，数据结构就更新成了下图这个样子。

2.4、Dictionary - Find操作

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

，会执行以下步骤.

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。

整个查找的过程如下图所示.

// 寻找Entry元素的位置
private int FindEntry(TKey key) {
    if( key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; // 获取HashCode，忽略符号位
        // int i = buckets[hashCode % buckets.Length] 找到对应桶，然后获取entry在entries中位置
        // i >= 0; i = entries[i].next 遍历单链表
        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;
        }
    }
    return -1;
}
...
internal TValue GetValueOrDefault(TKey key) {
    int i = FindEntry(key);
    // 大于等于0代表找到了元素位置，直接返回value
    // 否则返回该类型的默认值
    if (i >= 0) {
        return entries[i].value;
    }
    return default(TValue);
}

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

    if (buckets != null) {
        // 1. 通过key获取hashCode
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        // 2. 取余获取bucket位置
        int bucket = hashCode % buckets.Length;
        // last用于确定是否当前bucket的单链表中最后一个元素
        int last = -1;
        // 3. 遍历bucket对应的单链表
        for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                // 4. 找到元素后，如果last< 0，代表当前是bucket中最后一个元素，那么直接让bucket内下标赋值为 entries[i].next即可
                if (last < 0) {
                    buckets[bucket] = entries[i].next;
                }
                else {
                    // 4.1 last不小于0，代表当前元素处于bucket单链表中间位置，需要将该元素的头结点和尾节点相连起来,防止链表中断
                    entries[last].next = entries[i].next;
                }
                // 5. 将Entry结构体内数据初始化
                entries[i].hashCode = -1;
                // 5.1 建立freeList单链表
                entries[i].next = freeList;
                entries[i].key = default(TKey);
                entries[i].value = default(TValue);
                // *6. 关键的代码，freeList等于当前的entry位置，下一次Add元素会优先Add到该位置
                freeList = i;
                freeCount++;
                // 7. 版本号+1
                version++;
                return true;
            }
        }
    }
    return false;
}