深入理解 Python 虚拟机：字典（dict）的内存优化
在 Python 语言的发展历程中，字典（dict）作为最核心的内建数据结构之一，其性能与内存占用一直是 CPython 解释器优化的重点。早期的 Python 3 版本中，字典的实现虽然功能完备，但在处理大规模数据时存在显著的内存浪费问题。随着硬件成本的降低和软件对内存效率要求的提高，CPython 从 3.6 版本开始引入了紧凑字典（Compact Dict）机制，显著降低了内存开销。
旧版字典结构分析
在深入优化之前，我们需要回顾一下 Python 3.5 及更早版本中字典的基础实现结构。在 CPython 源码中，字典对象 PyDictObject 主要包含以下核心字段：
typedef struct {
PyObject_HEAD
Py_ssize_t ma_used;
PyDictKeysObject *ma_keys;
PyObject **ma_values;
} PyDictObject;
其中，ma_keys 指向一个键对象数组，而 ma_values 则是一个值指针数组。为了支持快速查找，键对象被组织在一个哈希表中。具体的键存储结构 _dictkeysobject 定义如下：
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
Py_ssize_t dk_size;
dict_lookup_func dk_lookup;
Py_ssize_t dk_usable;
PyDictKeyEntry dk_entries[1];
};
typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;
在这种旧版结构中，所有的键值对都存储在 dk_entries 数组当中。例如，对于 "Hello" 和 "World" 这样的键值对，系统会计算键的哈希值。假设 "Hello" 的哈希值为 8，通过取模运算确定其在数组中的位置。如果哈希表长度为 1024，且负载因子为 2/3，那么实际可用的槽位约为 682 个。由于哈希冲突的存在以及避免过度拥挤，哈希表通常设计得比实际元素数量大得多。
这种设计导致了一个严重的问题：dk_entries 数组中存在大量空槽位。每个 Entry 占用 24 字节（在 64 位系统上），如果哈希表长度是 1024，但只存入了少量数据，那么大量的空间被保留用于未来的扩展或处理冲突，造成了约 1/3 甚至更多的内存浪费。具体来说，如果负载因子限制为 2/3，意味着每 3 个槽位只能存 2 个有效数据，剩下的 1 个槽位必须留空。对于长度为 1024 的数组，大约会有 341 个空槽位，即 341 * 24 = 8184 字节的内存被闲置。
紧凑字典优化方案
为了解决上述内存浪费问题，新版 CPython 采用了紧凑字典的设计策略。其核心思想是将索引数组与实际的键值对存储分离开来。新的字典结构不再直接在稀疏的哈希表中存储完整的键值对，而是使用一个紧凑的索引数组来映射哈希值到实际数据的下标。
具体设计如下图所示（示意图）：
在新的字典架构中，dk_indices 是一个整型数组，它保存的是要保存对象在 dk_entries 当中的下标。例如，如果哈希值求余数之后的值等于 7，而 的值为 0，则表示该键值对实际上存储在 数组的第 0 个位置。
