源码阅读：深入理解Python字典的底层实现
目录
一、引言：为什么Python字典这么快？
在Python开发中，我们几乎每天都要和字典打交道。配置信息、数据缓存、对象属性……到处都有它的身影。但你有没有好奇过：为什么字典查找一个键的速度，几乎不受字典大小的影响？
无论是10个键还是1000万个键，my_dict[key]的执行时间几乎是恒定的——这就是O(1)时间复杂度的魅力。这个奇迹的背后，藏着一个叫做哈希表（Hash Table）的数据结构。Python的字典正是哈希表的一个经典实现。
本文将带你一步步深入CPython的源码，从最基础的概念开始，揭秘字典的内部工作原理。
二、哈希表是什么？先搞懂这个，才能懂字典
2.1 从数组到哈希表：一个思考过程
想象你有一个数组（列表），要从中找出某个特定的元素。如果不知道它在哪个位置，你只能挨个检查——这就是O(n)的时间复杂度，在数据量大的时候会非常慢。
现在，如果我们能有一种魔法：给定一个键，就能直接算出它应该存放在数组的哪个位置，那查找不就变成O(1)了吗？
这个魔法就是哈希函数。
2.2 哈希函数：把任意东西变成数字
哈希函数的作用很简单：把任意类型的输入（比如字符串、数字、元组）转换成一个固定范围内的整数。
python
# Python中内置的hash函数
print(hash("hello")) # 比如输出：-1004758382858577792
print(hash(42)) # 输出：42（整数hash就是它本身）
print(hash((1, 2, 3))) # 元组也可以哈希这个整数就是键的"指纹"。有了这个指纹，我们就可以把它映射到数组的某个位置。
2.3 哈希冲突：当两个键指向同一个位置
世界上不存在完美的哈希函数。不同的键有可能算出相同的哈希值，或者虽然哈希值不同，但对数组大小取模后落到了同一个位置。这种情况叫做哈希冲突。
举个例子：假设数组只有8个位置，hash(apple) % 8 = 3，hash(orange) % 8 = 3，那么苹果和橙子就会争夺同一个位置。
怎么解决呢？不同语言有不同策略。Java的HashMap用的是链地址法（每个位置放一个链表），而Python字典用的是开放寻址法（发生冲突就去找下一个空位置）。
开放寻址法的直观理解：想象你在一个停车场找车位。你想停的位置（车位3）已经被占了，你不会掉头离开整个停车场，而是继续往前开，找到下一个空位停下。这就是开放寻址——冲突了没关系，继续往下找。
三、走进源码：PyDictObject到底是什么？
3.1 CPython中字典的核心结构
在CPython源码中，字典的实现位于Objects/dictobject.c文件中。核心结构体PyDictObject包含以下重要成员：
typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill; // 字典中已存储的键值对数量
Py_ssize_t ma_used; // 散列表中已被使用的槽位数量
Py_ssize_t ma_mask; // 散列表的掩码，用于计算索引位置
PyDictEntry *ma_table; // 散列表的槽位数组
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE]; // 小型字典的默认数组
};各个字段的含义：
ma_fill： 字典中有效键值对的数量（不含已被删除的）
ma_used： 哈希表中已被占用的槽位数量（包括被标记删除的）
ma_mask： 掩码值，等于size - 1，用于快速计算索引
ma_table：指向哈希表数组的指针
ma_smalltable： 小型字典的默认数组，大小通常为8
3.2 小字典优化：为什么新建的字典不直接分配大内存？
你可能会注意到，PyDictObject里有两个表：ma_table和ma_smalltable。
原因很简单：Python代码中有大量的小字典。如果一个字典只有两三个键值对，却直接分配一个大型哈希表，内存浪费会非常严重。所以Python做了一个聪明的优化：
当字典的键值对数量少于PyDict_MINSIZE（默认是8）时，ma_table直接指向ma_smalltable，使用预先分配的8个槽位。只有当字典中的元素数量超过这个阈值时，才会动态分配更大的内存空间。
python
# 新建的空字典，底层只有8个槽位的小数组
d = {}
d["a"] = 1 # 仍然在这个小数组内
# 当键值对数量超过阈值后，才会扩容
for i in range(10):
d[f"key{i}"] = i # 某个时刻会触发扩容这就像你买了一个小盒子装日常杂物，等东西多到装不下了再换大箱子——既省钱又高效。
四、字典的紧凑存储模型（Python 3.6+）
4.1 从传统设计到紧凑设计
在Python 3.5及之前版本，字典的存储方式比较直接：一个哈希数组直接存储键值对。这种设计的缺点是内存利用率低——为了减少冲突，哈希表需要保持稀疏，大量槽位是空的。Python 3.6引入了一个革命性的改变：紧凑哈希表（Compact Hash Table）。从Python 3.7开始，这一设计成为正式标准，还意外地让字典变得有序（保持插入顺序）。
4.2 键值分离的设计思想
紧凑字典的核心思想可以用一句话概括：把"找位置"和"存数据"分开。
具体来说，字典内部维护了两个数组：
1. indices数组（索引数组）：大小是2的幂，每个元素是一个整数，指向entries数组中的位置，或者用特殊值标记空槽（-1）和已删除槽（-2）。
2. entries数组（条目数组）：按插入顺序存储键值对，每个entry包含me_hash（哈希值）、me_key（键）和me_value（值）。
4.3 为什么紧凑设计更快更省内存？
这种设计带来三大好处：
1. 内存更省：indices数组可以使用更小的整数类型（如int8、int16、int32），根据字典大小自适应选择，大大减少了内存占用。
2. 迭代更快：遍历字典时，只需要线性扫描entries数组，跳过空槽即可。由于entries是连续存储的，CPU缓存命中率极高。
3. 天然有序：entries数组按插入顺序排列，因此dict.keys()、dict.values()、dict.items()的返回顺序就是插入顺序——这个特性从Python 3.7开始正式成为语言规范。
python
# Python 3.7+ 字典保持插入顺序
d = {}
d["banana"] = 3
d["apple"] = 2
d["orange"] = 1
print(list(d.keys())) # ['banana', 'apple', 'orange'] —— 保持插入顺序！
五、字典操作的核心流程：从源码看细节
5.1 哈希计算：从键到数字
当执行d[key] = value时，Python的第一步是计算键的哈希值：
hash_value = PyObject_Hash(key)Python内置的不可变类型（str、int、tuple等）都实现了__hash__()方法。对于自定义类的实例，如果该实例是可哈希的（实现了__hash__和__eq__方法），也可以作为字典的键。
注意：列表、字典、集合是不可哈希的，因为它们是可变的。如果把列表作为字典的键，Python会抛出 TypeError: unhashable type: list。
5.2 查找流程：lookdict函数是怎么工作的
查找是字典最核心的操作，插入和删除都依赖它。Python 3.6+的查找流程如下：
1. 计算哈希值 h = hash(key)
2. 计算初始索引 i = h & (size - 1) —size是2的幂，位运算代替取模
3. 查看 indices[i]：
- 如果 indices[i] == -1：该位置从未使用过，键不存在 → 返回未找到
- 如果 indices[i] == -2：该位置曾被使用后删除，继续探测
- 如果 indices[i] >= 0：去 entries[indices[i]] 取 entry
4. 比对哈希值和键是否匹配：
- 如果 entry.me_hash == h 且 entry.me_key == key 或 key相等，找到，返回结果；
- 否则，继续探测下一个位置
5.3 冲突处理：Python的伪随机探测算法
当初始位置已经被占用时，Python不会简单地"+1"线性探测，而是采用一种更聪明的伪随机探测算法：
j = (5*j) + 1 + perturb
perturb >>= 5其中perturb初始化为哈希值右移5位，每次迭代后继续右移。这个算法在源码中的注释被称为perturb策略，它的优点是让探测序列看起来像随机的，有效避免"聚集"问题——即多个冲突的键挤在一起形成长链。
5.4 插入操作：当键不存在时
插入一个新键值对的流程如下：
1. 通过lookdict查找键是否存在。
2. 如果键已存在，直接覆盖me_value。
3. 如果键不存在：
- 找到一个空闲槽位（indices中为-1或-2的位置）
- 在entries数组末尾追加一个新的entry
- 将indices[i]指向该entry的索引
- 更新ma_used计数
5.5 删除操作：为什么被删除的槽位还在？
删除一个键时，Python并不会立即把该位置清空并回收内存。相反，它会把indices中对应的位置标记为-2（DELETED），即"伪空位"。
为什么不直接清空呢？——因为开放寻址的查找链不能断。
想象一下：你在停车场找车位，沿着一条路径找到了一个空位。但如果有人把某个中间车位彻底移除了（标记为空），后面的人沿着同一条路径可能会误以为后面也没有车位了。所以删除操作只能打一个"暂不可用"的标记，而不能把位置真正清空。
python
# 底层表现：删除元素后，字典大小可能没有变小
d = dict.fromkeys(range(1000))
import sys
print(sys.getsizeof(d)) # 某个较大的值
for i in range(500):
del d[i]
print(sys.getsizeof(d)) # 大小没有减少！只是内部标记为DELETED这就是为什么频繁增删字典不会立即释放内存——那些被标记为DELETED的槽位会一直占用空间，直到字典触发扩容或缩容时才会被清理。
六、动态扩容与负载因子
6.1 什么时候扩容？
字典不会无限地在一个固定大小的哈希表里塞东西。当槽位被占用的比例太高时，哈希冲突的概率会急剧上升，性能会下降。
Python字典使用一个指标叫负载因子：used / size（已使用槽位数 / 总槽位数）。当负载因子达到约2/3时，字典就会触发扩容。
python
# 观察字典何时扩容
d = {}
for i in range(20):
d[i] = i
print(f"元素数量: {len(d)}, 底层大小: {len(d.keys().__sizeof__()? 实际无法直接获取)}")6.2 扩容的过程：重哈希（Rehash）
扩容的过程可以理解为搬家：
1. 计算新的大小：通常是原大小的2倍（对于小字典可能是4倍），并且新大小保持为2的幂。
2. 分配新的indices数组和entries数组。
3. 遍历旧的entries数组中的所有有效键值对：
- 对每个键重新计算哈希值
- 根据新的大小重新计算索引位置
- 插入到新表中
4. 释放旧的数组内存
扩容的瞬间，时间复杂度是O(n)。但由于这种操作不是每次插入都发生，从长期来看，每次插入的平均成本仍然是O(1)——这就是"摊还分析"的威力。
6.3 为什么Python选择2/3作为阈值？
这是一个时间与空间的权衡：
阈值太高（比如0.9）：空间利用率高，但哈希冲突严重，查找速度下降。
阈值太低（比如0.3）：冲突少、查找快，但内存浪费严重。
2/3是一个经过大量实践检验的平衡点，既保证了较好的空间利用率，又维持了接近O(1)的查找性能。
七、字典的内存占用到底有多大？
7.1 一个空字典占多少内存？
python
import sys
empty_dict = {}
print(sys.getsizeof(empty_dict)) # 在64位Python上，输出通常是72字节这72字节包含了PyDictObject结构本身，以及预先分配的小型数组（`ma_smalltable`，8个槽位）。
7.2 随着元素增加，内存如何增长？
字典的内存增长不是线性的，而是阶梯式的——只有达到负载因子阈值时才会触发扩容，每次扩容后容量翻倍。
python
import sys
def dict_memory_usage(n):
d = {}
for i in range(n):
d[i] = i
return sys.getsizeof(d)
for size in [0, 10, 50, 100, 500, 1000, 5000]:
print(f"{size}个元素: {dict_memory_usage(size)} 字节")7.3 紧凑字典的内存优势
与Python 3.5及之前版本相比，紧凑字典的内存占用减少了约20%-25%，同时遍历速度提高了约10%-15%。这是因为：
1. entries数组连续紧凑，没有空槽浪费
2. indices数组可以根据字典大小选择最小的整数类型
3. 更好的缓存局部性
八、字典的性能优化与注意事项
8.1 选择合适的键类型
字符串是最快的键类型。Python对字符串哈希有专门优化，而且字符串在解释器内部有驻留机制（interning），可以加速比较操作。
python
# 推荐：用字符串作键
d["user_name"] = "Alice"
# 可以但稍慢：用元组作键
d[("user", "name")] = "Alice"
# 避免：用自定义对象作键（除非必须）
class User:
def __init__(self, name):
self.name = name
# 必须实现 __hash__ 和 __eq__8.2 预分配容量
如果你事先知道字典要存储大量元素，可以提前用某种方式预分配。虽然没有直接的reserve()方法，但可以这样：
python
# 方法1：一次性创建足够大的字典
keys = list(range(10000))
values = [0] * 10000
d = dict(zip(keys, values))
# 方法2：让字典先扩容到目标大小
d = {}
for i in range(10000):
d[i] = None # 先填充占位
# 然后再替换实际值这可以避免多次扩容带来的重复开销。
8.3 小心哈希攻击
如果攻击者能控制字典的键，并故意构造大量哈希值相同的键，会导致所有键落入同一个槽位，查找复杂度从O(1)退化到O(n)——这就是哈希冲突攻击或哈希洪水攻击。
Python从3.3版本开始引入了哈希随机化机制，每次启动解释器时使用随机种子来生成字符串的哈希值，使得攻击者无法预测哈希冲突模式。
8.4 字典 vs 其他映射类型
| 类型 | 适用场景 | 优点 | 缺点 |
| dict | 通用场景 | 最快、最灵活 | 内存占用相对较大 |
| defaultdict | 需要默认值 | 代码简洁 | 略慢于普通dict |
| OrderedDict | 需要额外顺序操作 | 支持move_to_end等 | Python 3.7+ 普通dict已有序 |
| Counter | 计数统计 | 专门的API | 仅适用于计数场景 |
| types.MappingProxyType | 只读字典视图 | 防止意外修改 | 不能修改 |
九、常见面试题：
问1：Python字典的底层数据结构是什么？
答：Python字典底层是哈希表，但在Python 3.6之后采用了紧凑哈希表的设计。它由两个核心数组组成：indices数组用于哈希索引查找，entries数组按插入顺序紧凑存储键值对。这种设计既保证了O(1)的查找性能，又实现了内存高效和插入有序。
问2：字典的键有什么要求？
答：字典的键必须是可哈希的，即键必须实现__hash__()和__eq__()方法，并且在生命周期内哈希值保持不变。Python内置的不可变类型（str、int、tuple等）都是可哈希的，而可变类型（list、dict、set）则不可哈希。自定义类的实例默认是可哈希的（基于对象ID），但如果重写了__eq__，通常也需要重写__hash__来保持一致。
问3：字典的查找时间复杂度真的是O(1)吗？
答：平均情况下是O(1)，最坏情况下是O(n)。得益于好的哈希函数和冲突处理机制，实际运行中绝大多数操作都是O(1)。但在极端情况下（比如所有键的哈希值都相同），查找会退化成线性扫描。不过Python有哈希随机化和自动扩容机制来避免这种情况。
问4：为什么Python 3.7+的字典是有序的？
答：因为紧凑哈希表的设计中，entries数组是按插入顺序存储键值对的。遍历字典时，实际上是线性扫描entries数组，所以顺序自然就是插入顺序。这个特性从Python 3.6开始作为实现细节存在，3.7正式成为语言规范。
问5：字典和列表，哪个更快？什么时候用字典什么时候用列表？
答：如果需要通过键（key）来查找值，字典更快（O(1) vs 列表的O(n)）；如果需要通过位置（index）来访问，列表更快（直接内存偏移）；如果只是顺序存储数据，列表更省内存。原则：需要快速查找用字典，需要顺序遍历用列表。
更多推荐
10
0- 0
已为社区贡献4条内容
所有评论(0)