深入理解 Python 虚拟机：字典（dict）的优化

1. 引言Python 的字典dict是这门语言最核心、最常用的数据结构之一。无论是模块的命名空间、对象的属性查找还是函数的关键字参数传递背后都离不开字典的身影。正因如此CPython 对字典的实现进行了多轮深度优化使其在保持灵活性的同时也能拥有出色的性能。本文将深入 CPython 源码剖析字典从早期版本到现代版本Python 3.6的演进历程重点讲解紧凑布局compact layout、哈希表结构、冲突解决策略以及**键共享key-sharing**等关键优化技术帮助你真正理解 Python 字典为什么快、快在哪里。2. 字典的基础哈希表字典本质上是一张哈希表hash table。它通过哈希函数将键key映射到一个固定大小的数组索引上从而实现平均 O(1) 的查找、插入和删除。2.1 哈希函数与哈希值Python 中每个对象都可以通过hash()函数获取一个整数哈希值。对于整数哈希值就是它本身取模后对于字符串CPython 使用 SipHash 算法计算对于自定义对象则调用其__hash__方法。hash(hello)-1182516015910hash(42)42需要注意的是哈希值并不是直接作为数组下标使用的而是需要经过一步**取模mod**运算映射到哈希表的容量范围内。2.2 冲突与解决当两个不同的键计算出相同的数组索引时就发生了哈希冲突collision。CPython 采用**开放寻址法open addressing**来解决冲突当某个槽位已被占用时会按照一定的探测序列probe sequence继续向后查找直到找到空槽或匹配的键。# 伪代码开放寻址的探测过程deffind_slot(table,key):indexhash(key)%len(table)whiletable[index]isnotNoneandtable[index].key!key:index(index1)%len(table)# 线性探测returnindexCPython 实际使用的探测策略比简单的线性探测更精细它基于哈希值的高位信息来生成探测步长从而减少聚集clustering现象。3. 传统实现分离式存储Python 3.5 及以前在 Python 3.5 及更早版本中字典的底层结构是一个单一的 entries 数组每个 entry 同时存储哈希值、键和值typedefstruct{Py_hash_t me_hash;// 哈希值PyObject*me_key;// 键PyObject*me_value;// 值}PyDictEntry;整个字典就是这样一个 entry 数组加上一些元信息容量、已用数量等。3.1 传统实现的问题这种实现有一个明显的缺点内存利用率低。为了保证查找效率哈希表的负载因子load factor通常维持在 2/3 以下也就是说有大约 1/3 的槽位是空的。在传统实现中这些空槽位同样占用完整的 entry 空间每个 entry 24 字节造成了大量内存浪费。此外遍历字典时需要扫描整个数组跳过所有空槽位效率也不高。4. 现代实现紧凑布局Python 3.6Python 3.6 引入了一项革命性的优化——紧凑字典compact dict由 INADA Naoki 提出。这一设计将索引与数据分离从根本上解决了内存浪费问题。4.1 双数组结构现代字典由两个数组组成索引数组indices一个int数组长度等于哈希表的容量通常是 2 的幂存储的是 entry 在 entries 数组中的下标。entries 数组一个紧凑的 entry 数组只包含实际存在的键值对按插入顺序排列。typedefstruct{PyObject*me_key;// 键PyObject*me_value;// 值Py_hash_t me_hash;// 哈希值}PyDictKeyEntry;4.2 查找过程查找时先通过哈希值定位到 indices 数组中的某个槽位取出对应的 entry 下标再到 entries 数组中访问真正的键值对# 伪代码紧凑字典的查找deflookup(d,key):idxhash(key)%len(d.indices)entry_indexd.indices[idx]ifentry_index-1:# 空槽returnNoneentryd.entries[entry_index]ifentry.keykey:returnentry.value# 冲突则继续探测4.3 内存节省由于 indices 数组只存储整数下标每个 1~8 字节视容量而定而 entries 数组只存储实际存在的键值对空槽位不再占用完整的 entry 空间。对于一个小字典如 8 个键值对内存占用可以从传统实现的数百字节降低到几十字节节省幅度可达数倍。4.4 保持插入顺序紧凑布局的另一个副产品是字典现在保持插入顺序。因为 entries 数组按插入顺序追加遍历时只需顺序扫描 entries 数组即可无需跳过空槽。这一特性在 Python 3.7 中被正式写入语言规范成为所有 Python 实现必须遵守的行为。d{b:1,a:2,c:3}list(d.keys())[b,a,c]# 保持插入顺序5. 键共享字典Key-Sharing Dict在 Python 3.3 中CPython 引入了键共享字典key-sharing dict专门用于优化对象属性存储。5.1 问题背景每个 Python 对象都有一个__dict__属性字典用于存储实例属性。如果每个实例都拥有一份独立的、完整的字典结构那么对于大量同类的实例对象会浪费大量内存——因为它们的键属性名几乎完全相同只有值不同。5.2 共享机制键共享字典的核心思想是将键属性名和哈希值提取出来放到一个共享的 keys 对象中所有同类的实例共用这一份 keys每个实例只保存自己的 values 数组。typedefstruct{Py_ssize_t dk_refcnt;// 引用计数Py_ssize_t dk_size;// 容量PyDictKeyEntry*dk_entries;// 共享的键和哈希值// ...}PyDictKeysObject;实例对象的结构变为typedefstruct{PyObject_HEAD PyDictKeysObject*ma_keys;// 指向共享的 keysPyObject**ma_values;// 本实例的值数组}PyDictObject;5.3 收益对于大量同类实例例如 ORM 模型、数据类实例键共享字典可以显著减少内存占用。假设有 10000 个实例每个有 5 个属性传统实现需要 10000 份完整的字典结构而键共享实现只需要 1 份 keys 10000 份 values 数组内存节省非常可观。classPoint:def__init__(self,x,y):self.xx self.yy# 大量 Point 实例共享同一份 keysx, ypoints[Point(i,i*2)foriinrange(10000)]5.4 注意事项键共享字典有一个限制一旦某个实例的字典被直接修改例如添加了新的键该实例就会脱离共享转为独立的完整字典。因此在性能敏感的场景中应尽量避免对实例的__dict__进行动态增删键的操作。6. 其他优化细节6.1 哈希值缓存对于字符串键CPython 会缓存其哈希值。字符串对象内部有一个字段用于存储计算过的哈希值这样同一个字符串在多次作为字典键查找时无需重复计算哈希。typedefstruct{PyObject_HEAD Py_ssize_t ob_shash;// 缓存的哈希值-1 表示未计算// ...}PyUnicodeObject;6.2 小字典的快速路径CPython 对容量较小的字典如 1~5 个键值对提供了专门的快速路径避免通用查找逻辑的开销。这些小型字典在创建时直接使用栈上分配的固定大小数组进一步减少内存分配次数。6.3 调整大小策略当字典的负载因子超过 2/3 时字典会进行扩容通常将容量翻倍。扩容时indices 数组会重新分配但 entries 数组中的键值对可以原地保留只需重新计算每个 entry 在 indices 中的映射关系这比传统实现中整体搬迁 entry 数组要高效得多。7. 性能对比与实测为了直观感受这些优化带来的收益我们可以做一个简单的内存对比实验importsys# 传统方式大量独立小字典dicts[{a:i,b:i1,c:i2}foriinrange(10000)]print(sys.getsizeof(dicts[0]))# 单个字典的大小# 键共享方式大量同类实例classObj:def__init__(self,a,b,c):self.aa self.bb self.cc objs[Obj(i,i1,i2)foriinrange(10000)]print(sys.getsizeof(objs[0].__dict__))# 单个实例字典的大小在 Python 3.11 中运行上述代码你会发现单个实例的__dict__大小远小于独立字典的大小这正是键共享优化的直接体现。8. 总结Python 字典的优化之路是 CPython 在内存效率与访问速度之间不断权衡的缩影紧凑布局将索引与数据分离大幅降低内存占用并顺带实现了插入有序键共享字典针对对象属性存储场景让大量同类实例共享键结构节省海量内存哈希值缓存与小字典快速路径等细节优化让常见操作更加高效。理解这些底层机制不仅能帮助你写出更高效的代码例如避免破坏键共享、合理预估字典容量也能让你在阅读 CPython 源码时更加游刃有余。字典虽小却凝聚了 Python 设计者数十年的智慧。