Python字典查找平均时间复杂度为O(1)，依赖哈希表结构：键经hash()计算哈希值，用位运算掩码映射下标，开放寻址法处理冲突，并通过装填因子触发扩容保障效率。
Python字典（dict）的查找平均时间复杂度是 O(1)，核心依赖于哈希表（hash table）结构，而非“哈希算法本身有多快”，关键在于哈希值如何被计算、映射、处理冲突。
哈希值怎么算？不是直接用对象内存地址
Python 对每个键调用 hash() 得到一个整数哈希值。这个值不是简单取内存地址，而是根据对象类型有专门逻辑：
- 整数：哈希值就是它自己（如
hash(42) == 42） - 字符串：通过一种确定性算法（如 SipHash 的变种）计算，相同字符串一定得相同哈希值
- 元组：递归哈希其元素（要求所有元素都可哈希）
- 自定义类：默认用
id()，但可重写__hash__和__eq__来支持字典键
⚠️ 注意：不可变对象才可哈希；列表、字典等可变类型不能做键，因为哈希值需稳定不变。
哈希值怎么映射到数组下标？用掩码替代取模
字典底层维护一个动态扩容的“桶数组”（buckets），长度始终是 2 的幂（如 8、16、32…）。Python 不用 hash % len(buckets)，而是用位运算：
立即学习“Python免费学习笔记（深入）”；
- 假设数组长为 16（二进制
10000），则掩码是15（01111） - 实际下标 =
hash & mask（比如hash=137 → 137 & 15 = 9） - 这比取模快，且保证结果落在
[0, len-1]范围内
冲突怎么处理？开放寻址 + 伪随机探测
不同键可能算出相同哈希值（哈希冲突），Python 字典不用链地址法（不拉链），而是用开放寻址法（open addressing）：
- 每个桶只存一个键值对（或空/已删除标记）
- 若目标位置被占，就按固定规则“试探下一个位置”——不是线性+1，而是用伪随机序列（基于哈希值二次扰动）
- 插入时找第一个空位；查找时顺着同一序列比对，直到遇到空桶才确认“键不存在”
- 删除键时不会真清空桶，而是打上
DELETED标记，避免打断后续查找链
为什么平均查找还是 O(1)？靠装填因子控制扩容
效率不崩的关键是限制“桶有多满”：
- 装填因子 = 已存键数 / 桶总数
- 当因子超过约
2/3（如 66%），字典自动扩容（通常是翻倍），并重新哈希所有键 - 扩容代价是 O(n)，但均摊下来每次插入仍是 O(1)
- 低因子保障了探测步数少，绝大多数查找一步到位，极少数最多几跳
所以，字典快不是因为“哈希函数无敌”，而是哈希计算快 + 掩码定位快 + 冲突探测路径短 + 扩容机制兜底。
