03-02-线性-List-T-动态数组布局-扩容与操作成本

List<T>：动态数组布局、扩容与操作成本

系列：C#与常用数据结构源码剖析 · 数据结构-线性篇
阅读时间：约 45 分钟
源码位置：dotnet/runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs
版本基线：私有字段与关键路径以.NET 8.0.0tag 为准；增长、收缩与 JIT 优化不是跨版本契约

一、引言

List<T>是 .NET 中最常用的可变长序列之一。它的主干是一个T[]数组，加上_size和_version两个整数，承载了从 Web API 反序列化到 Unity 每帧循环的大量场景。

理解 List<T> 的全部行为——扩容策略的数学依据、_version版本检测的设计困境、struct Enumerator 的低分配路径与装箱边界、JIT 对属性访问的内联条件——是掌握 C# 数据结构体系的第一个里程碑。

二、核心字段：_items、_size、_version

2.1 源码全景

// dotnet/runtime: src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs public class List<T> : IList<T>, IList, IReadOnlyList<T> { internal T[] _items; // 内部数组 internal int _size; // 实际元素数量（≤ _items.Length） internal int _version; // 修改计数器 private const int DefaultCapacity = 4; internal static readonly T[] s_emptyArray = Array.Empty<T>(); }

三个字段各有深意：

_itemsvs_size的分离：_items.Length是容量（Capacity）——底层数组能容纳的最大元素数。_size是实际数量——真正有效的元素数。两者分离允许你在知道最终大小时预分配 Capacity，一次性搞定所有扩容。如果你不预分配，List 会从 0 开始自动扩容——这带来均摊 O(1) 的效率，但每一次扩容都会留下一块"旧数组"作为 GC 垃圾。

_version不是线程安全机制：它是枚举修改检测的一部分。它不能防止多线程同时改写元素、计数、版本与数组引用。应用锁保护完整业务不变式，或按 FIFO、LIFO、无序复用、背压等真实语义选并发集合；ConcurrentBag<T>不是任意 List 的通用替代。

2.2 空 List 的内存状态

var list = new List<int>(); // _items = s_emptyArray (单例空数组), _size = 0

新 List 的_items不是null，而是指向共享零长度数组。这避免为每个空 List 新建数组，但 List 对象仍要分配。具体字节数取决于架构、对象头、对齐和运行时，不应写成固定值。

三、扩容策略：4 → 8 → 16 → ... 的数学

3.1 扩容触发的完整路径

public void Add(T item) { _version++; T[] array = _items; int size = _size; // 关键：用 uint 转换来一次比较同时检查 size >= 0 && size < array.Length if ((uint)size < (uint)array.Length) { _size = size + 1; array[size] = item; // 快速路径：直接写入 } else { AddWithResize(item); // 慢速路径：扩容后写入 } }

注意(uint)size < (uint)array.Length这个技巧——它将两个 int 转为 uint 比较，一次操作同时处理了"size 不能为负"和"size 必须小于容量"两个条件。如果size是负数，转为 uint 后会变成一个巨大的正数（如 -1 → 0xFFFFFFFF），必然大于array.Length，从而触发扩容路径。

AddWithResize 的内部：

private void AddWithResize(T item) { int size = _size; Grow(size + 1); // 确保容量至少为 size+1 _size = size + 1; _items[size] = item; } private void Grow(int capacity) { int newCapacity = _items.Length == 0 ? DefaultCapacity // 4 : _items.Length * 2; // 翻倍 if ((uint)newCapacity > Array.MaxLength) newCapacity = Array.MaxLength; if (newCapacity < capacity) newCapacity = capacity; Capacity = newCapacity; // 触发重新分配 + Array.Copy }

3.2 翻倍策略的均摊分析

为什么翻倍（×2）而不是加固定大小（+100）？考虑连续 Add N 个元素：

• 翻倍策略（×2）：扩容发生 log₂(N/4) 次，总复制元素数 ≈ 2N。均摊每元素 O(1)。
• 固定增量（+K）：扩容发生 N/K 次，总复制元素数 ≈ N²/(2K)。均摊每元素 O(N)。

翻倍策略背后的原理是"几何级数击败算术级数"。扩容次数以对数增长，而每次扩容的成本以指数增长——两者的乘积保持在线性范围内。

3.3 Capacity 属性与构造函数

// 最常用：完全信任自动扩容 var list = new List<int>(); // 预知大小：一次性分配，零扩容、零 GC 垃圾 var list = new List<int>(10000); // 从集合构造：先分配容量，再批量复制 var list = new List<int>(existingCollection); // 内部先设 capacity = collection.Count

Capacity setter 的内部：

public int Capacity { get => _items.Length; set { if (value < _size) throw new ArgumentOutOfRangeException(); if (value != _items.Length) { if (value > 0) { T[] newItems = new T[value]; if (_size > 0) Array.Copy(_items, newItems, _size); _items = newItems; } else { _items = s_emptyArray; } } } }

显式改变 Capacity 可创建新数组并复制有效前缀，旧数组在无其他引用后才可回收。设为 0 时 List 可重新指向共享空数组，但先前的非空数组仍是待 GC 处理的对象，不能说成“无 GC 垃圾”。

3.4 TrimExcess：收缩的艺术

public void TrimExcess() { int threshold = (int)(((double)_items.Length) * 0.9); if (_size < threshold) { Capacity = _size; // 只在实际使用率 < 90% 时收缩 } }

90% 阈值的设计智慧：如果刚收缩到_size，紧接着又 Add 一个元素，就会立即触发扩容——抖动（thrashing）。90% 阈值确保只有显著浪费（至少 10% 空间未使用）才收缩。

四、关键操作：逐行源码分析

4.1 Add vs AddRange：单兵 vs 军团

public void AddRange(IEnumerable<T> collection) { if (collection is ICollection<T> c) { int count = c.Count; if (count > 0) { if (_items.Length - _size < count) Grow(_size + count); c.CopyTo(_items, _size); _size += count; _version++; } } else { // 未知大小的集合：逐个 Add foreach (T item in collection) Add(item); } }

AddRange的优化点：如果传入的集合是ICollection<T>（可以获取 Count），它一次性扩容到位，然后CopyTo批量复制——没有多次扩容的中间垃圾数组。如果是IEnumerable<T>（不知道大小），只能逐个 Add，每次都可能扩容。

4.2 Insert：O(n) 的真正代价

public void Insert(int index, T item) { if ((uint)index > (uint)_size) throw new ArgumentOutOfRangeException(); if (_size == _items.Length) Grow(_size + 1); if (index < _size) { Array.Copy(_items, index, _items, index + 1, _size - index); } _items[index] = item; _size++; _version++; }

Array.Copy(_items, index, _items, index + 1, _size - index)这行是性能核心：将[index, _size)范围的元素整体后移一位。对于值类型，这是memmove（块内存移动）；对于引用类型，还要更新 GC 卡表。

头插需要移动当前全部有效元素，如果同时触发扩容还要复制到新数组。具体时间取决于T的宽度、是否含引用、规模、CPU 和运行时，未附原始报告时不写死毫秒数。

4.3 RemoveAll：双指针的就地过滤

public int RemoveAll(Predicate<T> match) { int freeIndex = 0; // 写指针 while (freeIndex < _size && !match(_items[freeIndex])) freeIndex++; if (freeIndex >= _size) return 0; int current = freeIndex + 1; // 读指针 while (current < _size) { while (current < _size && match(_items[current])) current++; if (current < _size) _items[freeIndex++] = _items[current++]; } // 清理尾部 if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) { Array.Clear(_items, freeIndex, _size - freeIndex); } int result = _size - freeIndex; _size = freeIndex; _version++; return result; }

两个 while 循环交替工作：第一个 while 找第一个不匹配的元素（确定写指针起点）。第二个 while 的外层是读指针遍历，内层跳过要删除的元素。整个过程中没有分配新数组——就地操作。

4.4 索引器与 JIT 优化

public T this[int index] { get { if ((uint)index >= (uint)_size) throw new ArgumentOutOfRangeException(); return _items[index]; } set { if ((uint)index >= (uint)_size) throw new ArgumentOutOfRangeException(); _items[index] = value; _version++; } }

索引器自带边界检查（(uint)index >= (uint)_size）。但在for (int i = 0; i < list.Count; i++)循环中，如果 JIT 能够通过范围分析证明i始终在[0, _size)范围内，它会在 Tier1 编译中消除这个检查——使得list[i]等价于直接数组访问。

Count 属性的内联：public int Count => _size;是很小的 getter，在当代 CoreCLR 的优化发布构建中通常具备良好的内联条件，内联后可表现为直接字段读取。这不是 C# 或 BCL 契约：Debug/未优化构建、Tier 状态、AOT 后端、泛型实例化与调用上下文都可能改变决定。只有目标环境的生成代码才能证明某一调用点是否真正消除了调用。

五、Enumerator：struct 的低分配路径与装箱边界

5.1 为什么不设计为 class

public struct Enumerator : IEnumerator<T>, IEnumerator { private readonly List<T> _list; private int _index; private readonly int _version; private T? _current; }

Enumerator 是struct——这是 .NET 设计中最精妙的性能决策之一。考虑foreach的展开：

// C# 源码 foreach (var item in list) { ... } // 编译器展开（简化） List<int>.Enumerator e = list.GetEnumerator(); try { while (e.MoveNext()) { int item = e.Current; // 循环体 } } finally { e.Dispose(); }

因为e是 struct，具体List<T>foreach 通常可按值保存枚举器，不需要为它单独分配对象。局部值可位于寄存器或栈，不应概括为 struct 永远“在栈上分配”。是否内联由 JIT 决定。

但 struct 枚举器有一个隐藏陷阱：当它转成IEnumerator<T>/IEnumerator或object时可装箱。是否需要避免必须看调用频率与目标 Mono/IL2CPP 构建的 Profiler 证据，不应声称所有 Unity 项目一律禁止。

5.2 _version 检测与并发陷阱

public bool MoveNext() { List<T> localList = _list; if (_version != localList._version) { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } if ((uint)_index < (uint)localList._size) { _current = localList._items[_index]; _index++; return true; } _index = _list._size + 1; _current = default; return false; }

_version检查在每次 MoveNext 时执行——即使是第 10000 次迭代。在本文的 .NET 8.0.0 基线中，枚举期间执行会改变该List<T>_version的公开修改操作，会使枚举器失效并在后续检查中抛出异常。这与修改引用类型元素所指对象的内部状态不同；_version也不是并发同步或内存安全机制。如果该检查在已测量的热路径上成为瓶颈（极少见），可比较for循环，但仍需由调用方保证不发生未同步的结构修改。

六、多版本演进如何核验

List<T>在 .NET Framework、历代 .NET Core/.NET 中的 Add、批量复制、清尾引用、搜索与容量 API 都可演进，JIT 又会改变内联与范围检查。但不应用没有对应 commit/基准的“提升 5—10%”或“快 20%”构造版本史，也不应把与 List 本体无直接关系的 API 写成它的集成优化。

核验版本差异应：

1. 对比明确发布 tag 的List.cs，记录具体 commit 和方法差异；
2. 分开 BCL 源码变化与 RyuJIT 代码生成变化；
3. 在每个目标 TFM/runtime 编译并运行同一基准，保留机器码与原始报告；
4. 检查 API 引入版本，不把当前 SDK 参考程序集与旧 runtime 混用；
5. CollectionsMarshal.AsSpan之类低级视图要单独审查失效、容量变化与并发边界。

七、复杂度、分配与引用生命周期

Clear()不等于释放支持数组。它将_size置零，对引用或含引用的T清除有效槽，使元素可回收，但容量为下一批复用保留。这对稳定峰值有利，对偶发巨大峰值则可造成长期驻留；应用内存预算决定是保留、收缩还是丢弃整个 List。

RuntimeHelpers.IsReferenceOrContainsReferences<T>()让实现仅在必要时清引用槽。对纯值T，移除后无效尾部字节可保留而不影响 GC；它们已在_size之外，不能通过公开索引器读取。

八、实战建议

1. 预分配 Capacity：在有合理上界/估计时减少扩容，但避免过度预留峰值内存
2. 先测 for 与 foreach：具体 List foreach 本身可无枚举器分配，不应只为版本检查牺牲可读性
3. 尾部 Add 通常是 List 最低成本的单项插入：在已选择List<T>且业务顺序允许尾插时，list.Add(item)为均摊 O(1)，但扩容当次仍是 O(n) 并可产生延迟尖峰。list.Insert(0, item)是 O(n)——每次都要移动所有元素；若需批量构建、队头操作或已知精确长度，还应比较AddRange、队列或数组等更匹配语义的方案
4. RemoveAll 优于循环 RemoveAt：前者是单次 O(n) 就地操作，后者是 O(n²)
5. 审查CollectionsMarshal.AsSpan所有权：视图存活期间不得让 List 改变容量/结构，不跨异步、不并发保存，并确认目标 TFM 提供 API

九、可复现验证与审查清单

9.1 差分正确性测试

用普通数组模型与 List 同时执行随机 Add、Insert、RemoveAt、set、Clear 和 RemoveAll，每步比较 Count 与序列。覆盖 0/1/刚好 Capacity/Capacity+1，以及引用类型、纯值 struct、含引用 struct。

9.2 分配与局部性实验

对比从空自动增长、合理预分配、过度预分配三组，报告扩容次数、分配、峰值与遍历。再对比List<SmallStruct>、List<LargeStruct>与List<Class>，将元素拷贝、对象数和缓存局部性分开解释。

9.3 枚举路径实验

比较具体List<T>foreach、IEnumerable<T>foreach、索引 for 与 Span 视图，用 IL 确认静态调用形状，用分配诊断查装箱，用 disassembly 查内联/边界检查。在 Unity 中分别跑 Mono 和 IL2CPP 真机，不从 CoreCLR 结果推断。

9.4 版本升级与容量峰值回归

升级 SDK、Unity 或脚本后端时，不要只重跑一个固定数量的 Add 微基准。建立阶梯负载：空表开始，依次写到预期容量前一项、恰好容量、容量后一项、典型高分位和业务硬上限；每个阶段记录Count、Capacity、扩容次数、每操作分配、峰值托管堆、操作尾延迟和清空后的驻留量。这样能把“普通追加成本”“跨扩容边界的复制尖峰”和“峰值数组长期保留”分开，而不会被平均值稀释。

三组容量策略应处理完全相同的输入：默认增长、按典型规模预留、按理论最大值预留。除时间与分配外，还要验证最终序列、顺序、重复项、异常位置以及引用对象是否在 Clear/Remove 后可回收。过度预留若降低了扩容次数，却让每个场景实例长期保留巨大数组，应记为内存回归而非单向优化；主动收缩若造成下一轮再次扩容，也应报告抖动周期。

版本对照一次只改变一个轴，并保存 SDK/runtime、源码 commit、构建配置和设备。若新版本结果不同，先区分是List<T>源码、JIT/AOT 代码生成、GC 策略还是测试噪声；只有差异在重复进程和真实场景中稳定出现，且正确性与峰值预算都通过，才能把它写成升级收益。报告还应保留每轮原始数据，而不只保留最优样本；结果方向反复变化时，正确结论是“尚未证明”，不是挑一次符合预期的数据发布。

审查时确认：

• _size <= _items.Length不变式永远成立；
• 未使用尾部不会保留已删引用；
• 不依赖增长倍数、Trim 阈值或枚举顺序作为未来契约；
• 并发访问由容器外的所有权/锁协议保护；
• 可变键/可变元素的业务契约不由 List 自动保护；
• 低级 Span 视图没有跨越结构修改、await 或多线程边界；
• 优化在目标 runtime/backend 上有原始报告和正确性回归。

十、总结

List<T>的不变式很少：_items是支持数组，_size定义有效前缀，_version帮助枚举器检测结构修改。正因为结构简单，它的成本能够被精确解释：尾部添加用几何增长换取均摊 O(1)，中间增删移动后缀，删除后的引用槽要清理，收缩容量需要新数组并可与后续增长抖动。

成熟使用不是一律“预分配、for、AsSpan”，而是从实际数量上界、顺序契约、元素宽度、所有权和目标运行时做选择。预分配可减少扩容也可浪费驻留，struct 枚举器可避免对象也可在接口边界装箱，Span 视图可去掉某些抽象也会暴露失效风险。用不变式证明正确性，再用固定 tag 源码、IL、分配与真机基准选择优化，才是理解这个“简单动态数组”的完整方式。

下一篇：LinkedList<T>：双向链表的实现与选择困境