SortedDictionaryTKey,TValue比较器定义唯一性的有序树映射系列C# 与常用数据结构源码剖析 · 排序集合篇阅读时间约 50 分钟前置知识二叉搜索树、红黑树、比较器、字典契约版本边界本文讲解当代 .NET 中稳定的公共契约。私有字段、内部辅助类和节点布局会随dotnet/runtime版本变化讨论源码时必须固定与目标 SDK/runtime 对应的 tag 或 commit。一、它是“按键有序的映射”SortedDictionaryTKey, TValue同时提供两个性质每个键最多对应一个值枚举时按键的比较顺序输出键值对。它不是“每次枚举前才排序”而是在每次插入和删除后都维护一棵平衡搜索树。var prices new SortedDictionarystring, decimal(StringComparer.Ordinal) { [potion] 12.5m, [apple] 3m, [sword] 80m }; foreach (KeyValuePairstring, decimal pair in prices) Console.WriteLine(${pair.Key}: {pair.Value});上例的枚举顺序是apple、potion、sword因为键比较器是StringComparer.Ordinal。这个顺序同时是查找树的组织依据不只是展示时的格式。值不参与定位。两个键是否相同、应位于左子树还是右子树全部由IComparerTKey决定。因此它是 tree map而不是将DictionaryTKey,TValue的结果临时调用OrderBy得到的快照。二、最重要的契约比较为零就是同一个键DictionaryTKey,TValue使用IEqualityComparerTKey定义键相等SortedDictionaryTKey,TValue使用IComparerTKey的结果同时定义排序和唯一性。对任意两个键a、bcomparer.Compare(a, b) 0 a 排在 b 前 comparer.Compare(a, b) 0 a 排在 b 后 comparer.Compare(a, b) 0 集合把 a 与 b 视为同一个键这一点可以刻意用来建模也可能造成数据丢失。例如忽略大小写的字符串比较器会把Player和player当作同一个键var users new SortedDictionarystring, int( StringComparer.OrdinalIgnoreCase); users.Add(Player, 10); // users.Add(player, 20); // 抛出重复键异常 users[player] 20; // 更新已有键对应的值自定义比较器若只比较主键中的一部分那么其他部分不会用来破平局。比如只比较日期而忽略订单 ID一天就只能存一个键。如果希望同日容纳多条订单必须在比较结果相同时继续比较稳定唯一 ID。public readonly record struct TimelineKey(long Timestamp, long Sequence); public sealed class TimelineKeyComparer : IComparerTimelineKey { public int Compare(TimelineKey x, TimelineKey y) { int byTime x.Timestamp.CompareTo(y.Timestamp); return byTime ! 0 ? byTime : x.Sequence.CompareTo(y.Sequence); } }比较器必须是自反的、反对称的、传递的并且对同一对键给出稳定结果。不要从当前文化、可变全局配置、随机数或时钟中读取会变化的排序状态。否则已在树中的键可能突然不再位于比较器认为正确的位置查找和删除的结果将失去意义。三、实现模型平衡搜索树如何支撑映射在特定的当代dotnet/runtimetag 中可以观察到SortedDictionary将键值对放入基于红黑树的内部集合再用一个只比较Key的包装比较器实现字典语义。但内部类型名称、字段名称和复用关系都不是公共契约。下面只是结构化模型不是任何版本的逐字源码// 教学模型实际源码需按固定 runtime tag 阅读。 private sealed class PairComparer : IComparerKeyValuePairTKey, TValue { private readonly IComparerTKey _keys; public PairComparer(IComparerTKey keys) _keys keys; public int Compare( KeyValuePairTKey, TValue x, KeyValuePairTKey, TValue y) _keys.Compare(x.Key, y.Key); }红黑树通过颜色和局部旋转保持高度为 O(log n)。查找从根开始比较为零则命中小于零进入一侧子树大于零进入另一侧。插入和删除除了定位节点还要通过重染色和旋转修复平衡约束。中序遍历依次访问左子树、节点和右子树因此自然按键比较顺序产生结果。这一结论来自树不变式不要反向假设内部节点在内存中也按这个顺序连续排列。四、Add 与索引器重复键时的语义不同Add(key, value)表示“这必须是一个新键”。如果比较器认为已有键与它相同Add抛出ArgumentException。这适合将重复视为业务错误的注册边界。索引器map[key] value表示插入或更新。键不存在时新建节点键存在时替换其值。替换值不改变键的排序位置但仍是集合修改应假定已存在的枚举器会失效。if (!map.TryAdd(key, value)) { // 仅当目标框架的公共 API 包含 TryAdd 时使用。 HandleDuplicate(key); }TryAdd是否可用要查目标框架的 reference assembly不能因为当前文档存在就倒推所有旧版本都支持。如果目标版本没有该 APIContainsKey后再Add会进行两次树定位但在非并发、非热路径的边界上可以优先保持意图清晰。五、查找、删除与空值边界TryGetValue(key, out value)在找到键时返回true并输出值未找到时返回false。它能区分“键不存在”与“键存在值恰好是default”通常比先ContainsKey再用索引器更合适。if (map.TryGetValue(key, out TValue value)) Consume(value);读索引器map[key]在键不存在时抛出KeyNotFoundException适合“缺少键表明程序不变式被破坏”的场景。ContainsKey是按键进行树查找ContainsValue无法利用键树排序需要检查值通常是 O(n)。Remove(key)按键定位节点成功时移除并修复树平衡。当目标版本提供带out TValue的移除重载时可在一次操作中取得被移除的值这仍需按 reference assembly 验证版本不应在针对旧 TFM 的教程中直接使用。对引用类型键null不是一个可依赖的普通键值公共操作会根据契约拒绝它。值则可以是null前提是TValue的类型允许。因此不能使用“返回值为 null”判断键是否存在TryGetValue才是对应契约。六、枚举、Keys 和 Values 是活视图不是快照直接枚举字典会按键顺序产生KeyValuePairTKey,TValue。Keys和Values返回的集合视图也分别按键顺序枚举键与对应值。Values的“有序”指它们跟随键的顺序不是按值自身排序。这些视图反映底层字典的当前内容不是调用属性时复制出来的数组。它们不提供向字典独立添加键或值的语义。如果需要一个不受后续修改影响的快照应显式复制到数组或其他容器。树的枚举器通常用栈记录中序遍历路径总枚举时间是 O(n)额外路径状态与树高相关。枚举期间修改字典会使枚举器失效不要在foreach中直接添加、删除或替换元素。需要批量删除时可先收集键快照再在枚举结束后修改。七、区间查询的能力边界有序树在数据结构层面适合范围查询但SortedDictionary的公共 API 并没有直接对齐SortedSetT.GetViewBetween的通用键区间视图。这是“底层结构可以做”与“公共容器提供了 API”的典型区别。如果从字典开头枚举跳过小于下界的键并在大于上界时停止结果是正确的但寻找下界的前缀扫描可能是 O(n)。LINQWhere或SkipWhile不会自动识别底层搜索树并跳到下界。public static IEnumerableKeyValuePairTKey, TValue ScanRangeTKey, TValue( SortedDictionaryTKey, TValue source, TKey lowerInclusive, TKey upperExclusive) where TKey : notnull { IComparerTKey comparer source.Comparer; foreach (KeyValuePairTKey, TValue pair in source) { if (comparer.Compare(pair.Key, lowerInclusive) 0) continue; if (comparer.Compare(pair.Key, upperExclusive) 0) yield break; yield return pair; } }这个方法的名字特意用Scan避免让调用者误以为它可以 O(log n) 定位下界。如果业务频繁做大字典上的窄区间查询可考虑将键值对封装为元素存入提供区间视图的有序集合使用能二分定位索引的SortedList或选择暴露 lower-bound 迭代器的专用索引。选择前要明确更新频率、区间宽度和内存预算。八、与 Dictionary 和 SortedList 的根本差异维度DictionaryTKey,TValueSortedDictionaryTKey,TValueSortedListTKey,TValue组织方式哈希桶与 Entry平衡搜索树并行的有序键/值数组唯一性IEqualityComparerTKeyIComparerTKey.Compare 0IComparerTKey.Compare 0键查找期望 O(1)O(log n)O(log n) 二分中间插入/删除期望 O(1)O(log n)O(n) 搬移顺序枚举不作为键排序契约按键比较顺序按键比较顺序局部性数组为主较好节点间接引用连续数组较好每项内存桶/Entry 开销节点、子链接/平衡元数据紧凑数组容量按索引访问不提供排名语义不提供Keys/Values支持索引语义Dictionary适合不需要按键排序、主要追求按键快速定位的场景。即使某个运行时的实际枚举看起来与插入顺序有关也不能将它当成“键排序”的替代。SortedList查找也是 O(log n)但插入或删除中间键需搬移后续数组。它适合构建后少改、需要紧凑存储或按排名索引访问的场景。SortedDictionary适合持续插入和删除但不应因为它的渐近复杂度更好就宣称任何数量下都更快。九、复杂度之外节点分配与缓存局部性平衡树保证搜索、插入和删除的 O(log n) 最坏时间但大 O 记号不说明常数开销。树查找会沿节点引用跳转节点未必在内存中连续每次插入可能需要新节点节点除键值外还要存储树链接和平衡状态。相比之下SortedList在两个连续数组上二分和遍历对 CPU 缓存通常更友好但中间更新会搬移数据。Dictionary也以数组存储为主但还要支付哈希和冲突链追踪。键和值的大小、比较成本、数据规模与访问模式都会改变转折点。因此“频繁增删就选树”只是起点。对几十个元素数组搬移可能比节点分配和指针跳转便宜对数万个且持续随机更新的键O(n) 搬移则可能成为主导成本。最终结论应来自目标 runtime、目标设备上的可重复基准而不是捏造固定倍数。十、可变键会让节点“消失”键入树后凡是会影响比较结果的状态都必须保持不变。假设PlayerKey的比较器使用可修改的Name键入树后改名节点仍留在旧名对应的树位置。以新名查找会沿另一条路径前进以旧名构造新键也未必能命中节点对应的内存没有丢失但搜索契约已经被破坏。正确做法是使用不可变键或者在更改排序字段前用旧键删除然后以新键重新插入。不要指望字典监听对象属性变化。字符串本身不可变但比较语义仍要明确。持久化标识符、协议字段和内部代码通常适合 ordinal 比较面向用户的词典排序可能需要指定文化。使用当前文化会让顺序随运行环境变化不适合需要跨机器确定性的存档、网络协议或工具输出。十一、线程安全与快照发布SortedDictionary不是并发集合。多个线程同时写入或在一个线程枚举时另一个线程修改都需要外部同步。TryGetValue、ContainsKey等名字不含“线程安全”承诺。只读并发在没有任何线程修改集合且对象已安全发布时才可讨论。如果业务是“后台周期更新大量读者无锁查询”一种方案是构建新的不可变快照完成后原子替换根引用。这用额外构建内存换取读路径简单性并不等于把可变SortedDictionary暴露给所有读者。若必须用锁要把“检查后修改”包在同一个临界区内避免两个线程都看到键不存在后同时Add。但不要在持锁期间调用不受控的回调或做长时间 I/O可以在锁内复制所需数据在锁外处理。十二、序列化枚举有序不等于协议保证顺序当序列化器通过公共枚举读取字典时输入键值对是按键比较顺序产生的。但输出格式是否保留属性顺序、解析器是否认为顺序有语义取决于具体序列化库和协议。JSON 对象属性的逻辑含义不应依赖文本中的排列顺序。重建SortedDictionary时还必须恢复原来的比较器语义。如果原对象使用忽略大小写比较反序列化时却使用默认比较器唯一性和枚举顺序都可能改变。不要假设序列化器会自动持久任意IComparerTKey的具体类型和状态。如果文件需要确定性以便做内容哈希、签名或差异审查应定义独立的规范化编码固定 ordinal 排序、数字与日期格式、字符编码、转义和重复键策略。不应只因为来源容器“看起来有序”就认定输出跨库、跨版本完全稳定。十三、排行榜案例主次键与反向顺序排行榜不能只用分数作键否则同分玩家会被比较器视为重复键。一个完整键可以按分数降序、达成时间升序、玩家 ID 升序比较public readonly record struct RankKey( long Score, long AchievedAt, long PlayerId); public sealed class RankKeyComparer : IComparerRankKey { public int Compare(RankKey x, RankKey y) { int byScore y.Score.CompareTo(x.Score); // 高分在前 if (byScore ! 0) return byScore; int byTime x.AchievedAt.CompareTo(y.AchievedAt); if (byTime ! 0) return byTime; return x.PlayerId.CompareTo(y.PlayerId); } }更新玩家分数时必须先用旧RankKey删除再添加新键。为了 O(log n) 找到玩家的旧键可以另维护DictionaryPlayerId, RankKey作为反向索引。两个结构必须在同一个事务边界内更新若中途操作失败要回滚或从单一事实源重建索引。但SortedDictionary不提供按排名索引 O(1) 取第 k 名也不在节点上维护子树元素数。枚举前 100 名很自然频繁查询“某玩家是第几名”则可能要扫描或需要支持 order statistic 的专用树。这是容器契约与业务查询的关键匹配问题。十四、时间索引案例同时刻事件与范围扫描事件时间线可以使用前文的(Timestamp, Sequence)键保证同一时刻多个事件仍然唯一且顺序明确。从最早时间开始消耗事件非常适合树的有序枚举但枚举期间不能删除因此可以先收集到期键再二次删除。public static ListTimelineKey CollectDueTEvent( SortedDictionaryTimelineKey, TEvent timeline, long now) { var due new ListTimelineKey(); foreach (KeyValuePairTimelineKey, TEvent pair in timeline) { if (pair.Key.Timestamp now) break; due.Add(pair.Key); } return due; }这对“从最早事件扫到 now”很有效因为无需跳过大量不相关前缀。但对“查询一年数据中某个很晚的五分钟窗口”SortedDictionary公共枚举器缺少 lower-bound 起点从头扫描会浪费前缀成本。这时应评估时间分桶、SortedList二分索引、数据库 B-tree 索引或专用范围树。十五、测试首先验证比较契约测试不应只验证三个整数能按升序枚举。一个教材级测试集至少包含空字典、单元素、严格递增、严格递减与随机插入。Add遇重复键抛异常索引器遇相同键替换值。TryGetValue区分缺少键和值为default。删除叶子、单子节点、双子节点、根以及不存在键。大量修改后枚举仍严格遵守比较器顺序。忽略大小写比较器对“比较相等但Equals不同”的键正确拒绝重复。主次键比较器在主键相同时不会丢失业务元素。枚举期间修改的失效行为Keys/Values视图在后续修改后反映当前内容。序列化往返后比较器语义、键唯一性与排序顺序不变。对自定义比较器可以做性质测试从业务键域生成大量a、b、c验证Compare(a,a)0比较符号反对称以及ab且bc时ac。还要专门生成主键相同、次键不同的样例因为漏掉最后的破平局字段是最常见的数据丢失原因之一。若做性能基准应在同一业务输入上分别测查找、批量构建、随机插入/删除、全量枚举和区间查询同时记录分配与驻留内存。固定 runtime 版本、CPU、数据规模、键分布和比较器并使用成熟基准框架。没有原始报告的固定性能倍数不是可复现的结论。十六、选型决策树选择前先回答“顺序是否是业务契约”。如果不需要按键有序枚举通常先考虑Dictionary。如果需要顺序再回答以下问题是否持续做随机插入和删除是则倾向SortedDictionary。是否构建一次、长期读取且重视紧凑存储和索引访问是则评估SortedList。是否只需要唯一的有序元素而不是键值映射是则使用SortedSetT。是否频繁查询窄键区间检查容器是否真正提供 lower-bound/区间视图不要只看“底层是树”。是否需要按排名查第 k 项或元素的排名普通红黑树字典没有子树数量应评估 order-statistic tree 或其他索引。是否多线程频繁更新先设计所有权、锁策略或不可变快照不要把容器类型当作并发方案。最后检查比较器它定义的不只是顺序还定义了“一个键”究竟是什么。如果团队无法用业务语言说清Compare(a,b)0的含义就还没有完成SortedDictionary的数据建模。结语SortedDictionaryTKey,TValue是一个按键有序、能在持续更新下保持 O(log n) 定位的树映射。它的灵魂不是“红黑树”这个名称而是比较器契约比较结果既决定节点位置也决定键是否重复。工程上不能只看 O(log n)。节点分配、指针跳转、比较器成本、缺少公共 lower-bound 视图、枚举修改限制和线程所有权都可能比渐近界更早决定选型。将公共契约与固定 tag 的源码细节分开用业务键测试比较性质再用真实工作负载对比Dictionary、SortedList与专用索引才能得到可验证的结论。下一篇SortedListTKey,TValue双数组实现的有序映射