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為值類型，哈希計算更迅速