通过.net core源码看下Dictionary的实现

电玩女神 2021-06-26 16:06 296阅读 0赞

**.net core的代码位置**  
[https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/Dictionary.cs][https_github.com_dotnet_corefx_blob_master_src_Common_src_CoreLib_System_Collections_Generic_Dictionary.cs]

`C#`中，`Dictionary`这个数据结构并不是很容易理解，因为看上不去并不像`C++`的`map`。底层是如何实现一个字典的并完全可知，因为从数据结构来说，很多结构都可以支持一个类似的加速`key-value`对存储的访问形式。比如`tree`，跳表，`hashtable`等等。

## 基于`bucket`的`Hashtable` ##

`Dictionary`的基本思想是通过一个`Entry`数值存储数据（`key`和`value`），其中的数据是紧密排布的。然后，通过`bucket`数组实现`hashcode`加速查找。如果两个对象的`hashcode%length`（数值的长度）相等，实现类似`hashtable`碰撞的退避规则，并通过`Entry.next`的引用住新的退避位置（用数组下标实现连接）。

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;
                private Entry[] _entries;

![在这里插入图片描述][20190115220932360.png]  
一个`key-value`数据，在经过`Key.GetHashCode`后的返回值，再对`_buckets`的长度取模。决定隐射到的`_buckets`下标，而实际存储的区域`_entries`是一个连续存储的数组，用来存储键值对（`Entry`）。如上图，如果插入时出现`hash`桶碰撞，会直接找到下一个空的格子插入数据，并把这个格子的`id`保存到上一个`entry.next`中，方便删除或查找时使用。

反之，如果删除数据时，就需要级联更新`entry.next`的情况。删除的关键代码如下，如果是一个通过`next`找到的`entry`，那`last`必然`>0`，所以需要把`last.next`指向自己的`next`，绕过自己。如果`last<0`则说明，自己是第一个元素，直接更新`bucket`指向自己的`next`（可能是`-1`，也可能是真的下一个元素的下标）。

if (last < 0)
                { 
                    // Value in buckets is 1-based
                    buckets[bucket] = entry.next + 1;
                }
                else
                { 
                    entries[last].next = entry.next;
                }

## 关于`Keys`和`Values` ##

private KeyCollection _keys;
    private ValueCollection _values;

许多时候，我们会用到对`Keys`和`Values`的访问。那我们来看看，这两个属性是如何实现的。先看一下`KeyCollection`的实现。这里删除了一些多余的代码，可以看出，他仅仅对`dict`的一个组合关系，内部的实际工作者是`dict`。

public sealed class KeyCollection : ICollection<TKey>, ICollection, IReadOnlyCollection<TKey>
                { 
                    private Dictionary<TKey, TValue> _dictionary;
         
                    public KeyCollection(Dictionary<TKey, TValue> dictionary)
                    { 
                        _dictionary = dictionary;
                    }
         
                    void ICollection<TKey>.Add(TKey item)
                        => ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
         
                    void ICollection<TKey>.Clear()
                        => ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet);
         
                    bool ICollection<TKey>.Contains(TKey item)
                        => _dictionary.ContainsKey(item);
                }

然后，看一下迭代过程的实现。非常简单，仅仅是每次都把`_currentKey`赋值为`_entries`的下一个元素。所以，可以看出来，`Keys`的访问是有序的（按插入顺序）。

public bool MoveNext()
                { 
                    while ((uint)_index < (uint)_dictionary._count)
                    { 
                        ref Entry entry = ref _dictionary._entries[_index++];
         
                        if (entry.hashCode >= 0)
                        { 
                            _currentKey = entry.key;
                            return true;
                        }
                    }
         
                    _index = _dictionary._count + 1;
                    _currentKey = default;
                    return false;
                }

`values`和`keys`的实现是完全一致的，所以`Values`的访问和`Keys`的访问性能是差不多的，不存在访问`Keys`快，访问`Values`慢的情况。

## 关于空间大小算法 ##

大家知道`hash`表是需要先分配一块比较大的空间，并在保持一定数据密度的情况下，会拥有比较高的存储和访问效率。

`C#`的`dict`，永远会去找当前需求的`capacity`的下一个素数，作为数组的分配`size`。如果，默认`new Dict`，传递的`capacity`是`0`，那么实际此时的`_entries`大小是`3`。

找素数的逻辑稍微提下。会先顺序遍历存储的`primes`数组；如果找不到，再用逐个数字遍历的方式找接下来的素数。

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

## 关于读取数据的效率 ##

题外话，讲一下有的同学喜欢这么写数据访问的代码。

if (techAddonDict.ContainsKey(3))
    { 
      var c = techAddonDict[3];
    }

从底层来说，所有查找的代码，都会先通过`bucket`找到一次`entry`对象（通过`FindEntry`函数）。那么上一段函数中实际需要访问两次`FindEntry`函数。

float v;
    if (techAddonDict.TryGetValue(3, out v))
    { 
       //todo xxx
    }

这段函数就很明显了，只需要访问一次`FindEntry`函数，性能自然会好一倍。

[https_github.com_dotnet_corefx_blob_master_src_Common_src_CoreLib_System_Collections_Generic_Dictionary.cs]: https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/Dictionary.cs
[20190115220932360.png]: /images/20210626/405c83610d17434b8f2cc8c34af1d8fd.png