ImmutableListT持久化 AVL 树实现系列C# 与常用数据结构源码剖析 · 不可变集合篇阅读时间约 80 分钟源码基线System.Collections.Immutable8.0.0对应 dotnet/runtime v8.0.0 / 5535e31a... 的 ImmutableList_1.cs版本边界本文固定上述包版本与仓库 tag。字段布局、Builder 优化和枚举器池化属于实现细节升级时应按新 tag 复核。代码约定所有算法代码均标为结构化节选、教学伪代码或业务示例不冒充逐字源码。一、先纠正定位它是序列树不是排序集合ImmutableListT保持插入顺序允许重复元素并通过整数索引访问。内部 AVL 树不是按IComparerT比较元素来决定左右分支而是用左子树节点数表达序列位置。Add(x)把 x 插在末尾Insert(i,x)把 x 插在逻辑位置 iSetItem(i,x)替换位置 i。所以旧稿中“比较 item小于走左、大于走右、相等不插入”的示例属于 SortedSet 一类结构完全不适用于 ImmutableList。以下序列是合法的// 业务示例保序且允许重复。 ImmutableListint values ImmutableList.Create(30, 10, 30, 20); ImmutableListint next values.Insert(1, 99); // values: 30, 10, 30, 20 // next: 30, 99, 10, 30, 20“不可变”指集合对象的可观察结构不会被其公开修改方法原地改变方法返回新列表旧列表仍表示原序列。它不是把整个对象图深度冻结也不意味着每次修改复制整棵树。持久化数据结构通过共享未改变子树让多个历史版本同时存在。二、Node、空哨兵与四个核心不变量.NET 8基线 Node 的重要状态可结构化为// 结构化节选名称与含义按 8.0.0省略方法和可空细节。 private sealed class Node { internal T _key; internal Node _left; internal Node _right; internal byte _height; internal int _count; internal bool _frozen; internal static readonly Node Empty new Node(); }字段名_key容易让人误以为这是按键搜索树在 ImmutableList 中它就是当前节点保存的元素。Node 使用单例Empty表示空子树而非让每个叶节点的 Left/Right 为 null。空哨兵能统一递归边界但 Empty 的内部访问契约仍应按源码使用不能把它当普通可写节点。对任意非空节点 n必须满足n.Count 1 n.Left.Count n.Right.Count n.Height 1 max(n.Left.Height, n.Right.Height) abs(n.Right.Height - n.Left.Height) 1 逻辑序列 Left 的序列 n.Key Right 的序列空哨兵的 Count 和 Height 为 0并处于冻结状态。根的 Count 就是列表 Count。高度存成 byte 是当前实现选择不是公开 APIAVL 平衡让现实可构造规模的高度保持很小但不要由字段宽度反推公开最大容量。第四个关键不变量是冻结边界对外发布为 ImmutableList 的节点图必须冻结任何后续“修改”都不能原地改变这些节点。Builder 暂时拥有的未冻结节点则可在所有权协议内原地更新。_frozen不是线程锁而是持久化写时复制的所有权标记。三、索引导航左子树 Count 是隐式秩节点的逻辑索引等于左子树 Count。访问索引 i 时i left.Count目标在左子树i left.Count目标就是当前元素i left.Count进入右子树并把 i 减去left.Count 1。// 教学伪代码展示秩导航参数校验和真实辅助方法已省略。 T ItemAt(Node node, int index) { while (!node.IsEmpty) { int leftCount node.Left.Count; if (index leftCount) { node node.Left; } else if (index leftCount) { return node.Key; } else { index - leftCount 1; node node.Right; } } throw new ArgumentOutOfRangeException(nameof(index)); }树高 O(log n)因此索引访问也是 O(log n)不像ListT和ImmutableArrayT的数组索引 O(1)。AVL 不按元素值组织IndexOf(value)无法凭大小关系走单边通常要按指定范围和IEqualityComparerT扫描时间上界 O(n)。Contains 也不因内部是树就自动成为 O(log n)。索引参数边界因操作不同读取、RemoveAt、SetItem 要求0 index CountInsert 允许index Count表示追加。区间重载还需防止 index count 溢出使用公开 API 时依赖其参数检查不自行写容易溢出的判断。四、路径复制持久化修改的通用骨架假设要修改从根到某个索引的路径。下降时只有一个子树包含目标另一个子树可以直接共享。回升时为路径上的每层产生新版本节点并重新计算 Count、Height再按需旋转。旧根仍指向旧路径新根指向新路径共同子树被两个版本同时引用。图中只有根到目标的节点链被新版本替换S1、S2、S3仍是同一批节点对象。旋转可能让新路径的局部形状与图不同但不会改变“旧根保留旧视图未修改子树尽量共享”的持久化边界。“每次严格创建 log₂(n) 个节点”并不准确。AVL 高度只是 O(log n)实际路径长度取决于树形旋转会构造或变异额外路径节点空列表添加只涉及少量节点Builder 还可能复用未冻结节点。可靠结论是普通单点永久修改访问 O(log n) 高度并产生 O(log n) 量级的新节点/路径状态而不是固定数量或固定共享百分比。结构共享也不等于旧版本免费。只要任何历史根仍可达它独有的旧路径与元素就不能回收。保存每一帧快照会让大量版本共同子树长期存活同时累计每次修改产生的新路径。内存预算必须考虑“活跃版本数 × 修改路径”而不只是最新列表 Count。五、Add 与 Insert按位置插入并恢复 AVLAdd(item)等价于在逻辑Count处插入Insert(index,item)通过左子树 Count 导航。概念递归如下// 教学伪代码不体现真实 Mutate/Freeze 优化和所有旋转分支。 Node Insert(Node node, int index, T item) { if (node.IsEmpty) return NewLeaf(item); int leftCount node.Left.Count; Node candidate; if (index leftCount) candidate Copy(node, left: Insert(node.Left, index, item)); else candidate Copy(node, right: Insert(node.Right, index - leftCount - 1, item)); return Balance(candidate); }注意index leftCount插到当前节点位置时新项应位于当前项之前因此进入左侧的相应末端。每次 Copy/Mutate 后必须更新 Count 和 Height。5.1 单旋与双旋定义平衡因子为右高减左高源码辅助函数的符号应按 tag 阅读。若一侧高度比另一侧超过 1需要旋转左左偏重 - 右旋 右右偏重 - 左旋 左右偏重 - 先左旋左孩子再右旋 右左偏重 - 先右旋右孩子再左旋持久化旋转不能原地改动已冻结节点。基线通过 Node 的Mutate类路径节点若未冻结可更新字段并返回自身若冻结则构造带新孩子/新 key 的节点。旋转调用这些受控变更因此对 ImmutableList 返回的新根不会破坏旧版本而 Builder 可以复用自己尚未冻结的节点。AddRange/InsertRange 不是简单保证逐项调用单点 Insert基线含针对输入和树构建的批量路径。复杂度与分配要结合输入类型和版本不应从单点公式机械乘 m。批量创建时优先使用CreateRange、AddRange或 Builder而不是先构造许多中间不可变版本。六、Remove、RemoveAt 与 SetItem6.1 RemoveAt删除一个序列位置删除路径仍由左 Count 导航。目标节点无孩子时返回 Empty只有一个非空孩子时返回该孩子两个孩子时可用右子树最左节点逻辑后继的元素替换当前元素再从右子树删除那个最左节点。回升时更新统计并平衡。// 教学伪代码只表达两个孩子时的序列保持逻辑。 if (index leftCount) { if (node.Right.IsEmpty) return node.Left; if (node.Left.IsEmpty) return node.Right; Node successor Leftmost(node.Right); Node rightWithoutSuccessor RemoveMin(node.Right); return Balance(Copy(node, key: successor.Key, right: rightWithoutSuccessor)); }用后继替换不会改变逻辑序列中其他元素的相对顺序。被删除的元素若不再被任何列表版本、调用者或其他对象引用最终可回收旧版本仍保留它是持久化语义而不是泄漏。6.2 Remove(value) 先寻找相等元素Remove(value, comparer)删除指定比较器命中的第一个元素。由于树不按 value 排序查找阶段可能 O(n)找到索引后的路径删除 O(log n)总体 O(n)。重复元素只删除一个匹配项RemoveAll、RemoveRange有各自语义和批量成本不能只看 AVL 高度宣称所有 Remove 都是 O(log n)。若未找到元素公开结果可复用原列表实例因为逻辑内容不变调用者应依据值语义不把引用是否相同当作跨版本契约除非文档明确保证。6.3 SetItem替换但不改变长度SetItem(index,value)只复制/变异到目标的路径把节点 key 换成 value左右结构及 Count 不变不需要因高度变化进行旋转。它仍为 O(log n)不可变路径通常分配 O(log n) 节点。新值可以与别处元素相等因为 ImmutableList 允许重复。Replace(oldValue,newValue,comparer)需要先按相等性查找 oldValue再调用位置替换所以查找可能 O(n)。区分“按索引已知位置”和“按值搜索”对理解复杂度非常重要。七、Builder受所有权约束的暂时可变树7.1_frozen的真实作用.NET 8Node 有_frozen标志。通过不可变列表发布的根会递归 Freeze先冻结左右子树再把当前节点标记为 frozen。冻结后 Node 的 Mutate 不得改写自身而是返回新节点未冻结节点可在 Builder 独占协议中更新自身并重算 Height/Count。ImmutableList.ToBuilder(): Builder 指向已冻结根 第一次修改路径冻结节点不能原改 - 复制出未冻结路径 后续修改命中 Builder 自有未冻结路径允许原地复用 Builder.ToImmutable(): 冻结当前根并包装/缓存不可变结果 再次修改 Builder已冻结路径再次写时复制这不是一般意义的“可变令牌对象传入每个 Node”而是该版本以节点冻结位和 Builder 根所有权实现的写时复制。不要把其他持久化集合的 owner token 机制硬套到 ImmutableList。7.2 Builder 何时有价值连续做大量修改并且不需要保留每一步历史版本时Builder 可避免为每一步都冻结并保留完整的不可变边界// 业务示例Builder 只在当前线程/所有者范围使用。 ImmutableListEntity.Builder builder snapshot.ToBuilder(); foreach (Patch patch in patches) Apply(builder, patch); ImmutableListEntity next builder.ToImmutable();Builder 本身是可变对象不是线程安全集合。不能多个线程同时写也不能一边写一边枚举而期待快照语义。ToImmutable()返回的列表可安全发布之后 Builder 再修改不会改变已发布列表因为冻结边界迫使写时复制。ToImmutable 可能缓存与当前根对应的不可变结果未修改时重复调用可复用结果这是基线优化不应把对象引用相等作为业务正确性条件。Builder 也不会让任意操作 O(1)索引导航和平衡仍受 AVL 高度约束批量算法和按值扫描仍有自身成本。它主要减少连续修改的节点分配和冻结开销收益必须在真实负载测量。八、枚举中序序列、版本和资源生命周期中序遍历恰好输出逻辑序列左子树、当前 key、右子树。枚举器用栈保存尚待返回的祖先时间 O(n)额外路径空间 O(log n)。基线实现为降低分配含有内部栈池/所有权细节使用者只应依赖公开 IEnumerator 契约并及时 Dispose 枚举器。ImmutableList 枚举期间不会发生结构变化因此无需像可变集合那样因另一变量获得新版本而失效// 业务示例enumerator 绑定 old 的节点图。 ImmutableListint old ImmutableList.Create(1, 2, 3); var enumerator old.GetEnumerator(); ImmutableListint next old.Add(4); // enumerator 仍枚举 1,2,3next 是另一个根。Builder 不同。它有版本状态修改 Builder 会让先前枚举器失效或不再可继续依赖应先ToImmutable()再跨线程/跨阶段枚举。反向枚举、区间枚举和接口枚举的具体分配可能不同。性能敏感代码应使用目标包和调用形态测量不能仅由“struct enumerator”推导绝对零分配装箱到接口或 LINQ 链仍可能分配。九、复杂度必须同时写时间与分配操作时间上界/典型量级不可变路径的分配特征this[index]O(log n)无路径复制Add/InsertO(log n)O(log n) 量级新节点含平衡路径RemoveAtO(log n)O(log n) 量级新节点SetItemO(log n)O(log n) 路径节点IndexOf/ContainsO(n)搜索本身无需建立新树Remove(value)/ReplaceO(n)找到后再复制 O(log n) 路径枚举O(n)枚举路径栈调用形态影响分配获取快照变量O(1)只复制根对象引用ToImmutableBuilder需冻结未冻结节点成本取决于 Builder 修改图与缓存状态节点是托管对象并带左右引用、统计和冻结状态实际字节数取决于运行时、架构、T 的形态和对象对齐不能写死“100 万元素约 48 MB”。与连续数组相比节点树通常对象更多、局部性更弱与每次完整复制数组相比多版本修改又能共享大部分未变子树。大结构体 T 会内联进每个 Node路径复制时复制 key引用类型 T 只在 Node 存引用但对象本体另行分配。选择前应同时测吞吐、分配、存活版本、GC 和索引热点而不是只看大 O。十、元素深层可变性与线程发布不可变集合不会克隆元素// 反例列表结构不变但元素对象仍可变。 var player new PlayerState { Score 10 }; ImmutableListPlayerState snapshot ImmutableList.Create(player); player.Score 999; // snapshot[0].Score 现在也是 999。若快照必须表达历史状态元素也应是不可变 record/readonly struct或在进入快照时深拷贝必要数据。只读接口同样不等于深不可变它可能包装仍会变化的对象。完成构造的 ImmutableList 可以安全地作为只读值在线程间共享更新线程产生新根后要通过正确同步发布“当前根”例如Volatile.Write、Interlocked.Exchange、锁或消息传递。不可变性防止节点图被修改但不能让一个普通共享字段的数据竞争自动满足内存可见性协议。// 业务示例原子替换当前快照引用。 ImmutableListState oldSnapshot Volatile.Read(ref _current); ImmutableListState nextSnapshot BuildNext(oldSnapshot); Volatile.Write(ref _current, nextSnapshot);多个写者基于同一旧根更新时最后一次 Write 会覆盖另一更新。若不能丢更新应使用Interlocked.CompareExchange重试循环、单写者模型或锁。不可变集合简化读者不自动合并写者意图。十一、与 List 和 ImmutableArray 的选择需求ListTImmutableArrayTImmutableListT索引热路径O(1)连续存储O(1)连续存储O(log n)节点导航尾部逐项追加摊销 O(1)单次修改通常需复制数组O(log n) 路径复制中间插入/删除O(n) 搬移O(n) 新数组复制O(log n) 路径修改快照必须复制或冻结所有权结构值共享整块数组根共享持久化子树多版本少量修改手工复制成本高每版复制整体典型优势场景批量构建非常合适Builder/创建 API 合适Builder/批量 API 合适读多、索引极热、发布后整体不变时ImmutableArrayT通常有更好的局部性持续中间编辑且要保留多个版本时ImmutableList 更有意义单线程局部构建且不需要历史版本时List 最简单。也可以用 List 构建最后转成 ImmutableArray“不可变”不要求整个构建过程都使用持久化操作。如果需要按值 O(log n) 查找应考虑 ImmutableSortedSet/Dictionary 等按比较键组织的集合而不是期待 ImmutableList 的 AVL 自动提供。若需要随机排名、范围聚合等增强秩操作确认公开 API 是否支持不要依赖私有 Node。十二、Unity 使用边界Unity 是否自带兼容版本的System.Collections.Immutable取决于 Unity 版本、API Compatibility Level、包依赖和目标平台。桌面.NET 8源码细节不能直接等同于 Unity Mono/IL2CPP 的实际包需在目标 Player 验证程序集、AOT 泛型、裁剪和性能。适合的游戏场景包括配置/规则快照、编辑器撤销历史、跨线程发布纯数据世界状态、少量修改的版本树。不适合的默认场景包括每帧大量随机索引的实体热循环、每帧保存无限历史、或元素仍是可变UnityEngine.Object包装的“假快照”。IL2CPP 下大量泛型实例可能影响生成代码与构建节点分配会进入对应 Unity GC 路径。不要引用 CoreCLR 节点字节数或 GC 阈值。Profiler 应在 Release/非 Development 的真实设备 Player 上同时观察 CPU、GC Alloc、存活内存和帧尾延迟。Unity 主线程可以原子接收后台生成的不可变纯数据根再把差异应用到引擎对象后台线程仍不能因为容器不可变就调用非线程安全 Unity API。退出 Play、场景卸载时也应释放持有的历史根否则编辑器服务/静态缓存可能让整个版本图继续可达。十三、失败反例把 ImmutableList 当排序集合期望 Add 自动按值排序并去重。在循环中忘记接收返回值list.Add(x);后 list 仍是旧版本。列表元素是可变 class却把列表当历史深快照。多写者各自读取旧根再普通赋值后写者覆盖先写者更新。每帧保存一个根且永不淘汰结构共享仍无法阻止历史路径累积。索引热点使用 ImmutableList并错误假设 AVL 索引 O(1)。调用 Remove(value) 后宣称 O(log n)忽略按值线性查找。多线程共享 Builder把它误当线程安全集合。ToImmutable 后认为 Builder 再修改会反向改变已发布快照。反射复用/修改私有 Node绕过 frozen 不变量。在 Unity 编辑器测量后把节点内存和性能直接套到 IL2CPP 真机。用百万元素与固定 log₂ 数量编造精确共享率或性能倍数。十四、属性测试与结构共享实验14.1 与 List 的差分测试随机生成 Add、Insert、RemoveAt、SetItem、Remove(value)、AddRange 操作序列同时维护一个普通 List 参考模型。每一步比较 Count、所有索引、正反枚举、IndexOf 结果同时保存随机旧版本之后再次断言旧版本内容未变化。输入覆盖空表、重复值、首尾索引、非法边界和大量相同对象引用。14.2 AVL 内部属性若是在学习项目中自研持久化 AVL可公开测试专用节点检查每个节点 Count/Height 与子树计算一致、平衡差不超过 1、中序结果等于参考序列、Empty 高度/数量为 0。不要让生产测试反射绑定框架私有字段否则包升级只改变字段名就会误报。14.3 共享行为实验公开 API 不承诺具体共享节点数因此不应通过反射断言“精确共享 99.998%”。可验证的行为是旧版本内容不变保留旧根会延长其元素生命周期释放所有历史根后旧版本独有对象最终可回收。弱引用 GC 实验要避免局部变量、枚举器和 JIT 生命周期造成假阳性并把 GC 测试与功能测试分开。若为了研究实现使用调试版源码或自研等价树可给 Node 分配稳定 ID修改一个索引后统计新旧根引用相同的子树验证未修改分支共享、修改路径分离、旋转附近共享变化并确认 Builder ToImmutable 后再次修改不会改变先前冻结根。结果只属于该实验实现/tag。14.4 并发发布实验单写者不断产生带版本号和校验和的不可变快照经 Volatile/Interlocked 发布多个读者验证 Count、版本与校验和自洽。再用两个写者执行 CompareExchange 重试验证所有逻辑更新都保留。对比普通“读—改—写”以稳定屏障控制竞态展示丢更新而不是依赖概率复现。性能实验报告包版本、运行时/Unity 后端、CPU、T 类型与大小、初始规模、修改位置分布、活跃历史数、Builder 与永久 API 路径、预热、分配和 GC。禁止从单次结果推出固定倍数。十五、源码阅读路线与总结固定System.Collections.Immutable8.0.0 后先读 ImmutableList 外壳如何持有 root 与 WrapNode再读 Node.Empty、构造器、Height/Count、索引器随后跟踪 Insert/Add、RemoveAt、ReplaceAt 与 Balance/Rotate最后阅读 Freeze、Mutate、Builder.Root/ToImmutable 和 Enumerator 的栈所有权。每一步都问这个节点是否 frozen哪个子树复用统计何时重算旋转是否仍保护旧根ImmutableList 的 AVL 是按位置维护的隐式秩树。左子树 Count 决定索引AVL 高度保证单点索引与位置修改 O(log n)。不可变 API 对冻结节点执行路径复制未修改子树共享旋转只改写新路径。Builder 利用_frozen边界在独占的未冻结节点上暂时原地修改ToImmutable 时冻结并发布。它最擅长的是多个版本共存并持续做少量中间修改而不是连续数组式索引热点。结构不可变也不等于元素深不可变、Builder 线程安全或多写者更新不丢失。只有同时理解 Count/Height 不变量、路径分配、冻结所有权、元素生命周期与发布协议才能把持久化集合用于真正可靠的快照系统。下一篇ImmutableDictionary 与 ImmutableHashSet持久化哈希树 08-02-不可变-ImmutableList-T-持久化AVL树实现
ImmutableListT持久化 AVL 树实现系列C# 与常用数据结构源码剖析 · 不可变集合篇阅读时间约 80 分钟源码基线System.Collections.Immutable8.0.0对应 dotnet/runtime v8.0.0 / 5535e31a... 的 ImmutableList_1.cs版本边界本文固定上述包版本与仓库 tag。字段布局、Builder 优化和枚举器池化属于实现细节升级时应按新 tag 复核。代码约定所有算法代码均标为结构化节选、教学伪代码或业务示例不冒充逐字源码。一、先纠正定位它是序列树不是排序集合ImmutableListT保持插入顺序允许重复元素并通过整数索引访问。内部 AVL 树不是按IComparerT比较元素来决定左右分支而是用左子树节点数表达序列位置。Add(x)把 x 插在末尾Insert(i,x)把 x 插在逻辑位置 iSetItem(i,x)替换位置 i。所以旧稿中“比较 item小于走左、大于走右、相等不插入”的示例属于 SortedSet 一类结构完全不适用于 ImmutableList。以下序列是合法的// 业务示例保序且允许重复。 ImmutableListint values ImmutableList.Create(30, 10, 30, 20); ImmutableListint next values.Insert(1, 99); // values: 30, 10, 30, 20 // next: 30, 99, 10, 30, 20“不可变”指集合对象的可观察结构不会被其公开修改方法原地改变方法返回新列表旧列表仍表示原序列。它不是把整个对象图深度冻结也不意味着每次修改复制整棵树。持久化数据结构通过共享未改变子树让多个历史版本同时存在。二、Node、空哨兵与四个核心不变量.NET 8基线 Node 的重要状态可结构化为// 结构化节选名称与含义按 8.0.0省略方法和可空细节。 private sealed class Node { internal T _key; internal Node _left; internal Node _right; internal byte _height; internal int _count; internal bool _frozen; internal static readonly Node Empty new Node(); }字段名_key容易让人误以为这是按键搜索树在 ImmutableList 中它就是当前节点保存的元素。Node 使用单例Empty表示空子树而非让每个叶节点的 Left/Right 为 null。空哨兵能统一递归边界但 Empty 的内部访问契约仍应按源码使用不能把它当普通可写节点。对任意非空节点 n必须满足n.Count 1 n.Left.Count n.Right.Count n.Height 1 max(n.Left.Height, n.Right.Height) abs(n.Right.Height - n.Left.Height) 1 逻辑序列 Left 的序列 n.Key Right 的序列空哨兵的 Count 和 Height 为 0并处于冻结状态。根的 Count 就是列表 Count。高度存成 byte 是当前实现选择不是公开 APIAVL 平衡让现实可构造规模的高度保持很小但不要由字段宽度反推公开最大容量。第四个关键不变量是冻结边界对外发布为 ImmutableList 的节点图必须冻结任何后续“修改”都不能原地改变这些节点。Builder 暂时拥有的未冻结节点则可在所有权协议内原地更新。_frozen不是线程锁而是持久化写时复制的所有权标记。三、索引导航左子树 Count 是隐式秩节点的逻辑索引等于左子树 Count。访问索引 i 时i left.Count目标在左子树i left.Count目标就是当前元素i left.Count进入右子树并把 i 减去left.Count 1。// 教学伪代码展示秩导航参数校验和真实辅助方法已省略。 T ItemAt(Node node, int index) { while (!node.IsEmpty) { int leftCount node.Left.Count; if (index leftCount) { node node.Left; } else if (index leftCount) { return node.Key; } else { index - leftCount 1; node node.Right; } } throw new ArgumentOutOfRangeException(nameof(index)); }树高 O(log n)因此索引访问也是 O(log n)不像ListT和ImmutableArrayT的数组索引 O(1)。AVL 不按元素值组织IndexOf(value)无法凭大小关系走单边通常要按指定范围和IEqualityComparerT扫描时间上界 O(n)。Contains 也不因内部是树就自动成为 O(log n)。索引参数边界因操作不同读取、RemoveAt、SetItem 要求0 index CountInsert 允许index Count表示追加。区间重载还需防止 index count 溢出使用公开 API 时依赖其参数检查不自行写容易溢出的判断。四、路径复制持久化修改的通用骨架假设要修改从根到某个索引的路径。下降时只有一个子树包含目标另一个子树可以直接共享。回升时为路径上的每层产生新版本节点并重新计算 Count、Height再按需旋转。旧根仍指向旧路径新根指向新路径共同子树被两个版本同时引用。图中只有根到目标的节点链被新版本替换S1、S2、S3仍是同一批节点对象。旋转可能让新路径的局部形状与图不同但不会改变“旧根保留旧视图未修改子树尽量共享”的持久化边界。“每次严格创建 log₂(n) 个节点”并不准确。AVL 高度只是 O(log n)实际路径长度取决于树形旋转会构造或变异额外路径节点空列表添加只涉及少量节点Builder 还可能复用未冻结节点。可靠结论是普通单点永久修改访问 O(log n) 高度并产生 O(log n) 量级的新节点/路径状态而不是固定数量或固定共享百分比。结构共享也不等于旧版本免费。只要任何历史根仍可达它独有的旧路径与元素就不能回收。保存每一帧快照会让大量版本共同子树长期存活同时累计每次修改产生的新路径。内存预算必须考虑“活跃版本数 × 修改路径”而不只是最新列表 Count。五、Add 与 Insert按位置插入并恢复 AVLAdd(item)等价于在逻辑Count处插入Insert(index,item)通过左子树 Count 导航。概念递归如下// 教学伪代码不体现真实 Mutate/Freeze 优化和所有旋转分支。 Node Insert(Node node, int index, T item) { if (node.IsEmpty) return NewLeaf(item); int leftCount node.Left.Count; Node candidate; if (index leftCount) candidate Copy(node, left: Insert(node.Left, index, item)); else candidate Copy(node, right: Insert(node.Right, index - leftCount - 1, item)); return Balance(candidate); }注意index leftCount插到当前节点位置时新项应位于当前项之前因此进入左侧的相应末端。每次 Copy/Mutate 后必须更新 Count 和 Height。5.1 单旋与双旋定义平衡因子为右高减左高源码辅助函数的符号应按 tag 阅读。若一侧高度比另一侧超过 1需要旋转左左偏重 - 右旋 右右偏重 - 左旋 左右偏重 - 先左旋左孩子再右旋 右左偏重 - 先右旋右孩子再左旋持久化旋转不能原地改动已冻结节点。基线通过 Node 的Mutate类路径节点若未冻结可更新字段并返回自身若冻结则构造带新孩子/新 key 的节点。旋转调用这些受控变更因此对 ImmutableList 返回的新根不会破坏旧版本而 Builder 可以复用自己尚未冻结的节点。AddRange/InsertRange 不是简单保证逐项调用单点 Insert基线含针对输入和树构建的批量路径。复杂度与分配要结合输入类型和版本不应从单点公式机械乘 m。批量创建时优先使用CreateRange、AddRange或 Builder而不是先构造许多中间不可变版本。六、Remove、RemoveAt 与 SetItem6.1 RemoveAt删除一个序列位置删除路径仍由左 Count 导航。目标节点无孩子时返回 Empty只有一个非空孩子时返回该孩子两个孩子时可用右子树最左节点逻辑后继的元素替换当前元素再从右子树删除那个最左节点。回升时更新统计并平衡。// 教学伪代码只表达两个孩子时的序列保持逻辑。 if (index leftCount) { if (node.Right.IsEmpty) return node.Left; if (node.Left.IsEmpty) return node.Right; Node successor Leftmost(node.Right); Node rightWithoutSuccessor RemoveMin(node.Right); return Balance(Copy(node, key: successor.Key, right: rightWithoutSuccessor)); }用后继替换不会改变逻辑序列中其他元素的相对顺序。被删除的元素若不再被任何列表版本、调用者或其他对象引用最终可回收旧版本仍保留它是持久化语义而不是泄漏。6.2 Remove(value) 先寻找相等元素Remove(value, comparer)删除指定比较器命中的第一个元素。由于树不按 value 排序查找阶段可能 O(n)找到索引后的路径删除 O(log n)总体 O(n)。重复元素只删除一个匹配项RemoveAll、RemoveRange有各自语义和批量成本不能只看 AVL 高度宣称所有 Remove 都是 O(log n)。若未找到元素公开结果可复用原列表实例因为逻辑内容不变调用者应依据值语义不把引用是否相同当作跨版本契约除非文档明确保证。6.3 SetItem替换但不改变长度SetItem(index,value)只复制/变异到目标的路径把节点 key 换成 value左右结构及 Count 不变不需要因高度变化进行旋转。它仍为 O(log n)不可变路径通常分配 O(log n) 节点。新值可以与别处元素相等因为 ImmutableList 允许重复。Replace(oldValue,newValue,comparer)需要先按相等性查找 oldValue再调用位置替换所以查找可能 O(n)。区分“按索引已知位置”和“按值搜索”对理解复杂度非常重要。七、Builder受所有权约束的暂时可变树7.1_frozen的真实作用.NET 8Node 有_frozen标志。通过不可变列表发布的根会递归 Freeze先冻结左右子树再把当前节点标记为 frozen。冻结后 Node 的 Mutate 不得改写自身而是返回新节点未冻结节点可在 Builder 独占协议中更新自身并重算 Height/Count。ImmutableList.ToBuilder(): Builder 指向已冻结根 第一次修改路径冻结节点不能原改 - 复制出未冻结路径 后续修改命中 Builder 自有未冻结路径允许原地复用 Builder.ToImmutable(): 冻结当前根并包装/缓存不可变结果 再次修改 Builder已冻结路径再次写时复制这不是一般意义的“可变令牌对象传入每个 Node”而是该版本以节点冻结位和 Builder 根所有权实现的写时复制。不要把其他持久化集合的 owner token 机制硬套到 ImmutableList。7.2 Builder 何时有价值连续做大量修改并且不需要保留每一步历史版本时Builder 可避免为每一步都冻结并保留完整的不可变边界// 业务示例Builder 只在当前线程/所有者范围使用。 ImmutableListEntity.Builder builder snapshot.ToBuilder(); foreach (Patch patch in patches) Apply(builder, patch); ImmutableListEntity next builder.ToImmutable();Builder 本身是可变对象不是线程安全集合。不能多个线程同时写也不能一边写一边枚举而期待快照语义。ToImmutable()返回的列表可安全发布之后 Builder 再修改不会改变已发布列表因为冻结边界迫使写时复制。ToImmutable 可能缓存与当前根对应的不可变结果未修改时重复调用可复用结果这是基线优化不应把对象引用相等作为业务正确性条件。Builder 也不会让任意操作 O(1)索引导航和平衡仍受 AVL 高度约束批量算法和按值扫描仍有自身成本。它主要减少连续修改的节点分配和冻结开销收益必须在真实负载测量。八、枚举中序序列、版本和资源生命周期中序遍历恰好输出逻辑序列左子树、当前 key、右子树。枚举器用栈保存尚待返回的祖先时间 O(n)额外路径空间 O(log n)。基线实现为降低分配含有内部栈池/所有权细节使用者只应依赖公开 IEnumerator 契约并及时 Dispose 枚举器。ImmutableList 枚举期间不会发生结构变化因此无需像可变集合那样因另一变量获得新版本而失效// 业务示例enumerator 绑定 old 的节点图。 ImmutableListint old ImmutableList.Create(1, 2, 3); var enumerator old.GetEnumerator(); ImmutableListint next old.Add(4); // enumerator 仍枚举 1,2,3next 是另一个根。Builder 不同。它有版本状态修改 Builder 会让先前枚举器失效或不再可继续依赖应先ToImmutable()再跨线程/跨阶段枚举。反向枚举、区间枚举和接口枚举的具体分配可能不同。性能敏感代码应使用目标包和调用形态测量不能仅由“struct enumerator”推导绝对零分配装箱到接口或 LINQ 链仍可能分配。九、复杂度必须同时写时间与分配操作时间上界/典型量级不可变路径的分配特征this[index]O(log n)无路径复制Add/InsertO(log n)O(log n) 量级新节点含平衡路径RemoveAtO(log n)O(log n) 量级新节点SetItemO(log n)O(log n) 路径节点IndexOf/ContainsO(n)搜索本身无需建立新树Remove(value)/ReplaceO(n)找到后再复制 O(log n) 路径枚举O(n)枚举路径栈调用形态影响分配获取快照变量O(1)只复制根对象引用ToImmutableBuilder需冻结未冻结节点成本取决于 Builder 修改图与缓存状态节点是托管对象并带左右引用、统计和冻结状态实际字节数取决于运行时、架构、T 的形态和对象对齐不能写死“100 万元素约 48 MB”。与连续数组相比节点树通常对象更多、局部性更弱与每次完整复制数组相比多版本修改又能共享大部分未变子树。大结构体 T 会内联进每个 Node路径复制时复制 key引用类型 T 只在 Node 存引用但对象本体另行分配。选择前应同时测吞吐、分配、存活版本、GC 和索引热点而不是只看大 O。十、元素深层可变性与线程发布不可变集合不会克隆元素// 反例列表结构不变但元素对象仍可变。 var player new PlayerState { Score 10 }; ImmutableListPlayerState snapshot ImmutableList.Create(player); player.Score 999; // snapshot[0].Score 现在也是 999。若快照必须表达历史状态元素也应是不可变 record/readonly struct或在进入快照时深拷贝必要数据。只读接口同样不等于深不可变它可能包装仍会变化的对象。完成构造的 ImmutableList 可以安全地作为只读值在线程间共享更新线程产生新根后要通过正确同步发布“当前根”例如Volatile.Write、Interlocked.Exchange、锁或消息传递。不可变性防止节点图被修改但不能让一个普通共享字段的数据竞争自动满足内存可见性协议。// 业务示例原子替换当前快照引用。 ImmutableListState oldSnapshot Volatile.Read(ref _current); ImmutableListState nextSnapshot BuildNext(oldSnapshot); Volatile.Write(ref _current, nextSnapshot);多个写者基于同一旧根更新时最后一次 Write 会覆盖另一更新。若不能丢更新应使用Interlocked.CompareExchange重试循环、单写者模型或锁。不可变集合简化读者不自动合并写者意图。十一、与 List 和 ImmutableArray 的选择需求ListTImmutableArrayTImmutableListT索引热路径O(1)连续存储O(1)连续存储O(log n)节点导航尾部逐项追加摊销 O(1)单次修改通常需复制数组O(log n) 路径复制中间插入/删除O(n) 搬移O(n) 新数组复制O(log n) 路径修改快照必须复制或冻结所有权结构值共享整块数组根共享持久化子树多版本少量修改手工复制成本高每版复制整体典型优势场景批量构建非常合适Builder/创建 API 合适Builder/批量 API 合适读多、索引极热、发布后整体不变时ImmutableArrayT通常有更好的局部性持续中间编辑且要保留多个版本时ImmutableList 更有意义单线程局部构建且不需要历史版本时List 最简单。也可以用 List 构建最后转成 ImmutableArray“不可变”不要求整个构建过程都使用持久化操作。如果需要按值 O(log n) 查找应考虑 ImmutableSortedSet/Dictionary 等按比较键组织的集合而不是期待 ImmutableList 的 AVL 自动提供。若需要随机排名、范围聚合等增强秩操作确认公开 API 是否支持不要依赖私有 Node。十二、Unity 使用边界Unity 是否自带兼容版本的System.Collections.Immutable取决于 Unity 版本、API Compatibility Level、包依赖和目标平台。桌面.NET 8源码细节不能直接等同于 Unity Mono/IL2CPP 的实际包需在目标 Player 验证程序集、AOT 泛型、裁剪和性能。适合的游戏场景包括配置/规则快照、编辑器撤销历史、跨线程发布纯数据世界状态、少量修改的版本树。不适合的默认场景包括每帧大量随机索引的实体热循环、每帧保存无限历史、或元素仍是可变UnityEngine.Object包装的“假快照”。IL2CPP 下大量泛型实例可能影响生成代码与构建节点分配会进入对应 Unity GC 路径。不要引用 CoreCLR 节点字节数或 GC 阈值。Profiler 应在 Release/非 Development 的真实设备 Player 上同时观察 CPU、GC Alloc、存活内存和帧尾延迟。Unity 主线程可以原子接收后台生成的不可变纯数据根再把差异应用到引擎对象后台线程仍不能因为容器不可变就调用非线程安全 Unity API。退出 Play、场景卸载时也应释放持有的历史根否则编辑器服务/静态缓存可能让整个版本图继续可达。十三、失败反例把 ImmutableList 当排序集合期望 Add 自动按值排序并去重。在循环中忘记接收返回值list.Add(x);后 list 仍是旧版本。列表元素是可变 class却把列表当历史深快照。多写者各自读取旧根再普通赋值后写者覆盖先写者更新。每帧保存一个根且永不淘汰结构共享仍无法阻止历史路径累积。索引热点使用 ImmutableList并错误假设 AVL 索引 O(1)。调用 Remove(value) 后宣称 O(log n)忽略按值线性查找。多线程共享 Builder把它误当线程安全集合。ToImmutable 后认为 Builder 再修改会反向改变已发布快照。反射复用/修改私有 Node绕过 frozen 不变量。在 Unity 编辑器测量后把节点内存和性能直接套到 IL2CPP 真机。用百万元素与固定 log₂ 数量编造精确共享率或性能倍数。十四、属性测试与结构共享实验14.1 与 List 的差分测试随机生成 Add、Insert、RemoveAt、SetItem、Remove(value)、AddRange 操作序列同时维护一个普通 List 参考模型。每一步比较 Count、所有索引、正反枚举、IndexOf 结果同时保存随机旧版本之后再次断言旧版本内容未变化。输入覆盖空表、重复值、首尾索引、非法边界和大量相同对象引用。14.2 AVL 内部属性若是在学习项目中自研持久化 AVL可公开测试专用节点检查每个节点 Count/Height 与子树计算一致、平衡差不超过 1、中序结果等于参考序列、Empty 高度/数量为 0。不要让生产测试反射绑定框架私有字段否则包升级只改变字段名就会误报。14.3 共享行为实验公开 API 不承诺具体共享节点数因此不应通过反射断言“精确共享 99.998%”。可验证的行为是旧版本内容不变保留旧根会延长其元素生命周期释放所有历史根后旧版本独有对象最终可回收。弱引用 GC 实验要避免局部变量、枚举器和 JIT 生命周期造成假阳性并把 GC 测试与功能测试分开。若为了研究实现使用调试版源码或自研等价树可给 Node 分配稳定 ID修改一个索引后统计新旧根引用相同的子树验证未修改分支共享、修改路径分离、旋转附近共享变化并确认 Builder ToImmutable 后再次修改不会改变先前冻结根。结果只属于该实验实现/tag。14.4 并发发布实验单写者不断产生带版本号和校验和的不可变快照经 Volatile/Interlocked 发布多个读者验证 Count、版本与校验和自洽。再用两个写者执行 CompareExchange 重试验证所有逻辑更新都保留。对比普通“读—改—写”以稳定屏障控制竞态展示丢更新而不是依赖概率复现。性能实验报告包版本、运行时/Unity 后端、CPU、T 类型与大小、初始规模、修改位置分布、活跃历史数、Builder 与永久 API 路径、预热、分配和 GC。禁止从单次结果推出固定倍数。十五、源码阅读路线与总结固定System.Collections.Immutable8.0.0 后先读 ImmutableList 外壳如何持有 root 与 WrapNode再读 Node.Empty、构造器、Height/Count、索引器随后跟踪 Insert/Add、RemoveAt、ReplaceAt 与 Balance/Rotate最后阅读 Freeze、Mutate、Builder.Root/ToImmutable 和 Enumerator 的栈所有权。每一步都问这个节点是否 frozen哪个子树复用统计何时重算旋转是否仍保护旧根ImmutableList 的 AVL 是按位置维护的隐式秩树。左子树 Count 决定索引AVL 高度保证单点索引与位置修改 O(log n)。不可变 API 对冻结节点执行路径复制未修改子树共享旋转只改写新路径。Builder 利用_frozen边界在独占的未冻结节点上暂时原地修改ToImmutable 时冻结并发布。它最擅长的是多个版本共存并持续做少量中间修改而不是连续数组式索引热点。结构不可变也不等于元素深不可变、Builder 线程安全或多写者更新不丢失。只有同时理解 Count/Height 不变量、路径分配、冻结所有权、元素生命周期与发布协议才能把持久化集合用于真正可靠的快照系统。下一篇ImmutableDictionary 与 ImmutableHashSet持久化哈希树