06-04-排序集合-SortedList-TKey-TValue-双数组实现的有序集合-北京尧图网络

SortedListTKey,TValue双数组有序映射的源码模型与选型边界系列C# 与常用数据结构源码剖析 · 排序集合篇阅读时间约 55 分钟前置知识二分查找、动态数组、比较器与 SortedDictionary版本边界以现代System.Collections.Generic.SortedListTKey,TValue的共同形状为主。私有字段、容量增长和便利 API 会随 TFM/tag 变化使用前应查目标 reference assembly 与固定源码 tag。一、名字像 List语义却是按键排序的 DictionarySortedList 实现键到值的唯一映射并按IComparerTKey定义的顺序保存键。它不是可以容纳重复键的排序条目 List也不是哈希表。当 comparer 返回零时两个键属于同一映射位置即使它们的Equals返回 false。它的核心实现是两个平行数组一个保存按比较器升序排列的 key另一个在相同索引保存 value。这种布局用连续存储换取了二分查找和紧凑遍历代价是中间插入/删除需要搬移后缀。SortedDictionary 则通常使用平衡树存储节点插入与删除无需搬移大段连续元素但逐节点对象、左右引用和指针追踪增加内存与缓存成本。选型不是“数组比树快”而是更新频率、规模、顺序访问、内存与比较器成本的组合。二、核心字段与不变式下面是教学模型不是可替换目标 runtime 的逐字源码public class SortedListTKey, TValue { private TKey[] _keys; private TValue[] _values; private int _size; private int _version; private IComparerTKey _comparer; }任何公开操作前后都必须维护_keys.Length _values.Length容量在两个数组上一致。0 _size Capacity有效区间恰好是[0, _size)。对每个有效索引 i_keys[i]与_values[i]组成一个键值对。相邻有效键满足Compare(_keys[i], _keys[i1]) 0零比较的重复键不能同时存在。有效区间外的槽不是公开数据对含引用类型删除/清空时应断开无效槽对对象的保活。这些不变式解释了为什么 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 重复也不要在“最后写入胜出”就是业务规则时用异常做正常分支。插入的教学步骤是拒绝不符合类型/API 契约的空 key。二分查找命中时按 Add 或 setter 语义处理。若未命中恢复插入位置并确保两个数组容量足够。将 key 和 value 数组在插入点之后的有效后缀各后移一位。在相同索引写入 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 不用EqualityComparerTKey判断重复而使用IComparerTKey.Compare(x,y)0。因此 comparer 必须提供稳定、自洽的全序或至少满足集合操作所需的严格弱序性质。若它一会儿认为 ab一会儿又认为 ba二分查找的前提就被破坏。下面的 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 与稳定键字段重建时明确使用相同业务规则或执行迁移。九、复杂度、常数与内存账本操作SortedListSortedDictionary决定成本的主要因素按键查找O(log n)O(log n)二分随机访问 vs 树节点追踪comparer 成本中间插入O(n)O(log n)双数组后缀搬移 vs 树搜索/修复删除O(n)O(log n)双数组左移 vs 树摘链/修复按已知索引访问内部 O(1)通常无排名索引公开 API 需按 TFM 核对顺序枚举O(n)O(n)连续扫描 vs 树遍历栈大 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、键顺序、键值对应和重复键行为。十三、审查清单业务需要的是有序映射还是只需精确查找的哈希映射comparer 是否定义了稳定顺序零比较是否真的表示同一键key 在集合中是否不可变排行榜分数等可变属性是否被误用为 key构建是一次性还是持续随机插入是否存在 O(n) 后缀搬移热点是否能合理预留容量还是因过度估计浪费两个大数组是否依赖某个并不存在于目标 TFM 的按索引 API是否把排名索引当成稳定 ID忽略了中间插入会移动后续位置Clear 后的大容量是有意复用还是未受控驻留缩容时机是否避开热路径枚举期间是否修改集合Keys/Values 是否被误当作独立快照序列化是否保存 schema 和键语义重建时是否检测新 comparer 下的冲突是否用无环境的固定 MB/倍数代替了真实堆快照与工作负载基准跨线程读写是否受同一同步协议保护或已改为构建后不变快照十四、本篇结论SortedList 用两个平行数组维护有序键值映射。二分查找使按键查询为 O(log n)连续布局使枚举和已知索引访问紧凑中间插入/删除则因双数组搬移为 O(n)。这些都是可从布局推导的成本不需要依赖无条件倍数。它的真正优势场景是更新少、查询/有序遍历多、容量可估且希望减少逐节点对象的映射。它的劣势是持续随机中间更新、大值搬移和索引不稳定。如果核心需求是大量动态插删SortedDictionary 或专用结构可能更合适如果不需有序Dictionary 可能更直接。最容易被忽略的仍然是 comparer它既定义顺序也定义键的唯一性。只有在 comparer 稳定、key 不变、平行数组不变式得到保护且工作负载经目标运行时验证时这个紧凑的双数组设计才会成为优势。建议实验对同一批键值分别以排序顺序和随机顺序构建 SortedList记录构建、查询、枚举、分配与驻留容量再与 SortedDictionary 做功能等价对照找到属于你的更新比例与规模转折点。下一篇SortedSet、SortedDictionary 与 SortedList 综合选型。

06-04-排序集合-SortedList-TKey-TValue-双数组实现的有序集合

相关推荐

极米投影配120英寸隐藏式光学幕布：从开槽到验收的全流程指南

基于Python的智能聊天助手：语音触发与模板消息自动发送实战

银行客户聚类分析实战：从K-Means算法到业务分群落地

更多资讯

泗县安监局电工证怎么报名外省证书能转吗

电工证过期哪里补办多久拿证？别怕考不过白交钱

虎林考电工证实操怕挂科？网上查询真题+备考方案全公开

博罗电工证考试试题保姆级教程：工地太忙根本没时间复习考试怎么办

检查电工证真假复审延期怎么办理

广州电工证年审千万别踩坑，外省证能转过来吗？

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？