企业官网建设流程全解析

SortedList<TKey,TValue>：双数组有序映射的源码模型与选型边界

系列：C# 与常用数据结构源码剖析 · 排序集合篇
阅读时间：约 55 分钟
前置知识：二分查找、动态数组、比较器与 SortedDictionary
版本边界：以现代System.Collections.Generic.SortedList<TKey,TValue>的共同形状为主。私有字段、容量增长和便利 API 会随 TFM/tag 变化，使用前应查目标 reference assembly 与固定源码 tag。

一、名字像 List，语义却是按键排序的 Dictionary

SortedList 实现键到值的唯一映射，并按IComparer<TKey>定义的顺序保存键。它不是可以容纳重复键的排序条目 List，也不是哈希表。当 comparer 返回零时，两个键属于同一映射位置，即使它们的Equals返回 false。

它的核心实现是两个平行数组：一个保存按比较器升序排列的 key，另一个在相同索引保存 value。这种布局用连续存储换取了二分查找和紧凑遍历，代价是中间插入/删除需要搬移后缀。

SortedDictionary 则通常使用平衡树存储节点，插入与删除无需搬移大段连续元素，但逐节点对象、左右引用和指针追踪增加内存与缓存成本。选型不是“数组比树快”，而是更新频率、规模、顺序访问、内存与比较器成本的组合。

二、核心字段与不变式

下面是教学模型，不是可替换目标 runtime 的逐字源码：

public class SortedList<TKey, TValue> { private TKey[] _keys; private TValue[] _values; private int _size; private int _version; private IComparer<TKey> _comparer; }

任何公开操作前后都必须维护：

1. _keys.Length == _values.Length，容量在两个数组上一致。
2. 0 <= _size <= Capacity，有效区间恰好是[0, _size)。
3. 对每个有效索引 i，_keys[i]与_values[i]组成一个键值对。
4. 相邻有效键满足Compare(_keys[i], _keys[i+1]) < 0；零比较的重复键不能同时存在。
5. 有效区间外的槽不是公开数据；对含引用类型，删除/清空时应断开无效槽对对象的保活。

这些不变式解释了为什么 key 和 value 必须同步搬移，也解释了为什么不能为了微优化只对 key 数组排序。一旦平行索引错位，查找仍可能命中正确键，却返回另一个键的值，这是比排序错误更难发现的数据损坏。

三、二分查找同时回答“存在吗”和“应插在哪”

按键查找只访问_keys[0.._size)。当命中时返回非负索引，未命中时Array.BinarySearch类 API 会返回插入点的按位取反，调用方使用~result恢复索引。

int index = Array.BinarySearch(_keys, 0, _size, key, _comparer); if (index >= 0) { // comparer 认为等价的键已存在 } else { int insertionIndex = ~index; // [0, insertionIndex) < key < [insertionIndex, _size) }

使用mid = lo + ((hi - lo) >> 1)而不是(lo + hi) / 2可避免两个大正数先相加的溢出形状，但实际 runtime helper 的写法应按 tag 查阅。二分查找的比较次数为 O(log n)，不代表总时间与键无关。字符串文化比较、复合键逐字段比较或有副作用的 comparer 都会放大每次比较成本。

四、Add 与索引器 setter：重复键的语义不同

Add(key,value)发现 comparer 等价键时抛出重复键异常；索引器 setter 在键已存在时更新对应 value，未存在时才插入。不要用 setter 静默吞掉本应暴露的配置 ID 重复；也不要在“最后写入胜出”就是业务规则时用异常做正常分支。

插入的教学步骤是：

1. 拒绝不符合类型/API 契约的空 key。
2. 二分查找；命中时按 Add 或 setter 语义处理。
3. 若未命中，恢复插入位置，并确保两个数组容量足够。
4. 将 key 和 value 数组在插入点之后的有效后缀各后移一位。
5. 在相同索引写入 key/value，最后增加_size并更新版本。

// 教学伪代码：忽略了具体抛错 helper 和增长策略。 void Insert(int index, TKey key, TValue value) { EnsureCapacityForOneMore(); int move = _size - index; if (move > 0) { Array.Copy(_keys, index, _keys, index + 1, move); Array.Copy(_values, index, _values, index + 1, move); } _keys[index] = key; _values[index] = value; _size++; _version++; }

二分查找是 O(log n)，后缀搬移是 O(n)，所以中间插入总复杂度是 O(n)。在末尾插入时无后缀搬移，如果容量足够，该次写入只有查找和常数写入。因此按 comparer 升序批量插入可比随机顺序减少搬移，但仍要支付每次查找和 API 调用。若数据本就来自无序大批量，“先收集后一次排序并验重”的自定义构建管线可能更合适，但要与直接 Add 做可复现对照。

五、删除、Clear 与引用清理

按键删除先二分查找索引，再将其后 key/value 同步左移一位。搬移后，原有最后一个有效槽会留下重复引用，实现应在 TKey/TValue 是引用或含引用时将尾槽置为 default，避免已删对象被后备数组继续保活。

Clear()将 Count 归零，并清理原有效区间中必要的引用，但通常保留 keys/values 数组容量以便复用。它不等于立即归还所有内存。将 Capacity 缩小或调用 TrimExcess 类 API 则要分配新数组和复制有效数据，应放在长期低水位或加载边界，不放在每次删除或每帧路径。

一个曾经容纳数十万配置项的 SortedList，即使 Clear 后逻辑为空，也可能保留大数组。这不是键值对引用泄漏，而是容器容量驻留。要区分“对象因旧引用保活”和“数组自身仍然很大”，分别用 GC root 分析与容量监控证明。

六、按键访问、按索引访问与 API 版本

按键读取需要二分查找，是 O(log n)。但双数组让“已知索引取第 i 个 key/value”的内部操作成为 O(1)。不应因此直接在文中虚构一个GetAt并宣称所有 .NET 版本都有该公开 API。不同 TFM 可能通过Keys[index]、Values[index]、GetKeyAtIndex/GetValueAtIndex或其他形状暴露能力；必须查目标 reference assembly。

如果业务需要按排名索引取值，还要定义更新时索引是否允许变化。在中间插入一个新键会使其后所有元素索引 +1，所以索引是查询时的位置，不是稳定实体 ID。不能将它持久化后在集合变化后继续当键使用。

TryGetValue在一次查找中表达“可能缺失”；ContainsKey后再用索引器会做两次二分查找。但若第一次检查和第二次使用有独立业务语义，可读性可以比微小重复更重要。不应给出脱离键类型、数量和运行时的固定速度倍数。

七、比较器是键空间的唯一性规则

SortedList 不用EqualityComparer<TKey>判断重复，而使用IComparer<TKey>.Compare(x,y)==0。因此 comparer 必须提供稳定、自洽的全序或至少满足集合操作所需的严格弱序性质。若它一会儿认为 a<b，一会儿又认为 b<a，二分查找的前提就被破坏。

下面的 comparer 只按玩家分数降序比较，会把所有同分玩家当成同一键：

// 错误：缺少唯一破平字段 int Compare(PlayerRank x, PlayerRank y) => y.Score.CompareTo(x.Score);

应把稳定唯一 ID 纳入破平，并用安全的CompareTo或显式分支，不直接相减避免溢出：

int Compare(PlayerRank x, PlayerRank y) { int byScore = y.Score.CompareTo(x.Score); return byScore != 0 ? byScore : x.PlayerId.CompareTo(y.PlayerId); }

键进入集合后，参与比较的状态不能原地改变。如果PlayerRank.Score可变且对象作为 key，改分后数组不会自动重排，查找结果就不再可信。排行榜更新应删除旧的不变排名键，再插入新键；若更新频繁，应重新评估数组搬移成本与数据结构选型。

八、枚举、Keys/Values 视图与版本号

枚举必须按 key comparer 顺序从索引 0 走到_size-1，每次用同一索引组成键值对。这是连续数组布局的长处。Keys和Values是对原集合的只读视图，通常不是每次将内容复制成新集合；底层 SortedList 变化后，视图观察的数据也随之变化。

枚举器通常捕获_version，结构修改后继续 MoveNext 会尽早失败。版本号不是锁，也不保证并发修改安全。普通 SortedList 不应在一个线程插入/删除时由另一个线程枚举。需要跨线程只读时，应在同步边界完成构建并安全发布，之后不再变更；或发布不可变快照。

有序枚举不等于存档可以忽略 comparer。如果写出顺序用当前文化比较，在另一文化下重建可能得到不同顺序，甚至出现新的比较等价冲突。持久化应写出 schema 与稳定键字段，重建时明确使用相同业务规则或执行迁移。

九、复杂度、常数与内存账本

大 O 不告诉转折点。小型集合中，连续数组、较少对象和直接遍历可能抵消 O(n) 搬移；大型高频中间更新中，搬移很快成为主导。元素大小也重要：移动大值类型 value 数组比移动引用更多字节，而树节点又要为每条数据支付对象头与引用。

不应写“一百万 int/string 固定占 16 MB vs 44 MB”这类无环境数字。字符串对象的内存是否计入，引用宽度、对齐、数组头、容量余量、节点布局与 runtime 都会改变结果。应用相同键值对、相同数量和相同运行时做堆快照，分开容器自身、键值对象与临时构建分配。

十、实战场景：配置索引和时间切片

配置表在加载后基本不变，又需按 ID 查询和顺序导出，是 SortedList 的候选。但若只需精确 ID 查询，不需有序遍历，Dictionary 的期望 O(1) 查找可能更直接。选 SortedList 必须有“有序”带来的真实功能，不是因为名称看起来更整齐。

时间切片例如按时间戳查找最近快照。二分查找得到精确键或插入点，由插入点可找前驱/后继：未命中时~index是第一个大于查询键的位置，前一个就是小于查询键的最大键。但公开 API 不一定直接暴露插入点，不应用反射取私有 key 数组。如果前驱/范围查询是核心需求，可选用直接暴露 lower-bound 的专用结构或封装自有排序数组。

定期热更配置时，不建议在正被游戏系统遍历的 SortedList 上逐项修改。可在后台或加载阶段构建新实例，完成完整性、重复键和引用校验后，在同步边界一次替换快照。这同时避免了枚举失效、半更新状态与长时间持锁。

十一、并发、序列化与 Unity 边界

SortedList 不保证多线程并发写安全。一个线程正在扩容或搬移两个数组时，另一个线程读取可以观察到未定义的中间状态。锁必须保护完整操作和所有访问，不是只锁 key 数组写入。读多写少的配置更适合构建后安全发布不再修改的实例。

序列化应保存键值数据、schema 和必要的顺序语义，不保存私有数组容量、版本号或 comparer 对象图。反序列化后应在明确 comparer 下重建，并检测新规则下的重复键。JSON object 属性名只是字符串，复合 key 通常更适合序列化为条目数组 DTO，而不是拼接成难以迁移的文本键。

Unity 内置序列化/JsonUtility 的容器支持不能根据桌面System.Text.Json推断。常用做法是将按键排序的条目列表作为资产/存档模型，在加载边界验证并建立运行时 SortedList。是否选 SortedList 作运行时索引取决于更新/查询模式，不应受 Inspector 能否直接显示私有实现影响。

十二、可复现基准与测试设计

比较 SortedList 和 SortedDictionary 时，至少使用以下工作负载：

• 从空容器随机顺序构建；
• 在已知最终数量时预留容量构建；
• 按已排序 key 顺序构建；
• 按 key 的命中/未命中混合查询；
• 顺序枚举所有条目；
• 头部、中部、尾部和随机删除；
• 稳态查询中穿插少量更新。

参数要来自业务规模，键不能只用顺序 int 代表所有复合/string comparer。报告记录 TFM、runtime、CPU、构建配置、数量、插入顺序、命中率、分配和驻留内存。微基准只回答局部问题，Unity 最终选型还需在目标 Player 的完整配置加载/查询场景中复测。

正确性可使用参考模型做差分测试：用普通 Dictionary 保存键值唯一性，每步后将其 key 按相同 comparer 排序，与 SortedList 枚举结果对比。随机生成 Add、setter、Remove、Clear 和查询序列，每步检查 Count、键顺序、键值对应和重复键行为。

十三、审查清单

1. 业务需要的是有序映射，还是只需精确查找的哈希映射？
2. comparer 是否定义了稳定顺序，零比较是否真的表示同一键？
3. key 在集合中是否不可变，排行榜分数等可变属性是否被误用为 key？
4. 构建是一次性还是持续随机插入？是否存在 O(n) 后缀搬移热点？
5. 是否能合理预留容量，还是因过度估计浪费两个大数组？
6. 是否依赖某个并不存在于目标 TFM 的按索引 API？
7. 是否把排名索引当成稳定 ID，忽略了中间插入会移动后续位置？
8. Clear 后的大容量是有意复用，还是未受控驻留？缩容时机是否避开热路径？
9. 枚举期间是否修改集合，Keys/Values 是否被误当作独立快照？
10. 序列化是否保存 schema 和键语义，重建时是否检测新 comparer 下的冲突？
11. 是否用无环境的固定 MB/倍数代替了真实堆快照与工作负载基准？
12. 跨线程读写是否受同一同步协议保护，或已改为构建后不变快照？

十四、本篇结论

SortedList 用两个平行数组维护有序键值映射。二分查找使按键查询为 O(log n)，连续布局使枚举和已知索引访问紧凑，中间插入/删除则因双数组搬移为 O(n)。这些都是可从布局推导的成本，不需要依赖无条件倍数。

它的真正优势场景是更新少、查询/有序遍历多、容量可估且希望减少逐节点对象的映射。它的劣势是持续随机中间更新、大值搬移和索引不稳定。如果核心需求是大量动态插删，SortedDictionary 或专用结构可能更合适；如果不需有序，Dictionary 可能更直接。

最容易被忽略的仍然是 comparer：它既定义顺序，也定义键的唯一性。只有在 comparer 稳定、key 不变、平行数组不变式得到保护，且工作负载经目标运行时验证时，这个紧凑的双数组设计才会成为优势。

建议实验：对同一批键值分别以排序顺序和随机顺序构建 SortedList，记录构建、查询、枚举、分配与驻留容量；再与 SortedDictionary 做功能等价对照，找到属于你的更新比例与规模转折点。
下一篇：SortedSet、SortedDictionary 与 SortedList 综合选型。