DictionaryTKey,TValue上核心数据结构系列C#与常用数据结构源码剖析 · 数据结构-哈希与映射篇阅读时间约 55 分钟源码位置dotnet/runtime5535e31.../Dictionary.cs版本边界以v8.0.0/ commit5535e31a712343a63f5d7d796cd874e563e5ac14的 .NET 8 实现形状为主线字段、快速取模和 comparer 特化会随 tag 与架构变化。本文代码均是教学节选或伪代码不伪装成可直接替换原文件的完整源码。前置知识04-01Hash 原理一、引言大多数人以为 Dictionary 内部存储的是KeyValuePairTKey,TValue数组。实际并非如此——.NET 的 Dictionary 使用了一个精巧的双数组 空闲链表设计这个设计是理解它全部行为的关键。它是用结构体替代对象哲学的极致体现一个Entrystruct 包含hashCode、next、key、value四个字段紧凑排列在连续内存中没有单独为每个键值对分配堆对象。这种设计与 04-01 中讨论的链地址法一脉相承——但 .NET 用连续数组和 int 索引替代了传统链表节点。理解了这个架构你就能回答这些问题为什么 Dictionary 的Remove不会缩小数组为什么删除后再添加能复用之前的位置为什么 1-based 索引能让数组的默认零值直接表示“桶为空”为什么next字段的负数范围被设计为双重编码本文从 .NET 8 的实现形状出发按结构与不变式解析设计。对私有字段做“逐行”分析时必须固定 tag因此文中更重视哪些性质在操作前后不能被破坏。理解这一篇后续 Add、Remove 和 Resize 的控制流才有可验证的主线。二、双数组架构全景2.1 核心字段一览// System.Collections.Generic.DictionaryTKey,TValue // 源码路径: dotnet/runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs public class DictionaryTKey, TValue : IDictionaryTKey, TValue { private int[]? _buckets; // 桶数组存储冲突链头索引1-based private Entry[]? _entries; // 条目数组所有键值对紧凑存储 private int _count; // 已使用过的 Entry 上界包含尚未复用的空闲槽 private int _freeList; // 空闲链表头-1 表示无空闲 private int _freeCount; // 空闲条目数量 private int _version; // 版本号枚举器并发检测 private IEqualityComparerTKey? _comparer; // 键比较器 private KeyCollection? _keys; // Keys 属性缓存 private ValueCollection? _values; // Values 属性缓存 private const int StartOfFreeList -3; // 空闲链表编码基值见第四章 }架构全景图分工示意数值不表示同一个实际快照DictionaryTKey,TValue ┌─────────────────────────────────────────────────────────┐ │ _buckets (int[]) _entries (Entry[]) │ │ ┌─────┬─────┬─────┬┐ ┌──────┬──────┬─────┬───────┐ │ │ │ 3 │ 0 │ 5 ││ │hash │ next │ key │ value │ │ │ ├─────┼─────┼─────┤│ ├──────┼──────┼─────┼───────┤ │ │ │ 0 │ 0 │ 0 ││ │0xA3 │ -1 │ a │apple │ │ │ ├─────┼─────┼─────┤│ ├──────┼──────┼─────┼───────┤ │ │ │ 0 │ 0 │ 0 ││ │0xA3 │ 0 │ b │banana │ │ │ └─────┴─────┴─────┘│ ├──────┼──────┼─────┼───────┤ │ │ │ │0xB7 │ -1 │ d │durian │ │ │ _freeList ... │ ├──────┼──────┼─────┼───────┤ │ │ _freeCount ... │ │(free)│ ... │ ... │ ... │ │ │ _count ... │ └──────┴──────┴─────┴───────┘ │ │ _version 5 │ │ └─────────────────────────────────────────────────────────┘关键设计决策_buckets和_entries是两个独立数组。前者只存桶头索引后者存完整条目。在常见实现中两个数组通常以同一选定容量初始化并非“桶数量远小于条目数”。分离的价值是角色清晰先读紧凑的 int 桶头再访问 Entry不为每个冲突节点分配独立对象。_count是最容易读错的字段。它不是公开Count的直接存储而是从 Entry 数组头部开始已经启用过的槽位上界。删除一个元素后_count通常不减_freeCount增加因此对外元素数是_count - _freeCount。只有理解这个不变式才不会在阅读 Resize、枚举或空闲槽复用时得出错误结论。2.2 Entry 结构体——紧凑的数据容器private struct Entry { public uint hashCode; // 键的完整哈希码32 位无符号 public int next; // 双重编码0 用于冲突链0 用于空闲链表 public TKey key; // 键 public TValue value; // 值 }Entry 是一个结构体每个元素不是独立托管对象因此没有逐节点对象头。但 Entry 数组本身仍是托管对象键或值如果是引用类型Entry 中保存的仍然是需要 GC 追踪的引用。“结构体”不等于字典不使用托管堆。不同泛型参数组合下的 Entry 大小64 位系统Dictionarystring, object: uint hashCode: 4 bytes int next: 4 bytes string key: 8 bytes (引用) object value: 8 bytes (引用) ───────────────────────── 总计: 24 bytes (正好 3 个 8 字节对齐) Dictionaryint, int: uint hashCode: 4 bytes int next: 4 bytes int key: 4 bytes int value: 4 bytes ───────────────────────── 总计: 16 bytes (紧凑打包) Dictionarylong, string: uint hashCode: 4 bytes int next: 4 bytes long key: 8 bytes (对齐到 8 字节边界) string value: 8 bytes ───────────────────────── 总计: 24 bytes为什么是 uint hashCode 而不是 int因为 Dictionary 内部是这样使用哈希码的// 比较器返回 int按位转换为 uint 保留全部 32 位 uint hashCode (uint)comparer.GetHashCode(key); int bucketIndex (int)(hashCode % (uint)_buckets.Length);不再用 0x7fffffff清掉符号位意味着哈希的 32 位都可用。在冲突链比较时先比较 hashCode再调用键相等性逻辑可以快速排除大部分不匹配条目。“单条 CPU 指令”不是 C# 语义保证具体机器码要以对应 JIT/AOT 产物为准。// FindValue 中的比较路径 if (entry.hashCode hashCode // 快速路径单条指令比较 _comparer.Equals(entry.key, key)) // 慢路径可能虚方法调用 { return entry; // 命中 } // 不匹配 → 继续沿冲突链查找三、1-based 桶索引的设计巧思3.1 为什么桶索引要加 1这是整个设计中最小但最精妙的细节。// _buckets[bucket] 的语义 // 0 → 桶为空没有条目映射到此桶 // j1 → 桶的第一个条目在 _entries[j]为什么是j1而不是直接用j问题在于数组索引从 0 开始。_entries[0]是一个有效的条目。如果_buckets[i] 0表示空桶但_buckets[i] 0正好也是_entries[0]的索引——冲突了无法区分桶为空和桶指向第 0 个条目。解决的方案是存储索引 1// 取桶中第一个条目 int rawBucketValue _buckets[bucketIndex]; if (rawBucketValue 0) { // 桶为空条目不存在 return false; } int entryIndex rawBucketValue - 1; // 还原为真实索引这样设计的好处零检查成本_buckets[i] 0就是空桶没有额外标志位无额外内存不需要为每个桶存储一个是否为空的 bool简单高效取值-减1-使用三个步骤一条龙这看起来是一个微小的优化但在每次 Dictionary 操作插入、查找、删除中都会用到。在每秒数百万次操作的场景中这个设计节省了可观的 CPU 周期。3.2 桶的初始化和冲突链初始状态空字典尚未添加元素_buckets所有元素为 0。_entries为 null 或空数组。添加第一个键值对后// 添加 (c, cherry)假设 hashCode 0xA3桶索引为 0 _buckets[0] 1 // 1-based指向 _entries[0] _entries[0] { hashCode: 0xA3, next: -1, key: c, value: cherry } // next -1 表示冲突链尾图示_buckets: [1, 0, 0, ...] │ ▼ _entries[0]: { 0xA3, -1, c, cherry }添加第二个键哈希到同一桶时// 添加 (b, banana)hashCode 0xA3桶索引也为 0 _buckets[0] 2 // 新头指向 _entries[1] _entries[1] { hashCode: 0xA3, next: 0, key: b, value: banana } // next 0指向 _entries[0]老条目 // 冲突链_buckets[0]2 → _entries[1].next0 → _entries[0].next-1图示_buckets: [2, 0, 0, ...] │ ▼ _entries[1]: { 0xA3, 0, b, banana } ← 链表头 │ ▼ _entries[0]: { 0xA3, -1, c, cherry } ← 链表尾添加第三个键哈希到不同桶// 添加 (d, durian)hashCode 0xB7桶索引为 4 _buckets[4] 3 // 1-based指向 _entries[2] _entries[2] { hashCode: 0xB7, next: -1, key: d, value: durian }完整状态_buckets: [2, 0, 0, 0, 3, 0, ...] │ ▼ _entries[2]: { 0xB7, -1, d, durian } _entries[0] ← _entries[1] ← _buckets[0] (冲突链)四、next 字段的双重编码4.1 两条链共享同一个字段Entry.next是一个 int 字段但它编码了两个完全不同的链表Used Chain已使用链当next 0时表示同一冲突桶中下一个条目的索引。next -1表示链尾。Free List空闲链表当next -2时表示该条目已被删除处于空闲列表。使用公式StartOfFreeList - next解码为实际索引StartOfFreeList -3// 空闲链表解码 // next -3 → 空闲索引 0 (StartOfFreeList - (-3) -3 3 0) // next -4 → 空闲索引 1 (StartOfFreeList - (-4) -3 4 1) // next -5 → 空闲索引 2 // next -6 → 空闲索引 3 // ...于是-1和-2被保留为特殊哨兵值next 值含义 0在 Used Chain 中指向下一个条目的索引-1Used Chain 链尾-2Free List 链尾 -3在 Free List 中用公式解码为下一个空闲条目的索引4.2 双重编码的完整示例假设 _entries 中有 6 个条目索引 0、1、2 活跃索引 3、5 被删除空闲_entries: 索引 hashCode next key value 0 0xA3 -1 a apple ← used chain 尾 1 0xA3 0 b banana ← next 0 → _entries[0] 2 0xA3 1 c cherry ← 冲突链头_buckets[0] 指向 3 (free) -2 null null ← free list 尾 (next -2) 4 0xB7 -1 d durian ← 另一条 used chain 5 (free) -6 null null ← free list 头指向 3 解码-3 - (-6) 3 → _entries[3] _freeList 5 _freeCount 2空闲链表_freeList 5 → _entries[5].next -6 → 解码得 3 → _entries[3].next -2 → 链尾4.3 设计理由零成本抽象为什么不单独用一个bool _isFree字段标记是否空闲// 方案 A实际方案复用 next 字段 // Entry 大小不增加没有额外字段 // 方案 B朴素方案增加 bool _isFree private struct Entry { public uint hashCode; public int next; public TKey key; public TValue value; public bool _isFree; // ❌ 额外字段 } // 在 64 位系统上bool 占 1 字节但 struct 会 padding 到 4 字节对齐 // 实际 padding 取决于后续字段、泛型参数和平台对齐不能固定断言每项浪费 3 字节实际方案复用已存在的next字段避免添加标志与另一个索引。这是紧凑编码但“零开销”仍然过度简化编解码需要整数运算Entry 实际大小受对齐影响整个字典还有两个数组对象与管理字段。五、空闲链表机制详解5.1 删除时加入空闲链表当一个键被Remove时该条目不从 _entries 数组中移除——而是被插入空闲链表// Remove 操作的关键步骤简化版 public bool Remove(TKey key) { int entryIndex FindEntry(key); // 在 used chain 中查找 if (entryIndex 0) return false; // ... 从 used chain 中移除调整前一个条目的 next 指针... // 将该条目插入 free list 头部 ref Entry entry ref _entries[entryIndex]; entry.next StartOfFreeList - _freeList; // 编码空闲链索引 entry.key default!; // 断开引用帮助 GC entry.value default!; // 断开引用 _freeList entryIndex; // 更新 free list 头 _freeCount; // 空闲计数 1 // 版本号是否在 Remove 中变化是版本实现细节应查阅固定 tag return true; }过程演示初始状态字典有 4 个条目无空闲位置_freeList -1, _freeCount 0。第一次删除_entries[5]操作前_freeList -1无空闲 操作后_freeList 5 _entries[5].next StartOfFreeList - (-1) -3 1 -2free list 尾 _freeCount 1图示_freeList 5 ──→ _entries[5].next -2 (链尾)第二次删除_entries[8]操作前_freeList 5 操作后_freeList 8 _entries[8].next StartOfFreeList - 5 -3 - 5 -8 _freeCount 2图示_freeList 8 ──→ _entries[8].next -8 ──解码-- 5 ──→ _entries[5].next -2 (链尾)5.2 添加时优先复用空闲位置添加新条目时不是总是追加到 _entries 末尾——而是先查看 free list 是否有空位// Add 中决定条目存储位置的核心逻辑 private int GetEntryIndex() { int index; if (_freeCount 0) { // ✅ 有空闲位置从 free list 头部取一个复用 index _freeList; // 取 free list 头 _freeList StartOfFreeList - _entries[_freeList].next; // 更新 free list 头 _freeCount--; } else { // ❌ 无空闲位置追加到 _entries 末尾 index _count; // 如果 _count _entries.Length触发 Resize } return index; }这个机制的关键特性删除不会导致 _entries 数组收缩后续添加直接复用空位。这避免了增删频繁场景下的数组反复分配——Remove不会触发数组操作Add只是在数组中找一个空位填进去。与 ListT 的对比特性ListT 删除DictionaryK,V 删除内部操作移动后续元素填补空位O(n)先按键查链命中后调整索引并入空闲链期望 O(1)内存收缩无Clear/Trim 除外无TrimExcess 除外空位复用不适用List 用 _size 直接覆盖通过 free list 复用为什么不同List 必须保持紧凑顺序Dictionary 的 Entry 物理顺序不是键值映射语义5.3 生命周期实例增删交替var dict new Dictionaryint, string(); // 阶段 1添加 5 个元素 for (int i 0; i 5; i) dict.Add(i, i.ToString()); // _entries: [0,1,2,3,4], _count5, _freeCount0, _freeList-1, Count5 // 阶段 2删除 2 个索引 1 和 3 dict.Remove(1); dict.Remove(3); // _entries: [0, F, 2, F, 4] (F free) // _count5, _freeCount2, Count3 // _freeList 指向最后删除槽再链向上一个空闲槽 // 注意_entries 大小不变只是多了两个空洞 // 阶段 3再添加 2 个 dict.Add(5, five); // 复用 _freeList3 的位置 dict.Add(6, six); // 复用 _entries[1] 的位置 // _entries: [0, SIX, 2, FIVE, 4] // _count5, _freeCount0, Count5, _freeList-1 // _entries 数组在此期间从未缩容/重新分配 // 没有空闲槽且 _count _entries.Length 时下一次添加触发扩容六、初始化与容量策略6.1 构造函数的容量选择public Dictionary() : this(0, null) { } public Dictionary(int capacity, IEqualityComparerTKey? comparer) { if (capacity 0) { Initialize(capacity); } if (comparer ! null) { _comparer comparer; } }延迟初始化Lazy Initialization如果使用无参构造capacity 0Initialize不会被调用var dict new Dictionarystring, int(); // dict._buckets null // dict._entries null // dict._freeList 0 (未初始化)直到第一次Add才在Insert方法中调用Initialize(0)private void Insert(TKey key, TValue value, ...) { if (_buckets null) { Initialize(0); // 第一次 Add 才初始化 } // ... }延迟初始化的价值避免为不必要的空字典分配数组。如果你创建了一个 Dictionary 但只在条件分支中使用它不会浪费任何堆内存。6.2 GetPrime 素数选择private int Initialize(int capacity) { int size HashHelpers.GetPrime(capacity); _buckets new int[size]; _entries new Entry[size]; _freeList -1; return size; }HashHelpers.GetPrime从预计算素数表04-01 第 3.3 节中选取 capacity 的最小素数internal static int GetPrime(int min) { // 预计算素数表 foreach (int prime in Primes) { if (prime min) return prime; } // 超过 720 万 → 动态计算 for (int i min | 1; i int.MaxValue; i 2) { if (IsPrime(i) (i - 1) % HashPrime ! 0) return i; } return min; }初始容量 0 时 →GetPrime(0)返回 3表中第一个素数→ 第一次 Add 后数组大小为 3。6.3 版本演进必须固定 tagDictionary 的整体轮廓长期稳定桶、Entry 数组、冲突链和空闲链。但字段类型、桶索引编码、字符串哈希策略、快速取模、序列化兼容逻辑和枚举器行为都发生过演进。一篇源码文不能只写“.NET 8 源码”就宣称所有细节永久有效应记录例如v8.0.0的 tag以及源文件路径。原文曾将一段连续扫描 hashCode 的Vector256代码标成“.NET 8 Dictionary FindValue 简化源码”。这个模型与 Dictionary 的冲突链布局并不匹配同一桶的条目由next索引连接它们不保证在 Entry 数组中连续因此不能在没有对应布局证据时假设可一次加载八个链节点的 hashCode。本文删除该伪源码和“3—5 倍”结论。若某个未来版本确实改变了内存布局或增加 SIMD 路径应以具体 PR、tag 与基准报告另行分析。IAlternateEqualityComparer和 alternate lookup 也属于版本敏感主题不在本篇的核心布局上强行挂一个“.NET 6”标签。它们的真实 API 形状、约束和可用版本放在 04-04并要通过当前目标 SDK 编译或查阅对应 ref assembly 确认。6.4 容量不等于可再添加数Capacity表示当前内部数组可容纳的 Entry 槽位数公开Count表示活跃键值对数_freeCount表示已启用区间中可复用的删除槽。因此下一次添加可能复用空闲槽即使_count已经到达数组长度只有无空闲槽且已启用上界到达容量时才需要 Resize。EnsureCapacity(n)的意思是确保内部容量至少为 n并不是“在当前 Count 之外再留 n 个”。若已知最终会有 10,000 个活跃键应传最终总量上界不是传增量后在每轮叠加。预留可以避免中途扩容但同时分配 bucket 和 Entry 空间在大量小字典或低内存设备上过度预留也有真实代价。七、与 ListT 的核心差异对比特性DictionaryK,VListT内部存储双数组桶 条目单数组空闲管理Free List复用删除位置无_size 指针覆盖按键/按值删除期望 O(1)先查链再摘链O(n) 查找再搬移后续元素缩容策略不自动缩容TrimExcess 手动不自动缩容TrimExcess 手动扩容策略由对应版本HashHelpers选择常见实现按倍增长受上限约束无参构造通常延迟到首次写入分配内部数组通常先共享空数组首次写入再增长枚举器类型struct值类型struct值类型并发安全不保证有版本检测不保证有版本检测两者的核心差异源于数据组织方式的不同List 的语义要求[0, Count)是紧凑的顺序区间因此中间删除需搬移Dictionary 的语义是键到值的映射Entry 槽的物理顺序不是公开契约因此删除可以摘除冲突链节点并留下可复用空洞。这里调整的是整数索引不是托管指针。7.1 枚举顺序不是持久化契约因为枚举器通常扫描 Entry 的已启用区间并跳过空闲槽某些现代实现在只添加时会呈现接近插入顺序的观察结果。但删除后的空闲槽复用会让新键出现在旧槽位Trim/Resize 与版本变化也可改变观察结果。公开 Dictionary 契约不应被当成有序映射。因此不要把枚举顺序直接写入回放 Hash、网络协议、存档 diff 或签名计算。需要确定性时应按明确 comparer 排序键或选择对顺序有公开保证的容器。这会带来排序时间与临时存储必须纳入预算不能为避免成本而依赖实现偶然性。八、不变式用于阅读源码和设计测试的导航仪与其记住每一行实现不如记住操作前后必须成立的性质公开Count _count - _freeCount且三者都不为负。每个活跃 Entry 恰好能从一个 bucket 的冲突链到达不能同时属于两条链。每个空闲 Entry 恰好能从_freeList到达且空闲节点数等于_freeCount。活跃链与空闲链不相交所有索引均在[0, _count)内并且链最终终止。对每个活跃 Entry其 hashCode 定位的 bucket 与它所在链一致链中不存在两个按 comparer 相等的键。引用类型键和值被删除后不应只因空闲 Entry 而被长期保活实现会在需要时清除相应字段。这些不变式可以用来手绘一个最小 Dictionary 实验为多个键故意返回相同哈希依次 Add、Remove 链头/链中/链尾、再 Add每步都验证所有剩余键可查找、已删键不可查找、Count 正确且无重复键。公开 API 不暴露内部数组若要验证实现级不变式可在自制教学版字典中加断言不建议生产代码用反射依赖 BCL 私有字段。九、内存与 GC 账本字典至少包含字典对象、bucket 数组和 Entry 数组。小字典的固定对象与数组开销可能比实际数据还显眼因此不要为每个实体创建大量只存一两项的字典却不测量总驻留量。对键集很小且固定的组件数组、字段或紧凑结构体可能更合适。Entry 中的引用会被 GC 扫描。Dictionaryint, int的 Entry 数组不包含引用Dictionarystring, object则包含键与值引用两者的相同 Capacity 不代表相同的数组字节数或 GC 扫描特征。大值结构体还会增大每个 Entry使 Resize 复制与缓存局部性成本上升。这并不意味着应把所有大值换成类因为类又引入独立对象和间接访问选择要由数量、更新、复制和生命周期一起决定。Clear将字典变为逻辑空但通常保留容量以便复用。TrimExcess可以在长期低水位时缩小内部数组但需要新数组与重建成本不应在帧循环或每次删除后调用。一次偶然峰值后是保留容量还是缩容取决于峰值是否会重现、内存预算和可接受的重建时机。十、线程安全、可变键与信任边界Dictionary 不是并发可写容器。一个线程在 Resize 或修改冲突链时另一个线程读取不具备字典级保证。枚举器的版本检测是尽早暴露部分修改错误的机制不是锁也不是内存屏障契约。跨线程共享时应使用锁保护完整不变式发布不可变快照或选择符合操作模式的并发容器。键在存入后参与GetHashCode和Equals的状态必须保持稳定。如果可变键在字典内部改变了哈希它仍留在旧 bucket 链上用新状态查找就可能失败这不是 Dictionary 会自动修复的情况。详细的 comparer 契约、复合键和序列化边界在 04-04 继续展开。对不可信输入哈希冲突可以将期望 O(1) 查找拉长为链遍历。不应自制只取前几个字符的弱哈希比较器也不应在网络边界允许无上限键数、键长度和复杂 comparer 工作量。随机化字符串哈希是防御的一部分不能替代输入配额、超时和资源限制。十一、总结Dictionary 的核心数据结构建立在一个精巧的双数组设计上_buckets[] _entries[] 双数组——桶数组提供期望 O(1) 的桶定位条目数组紧凑存储所有槽位Entry struct 紧凑设计——无对象头、无虚方法表每个键值对只占用其所必需的字节1-based 桶索引——使数组默认零值自然表示空桶同时保留 Entry 0 作为有效槽next 字段双重编码——一个 int 同时服务于冲突链和空闲链表不增加任何内存Free List 机制——删除不引发数组收缩后续添加优先复用空位避免增删时的反复分配延迟初始化——空字典不分配任何数组只在第一次添加时初始化理解这个数据结构你就掌握了阅读 Dictionary 全部源码的钥匙。下一篇我们把 Add、FindValue、Remove、Resize 四个核心操作逐行走一遍——你会看到每个操作如何在这个精妙的结构上运转。延伸阅读dotnet/runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs完整源码04-01Hash 原理——哈希函数、素数桶、冲突解决的背景知识本文 04-03Dictionary下关键操作逐行分析阅读建议在 dotnet/runtime 固定 tag 后同时查看Dictionary.cs、HashHelpers.cs与相应单元测试不从单个性能博客反推源码布局。下一篇DictionaryTKey,TValue下关键操作逐行分析