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

2019-11-17 02:29:16

字體：大中小

供稿：網(wǎng)友

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

一、前言

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

二、Dictionary源碼剖析

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

　　2.1 添加元素

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

// buckets是哈希表，用來存放Key的Hash值        // entries用來存放元素列表        // count是元素?cái)?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; // 計(jì)算key值對應(yīng)的哈希值(HashCode)            int targetBucket = hashCode % buckets.Length; // 對哈希值求余，獲得需要對哈希表進(jìn)行賦值的位置#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++;            }            // 對元素列表進(jìn)行賦值            entries[index].hashCode = hashCode;            entries[index].next = buckets[targetBucket];            entries[index].key = key;            entries[index].value = value;            // 對哈希表進(jìn)行賦值            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        }

　　下面以一個(gè)實(shí)際的添加例子來具體分析下上面的添加元素代碼，從而更好地理解Add方法的實(shí)現(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");

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

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

　　2.2 解決沖突

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

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

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

public TValue this[TKey key]        {            get            {                int i = FindEntry(key);                // 通過元素所在存在的位置直接獲取其對應(yīng)的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值對應(yīng)的哈希值                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;                // 查找元素在元素列表中的位置，如果沒有沖突的情況下，此時(shí)查找速度為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之所以能實(shí)現(xiàn)快速查找元素，其內(nèi)部使用哈希表來存儲元素對應(yīng)的位置，然后我們可以通過哈希值快速地從哈希表中定位元素所在的位置索引，從而快速獲取到key對應(yīng)的Value值。