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)
• 低因子保障了探测步数少，绝大多数查找一步到位，极少数最多几跳

所以，字典快不是因为“哈希函数无敌”，而是哈希计算快 + 掩码定位快 + 冲突探测路径短 + 扩容机制兜底。