Dictionary、SortedDictionary、Hashtable 与 OrderedDictionary映射结构选型系列C# 与常用数据结构源码剖析 · 哈希与映射篇阅读时间约 85 分钟版本口径DictionaryTKey,TValue、SortedDictionaryTKey,TValue、Hashtable以.NET 8.0.0为实现参考泛型OrderedDictionaryTKey,TValue以.NET 9.0公共 API/实现为参考。兼容边界System.Collections.Specialized.OrderedDictionary是早期非泛型类型与 .NET 9 泛型类型不同Unity/Mono/IL2CPP 的类库版本需单独核验。选型原则先确定“无序、按键排序、按位置有序”哪一种语义再比较键契约、修改分布、内存和平台不依据偶然枚举顺序。一、四个名字背后是三种顺序语义“有序字典”最容易产生误解DictionaryTKey,TValue与Hashtable的核心契约是按键查找不提供可持久依赖的排序语义。SortedDictionaryTKey,TValue按IComparerTKey定义的键顺序枚举。.NET 9 OrderedDictionaryTKey,TValue维护键值对的位置顺序支持按 key 和按 index 访问/修改默认常见使用表现为插入顺序但显式按位置插入/移动后顺序由位置操作决定。下面三种输出的业务含义不同按键排序A, B, C比较器定义 按位置顺序C, A, B插入/位置操作定义 无顺序契约不要将当前观察结果编码进协议JSON 对象字段在某些系统中虽然能保序展示但协议语义未必依赖字段顺序。若 UI/补丁/签名算法要求顺序应把顺序写进模型和测试不能“刚好 Dictionary 这样枚举”。二、总体矩阵复杂度必须写前提能力Dictionary (.NET 8)SortedDictionary (.NET 8)Hashtable (.NET 8)OrderedDictionary (.NET 9)键/值类型泛型泛型object/object泛型核心结构buckets entries/冲突链红黑树节点Bucket[] 开放寻址/双重哈希顺序键值存储 key 到位置索引按键查找期望 O(1)最坏 O(n)O(log n)期望 O(1)最坏 O(n)期望 O(1)最坏受哈希影响添加新键摊销期望 O(1)O(log n)摊销期望 O(1)尾部添加期望/摊销 O(1)按位置插入 O(n)删除键期望 O(1)O(log n)期望 O(1)墓碑影响探测查键期望 O(1)维持紧凑位置通常 O(n) 移动/重索引最小/最大键需扫描 O(n)O(log n) 沿树边需扫描 O(capacity)位置首尾不等于键最值按 index 访问无无无O(1) 位置访问枚举语义不承诺键排序/位置协议comparer 键顺序不承诺位置顺序每元素对象entries 数组内联通常一个树 Node 对象Bucket[] 存 object 引用顺序项通常数组式存储细节按 tag“期望 O(1)”依赖哈希分布、负载、比较成本和未遭攻击Resize/Rehash 是 O(n) 尖峰。OrderedDictionary 删除/中间插入若要保持连续位置不能宣称统一 O(1)。SortedDictionary O(log n) 还乘以 comparer 成本。容量与实现阈值不是公共契约。.NET版本可能改变桶长选择、快速取模、字符串 comparer 和增长策略。三、Dictionary通用无序哈希映射3.1 数据结构与空闲复用.NET 8Dictionary 使用 bucket 索引数组和 Entry 数组。Entry 保存 hashCode、next、key、value冲突通过 Entry 链连接删除槽可进入 free list后续插入复用。具体字段类型/编码按 tag不能从概念图推导所有版本。连续 Entry 数组通常比每元素 Node 有更少对象和更好遍历局部性键值若为 classEntry 内联的是引用目标对象仍分散。扩容分配新数组并重建桶链旧数组等待 GC。3.2 顺序不是契约某些现代 .NET 工作负载中 Dictionary 枚举看似接近插入顺序但删除、free slot复用、Resize、runtime升级都可能改变。官方类型的目的不是顺序模型。稳定 wire/测试输出应排序或使用有顺序契约的结构。3.3 API 选择if (map.TryGetValue(key, out Item? item)) Use(item);需要值时用一次 TryGetValue避免ContainsKey后索引器重复查找。只关心存在时 ContainsKey 合理添加冲突用 TryAdd覆盖用索引器CollectionsMarshalref API只在目标存在且能保证 ref 不跨结构修改时使用。3.4 适用场景无需稳定顺序、按 key 高频点查、构建/更新普遍的映射通常从 Dictionary 开始。它不是线程安全写容器多线程用外部锁、ConcurrentDictionary 或不可变快照取决于复合不变量。四、SortedDictionary按比较器维护红黑树4.1 比较为零就是键等价SortedDictionary 的键唯一性由IComparerTKey.Compare(x,y)0定义而 Dictionary 由IEqualityComparerTKey.Equals/GetHashCode定义。两个对象Equals不同但 comparer 返回 0 时在 SortedDictionary 中是同一键。var sorted new SortedDictionarystring, int( StringComparer.OrdinalIgnoreCase); sorted.Add(alpha, 1); // sorted.Add(ALPHA, 2); // 比较为 0重复键。comparer 必须稳定、反对称、传递。键入树后修改参与比较字段会破坏搜索方向与可变哈希键同样危险。4.2 为什么是 O(log n)红黑树限制高度ContainsKey/Add/Remove 在最坏情况下沿 O(log n) 高度并做有限旋转/着色。它不依赖哈希分布因此对需要有序范围/最小最大/确定键序的场景有价值。但公共 SortedDictionary 缺少所有顺序统计能力按第 k 个键随机访问不是自动 O(log n)节点通常不维护公开 subtree size。枚举全表仍 O(n)。范围查询 API 也不等同 SortedSet 的 GetViewBetween需按公开表面设计。4.3 内存与 GC每个键值通常对应树 Node 对象含左右引用、颜色和 KeyValuePair对象头/对齐依 runtime。相比 Dictionary Entry 数组对象更多且遍历指针化但中间更新无需移动一整个排序数组。不要给固定内存倍率。4.4 适用场景持续插入/删除同时需要随时按键顺序枚举、Min/Max风格访问或自定义排序时考虑。若构建一次、查询/枚举很多SortedListTKey,TValue或排序数组可能有更好局部性写入 O(n) 与读取布局之间权衡。五、Hashtableobject 边界与开放寻址遗产5.1 不是 Dictionary 的链式版本.NET 8Hashtable 兼容实现使用 Bucket[] 开放寻址和双重哈希探测。Bucket 概念上保存 key、val 和 hash/collision 状态冲突键按第二哈希步长寻找后续槽不创建 Entry 冲突链。slot(i) (h1 i * h2) mod bucketLength实际增量公式、质数和位编码按源码。探测遇到从未使用空槽可结束删除槽必须保留墓碑/碰撞信息否则会截断后续碰撞键的查找。删除多、负载高会增加探测rehash 时将有效项重新放入新表。5.2 object、装箱和延迟类型错误值类型 key/value 转 object 时发生装箱语义读取需精确拆箱异质错误从编译期推迟到运行时。引用类型本身不因 object 再装箱。var legacy new Hashtable(); legacy[42] 7; // key/value 均为值类型跨 object 边界。 int value (int)legacy[42]!;实际分配/JIT逃逸优化用目标环境测不能写每项固定字节或倍率。泛型 Dictionary 的最确定收益是类型安全且值类型常可内联 Entry。5.3 comparer 与 nullHashtable 支持兼容的非泛型相等比较器/历史 comparer 入口。key 不允许 nullvalue 可为 null索引器返回 null 无法单独区分“缺失键”和“存在 null value”应用要 ContainsKey。迁移旧表必须保存字符串大小写/文化 comparer不是简单 Cast 到 Dictionary。旧IHashCodeProvider/IComparer组合也可能有特别语义。5.4 同步包装Hashtable.Synchronized只让单方法通过 SyncRoot 协调不让 ContainsAdd 成事务枚举需按文档锁住整个过程。迁到普通 Dictionary 会丢同步迁 ConcurrentDictionary 又会改变委托/枚举语义应显式设计。Hashtable 合理存在于旧 API/二进制/序列化边界新核心代码一般封装后向泛型迁移但“不使用”不是删除兼容合同的授权。六、.NET 9 泛型 OrderedDictionarykey 与 index 双访问6.1 它维护位置不做键排序var ordered new OrderedDictionarystring, int(); ordered.Add(C, 3); ordered.Add(A, 1); ordered.Insert(1, B, 2); // 位置顺序C, B, A不是 A, B, C。泛型 OrderedDictionary 同时支持按 key 和按整数 index 访问/更新并可 Insert/RemoveAt/IndexOf 等。具体成员名和重载以.NET 9reference assembly 为准不把 preview API 记忆当正式表面。6.2 实现成本.NET 9 实现以顺序键值存储保持 index 访问再用哈希索引将 key 映射到位置。它不是必须采用“哈希表 双向链表 第三个索引数组”的公共契约私有结构未来可变。尾部 Add 有利于摊销中间 Insert/RemoveAt 为维持连续顺序要移动后续项并更新受影响的 key-index 映射通常 O(n)。按 key Remove 先哈希定位再承担位置压缩。按 index 访问可 O(1)。因此它适合“位置访问/顺序输出重要修改主要尾部或规模可控”不是免费同时获得所有结构优点。6.3 comparer 与键不变量key 唯一性仍由IEqualityComparerTKey/哈希定义不是顺序 comparer。键入表后不可改变哈希/相等字段。顺序变化不改变 key 身份。6.4 与非泛型 OrderedDictionary 区分System.Collections.Specialized.OrderedDictionary使用 object key/value有装箱/运行时类型边界和自己的 API泛型类型位于现代集合命名空间/程序集按 .NET 9 reference确认。二者序列化、接口和线程语义不能互换。七、比较器是映射的身份规则结构身份接口必须满足Dictionary / OrderedDictionaryIEqualityComparerTKey相等键同哈希相等稳定Hashtable非泛型IEqualityComparer/兼容路径object 类型兼容相等同哈希SortedDictionaryIComparerTKeycompare0 为等价全序稳定字符串常见选择Ordinal 适合协议/机器 IDOrdinalIgnoreCase 适合明确不区分大小写的机器键文化比较适合面向人的排序但需固定 culture/规则。默认不是错误关键是写清领域身份。不要用当前进程GetHashCode作为持久化 ID字符串哈希可能随机化算法随 runtime 变。排序 comparer 的结果也可能随文化数据升级而变化稳定存档/签名要定义规范化与版本。可变 key 是四种结构共同风险Hashtable/哈希表可能找错桶树可能沿错方向。使用 immutable record/readonly struct、稳定 ID或 Remove旧键后再 Add新键。比较器本身可能是性能主因。复杂 Unicode 规范化、数据库访问或分配都比结构导航昂贵比较器应纯、快速并在插入前预规范化适当数据。八、容量、分配与 GC8.1 组成式成本Dictionary ≈ object bucket array Entry array key/value对象若引用 SortedDictionary ≈ object count * Node key/value对象 Hashtable ≈ object Bucket arrayobject key/value 装箱/目标对象 OrderedDictionary ≈ object 顺序项存储 key索引存储 目标对象不写固定字节对象头、引用宽度、T 大小、对齐、runtime 均变化。SortedDictionary 节点多GC 图更碎数组式结构扩容产生大数组峰值OrderedDictionary 为双访问保留两套索引信息Hashtable 值类型盒对象增加对象数。8.2 Ensure/TrimDictionary/OrderedDictionary 的 capacity API 随版本预分配能减少 Resize但过估提高常驻。Trim 是 O(n)/可能分配重建之后增长会震荡。SortedDictionary 无连续 capacityClear 后节点等待 GC。Hashtable 构造 capacity 与 load factor 影响实际 Bucket 长度不是“恰有 capacity 槽”。迁移不要比较 Capacity 数字表面相等而应比较预计 Count 和峰值。8.3 引用清理和池删除后容器应解除有效 key/value 引用free capacity 本身不保活已清字段但旧枚举器、快照或外部索引可能保留。对象池会保留历史峰值并非自动改善 GC。用 heap retention path 证明 owner。九、枚举、版本与快照四者的可变实例都不应在枚举期间结构修改通常 version 检测抛 InvalidOperationException但 fail-fast 不是线程安全。Dictionary/Hashtable 的枚举顺序无业务保证。SortedDictionary 保证 comparer key 顺序OrderedDictionary 保证位置顺序。ToArray/复制才是结构快照枚举器不是并发快照。即使复制 KeyValuePair 数组key/value 若为可变 class 仍共享对象。需要历史快照应使用不可变元素或深拷贝策略。排序/位置顺序的 comparer 或 index 修改也会影响序列化输出。签名算法应显式 canonicalize不仅依赖容器枚举。十、并发与复合操作这四种类型的普通实例均不提供任意并发写安全。多个只读线程仅在没有任何写者、comparer和键对象也不变时可行。// 竞态每个方法单独安全也不足以保证复合唯一插入。 if (!map.ContainsKey(key)) map.Add(key, value);外部 lock 覆盖整个事务或使用 ConcurrentDictionary 的 TryAdd/GetOrAdd后者不维护位置/排序且 factory 可能多次执行。需要“并发 有序快照”常用单写者更新普通结构并发布不可变快照而不是寻找一个全能容器。SortedDictionary 的 range 修改、OrderedDictionary 的 key/index 双索引都需同一锁维护不变量。Synchronized Hashtable 也不解决跨调用事务。十一、失败场景用 Dictionary 当前枚举顺序做存档/网络协议。把 SortedDictionary 的“有序”理解为插入顺序。把 OrderedDictionary 的“有序”理解为按 key 比较排序。宣称 OrderedDictionary 所有增删 O(1)忽略位置移动/重索引。把 Hashtable 画成 Dictionary Entry 冲突链。删除开放寻址槽时清成空截断碰撞探测。迁 Hashtable 忽略旧 comparer/null value/同步包装。用可变对象做 key入表后改变哈希/比较字段。comparer 认为相等但 hash 不同或排序不传递。先 ContainsKey 再索引器重复查找且暴露并发窗口。Clear 后断言后备容量已归还。枚举中修改或把 version 检测当线程锁。用 ConcurrentDictionary 替换有序结构并假设顺序仍在。Unity 项目照抄.NET 9OrderedDictionary 而未检查 API profile。依据固定倍数/推荐星级选择不测键和操作分布。十二、Unity、Mono 与 IL2CPPUnity 2022.3 的 API Compatibility Level 不等于.NET 8/9reference assembly。泛型.NET 9 OrderedDictionaryTKey,TValue通常不能假定存在复制新 CoreLib 类型源码/程序集可能与 Unity BCL 内部依赖冲突。Unity 内置 Mono 的 Dictionary/SortedDictionary/Hashtable 实现可能来自不同类库代际IL2CPP 编译该类库语义为 C/native code不把它自动升级到桌面实现。私有 bucket/Entry、字符串 comparer和增长策略必须按 Unity 包/源码/生成代码核验。Burst Jobs 通常不能使用托管 Dictionary/SortedDictionary/Hashtable使用NativeHashMap、NativeParallelHashMap等目标 Collections 包结构并遵守 unmanaged约束、Allocator、JobHandle与ParallelWriter协议。Native 容器的顺序同样不可臆测。UnityEngine.Object 作为 value 会保留托管包装引用原生对象销毁后有特殊 null 语义。作为 key 更危险对象生命周期/哈希稳定性与 InstanceID 复用应按引擎规则不用作长期存档身份。Inspector/Unity serializer 对 Dictionary 支持边界依版本/自定义封装有序显示需求可序列化列表 DTO并在加载时构建运行时索引。不要让编辑器显示顺序绑死哈希枚举。性能在 Editor Mono 和目标 IL2CPP Release 真机分别测Burst/Native结果属于另一结构域。十三、决策流程需要 key - value 映射 ├─ 要按 comparer 的 key 顺序持续枚举/Min-Max │ └─ SortedDictionary或构建后排序数组/SortedList按更新比选择 ├─ 要稳定位置顺序 key/index 双访问 │ └─ .NET 9 OrderedDictionary旧TFM考虑显式 List Dictionary 双结构 ├─ 只要 key 点查不要顺序契约 │ └─ Dictionary └─ 被旧 object API/序列化绑定 └─ Hashtable 留在适配边界逐步迁移然后修正多线程写加入完整同步/ConcurrentDictionary/快照架构。每键多值四者都不是自动 multi-mapvalue 用列表/集合并定义所有权。读多写少且构建后固定考虑 FrozenDictionary/ImmutableDictionary目标版本支持时。key 排序只在偶尔输出需要Dictionary 输出时排序可能比持续维护树更合适。位置中间插删频繁且规模大OrderedDictionary O(n) 搬移可能不合适考虑链索引/专用结构并承担对象成本。Unity Job转 Native/ECS 域不在四个托管类型中硬选。十四、迁移案例14.1 Hashtable 到 Dictionary先扫描实际 key/value 类型、null value、字符串大小写/文化、重复冲突和同步调用。用显式循环校验并迁移遇到 comparer 合并冲突由业务规则处理不用枚举后项静默覆盖。历史序列化保留适配 DTO不直接改字段类型后期待旧文件可读。14.2 Dictionary List 双结构到 OrderedDictionary原实现若DictionaryTKey,ItemListTKey先写不变量每个 key 在两边恰好一次、位置一致、删除/覆盖/移动原子。迁泛型 OrderedDictionary 后做差分按 key查找、按 index、Insert、Remove、Move/Set按真实 API、重复与 comparer。并发锁仍不能删除。14.3 SortedDictionary 到 Dictionary若 profile 发现排序只在导出时用可稳态用 Dictionary导出将 Keys/entries 复制排序。代价从每次更新 O(log n) 转到每次导出 O(n log n)分配。输出频率和 n 决定交叉点不能普遍化。十五、可复现实验15.1 相同语义操作轨迹预生成 keys 与 Add/lookup/remove 轨迹统一 comparer、重复处理和结果 checksum。分别测试构建、稳态点查、删除重插、完整枚举Ordered/Sorted 的顺序结果按各自契约验证不能用同一顺序断言。15.2 哈希退化与 comparer正常 hash、恒定 hash、长字符串、Ordinal/OrdinalIgnoreCase记录 hash/equals/compare调用次数代理、CPU、分配。退化输入先验证正确性再观察曲线不发布固定倍率。SortedDictionary 不受 hash影响但受 Compare成本。15.3 修改分布OrderedDictionary 测尾部 Add、头/中 Insert、按 key Remove、RemoveAtSortedDictionary测随机/有序 key 插删Dictionary/Hashtable测 Resize和墓碑/删除重插。参数化 n寻找成本曲线。15.4 内存与 GCT 取 int、large struct、class记录总分配、对象数、存活、Capacity/Count、Clear/Trim/再增长峰值。Hashtable值类型装箱单独用 IL/alloc验证。快照 root确保旧枚举器/结果没有保留容器。15.5 Unity Player在目标 Unity完整版本上只测试实际可用结构Editor Mono/IL2CPP Release分开若用NativeHashMap再单列复制/schedule/Dispose端到端。记录设备、backend、API profile、键分布、Profiler capture不把桌面.NET9结果外推。十六、审查清单业务说的“有序”是按键、按位置还是仅想确定输出当前类型/目标 TFM 真正提供哪些 APIkey 的 equals/hash 或 compare 是否稳定、一致、可测试null key/value 与缺失键怎样区分重复键是拒绝、覆盖、合并还是多值复杂度是否包含查找、移动、Resize、comparer和用户回调是否依赖偶然枚举顺序或内部地址Capacity 是否有依据Trim后会不会马上增长可变 value 内部是否另有线程安全/深快照要求复合操作是否由一把锁/单写者事务保护旧 Hashtable 的 comparer、同步和序列化契约是否保存Unity Mono/IL2CPP/Native域是否分别验证性能报告是否包含代码、版本、T、键分布和原始结果十七、总结先选择顺序合同再选择成本Dictionary 是通用无序哈希映射期望 O(1) 依赖良好哈希并承受 Resize尖峰SortedDictionary 用红黑树换取 comparer定义的稳定键序与最坏 O(log n)点操作Hashtable 是 object 边界的开放寻址/双重哈希兼容类型不是链式 Dictionary.NET 9泛型 OrderedDictionary 同时维护 key索引和位置序列中间修改为保序可能 O(n)。四者的 key 身份分别受 equality/hash或ordering comparer支配可变键都会破坏不变量。泛型避免延后类型错误并常减少值类型装箱但内存取决于T与实现。并发、序列化、深快照和Unity Jobs都不是容器名自动解决的问题。选型时先问排序/位置/无序再写重复、null、线程和迁移合同最后用同语义、同 comparer、同输入的曲线实验验证。这样不会因一次枚举顺序或一张固定倍率表选中契约错误的结构。下一篇StackLIFO 的数组实现