03-05-线性-Array-List-LinkedList与Span-所有权与成本模型选型

Array、List、LinkedList 与 Span从所有权到成本模型的选型指南系列C# 与常用数据结构源码剖析 · 数据结构-线性篇阅读时间约 85 分钟版本口径公共语义以 C# 12、.NET 8为参考Unity 部分以 Unity 2022.3 LTS 为讨论基线。私有布局、增长策略与代码生成需按目标运行时复核。选型原则先确定所有权、长度、顺序与生命周期再比较复杂度、分配和缓存不使用脱离元素类型与硬件的固定倍率。一、第一问不是“谁最快”而是“谁拥有存储”Array、List、LinkedList 是容器Span 是视图。把四者放在一张“存 10 万个 int 占多少内存”表里会重复计算或隐藏底层 owner。类型拥有/管理什么长度能否变化底层位置T[]一个固定长度托管数组对象否连续元素区ListTList 对象管理一个可替换的T[]Count 可变Capacity 可变有效元素在后备数组[0,Count)LinkedListT容器管理一组独立 Node 对象可变节点通常分散在托管堆SpanT不拥有借用一段连续 T视图长度固定可切片成新视图数组、stackalloc、native memory 等int[] owner new int[128]; Spanint view owner.AsSpan(16, 32);这里不是“数组 128 项 Span 32 项”两份数据Span 只是指向 owner 中一段。owner 被修改时 view 看到变化。Span 离开作用域不释放数组数组可达性和 GC 决定其生命周期。选择 Span 的问题是“如何借用现有连续存储并携带长度”不是“用什么容器长期保存集合”。二、语义矩阵先看能否表达需求维度ArrayListTLinkedListTSpanT固定逻辑长度是否否当前视图是连续元素存储是是后备数组否节点分散要求底层连续O(1) 随机索引是是否是尾部增长不能原地增长摊销 O(1)已有尾节点时 O(1)不拥有不能增长中间插入保持顺序新数组并复制 O(n)移动尾部 O(n)已知节点时 O(1) 链接不能改变 owner 长度按值查找无序时 O(n)O(n)O(n)O(n)切片是否复制常规 range 产生新数组GetRange复制无连续切片Slice/O(1) 视图可跨 await/普通对象字段是是是否考虑MemoryT结构修改版本检测无集合版本枚举器检查 version枚举器检查 version不追踪 owner 版本单个元素分配节点否否是否但 owner 可能分配复杂度只在前提成立时有意义。LinkedList 插入 O(1) 的前提是调用方已经持有属于该链表的LinkedListNodeT如果先Find(value)总成本 O(n)。List 尾部 Add 的摊销 O(1) 隐藏了扩容时 O(n) 复制和新数组分配。Span 索引 O(1) 不代表创建它的 native/池 owner 免费。三、Array固定长度、连续存储和协变陷阱3.1 固定长度不是不可变数组长度在创建后固定但元素可写var values new int[4]; values[0] 10; // 无法把 values 原地增长到 8只能创建并复制到新数组。固定长度适合协议帧、构建完成后的只读数据、矩阵/查找表和 API 明确返回快照。若调用方需要不可修改契约暴露ReadOnlySpanT、ReadOnlyMemoryT或只读接口但只读视图不使拥有数组深度不可变owner 仍能写。3.2 连续只限元素槽int[]内联连续 int。Enemy[]若 Enemy 是 class连续的是引用槽Enemy 对象仍分散。缓存比较必须固定 T拿int[]与LinkedListLargeClass比较没有解释力。数组本身是托管对象有对象头/长度/对齐实际大小依运行时与架构。大数组的 GC 策略也依后端不能套固定字节。3.3 数组协变C# 引用类型数组具有历史协变string[] names new string[1]; object[] objects names; // 编译允许 objects[0] new object(); // 运行时抛 ArrayTypeMismatchException运行时每次潜在不安全存储要保护数组实际元素类型。泛型Liststring不能赋给Listobject因此类型错误更早。公共 API 接受object[]并写入时要考虑调用方实际传入派生数组。值类型数组不参与这种引用协变。SpanT也不提供数组式协变因为可写别名会破坏类型安全ReadOnlySpanT的转换规则应按语言/API查看不能由数组经验推断。3.4 快照与切片数组赋值只复制引用不是快照Clone/ToArray是浅元素复制。元素为 class 时对象仍共享。数组 rangearray[a..b]创建新数组而array.AsSpan(a,count)创建视图。相同[..]语法在目标类型上有不同成本。四、List动态数组的 Count、Capacity 与版本契约4.1 两个长度Count是有效元素数Capacity是后备数组长度。Add 在Count Capacity时写尾槽满时分配更大数组、复制 Count 个元素并替换 owner。增长倍率和初始容量是版本细节。var items new ListEntity(expectedCount);预估容量能把扩容移出热路径但过估提高常驻数组和峰值。Clear通常把 Count 归零并清必要引用不自动把 Capacity 归零。TrimExcess以分配复制换内存若随后增长会震荡。4.2 中间增删Insert/RemoveAt 为保持顺序移动尾段。成本可近似为移动元素数乘元素槽宽度再加引用写屏障/清槽等。大 struct 的每次移动字节多class 元素移动引用槽但对象本体不移动。大量过滤可用RemoveAll或稳定压缩将多次 RemoveAt 变成一次线性写回。若顺序不重要swap-back O(1) 删除但会改变索引、枚举顺序和确定性。4.3 枚举 versionList 结构修改推进 version已有 Enumerator 在 MoveNext 时发现不一致并抛异常。它是 fail-fast不是线程同步。for 循环没有同样的 version 快照边遍历边 Add/Remove 可能悄悄改变访问集合。把 foreach 改 for 不是纯性能等价变换要先定义修改语义。4.4 内部视图失效桌面.NET的CollectionsMarshal.AsSpan(list)可借用有效后备区但潜在扩容/结构修改会使视图失效且绕过 List API 写元素不会推进 version。Unity 目标未必提供该 API。普通业务不应反射后备数组。List 本身非线程安全多个只读线程只有在没有任何写者且元素状态也安全时才成立。五、LinkedListO(1) 修改购买了什么5.1 已知节点与查找必须拆开LinkedListNodeEntry? node list.Find(target); // O(n) if (node is not null) list.Remove(node); // O(1)总操作仍 O(n)。LRU 常用DictionaryTKey,LinkedListNodeEntry保存节点索引使查找期望 O(1)再 O(1) 移到链首/删除。这时维护两套结构的一致性是代价每次添加、删除、淘汰必须同步更新。传给 Remove/AddBefore 的 node 必须属于预期列表或处于允许的 detached 状态同一节点不能同时属于两个链。5.2 节点成本每个元素通常有 Node 对象含 value、prev、next、list 等引用/状态。实际字节数依 T、对象头、对齐和 runtime不能固定写 48B。节点增加分配数和 GC 图边遍历依赖下一节点引用局部性通常弱于连续数组。但不能说每次遍历都 cache miss 或固定慢几十倍。allocator 可能让近期节点相邻方法体和 T 也会主导。用硬件计数器和目标数据测。5.3 适用不变量LinkedList 有价值的条件通常同时成立已持有节点引用或有外部索引频繁在任意已知节点附近插入/删除/移动不需要按整数索引随机访问节点身份本身是协议的一部分分配/局部性成本可接受。撤销历史若只在尾部 push/popList/Stack 可能更简单消息队列应考虑 Queue大量顺序数据编辑可能用 gap buffer、rope 或批量数组。不要因“中间删除 O(1)”单独选链表。5.4 快照和枚举复制 LinkedList 需要枚举并创建新节点 O(n)普通变量赋值仍共享同一链表对象。枚举器有版本检测。Node 引用让调用方可长期保留元素/整条 list 关系缓存节点时要在删除后同步释放引用。六、Spanref safety、切片与借用所有权6.1 ref struct 生命周期Span/ReadOnlySpan 是 ref struct编译器限制装箱、普通 class 字段、闭包捕获以及跨不允许的 await/yield。限制用于防止视图活过 stackalloc 或托管内部 byref。static int Sum(ReadOnlySpanint values) { int sum 0; foreach (int value in values) sum checked(sum value); return sum; }Span 不保证底层只读、不移动或永远存活它在允许作用域内保持合法引用语义。来自 native memory 的 Span 还依赖外部 owner 不提前 Dispose。6.2 切片是视图Slice/范围通常只是调整起点和长度 O(1)不复制元素。子 Span 与父 Span 别名同一存储写入可互相观察。需要独立快照应ToArray并承担 O(n) 分配复制。6.3 stackalloc、数组和 native数组 Span数组是 ownerGC/引用生命周期由运行时维护stackalloc Span存储随方法栈帧结束失效长度必须有上限native Span调用方证明地址、长度、对齐与 owner 生命周期池数组 Span归还池后视图立即不再可用。Span 索引仍检查边界JIT/AOT 可能消除可证明冗余检查但不是规范保证。“零分配”只指创建视图本身不创建元素副本周边 parse、delegate、owner 仍可能分配。6.4 跨 async 使用 MemorySpan 不能作为普通 async 状态机字段跨 await。MemoryT/ReadOnlyMemoryT可保存但仍是视图/包装不总是 ownerstatic async Task ConsumeAsync(ReadOnlyMemorybyte data) { await WaitAsync(); Parse(data.Span); }如果 data 包装 ArrayPool 数组调用完成前不能归还。Memory 解决语言生命周期表达不自动解决资源所有权。需要独立稳定数据时复制到自有数组。七、复杂度表必须带隐藏前提操作ArrayListLinkedListSpanx[i]O(1)范围检查O(1)按 Count 检查O(n)从邻近端走O(1)范围检查尾部添加新数组 O(n)摊销 O(1)扩容 O(n)O(1)Node 分配不支持结构增长已知整数位置插入新数组 O(n)O(n) 移动先导航 O(n)不支持已知 Node 旁插入不适用不适用O(1)Node 分配不适用按值删除首项新数组/自定义 O(n)查找移动 O(n)Find O(n)unlink只可逻辑过滤/复制已知 Node 删除不适用不适用O(1)不适用遍历O(n) 连续槽O(n) 连续有效槽O(n) 指针追踪O(n) 取决于底层快照O(n) 浅复制O(n) ToArray/新 ListO(n) 新节点ToArray O(n)切片不是快照O(n) 还应乘以元素复制、比较/谓词与缓存成本。引用类型复制槽值类型复制值Contains 的 Equals 可能比导航贵。并发锁、GC、扩容峰值和所有权错误不在大 O 中。八、内存与 GC 成本模型不要写死对象字节数使用组成式Array ≈ array header capacity * sizeof(slot) alignment List ≈ List object backing array(capacity) LinkedList ≈ list object count * (node header value links alignment) Span ≈ 一个短生命周期 view底层 owner 成本另计T 为 class 时 slot 是引用元素对象成本另算T 为 struct 时值内联若含引用字段GC 仍需扫描对应引用。大 struct 改善对象数但可能增加复制和缓存带宽。List 扩容产生新数组旧数组等 GCLinkedList 每节点分配且删除节点随后回收Array 一次分配但换大小需新数组Span 不拥有数据不能从“Span 0B”推导业务总内存 0B。缓存局部性也不是二元标签。连续遍历适合硬件预取随机索引会破坏。LinkedList 指针依赖限制预取但节点分配位置有分布。元素为分散 class 时数组只让引用槽连续访问对象字段仍跳转。九、快照、只读与线程安全IReadOnlyListT只限制通过接口修改不保证底层不变ReadOnlySpan 也是只读视图而非不可变 owner。变量复制 Array/List/LinkedList 只复制引用。真正快照要复制元素槽并对可变元素决定是否深拷贝。四者都不自动提供并发写安全。Span 对同一存储的多个别名也可能数据竞争。发布后完全不变的数组适合多线程只读List 若无写也可读但不能同时扩容LinkedList 写会改变多个链接Memory 跨线程仍需 owner 同步。需要 lock-free/并发结构时根据队列、map、snapshot 语义选专用类型不是在这些线性结构外随手加volatile。十、Unity、Jobs 与 NativeContainer 边界Unity 2022.3 的托管 Array/List/LinkedList 在 Mono/IL2CPP 类库与 GC 上运行本文.NET 8私有布局和 API 不可直接套用。SpanT可用性还受 Unity 编译器、API Compatibility Level 与目标平台影响。Burst Job 通常不能使用托管 List/LinkedList/class 对象。使用NativeArrayT、NativeListT等 NativeContainer并遵守 Allocator.Temp/TempJob/Persistent、Dispose、SafetyHandle 和 JobHandle 依赖。NativeList 扩容也会使地址/别名失效。托管 List - 复制/烘焙 - NativeArray - schedule Job - Complete/依赖 - Dispose端到端成本包含复制、schedule、同步不只比较循环内核。若数据长期就在 Native/ECS 域避免每帧来回转换若只是少量主线程数据普通 List 可能更简单。UnityEngine.Object[]/List 保存托管包装引用原生对象销毁后有 Unity 特殊 null 语义。数组/List 清除索引不等于立即卸载资产应配合 Addressables/资源 owner。Unity 主线程热路径关注尾帧与 GC Alloc服务端关注吞吐、每请求分配和并发。相同容器可以因预算不同得到不同选择。十一、场景决策树是否需要拥有数据 ├─ 否只在同步调用链借用连续区域 │ └─ Span/ReadOnlySpan │ └─ 要跨 await改用 Memory/ReadOnlyMemory并明确 owner └─ 是 ├─ 长度创建后固定 │ ├─ 是Array发布只读时考虑 ReadOnlyMemory/不可变契约 │ └─ 否 │ ├─ 需要随机索引/顺序遍历List │ └─ 频繁操作任意已知节点 │ ├─ 是且节点身份/分配可接受LinkedList │ └─ 否先用 List/Queue/Deque/专用结构再问五个修正问题顺序可否改变若可List swap-back 可能免中间搬移。是否已有节点索引没有就不能领取 LinkedList O(1) 查找收益。是否需要稳定快照切片和只读接口都不是快照。owner 是否跨 async/线程/Jobref safety 与资源生命周期必须匹配。元素是大 struct、class 引用还是含引用 struct复制/GC 模型不同。十二、典型场景12.1 LRUDictionaryTKey,LinkedListNodeEntry LinkedList 能 O(1) 期望查找与节点移动。需要原子维护两结构、容量上限、更新值/顺序、淘汰和并发锁。若容量很小或访问少简单 List 可能更易维护测量再选。12.2 网络解析拥有接收 buffer 的数组/池同步解析用 ReadOnlySpan 切片异步排队要转移 Memory owner 或复制。不能把指向即将归还池的 Span/Memory 放入队列。12.3 帧内实体列表主线程动态实体通常 List 预估容量批量稳定删除用压缩顺序无关用 swap-back。数据导向 Job 使用 NativeArray/NativeList。LinkedList 只有在系统确实持有节点并频繁移动时才考虑。12.4 发布配置快照构建阶段 List完成后ToArray发布读者用 ReadOnlyMemory/Span 临时读取。数组元素若为可变 class仍需不可变 DTO 或深拷贝策略。十三、常见反例把 Span 当拥有数据的第五种容器并把 owner 内存漏算。认为数组固定长度等于元素不可变。用object[]接收string[]后写入任意 object触发协变异常。把 List 尾部 Add 写成“每次 O(1)”忽略扩容尖峰。Clear 后断言 List 已释放后备数组。枚举 List 时改用 for意外取消 version 失败语义。先 LinkedList.Find 再 Remove却只宣称删除 O(1)。用 LinkedList 做随机索引/顺序扫描热点只看理论插入。缓存已删除 LinkedListNode延长对象生命周期或误复用。把 Span 切片当独立快照。让 Span 跨 await或归还池后继续使用 Memory。持有 List/NativeList 内部引用后让容器扩容。认为 ReadOnly 接口/视图让底层线程安全。把 Unity NativeContainer 的 Dispose 交给 GC。引用固定节点字节、缓存 miss、性能倍率作为跨平台定律。十四、可复现实验14.1 操作分布而非单点数字参数化 n、Tint、大 struct、class、初始 Capacity、插入/删除位置分布和读写比。分别测构建、稳态、扩容尖峰、释放后存活返回 checksum验证最终序列。14.2 LinkedList 前提实验分开测Remove(knownNode)与FindRemoveLRU 同时包含 Dictionary 查找与两结构更新。随机/顺序访问分别记录 CPU、分配与硬件 cache/branch counter平台支持时不从一个 n 推导固定倍率。14.3 快照/切片实验对数组 range、AsSpan Slice、ToArray、ReadOnlyMemory 分别修改原 owner验证别名/复制行为元素换成可变 class 再验证浅复制。跨 async 对池 owner 做正确/提前归还两种状态机测试错误路径应由 owner 防护而非执行未定义使用。14.4 GC 与容量阶跃负载让 List 达到峰值后 Clear比较保留容量与 Trim 后再增长记录分配、存活、GC 和峰值不只看 Count。LinkedList 构建/清空后用堆快照确认节点根路径消失避免局部 Enumerator/Node 仍持有。14.5 Unity Player同一语义分别在 Editor Mono、目标 IL2CPP Release、NativeArray/Burst适用测试。包含 managed-native 复制、schedule/Complete、Dispose记录 GC Alloc、主线程/Job 时间、帧分位数与内存。保存完整 Unity/Burst/Collections 版本和设备。BenchmarkDotNet 实验记录.NETSDK/runtime、Tier/PGO、CPU/架构、输入、预热和原始报告。不要把 Debug、第一次 JIT 或数据创建放进被测操作除非调查的正是启动。十五、总结选的是所有权和不变量不是类型排名Array 拥有固定长度连续存储适合构建完成的数据与明确快照但元素可变且引用数组协变会推迟类型错误。List 用 Capacity 换动态增长随机访问和遍历友好中间增删、扩容、version 与内部引用失效必须计入。LinkedList 用每元素节点、较弱局部性和 GC 图换取已有节点附近 O(1) 链接修改若先查找总体仍 O(n)。Span 不拥有数据它以 ref-safety 提供同步短期连续借用与 O(1) 切片跨 async 用 Memory 仍要管理 owner。可靠选择先写清长度、顺序、节点身份、快照、跨 async/Job 与元素布局再用带前提的复杂度和目标环境实验比较。没有一种结构覆盖所有场景也没有固定倍率能代替这些问题。继续旅程进入 04 篇章哈希与映射 → Hash 原理