Dictionary查找平均O(1)因采用开放寻址+线性探测哈希表，键值对存于连续数组，通过GetHashCode取模定位后线性探测，负载因子超0.75自动扩容。
Dictionary 查找为什么是 O(1) 平均时间复杂度
因为底层用的是开放寻址法（Open Addressing）+ 线性探测（Linear Probing）的哈希表，不是链地址法（chaining）。这意味着所有键值对都存放在一个连续的 Entry[] 数组里，没有额外的链表或子数组开销。
每次 TryGetValue 或 this[key] 时，先算 key.GetHashCode()，再通过位运算取模定位初始桶（bucket），如果位置被占且 key 不匹配，就顺序往后探测——直到遇到空槽、或回到起点（说明不存在）。
- 哈希冲突不导致内存分配，但会增加探测步数；负载因子（
Count / buckets.Length）超过 0.75 时自动扩容，重建整个数组 -
GetHashCode()返回值必须稳定：对象用作 key 期间，只要还在字典中，就不能改变影响哈希值的字段 - 自定义类型作 key 时，必须重写
GetHashCode()和Equals()，否则默认引用比较，查找必然失败
和 Hashtable、ConcurrentDictionary 的关键区别在哪
Dictionary 是非线程安全、泛型、数组驱动的哈希表；Hashtable 是非泛型、装箱/拆箱严重、内部用 bucket[] + link[] 模拟链地址法；ConcurrentDictionary 则分段加锁 + 多种策略混合（部分桶用链表，部分用跳表），牺牲平均性能换并发安全。
- 单线程场景下，
Dictionary比Hashtable快 2–3 倍，主要省在避免装箱和更紧凑的内存布局 -
ConcurrentDictionary的TryGetValue虽然也接近 O(1)，但有额外的 volatile 读和段锁判断，微基准测试里慢约 30%–50% - 不要为了“看起来线程安全”而滥用
ConcurrentDictionary：若只读多写少，用ReaderWriterLockSlim+ 普通Dictionary可能更高效
哪些操作会意外触发 O(n) 行为
表面上所有查找都是 O(1)，但实际受哈希分布、内存局部性、GC 压力影响。真正掉出常数级的典型情况包括：
- 大量哈希碰撞：比如用字符串做 key 且都以相同前缀开头，
String.GetHashCode()在旧 .NET Framework 中易发生聚集（.NET Core+ 已改进，但仍可能） - 频繁 Add/Remove 导致反复扩容缩容：每次扩容要重新哈希全部元素，
Dictionary不支持 shrink-to-fit，删完 90% 元素后仍占原容量 - value 类型过大（如
Dictionary）：Entry 数组里存的是结构体副本，复制成本随 value size 线性增长
怎么验证你正在用的确实是 Dictionary 的原生行为
别只看文档，直接查 Dictionary 的反编译代码或官方源码（github.com/dotnet/runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs）。你会发现核心逻辑就是循环探测 entries[i].hashCode == hash && EqualityComparer。
- 用
dotnet trace抓 GC 和内存分配，确认没意外装箱（比如误把int当object存进非泛型集合） - 用
Unsafe.SizeOf看 Entry 结构大小，.NET 6+ 是 12 字节（int hashCode + int next + TKey key + TValue value），能估算缓存行利用率.Entry>() - 如果发现查找延迟毛刺明显，优先检查
GetHashCode()实现是否退化（如始终返回 0）、或是否在循环中反复 new 同一个 Dictionary
哈希函数质量、负载因子控制、内存访问模式——这三者共同决定实际性能，光记住“O(1)”容易在真实服务里栽跟头。
