不可变集合综合篇栈、队列、Builder 与原子更新专栏C# 与常用数据结构源码剖析基线公开语义以 .NET 8 /System.Collections.Immutable对应版本为主私有字段与节点布局必须按具体包 tag 复核核心主题不可变性不是“修改时复制整个集合”而是通过结构共享、受控批处理和原子发布管理状态版本。不可变集合的价值常被一句话概括“读取天然线程安全”。这是结果不是设计方法。真正需要掌握的是旧版本为什么不被破坏新版本复用了多少旧节点批量更新何时应用 Builder多线程同时替换根引用时怎么避免丢失更新以及“集合不可变”为什么不等于“元素对象不可变”。1. 心智模型值是某个版本的根可变集合往往有一个长期存活的容器对象Add修改它的内部数组、树或计数。不可变集合的更新方法返回新根ImmutableStackint v0 ImmutableStackint.Empty; ImmutableStackint v1 v0.Push(10); ImmutableStackint v2 v1.Push(20); // v0、v1、v2 都仍然是合法且独立可观测的版本。此时“值”不一定意味着整个对象图都被复制。新根可以指向旧版本已有的不可变子结构这称为结构共享。只要共享节点永不被就地修改两个版本就能安全共存。这带来四个后果保留旧根即可保留旧快照适合撤销、配置切换和读多写少状态更新成本是“新建的路径/节点”不一定是整个集合也不一定是零长期保留很多旧根会让共享子图继续存活GC 不能回收仍可达节点容器不可变只限制索引/节点关系不会冻结元素对象的字段。2.ImmutableStackT单链表是持久化栈的理想形状2.1 不变式与结构共享教学模型可以把非空栈理解为一个值与后继栈。下列是伪代码不是 BCL 逐字源码Stack Push(T value) new Node(value, this); Stack Pop() IsEmpty ? throw ... : Tail; T Peek() IsEmpty ? throw ... : Head;当v2 v1.Push(20)时新版本只需要新头节点其后继直接指向v1的整条链v2 - [20] - [10] - Empty ^ v1 -------------| v0 --------------------- Empty关键不变式是非空节点的值与后继在构造后不变后继最终到达标准空栈不存在环。Push、Pop、Peek都只处理根附近的节点因而是 O(1)。但每次Push会为新版本分配节点“O(1)”不是“零分配”。2.2Pop不销毁旧版本ImmutableStackint newer older.Push(42); ImmutableStackint back newer.Pop(); // back 的逻辑内容与 older 相同 // older 和 newer 仍可继续使用。Pop返回后继栈不会清空原栈或对原节点执行手工释放。只有当没有任何根再引用节点时GC 才能回收它。如果撤销历史保留了每次推入后的根那么保留内存是功能需求的直接结果。2.3 叠代与并发读节点不变使遍历某个根时无需版本检查。将一个已安全发布的栈根分享给多个线程后各线程可以同时遍历。但若T是可变对象各版本共享的也是同一元素引用容器无法保证对象内部读写安全。3.ImmutableQueueT用两个不可变栈实现均摊 FIFO3.1 为什么单链表不能同时优惠两端不可变单链表在头部添加很便宜但在尾部添加若没有其他结构需要重建整条前缀。持久化队列因此将状态分成两部分出队栈顶部是下一个出队元素入队栈新元素以反向顺序压入。这是概念模型具体字段名应以固定包版本为准逻辑队列: A, B, C, D 出队栈: top - A - B 入队栈: top - D - C当出队栈非空时Peek/Dequeue在其顶部处理。当它为空而入队栈非空时需将入队栈的顺序反转使最早元素成为新的出队栈顶。3.2 均摊 O(1) 的证明与边界单次反转可以是 O(n)所以不能声称每次Dequeue最坏 O(1)。在不反复回到特意构造的旧版本并重复触发同一逻辑转移的常规线性使用序列中每个元素入入队栈一次、反转到出队方向一次、移出一次因而可以均摊为 O(1)。持久化使事情比可变双栈更微妙程序可以保留分支版本成本分析要明确是单条演化路径还是任意版本 DAG。对普通 API 选型“线性使用下均摊 O(1)”是比“所有操作永远 O(1)”更准确的表述。3.3 出队返回的是新队列var q0 ImmutableQueueint.Empty; var q1 q0.Enqueue(10).Enqueue(20); int first q1.Peek(); var q2 q1.Dequeue(); // q1 仍表示 [10, 20]q2 表示 [20]。忽略返回值是不可变 API 中最常见的错误之一q1.Enqueue(30); // 结果未保存q1 不会被就地修改。编译器不一定能判定这是错误代码评审或分析器应把忽略不可变集合更新结果视为重点。4. Builder受控的可变窗口不是通用共享容器ImmutableArrayT、ImmutableListT、ImmutableDictionaryTKey,TValue等类型提供各自的 Builder 或创建器 API用于在局部范围内完成多次修改再生成不可变结果var builder ImmutableList.CreateBuilderint(); for (int i 0; i source.Length; i) { if (source[i] 0) builder.Add(source[i]); } ImmutableListint snapshot builder.ToImmutable();不能把所有 Builder 统一解释成“内部就是ListT最后只复制一次”。ImmutableArrayT.Builder偏向数组容量模型树形 Builder 可以通过所有权/冻结策略在受控范围内重用或就地调整尚未共享节点。精确做法会随类型和包版本不同。Builder 的通用契约是它可变且通常不承诺并发写安全。正确生命周期是在一个明确所有者内创建完成批量增删、去重或排序生成不可变根只发布不可变结果不发布 Builder若继续修改 Builder要依赖其公开契约保证已生成快照不受影响。ToImmutable()不保证对所有 Builder 都是 O(1) 或零分配。专用的MoveToImmutable()之类 API 可能转移内部存储所有权但往往有容量必须恰好匹配计数等前置条件且转移后 Builder 状态必须按目标版本文档处理。不要把某一 Builder 的优化推广给所有不可变集合。5. 原子发布不可变数据把大临界区缩成根交换不可变集合为无锁读取提供了很好的基础写者在私有局部变量中构造新版本最后一次原子替换共享根读者捕获某个根后遍历不会被改坏的对象图。但下面的普通赋值存在丢失更新// 错误模式两个线程可同时基于同一旧根计算 // 后写者覆盖先写者。 shared shared.Add(item);概念上需要 CAS 循环// 教学伪代码 do { observed Volatile.Read(ref shared); updated observed.Add(item); } while (Interlocked.CompareExchange( ref shared, updated, observed) ! observed);ImmutableInterlocked提供针对若干不可变集合的帮助操作可以避免每个项目自行写 CAS 细节。它的Update类回调可因 CAS 竞争而执行多次因此必须是可重试的纯转换不应在回调中发奖、扣款、写文件或发送网络消息。原子根替换的优势是读者不需要参与长时间的锁。代价是写竞争时失败线程刚刚构造的新版本可能被丢弃并重新计算。当转换很昂贵、写者很多或必须原子更新多个独立根时一把锁保护 Builder/整体状态可能更合适。6. 容器不可变与深度不可变以下列表的结构不会变但玩家对象可以变sealed class Player { public int Score; } var player new Player { Score 10 }; var snapshot ImmutableArray.Create(player); player.Score 999; // snapshot[0].Score 现在也观测到 999。不可变集合保证的是不能通过它的 API 增删或替换元素不是对元素做深拷贝。真正快照通常需要元素也是不可变值或在进入快照时执行防御复制。其他常见边界包括字典/集合的键若在加入后改变哈希或比较字段查找不变式仍会破坏ReadOnlyCollectionT只是一个不暴露修改 API 的视图底层可变集合仍可被其他持有者修改把 Builder 当作全局单例会重新引入共享可变状态序列化时得到的是值内容内存中的结构共享关系一般不会被自动保留。7. 全家族选型根据更新形状不根据名字需求候选类型主要成本/边界构造后主要按索引顺序读ImmutableArrayT紧凑数组单点增删常需复制区间保留多版本且经常中间增删ImmutableListT树形路径复制随机读与局部性不如数组按键保留多版本ImmutableDictionaryTKey,TValue哈希、碰撞、比较器与节点分配无重复元素及集合运算ImmutableHashSetT元素等价性由比较器决定需要键/元素有序ImmutableSortedDictionary/ImmutableSortedSet比较全序、树高与路径复制版本只在头部推入/弹出ImmutableStackT操作 O(1)新推入分配节点LIFO持久化 FIFOImmutableQueueT双栈反转线性演化下均摊 O(1)本地批量生成一个快照对应 Builder/工厂可变期间要独占转快照成本依类型而异如果不需要保留旧版本且所有读写都在一个所有者内可变ListT/DictionaryTKey,TValue可能更简单、分配更少。如果是高频多写者就地更新ConcurrentDictionary之类并发容器可能比反复构造整个不可变根更合适。不可变是状态管理选择不是无条件性能优化。8. Unity 场景配置快照很好每帧重建要谨慎Unity 中的System.Collections.Immutable可用性要以具体编辑器版本、API Compatibility Level、包/程序集引用和目标平台为准。不应仅因为某个 .NET 8 控制台示例可以编译就假定所有 Unity Mono/IL2CPP 目标都提供同一包版本和相同实现。适合的模式包括后台解析一份纯托管配置生成不可变根后原子发布主线程每帧只捕获一次根战斗规则、本地化表或导航参数的版本化旧任务继续使用启动时快照编辑器工具中的撤销/重做根但要控制历史长度和大资源引用。不适合直接照搬的模式是每帧、每实体为高频变动数据生成大量中间版本。这可增加托管分配和 GC 压力。先在单所有者可变状态中批量计算在帧边界或配置提交点生成一个快照通常更符合成本模型。Unity API 的主线程限制也不会因为根不可变而消失。快照中应尽量存放纯数据或稳定 ID而不是让后台线程通过快照访问GameObject、Transform等引擎对象。9. 常见失败模式9.1 把忽略返回值当作就地修改所有返回新集合的操作都必须保存结果。建议尽量使用不重用旧名称的版本变量让快照演化可见。9.2 高竞争 CAS 中执行昂贵转换每次 CAS 失败都可能丢弃一个刚构造的版本。如果每次转换会解析大文件或建立巨大索引应把计算与提交分离或使用串行写者。9.3 为了“零锁”分裂必须一致的根玩家索引、队伍索引和版本号若必须共同切换将它们分别存入三个原子字段会产生混合世代。应把它们组合成一个不可变状态对象一次发布整个根。9.4 把 Builder 泄漏给读者读者如果拿到 Builder就重新进入并发可变状态问题。对外 API 只返回不可变值Builder 保持在函数、事务或单一写者内部。9.5 无限保留快照结构共享能节约许多重复内存但不能让保留历史变成免费。对撤销栈设定步数/字节预算对运行时配置只保留活动世代和必要回退世代。10. 可复现实验与性质测试10.1 版本独立性从空集合开始生成一系列随机操作保存每一个根及对应的普通模型副本。完成全部更新后再倒序验证每个旧根内容未改变。这能发现自研持久化结构误修改共享节点的问题。10.2 栈与队列差分测试将不可变栈与测试中的可变StackT对照将不可变队列与QueueT对照。随机生成 Push/Pop 或 Enqueue/Dequeue每步比较顶/队头、元素序列、空状态与异常。额外保留随机旧根并从它分叉验证分支不互相影响。10.3 原子更新压力测试多个线程各自加入唯一编号通过ImmutableInterlocked更新共享根。所有线程结束后验证每个编号恰好存在一次。在回调中另外累加调用计数观察它可能高于成功更新数用事实证明回调必须可重试。10.4 成本实验分别比较“每步生成新集合”、“Builder 批量后一次生成”和“可变集合构造后转快照”。固定输入序列和最终语义报告 SDK、包版本、CPU、OS、GC 模式、操作数、分配和高分位耗时。测试另分纯线性演化和保留多分支版本两种负载。不提前写死“Builder 快多少倍”。输入大小、操作形状、版本保留、类型实现和 JIT/AOT 都会改变结果。11. 代码评审清单需求确实需要快照、多版本或无锁读而不是只追求“函数式”标签选择的集合形状与更新模式匹配索引读、中间增删、键查找、LIFO 或 FIFO每个更新方法的返回值都被保存或明确丢弃Builder 只有单一所有者不作为公共可变状态发布多写者更新使用 CAS/帮助 API 或显式锁不依赖普通读改写CAS 回调无不可重试副作用且已考虑高竞争重算成本元素是不可变值或已为可变元素定义同步/防御复制快照历史有上限大对象、资源和旧节点的留存可观测Unity 主线程限制、包参考、IL2CPP 构建与真机分配均已验证性能结论固定运行时/包版本并保留原始实验配置和结果。12. 总结ImmutableStackT利用单链后继实现 O(1) 根部更新ImmutableQueueT用两个方向相反的栈换取线性演化下的均摊 FIFO。它们的共同基础是新版本创建新根或少量新节点而旧版本可继续安全引用不变子结构。Builder 在单一所有者内提供受控可变窗口原子根替换则让完整快照在线程间发布。两者的边界必须分清Builder 不是并发容器CAS 更新也不保证回调只执行一次。最后不可变只有在更新形状、快照价值与分配预算同时吻合时才是优势它从来不是免费的性能标签。