[C#進階系列]專題二：你知道Dictionary查找速度為什么快嗎？

一、前言

　　在之前有一次面試中，被問到你了解Dictionary的內(nèi)部實現(xiàn)機制嗎？當時只是簡單的了問答了：Dictionary的內(nèi)部結構是哈希表，從而可以快速進行查找。但是對于更深一步了解就不清楚了。所以面試回來之后，就打算好好研究下Dictionary的源碼。所以也就有了這篇文章。

二、Dictionary源碼剖析

 　　大家都知道，現(xiàn)在微軟已經(jīng)開源了.NET Framework的源碼了，在線源碼查看地址為：http://referencesource.microsoft.com/。通過查找可以找到.NET Framework類的源碼。下面我們就一起來看下Dictionary源碼。

　　2.1 添加元素

　　首先我們來查看下Dictionary.Add方法的實現(xiàn)。為了讓大家更好地實現(xiàn)，下面抽取了Dictionary源碼核心部分來進行分析，詳細的分析代碼如下所示：

// buckets是哈希表，用來存放Key的Hash值
        // entries用來存放元素列表
        // count是元素數(shù)量
        private void Insert(TKey key, TValue value, bool add)
        {
            if (key == null)
            {
                throw new ArgumentNullException(key.ToString());
            }
            // 首先分配buckets和entries的空間
            if (buckets == null) Initialize(0);
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; // 計算key值對應的哈希值(HashCode)
            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)
                    {
                        throw new ArgumentNullException();
                    }
                    entries[i].value = value;
                    version++;
                    return;
                }

#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount++;
#endif
            }

            int index; // index記錄了元素在元素列表中的位置
            if (freeCount > 0)
            {
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else
            {
                // 如果哈希表存放哈希值已滿，則重新從primers數(shù)組中取出值來作為哈希表新的大小
                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(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 
            {
                comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
                Resize(entries.Length, true);
            }
#endif
        }

    下面以一個實際的添加例子來具體分析下上面的添加元素代碼，從而更好地理解Add方法的實現(xiàn)原理。

Dictionary<int, string> myDictionary = new Dictionary<int, string>();
            myDictionary.Add(1, "Item 1");
            myDictionary.Add(2, "Item 2");
            myDictionary.Add(3, "Item 3");

    當添加第一個元素時，此時會分配哈希表buckets數(shù)組和entries數(shù)組的空間和初始大小為3，分配完成之后，會計算添加元素key值的哈希值，哈希值的計算由具體的哈希算法來實現(xiàn)的，假設1的哈希值為9的話，此時targetBucket = 9%buckets.Length(3)的值為0，index的值為0，則第一個元素存放在entries列表中的第一個位置，最后對哈希表進行賦值，此時賦值的位置為第0個位置，其值為index的值，所以為0，插入第一個元素后Dictionary的內(nèi)部結構如下所示：

　　后面添加元素的過程依次類推。其原理就是，buckets記錄了元素的在元素列表的存儲位置，也就相當于一個映射列表。在查找的時候，就可以通過key值的哈希值來與buckets數(shù)組長度求余來獲得元素在元素列表中的索引，這樣就可以快速定位元素的位置，從而獲得元素的key對應的Value值。如上面的例子中，如果想找到key值為1對應的Value值時，此時計算1的哈希值為9，然后對buckets數(shù)組長度求余，此時獲得的值正是0，這樣就可以直接從entries[0].Value的方式來獲取對應的Value的值，這也就是Dictionary能完成快速查找的實現(xiàn)原理。后面會通過Dictionary內(nèi)部的查找源碼來證實上面分析的過程。

　　2.2 解決沖突

　　在添加元素過程中，有一個很重要的問題，如果產(chǎn)生沖突怎么辦？即如果我后面需要插入的一個元素(假設這個值為11吧)的key值的哈希值也為6，此時targetBucket的值也是為0，但元素列表中0的位置已經(jīng)存放了元素了，這樣就出現(xiàn)了沖突，那Dictionary是怎樣處理這個沖突的呢？處理沖突的方法有很多種，Dictionary處理的方式是鏈接法。Dictionary會把發(fā)生沖突的元素鏈接之前元素的后面，通過next屬性來指定沖突關系。此時Dictionary內(nèi)部結構如下圖所示：

三、Dictionary如何實現(xiàn)快速查找呢？

　　針對于Dictionary實現(xiàn)快速查找的原因，在上面我們已經(jīng)做了一個推斷了，下面通過Dictionary內(nèi)部的代碼實現(xiàn)來驗證下，具體的查找代碼如下所示：

public TValue this[TKey key]
        {
            get
            {
                int i = FindEntry(key);
                // 通過元素所在存在的位置直接獲取其對應的Value
                if (i >= 0) return entries[i].value;
                throw new KeyNotFoundException();
                return default(TValue);
            }
            set
            {
                Insert(key, value, false);
            }
        }

        private int FindEntry(TKey key)
        {
            if (key == null)
            {
                throw new ArgumentNullException();
            }

            if (buckets != null)
            {
                // 獲得Key值對應的哈希值
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                // 查找元素在元素列表中的位置，如果沒有沖突的情況下，此時查找速度為O(1),存在沖突的情況下為O(N),N為存在沖突的次數(shù)
                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;
        }

    通過代碼可以看出，我們之前的分析是完成正確的。從中可以明白：Dictionary之所以能實現(xiàn)快速查找元素，其內(nèi)部使用哈希表來存儲元素對應的位置，然后我們可以通過哈希值快速地從哈希表中定位元素所在的位置索引，從而快速獲取到key對應的Value值。

四、總結

 　　可以說，Dictionary的實現(xiàn)原理也是一種空間換時間的思路，多使用一個buckets的存儲空間來存儲元素的位置，從而來提升查找速度。

　　 本文所有×××：DictonaryInDepth.zip