C# Dictionary源码分析

关键属性

public class Dictionary<TKey, TValue> : 
    IDictionary<TKey, TValue>, 
    IDictionary, 
    IReadOnlyDictionary<TKey, TValue>, 
    ISerializable, 
    IDeserializationCallback 
    where TKey : notnull
{
    // 存储哈希桶的索引数组，用于快速定位 Entry 的位置。
    // 每个 bucket 对应一个哈希值 % _buckets.Length 的结果，
    // 指向 entries 中该哈希值对应的第一项。
    private int[]? _buckets;

    private Entry[]? _entries;

    // 当前字典中实际存储的键值对数量（即有效元素的数量）
    private int _count;

    // 空闲链表的头指针，指向 _entries 中第一个空闲的位置的真实索引。
    // 初始化为-1。
    private int _freeList;

    // 空闲槽位的数量（即 _entries 中尚未使用的条目数）
    private int _freeCount;

    // 字典的版本号，用于在遍历时检测集合是否被修改，防止并发修改异常。
    private int _version;

    // 用于比较 TKey 是否相等的比较器接口实例。
    // 如果没有自定义比较器，则使用默认的 EqualityComparer<TKey>.Default。
    private IEqualityComparer<TKey>? _comparer;

    // 缓存的键集合，用于 Keys 属性访问，避免每次调用时都新建 KeyCollection 实例。
    private KeyCollection? _keys;

    // 缓存的值集合，用于 Values 属性访问，避免每次调用时都新建 ValueCollection 实例。
    private ValueCollection? _values;

    // 其他成员省略...
}

其中Entry的结构如下

private struct Entry
{
    public uint hashCode;
    public int next;
    public TKey key;    
    public TValue value; 
}

当指定大小和比较器创建时

public Dictionary(int capacity, IEqualityComparer<TKey>? comparer)
{
    if (capacity < 0)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
    }

    // 如果容量大于 0，则初始化内部结构（分配哈希表空间）
    if (capacity > 0)
    {
        Initialize(capacity); // 实际上会创建 buckets 和 slots 数组
    }

    // 判断 TKey 是否是引用类型
    if (!typeof(TKey).IsValueType)
    {
        // 对于引用类型，我们总是希望存储一个比较器实例：
        // - 如果用户提供了比较器，则使用它；
        // - 否则使用 EqualityComparer<TKey>.Default。
        // 这样做的原因是：对于引用类型，在每次访问字典时都调用 EqualityComparer<TKey>.Default
        // 可能会有性能开销（尤其是在泛型共享的情况下）。
        _comparer = comparer ?? EqualityComparer<TKey>.Default;

        // 特殊处理字符串类型的比较器：
        // 如果 TKey 是 string 类型，并且当前比较器是 StringComparer.Ordinal 或者 
        // StringComparer.OrdinalIgnoreCase，或者就是 EqualityComparer<string>.Default，
        // 那么我们可以使用一个非随机化的字符串比较器来提高性能。
        // 当 hash 冲突严重时，会自动切换回随机化比较器以防止 DoS 攻击。
        if (typeof(TKey) == typeof(string) &&
            NonRandomizedStringEqualityComparer.GetStringComparer(_comparer!) is IEqualityComparer<string> stringComparer)
        {
            _comparer = (IEqualityComparer<TKey>)stringComparer;
        }
    }
    else // TKey 是值类型的情况
    {
        // 对于值类型，只有当提供了非默认的比较器时才存储它。
        // 如果没有提供或提供的就是默认比较器，则不保存到 _comparer 中，
        // 而是在实际使用时直接调用 EqualityComparer<TKey>.Default.Equals 方法。
        // 这样可以让 JIT 编译器进行虚方法去虚拟化（devirtualization）并可能内联 Equals 方法，
        // 从而提升性能。

        if (comparer is not null && // 先判断是否为 null，避免不必要的默认比较器创建
            comparer != EqualityComparer<TKey>.Default)
        {
            _comparer = comparer;
        }
    }
}

默认创建时

public Dictionary() : this(0, null) { }

指定大小创建时

public Dictionary(int capacity) : this(capacity, null) { }

一、Add方法

1.代码解析

 public void Add(TKey key, TValue value)
 {
     bool modified = TryInsert(key, value, InsertionBehavior.ThrowOnExisting);
     Debug.Assert(modified); // If there was an existing key and the Add failed, an exception will already have been thrown.
 }

TryInsert方法

private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
{
    // 注意：这个方法在 CollectionsMarshal.GetValueRefOrAddDefault 中也有镜像实现。
    // 如果修改了这里，请同步更新另一处代码以保持一致性。
    
    if (key == null)
    {
        // 键不能为 null，否则抛出 ArgumentNullException
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (_buckets == null)
    {
        // 如果哈希桶未初始化，则进行初始化（容量为0表示延迟分配）
        Initialize(0);
    }
    Debug.Assert(_buckets != null); // 确保此时 _buckets 不为 null

    Entry[]? entries = _entries;
    Debug.Assert(entries != null, "expected entries to be non-null");

    // 获取当前使用的比较器
    IEqualityComparer<TKey>? comparer = _comparer;

    // 对于引用类型必须有比较器（Debug 断言）
    Debug.Assert(comparer is not null || typeof(TKey).IsValueType);

    // 计算 key 的哈希值：
    // - 如果是值类型且没有自定义比较器，直接调用 GetHashCode()
    // - 否则使用比较器的 GetHashCode()
    uint hashCode = (uint)((typeof(TKey).IsValueType && comparer == null) 
        ? key.GetHashCode() 
        : comparer!.GetHashCode(key));

    // 冲突计数器，用于检测链表循环（并发问题）
    uint collisionCount = 0;

    // 获取该哈希值对应桶的位置（ref 表示可直接修改桶的内容）
    ref int bucket = ref GetBucket(hashCode);

    // 当前 entry 的索引，_buckets 存储的是 1-based 的索引（+1 是为了区分 0 和 null）
    int i = bucket - 1;

    // 值类型优化路径（允许 JIT 消除引用类型的分支）
    if (typeof(TKey).IsValueType && comparer == null)
    {
        // 当 i == -1(末尾)时，(uint)i 是一个非常大的数，肯定大于等于 entries.Length，因此循环条件不成立，循环终止。
        while ((uint)i < (uint)entries.Length)
        {
            // 如果 hash 相同，并且键相等（使用默认比较器判断）
            if (entries[i].hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i].key, key))
            {
                // 根据插入行为决定如何处理重复键
                if (behavior == InsertionBehavior.OverwriteExisting)
                {
                    entries[i].value = value; // 覆盖旧值
                    return true;
                }

                if (behavior == InsertionBehavior.ThrowOnExisting)
                {
                    // 抛出“添加重复键”的异常
                    ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
                }

                // 其他情况（如 Ignore），返回 false 表示插入失败
                return false;
            }

            // 遍历冲突链表
            i = entries[i].next;

            // 冲突计数增加
            collisionCount++;

            // 如果冲突次数超过数组长度，说明可能出现了环（并发写入）
            if (collisionCount > (uint)entries.Length)
            {
                ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
            }
        }
    }
    else
    {
        // 引用类型路径，或者使用了自定义比较器的情况
        Debug.Assert(comparer is not null);

        while ((uint)i < (uint)entries.Length)
        {
            // 使用自定义比较器判断键是否相同
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
            {
                if (behavior == InsertionBehavior.OverwriteExisting)
                {
                    entries[i].value = value;
                    return true;
                }

                if (behavior == InsertionBehavior.ThrowOnExisting)
                {
                    ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
                }

                return false;
            }

            i = entries[i].next;

            collisionCount++;
            if (collisionCount > (uint)entries.Length)
            {
                ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
            }
        }
    }

    // 执行到这里说明没有找到重复的键，准备插入新项

    int index;

    // 如果有空闲槽位（_freeCount > 0），优先复用这些位置
    if (_freeCount > 0)
    {
        index = _freeList; // 获取第一个空闲槽位索引
        Debug.Assert((StartOfFreeList - entries[_freeList].next) >= -1);

        // 更新空闲链表头指针，下面会解释这部分
        _freeList = StartOfFreeList - entries[_freeList].next;
        _freeCount--;
    }
    else
    {
        // 没有空闲槽位，检查是否需要扩容
        int count = _count;
        if (count == entries.Length)
        {
            Resize(); // 扩容操作
            bucket = ref GetBucket(hashCode); // 扩容后重新定位桶
        }

        // 插入到当前最后一个有效位置
        index = count;
        _count = count + 1;
        entries = _entries; // 可能被 Resize() 改变，所以重新获取
    }

    // 设置新的 Entry 数据
    ref Entry entry = ref entries![index];
    entry.hashCode = hashCode;          // 哈希值
    entry.next = bucket - 1;            // 插入到桶链表头部
    entry.key = key;                    // 键
    entry.value = value;                // 值
    bucket = index + 1;                 // 更新桶指向当前 entry（1-based）
    _version++;                         // 版本号递增，防止遍历时修改集合

    // 如果是非随机化字符串比较器，且冲突过多，切换回随机化比较器防止 DoS 攻击
    if (!typeof(TKey).IsValueType &&
        collisionCount > HashHelpers.HashCollisionThreshold &&
        comparer is NonRandomizedStringEqualityComparer)
    {
        // 切换为随机化字符串比较器（即 EqualityComparer<string>.Default）
        //强制重新构建 buckets 和 entries 数组，但保持数组长度不变
        Resize(entries.Length, true);
    }

    return true; // 插入成功
}

GetBucket方法

 private ref int GetBucket(uint hashCode)
 {
     int[] buckets = _buckets!;
#if TARGET_64BIT
     return ref buckets[HashHelpers.FastMod(hashCode, (uint)buckets.Length, _fastModMultiplier)];
#else
     return ref buckets[(uint)hashCode % buckets.Length];
#endif
 }

补充说明

这里面的StartOfFreeList 是一个偏移,为常量

 private const int StartOfFreeList = -3;

• 它是一个偏移量，用来区分 next 是表示“冲突链表”的索引，还是“空闲链表”的索引。
• 所有 next <= -3 的值都被认为属于空闲链表。
• 利用公式 index = StartOfFreeList - next，可以将这些负数解码成真正的 Entry 索引。

规则如下：

 _freeList = StartOfFreeList - entries[_freeList].next;

如entrie.next = -4,对应的“真实索引”为：-3 - (-4) = 1

为什么选择 -3 作为起始偏移？

因为：

• -2 作为空闲链表的结尾标志
• -1 和 >=0 保留给冲突链表使用
• 所以 -3 开始的负值不会与上述冲突，可用于编码空闲链表索引

这是一种 巧妙的状态复用方式，使得一个 int 字段能承载多种语义。

2. 关键变量解释

3. 主要功能总结

4. 时间复杂度分析

💡 通常我们说 Dictionary 的插入和查找操作是 O(1)，但最坏情况（所有键都冲突）会退化为 O(n)。

5. 示例说明

var dict = new Dictionary<string, int>();
dict.Add("apple", 5);   // 插入
dict.Add("banana", 7);  // 插入
dict.Add("apple", 10);  // 抛出 ArgumentException

如果换成：

dict.TryInsert("apple", 10, InsertionBehavior.OverwriteExisting); // 成功覆盖

6. 总结

二、TryAdd方法

1. 代码解析

public bool TryAdd(TAlternateKey key, TValue value)
{
    ref TValue? slot = ref GetValueRefOrAddDefault(key, out bool exists);
    if (!exists)
    {
        slot = value;
        return true;
    }
    return false;
}

GetValueRefOrAddDefault方法

internal ref TValue? GetValueRefOrAddDefault(TAlternateKey key, out bool exists)
{
    // 注意：该方法与标准的 GetValueRefOrAddDefault 方法类似，保持同步

    // 获取底层 Dictionary<TKey, TValue> 实例
    Dictionary<TKey, TValue> dictionary = Dictionary;

    // 获取用于比较 alternate key 和 TKey 的自定义比较器
    IAlternateEqualityComparer<TAlternateKey, TKey> comparer = GetAlternateComparer(dictionary);

    // 如果 buckets 数组为空，初始化字典（初始容量为 0）
    if (dictionary._buckets == null)
    {
        dictionary.Initialize(0);
    }

    // 调试断言：确保 buckets 已初始化
    Debug.Assert(dictionary._buckets != null);

    // 获取 entries 数组（实际存储键值对的地方）
    Entry[]? entries = dictionary._entries;

    // 调试断言：确保 entries 不为 null
    Debug.Assert(entries != null, "expected entries to be non-null");

    // 计算当前 key 的哈希码，并转为无符号整数
    uint hashCode = (uint)comparer.GetHashCode(key);

    // 哈希冲突计数器，用于检测是否发生死循环（并发修改）
    uint collisionCount = 0;

    // 获取当前哈希码对应的 bucket 索引（引用传递，后续可修改 bucket 指向）
    ref int bucket = ref dictionary.GetBucket(hashCode);

    // 从 bucket 中取出第一个 entry 的索引（注意：bucket 是 1-based）
    int i = bucket - 1;

    Debug.Assert(comparer is not null);

    // 遍历冲突链表查找是否存在相同 key
    while ((uint)i < (uint)entries.Length)
    {
        // 如果哈希码匹配且 key 相等，则找到已有条目
        if (entries[i].hashCode == hashCode && comparer.Equals(key, entries[i].key))
        {
            exists = true;

            // 返回 value 的引用，允许外部直接赋值而无需复制
            return ref entries[i].value!;
        }

        // 否则继续遍历链表
        i = entries[i].next;

        // 冲突计数 +1
        collisionCount++;

        // 如果冲突次数超过 entries 长度，说明可能发生了循环引用（并发修改）
        if (collisionCount > (uint)entries.Length)
        {
            ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
        }
    }

    // 没有找到 key，准备插入新条目

    // 使用比较器创建实际 TKey 类型的 key（比如字符串到 string 的转换）
    TKey actualKey = comparer.Create(key);

    // 如果创建失败（如 key 为 null），抛出 ArgumentNullException
    if (actualKey is null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    int index;

    // 如果存在空闲槽位（_freeCount > 0），复用 _freeList 中的位置
    if (dictionary._freeCount > 0)
    {
        index = dictionary._freeList;
        // 更新 freeList 指向下一个空闲位置（使用 StartOfFreeList 编码方式）
        Debug.Assert((StartOfFreeList - entries[dictionary._freeList].next) >= -1,
                     "shouldn't overflow because `next` cannot underflow");
        dictionary._freeList = StartOfFreeList - entries[dictionary._freeList].next;
        dictionary._freeCount--;
    }
    else
    {
        // 否则获取当前 count 并判断是否需要扩容
        int count = dictionary._count;

        if (count == entries.Length)
        {
            // 扩容
            dictionary.Resize();

            // 重新获取 bucket（因为 Resize 可能改变了 buckets 数组）
            bucket = ref dictionary.GetBucket(hashCode);
        }

        // 插入到 entries[count] 的位置
        index = count;
        dictionary._count = count + 1;

        // 重新获取 entries（可能在 Resize 后已更新）
        entries = dictionary._entries;
    }

    // 定位到要插入的 entry
    ref Entry entry = ref entries![index];

    // 设置 entry 的属性
    entry.hashCode = hashCode;          // 哈希码
    entry.next = bucket - 1;            // 插入到冲突链表头部
    entry.key = actualKey;              // 键
    entry.value = default!;             // 初始值为默认值（稍后由调用者设置）

    // 更新 bucket 指向新的 entry（注意：bucket 是 1-based）
    bucket = index + 1;

    // 版本号增加，用于枚举时检测修改
    dictionary._version++;

    // 如果是引用类型、哈希冲突过多、且使用的是非随机化字符串比较器
    if (!typeof(TKey).IsValueType &&
        collisionCount > HashHelpers.HashCollisionThreshold &&
        comparer is NonRandomizedStringEqualityComparer)
    {
        // 触发 Resize 并启用随机化字符串比较器（防止 DoS 攻击）
        dictionary.Resize(entries.Length, true);

        exists = false;

        // 因为 Resize 后 entries 已经变化，之前的引用失效，必须重新查找
        ref TValue? value = ref dictionary.FindValue(actualKey)!;

        // 调试断言：此时一定能找到值
        Debug.Assert(!Unsafe.IsNullRef(ref value), "the lookup result cannot be a null ref here");

        return ref value;
    }

    // 表示这是新添加的项
    exists = false;

    // 返回 value 字段的引用，供调用者赋值
    return ref entry.value!;
}

2. 关键变量解释

3. 主要功能总结

✅ 该段代码实现了以下核心功能：

1. 尝试插入一个键值对（TryAdd）
2. 查找键是否存在（通过哈希码 + 比较器）
3. 若存在，返回失败；若不存在，添加新条目并返回成功
4. 支持使用替代键类型 TAlternateKey，提升灵活性
5. 自动管理内存池（空闲槽位复用）
6. 动态扩容机制（Resize）
7. 防止哈希碰撞攻击（切换为随机化比较器）

4. 时间复杂度分析

⚠️ 注意：当频繁触发 Resize 或哈希冲突过多时性能会下降。

5. 示例说明

假设我们定义如下类：

class MyKey
{
    public int Id { get; }

    public MyKey(int id) => Id = id;

    public override int GetHashCode() => Id;
    public override bool Equals(object obj) => 
        obj is MyKey other && Id == other.Id;
}

然后使用扩展的 TryAdd 方法：

var dict = new Dictionary<MyKey, string>();
dict.TryAdd(new MyKey(1), "A"); // 成功
dict.TryAdd(new MyKey(1), "B"); // 失败（键已存在）
dict.TryAdd(new MyKey(2), "C"); // 成功

此时：

• MyKey(1) 落在 bucket[1 % N]（N 为 buckets 长度）
• MyKey(2) 落在 bucket[2 % N]
• 它们的 GetHashCode() 不同，落在不同 bucket 中

6. 总结

三、Remove方法

1. 代码解析

public bool Remove(TKey key)
{
    // 注意：这个 Remove(TKey key) 是 Remove(TKey key, out TValue value) 的简化版本。
    // 为了性能考虑，这两个方法是复制关系，没有提取公共逻辑。

    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (_buckets != null)
    {
        Debug.Assert(_entries != null, "entries should be non-null");
        uint collisionCount = 0;

        IEqualityComparer<TKey>? comparer = _comparer;
        Debug.Assert(typeof(TKey).IsValueType || comparer is not null);

        // 计算 key 的哈希码
        uint hashCode = (uint)(typeof(TKey).IsValueType && comparer == null ? key.GetHashCode() : comparer!.GetHashCode(key));

        // 获取当前 key 对应的 bucket 索引（引用方式）
        ref int bucket = ref GetBucket(hashCode);

        Entry[]? entries = _entries;
        int last = -1; // 上一个节点索引，用于维护链表
        int i = bucket - 1; // buckets 存储的是 1-based 索引

        // 遍历冲突链表查找匹配的 key
        while (i >= 0)
        {
            ref Entry entry = ref entries[i];

            // 判断是否匹配：
            // 1. 哈希码相同
            // 2. 键相等（使用默认比较器或自定义比较器）
            if (entry.hashCode == hashCode &&
                (typeof(TKey).IsValueType && comparer == null ?
                    EqualityComparer<TKey>.Default.Equals(entry.key, key) :
                    comparer!.Equals(entry.key, key)))
            {
                // 如果是链表头节点
                if (last < 0)
                {
                    //bucket存储的索引是从1开始的，因为0表示当前桶为空,没有 Entry
                    //如果bucket = 1,代表存储的为entrys[0]
                    //更新bucket 指向下一个节点
                    bucket = entry.next + 1; 
                }
                else
                {
                    // 否则更新前一个节点的 next 指针跳过当前节点
                    entries[last].next = entry.next;
                }

                // 将当前 entry 的 next 设置为指向下一个空闲槽位（FreeList 编码）
                Debug.Assert((StartOfFreeList - _freeList) < 0,
                             "shouldn't underflow because max hashtable length is MaxPrimeArrayLength = 0x7FEFFFFD(2146435069)");
                entry.next = StartOfFreeList - _freeList;

                // 清理 key 和 value 字段（如果是引用类型）
                if (RuntimeHelpers.IsReferenceOrContainsReferences<TKey>())
                {
                    entry.key = default!;
                }

                if (RuntimeHelpers.IsReferenceOrContainsReferences<TValue>())
                {
                    entry.value = default!;
                }

                // 更新 freeList 和 freeCount
                _freeList = i;
                _freeCount++;

                return true; // 成功移除
            }

            // 继续遍历链表
            last = i;
            i = entry.next;

            // 哈希冲突计数器，防止死循环（并发修改导致）
            collisionCount++;
            if (collisionCount > (uint)entries.Length)
            {
                ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
            }
        }
    }

    return false; // 没有找到对应的 key，返回 false
}

补充说明

“既然 _buckets 是一个 int[] 数组，为什么不用 -1 来表示空桶，而是用 0？毕竟 -1 是一个很常见的‘无效索引’标记。”

哈希码是 uint 类型（无符号）

• 每个键的哈希码是通过 GetHashCode() 得到的，最终被转换为 uint
• 所以计算桶索引时，使用的是模运算：(int)(hashCode % (uint)_buckets.Length)
• 结果一定是一个非负整数（0 到 length - 1）
• 如果用 -1 表示空，就无法和这些合法的桶索引冲突

✅ 所以 0 是最自然的“空桶”值。

2. 关键变量解释

3. 主要功能总结

• 安全地删除指定键的条目
• 支持自定义比较器（IEqualityComparer）
• 维护冲突链表结构
• 复用空闲槽位（避免频繁扩容）
• 清理引用类型字段以避免内存泄漏
• 检测并发写入导致的死循环

4. 时间复杂度分析

⚠️ 与插入类似，当哈希冲突过多时性能会下降。

5. 示例说明

Dictionary<string, int> dict = new();
dict.Add("a", 1);
dict.Add("b", 2);

bool removed = dict.Remove("a"); // 返回 true
removed = dict.Remove("a");      // 返回 false（不存在）

// 此时 "a" 的槽位被加入 freeList，下次 Add 时可复用

6. 总结

四、TryGetValue方法

1. 代码解析

public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
{
    ref TValue valRef = ref FindValue(key);
    if (!Unsafe.IsNullRef(ref valRef))
    {
        value = valRef;
        return true;
    }

    value = default;
    return false;
}

FindValue方法

internal ref TValue FindValue(TKey key)
{
    // 检查键是否为 null，如果是则抛出 ArgumentNullException
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    // 初始化一个空 Entry 引用，用于后续返回结果
    ref Entry entry = ref Unsafe.NullRef<Entry>();

    // 如果 buckets 已初始化，说明字典中可能有数据
    if (_buckets != null)
    {
        Debug.Assert(_entries != null, "expected entries to be non-null");

        // 获取比较器，默认为 null
        IEqualityComparer<TKey>? comparer = _comparer;

        // 对值类型进行优化：如果 TKey 是值类型且没有自定义比较器，则启用去虚化优化
        if (typeof(TKey).IsValueType && comparer == null)
        {
            // 使用默认 GetHashCode 计算哈希码
            uint hashCode = (uint)key.GetHashCode();

            // 获取 bucket 索引（bucket 存储的是 1-based 的索引）
            int i = GetBucket(hashCode);

            // 获取 entries 数组引用
            Entry[]? entries = _entries;

            // 冲突计数器，防止死循环（并发修改导致链表成环）
            uint collisionCount = 0;

            // 转换为 0-based 索引
            i--;

            do
            {
                // 如果当前索引越界，跳转到未找到
                if ((uint)i >= (uint)entries.Length)
                {
                    goto ReturnNotFound;
                }

                // 定位当前 entry
                entry = ref entries[i];

                // 判断是否匹配：
                // 1. 哈希码相同
                // 2. 键相等（使用默认比较器）
                if (entry.hashCode == hashCode &&
                    EqualityComparer<TKey>.Default.Equals(entry.key, key))
                {
                    goto ReturnFound; // 找到，跳转返回
                }

                // 继续遍历链表
                i = entry.next;

                // 冲突计数 +1
                collisionCount++;
            } while (collisionCount <= (uint)entries.Length); // 控制最大冲突次数

            // 如果超出最大冲突次数，说明发生了并发写入导致循环
            goto ConcurrentOperation;
        }
        else
        {
            // 非值类型或有自定义比较器的情况
            Debug.Assert(comparer is not null);

            // 使用自定义比较器计算哈希码
            uint hashCode = (uint)comparer.GetHashCode(key);

            // 获取 bucket 索引
            int i = GetBucket(hashCode);

            // 获取 entries 数组
            Entry[]? entries = _entries;

            // 冲突计数器
            uint collisionCount = 0;

            // 转为 0-based 索引
            i--;

            do
            {
                if ((uint)i >= (uint)entries.Length)
                {
                    goto ReturnNotFound;
                }

                entry = ref entries[i];

                if (entry.hashCode == hashCode &&
                    comparer.Equals(entry.key, key))
                {
                    goto ReturnFound;
                }

                i = entry.next;

                collisionCount++;
            } while (collisionCount <= (uint)entries.Length);

            goto ConcurrentOperation;
        }
    }

    // 默认路径：未找到
    goto ReturnNotFound;

// 处理并发修改异常
ConcurrentOperation:
    ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();

// 返回找到的值
ReturnFound:
    ref TValue value = ref entry.value;
Return:
    return ref value;

// 返回未找到的结果
ReturnNotFound:
    value = ref Unsafe.NullRef<TValue>();
    goto Return;
}

2. 关键变量解释

3. 主要功能总结

✅ 该方法实现了以下核心功能：

• 高效查找键对应的值引用
• 支持自定义比较器（IEqualityComparer）
• 针对值类型进行了 JIT 去虚化优化
• 防止并发写入导致的死循环
• 返回 ref TValue，允许直接修改字典中的值
• 避免不必要的拷贝操作，提升性能

4. 时间复杂度分析

⚠️ 性能受哈希分布影响较大，建议使用良好的哈希函数或启用随机化字符串比较器以提高安全性与性能。

5. 示例说明

var dict = new Dictionary<string, int>();
dict.Add("a", 100);
dict.Add("b", 200);

// 查找键 "a" 对应的值的引用
ref int val = ref dict.FindValue("a");

val = 999; // 直接修改了字典中 "a" 的值

Console.WriteLine(dict["a"]); // 输出：999

6. 总结

五、ContainsValue方法

1. 代码解析

public bool ContainsValue(TValue value)
{
    // 获取 entries 数组引用
    Entry[]? entries = _entries;

    // 情况一：查找 null 值
    if (value == null)
    {
        for (int i = 0; i < _count; i++)
        {
            // entry.next >= -1 表示该 entry 是有效（未被删除）的
            // 检查当前 entry 的值是否为 null
            if (entries![i].next >= -1 && entries[i].value == null)
            {
                return true; // 找到 null 值，返回 true
            }
        }
    }
    // 情况二：查找值类型值
    else if (typeof(TValue).IsValueType)
    {
        // 针对值类型使用 EqualityComparer<T>.Default 进行去虚化优化（JIT 可以优化掉虚方法调用）
        for (int i = 0; i < _count; i++)
        {
            if (entries![i].next >= -1 &&
                EqualityComparer<TValue>.Default.Equals(entries[i].value, value))
            {
                return true; // 找到匹配值，返回 true
            }
        }
    }
    // 情况三：查找引用类型值
    else
    {
        // 引用类型无法进行 JIT 去虚化优化，因此缓存 EqualityComparer 实例避免每次循环都获取一次
        EqualityComparer<TValue> defaultComparer = EqualityComparer<TValue>.Default;
        for (int i = 0; i < _count; i++)
        {
            if (entries![i].next >= -1 &&
                defaultComparer.Equals(entries[i].value, value))
            {
                return true; // 找到匹配值，返回 true
            }
        }
    }

    // 遍历完成未找到匹配值，返回 false
    return false;
}

2. 关键变量解释

3. 主要功能总结

✅ 该方法实现了以下核心功能：

• 检查字典中是否存在指定的值
• 支持 null 值查找
• 区分处理 null、值类型和引用类型，进行性能优化
• 跳过已删除项（通过 entry.next >= -1 判断）
• 高效遍历 _entries 数组，不依赖哈希表结构

4. 时间复杂度分析

⚠️ ContainsValue() 是一个线性时间操作，应谨慎在频繁调用的场景中使用。

5. 示例说明

• 示例 1：查找普通值类型值

var dict = new Dictionary<string, int>
{
    { "a", 1 },
    { "b", 2 },
    { "c", 3 }
};

bool found = dict.ContainsValue(2); // 返回 true

• 示例 2：查找 null 值

var dict = new Dictionary<string, string?>
{
    { "a", null },
    { "b", "hello" }
};

bool found = dict.ContainsValue(null); // 返回 true

• 示例 3：查找引用类型值

class Person { public string Name; }

var p1 = new Person { Name = "Alice" };
var p2 = new Person { Name = "Bob" };

var dict = new Dictionary<int, Person>
{
    { 1, p1 },
    { 2, p2 }
};

bool found = dict.ContainsValue(p2); // 返回 true

6. 总结

为什么不能像 ContainsKey 一样高效？

• ContainsKey 利用哈希码快速定位 bucket，是常数时间操作。
• ContainsValue 必须遍历整个 _entries 数组，因为没有“值 → 键”的反向映射。

六、Resize方法

1. 代码解析

private void Resize(int newSize, bool forceNewHashCodes)
{
    // 断言：引用类型才可能需要重新计算哈希码（forceNewHashCodes）
    Debug.Assert(!forceNewHashCodes || !typeof(TKey).IsValueType);

    // _entries 必须存在
    Debug.Assert(_entries != null, "_entries should be non-null");

    // 新大小必须大于等于当前 entries 的长度
    Debug.Assert(newSize >= _entries.Length);

    // 创建一个新的 Entry 数组用于扩容
    Entry[] entries = new Entry[newSize];

    // 将旧 entries 中的数据复制到新数组中（只复制有效元素）
    int count = _count;
    Array.Copy(_entries, entries, count);

    // 如果是引用类型，并且强制重新计算哈希码（如字符串启用随机化比较器）
    if (!typeof(TKey).IsValueType && forceNewHashCodes)
    {
        // 当前比较器必须是 NonRandomizedStringEqualityComparer
        Debug.Assert(_comparer is NonRandomizedStringEqualityComparer);

        // 获取新的随机化比较器
        IEqualityComparer<TKey> comparer = _comparer =
            (IEqualityComparer<TKey>)((NonRandomizedStringEqualityComparer)_comparer).GetRandomizedEqualityComparer();

        // 重新计算每个 entry 的哈希码
        for (int i = 0; i < count; i++)
        {
            if (entries[i].next >= -1) // 判断是否为有效 entry（不是已删除项）
            {
                entries[i].hashCode = (uint)comparer.GetHashCode(entries[i].key);
            }
        }
    }

    // 分配新的 buckets 数组
    _buckets = new int[newSize];

#if TARGET_64BIT
    // 在 64 位平台上使用快速取模乘法优化 GetBucket 性能
    _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)newSize);
#endif

    // 重建 bucket 链表结构
    for (int i = 0; i < count; i++)
    {
        if (entries[i].next >= -1) // 只处理有效的 entry
        {
            // 定位该 entry 应该属于哪个 bucket
            ref int bucket = ref GetBucket(entries[i].hashCode);

			//头插法
            // 设置 next 指针：指向当前 bucket 所在位置的前一个（1-based 转换为 0-based）
            entries[i].next = bucket - 1;

            // 更新 bucket 指向当前 entry 的索引 + 1（保持 1-based）
            bucket = i + 1;
        }
    }

    // 替换为新的 entries 数组
    _entries = entries;
}

2. 关键变量解释

3. 主要功能

✅ 该方法实现了以下核心功能：

• 扩容字典内部存储结构（entries 和 buckets）
• 支持强制重新计算哈希码（主要用于字符串等引用类型防攻击）
• 保留原有数据并重新构建哈希链表结构
• 支持性能优化（如 64 位平台的快速取模）
• 确保线程安全与结构一致性

4. 时间复杂度分析

⏱️ Resize() 是一个相对耗时的操作，应尽量避免频繁调用。通常在添加元素导致负载因子过高时才会触发。

5. 示例说明

虽然 Resize() 是私有方法，不会被直接调用，但它会在如下场景自动触发：向字典中添加大量元素导致容量不足

var dict = new Dictionary<string, int>(StringComparer.Ordinal);
for (int i = 0; i < 1000; i++)
{
    dict.Add("key" + i, i);
}

// 此时会多次触发 Resize()

在这个过程中，每次 Add() 发现容量不足时都会调用 Resize() 来扩大存储空间，并可能启用 forceNewHashCodes=false。

6. 总结表格

以下是对你提供的 Dictionary<TKey, TValue>.Enumerator 结构的完整结构化分析与注释版代码解析，按照你要求的格式组织：

七、Enumerator迭代器

1. 代码解析

public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>, IDictionaryEnumerator
{
    // 引用字典实例
    private readonly Dictionary<TKey, TValue> _dictionary;

    // 用于检测版本变化，防止枚举期间被修改
    private readonly int _version;

    // 当前遍历到的 entries 索引
    private int _index;

    // 当前键值对
    private KeyValuePair<TKey, TValue> _current;

    // 枚举器返回类型：DictEntry 或 KeyValuePair
    private readonly int _getEnumeratorRetType;

    internal const int DictEntry = 1;
    internal const int KeyValuePair = 2;

    // 构造函数
    internal Enumerator(Dictionary<TKey, TValue> dictionary, int getEnumeratorRetType)
    {
        _dictionary = dictionary;
        _version = dictionary._version; // 记录当前版本号
        _index = 0; // 初始索引为 0
        _getEnumeratorRetType = getEnumeratorRetType; // 返回类型
        _current = default; // 初始化当前项
    }

    // 移动到下一个有效条目
    public bool MoveNext()
    {
        if (_version != _dictionary._version)
        {
            ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
        }

        // 使用无符号比较防止整数溢出问题
        while ((uint)_index < (uint)_dictionary._count)
        {
            ref Entry entry = ref _dictionary._entries![_index++];

            if (entry.next >= -1) // 检查是否是有效 entry（未被删除）
            {
                _current = new KeyValuePair<TKey, TValue>(entry.key, entry.value);
                return true;
            }
        }

        _index = _dictionary._count + 1; // 标记枚举结束
        _current = default;
        return false;
    }

    // 获取当前 KeyValuePair
    public KeyValuePair<TKey, TValue> Current => _current;

    // Dispose 方法为空（结构体不需要释放资源）
    public void Dispose() { }

    // 实现 IEnumerator.Current（支持非泛型接口）
    object? IEnumerator.Current
    {
        get
        {
            if (_index == 0 || _index == _dictionary._count + 1)
            {
                ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
            }

            if (_getEnumeratorRetType == DictEntry)
            {
                return new DictionaryEntry(_current.Key, _current.Value);
            }

            return new KeyValuePair<TKey, TValue>(_current.Key, _current.Value);
        }
    }

    // 重置枚举器状态
    void IEnumerator.Reset()
    {
        if (_version != _dictionary._version)
        {
            ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
        }

        _index = 0;
        _current = default;
    }

    // IDictionaryEnumerator.Entry 属性（非泛型接口）
    DictionaryEntry IDictionaryEnumerator.Entry
    {
        get
        {
            if (_index == 0 || _index == _dictionary._count + 1)
            {
                ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
            }

            return new DictionaryEntry(_current.Key, _current.Value);
        }
    }

    // IDictionaryEnumerator.Key 属性
    object IDictionaryEnumerator.Key
    {
        get
        {
            if (_index == 0 || _index == _dictionary._count + 1)
            {
                ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
            }

            return _current.Key;
        }
    }

    // IDictionaryEnumerator.Value 属性
    object? IDictionaryEnumerator.Value
    {
        get
        {
            if (_index == 0 || _index == _dictionary._count + 1)
            {
                ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
            }

            return _current.Value;
        }
    }
}

2. 关键变量解释

3. 主要功能

✅ 该结构实现了以下核心功能：

• 支持泛型和非泛型枚举（实现 IEnumerator<T> 和 IDictionaryEnumerator）
• 安全检测版本号，防止在枚举期间字典被修改
• 跳过已被删除的 entry（通过 entry.next >= -1 判断）
• 支持多种返回类型（KeyValuePair / DictionaryEntry）
• 高效遍历 _entries 数组，不依赖 buckets

4. 时间复杂度分析

⏱️ 整体性能优秀，适用于大多数遍历场景。但在频繁增删元素后，可能会出现较多“空槽”，影响效率。

5. 示例说明

• 泛型使用方式（foreach 推荐）

var dict = new Dictionary<string, int>
{
    { "a", 1 }, { "b", 2 }
};

foreach (var kvp in dict)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
}
// 输出：
// a: 1
// b: 2

• 非泛型使用方式（兼容旧 API）

IDictionaryEnumerator enumerator = ((IDictionary)new Dictionary<string, int> { { "x", 10 } }).GetEnumerator();

while (enumerator.MoveNext())
{
    Console.WriteLine($"{enumerator.Key} -> {enumerator.Value}");
}
// 输出：
// x -> 10

6. 总结

八、其他方法

1.Initialize

private int Initialize(int capacity)
{
    int size = HashHelpers.GetPrime(capacity);
    int[] buckets = new int[size];
    Entry[] entries = new Entry[size];

    // Assign member variables after both arrays allocated to guard against corruption from OOM if second fails
    _freeList = -1;
#if TARGET_64BIT
    _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)size);
#endif
    _buckets = buckets;
    _entries = entries;

    return size;
}

2.ContainsKey

 public bool ContainsKey(TAlternateKey key) =>
             !Unsafe.IsNullRef(ref FindValue(key, out _));

3.Clear

public void Clear()
{
    int count = _count;
    if (count > 0)
    {
        Debug.Assert(_buckets != null, "_buckets should be non-null");
        Debug.Assert(_entries != null, "_entries should be non-null");

        Array.Clear(_buckets);

        _count = 0;
        _freeList = -1;
        _freeCount = 0;
        Array.Clear(_entries, 0, count);
    }
}

4.Resize

//返回一个大于等于给定容量（_count）的最小质数（prime number）
private void Resize() => Resize(HashHelpers.ExpandPrime(_count), false);