ImmutableDictionary 与 ImmutableHashSet哈希桶树、结构共享与原子快照系列C# 与常用数据结构源码剖析 · 不可变集合篇阅读时间约 60 分钟前置知识哈希表、平衡树、持久化数据结构、比较器源码基线System.Collections.Immutable8.0.0对应dotnet/runtime v8.0.0/ commit5535e31a712343a63f5d7d796cd874e563e5ac14固定源码为 ImmutableDictionary_2.cs 与 ImmutableHashSet_1.cs。版本边界公共契约以目标 TFM 的 reference assembly 和官方 API 文档为准。本文的内部树、桶、节点名称与优化路径只指上述 8.0.0/v8.0.0基线不是跨版本承诺本文也不把它们想当然地写成 HAMT/CHAMP。一、先纠正数据结构这不是 32 路 HAMT不可变哈希容器经常用 Hash Array Mapped Trie 实现但“持久化 哈希”不能推导出某个 .NET 类一定使用 HAMT。在上述System.Collections.Immutable8.0.0/dotnet/runtime v8.0.0的两份源码中ImmutableDictionaryTKey,TValue和ImmutableHashSetT可分别概括为共享下列高层结构先通过键或元素的相等比较器计算 32 位哈希码。用哈希码作为整数键在平衡二叉树中定位一个哈希桶。哈希码相同的不同键/元素进入同一冲突桶再用相等比较器区分。修改时重建受影响的树路径和桶其他不变节点与旧版本共享。hash 25 / \ hash 8 hash 91 | | [hash bucket] [hash bucket] key A - value key X - value key B - value // A/B 同 hash但不相等因此原文中“每次取 5 bit、32 路分支、bitmap popcount”并不是这个实现的源码模型“百万元素只需四层”也不能用来分析它。本文使用“哈希桶树”这个教学名称但私有类名和精确平衡实现仍应通过目标 tag 核对。二、不可变的真正含义ImmutableDictionary的Add、SetItem、Remove不会就地修改原对象而是返回一个代表新内容的字典。旧引用仍然指向旧快照ImmutableDictionaryint, string v1 ImmutableDictionaryint, string.Empty; ImmutableDictionaryint, string v2 v1.Add(1, one); ImmutableDictionaryint, string v3 v2.SetItem(1, ONE); Console.WriteLine(v1.Count); // 0 Console.WriteLine(v2[1]); // one Console.WriteLine(v3[1]); // ONE这不等于每次都复制全部 n 个键值对。新版本可以共享未变的子树、桶内部持久化节点以及比较器。只有从根到目标哈希码的路径、发生改变的冲突桶和平衡修复所需节点发生更新。这就是结构共享。old root new root / \ / \ A B Add/Remove A B / \ ---- / \ C D C D A 和 C 被新旧版本共享只复制受影响路径。但不可变只适用于“集合自身的键值关系”。它不会递归冻结TKey、TValue或T对象。如果值是一个可变Listint修改该列表后所有共享同一列表引用的字典版本都会观察到新内容。var mutable new Listint { 1 }; var snapshot ImmutableDictionarystring, Listint.Empty .Add(numbers, mutable); mutable.Add(2); // snapshot[numbers] 现在也包含 2。字典不可变值并不是深层不可变。如果快照需要真正隔离值也应使用不可变模型、防御性副本或清晰的所有权转移。三、哈希桶树的不变式可以用三层不变式理解整个容器。第一层是树节点按有符号 32 位哈希码的确定顺序组织左子树、当前节点、右子树满足搜索树顺序并维持高度平衡。第二层是桶树中每个哈希码最多对应一个桶桶内包含所有具有该哈希码的键值对或集合元素。它们可能相等也可能只是哈希冲突需要再用相等比较器区分。第三层是版本已发布给不可变容器的节点不能再被就地修改。新操作只能创建新路径并让新根指向旧子树和新节点的组合。Builder 可以在独占的可变阶段里复用节点但发布为不可变快照后必须遵守这个边界。四、比较器是容器语义的一部分ImmutableDictionaryTKey,TValue至少涉及键比较器和值比较器。键比较器决定哈希码和键相等因此决定字典中“同一个键”的意义。值比较器用于需要判断已有值与新值是否相同的操作语义。应在创建空集合时就选定比较器ImmutableDictionarystring, int scores ImmutableDictionary.Createstring, int(StringComparer.OrdinalIgnoreCase); scores scores.Add(Player, 10); // scores.Add(player, 20) 会遇到已有键。一个正确的相等比较器必须满足若Equals(a,b)为真则GetHashCode(a)必须等于GetHashCode(b)。哈希相同不必推出相等冲突桶就是为了处理这种情况。比较结果还必须在键存活期间稳定不能依赖会改变的全局状态。WithComparers一类 API 表面上只是换比较器语义上却可能改变键等价类。例如从 ordinal 换到 ordinal-ignore-case 时原来两个不同键可能合并为冲突。具体 API 对这种冲突如何处理应查目标版本契约不能把更换比较器当成 O(1) 字段赋值。五、Add、SetItem 和 RemoveAdd(key,value)表示“添加一个不存在的键”。已存在等价键时若不满足目标 API 允许的幂等情况它会通过异常报告冲突。这适合重复就是错误的注册边界。SetItem(key,value)表示 upsert键不存在时添加键存在时替换值。如果操作没有造成逻辑变化实现可能返回原实例但调用者不应用引用相等代替集合内容语义。Remove(key)在键存在时从冲突桶中移除该键值对。桶中还有其他冲突键时替换该桶桶变空时从哈希树中移除整个哈希码节点并修复平衡。键不存在时结果在内容上与原字典一致。下面是结构化伪代码不是任何 runtime tag 的逐字源码// 伪代码用于解释路径复制和桶更新。 Node SetItem(Node node, int hash, TKey key, TValue value) { if (node.IsEmpty) return NewNode(hash, Bucket.Single(key, value)); if (hash node.Hash) return Balance(node.WithLeft(SetItem(node.Left, hash, key, value))); if (hash node.Hash) return Balance(node.WithRight(SetItem(node.Right, hash, key, value))); Bucket updated node.Bucket.SetItem(key, value, _keyComparer); return node.WithBucket(updated); }WithLeft、WithRight和WithBucket在不可变路径上产生新节点未走过的子树引用被原样复用。Balance只对被修改路径做局部旋转。真实源码还包含变更结果、计数、已冻结节点与各种快路径需按固定 tag 阅读。六、ImmutableHashSet 的同与不同ImmutableHashSetT只保存唯一元素没有独立 TValue。在目标实现中它与不可变字典共享“哈希码平衡树 冲突桶”的整体思路但桶的元素和更新语义不同。它使用IEqualityComparerT同时定义元素的哈希和相等。ImmutableHashSetstring tags ImmutableHashSet.Createstring(StringComparer.OrdinalIgnoreCase); tags tags.Add(Boss); tags tags.Add(boss); // 逻辑内容仍只有一个等价元素集合的并集、交集、差集和对称差集都会返回新集合但新实例可以共享未变结构。具体算法是否会利用另一个同类集合的内部结构、哪个操作会转到 Builder都属于需按版本核验的优化。七、Builder在可变阶段批量修改连续写map map.SetItem(...)在语义上完全正确但每步都要产生一个可独立发布的不可变根。当业务是“在单一所有者中执行一批修改然后发布一个快照”时Builder 可以减少中间版本和部分路径分配。ImmutableDictionarystring, Player.Builder builder snapshot.ToBuilder(); foreach (PlayerDelta delta in deltas) { if (delta.IsRemoved) builder.Remove(delta.Id); else builder[delta.Id] delta.Player; } ImmutableDictionarystring, Player next builder.ToImmutable();Builder 是可变对象不继承不可变快照的无锁并发读特性。不应让多个线程无同步共享一个 Builder。一个安全模式是更新线程独占 Builder读者只能看到上一个已发布的ImmutableDictionary整批更新完成后才替换快照引用。ToImmutable()之后 Builder 仍可以继续修改但已返回的快照不会被后续修改污染。这需要实现在节点上维护可变/冻结所有权边界并在必要时恢复路径复制不能把 Builder 理解成直接篡改已发布树。八、枚举顺序不是哈希容器的持久化契约不可变集合在枚举过程中不会被修改因此枚举器不需要像可变Dictionary一样对后续写做 fail-fast 版本检测。这非常适合长时间读快照写者创建新根已经获得旧根的枚举器继续读旧结构。但枚举顺序由内部哈希码树、哈希比较器和冲突桶布局决定不是插入顺序、键排序或跨运行时稳定顺序的承诺。字符串哈希策略、比较器或私有实现改变时顺序可以改变。如果需要确定性序列化、跨设备哈希或可读 diff应在输出边界按明确比较规则排序不能依赖当前枚举的偶然顺序。排序会产生自己的时间和快照内存成本应只在真正需要规范化的边界做。九、复杂度平衡树高度与冲突桶同时存在设不同哈希码的数量为h目标哈希码桶内有c个冲突元素。在目标实现模型下查找、添加或删除首先支付 O(log h) 的平衡树定位再支付冲突桶中相等比较的成本。当哈希分布良好时c很小当大量键返回同一哈希码时操作可退化为对长冲突桶的线性搜索。操作良好哈希分布的模型极端冲突的边界按键/元素查找O(log h c)可退化至 O(n)Add / SetItem / Remove树路径 桶更新桶搜索/更新可 O(n)枚举O(n)O(n)Builder 批量更新减少中间分配不会修复坏哈希函数表中没有写“O(1) 哈希查找”因为该源码模型的一级索引是哈希码平衡树不是可直接按桶余数定位的可变数组。也不能写成O(log_32 n)因为这不是 32 路 trie。渐近复杂度不说明分配、节点跳转和比较器成本。不可变树为单次更新分配新路径局部性通常不如连续DictionaryEntry 数组。结构共享节省了整体复制却不代表“无分配”或“与可变字典速度相同”。必须根据版本数量、更新批次、键分布和目标 runtime 实测。十、键不变式不可变字典也怕可变键字典不修改自己不意味它能防止外部修改键对象。键加入后任何影响GetHashCode或Equals的状态都必须保持不变。否则键仍然存储在旧哈希码对应的树节点中但查找会计算新哈希码并走向另一个节点。public sealed class BadKey { public string Name { get; set; } ; public override int GetHashCode() Name.GetHashCode(); public override bool Equals(object? obj) obj is BadKey other Name other.Name; }这种键即使放入ImmutableDictionary也不安全。更好的键是不可变值对象、封装的整数 ID 或不可变字符串。若业务实体的名称会变使用稳定 ID 作键将名称放在值中。另一个反例是所有键都返回常量哈希码。它可以满足“相等键哈希相同”的最低正确性契约却会把全部元素放入一个冲突桶使查找与更新退化。正确的哈希函数还应尽量使典型键均匀分布但不要为了均匀而破坏等价契约。十一、原子发布与多步更新不可变对象非常适合快照发布写者在私有局部变量中构建完整新字典然后一次替换共享根引用。读者只需读取一次根引用整个操作期间都使用同一快照。private ImmutableDictionarystring, Player _players ImmutableDictionarystring, Player.Empty; public ImmutableDictionarystring, Player Snapshot() Volatile.Read(ref _players); public void Publish(ImmutableDictionarystring, Player next) Volatile.Write(ref _players, next);这个例子只适合单写者或写者已由外部串行化的系统。若两个写者都读取同一旧快照各自添加不同键并先后Volatile.Write后发布者会覆盖前者的更新。不可变保证快照不被就地破坏不保证 read-modify-write 组合自动原子。多写者可以用 CAS 循环从当前快照计算新快照只有当根仍是原来那个引用时才替换失败则基于新根重算。标准不可变帮助 API 提供了对应的原子更新模式但具体重试回调可能执行多次不能在其中直接发送邮件、扣款或产生不可重复的副作用。// 结构化模式实际项目优先使用目标版本的 ImmutableInterlocked API。 while (true) { var before Volatile.Read(ref _players); var after before.SetItem(player.Id, player); if (ReferenceEquals( Interlocked.CompareExchange(ref _players, after, before), before)) break; }多个键需要共同满足业务不变式时应在一个局部快照上完成所有SetItem/Remove最后只发布一次根。不要每改一个键就发布否则读者可能看到业务上无效的中间状态。十二、GC 成本与版本保留结构共享降低了“每次快照复制整个字典”的成本但新路径、新桶和新根仍是托管对象。高频单项更新可以产生大量短命节点Builder 能降低批处理中间分配却不会把最终不可变结构变成连续数组。只要某个旧快照仍被引用它独有的节点以及通过共享节点可达的键值对就不能被 GC 回收。这是版本快照正确性的必然结果。无界保留每一个历史版本会使内存随业务历史增长并不是“因为共享就几乎免费”。需要 undo/redo 时应设定版本上限、检查大对象值和深层可变值并用堆快照定位保留根。需要长期审计时增量事件日志或周期 checkpoint 可能比在内存中保留所有集合根更合适。十三、与 Dictionary、ConcurrentDictionary 和 FrozenDictionary 的区别容器更新模型并发读/写快照适合场景DictionaryTKey,TValue原地可变写需外部同步需复制单所有者、高频可变更新ConcurrentDictionaryTKey,TValue共享可变提供并发原子 API枚举语义需按契约理解多线程持续按键更新ImmutableDictionaryTKey,TValue返回新根已发布快照可并发读写者需协调原生版本读多写少、原子快照、undoFrozenDictionaryTKey,TValue构建后冻结只读发布没有增量新版本 API构建一次、长期查询FrozenDictionary面向“准备阶段可以付出构建成本之后大量只读查询”不是可持久化更新树。它的 API 可用性和实现优化要查目标 .NET 版本。每次数据变化都重建 Frozen 容器可能让构建成本主导。ConcurrentDictionary适合多写者对共享当前状态做按键更新但一系列不同键的更新不自动变成一个原子快照。ImmutableDictionary可以在私有新根上完成多键变更后一次发布但写者之间必须用 CAS 重试或串行所有权解决更新丢失。十四、Unity 边界Unity 项目首先要核对目标 Editor 版本、API Compatibility Level、引用程序集、包版本、后端和平台。桌面当前 .NET SDK 支持某个System.Collections.ImmutableAPI不代表目标 Unity Mono/IL2CPP Player 中存在同一 API 表面和同一私有实现。应用最小 asmdef 探针编译并在目标设备构建运行不要把 CoreCLR 源码直接视为 Unity 源码。不可变快照适合将纯托管配置、寻路图索引或游戏规则表发布给工作线程。但集合不可变不会让GameObject、Transform、Texture等 Unity 对象变成可从后台线程访问也不会解决原生对象销毁后托管包装器的生命周期。快照的键值应是可跨线程安全读取的纯数据。节点树和路径复制会产生托管分配。在每帧更新成千上万键的热路径中不能仅因为“结构共享”就假设 GC 可忽略。对每个目标设备的 Player 实测更新批次、分配、托管堆、帧时间与驻留旧版本数量。如果只需要主线程可变状态普通Dictionary与明确帧边界可能更简单。十五、故障反例反例一忽略返回值。var map ImmutableDictionarystring, int.Empty; map.Add(score, 10); // 错误新字典被丢弃所有修改操作都返回新容器必须保存map map.Add(...)或者在表达式链中使用结果。编译器不会因为你忽略了返回值而报错。反例二将 Builder 发布给读者。Builder 是可变批处理工具多线程无同步读写会破坏安全边界。发布ToImmutable()返回的快照而不是 Builder。反例三值是可变对象却声称快照完全隔离。容器只冻结映射关系不会深拷贝。设计不可变值模型或在发布边界复制。反例四多写者用普通赋值替换根。两个写者基于同一旧根生成新根后赋值会丢失前更新。使用单写者、锁或原子 CAS 帮助 API。反例五依赖枚举顺序生成网络签名。哈希集合顺序不是跨版本规范。在签名编码中按明确的稳定比较器排序并固定数字、文本与转义格式。十六、可复现正确性与性能实验正确性测试应先覆盖持久化语义生成 v0逐步 Add/SetItem/Remove 得到 v1、v2、v3每一步都保留旧引用最后验证每个版本的内容与当时期望完全相同。同时对照一个简单的可变Dictionary副本作为参考模型。比较器测试应包含大小写等价键不同键返回相同哈希码值为default删除冲突桶的首项、中间项和最后一项从多元素桶删至空桶用 Builder 批量更新后确认旧快照未变。还应用故意常量哈希比较器覆盖最坏冲突路径但不要把它的性能当作正常负载结论。public sealed class ConstantHashComparer : IEqualityComparerint { public bool Equals(int x, int y) x y; public int GetHashCode(int value) 0; }并发发布测试应让多个读者持续读取根快照验证跨多键的业务不变式写者在局部完成整批变更后发布。对多写者 CAS 循环记录重试次数验证每个逻辑更新恰好一次出现并保证重算函数无不可重复副作用。性能实验应区分单项更新、批量 Builder 更新、稳态查找、全量枚举、保留多个旧版本以及全部丢弃旧版本。同时记录时间、分配字节、GC 次数与驻留堆固定 SDK/runtime、CPU、键分布、比较器、初始规模、更新批次和随机种子。对比Dictionary、ConcurrentDictionary、ImmutableDictionary和目标版本支持的 Frozen 容器时必须使用等价业务契约。如果一个方案每次保留版本另一个方案就地更新且不提供快照单纯对比每秒操作数不是公平比较。不要发布没有原始报告和可运行代码的固定倍数。十七、源码审查清单阅读一个特定版本的源码时可依次问代码属于哪个dotnet/runtimetag/commit目标应用实际加载哪个程序集版本一级树节点的整数键是什么它如何平衡空节点如何表示HashBucket 如何区分第一项和额外冲突项桶本身使用什么持久化结构键比较器和值比较器分别用在哪些 API 分支Add、SetItem、Remove 如何区分无变化、添加、更新与冲突树路径何时复制哪些子树直接共享平衡旋转会创建哪些节点Builder 如何标识节点所有权/冻结状态ToImmutable后继续修改为何不污染旧快照枚举器如何穿过树与桶是否有结构体枚举和接口枚举的不同路径更换比较器时是否需要重建新比较器使旧键等价时如何处理哪些结论是公共契约哪些只是该 tag 的分配或快路径优化结语ImmutableDictionary和ImmutableHashSet的核心不是一个可以从“持久化哈希容器”猜出来的 HAMT 标签。在可核验的目标 .NET 实现中它们通过按 32 位哈希码组织的平衡树定位桶用桶内相等比较解决哈希冲突通过路径复制和未变子树共享保留旧版本。不可变快照带来的主要收益是清晰的发布边界读者拿到一个根就能稳定遍历写者可以在私有新根上完成多步更新后一次发布。但它不会深度冻结键值对象不会自动解决多写者更新丢失也不会消除节点分配、GC 和最坏哈希冲突。正确选型需要回到业务语义需要高频原地更新就评估普通或并发字典构建一次长期只读就评估 Frozen 容器需要版本、原子快照和读者隔离时再选不可变容器。最后用固定 runtime tag 核对源码用坏哈希和并发发布测试边界用真实更新批次和版本保留模式测量成本。下一篇不可变集合综合对比与选型 
长河君 · 2026/9/8 16:56:48 · 阅读 1.2k 08-03-不可变-ImmutableDictionary-TKey-TValue-与ImmutableHashSet-T-持久化哈希树
ImmutableDictionary 与 ImmutableHashSet哈希桶树、结构共享与原子快照系列C# 与常用数据结构源码剖析 · 不可变集合篇阅读时间约 60 分钟前置知识哈希表、平衡树、持久化数据结构、比较器源码基线System.Collections.Immutable8.0.0对应dotnet/runtime v8.0.0/ commit5535e31a712343a63f5d7d796cd874e563e5ac14固定源码为 ImmutableDictionary_2.cs 与 ImmutableHashSet_1.cs。版本边界公共契约以目标 TFM 的 reference assembly 和官方 API 文档为准。本文的内部树、桶、节点名称与优化路径只指上述 8.0.0/v8.0.0基线不是跨版本承诺本文也不把它们想当然地写成 HAMT/CHAMP。一、先纠正数据结构这不是 32 路 HAMT不可变哈希容器经常用 Hash Array Mapped Trie 实现但“持久化 哈希”不能推导出某个 .NET 类一定使用 HAMT。在上述System.Collections.Immutable8.0.0/dotnet/runtime v8.0.0的两份源码中ImmutableDictionaryTKey,TValue和ImmutableHashSetT可分别概括为共享下列高层结构先通过键或元素的相等比较器计算 32 位哈希码。用哈希码作为整数键在平衡二叉树中定位一个哈希桶。哈希码相同的不同键/元素进入同一冲突桶再用相等比较器区分。修改时重建受影响的树路径和桶其他不变节点与旧版本共享。hash 25 / \ hash 8 hash 91 | | [hash bucket] [hash bucket] key A - value key X - value key B - value // A/B 同 hash但不相等因此原文中“每次取 5 bit、32 路分支、bitmap popcount”并不是这个实现的源码模型“百万元素只需四层”也不能用来分析它。本文使用“哈希桶树”这个教学名称但私有类名和精确平衡实现仍应通过目标 tag 核对。二、不可变的真正含义ImmutableDictionary的Add、SetItem、Remove不会就地修改原对象而是返回一个代表新内容的字典。旧引用仍然指向旧快照ImmutableDictionaryint, string v1 ImmutableDictionaryint, string.Empty; ImmutableDictionaryint, string v2 v1.Add(1, one); ImmutableDictionaryint, string v3 v2.SetItem(1, ONE); Console.WriteLine(v1.Count); // 0 Console.WriteLine(v2[1]); // one Console.WriteLine(v3[1]); // ONE这不等于每次都复制全部 n 个键值对。新版本可以共享未变的子树、桶内部持久化节点以及比较器。只有从根到目标哈希码的路径、发生改变的冲突桶和平衡修复所需节点发生更新。这就是结构共享。old root new root / \ / \ A B Add/Remove A B / \ ---- / \ C D C D A 和 C 被新旧版本共享只复制受影响路径。但不可变只适用于“集合自身的键值关系”。它不会递归冻结TKey、TValue或T对象。如果值是一个可变Listint修改该列表后所有共享同一列表引用的字典版本都会观察到新内容。var mutable new Listint { 1 }; var snapshot ImmutableDictionarystring, Listint.Empty .Add(numbers, mutable); mutable.Add(2); // snapshot[numbers] 现在也包含 2。字典不可变值并不是深层不可变。如果快照需要真正隔离值也应使用不可变模型、防御性副本或清晰的所有权转移。三、哈希桶树的不变式可以用三层不变式理解整个容器。第一层是树节点按有符号 32 位哈希码的确定顺序组织左子树、当前节点、右子树满足搜索树顺序并维持高度平衡。第二层是桶树中每个哈希码最多对应一个桶桶内包含所有具有该哈希码的键值对或集合元素。它们可能相等也可能只是哈希冲突需要再用相等比较器区分。第三层是版本已发布给不可变容器的节点不能再被就地修改。新操作只能创建新路径并让新根指向旧子树和新节点的组合。Builder 可以在独占的可变阶段里复用节点但发布为不可变快照后必须遵守这个边界。四、比较器是容器语义的一部分ImmutableDictionaryTKey,TValue至少涉及键比较器和值比较器。键比较器决定哈希码和键相等因此决定字典中“同一个键”的意义。值比较器用于需要判断已有值与新值是否相同的操作语义。应在创建空集合时就选定比较器ImmutableDictionarystring, int scores ImmutableDictionary.Createstring, int(StringComparer.OrdinalIgnoreCase); scores scores.Add(Player, 10); // scores.Add(player, 20) 会遇到已有键。一个正确的相等比较器必须满足若Equals(a,b)为真则GetHashCode(a)必须等于GetHashCode(b)。哈希相同不必推出相等冲突桶就是为了处理这种情况。比较结果还必须在键存活期间稳定不能依赖会改变的全局状态。WithComparers一类 API 表面上只是换比较器语义上却可能改变键等价类。例如从 ordinal 换到 ordinal-ignore-case 时原来两个不同键可能合并为冲突。具体 API 对这种冲突如何处理应查目标版本契约不能把更换比较器当成 O(1) 字段赋值。五、Add、SetItem 和 RemoveAdd(key,value)表示“添加一个不存在的键”。已存在等价键时若不满足目标 API 允许的幂等情况它会通过异常报告冲突。这适合重复就是错误的注册边界。SetItem(key,value)表示 upsert键不存在时添加键存在时替换值。如果操作没有造成逻辑变化实现可能返回原实例但调用者不应用引用相等代替集合内容语义。Remove(key)在键存在时从冲突桶中移除该键值对。桶中还有其他冲突键时替换该桶桶变空时从哈希树中移除整个哈希码节点并修复平衡。键不存在时结果在内容上与原字典一致。下面是结构化伪代码不是任何 runtime tag 的逐字源码// 伪代码用于解释路径复制和桶更新。 Node SetItem(Node node, int hash, TKey key, TValue value) { if (node.IsEmpty) return NewNode(hash, Bucket.Single(key, value)); if (hash node.Hash) return Balance(node.WithLeft(SetItem(node.Left, hash, key, value))); if (hash node.Hash) return Balance(node.WithRight(SetItem(node.Right, hash, key, value))); Bucket updated node.Bucket.SetItem(key, value, _keyComparer); return node.WithBucket(updated); }WithLeft、WithRight和WithBucket在不可变路径上产生新节点未走过的子树引用被原样复用。Balance只对被修改路径做局部旋转。真实源码还包含变更结果、计数、已冻结节点与各种快路径需按固定 tag 阅读。六、ImmutableHashSet 的同与不同ImmutableHashSetT只保存唯一元素没有独立 TValue。在目标实现中它与不可变字典共享“哈希码平衡树 冲突桶”的整体思路但桶的元素和更新语义不同。它使用IEqualityComparerT同时定义元素的哈希和相等。ImmutableHashSetstring tags ImmutableHashSet.Createstring(StringComparer.OrdinalIgnoreCase); tags tags.Add(Boss); tags tags.Add(boss); // 逻辑内容仍只有一个等价元素集合的并集、交集、差集和对称差集都会返回新集合但新实例可以共享未变结构。具体算法是否会利用另一个同类集合的内部结构、哪个操作会转到 Builder都属于需按版本核验的优化。七、Builder在可变阶段批量修改连续写map map.SetItem(...)在语义上完全正确但每步都要产生一个可独立发布的不可变根。当业务是“在单一所有者中执行一批修改然后发布一个快照”时Builder 可以减少中间版本和部分路径分配。ImmutableDictionarystring, Player.Builder builder snapshot.ToBuilder(); foreach (PlayerDelta delta in deltas) { if (delta.IsRemoved) builder.Remove(delta.Id); else builder[delta.Id] delta.Player; } ImmutableDictionarystring, Player next builder.ToImmutable();Builder 是可变对象不继承不可变快照的无锁并发读特性。不应让多个线程无同步共享一个 Builder。一个安全模式是更新线程独占 Builder读者只能看到上一个已发布的ImmutableDictionary整批更新完成后才替换快照引用。ToImmutable()之后 Builder 仍可以继续修改但已返回的快照不会被后续修改污染。这需要实现在节点上维护可变/冻结所有权边界并在必要时恢复路径复制不能把 Builder 理解成直接篡改已发布树。八、枚举顺序不是哈希容器的持久化契约不可变集合在枚举过程中不会被修改因此枚举器不需要像可变Dictionary一样对后续写做 fail-fast 版本检测。这非常适合长时间读快照写者创建新根已经获得旧根的枚举器继续读旧结构。但枚举顺序由内部哈希码树、哈希比较器和冲突桶布局决定不是插入顺序、键排序或跨运行时稳定顺序的承诺。字符串哈希策略、比较器或私有实现改变时顺序可以改变。如果需要确定性序列化、跨设备哈希或可读 diff应在输出边界按明确比较规则排序不能依赖当前枚举的偶然顺序。排序会产生自己的时间和快照内存成本应只在真正需要规范化的边界做。九、复杂度平衡树高度与冲突桶同时存在设不同哈希码的数量为h目标哈希码桶内有c个冲突元素。在目标实现模型下查找、添加或删除首先支付 O(log h) 的平衡树定位再支付冲突桶中相等比较的成本。当哈希分布良好时c很小当大量键返回同一哈希码时操作可退化为对长冲突桶的线性搜索。操作良好哈希分布的模型极端冲突的边界按键/元素查找O(log h c)可退化至 O(n)Add / SetItem / Remove树路径 桶更新桶搜索/更新可 O(n)枚举O(n)O(n)Builder 批量更新减少中间分配不会修复坏哈希函数表中没有写“O(1) 哈希查找”因为该源码模型的一级索引是哈希码平衡树不是可直接按桶余数定位的可变数组。也不能写成O(log_32 n)因为这不是 32 路 trie。渐近复杂度不说明分配、节点跳转和比较器成本。不可变树为单次更新分配新路径局部性通常不如连续DictionaryEntry 数组。结构共享节省了整体复制却不代表“无分配”或“与可变字典速度相同”。必须根据版本数量、更新批次、键分布和目标 runtime 实测。十、键不变式不可变字典也怕可变键字典不修改自己不意味它能防止外部修改键对象。键加入后任何影响GetHashCode或Equals的状态都必须保持不变。否则键仍然存储在旧哈希码对应的树节点中但查找会计算新哈希码并走向另一个节点。public sealed class BadKey { public string Name { get; set; } ; public override int GetHashCode() Name.GetHashCode(); public override bool Equals(object? obj) obj is BadKey other Name other.Name; }这种键即使放入ImmutableDictionary也不安全。更好的键是不可变值对象、封装的整数 ID 或不可变字符串。若业务实体的名称会变使用稳定 ID 作键将名称放在值中。另一个反例是所有键都返回常量哈希码。它可以满足“相等键哈希相同”的最低正确性契约却会把全部元素放入一个冲突桶使查找与更新退化。正确的哈希函数还应尽量使典型键均匀分布但不要为了均匀而破坏等价契约。十一、原子发布与多步更新不可变对象非常适合快照发布写者在私有局部变量中构建完整新字典然后一次替换共享根引用。读者只需读取一次根引用整个操作期间都使用同一快照。private ImmutableDictionarystring, Player _players ImmutableDictionarystring, Player.Empty; public ImmutableDictionarystring, Player Snapshot() Volatile.Read(ref _players); public void Publish(ImmutableDictionarystring, Player next) Volatile.Write(ref _players, next);这个例子只适合单写者或写者已由外部串行化的系统。若两个写者都读取同一旧快照各自添加不同键并先后Volatile.Write后发布者会覆盖前者的更新。不可变保证快照不被就地破坏不保证 read-modify-write 组合自动原子。多写者可以用 CAS 循环从当前快照计算新快照只有当根仍是原来那个引用时才替换失败则基于新根重算。标准不可变帮助 API 提供了对应的原子更新模式但具体重试回调可能执行多次不能在其中直接发送邮件、扣款或产生不可重复的副作用。// 结构化模式实际项目优先使用目标版本的 ImmutableInterlocked API。 while (true) { var before Volatile.Read(ref _players); var after before.SetItem(player.Id, player); if (ReferenceEquals( Interlocked.CompareExchange(ref _players, after, before), before)) break; }多个键需要共同满足业务不变式时应在一个局部快照上完成所有SetItem/Remove最后只发布一次根。不要每改一个键就发布否则读者可能看到业务上无效的中间状态。十二、GC 成本与版本保留结构共享降低了“每次快照复制整个字典”的成本但新路径、新桶和新根仍是托管对象。高频单项更新可以产生大量短命节点Builder 能降低批处理中间分配却不会把最终不可变结构变成连续数组。只要某个旧快照仍被引用它独有的节点以及通过共享节点可达的键值对就不能被 GC 回收。这是版本快照正确性的必然结果。无界保留每一个历史版本会使内存随业务历史增长并不是“因为共享就几乎免费”。需要 undo/redo 时应设定版本上限、检查大对象值和深层可变值并用堆快照定位保留根。需要长期审计时增量事件日志或周期 checkpoint 可能比在内存中保留所有集合根更合适。十三、与 Dictionary、ConcurrentDictionary 和 FrozenDictionary 的区别容器更新模型并发读/写快照适合场景DictionaryTKey,TValue原地可变写需外部同步需复制单所有者、高频可变更新ConcurrentDictionaryTKey,TValue共享可变提供并发原子 API枚举语义需按契约理解多线程持续按键更新ImmutableDictionaryTKey,TValue返回新根已发布快照可并发读写者需协调原生版本读多写少、原子快照、undoFrozenDictionaryTKey,TValue构建后冻结只读发布没有增量新版本 API构建一次、长期查询FrozenDictionary面向“准备阶段可以付出构建成本之后大量只读查询”不是可持久化更新树。它的 API 可用性和实现优化要查目标 .NET 版本。每次数据变化都重建 Frozen 容器可能让构建成本主导。ConcurrentDictionary适合多写者对共享当前状态做按键更新但一系列不同键的更新不自动变成一个原子快照。ImmutableDictionary可以在私有新根上完成多键变更后一次发布但写者之间必须用 CAS 重试或串行所有权解决更新丢失。十四、Unity 边界Unity 项目首先要核对目标 Editor 版本、API Compatibility Level、引用程序集、包版本、后端和平台。桌面当前 .NET SDK 支持某个System.Collections.ImmutableAPI不代表目标 Unity Mono/IL2CPP Player 中存在同一 API 表面和同一私有实现。应用最小 asmdef 探针编译并在目标设备构建运行不要把 CoreCLR 源码直接视为 Unity 源码。不可变快照适合将纯托管配置、寻路图索引或游戏规则表发布给工作线程。但集合不可变不会让GameObject、Transform、Texture等 Unity 对象变成可从后台线程访问也不会解决原生对象销毁后托管包装器的生命周期。快照的键值应是可跨线程安全读取的纯数据。节点树和路径复制会产生托管分配。在每帧更新成千上万键的热路径中不能仅因为“结构共享”就假设 GC 可忽略。对每个目标设备的 Player 实测更新批次、分配、托管堆、帧时间与驻留旧版本数量。如果只需要主线程可变状态普通Dictionary与明确帧边界可能更简单。十五、故障反例反例一忽略返回值。var map ImmutableDictionarystring, int.Empty; map.Add(score, 10); // 错误新字典被丢弃所有修改操作都返回新容器必须保存map map.Add(...)或者在表达式链中使用结果。编译器不会因为你忽略了返回值而报错。反例二将 Builder 发布给读者。Builder 是可变批处理工具多线程无同步读写会破坏安全边界。发布ToImmutable()返回的快照而不是 Builder。反例三值是可变对象却声称快照完全隔离。容器只冻结映射关系不会深拷贝。设计不可变值模型或在发布边界复制。反例四多写者用普通赋值替换根。两个写者基于同一旧根生成新根后赋值会丢失前更新。使用单写者、锁或原子 CAS 帮助 API。反例五依赖枚举顺序生成网络签名。哈希集合顺序不是跨版本规范。在签名编码中按明确的稳定比较器排序并固定数字、文本与转义格式。十六、可复现正确性与性能实验正确性测试应先覆盖持久化语义生成 v0逐步 Add/SetItem/Remove 得到 v1、v2、v3每一步都保留旧引用最后验证每个版本的内容与当时期望完全相同。同时对照一个简单的可变Dictionary副本作为参考模型。比较器测试应包含大小写等价键不同键返回相同哈希码值为default删除冲突桶的首项、中间项和最后一项从多元素桶删至空桶用 Builder 批量更新后确认旧快照未变。还应用故意常量哈希比较器覆盖最坏冲突路径但不要把它的性能当作正常负载结论。public sealed class ConstantHashComparer : IEqualityComparerint { public bool Equals(int x, int y) x y; public int GetHashCode(int value) 0; }并发发布测试应让多个读者持续读取根快照验证跨多键的业务不变式写者在局部完成整批变更后发布。对多写者 CAS 循环记录重试次数验证每个逻辑更新恰好一次出现并保证重算函数无不可重复副作用。性能实验应区分单项更新、批量 Builder 更新、稳态查找、全量枚举、保留多个旧版本以及全部丢弃旧版本。同时记录时间、分配字节、GC 次数与驻留堆固定 SDK/runtime、CPU、键分布、比较器、初始规模、更新批次和随机种子。对比Dictionary、ConcurrentDictionary、ImmutableDictionary和目标版本支持的 Frozen 容器时必须使用等价业务契约。如果一个方案每次保留版本另一个方案就地更新且不提供快照单纯对比每秒操作数不是公平比较。不要发布没有原始报告和可运行代码的固定倍数。十七、源码审查清单阅读一个特定版本的源码时可依次问代码属于哪个dotnet/runtimetag/commit目标应用实际加载哪个程序集版本一级树节点的整数键是什么它如何平衡空节点如何表示HashBucket 如何区分第一项和额外冲突项桶本身使用什么持久化结构键比较器和值比较器分别用在哪些 API 分支Add、SetItem、Remove 如何区分无变化、添加、更新与冲突树路径何时复制哪些子树直接共享平衡旋转会创建哪些节点Builder 如何标识节点所有权/冻结状态ToImmutable后继续修改为何不污染旧快照枚举器如何穿过树与桶是否有结构体枚举和接口枚举的不同路径更换比较器时是否需要重建新比较器使旧键等价时如何处理哪些结论是公共契约哪些只是该 tag 的分配或快路径优化结语ImmutableDictionary和ImmutableHashSet的核心不是一个可以从“持久化哈希容器”猜出来的 HAMT 标签。在可核验的目标 .NET 实现中它们通过按 32 位哈希码组织的平衡树定位桶用桶内相等比较解决哈希冲突通过路径复制和未变子树共享保留旧版本。不可变快照带来的主要收益是清晰的发布边界读者拿到一个根就能稳定遍历写者可以在私有新根上完成多步更新后一次发布。但它不会深度冻结键值对象不会自动解决多写者更新丢失也不会消除节点分配、GC 和最坏哈希冲突。正确选型需要回到业务语义需要高频原地更新就评估普通或并发字典构建一次长期只读就评估 Frozen 容器需要版本、原子快照和读者隔离时再选不可变容器。最后用固定 runtime tag 核对源码用坏哈希和并发发布测试边界用真实更新批次和版本保留模式测量成本。下一篇不可变集合综合对比与选型