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

时间：2022-04-26 11:46:41

.net core的代码位置

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;

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

    一个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 < )

        {

            // Value in buckets is 1-based

            buckets[bucket] = entry.next + ;

        }

        else

        {

            entries[last].next = entry.next;

        }
  •         

关于Keys和Values

  1.  
    private KeyCollection _keys;
  2.  
    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 >= )

{

_currentKey = entry.key;

return true;

}

}

_index = _dictionary._count + ;

_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 = {

, , , , , , , , , , , , , , , , , , , , , , ,

, , , , , , , , , , , , , , ,

, , , , , , , , , , , , ,

, , , , , , , , , , , ,

, , , , , , , ,  };

关于读取数据的效率

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

 
if (techAddonDict.ContainsKey())

{

var c = techAddonDict[];

}

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

 

float v;

if (techAddonDict.TryGetValue(3, out v))
{

//todo xxx

}

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

相关文章