2.3　Dictionary底層源碼剖析

前面剖析了List的源碼，明白了List是基于數(shù)組構(gòu)建而成的，增加、減少、插入的操作都在數(shù)組中進(jìn)行。我們還分析了大部分List的接口，包括Add、Remove、Insert、IndexOf、Find、Sort、ToArray等，并得出了一個(gè)結(jié)論：List是一個(gè)兼容性比較好的組件，但List在效率方面沒(méi)有做優(yōu)化，線程也不安全，需要加鎖機(jī)制來(lái)保證線程的安全性。

下面對(duì)另一個(gè)常用Dictionary組件進(jìn)行底層源碼的分析，看看常用的字典容器是如何構(gòu)造的，它的優(yōu)缺點(diǎn)如何。

1. Dictionary底層代碼剖析

我們知道，Dictionary字典型數(shù)據(jù)結(jié)構(gòu)是以關(guān)鍵字Key值和Value值進(jìn)行一一映射的。Key的類(lèi)型并沒(méi)有做任何的限制，可以是整數(shù)，也可以是字符串，甚至可以是實(shí)例對(duì)象。關(guān)鍵字Key是如何映射到實(shí)例的呢？

其實(shí)沒(méi)有什么神秘的，這種映射關(guān)系可以用一個(gè)Hash函數(shù)來(lái)建立，Dictionary也確實(shí)是這樣做的。這個(gè)Hash函數(shù)并非神秘，我們可以簡(jiǎn)單地認(rèn)為它只是做了一個(gè)模（Mod）的操作，Dictionary會(huì)針對(duì)每個(gè)Key加入容器的元素都進(jìn)行一次Hash（哈希）運(yùn)算操作，從而找到自己的位置。

Hash函數(shù)可以有很多種算法，最簡(jiǎn)單的可以認(rèn)為是余操作，比如當(dāng)Key為整數(shù)93時(shí)，其源碼如下：

---

hash_key = Key % 30 = 3

---

對(duì)于實(shí)例對(duì)象和字符串來(lái)說(shuō)，它們沒(méi)有直接的數(shù)字作為Hash標(biāo)準(zhǔn)，因此它們需要通過(guò)內(nèi)存地址計(jì)算一個(gè)Hash值，計(jì)算這個(gè)內(nèi)存對(duì)象的函數(shù)就叫HashCode，它是基于內(nèi)存地址計(jì)算得到的結(jié)果，編寫(xiě)類(lèi)時(shí)可重載HashCode()來(lái)設(shè)計(jì)一個(gè)我們自己的Hash值計(jì)算方式，也可以使用原始的計(jì)算方式。實(shí)際算法沒(méi)有我舉的例子這么簡(jiǎn)單，我們將在下面的源碼剖析中詳細(xì)講解。

對(duì)于不同的關(guān)鍵字Key，在Hash計(jì)算時(shí)可能得到同一Hash地址，即當(dāng)key1 !=key2不相等，但HashCode(key1)與HashCode(fey2)相等時(shí)，這種現(xiàn)象稱(chēng)為Hash沖突，一般情況下，沖突只能盡可能地少，而不能完全避免。因?yàn)镠ash函數(shù)是從關(guān)鍵字范圍到索引范圍的映射，通常關(guān)鍵字范圍要遠(yuǎn)大于索引范圍，它的元素包括多個(gè)可能的關(guān)鍵字。既然如此，如何處理沖突，則是構(gòu)造Hash表不可不解決的一個(gè)問(wèn)題。

在處理Hash沖突的方法中，通常有開(kāi)放定址法、再Hash法、鏈地址法、建立一個(gè)公共溢出區(qū)等。Dictionary使用的解決沖突方法是拉鏈法，又稱(chēng)鏈地址法。

拉鏈法的原理如下：

將所有關(guān)鍵字為同義詞的節(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。若選定的Hash表長(zhǎng)度為n，則可將Hash表定義為一個(gè)由n個(gè)頭指針組成的指針數(shù)組T[0...n-1]。凡是Hash地址為i的節(jié)點(diǎn)，均插入以T[i]為頭指針的單鏈表中。T中各分量的初值均為空指針。

在Hash表上進(jìn)行查找的過(guò)程與Hash表構(gòu)建的過(guò)程基本一致。

給定Key值，根據(jù)造表時(shí)設(shè)定的Hash函數(shù)求得Hash地址，若表中此位置沒(méi)有記錄，則表示查找不成功；否則比較關(guān)鍵字，若給定值相等，則表示查找成功；否則，根據(jù)處理沖突的方法尋找“下一地址”，直到Hash表中某個(gè)位置為空或者表中所填記錄的關(guān)鍵字等于給定值為止。

我們來(lái)看看更形象的結(jié)構(gòu)圖，如圖2-1所示。

圖2-1　Hash沖突拉鏈法

在圖2-1的Hash沖突拉鏈法結(jié)構(gòu)中，主要的宿主為數(shù)組指針，每個(gè)數(shù)組元素里存放著指向下一個(gè)節(jié)點(diǎn)的指針，如果沒(méi)有元素在單元上，則為空指針。當(dāng)多個(gè)元素都指向同一個(gè)單元格時(shí)，則以鏈表的形式依次存放并列的元素。

2. Dictionary的接口

Dictionary究竟是如何實(shí)現(xiàn)的呢？我們來(lái)剖析一下源碼。

首先看看源碼中Dictionary的變量定義部分，如下：

---

public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary, 
    IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback
{

    private struct Entry {
        public int hashCode;            // 低31位為Hash值，如果未使用則為-1
        public int next;                // 下一個(gè)實(shí)例索引，如果是最后一個(gè)則為-1
        public TKey key;                // 實(shí)例的鍵值
        public TValue value;            // 實(shí)例的值
    }

    private int[] buckets;
    private Entry[] entries;
    private int count;
    private int version;
    private int freeList;
    private int freeCount;
    private IEqualityComparer<TKey>comparer;
    private KeyCollection keys;
    private ValueCollection values;
    private Object _syncRoot;
}

---

從繼承的類(lèi)和接口看，Dictionary主要繼承了IDictionary接口和ISerializable接口。IDictionary和ISerializable在使用過(guò)程中，主要的接口為Add、Remove、ContainsKey、Clear、TryGetValue、Keys、Values，以及以[]數(shù)組符號(hào)形式作為返回值的接口。也包括常用庫(kù)Collection中的接口Count、Contains等。

從Dictionary的定義變量中可以看出，Dictionary是以數(shù)組為底層數(shù)據(jù)結(jié)構(gòu)的類(lèi)。當(dāng)實(shí)例化new Dictionary()后，內(nèi)部的數(shù)組是0個(gè)數(shù)組的狀態(tài)。與List組件一樣，Dictionary也是需要擴(kuò)容的，會(huì)隨著元素?cái)?shù)量的增加而不斷擴(kuò)容。具體來(lái)看看接口源碼剖析。

下面將圍繞上述接口解析Dictionary底層運(yùn)作機(jī)制。

了解Add接口是最直接了解底層數(shù)據(jù)結(jié)構(gòu)如何運(yùn)作的途徑。我們來(lái)看Add接口的實(shí)現(xiàn)，其源代碼如下：

---

public void Add(TKey key, TValue value)
{
    Insert(key, value, true);
}

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;
    entries = new Entry[size];
    freeList = -1;
}

private void Insert(TKey key, TValue value, bool add)
{
    if( key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets == null) Initialize(0);
    int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
    int targetBucket = hashCode % buckets.Length;

#if FEATURE_RANDOMIZED_STRING_HASHING
    int collisionCount = 0;
#endif

    for (int i = buckets[targetBucket]; i>= 0; i = entries[i].next) {
        if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
            if (add) {
                ThrowHelper.ThrowArgumentException(
                    ExceptionResource.Argument_AddingDuplicate);
            }
            entries[i].value = value;
            version++;
            return;
        }

#if FEATURE_RANDOMIZED_STRING_HASHING
        collisionCount++;
#endif
    }
    int index;
    if (freeCount>0) {
        index = freeList;
        freeList = entries[index].next;
        freeCount--;
    }
    else {
        if (count == entries.Length)
        {
            Resize();
            targetBucket = hashCode % buckets.Length;
        }
        index = count;
        count++;
    }

    entries[index].hashCode = hashCode;
    entries[index].next = buckets[targetBucket];
    entries[index].key = key;
    entries[index].value = value;
    buckets[targetBucket] = index;
    version++;

#if FEATURE_RANDOMIZED_STRING_HASHING

#if FEATURE_CORECLR
    // 如果我們觸碰到閾值，則需要切換到使用隨機(jī)字符串Hash的比較器上
    // 在這種情況下，將是EqualityComparer<string>.Default
    // 注意，默認(rèn)情況下，coreclr上的隨機(jī)字符串Hash是打開(kāi)的，所以EqualityComparer<string>.
Default將使用隨機(jī)字符串Hash

    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))
    {
        comparer = (IEqualityComparer<TKey>)
            HashHelpers.GetRandomizedEqualityComparer(comparer);
        Resize(entries.Length, true);
    }
#endif // FEATURE_CORECLR

#endif

}

---

以上展示的代碼稍稍多了點(diǎn)，我們摘出其中的要點(diǎn)，通過(guò)要點(diǎn)來(lái)了解重點(diǎn)，再通過(guò)重點(diǎn)了解全局。

其實(shí)Add接口就是Insert()的代理，它只有Insert()這一個(gè)函數(shù)調(diào)用，那么Insert()函數(shù)做了什么呢？

在加入數(shù)據(jù)前，首先需要對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行構(gòu)造，其代碼如下：

---

if (buckets == null) Initialize(0);

---

在構(gòu)建Dictionary時(shí)，如果沒(méi)有指定任何數(shù)量，buckets就是一個(gè)空的數(shù)組，所以需要對(duì)buckets進(jìn)行初始化，即Initialize(0)，說(shuō)明構(gòu)建的數(shù)量級(jí)最少。

不過(guò)奧妙就在Initialize()函數(shù)里，如果傳入的參數(shù)不是0，而是5、10、25或其他更大的數(shù)，那么構(gòu)造多大的數(shù)據(jù)結(jié)構(gòu)才合適呢？

在Initialize()函數(shù)中給了我們答案，看下面代碼：

---

int size = HashHelpers.GetPrime(capacity);

---

它們有專(zhuān)門(mén)的方法來(lái)計(jì)算到底該使用多大的數(shù)組，從GetPrime字面意思可以猜測(cè)到應(yīng)該跟質(zhì)數(shù)有關(guān)，我們找出源碼HashHelpers，primes數(shù)值的定義如下：

---

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};

public static int GetPrime(int min)
{
    if (min<0)
        throw new ArgumentException(
            Environment.GetResourceString("Arg_HTCapacityOverflow"));
    Contract.EndContractBlock();

    for (int i = 0; i<primes.Length; i++)
    {
        int prime = primes[i];
        if (prime>= min) return prime;
    }

    // 如果在我們的預(yù)定義表之外，則做硬計(jì)算
    for (int i = (min | 1); i<Int32.MaxValue;i+=2)
    {
        if (IsPrime(i) && ((i - 1) % Hashtable.HashPrime != 0))
            return i;
    }
    return min;
}

// 返回要增長(zhǎng)到的Hash表的大小
public static int ExpandPrime(int oldSize)
{
    int newSize = 2 * oldSize;

    // 在遇到容量溢出之前，允許Hash表增長(zhǎng)到最大可能的大小（約2G個(gè)元素）
    // 請(qǐng)注意，即使（item.Length）由于（uint）強(qiáng)制轉(zhuǎn)換而溢出，此檢查仍然有效
    if ((uint)newSize>MaxPrimeArrayLength && MaxPrimeArrayLength>oldSize)
    {
        Contract.Assert( MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength),
            "Invalid MaxPrimeArrayLength");
        return MaxPrimeArrayLength;
    }

    return GetPrime(newSize);
}

---

上述代碼為HashHelpers部分的源碼，其中GetPrime()會(huì)返回一個(gè)需要的size最小的質(zhì)數(shù)值，從GetPrime()函數(shù)的代碼中可以知道這個(gè)size是數(shù)組primes里的值，與當(dāng)前需要的數(shù)量大小有關(guān)，當(dāng)需要的數(shù)量小于primes某個(gè)單元格的數(shù)字時(shí)返回該數(shù)字，而ExpandPrime()則更加簡(jiǎn)單粗暴，直接返回原來(lái)size的2倍作為擴(kuò)展數(shù)量。

從Prime的定義看得出，首次定義size為3，每次擴(kuò)大2倍，也就是3→7→17→37→…底層數(shù)據(jù)結(jié)構(gòu)的大小是按照這個(gè)數(shù)值順序來(lái)擴(kuò)展的，而且每次都是質(zhì)數(shù)。如果你在創(chuàng)建Dictionary時(shí)先定義了它的初始大小，指定的初始大小也會(huì)被GetPrime()計(jì)算為應(yīng)該分配的質(zhì)數(shù)數(shù)量，最終得到應(yīng)該分配的數(shù)組大小。這與List組件的分配方式一模一樣。

我們繼續(xù)看初始化后的內(nèi)容，對(duì)關(guān)鍵字Key做Hash操作，從而獲得地址索引，其源碼如下：

---

int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int targetBucket = hashCode % buckets.Length;

---

當(dāng)調(diào)用函數(shù)獲得Hash值后，還需要對(duì)Hash地址執(zhí)行余操作，以確保索引地址落在Dictionary數(shù)組長(zhǎng)度范圍內(nèi)，而不會(huì)溢出。

接著對(duì)指定數(shù)組單元格內(nèi)的鏈表元素執(zhí)行遍歷操作，找出空出來(lái)的位置將值填入，其源代碼如下：

---

for (int i = buckets[targetBucket]; i>= 0; i = entries[i].next) {
    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
        if (add) {
            ThrowHelper.ThrowArgumentException(
                ExceptionResource.Argument_AddingDuplicate);
        }
        entries[i].value = value;
        version++;
        return;
    }

#if FEATURE_RANDOMIZED_STRING_HASHING
    collisionCount++;
#endif
}

---

這一步就是前面所說(shuō)的拉鏈法的鏈表推入操作。在獲得Hash值的數(shù)組索引后，我們知道了應(yīng)該將數(shù)據(jù)存放在哪個(gè)數(shù)組位置上，如果該位置已經(jīng)有元素被推入，則需要將其推入鏈表的尾部。從for循環(huán)開(kāi)始，檢查是否到達(dá)鏈表的末尾，最后將數(shù)據(jù)放入尾部，并結(jié)束函數(shù)。

如果數(shù)組的空間不夠怎么辦？源碼中體現(xiàn)了這一點(diǎn)：

---

int index;
if (freeCount>0) {
    index = freeList;
    freeList = entries[index].next;
    freeCount--;
}
else {
    if (count == entries.Length)
    {
        Resize();
        targetBucket = hashCode % buckets.Length;
    }
    index = count;
    count++;
}

entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;

---

當(dāng)被用來(lái)記錄剩余單元格數(shù)量的變量freeCount等于0時(shí)，則進(jìn)行擴(kuò)容，擴(kuò)容后的大小就是前面提到的調(diào)用ExpandPrime后的數(shù)量，即通常情況下為原來(lái)的2倍，再根據(jù)這個(gè)空間大小數(shù)字調(diào)用GetPrime()來(lái)得到真正的新數(shù)組的大小。

了解了Add接口，再來(lái)看看Remove部分。

刪除的過(guò)程和插入的過(guò)程類(lèi)似，因?yàn)橐檎襅ey元素所在的位置，所以再次將Key值執(zhí)行Hash操作也是難免的，然后類(lèi)似沿著拉鏈法的模式尋找與關(guān)鍵字匹配的元素。

Remove()使用關(guān)鍵字刪除元素的接口源碼如下：

---

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

    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        int bucket = hashCode % buckets.Length;
        int last = -1;
        for (int i = buckets[bucket]; i>= 0; last = i, i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].
                key, key)) {
                if (last<0) {
                    buckets[bucket] = entries[i].next;
                }
                else {
                    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 = i;
                freeCount++;
                version++;
                return true;
            }
        }
    }
    return false;
}

---

我們注意到，Remove接口相對(duì)于Add接口簡(jiǎn)單得多，同樣使用Hash函數(shù)comparer.GetHashCode()獲得Hash值，再執(zhí)行余操作，確定索引值落在數(shù)組范圍內(nèi)，從Hash索引地址開(kāi)始查找鏈表中的值，查找沖突鏈表中元素的Key值是否與需要移除的Key值相同，若相同，則進(jìn)行移除操作并退出。

注意源碼中Remove()函數(shù)的移除操作并沒(méi)有對(duì)內(nèi)存進(jìn)行刪減，而只是將其單元格置空，這是為了減少內(nèi)存的頻繁操作。

繼續(xù)剖析另一個(gè)重要的接口ContainsKey，即檢測(cè)是否包含關(guān)鍵字的接口。其源碼如下：

---

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()函數(shù)的運(yùn)行是一個(gè)查找Key位置的過(guò)程。它調(diào)用了FindEntry()函數(shù)，F(xiàn)indEntry()查找Key值位置的方法與前面提到的相同。從使用Key值得到的Hash值地址開(kāi)始查找，查看所有沖突鏈表中是否有與Key值相同的值，若找到，即刻返回該索引地址。

有了對(duì)幾個(gè)核心接口理解的基礎(chǔ)，理解其他接口相對(duì)就簡(jiǎn)單多了，我們可快速地學(xué)習(xí)一下。

TryGetValue接口是嘗試獲取值的接口，其源碼如下：

---

public bool TryGetValue(TKey key, out TValue value)
{
    int i = FindEntry(key);
    if (i>= 0) {
        value = entries[i].value;
        return true;
    }
    value = default(TValue);
    return false;
}

---

與ContainsKey()函數(shù)類(lèi)似，它調(diào)用的也是FindEntry()函數(shù)的接口，以此來(lái)獲取Key對(duì)應(yīng)的Value值，并對(duì)[]操作符重定義，其源碼如下：

---

public TValue this[TKey key] {
    get {
        int i = FindEntry(key);
        if (i>= 0) return entries[i].value;
        ThrowHelper.ThrowKeyNotFoundException();
        return default(TValue);
    }
    set {
        Insert(key, value, false);
    }
}

---

在重新定義[]符號(hào)的代碼中，獲取元素時(shí)同樣也會(huì)使用FindEntry()函數(shù)，而Set設(shè)置元素時(shí)，則會(huì)使用與Add調(diào)用相同的Insert()函數(shù)，它們都是同一套方法，即Hash拉鏈沖突解決方案。

從源碼剖析來(lái)看，Hash沖突的拉鏈法貫穿了整個(gè)底層數(shù)據(jù)結(jié)構(gòu)。因此Hash函數(shù)是關(guān)鍵，Hash函數(shù)的好壞直接決定了效率的高低。

既然這么重要，我們來(lái)看看Hash函數(shù)的創(chuàng)建過(guò)程，函數(shù)創(chuàng)建的源碼如下：

---

private static EqualityComparer<T>CreateComparer()
{
    Contract.Ensures(Contract.Result<EqualityComparer<T>>() != null);

    RuntimeType t = (RuntimeType)typeof(T);
    // 出于性能原因?qū)ｉT(mén)用字節(jié)類(lèi)型
    if (t == typeof(byte)) {
        return (EqualityComparer<T>)(object)(new ByteEqualityComparer());
    }
    // 如果T implements IEquatable<T>返回一個(gè)GenericEqualityComparer<T>
    if (typeof(IEquatable<T>).IsAssignableFrom(t)) {
        return (EqualityComparer<T>)
            RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter(
            (RuntimeType)typeof(GenericEqualityComparer<int>), t);
    }
    // 如果T是一個(gè)Nullable<U>從U implements IEquatable<U>返回的NullableEquality
        Comparer<U>
    if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) {
        RuntimeType u = (RuntimeType)t.GetGenericArguments()[0];
        if (typeof(IEquatable<>).MakeGenericType(u).IsAssignableFrom(u)) {
            return (EqualityComparer<T>)
                RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
                RuntimeType)typeof(NullableEqualityComparer<int>), u);
        }
    }

    // 看這個(gè)METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST和METHOD__JIT_HELPERS__UNSAFE_
ENUM_CAST_LONG在getILIntrinsicImplementation中的例子
    if (t.IsEnum) {
        TypeCode underlyingTypeCode = Type.GetTypeCode(
            Enum.GetUnderlyingType(t));

        // 根據(jù)枚舉類(lèi)型，我們需要對(duì)比較器進(jìn)行特殊區(qū)分，以免裝箱
        // 注意，我們要對(duì)Short和SByte使用不同的比較器，因?yàn)閷?duì)于這些類(lèi)型，
        // 我們需要確保在實(shí)際的基礎(chǔ)類(lèi)型上調(diào)用GetHashCode，其中，GetHashCode的實(shí)現(xiàn)比其他類(lèi)型更復(fù)雜
        switch (underlyingTypeCode) {
            case TypeCode.Int16: 
                return (EqualityComparer<T>)
                RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
                RuntimeType)typeof(ShortEnumEqualityComparer<short>), t);
            case TypeCode.SByte:
                return (EqualityComparer<T>)
                RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
                RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), t);
            case TypeCode.Int32:
            case TypeCode.UInt32:
            case TypeCode.Byte:
            case TypeCode.UInt16: 
                return (EqualityComparer<T>)
                RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
                RuntimeType)typeof(EnumEqualityComparer<int>), t);
            case TypeCode.Int64:
            case TypeCode.UInt64:
                return (EqualityComparer<T>)
                    RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((
                    RuntimeType)typeof(LongEnumEqualityComparer<long>), t);
        }
    }
    // 否則，返回一個(gè)ObjectEqualityComparer<T>
    return new ObjectEqualityComparer<T>();
}

---

我們看到，以上源碼對(duì)數(shù)字、byte、有“比較”接口（IEquatable<T>）和沒(méi)有“比較”接口（IEquatable）這四種方式進(jìn)行了區(qū)分。前面說(shuō)的實(shí)例對(duì)象的Hash值是通過(guò)HashCode()函數(shù)來(lái)計(jì)算獲得的，它以?xún)?nèi)存地址為標(biāo)準(zhǔn)計(jì)算得到一個(gè)Hash值，我們也可以重寫(xiě)這個(gè)方法來(lái)計(jì)算自己的Hash值。

對(duì)于數(shù)字和byte類(lèi)，比較容易對(duì)比，所以它們是一類(lèi)。而有“比較”接口（IEquatable<T>）的實(shí)體，則直接使用GenericEqualityComparer<T>來(lái)獲得Hash函數(shù)。最后那些沒(méi)有“比較”接口（IEquatable）的實(shí)體，如果繼承了Nullable<U>接口，則使用一個(gè)叫NullableEquality-Comparer()的比較函數(shù)來(lái)代替。如果什么都不是，就只能使用ObjectEqualityComparer<T>默認(rèn)的對(duì)象比較方式來(lái)做比較了。

在C#里，所有類(lèi)都繼承了Object類(lèi)，因此，即使沒(méi)有特別的重寫(xiě)Equals()函數(shù)，都會(huì)使用Object類(lèi)的Equals()函數(shù)，其源碼如下：

---

public virtual bool Equals(Object obj)
{
    return RuntimeHelpers.Equals(this, obj);
}

[System.Security.SecuritySafeCritical]  
[ResourceExposure(ResourceScope.None)]
[MethodImplAttribute(MethodImplOptions.InternalCall)]
public new static extern bool Equals(Object o1, Object o2);

---

這個(gè)Equals()函數(shù)對(duì)兩個(gè)對(duì)象進(jìn)行比較，是以?xún)?nèi)存地址為基準(zhǔn)的。

Dictionary同List一樣，并不是線程安全的組件，官方源碼中進(jìn)行了這樣的解釋?zhuān)?/p>

---

** Hashtable has multiple reader/single writer (MR/SW) thread safety built into
** certain methods and properties, whereas Dictionary doesn't. If you're
** converting framework code that formerly used Hashtable to Dictionary, it's
** important to consider whether callers may have taken a dependence on MR/SW
** thread safety. If a reader writer lock is available, then that may be used
** with a Dictionary to get the same thread safety guarantee.

---

Hashtable在多線程讀/寫(xiě)中是線程安全的，而Dictionary不是。如果要在多個(gè)線程中共享Dictionary的讀/寫(xiě)操作，就要自己寫(xiě)lock，以保證線程安全。

到這里我們已經(jīng)全面了解了Dictionary的內(nèi)部構(gòu)造和運(yùn)作機(jī)制。它是由數(shù)組構(gòu)成，并且由Hash函數(shù)完成地址構(gòu)建，由拉鏈法沖突解決方式來(lái)解決沖突的。

從效率上看，同List一樣，最好在實(shí)例化對(duì)象，即新建時(shí)，確定大致數(shù)量，這樣會(huì)使得內(nèi)存分配次數(shù)減少，另外，使用數(shù)值方式作為鍵值比使用類(lèi)實(shí)例的方式更高效，因?yàn)轭?lèi)對(duì)象實(shí)例的Hash值通常都由內(nèi)存地址再計(jì)算得到。

從內(nèi)存操作上看，其大小以3→7→17→37→…的速度（每次增加2倍多）增長(zhǎng)，刪除時(shí)，并不縮減內(nèi)存。

如果想在多線程中共享Dictionary，則需要我們自己進(jìn)行l(wèi)ock操作。

Dictionary源碼網(wǎng)址為https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs。