.NET source 系列：System.Collections.Generic.Dictionary

发表于 分类于 ， ， 阅读次数： 本文字数： 15k 阅读时长 ≈ 13 分钟
探究了 .net framework 4.8 下的dictionary及其常见操作实现

System.Collections.Generic.Dictionary

参考版本为 .net framework 4.8

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs

前言

避免犯先入为主的错，先简单 diff 一下和 mono 2.0 有什么不同

附件1：Dictionary from mono-2-0

附件2：Dictionary from .net framework 4.8

diff 结果：

只能说是完全不一样了。哈哈。

.net framework 4.8

reference:

摘要

public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback  {

    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;
    private int count;
    private int version;
    private int freeList;
    private int freeCount;
    private IEqualityComparer<TKey> comparer;
    private KeyCollection keys;
    private ValueCollection values;
    private Object _syncRoot;
    // ...       
}

.NET中的Dictionary实现，是哈希表HashTable和LinkedList的组合，LinkedList被用于处理哈希冲突（拉链法 separate chaining）

  • HashTable是一个用于存储Pair的数据结构，每个Pair都包含Key和Value。
  • HashTable的重要功能就是提供Key之后，要能很快地找到与Key值对应的Value。
  • HashTable会使用hash function来基于Key计算出下标。

Dictionary中最重要的几个组成部分（字段）：

  • buckets(int[])：有相同hashcode的条目归属于同一个bucket。哈希结果取余之后得到这个 buckets 的下标，下标对应位置存储的是元素集合在 entries 中的第一个元素位置
  • entries(Entry[])：Dicionary<TKey, TValue> 的元素集合
  • freeList(int)：第一个空闲位置的下标
  • freeCount(int)：Entry[] 中共有多少个空闲位置
  • count(int)：Dictionary中的内部数组大小，注意并非有效元素个数。有效元素个数通过属性Count返回。
  • version(int)：Dictionary的修改次数，容器的标记

同时Entry也是Dictionary的一个重要结构，包含：

  • Key与Value对象
  • 哈希结果 hashCode
  • next：entries 中相同hashcode的下一个元素下标。如果next值为-1，即表示此元素为相同bucket集合中的最后一个元素

主要行为

构造函数 ctor

若不传入任何参数会以0为默认capacity调用 Initialize() 开辟空间，同时会使用 EqualityComparer<TKey>.Default 作为默认比较器，用于获取HashCode，以及判断Key之间是否相等。

IEqualityComparer 只需要实现两个方法：

// The generic IEqualityComparer interface implements methods to if check two objects are equal
// and generate Hashcode for an object.
// It is use in Dictionary class.  
public interface IEqualityComparer<in T>
{
    bool Equals(T x, T y);
    int GetHashCode(T obj);                
}

Initialize(int capacity)

private void Initialize(int capacity) {
    int size = HashHelpers.GetPrime(capacity);
    buckets = new int[size];
    for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
    entries = new Entry[size];
    freeList = -1;
}

此方法依赖 HashHelpers.GetPrime(int min) 来获取第一个大于capacity的质数。

类型 HashHelpers 中存在静态整型数组 primes，这是一个特别挑出的质数组成的质数表（为什么选了这些质数？值得研究下），以3开始，以7199369结束。若提供的min数字小于 primes 数组中最大值，那么简单地查表就能得到大于它的目标质数。

// system\Collections\hashtable.cs:1711
        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};

// System.Collections.HashHelpers.GetPrime
// system\Collections\hashtable.cs:1754
        public static int GetPrime(int min) 
        {
            if (min < 0)
                throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
            Contract.EndContractBlock();

            for (int i = 0; i < primes.Length; i++) 
            {
                int prime = primes[i];
                if (prime >= min) return prime;
            }

            //outside of our predefined table. 
            //compute the hard way. 
            for (int i = (min | 1); i < Int32.MaxValue;i+=2) 
            {
                if (IsPrime(i) && ((i - 1) % Hashtable.HashPrime != 0))
                    return i;
            }
            return min;
        }

否则，GetPrime() 方法将回退到朴素的质数查找：从 min | 1 开始直到 Int32.MaxValue，进行步长为2的遍历，判断每个数字是否是质数 HashHelpers.IsPrime(int candidate)。注意，这个判断方法涉及平方根操作，与一个时间复杂度为\(\bf{O}(\sqrt{\bf{n}})\)的循环。

// System.Collections.HashHelpers.IsPrime
// system\Collections\hashtable.cs:1738
        public static bool IsPrime(int candidate) 
        {
            if ((candidate & 1) != 0) 
            {
                int limit = (int)Math.Sqrt (candidate);
                for (int divisor = 3; divisor <= limit; divisor+=2)
                {
                    if ((candidate % divisor) == 0)
                        return false;
                }
                return true;
            }
            return (candidate == 2);
        }

插入元素 Add(TKey key, TValue value) / 索引器

public TValue this[TKey key] {
    get {
        int i = FindEntry(key);
        if (i >= 0) return entries[i].value;
        ThrowHelper.ThrowKeyNotFoundException();
        return default(TValue);
    }
    set {
        Insert(key, value, false);
    }
}

public void Add(TKey key, TValue value) {
    Insert(key, value, true);
}

因为Dictionary实现了非泛型版本的IDictionary，所以也有Add(object key, object value)这样的方法，但也只是在Add(TKey key, TValue value)的基础上新增了类型转换和一些错误检查而已。

方法Add(TKey key, TValue value)依赖方法Insert(TKey key, TValue value, bool add)的实现，参数add就是用来区分调用是否来自于Add()方法。在.net源码中看到这样的标识方法还挺意外的…

另外一个依赖方法Insert()的插入元素方法就是使用索引器 this[TKey key]，这时传入的参数add就会是false。一直以来的使用经验也告诉我们传不同参数会带来什么不同了：当调用Add()方法时，若key已存在会抛出异常，而使用索引器能够直接覆盖此key对应的内容。

插入元素 Insert(TKey key, TValue value, bool add)

Insert() 方法将新元素插入到entries中，选择性地使用freeList，相应地更新buckets，并且可能造成扩容行为。

若当前的buckets在Dictionary构造后还没有进行过初始化，那么会使用0作为初始容量进行初始化，按照上面的信息，我们应该能得到一个大小为3的buckets。

获取buckets中下标

插入的元素通过comparer以及自己的key得到hashcode后，通过对buckets.Length取余得到目标bucket在数组中的下标targetBucket。

查找entries中下标

for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
        if (add) { 
            ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
        }
        entries[i].value = value;
        version++;
        return;
    } 
    
    // 记录发生冲突的次数，这实际上是用于 FEATURE_RANDOMIZED_STRING_HASHING
    collistionCount++;
}

接下来会通过一个在Dictionary实现中很常见的循环，来查找是否存在一个hashcode与key均相等的元素，如果存在则说明添加了key重复的value，便根据此次Insert是否来源于Add来决定是要抛出异常，还是覆盖原值并更新version。

若不存在这样的元素，那么便可以考虑将新元素加入到Dictionary中：

  • 如果freeCount尚有剩余，那么使用freeList的队首元素下标，freeList队首后移，更新freeCount，而不更新count
  • 否则直接使用当前元素count为下标索引entries，更新count
    • 注意，当entries已满时（count == entries.Length），发生扩容Resize()以及targetBucket的重新计算，毕竟现在的buckets.Length已经不同了
entries[index].hashCode = hashCode;
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
buckets[targetBucket] = index;
version++;

最后，通过上述步骤得到的index，设置entries[index]的各种key / hashcode / value信息，将此entries[index]设置为targetBucket的队首（buckets[targetBucket] → new_entry.next → previous_entry）。

FEATURE_RANDOMIZED_STRING_HASHING

如果上述提到的冲突次数大于HashHelpers.HashCollisionThreshold（100）次，且当前comparer被判定为“WellKnownEqualityComparer”，则会为当前Dictionary选择一个RandomziedEqualityComparer，之后对Dictionary进行Resize，并且forceNewHashCodes，使用新的comparer来计算hashcode

举例在mscorlib中就能找到System/StringComparer.cs，其中包含了 CultureAwareRandomizedComparer，OrdinalRandomizedComparer 等comparer，这里就先不展开了。

扩容 Resize()

Resize() 方法会用一个大于当前元素个数两倍的质数，来对当前字典进行扩容。

默认无参的Resize()方法会根据当前的有效元素个数count，调用方法 HashHelpers.ExpandPrime。

HashHelpers.ExpandPrime(int oldSize) 的行为逻辑为简单地将 oldSize x 2 得到 newSize，做一个越界检查（此处对比的常量为 HashHelpers.MaxPrimeArrayLength / 0x7FEFFFFD / 2146435069），接着并将 newSize 传入方法 HashHelpers.GetPrime 得到比它更大的质数，最后将此结果用于调用方法 Resize(int newSize, bool forceNewHashCodes)。

扩容 Resize(int newSize, bool forceNewHashCodes)

private void Resize(int newSize, bool forceNewHashCodes) {
    Contract.Assert(newSize >= entries.Length);
    int[] newBuckets = new int[newSize];
    for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
    Entry[] newEntries = new Entry[newSize];
    Array.Copy(entries, 0, newEntries, 0, count);
    if(forceNewHashCodes) {
        for (int i = 0; i < count; i++) {
            if(newEntries[i].hashCode != -1) {
                newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
            }
        }
    }
    // pay attention to this loop
    for (int i = 0; i < count; i++) {
        int bucket = newEntries[i].hashCode % newSize;
        newEntries[i].next = newBuckets[bucket];
        newBuckets[bucket] = i;
    }
    buckets = newBuckets;
    entries = newEntries;
}

方法内部按照新的size大小开辟了两个新数组，分别是 buckets 和 entries。buckets的每个成员都会被初始化为-1。而对 entries，则是先进行了已有 count 个条目的 Array.Copy。

如果方法传入了forceNewHashCodes，那么每个entry的hashcode都会基于字典内部的comparer以及entry的key重新计算一遍。

很有意思的是方法内部通过一个循环来重置了Resize操作后的buckets以及entries链表，而循环体的实现可以同时应对两种情况：

  • 对那些对应bucket为空的entry，entry的next会被设置为-1，之后这个bucket会指向这个entry；
  • 对那些对应bucket不为空的entry（即存在其他相同hashcode的entry），entry的next会被设置为bucket指向的同hashcode entry，随后bucket同样会指向这个entry。

这样一来，新的entry总是被插入到bucket指向的队首。

移除元素 Remove(TKey key)

public bool Remove(TKey key) {
    if(key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        int bucket = hashCode % buckets.Length;
        int last = -1;
        for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                if (last < 0) {
                    buckets[bucket] = entries[i].next;
                }
                else {
                    entries[last].next = entries[i].next;
                }
                entries[i].hashCode = -1;
                entries[i].next = freeList;
                entries[i].key = default(TKey);
                entries[i].value = default(TValue);
                freeList = i;
                freeCount++;
                version++;
                return true;
            }
        }
    }
    return false;
}

当Remove操作发生时：

维护 buckets / entries 链表：

  • 如果移除的entry是此hashcode对应的bucket指向的首个entry，那么需要更新bucket的值
  • 如果不是bucket指向的entry，那么需要更新同hashcode的指向这个entry的上一entry存储的next

维护空闲队列，freeList / freeCount 更新操作发生：

  • 被移除的entry，其next会指向当前freeList，即旧的freeList队首
  • freeList指向被移除的entry，此空闲entry现在变成freeList的队首元素
  • freeCount / version 递增

注意也是这个方法内表明了， 当Entry被移除时，hashCode会被标记为-1，这也是根据comparer获取HashCode后总是要取低31位的原因。

查找元素 ContainsKey(TKey key) / ContainsValue(TValue value)

ContainsKey 的实现是基于方法 FindEntry(TKey key) 的，而 ContainsValue 的实现是一个简单的对entries的遍历，对于非null的目标value，会使用当前TValue类型的DefaultEqualityComparer进行比较。

FindEntry(TKey key) 的实现是先基于key获取hashcode，再从buckets索引到entries的起始位置，接下来根据每个entry的next遍历整个数组中的链表，进行key的相等判定。

对字典的直接索引方法 dict[key] 也是基于方法 FindEntry(TKey key) 的，这里就不赘述了，唯一需要注意的是索引方法在找不到对应key时会直接抛出异常，想要安全的获取值，推荐的是下述TryGetValue方法。

public TValue this[TKey key] {
    get {
        int i = FindEntry(key);
        if (i >= 0) return entries[i].value;
        ThrowHelper.ThrowKeyNotFoundException();
        return default(TValue);
    }
    set {
        Insert(key, value, false);
    }
}

获取元素 TryGetValue(TKey key, out Tvalue value)

TryGetValue 方法同样基于 FindEntry(TKey key)，只是其结果通过 out 关键字返回，而key是否在字段中的结果会使用bool结果返回。

迭代器 Enumerator

字典中存在三个可遍历的对象，分别是 Dictionary<TKey,TValue>.Enumerator，Dictionary<TKey,TValue>.KeyCollection，以及 Dictionary<TKey,TValue>.ValueCollection 分别可通过字典的 GetEnumerator，以及 Keys，Values 属性返回。

其中 Dictionary<TKey,TValue>.Enumerator 为struct，而KeyCollection与ValueCollection均为class，且存在相应的内部成员，会在第一次获取的时候发生实例化及堆内存分配。KeyCollection 与 ValueCollection 均存在自己的内部 Enumerator 声明。

值得一提的是三者的 Dispose() 方法中均为空，没有重要弃置的外部资源。

Dictionary<TKey,TValue>.Enumerator

持有当前dictionary引用。

调用方法 MoveNext() 时会基于 entries 进行遍历，遍历过程中只有 hashcode ≥ 0 的条目会被返回，即只会遍历有效条目。方法内会将 version，遍历下标 index，以及当前KeyValuePair<TKey, TValue> (struct) 作为自身成员保存。

当前遍历的键值对为struct，可不用担心堆内存分配，此结果被保存在 current 成员中，也是 Current 属性的返回结果。

KeyCollection / ValueCollection

两者返回的Enumerator，及其遍历过程均与字典自身返回KeyValuePair的Enumerator无太大差异，下面直接贴上代码进行比较。

// Dictionary<TKey,TValue>.Enumerator.MoveNext
public bool MoveNext() {
    // ...

    // 使用uint转换比较，可以保证即使dicionary.count为Int32.MaxValue，
    // 遍历结束后将index设置为count+1（int下为负值），后续也不会通过这个判断式进入while块
    while ((uint)index < (uint)dictionary.count) {
        if (dictionary.entries[index].hashCode >= 0) {
            current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value);
            index++;
            return true;
        }
        index++;
    }

    index = dictionary.count + 1;
    current = new KeyValuePair<TKey, TValue>();
    return false;
}

    // Dictionary<TKey,TValue>.KeyCollection.Enumerator.MoveNext
    public bool MoveNext() {
        // ...

        while ((uint)index < (uint)dictionary.count) {
            if (dictionary.entries[index].hashCode >= 0) {
                currentKey = dictionary.entries[index].key;
                index++;
                return true;
            }
            index++;
        }

        index = dictionary.count + 1;
        currentKey = default(TKey);
        return false;
    }
    
    // Dictionary<TKey,TValue>.ValueCollection.Enumerator.MoveNext
    public bool MoveNext() {                    
        if (version != dictionary.version) {
            ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
        }
        
        while ((uint)index < (uint)dictionary.count) {
            if (dictionary.entries[index].hashCode >= 0) {
                currentValue = dictionary.entries[index].value;
                index++;
                return true;
            }
            index++;
        }
        index = dictionary.count + 1;
        currentValue = default(TValue);
        return false;
    }

可借鉴之处

记录一些在阅读 .net framework 4.8 的 Dictionary 源码过程中，觉得未来在设计数据结构可以参照学习的要点:

  • 存储Dictionary的Value的实体Entry被设计为了值类型，而不是引用类型。一般而言，对于基本的数据类型或者纯字段或者小于16个字节的，设计为struct，而不是class能够明显提高内存局部性，并且能极大减少GC压力。
  • 特别地，相比class数组，struct数组的内存局部性有极大的优势。
  • 删除Dictionary某个key对应的元素，只是将entries中对应的元素移到了空闲列表中，在下次插入时，优先把数据分配到空闲列表上。这样一定程度上能减少page交换，和新的内存注销和分配。
  • 这种技巧在C++编程语言中广泛存在，由于在非托管语言中，内存的注销和分配是一个相对来说比较耗资源的操作，所以这种内存留用操作非常普遍。
  • 在判断链表是否到达尽头时，即next是否为-1时，对于普通储值的链表，直接将-1转换为uint，然后跟entries的length做比较，这里利用了负数转为无符号整型会溢出成为非常大的整数的特性。

mono 2.0 Dictionary Allocation

在这里额外记录一个个人觉得在比较过时的.NET环境开发中需要注意的点，就是字典在初始化以及扩容时带来的较大内存开销，从初始化的两个重要方法中我们可以看到：

const int INITIAL_SIZE = 10;
const float DEFAULT_LOAD_FACTOR = (90f / 100);

private void Init (int capacity, IEqualityComparer<TKey> hcp)
{
    if (capacity < 0)
        throw new ArgumentOutOfRangeException ("capacity");
    this.hcp = (hcp != null) ? hcp : EqualityComparer<TKey>.Default;
    if (capacity == 0)
        capacity = INITIAL_SIZE;

    /* Modify capacity so 'capacity' elements can be added without resizing */
    capacity = (int)(capacity / DEFAULT_LOAD_FACTOR) + 1;
    
    InitArrays (capacity);
    generation = 0;
}

private void InitArrays (int size) {
    table = new int [size];

    linkSlots = new Link [size];
    emptySlot = NO_SLOT;

    keySlots = new TKey [size];
    valueSlots = new TValue [size];
    touchedSlots = 0;

    threshold = (int)(table.Length * DEFAULT_LOAD_FACTOR);
    if (threshold == 0 && table.Length > 0)
        threshold = 1;
}

可以看到一般来说若没有传入初始容量，或者传入0，直接的结果就是导致计算初始容量时将得到12，且在InitArrays中将分配四个数组，分别负责：

  1. table：存储取余后的hashcode，到linkSlots下标的映射，这个下标同样用于索引keySlots与valueSlots。
  2. linkSlots：存储计算hashcode结果以及next信息
  3. keySlots：键内容的存储数组
  4. valueSlots：值内容的存储数组

因此如果有把握此字典被插入的元素并不多（甚至仅有一个元素），或许可以考虑一开始就传入初始容量1，这样至少分配的数组的大小是最小的。

测试代码示例：

public class DictionaryAllocationTest : MonoBehaviour
{
    private Dictionary<uint, GameObject> m_Objects;
    // Start is called before the first frame update
    void Start()
    {
        m_Objects = new Dictionary<uint, GameObject>();
        for (int i = 0; i < 14; i++)
        {
            m_Objects.Add((uint)i, null);
        }
    }
}

Start() 中构造函数执行完毕，尚未进行元素插入的debug结果：

而当插入12个元素后，内部数组将同步扩容到37：

而在上述更新版本的字典实现中，无论是初始化大小，还是扩容速度，都要更为保守。

因此需要注意当自己在版本老旧的.NET环境开发，且代码运行在内存资源吃紧的场景下时，要慎用Dictionary。