汤不热吧简介：Python字典的魔力
Python中的字典（dict）是使用最广泛的数据结构之一，它提供了平均 O(1) 的时间复杂度进行查找、插入和删除操作。这种高效性能的背后，是基于哈希表（Hash Table）的精妙设计。然而，在Python 3.6版本之前，字典的实现方式存在一定的内存浪费。本文将深入解析字典的底层原理，并重点介绍Python 3.6+如何通过结构演进实现内存优化。
1. 哈希表基础：开放地址法
Python字典底层采用哈希表实现，具体来说，是开放地址法（Open Addressing）来处理哈希冲突。当一个键值对要被插入时：
- 计算哈希值：使用内置的 hash() 函数计算键的哈希值。
- 确定索引：通过哈希值对哈希表大小取模，确定初始槽位。
- 处理冲突：如果初始槽位已被占用（即发生冲突），则使用探测（Probing）技术寻找下一个空闲槽位。CPython使用伪随机序列或线性探测的变种来查找下一个位置。
2. Python 3.6 之前的字典结构（稀疏型）
在Python 3.6之前，字典结构相对简单，通常由一个巨大的数组（槽位，Entry Array）构成。每个槽位都可能存储一个包含三元组（哈希值、键引用、值引用）的数据结构。
想象一下这种结构：
| Index | Hash | Key Ref | Value Ref |
|---|---|---|---|
| 0 | – | – | – |
| 1 | hash(k1) | k1 | v1 |
| 2 | – | – | – |
| 3 | hash(k2) | k2 | v2 |
| … | … | … | … |
问题： 随着字典的填充因子（Load Factor）越来越低（即字典很空），这个Entry Array中会有大量的空槽位（即 –）。这些空槽位虽然没有存储数据，但它们依然占据着分配的内存空间。这种结构是稀疏的，导致内存利用率不高。
3. Python 3.6+ 的紧凑型字典结构（内存优化）
从Python 3.6（针对CPython实现）开始，字典的底层结构经历了重大重构，引入了“紧凑型”字典（Compact Dictionary）。这种结构的核心思想是将索引和实际存储的数据分离，从而实现内存优化。
新的字典由两部分组成：
A. Indices 数组（哈希表）
这是一个真正的哈希表，负责存储键的哈希值计算得到的槽位，但它不直接存储键值对，而是存储一个指向实际存储位置的整数索引。
B. Entries 数组（数据存储）
这是一个按插入顺序排列的列表，用于存储实际的 (hash, key, value) 三元组。重要的是，这个列表只存储已有的键值对，没有空槽位，因此它是紧凑的（Compact）。
查找过程演进：
- 计算 Key 的哈希值 H。
- 通过 H 查找 Indices 数组，得到一个整数 I（即 Entries 数组的索引）。
- 使用 I 直接定位到 Entries 数组中的紧凑存储位置，获取键值对。
| 结构 | Indices (哈希表) | Entries (紧凑存储) |
|---|---|---|
| 内容 | 存储 Entries 数组的索引 | 存储 (Hash, Key, Value) 三元组 |
| 特点 | 保持稀疏以减少冲突 | 保持紧凑以节省空间 |
带来的优化和额外收益
- 内存节省：由于 Entries 数组是紧凑的，极大地减少了用于存储空槽位（Padding）的内存开销。特别是对于包含少量键值对的大容量哈希表，效果更明显。
- 有序性：由于 Entries 数组是严格按照插入顺序追加的，这使得 Python 3.7+ (CPython 3.6+ 开始实现，3.7+ 成为标准语言特性) 的字典自然地具有了插入顺序（Ordered）的特性。
4. 实践代码示例：观察字典内存的优化
虽然我们无法直接在Python中访问底层的 C 结构，但可以通过 sys.getsizeof() 观察字典结构带来的内存开销差异，尤其是当字典包含少量元素时。
假设我们创建了一个字典并删除了大部分元素，旧版本的字典会保留大量空槽位，而新版本的紧凑结构则能更好地回收空间（虽然整体内存不会降到极低，但空闲槽位的开销会减少）。
import sys
# 字典在内存中的基础开销
# 注意：sys.getsizeof只计算对象本身的大小，不包括它引用的对象（key和value）。
empty_dict_size = sys.getsizeof({})
print(f"空字典基础大小：{empty_dict_size} 字节")
def create_and_measure_dict(size):
d = {i: str(i) for i in range(size)}
# 测量完全填充的字典
filled_size = sys.getsizeof(d)
print(f"填充 {size} 个元素后的字典大小：{filled_size} 字节")
return d
def measure_dict_after_deletion(d, count_to_keep):
keys_to_delete = list(d.keys())[count_to_keep:]
for key in keys_to_delete:
del d[key]
deleted_size = sys.getsizeof(d)
print(f"删除大部分元素，仅保留 {count_to_keep} 个元素后的字典大小：{deleted_size} 字节")
# 示例操作
# 在 Python 3.6+ 中运行，可以观察到即使删除了大量元素，
# 由于 Entries 数组是紧凑的，内存开销比旧版本（稀疏结构）更优。
N = 50 # 初始填充数量
d_test = create_and_measure_dict(N)
measure_dict_after_deletion(d_test, 5)
运行结果分析（取决于环境，但趋势一致）：
- 在Python 3.6+中，当你删除元素时，紧凑型结构能够更有效地管理 Entries 数组的空间，尽管 Indices 数组可能需要时间重新调整大小（rehash），但总体上内存利用率更高。
- 如果是在 Python 3.5- 环境下运行，即使大量删除，由于稀疏数组不会立即收缩，内存占用会显得更大。
总结
Python 字典从传统的稀疏哈希表结构，进化到 Python 3.6+ 的紧凑型结构，是CPython优化内存使用和提高效率的重要一步。通过分离哈希索引和紧凑的数据存储，不仅实现了显著的内存优化，同时还附带了字典有序性的特性。理解这一底层机制，有助于我们编写更高效、更节约内存的Python代码。