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<int byte></int>）：Entry 数组里存的是结构体副本，复制成本随 value size 线性增长
怎么验证你正在用的确实是 Dictionary 的原生行为
别只看文档，直接查
Dictionary<tkey tvalue>.FindEntry</tkey>的反编译代码或官方源码（github.com/dotnet/runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs）。你会发现核心逻辑就是循环探测
entries[i].hashCode == hash && EqualityComparer<tkey>.Default.Equals(entries[i].key, key)</tkey>。 用
dotnet trace抓 GC 和内存分配，确认没意外装箱（比如误把
int当
object存进非泛型集合） 用
Unsafe.SizeOf<dictionary>.Entry>()</dictionary>看 Entry 结构大小，.NET 6+ 是 12 字节（int hashCode + int next + TKey key + TValue value），能估算缓存行利用率 如果发现查找延迟毛刺明显，优先检查
GetHashCode()实现是否退化（如始终返回 0）、或是否在循环中反复 new 同一个 Dictionary
哈希函数质量、负载因子控制、内存访问模式——这三者共同决定实际性能，光记住“O(1)”容易在真实服务里栽跟头。
