企业官网建设流程全解析

Dictionary、SortedDictionary、Hashtable 与 OrderedDictionary：映射结构选型

系列：C# 与常用数据结构源码剖析 · 哈希与映射篇
阅读时间：约 85 分钟
版本口径：Dictionary<TKey,TValue>、SortedDictionary<TKey,TValue>、Hashtable以.NET 8.0.0为实现参考；泛型OrderedDictionary<TKey,TValue>以.NET 9.0公共 API/实现为参考。
兼容边界：System.Collections.Specialized.OrderedDictionary是早期非泛型类型，与 .NET 9 泛型类型不同；Unity/Mono/IL2CPP 的类库版本需单独核验。
选型原则：先确定“无序、按键排序、按位置有序”哪一种语义，再比较键契约、修改分布、内存和平台，不依据偶然枚举顺序。

一、四个名字背后是三种顺序语义

“有序字典”最容易产生误解：

1. Dictionary<TKey,TValue>与Hashtable的核心契约是按键查找，不提供可持久依赖的排序语义。
2. SortedDictionary<TKey,TValue>按IComparer<TKey>定义的键顺序枚举。
3. .NET 9 OrderedDictionary<TKey,TValue>维护键值对的位置顺序，支持按 key 和按 index 访问/修改；默认常见使用表现为插入顺序，但显式按位置插入/移动后顺序由位置操作决定。

下面三种输出的业务含义不同：

按键排序：A, B, C（比较器定义） 按位置顺序：C, A, B（插入/位置操作定义） 无顺序契约：不要将当前观察结果编码进协议

JSON 对象字段在某些系统中虽然能保序展示，但协议语义未必依赖字段顺序。若 UI/补丁/签名算法要求顺序，应把顺序写进模型和测试，不能“刚好 Dictionary 这样枚举”。

二、总体矩阵：复杂度必须写前提

“期望 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 有更少对象和更好遍历局部性；键值若为 class，Entry 内联的是引用，目标对象仍分散。扩容分配新数组并重建桶链，旧数组等待 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 的键唯一性由IComparer<TKey>.Compare(x,y)==0定义，而 Dictionary 由IEqualityComparer<TKey>.Equals/GetHashCode定义。两个对象Equals不同但 comparer 返回 0 时，在 SortedDictionary 中是同一键。

var sorted = new SortedDictionary<string, 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风格访问或自定义排序时考虑。若构建一次、查询/枚举很多，SortedList<TKey,TValue>或排序数组可能有更好局部性；写入 O(n) 与读取布局之间权衡。

五、Hashtable：object 边界与开放寻址遗产

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 与 null

Hashtable 支持兼容的非泛型相等比较器/历史 comparer 入口。key 不允许 null，value 可为 null；索引器返回 null 无法单独区分“缺失键”和“存在 null value”，应用要 ContainsKey。

迁移旧表必须保存字符串大小写/文化 comparer，不是简单 Cast 到 Dictionary。旧IHashCodeProvider/IComparer组合也可能有特别语义。

5.4 同步包装

Hashtable.Synchronized只让单方法通过 SyncRoot 协调，不让 Contains+Add 成事务；枚举需按文档锁住整个过程。迁到普通 Dictionary 会丢同步，迁 ConcurrentDictionary 又会改变委托/枚举语义，应显式设计。

Hashtable 合理存在于旧 API/二进制/序列化边界；新核心代码一般封装后向泛型迁移，但“不使用”不是删除兼容合同的授权。

六、.NET 9 泛型 OrderedDictionary：key 与 index 双访问

6.1 它维护位置，不做键排序

var ordered = new OrderedDictionary<string, 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 唯一性仍由IEqualityComparer<TKey>/哈希定义，不是顺序 comparer。键入表后不可改变哈希/相等字段。顺序变化不改变 key 身份。

6.4 与非泛型 OrderedDictionary 区分

System.Collections.Specialized.OrderedDictionary使用 object key/value，有装箱/运行时类型边界和自己的 API；泛型类型位于现代集合命名空间/程序集（按 .NET 9 reference确认）。二者序列化、接口和线程语义不能互换。

七、比较器是映射的身份规则

字符串常见选择：Ordinal 适合协议/机器 ID，OrdinalIgnoreCase 适合明确不区分大小写的机器键，文化比较适合面向人的排序但需固定 culture/规则。默认不是错误，关键是写清领域身份。

不要用当前进程GetHashCode作为持久化 ID；字符串哈希可能随机化，算法随 runtime 变。排序 comparer 的结果也可能随文化数据升级而变化，稳定存档/签名要定义规范化与版本。

可变 key 是四种结构共同风险：Hashtable/哈希表可能找错桶，树可能沿错方向。使用 immutable record/readonly struct、稳定 ID，或 Remove旧键后再 Add新键。

比较器本身可能是性能主因。复杂 Unicode 规范化、数据库访问或分配都比结构导航昂贵；比较器应纯、快速，并在插入前预规范化适当数据。

八、容量、分配与 GC

8.1 组成式成本

Dictionary ≈ object + bucket array + Entry array + key/value对象（若引用） SortedDictionary ≈ object + count * Node + key/value对象 Hashtable ≈ object + Bucket array（object key/value）+ 装箱/目标对象 OrderedDictionary ≈ object + 顺序项存储 + key索引存储 + 目标对象

不写固定字节：对象头、引用宽度、T 大小、对齐、runtime 均变化。SortedDictionary 节点多，GC 图更碎；数组式结构扩容产生大数组峰值；OrderedDictionary 为双访问保留两套索引信息；Hashtable 值类型盒对象增加对象数。

8.2 Ensure/Trim

Dictionary/OrderedDictionary 的 capacity API 随版本；预分配能减少 Resize，但过估提高常驻。Trim 是 O(n)/可能分配重建，之后增长会震荡。SortedDictionary 无连续 capacity，Clear 后节点等待 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 也不解决跨调用事务。

十一、失败场景

1. 用 Dictionary 当前枚举顺序做存档/网络协议。
2. 把 SortedDictionary 的“有序”理解为插入顺序。
3. 把 OrderedDictionary 的“有序”理解为按 key 比较排序。
4. 宣称 OrderedDictionary 所有增删 O(1)，忽略位置移动/重索引。
5. 把 Hashtable 画成 Dictionary Entry 冲突链。
6. 删除开放寻址槽时清成空，截断碰撞探测。
7. 迁 Hashtable 忽略旧 comparer/null value/同步包装。
8. 用可变对象做 key，入表后改变哈希/比较字段。
9. comparer 认为相等但 hash 不同，或排序不传递。
10. 先 ContainsKey 再索引器重复查找且暴露并发窗口。
11. Clear 后断言后备容量已归还。
12. 枚举中修改，或把 version 检测当线程锁。
13. 用 ConcurrentDictionary 替换有序结构并假设顺序仍在。
14. Unity 项目照抄.NET 9OrderedDictionary 而未检查 API profile。
15. 依据固定倍数/推荐星级选择，不测键和操作分布。

十二、Unity、Mono 与 IL2CPP

Unity 2022.3 的 API Compatibility Level 不等于.NET 8/9reference assembly。泛型.NET 9 OrderedDictionary<TKey,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 留在适配边界，逐步迁移

然后修正：

1. 多线程写？加入完整同步/ConcurrentDictionary/快照架构。
2. 每键多值？四者都不是自动 multi-map，value 用列表/集合并定义所有权。
3. 读多写少且构建后固定？考虑 FrozenDictionary/ImmutableDictionary（目标版本支持时）。
4. key 排序只在偶尔输出需要？Dictionary + 输出时排序可能比持续维护树更合适。
5. 位置中间插删频繁且规模大？OrderedDictionary O(n) 搬移可能不合适，考虑链+索引/专用结构并承担对象成本。
6. Unity Job？转 Native/ECS 域，不在四个托管类型中硬选。

十四、迁移案例

14.1 Hashtable 到 Dictionary

先扫描实际 key/value 类型、null value、字符串大小写/文化、重复冲突和同步调用。用显式循环校验并迁移，遇到 comparer 合并冲突由业务规则处理，不用枚举后项静默覆盖。历史序列化保留适配 DTO，不直接改字段类型后期待旧文件可读。

14.2 Dictionary + List 双结构到 OrderedDictionary

原实现若Dictionary<TKey,Item>+List<TKey>，先写不变量：每个 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、RemoveAt；SortedDictionary测随机/有序 key 插删；Dictionary/Hashtable测 Resize和墓碑/删除重插。参数化 n，寻找成本曲线。

15.4 内存与 GC

T 取 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结果外推。

十六、审查清单

1. 业务说的“有序”是按键、按位置还是仅想确定输出？
2. 当前类型/目标 TFM 真正提供哪些 API？
3. key 的 equals/hash 或 compare 是否稳定、一致、可测试？
4. null key/value 与缺失键怎样区分？
5. 重复键是拒绝、覆盖、合并还是多值？
6. 复杂度是否包含查找、移动、Resize、comparer和用户回调？
7. 是否依赖偶然枚举顺序或内部地址？
8. Capacity 是否有依据，Trim后会不会马上增长？
9. 可变 value 内部是否另有线程安全/深快照要求？
10. 复合操作是否由一把锁/单写者事务保护？
11. 旧 Hashtable 的 comparer、同步和序列化契约是否保存？
12. Unity Mono/IL2CPP/Native域是否分别验证？
13. 性能报告是否包含代码、版本、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、同输入的曲线实验验证。这样不会因一次枚举顺序或一张固定倍率表，选中契约错误的结构。

下一篇：Stack：LIFO 的数组实现