Python里的dict(字典)——哈希表

Python 里的  dict （字典）本质就是一个用开放寻址法实现的哈希表，查找、插入、删除平均都是 O(1) 级别。

下面用最清晰、面试常考的方式讲一遍：


1. 底层结构

- 本质是一个伪随机探测的哈希表
- 底层是一个连续的数组（table）
- 每个数组元素叫一个 entry，存三样东西：
  hash ：key 的哈希值
key ：键
value ：值

2. 插入 & 查找原理

（1）计算哈希
对 key 计算  hash(key) ，得到一个整数。

（2）计算下标
用哈希值对数组长度取模，得到初始下标：
index = hash(key) % len(table)

（3）探测（解决冲突）
如果该位置已经被占了（冲突），Python 用开放寻址 + 伪随机探测：

不是简单往后挪一位
​ 而是用固定公式算出下一个候选下标
​ 直到找到空位置（插入）或找到相同 key（覆盖/读取）

（4）比较 key

即使下标命中，也要严格比较 key：
哈希相同 ≠ key 相同
只有  key == 目标key  才算真正命中

3. 扩容机制

- 当数组填充率（负载因子）达到 2/3 时
​
- Python 会自动扩容：新长度一般是原来的 2~4 倍
​
- 重新计算所有 key 的下标，全部重排 → rehash

这就是为什么字典大了之后偶尔会突然慢一下。
 

4. Python 3.7+ 重要特性

Python 3.7 开始，dict 默认记住插入顺序
​
实现方式：
​用一个紧凑数组存所有 entry
​另一个索引表记录顺序
​
——既保留哈希表速度，又实现有序


一句话总结：

Python dict =
哈希函数计算下标 + 开放寻址解决冲突 + 达到负载因子自动扩容 + 3.7后有序