程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> [C#進階系列]專題二：你知道Dictionary查找速度為什麼快嗎？，

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

編輯：C#入門知識

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

一、前言

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

二、Dictionary源碼剖析

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

　　2.1 添加元素

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

// buckets是哈希表，用來存放Key的Hash值
        // entries用來存放元素列表
        // count是元素數量
        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數組中取出值來作為哈希表新的大小
                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方法的實現原理。

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

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

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為存在沖突的次數 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之所以能實現快速查找元素，其內部使用哈希表來存儲元素對應的位置，然後我們可以通過哈希值快速地從哈希表中定位元素所在的位置索引，從而快速獲取到key對應的Value值。