CPython 字典查找优化：快表（Fast Map）与哈希探查序列
大家好，今天我们来深入探讨 CPython 字典查找的内部优化机制，重点关注快表（Fast Map）以及哈希探查序列的底层实现。字典作为 Python 中最常用的数据结构之一，其查找效率对程序性能至关重要。理解 CPython 如何优化字典查找过程，能帮助我们编写更高效的 Python 代码，也能更深刻地理解这门语言的底层原理。
1. 字典的底层结构：PyDictObject
在 CPython 中，字典的底层实现是 PyDictObject 结构体。它主要包含两部分：
ma_fill: 已使用的 entry 数量。ma_used: 有效 entry 数量 (不包括被删除的 entry)。ma_mask: 哈希表的尺寸掩码，size = ma_mask + 1，表示哈希表的大小。ma_table: 指向哈希表的指针，类型为PyDictEntry*或PyDictKeysObject*。这是字典的核心存储区域。ma_keys: 指向PyDictKeysObject的指针，存储键的元信息（例如键的哈希值）。
哈希表本质上是一个 PyDictEntry 数组，每个 PyDictEntry 存储一个键值对。但实际上，CPython 对字典的存储结构进行了优化，区分了两种模式：分离链接（separate chaining）模式 和 紧凑（compact）模式。
1.1 分离链接模式 (Split Table)
在早期版本的 CPython 中，字典采用分离链接模式。在这种模式下，ma_table 直接指向一个 PyDictEntry 数组。每个 PyDictEntry 结构体包含三个字段：
typedef struct {
Py_hash_t me_hash; // 键的哈希值
PyObject *me_key; // 键对象
PyObject *me_value; // 值对象
} PyDictEntry;当发生哈希冲突时，多个键值对会存储在哈希表的同一个位置（索引），形成一个链表。查找时，需要遍历链表来找到目标键。
缺点：
- 内存占用高：每个键值对都需要单独分配一个
PyDictEntry结构体。 - 查找效率低：哈希冲突会导致链表变长，增加查找时间。
1.2 紧凑模式 (Combined Table)
为了解决分离链接模式的缺点，CPython 3.6 引入了紧凑模式，作为默认的字典实现。在紧凑模式下，ma_table 指向一个 PyDictKeysObject 结构体，而 PyDictEntry 数组被移动到了 PyDictKeysObject 内部。ma_keys 指向该 PyDictKeysObject 实例。
typedef struct {
Py_ssize_t dk_refcnt;
Py_ssize_t dk_size; // 哈希表的大小
Py_ssize_t dk_usable; // 可用 entry 数量
Py_ssize_t dk_nentries; // 已使用的 entry 数量
char dk_indices[]; // 存储索引的数组
} PyDictKeysObject;紧凑模式的关键在于 dk_indices 数组，它存储了 PyDictEntry 在另一个连续数组中的索引。这个连续数组存储着键和值对象。
这种布局带来的好处是：
- 内存占用更少： 键和值对象被连续存储，减少了内存碎片。
- 查找速度更快： 快表（Fast Map）的引入，加速了哈希冲突的解决。
2. 快表（Fast Map）：加速哈希探查
快表是紧凑模式字典中一个重要的优化手段，用于加速哈希冲突的解决。它的核心思想是利用 dk_indices 数组来存储哈希冲突的探查序列。
2.1 dk_indices 数组的结构
dk_indices 数组的类型是 char，int8_t 或 int32_t，具体取决于字典的大小。它存储了哈希表中每个位置的状态信息：
- Unused (Unused)： 表示该位置未被使用。
- Active (Active)： 表示该位置已被键值对占用。
- Deleted (Deleted)： 表示该位置已被删除，可以被新的键值对覆盖。
在 dk_indices 中存储的是索引，这些索引指向一个连续存储键值对的数组，这个数组并不直接存在于 PyDictKeysObject 结构体中，而是通过计算偏移量来访问。
2.2 哈希探查序列
当发生哈希冲突时，CPython 会使用一种叫做 "开放寻址法" 的策略来寻找下一个可用的位置。具体来说，它会生成一个伪随机探查序列，尝试不同的索引，直到找到一个空闲的位置或者找到目标键。
在快表机制下，dk_indices 数组存储了哈希探查序列的信息。例如，如果 dk_indices[i] 的值为 j，则表示哈希值为 i 的键值对存储在键值对数组的 j 位置。
2.3 快表如何加速查找
快表通过以下方式加速查找：
- 快速判断位置状态： 通过直接访问
dk_indices[hash_value]，可以快速判断哈希表中的对应位置是空闲、已被占用还是已被删除。 - 加速冲突解决： 当发生哈希冲突时，无需像分离链接模式那样遍历链表。快表直接存储了探查序列的信息，可以快速找到下一个可能的位置。
2.4 示例
假设我们有一个字典，其 dk_size 为 8，dk_nentries 为 3。dk_indices 数组如下：
dk_indices: [0, -1, 1, -2, -1, 2, -1, -1]0表示索引 0 处存储了一个键值对。-1表示索引 1, 4, 6, 7 处未被使用。1表示索引 2 处存储了一个键值对。-2表示索引 3 处已被删除。2表示索引 5 处存储了一个键值对。
现在，我们要查找一个键，其哈希值为 0。我们首先访问 dk_indices[0]，得到值为 0。这意味着该键值对存储在键值对数组的索引 0 处。
如果我们要查找一个键，其哈希值为 1，我们访问 dk_indices[1]，得到值为 -1。这意味着该位置未被使用，说明字典中不存在该键。
3. 哈希探查序列的生成
CPython 使用一种称为 "Perturb-Shift" 的算法来生成哈希探查序列。这种算法保证了探查序列的伪随机性，并且能够充分利用哈希表中的空间。
3.1 Perturb-Shift 算法
Perturb-Shift 算法的核心思想是使用键的哈希值和一个扰动值（perturb）来生成探查序列。
size_t i = hash & mask; // 初始索引
size_t perturb = hash; // 扰动值
while (1) {
if (dk_indices[i] == UNUSED) {
// 找到空闲位置
break;
}
if (dk_indices[i] == ACTIVE && key_matches(key, i)) {
// 找到目标键
break;
}
perturb >>= PERTURB_SHIFT; // 右移扰动值
i = (i * 5 + 1 + perturb) & mask; // 计算下一个索引
}其中：
hash是键的哈希值。mask是哈希表的尺寸掩码。PERTURB_SHIFT是一个常量，通常为 5。key_matches(key, i)是一个函数，用于比较键和哈希表中索引i处的键是否相等。
3.2 算法解释
- 初始索引： 首先，使用哈希值和掩码计算出初始索引
i。 - 扰动值： 将哈希值作为扰动值
perturb。 - 循环探查：
- 如果
dk_indices[i]为UNUSED，表示找到空闲位置，结束循环。 - 如果
dk_indices[i]为ACTIVE并且key_matches(key, i)返回True，表示找到目标键，结束循环。 - 否则，右移扰动值
perturb，并使用公式i = (i * 5 + 1 + perturb) & mask计算下一个索引i。
- 如果
3.3 算法特点
- 伪随机性： Perturb-Shift 算法生成的探查序列具有伪随机性，能够尽可能地避免聚集现象（多个键值对聚集在哈希表的同一区域）。
- 充分利用空间： 该算法能够充分利用哈希表中的空间，即使在哈希表接近满时，也能找到空闲位置。
- 高效： 算法的计算复杂度较低，能够快速生成探查序列。
4. 字典扩容
当字典中的键值对数量超过一定阈值时，CPython 会自动进行扩容。扩容的目的是为了保持字典的查找效率。
4.1 扩容条件
扩容的条件通常是 ma_used > ma_mask * 2 / 3。也就是说，当字典中已使用的 entry 数量超过哈希表大小的 2/3 时，就会触发扩容。
4.2 扩容过程
- 分配新的哈希表： 分配一块更大的内存空间，作为新的哈希表。新的哈希表的大小通常是旧哈希表的 4 倍。
- 重新哈希： 遍历旧哈希表中的所有键值对，并使用新的哈希表的大小重新计算每个键的哈希值和索引。
- 迁移数据： 将键值对从旧哈希表迁移到新的哈希表中。
- 释放旧哈希表： 释放旧哈希表的内存空间。
4.3 扩容的影响
扩容会带来一定的性能开销，因为需要重新哈希和迁移数据。但是，扩容能够有效地降低哈希冲突的概率，从而提高字典的查找效率。
5. 代码示例：模拟字典查找
为了更直观地理解字典查找的过程，我们可以用 Python 代码来模拟 CPython 字典的查找过程（简化版）。
class DictEntry:
def __init__(self, key, value):
self.key = key
self.value = value
self.hash = hash(key)
class MyDict:
def __init__(self, size=8):
self.size = size
self.table = [None] * size
self.used = 0
self.mask = size - 1
def __setitem__(self, key, value):
entry = DictEntry(key, value)
index = entry.hash & self.mask
perturb = entry.hash
while self.table[index] is not None:
if self.table[index].key == key:
self.table[index].value = value
return
perturb >>= 5
index = (index * 5 + 1 + perturb) & self.mask
self.table[index] = entry
self.used += 1
def __getitem__(self, key):
hash_value = hash(key)
index = hash_value & self.mask
perturb = hash_value
while self.table[index] is not None:
if self.table[index].key == key:
return self.table[index].value
perturb >>= 5
index = (index * 5 + 1 + perturb) & self.mask
raise KeyError(key)
def __delitem__(self, key):
hash_value = hash(key)
index = hash_value & self.mask
perturb = hash_value
while self.table[index] is not None:
if self.table[index].key == key:
self.table[index] = "DELETED" # 标记为已删除，实际实现更复杂
self.used -= 1
return
perturb >>= 5
index = (index * 5 + 1 + perturb) & self.mask
raise KeyError(key)
def __len__(self):
return self.used
# 示例
my_dict = MyDict()
my_dict["a"] = 1
my_dict["b"] = 2
my_dict["c"] = 3
print(my_dict["a"]) # 输出 1
print(my_dict["b"]) # 输出 2
print(len(my_dict)) # 输出 3
del my_dict["b"]
print(len(my_dict)) # 输出 2
try:
print(my_dict["b"])
except KeyError as e:
print(f"KeyError: {e}") #KeyError: 'b'这个示例代码简化了 CPython 字典的实现，但它包含了哈希、冲突解决、探查序列等核心概念。注意，真正的 CPython 字典实现要复杂得多，涉及到更多的细节和优化。
6. 表格总结：两种模式的比较
| 特性 | 分离链接模式 (Split Table) | 紧凑模式 (Combined Table) |
|---|---|---|
| 存储方式 | PyDictEntry 数组 |
PyDictKeysObject + 键值对数组 |
| 内存占用 | 较高 | 较低 |
| 查找速度 | 较慢 (哈希冲突时遍历链表) | 较快 (快表加速冲突解决) |
| 引入版本 | 早于 Python 3.6 | Python 3.6 |
| 是否默认 | 否 | 是 |
7. 深入理解才能写出更好的代码
通过对 CPython 字典底层实现，特别是快表和哈希探查序列的深入分析，我们能更好地理解 Python 字典高效的秘密。理解这些机制，能帮助我们更好地利用 Python 字典，编写出更高效、更优雅的代码。
更多IT精英技术系列讲座，到智猿学院