04-06-哈希-OrderedDictionary-TKey-TValue-NET9有序键值映射

OrderedDictionary<TKey,TValue>：.NET 9 的有序键值映射

系列：C# 与常用数据结构源码剖析 · 哈希与映射篇
版本边界：.NET 9 GA 公共 API；私有实现固定为 dotnet/runtime v9.0.0 / 9d5a6a9a... 的 OrderedDictionary.cs
核心语义：按键唯一映射，同时保留可按整数位置观察和修改的顺序

一、“有序”是位置顺序，不是按键排序

System.Collections.Generic.OrderedDictionary<TKey,TValue>在 .NET 9 成为泛型 BCL 类型。它结合两套访问语义：用 key 查 value，也用整数 index 访问/插入/移除某个位置。枚举遵循当前位置顺序。

var map = new OrderedDictionary<string, int>(); map.Add("z", 1); map.Add("a", 2); map.Add("m", 3); foreach (KeyValuePair<string, int> pair in map) Console.WriteLine(pair.Key); // z, a, m

这不是SortedDictionary<TKey,TValue>：后者按IComparer<TKey>的键序维护平衡搜索树；OrderedDictionary的 comparer只决定键是否相等、哈希如何计算，不决定位置。调用者可以把项插入任意index，或显式改变顺序；“插入顺序”只是不断尾部Add且不重排时的结果。

它也不同于System.Collections.Specialized.OrderedDictionary：后者是较早的非泛型类型，namespace、API、序列化与实现边界均不同。迁移不能只替换 using。

本文只依赖 .NET 9公开契约。下面对架构的描述来自v9.0.0源码的结构化总结；字段名/布局、容量算法和helper不是ABI。所有算法代码均标为伪代码，不冒充runtime逐字源码。

二、双重不变量：顺序存储与键索引必须一致

OrderedDictionary必须同时保持：

1. 0 <= index < Count的每个位置恰好有一个键值对；
2. 顺序存储中的key按 equality comparer互不重复；
3. 按key查找能定位到该项当前index；
4. 插入/删除/移动导致index变化后，键索引同步更新；
5. 枚举、Keys和Values按相同位置顺序观察；
6. 失败操作不能留下“列表已改、索引未改”的半状态。

v9.0.0实现可从“有序 entry存储 + hash buckets/index”角度理解，而不是原文声称的“Dictionary双数组 + 双向链表 + 独立index数组”三结构。项目不能依赖具体Entry字段，但理解这种映射很重要：按位置访问适合连续存储，按键查找需要哈希索引；位置变化会要求修正索引信息。

位置存储（枚举/整数索引） index 0 1 2 entry [z, 1] [a, 2] [m, 3] ^ ^ ^ +------ hash buckets/chains按key定位到当前位置

当在index 1插入[b,4]，后缀a/m向后移动，哈希结构中指向其位置的信息必须随之修正：

before: [z][a][m] insert: [b] after: [z][b][a][m]

这解释了为何键查找与位置读取可以快，而中部插入/移除要支付线性移动/修正成本。具体实现可能通过压缩字段、重建buckets或局部更新优化，复杂度边界不因此消失。

三、公共 API 的两套索引器要读清类型

OrderedDictionary 的公开索引器map[key]按 key 访问 value；按位置的公开入口是GetAt、SetAt、Insert与RemoveAt。它还显式实现IList<KeyValuePair<TKey,TValue>>/IReadOnlyList<KeyValuePair<TKey,TValue>>的整数索引器，但普通的具体类型变量不会用map[index]表达位置读取。若TKey本身是int，map[0]仍是按整数 key 查 value，这个区别尤其重要。

var names = new OrderedDictionary<string, string> { ["p1"] = "Ada", ["p2"] = "Lin" }; string byKey = names["p1"]; KeyValuePair<string, string> first = names.GetAt(0);

.NET 9 GA 提供GetAt(index)、两个SetAt重载、IndexOf(key)、Insert与RemoveAt等位置 API。整数索引器只在显式列表接口视图中暴露，通常直接使用具名方法更不易混淆。本文已用 SDK 9.0.317 的net9.0reference assembly 和最小工程编译核验；其他 SDK patch 仍应在 CI 复测。

键索引器赋值通常表达“key存在则更新value，不存在则按契约加入”；它不应在更新已有value时偷偷改变位置。位置式Set若允许替换key，则必须检查新key唯一性并更新hash索引。调用者应写测试固定自己依赖的顺序语义。

四、Add 与按位置 Insert

尾部Add的逻辑可抽象为：验证key、查重、确保容量、把entry写到Count位置、把key纳入hash索引、增加Count/version。

// 算法伪代码，不是 .NET 9源码。 void Add(TKey key, TValue value) { ValidateKey(key); if (FindIndex(key) >= 0) ThrowDuplicateKey(); EnsureCapacityForOneMore(); entries[count] = new Entry(key, value, hashInfo); LinkHashIndex(count); count++; version++; }

若容量充足且hash分布正常，尾部Add常见为摊销O(1)；扩容会分配/复制并重建索引。不能把平均哈希查找写成无条件O(1)，恶劣comparer/冲突可退化。

按位置Insert除了查重，还要移动[index..Count)后缀，并让hash索引反映新位置，因此O(n)。插入末尾接近Add路径；插入头部移动最多。它的价值是保持业务顺序，不是高频队头队列。

var pipeline = new OrderedDictionary<string, Handler>(); pipeline.Add("parse", Parse); pipeline.Add("store", Store); pipeline.Insert(1, "validate", Validate); // 顺序：parse, validate, store

具体Insert重载以net9.0编译核验；示例表达公共意图。

五、查找、更新与 comparer

ContainsKey、TryGetValue和key索引器通过IEqualityComparer<TKey>计算hash并比较候选。平均成本接近Dictionary的哈希查找，但不能因此说内部“与Dictionary同源”或性能相同。

var headers = new OrderedDictionary<string, string>( StringComparer.OrdinalIgnoreCase); headers.Add("Content-Type", "application/json"); Console.WriteLine(headers.ContainsKey("content-type")); // true

comparer定义键身份。若Equals(x,y)为true，hash必须相同；结果在key驻留期间保持稳定。忽略大小写意味着两种拼写不能并存，但保留哪一个原始key要看是Add、value更新还是位置替换，必须按API测试。

5.1 可变键陷阱

sealed class MutableKey { public string Id { get; set; } = ""; public override bool Equals(object? obj) => obj is MutableKey other && Id == other.Id; public override int GetHashCode() => Id.GetHashCode(); }

插入后修改Id，会让entry仍位于按旧hash建立的索引中，Contains/Remove可能找不到。顺序数组仍能枚举该对象，形成“看得见却按key找不到”的症状。使用不可变key，或Remove旧key再Add/Insert新key。

自定义comparer不应依赖当前文化/时间/外部可变配置。技术标识符通常选择显式Ordinal规则。昂贵comparer成本会乘以冲突比较次数；性能实验必须记录它。

六、Remove 与 RemoveAt：位置变化是主成本

按key Remove先哈希定位index，再移除位置；RemoveAt已知位置无需key查找。但两者都要移动后缀并修正hash索引，所以中部删除为O(n)。尾部删除移动较少，仍需移除hash链和清理槽位。

remove index 1: [z][a][m][q] X [z][m][q] <- m/q位置改变，hash索引同步

引用类型key/value被移除后，实现需要清空不再有效槽位，避免后备数组继续保持对象可达；含引用的struct也需处理。Clear移除全部逻辑项和引用，但通常可能保留容量以便复用，准确行为按.NET 9实现/API核验。

如果业务频繁从头部取项，OrderedDictionary不是Queue/LinkedList替代品；O(n)移动会成为风险。若需要按key删除且保持顺序，但无需整数随机访问，其他组合结构可能更合适，但也会增加节点和一致性成本。

七、顺序重排与索引写入

.NET 9 OrderedDictionary提供的位置API允许按index读取/写入，具体是否有显式Move取决于GA API。即便没有单步Move，也可通过RemoveAt+Insert表达，但会做两次结构修改并使枚举器失效；异常中间状态和key/value保存需处理。

// 业务伪代码：先保存项，再删除并插入；方法名按实际API调整。 static void Move<TKey, TValue>( OrderedDictionary<TKey, TValue> map, int from, int to) where TKey : notnull { KeyValuePair<TKey, TValue> item = map.GetAt(from); map.RemoveAt(from); if (to > from) to--; // 删除后索引收缩 map.Insert(to, item.Key, item.Value); }

若Insert失败（例如并发修改或参数错误），项已被删除。生产实现先校验所有边界，在普通集合外加锁，并考虑回滚；更可靠的是在副本上修改后原子替换快照。OrderedDictionary本身不保证多线程复合操作原子。

八、版本化枚举与并发边界

枚举器通常捕获集合version。Add、Insert、Remove、Clear、位置替换/重排等结构修改会改变version，后续MoveNext按契约/实现抛InvalidOperationException。value更新是否使枚举失效必须以.NET9 API测试，不能从Dictionary旧经验推断。

foreach (var pair in map) { // map.Remove(pair.Key); // 不在同一枚举中修改 Consume(pair); }

fail-fast是错误检测，不是线程同步。一个线程枚举、另一个写入仍是数据竞争；异常不是一致快照保证。需要并发读写时：lock覆盖完整操作；写者构建新集合并发布只读快照；或选择语义适合的并发结构。没有标准ConcurrentOrderedDictionary可直接假定替代。

Keys/Values视图通常关联源集合而非独立快照，顺序与version行为按契约核验。需要稳定迭代时显式ToArray并接受分配。

九、容量、扩容与 GC

构造容量/EnsureCapacity/TrimExcess等API是否存在及语义以net9.0 reference assembly为准。预知项数时容量提示可减少entry/bucket重分配；高估会增加驻留内存。具体增长倍数、初始数组、阈值与hash重建属于v9.0.0私有实现，不写进业务逻辑。

扩容可能同时分配顺序entry存储和hash索引，旧数组变成垃圾；大数组是否进入LOH由实际字节布局和runtime决定，不用固定元素数猜测。TKey/TValue为大struct时entry复制更重；包含引用时GC扫描对应引用槽。

Clear后容量可能保留；TrimExcess缩容可能分配/复制，之后增长再扩容。对象池中一个偶发巨型OrderedDictionary可能长期保留峰值容量，应设置淘汰阈值或丢弃实例。池化还需Clear防止key/value陈旧引用，并保证单一租用者。

不能写固定“每entry增加多少字节”。内存由私有Entry布局、bucket类型、对齐、引用大小、容量余量、TKey/TValue和runtime决定。用MemoryDiagnoser/heap snapshot测目标实例。

十、复杂度表及适用前提

这些是算法边界，不是延迟数字。小n连续移动可能比节点结构快；大n头部频繁更新则可能差。CPU缓存、comparer、元素大小和扩容决定常数项。

适合：需按key快速查找，又需稳定业务位置/展示顺序；读多、尾部Add多、中部编辑相对少；配置、命令管线、UI模型等。若只要插入顺序枚举而不需要整数index，应先核实Dictionary当前契约是否已满足，但不要依赖未承诺顺序。若按key排序，使用SortedDictionary/SortedList；若FIFO用Queue；若最高优先级用PriorityQueue。

十一、配置与 UI 案例

配置编辑器需要保持用户排列，同时按ID定位：

public sealed record Setting(string Id, string Value); var settings = new OrderedDictionary<string, Setting>( StringComparer.Ordinal); settings.Add("graphics.quality", new("graphics.quality", "high")); settings.Add("audio.volume", new("audio.volume", "80"));

若Setting.Id与字典key重复保存，两者可能不一致。可以让value不重复Id，或封装Add/Replace验证。持久化只保存有序键值列表，不序列化私有buckets/capacity；加载时逐项检查重复，并定义“首个胜出、最后胜出还是报错”。

UI列表重排时，OrderedDictionary不是INotifyCollectionChanged。数据结构改变不会自动通知WPF/MAUI/Unity UI；需要ViewModel发布Move/Reset或替换快照。不要在绘制回调中高频RemoveAt+Insert而未profile。

十二、Unity 可用性与替代方案

Unity项目通常不以.NET 9为目标，Unity 2022/2023/Unity 6的BCL/API Compatibility和Mono/IL2CPP不能假定包含泛型OrderedDictionary。即使安装某个包/复制源码能编译，还要确认许可证、AOT泛型、裁剪、序列化和目标平台。

Unity内置序列化也不保证支持该泛型类型或保留顺序/字典内容。常见做法是序列化List<EntryDto>，OnAfterDeserialize时重建Dictionary索引；或维护List+Dictionary的领域容器并完整封装不变量。

[Serializable] public struct EntryDto { public string key; public string value; }

重建时检查null/重复key，编辑器OnValidate保持一致。List+Dictionary中部移动后必须更新索引，不能只移动List。IL2CPP Player做正确性、分配和帧时间测试；桌面.NET9基准不能外推Unity。

十三、失败反例

反例一：把Ordered当Sorted

期望key字母序，实际是位置顺序。使用SortedDictionary/排序快照。

反例二：高频RemoveAt(0)当队列

每次移动后缀。使用Queue/Deque语义结构。

反例三：修改可变key字段

枚举看得到，按key找不到。使用不可变key并Remove+Insert。

反例四：foreach内重排

version失效并抛异常。先收集变更，枚举后应用或操作副本。

反例五：用int key时混淆key/index重载

读错项或调用错误 API。使用GetAt/SetAt等明确的位置 API，并测试负索引、等于 Count 和移动后的边界。

反例六：Clear后认为内存归零

容量可能保留，工作集不会立即下降。按稳定负载决定复用/Trim/丢弃。

反例七：复制私有字段做存档

升级runtime即破坏。只序列化逻辑有序键值。

反例八：认为.NET9类型可直接用于Unity

目标BCL可能没有，序列化/IL2CPP也未验证。使用项目兼容实现并Player测试。

十四、可复现实验

建立net9.0BenchmarkDotNet项目，固定.NET 9 patch、runtime commit、CPU/OS、Release、GC、TKey/TValue与comparer。工作负载分开：尾部Add；头/中/尾Insert；key命中/未命中；头/随机/尾Remove；GetAt位置读取；全量枚举；Clear复用；初始容量与自然增长。

[MemoryDiagnoser] public class OrderedMapBenchmarks { [Params(32, 4096)] public int N { get; set; } private OrderedDictionary<int, int> _map = null!; [IterationSetup] public void Setup() { _map = new OrderedDictionary<int, int>(N + 1); for (int i = 0; i < N; i++) _map.Add(i, i * 2); } [Benchmark] public int KeyLookups() { int sum = 0; for (int i = 0; i < N; i++) if (_map.TryGetValue(i, out int value)) sum += value; return sum; } [Benchmark] public void InsertMiddle() => _map.Insert(N / 2, -1, -2); }

构造签名/Insert签名须按.NET9 GA实际编译调整。IterationSetup成本不计入Benchmark但会影响GC状态，应另测端到端构建并审查框架配置。每个用例验证Count、顺序、key唯一和checksum，避免测到错误实现。

与Dictionary/SortedDictionary/SortedList对照时只比较共同语义：若Dictionary不提供index，就不能把缺少工作当更快。内存用MemoryDiagnoser+heap snapshot，源码机制用固定v9.0.0 tag，不提供无环境倍数。

十五、审查清单与结论

• 项目确实目标net9.0，GA API签名已由reference assembly核验；
• “有序”定义为当前位置，不是key排序；
• key comparer等价类符合领域身份，key驻留期间不可变；
• integer key与integer index调用无歧义；
• 中部Insert/Remove的O(n)成本符合更新分布；
• value更新、key替换和重排后的顺序有测试；
• 枚举期间不修改，跨线程有锁/快照协议；
• 初始容量、Clear、Trim和池化按GC/峰值实测；
• 序列化只保存逻辑顺序，不保存私有实现；
• Unity未假定拥有.NET9 BCL，Mono/IL2CPP Player已验证；
• 私有架构结论标注v9.0.0 tag，实验保存环境和原始报告。

OrderedDictionary的价值是把两套常见需求收进一个公共类型：key提供哈希映射，index提供业务顺序。代价也由双重不变量直接导出：中部位置变化会移动entry并修正hash索引，枚举与视图必须跟随version，容量同时影响顺序存储和索引内存。

不要把它描述为哈希表、双向链表、索引数组的固定三件套，也不要宣称删除均摊O(1)或每项固定字节。依赖公共顺序/映射契约，按v9.0.0源码解释当前实现，再用真实更新分布和目标平台实验决定是否适合。

下一篇：哈希结构综合对比