Unity3d+C#：Dictionary源码与使用注意（转）

Entry结构体

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

private struct Entry
        {
            public int hashCode;    // Lower 31 bits of hash code, -1 if unused
            public int next;        // Index of next entry, -1 if last
            public TKey key;           // Key of entry
            public TValue value;         // Value of entry
        }      

其他私有变量

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的集合      

构造

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在构造的时候做了以下几件事：

1、初始化一个this.buchkets=new int[prime]

2、初始化一个this.entries=new Entry<TKey,TValue>[prime]

3、Bucket和entries的容量都为大于字典容量的一个最小的质数

其中this.buckets主要用来进行Hash碰撞，this.entries用来存储字典的内容，并且标识下一个元素的位置。

Q:prime跟capacity的关系

A:

int size = HashHelpers.GetPrime(capacity);

public static readonly int[] primes = { 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

创建了6，返回的是7

Add操作

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

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。

概况：11的哈希碰到了4的哈希，所以，buckets[4]指向新的Entries[1]，然后Entries[1].next = 0，代表它指向Entries[0]

Test.Add(18,“18”) Test.Add(19,“19”)

Remove操作

Test.Remove(4)

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

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

ContainsKey

public bool ContainsKey(TKey key)
{
    return FindEntry(key) >= 0;
}

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

    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        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;
}      

从源码中看到 ContainsKey 是一个查找Key位置的过程。它调用了 FindEntry 函数，FindEntry 查找Key值位置的方法跟我们前面提到的相同。从用Key值得到的哈希值地址开始查找，查看所有冲突链表中，是否有与Key值相同的值，找到即刻返回该索引地址。

Q：C#中为什么字典的查询速度比List快

A：List是全部遍历，字典按照hashCode遍历

1. 字典按照key先buckets里面找(key.GetHashCode()%prime=buckets的索引)，i = buckets[hashCode % buckets.Length]即是entries的索引值
2. int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next：一直找，找到next为-1停止。
3. 找到entries[i].hashCode == hashCode&& comparer.Equals(entries[i].key, key)的，返回

Dictionary哈希桶算法

Hash碰撞冲突解决算法

1. 所有的entries是个单链表，对于有相同的buckets[i], next指向下一个的索引
2. Hash表桶即buckets，里面buckets[i]值为entries的索引

优化

1. new时分配容量3->7->17->37
2. key为值类型，哈希计算更迅速