Python dict 的底层原理是什么？哈希冲突时怎么处理？

简化版

Python 的 dict 底层是哈希表，通过 key 的哈希值快速定位存储位置，平均查找、插入、删除复杂度接近 O(1)。发生哈希冲突时，CPython 使用开放寻址和探测序列继续寻找可用位置，而不是每个桶挂链表。

详细版

dict 的核心思路是：先用 hash(key) 得到哈希值，再把哈希值映射到内部表的某个槽位。如果槽位为空，就直接放入；如果槽位已有元素，就比较哈希值和 key 是否相等；如果不是同一个 key，就按探测规则寻找下一个候选槽位。

Python 要求字典 key 必须可哈希，原因是 key 的哈希值要在字典生命周期内保持稳定。不可变类型如 str、int、tuple 通常可以做 key；list、dict、set 这类可变对象不能做 key，因为内容变化会导致哈希定位失效。

从 Python 3.7 开始，字典的插入顺序成为语言保证。这个“有序”不代表底层是链表或排序树，而是 CPython 的紧凑字典结构把索引表和条目数组分开，让遍历可以按插入条目的顺序进行，同时仍保持哈希查找。

面试回答时要强调三点：dict 是哈希表；冲突靠开放寻址探测；平均 O(1) 依赖哈希分布和扩容，极端冲突下会退化。

完整版教学

一、dict 为什么能做到平均 O(1)

如果用普通列表保存键值对，查找一个 key 需要从头扫到尾。10 个元素还好，100 万个元素就会变成明显的线性成本。哈希表的想法是先把 key 转成一个整数哈希值，再用这个整数直接计算候选位置，这样大多数情况下不用逐个比较。

看一个简化模型：内部表容量是 8，某个 key 的哈希值是 45，那么可以先用 45 & (8 - 1) 得到槽位 5。真实 CPython 比这个模型复杂，但“哈希值映射到槽位”的思路一致。

hash("name") = 45
capacity = 8
index = 45 & 7 = 5

槽位: 0 1 2 3 4 5 6 7
内容: . . . . . name .

这里的 O(1) 是平均意义：一次定位通常就能找到候选槽位，少量冲突再探测几次。它不是数学上永远只比较一次；哈希分布差、装载因子太高、恶意构造冲突时，探测次数会增加。

二、key 为什么必须可哈希

字典查找依赖两个条件：key 有稳定的哈希值，且相等对象的哈希值必须相等。如果一个对象作为 key 放进字典后内容又变了，它原来的槽位就可能再也找不回来了。Python 因此直接禁止常见可变容器作为 key。

d = {}
d[[1, 2]] = "bad"      # TypeError: unhashable type: 'list'
d[(1, 2)] = "ok"       # tuple 内容不可变，可以作为 key

更细一点，tuple 只有在所有元素都可哈希时才可哈希。(1, 2) 可以做 key，([1], 2) 不行，因为里面嵌了一个可变列表。

对象	能否做 dict key	原因
`int` / `str`	可以	值不可变，哈希稳定
`tuple`	视元素而定	所有元素可哈希才行
`list`	不可以	内容可变，哈希不稳定
自定义对象	视实现而定	取决于 `__eq__`、`__hash__`

记 key 的规则不要背“不可变就行”这么粗：真正要求是“可哈希且哈希稳定”，不可变只是最常见的实现方式。

三、哈希冲突是怎么来的

哈希值空间很大，但内部表槽位数量有限，所以不同 key 落到同一个槽位是必然可能发生的。比如表容量是 8，哈希值 5、13、21 都会映射到索引 5，因为它们的低 3 位相同。

5  & 7 = 5
13 & 7 = 5
21 & 7 = 5

哈希冲突不代表两个 key 相等，只代表它们第一落点相同。字典必须继续比较：如果哈希值相同且 key 相等，就是更新已有值；如果不是同一个 key，就要找下一个槽位。

这个过程解释了为什么自定义对象实现 __eq__ 时要小心 __hash__。如果两个对象相等但哈希值不同，字典可能把它们放在不同位置，破坏“相等 key 对应同一个值”的基本语义。

四、开放寻址和链地址法有什么区别

解决冲突有两大经典路线：链地址法是在槽位后面挂链表或其他结构；开放寻址法是在同一个数组里继续探测其他槽位。CPython 的 dict 采用开放寻址思路，因此冲突元素仍然保存在表结构内部。

方案	冲突处理	优点	代价
链地址法	槽位挂链表/树	删除直观，负载可较高	指针多，缓存局部性较差
开放寻址	按探测序列找别的槽位	内存紧凑，缓存友好	删除和高负载处理更复杂

用数字感受一下：容量 8 的表里，如果索引 5 已经有 "name"，另一个 key 也落到 5，开放寻址会按探测序列找 2、3、0 之类的后续位置。真实探测序列不是简单 +1，这样能减少连续聚集。

第一次落点: 5，被占用
探测候选: 2 -> 3 -> 0 ...

槽位: 0 1 2 3 4 5 6 7
内容: . . age . . name . .

五、为什么 dict 需要扩容

开放寻址最怕表太满。空槽越少，冲突后探测越长，查找速度就会从“很快定位”变成“到处找空位”。所以字典会在装载因子升高后扩容，把元素重新分布到更大的表里。

假设容量 8 的表已经放了 5 个元素，再插入时很容易遇到冲突；扩到 16 后，同样的 key 会根据新掩码映射到更分散的位置。扩容本身要搬迁或重建索引，单次插入可能较贵，但摊还到多次插入后，平均成本仍接近 O(1)。

扩容前: capacity = 8,  used = 5,  冲突概率升高
扩容后: capacity = 16, used = 5,  空槽变多，探测变短

这也是为什么大量插入字典时，偶尔某一次插入会比平时慢。面试里可以说：字典操作平均 O(1)，但扩容、冲突和哈希计算都会影响实际耗时。

六、插入顺序是怎么保证的

Python 3.7 起，dict 保持插入顺序是语言层面的保证。它不是每次遍历都排序，也不是依靠 OrderedDict 的双向链表语义来完成。CPython 的紧凑字典把稀疏索引和紧凑条目分开，条目数组按插入顺序保存键值。

简化理解如下：

索引表:  [空, 2, 空, 0, 空, 1]
条目表:  0: ("a", 1)
        1: ("b", 2)
        2: ("c", 3)

遍历条目表 -> a, b, c
查找走索引表 -> hash(key) -> entry index

这样既保留哈希查找，也让遍历顺序稳定。删除后再插入同一个 key，一般会按新的插入位置体现；更新已有 key 的值不会改变原来的插入顺序。

七、常见误区与追问

误区：Python dict 有序，所以底层是有序数组或树。 有序指保留插入顺序，查找仍然依赖哈希表，不是按 key 排序。
误区：哈希冲突说明两个 key 相等。 冲突只是槽位相同；是否相等还要比较哈希和 __eq__。
误区：dict 操作永远是 O(1)。 平均接近 O(1)，但扩容、冲突、恶意哈希输入都会让单次操作变慢。
追问：为什么 list 不能做 key？ list 内容可变，作为 key 后如果内容变化，哈希定位会失效，所以 Python 不允许它可哈希。
追问：自定义类重写 __eq__ 后为什么常常不能哈希？ Python 会把 __hash__ 置为 None，避免相等语义变了但哈希语义没跟上。
追问：dict 和 OrderedDict 还有区别吗？ 普通 dict 保序已够多数场景；OrderedDict 仍有移动顺序、顺序敏感相等性等额外语义。
追问：为什么字符串 key 的 dict 很快？ 字符串不可变、哈希可缓存，且实际业务中字符串哈希分布通常较好。

八、加强记忆

把 dict 记成“哈希定位 + 冲突探测 + 适时扩容 + 插入保序”。查找时先算 hash，再映射槽位；槽位撞了就开放寻址继续找；表太满就扩容减少探测长度；遍历顺序来自紧凑条目表的插入顺序。回答面试题时不要只背 O(1)，要补一句“平均 O(1)，依赖哈希分布和装载因子，极端冲突会退化”，这句话能把底层理解和复杂度边界一起交代清楚。

简化版

详细版