Chapter 64: dictobject.c

dictobject.c 解释的是一个普通 dict 为什么能同时承担映射表、对象属性表、模块命名空间、类命名空间、globals 和 builtins 的职责。本章要建立的判断能力是：看到一次 d[key]、一次属性写入或一次全局名字读取时，能追踪它在 CPython 中怎样落到 hash、index table、entry table、key-sharing、resize 和 inline cache 上。

本章以 CPython 的 dict 实现为主。语言层面的 dict 行为由 Python 规范和文档约束；CPython 的内存布局、探测算法、version tag 和 specialization 属于实现策略，字段名、opcode 名称和 cache 结构会随版本演进。本章默认讨论 Python 3.7 之后的语言语义，因为官方文档已经把 dict 插入顺序列为语言保证；同时用 CPython 3.11 之后的 specializing interpreter 解释 LOAD_GLOBAL 的加速思路。

贯穿本章的现象很短：

class User:
    def __init__(self, name, score):
        self.name = name
        self.score = score

users = {"alice": User("alice", 10), "bob": User("bob", 20)}
bonus = 5

def total(name):
    return users[name].score + bonus

这段代码同时经过三条 dict 路径：users[name] 是普通映射查找，user.score 背后通常读实例属性字典，bonus 和 users 是全局名字查找。dictobject.c 的阅读价值在于，它能把这些高层动作还原成同一组底层问题：key 的 hash 是否稳定，冲突如何探测，entry 怎样保存插入顺序，实例属性怎样共享 keys，字典变化怎样让全局名字缓存失效。

64.1 compact dict

compact dict 先解决内存布局问题。CPython 的现代 dict 把稀疏的哈希索引和紧凑的 entry 序列分开：dk_indices 是真正参与哈希定位的 index table，里面保存 entry 下标或空洞标记；dk_entries 是紧凑排列的 key、hash、value 信息。CPython 源码注释把这种结构描述为 compact and ordered，并列出 dk_indices[] 与 dk_entries[] 两段布局，Objects/dictobject.c 是阅读这一路径的入口。

这种分离让 dict 同时满足两个目标。查找时，解释器通过 hash 在 dk_indices 中探测；迭代时，解释器顺着 dk_entries 的物理顺序读取 active entries。插入新 key 通常追加到 entries 尾部，所以插入顺序天然可以通过 entries 顺序得到。Python 官方文档在 3.7 起保证 dict 保留插入顺序，并明确“更新已有 key 不改变顺序，删除后重新插入会放到末尾”，这条语义可以在 Built-in Types: mapping types 中看到。

下面的代码只观察语言层行为，用它可以对应 compact dict 的 entry 顺序：

data = {"a": 1, "b": 2, "c": 3}
data["a"] = 10
removed = data.pop("b")
data["b"] = 20

print(list(data))
print(data)

输出中的 key 顺序会是 a, c, b。a 的 value 被更新，entry 的位置仍然代表第一次插入的位置；b 删除后重新插入，新 entry 进入尾部。这个例子要说明的判断是：插入顺序是 dict 的语言行为，CPython 通过 compact layout 低成本实现它；顺序稳定并不说明内部没有空洞，删除会留下对查找路径有意义的状态。

从源码阅读角度看，compact dict 的第一层检查顺序是：先看当前字典是 combined table 还是 split table，再看 keys table 中 dk_indices 的大小和 dk_entries 的有效数量，最后看 value 存放在 entry 里还是单独的 values array 里。普通 {} 和 dict() 创建的映射通常走 combined table；对象实例的属性字典常见于 split table 路径。这个区分会影响内存占用、删除状态、resize 方式和属性访问优化。

combined table 把 key、hash、value 放在同一组 entries 中，适合普通映射，因为 key 集合变化频繁，局部性更好。split table 把 keys 与 values 分离，适合大量同类实例，因为许多实例拥有相同属性名集合，只是每个实例的属性值不同。compact dict 的核心结论是把 dict 拆成“定位用的稀疏结构”和“保存内容与顺序的紧凑结构”，插入顺序来自这个布局带来的稳定 entry 序列。

可以用下面这张图固定阅读入口。图中只表达 CPython compact dict 的概念结构，不表达具体 C 结构体的全部字段。

查找从 dk_indices 进入，最终落到 dk_entries 或 split values array。迭代从 entries 的顺序进入，跳过已经失效或没有 value 的位置。这个分层解释了两个常见现象：dict 查找依赖 hash table，dict 迭代又能稳定给出插入顺序。

64.2 probing algorithm

probing algorithm 解决 hash 冲突问题。哈希表无法让所有 key 都落到不同位置；当多个 key 的 hash 映射到同一个初始 index 时，CPython 必须按确定序列继续探测候选 slot。dictobject.c 中的注释描述了 perturb 参与的探测递推：用 hash 的低位得到初始位置，再让 perturb 逐步右移并进入 5 * j + 1 + perturb 形式的下一位置计算。

查找一个 key 时，CPython 的路径可以概括为五步：计算 key 的 hash；用 hash 和 mask 得到初始 slot；读取 dk_indices 中的状态；如果 slot 指向 active entry，就比较 hash 与 key 相等性；如果 slot 是 empty，查找终止并报告 miss；如果 slot 是 dummy 或 hash/key 不匹配，就沿 probe sequence 继续。这里的关键点是 empty 与 dummy 的语义不同：empty 表示这个位置从未持有 active key，探测链可以结束；dummy 表示这个位置曾经持有 key，探测链必须继续。

下面的例子用人为冲突展示 probing 的必要性。代码不暴露 CPython 的 slot 序列，只让读者观察语义结果：

class Collide:
    def __init__(self, label):
        self.label = label

    def __hash__(self):
        return 42

    def __eq__(self, other):
        return isinstance(other, Collide) and self.label == other.label

first = Collide("first")
second = Collide("second")
store = {first: "A", second: "B"}

print(store[Collide("first")])
print(store[Collide("second")])

两个 key 的 hash 相同，dict 仍然能区分它们，因为 hash 只负责缩小候选范围，最终身份由相等性比较确认。这个例子还说明一个工程边界：自定义 key 的 __hash__ 和 __eq__ 必须保持一致，同一个 key 在生命周期内参与查找时的 hash 应保持稳定。可变对象如果把可变字段纳入 hash，就会让“插入时的位置”和“查找时的位置”分离，表现为 key 已在字典中却无法按新状态稳定取回。

删除路径把 probing 的边界暴露得更清楚。combined table 中删除一个 key 后，index slot 通常进入 dummy 状态。dummy 能在后续插入中被复用，但它在查找 miss 时没有终止资格。原因是冲突链上的后续 active key 可能依赖这个位置继续向后探测；如果删除时把 dummy 直接还原成 empty，后面的 key 会在查找时被截断。

阅读 probing 相关代码时，可以按这个顺序判断一次查找为什么慢：先看 key 的 hash 分布是否集中，再看冲突后 equality 调用是否昂贵，再看删除是否留下大量 dummy slot，最后看 resize 是否已经重建索引。dict 平均查找很快，依赖的是 hash 分布、空位比例和探测序列共同维持；单独讨论 Big-O 会丢失 CPython 实际成本来源。

64.3 key-sharing dict

key-sharing dict 解决对象属性字典的重复存储问题。普通映射的 key 集合经常变化，所以 combined table 更直接；同一个类的大量实例通常拥有相同属性名，例如 name 和 score，每个实例重复保存这两个字符串 key 会造成额外内存开销。PEP 412 提出了 key-sharing dictionary，核心思想是把 keys 和 values 分离，让同类实例共享 keys table，每个实例只保存自己的 values array；PEP 原文说明了这种实现让实例 __dict__ 可以与同类其它实例共享 keys。

回到开头的 User：

class User:
    def __init__(self, name, score):
        self.name = name
        self.score = score

alice = User("alice", 10)
bob = User("bob", 20)

在 CPython 的常见路径中，alice.__dict__ 和 bob.__dict__ 可以共享表示属性名集合的 keys table。name 和 score 这两个属性名只需要在共享结构中保存一份；alice 与 bob 各自的 values array 保存不同值。属性读取 alice.score 经过 attribute lookup 后，如果最终落到实例 dict，底层可以用共享 keys table 确定属性位置，再从该实例自己的 values array 读取值。

key-sharing 的收益取决于实例形状是否稳定。大量实例在构造阶段设置同一组属性时，shared keys 的价值最大；如果某些实例不断增加独有属性，实例字典可能转向 combined table 或产生更高维护成本。PEP 412 对 split-table dictionaries 的描述也指出，对象 __dict__ 会以 split form 创建，同类实例可共享 keys；当 key 集合开始分化时，个别字典会惰性转成 combined-table form，从而保持语义正确。

这一路径也解释了 __slots__ 与普通实例 dict 的边界。__slots__ 把属性存储从 dict 迁移到类型定义的 slot 描述中，实例可以减少或取消 __dict__；key-sharing dict 则仍然使用 __dict__ 语义，只优化多实例共享属性名的内存成本。判断对象属性成本时，应先确认类是否有实例 dict，再判断该实例 dict 是否可能共享 keys，最后再讨论属性访问是否被 LOAD_ATTR specialization 命中。

在源码中，split table 的核心信号是 values 分离。combined table 的 value 存在 entry 中；split table 的 entry 主要保存 key 和 hash，value 放在 ma_values 指向的数组中。这个结构也带来一个阅读结论：实例属性字典看起来是普通 dict，但它的内部形态可能专门为对象系统优化。把实例属性查找理解成“普通映射查找加一层对象系统入口”，比把它完全等同于手写 {} 更准确。

64.4 dict resizing

dict resizing 解决容量、冲突和删除痕迹的再平衡问题。dict 插入时需要保证 table 中有足够 empty slot，让 probing 可以在较短路径内找到目标；删除时产生的 dummy slot 会保留探测链，但 dummy 累积后会拉长查找路径。resize 的职责因此包含两类动作：扩大 table 容量，以及在容量变化或重建时清理 dummy。

一次插入触发 resize 的常见原因是 usable entries 不足。CPython 的 keys table 维护可用计数和 entry 数量；当 active entries 加上历史删除痕迹使得可用空间下降时，新插入会先扩容或重建。扩容会改变 index table 的大小和 mask，所有 active key 都需要按新 table 重新建立索引。entries 中的 active 内容会被保留，index table 会重新计算。

下面的代码展示 resize 与语言语义之间的边界。代码不保证在某个固定插入次数触发 resize，因为阈值属于 CPython 实现细节；它展示的是 resize 发生后用户可见语义仍保持稳定：

items = {}
for number in range(1000):
    items[number] = number * 10

for number in range(0, 1000, 2):
    del items[number]

for number in range(1000, 1300):
    items[number] = number * 10

print(items[999])
print(list(items)[:3])

这段代码经历大量插入、删除和继续插入。CPython 可以在内部扩容或重建 table，但 items[999] 的查找语义不变，迭代顺序仍按保留下来的 key 与新插入 key 的顺序组织。工程上需要关注的是峰值内存和写入抖动：resize 期间需要新 table，并重新散列 active entries，短时间内会增加分配和复制成本。

对性能判断来说，resize 的成本集中出现在少数触发布局重建的插入上。多数插入只写入一个 empty 或 dummy slot；少数插入触发扩容或重建，会承担重新布局的成本。这就是 dict 插入平均很快但个别插入可能更贵的原因。分析延迟尖峰时，应把“这次插入是否触发 resize”与“单次 hash/equality 是否昂贵”分开。

split table 的 resize 还有一个对象系统边界。实例字典如果为了属性写入而扩展 key 集合，CPython 需要在共享 keys、实例 values array 和可能的 combined table 转换之间保持一致。大量对象在构造后继续动态增加不同属性，会削弱 key-sharing 的内存优势，并增加属性布局变化带来的维护成本。工程上，把实例属性集合稳定在构造阶段，有利于保持共享 keys 与属性访问缓存的命中。

源码阅读时，resize 相关判断可以按三层走：第一层看 table 是否还有 usable slot；第二层看 dummy 数量是否让重建有价值；第三层看当前是 combined 还是 split 形态。这样能把“字典变大了”拆成容量变化、探测路径变化和布局形态变化三个可观察问题。

64.5 hash strategy

hash strategy 连接正确性、性能和安全。dict 查找先用 hash 定位候选区域，再用 equality 确认 key；hash 决定探测起点和冲突形态，equality 决定最终命中对象。对不可变内置类型，CPython 可以提供稳定 hash；对自定义对象，开发者通过 __hash__ 和 __eq__ 参与这条路径。

正确性的第一条约束是：相等对象必须有相同 hash。否则两个逻辑相等的 key 可能进入不同探测路径，字典无法按映射语义维护唯一 key。正确性的第二条约束是：key 插入后参与 hash 和 equality 的状态应保持稳定。Python 允许对象内部状态变化，但作为 dict key 的状态变化会破坏查找前提。

下面这个例子展示“可变 hash key”的风险。代码可以运行，但它表达的是反例边界：

class MutableKey:
    def __init__(self, label):
        self.label = label

    def __hash__(self):
        return hash(self.label)

    def __eq__(self, other):
        return isinstance(other, MutableKey) and self.label == other.label

key = MutableKey("old")
cache = {key: "value"}
key.label = "new"

print(cache.get(key))
print(list(cache.keys())[0].label)

cache 仍然持有那个 key 对象，但查找时使用的新 hash 已经指向另一条探测路径。这个例子说明，dict 的 key 设计要围绕 hash 稳定性展开；对象身份稳定无法替代 hash 语义稳定。

性能层面，hash 分布影响冲突数量，equality 成本影响冲突后的比较成本。大量 key 落到同一 hash 时，probe sequence 会继续保证语义正确，但查找会退化为更多 slot 访问和更多 equality 调用。自定义 __eq__ 如果包含 I/O、复杂遍历或可变外部状态，会把 dict 查找拖入不可控成本路径。工程上应让 key 的 hash 计算短、稳定，让 equality 只比较决定身份的最小不可变字段。

安全层面，CPython 对 str 和 bytes 等类型使用 hash randomization，降低精心构造输入导致大量碰撞的拒绝服务风险。Python 命令行文档说明，hash randomization 默认启用，PYTHONHASHSEED 可以设置固定 seed；该机制让同一字符串在单个进程内 hash 稳定，但跨进程不保证同值 hash 数字相同，相关说明见 Command line and environment: PYTHONHASHSEED。

string hash cache 还解释了常见的名字查找成本。字符串作为标识符、属性名、dict key 高频出现，CPython 会缓存字符串对象的 hash，重复查找时可以减少 hash 计算成本。这个缓存只减少 hash 计算，不改变冲突后的 equality 路径，也不改变 dict 需要在命名空间变化时维护缓存失效的事实。

64.6 globals lookup optimization

globals lookup optimization 把 dict 从通用映射推进到解释器执行路径。函数中的全局名字读取通常对应 LOAD_GLOBAL：先查函数的 globals dict，再查 builtins dict。开头例子里的 users 和 bonus 都属于这类读取。没有优化时，每次执行 total("alice") 都要进行字典查找；在热路径中，CPython 会利用 namespace dict 的稳定性，把重复查找压缩成带 guard 的缓存读取。

PEP 509 提出了为 dict 添加私有 version 的动机：许多命名空间是 dict，优化需要快速判断命名空间是否变化；当 version 不变时，guard 可以用常数成本确认缓存仍有效。该 PEP 当前状态已经被后续实现演进覆盖，但它仍然清楚说明了 version tag 的设计动机：用 dict 的变化计数支撑 namespace cache。PEP 659 则描述了 specializing adaptive interpreter：指令可以在运行中变成更具体的 specialized instruction，并使用 inline cache 保存额外数据；其中 LOAD_GLOBAL_MODULE 可以在 globals keys 未变化时从缓存 index 读取值。

可以用下面的代码现象理解这条路径：

bonus = 5

def total(score):
    return score + bonus

print(total(10))
bonus = 7
print(total(10))

第一次和第二次调用之间，bonus 所在 globals dict 被写入。解释器如果曾经把 bonus 的位置缓存下来，就需要通过 dict version、keys version 或类似 guard 确认缓存是否仍然可用。写入后 guard 失败，解释器回到通用查找或重新 specialization，随后再建立新的缓存状态。这个过程保证了 Python 的动态语义：全局名字可以被重新绑定，优化只能在 guard 成立时使用。

LOAD_GLOBAL 的优化有三个层级。第一层是语言语义：普通名字读取在 local 之外会查 globals 与 builtins。第二层是 dict 事实：globals 与 builtins 在 CPython 中通常是真实 dict，可以携带内部版本和 keys 状态。第三层是解释器执行：specialized opcode 把“查 key”改成“验证 namespace 状态后按缓存位置取值”。三个层级同时成立，优化才安全。

这条路径也解释了为何 monkey patching 和动态执行会影响热路径性能。修改 module globals、替换 builtins、通过 exec 写入 globals dict，都会改变 namespace 状态并让已有 guard 失效。语义上这些操作完全合法；性能上它们会让解释器更频繁回到通用查找或重新 specialization。判断全局名字读取成本时，应先看它是否处在热循环中，再看 globals/builtins 是否稳定，最后看该 Python 版本的 opcode specialization 是否能覆盖这种形态。

本章到这里把 dictobject.c 的主线收束成一个检查顺序：普通映射先看 compact layout，再看 hash/probing；属性字典再看 key-sharing；频繁写入再看 resize 与 dummy；全局名字读取再看 version tag 和 inline cache。这个顺序能把一个表层的 dict 问题拆成内存布局、查找路径、状态变化和解释器优化四个层级。

最小自检任务

阅读下面代码，不运行程序，判断三个问题：records 删除再插入后迭代顺序怎样变化；两个 BadHash key 为什么都能被取回；第二次调用 read_total() 前修改 bonus 会怎样影响全局名字缓存。

class BadHash:
    def __init__(self, label):
        self.label = label

    def __hash__(self):
        return 1

    def __eq__(self, other):
        return isinstance(other, BadHash) and self.label == other.label

records = {"x": 1, "y": 2, "z": 3}
del records["y"]
records["y"] = 20

left = BadHash("left")
right = BadHash("right")
lookup = {left: 100, right: 200}

bonus = 5

def read_total():
    return records["y"] + lookup[BadHash("right")] + bonus

first = read_total()
bonus = 7
second = read_total()

答案要点

records 的迭代顺序是 x, z, y，因为删除 y 后重新插入会把它放到插入顺序末尾；更新已有 key 的 value 才会保持原位置。CPython 的 compact dict 通过紧凑 entries 顺序表达这种语言语义，同时在 index table 中保留查找需要的状态。

left 和 right 的 hash 都是 1，它们会发生冲突，但 probing 会沿探测序列继续寻找候选 slot。命中候选 entry 后，dict 还会用 equality 区分 label，所以 BadHash("right") 可以取回 right 对应的 value。这个例子成立的前提是 __eq__ 与 __hash__ 对相等对象保持一致，并且参与比较的状态在查找期间稳定。

修改 bonus 会改变 globals dict 的状态。解释器如果已经为 LOAD_GLOBAL bonus 建立 inline cache，下一次执行前需要通过 dict 版本或 keys 状态 guard 判断缓存是否仍可用。guard 失效后走通用查找或重新 specialization，语义结果是 second 使用新的 bonus = 7，优化必须尊重 Python 的动态绑定规则。

本章知识点总结

• compact dict：CPython 现代 dict 把稀疏 dk_indices 和紧凑 dk_entries 分开，查找走索引，迭代走 entries 顺序。
• 插入顺序：Python 3.7 起 dict 插入顺序是语言保证，更新已有 key 保持位置，删除后重新插入进入末尾。
• combined table：普通映射通常把 key、hash、value 放在 entries 中，适合 key 集合频繁变化的场景。
• split table：实例属性字典可以把 shared keys 与 per-instance values 分离，降低同类大量实例的属性名重复存储成本。
• probing：哈希冲突时，CPython 使用 hash、mask、perturb 和递推探测序列继续寻找候选 slot。
• dummy slot：删除后的 dummy 保留冲突链信息，查找 miss 时 dummy 没有终止资格。
• resize：扩容或重建会重新建立 index table，并清理删除痕迹带来的探测成本。
• hash 契约：相等对象必须拥有相同 hash，作为 dict key 的对象应保持参与 hash 与 equality 的状态稳定。
• hash randomization：CPython 对部分内置类型使用随机化 hash seed，降低碰撞型拒绝服务风险，同时保持单进程内 hash 稳定。
• 字符串缓存：字符串 hash cache 减少重复名字查找中的 hash 计算成本，但不替代 equality 和命名空间失效检查。
• dict version：命名空间 dict 的内部版本或 keys 状态让解释器可以用 guard 判断缓存是否仍然有效。
• 全局查找优化：LOAD_GLOBAL 可以通过 inline cache 把重复 globals/builtins 查找压缩成“验证状态后按缓存位置取值”。
• 动态语义边界：修改 globals、builtins 或通过动态执行写入命名空间会让相关缓存失效，解释器必须回到语义正确的查找路径。
• 阅读顺序：分析 dict 问题时，先定位 compact layout，再追踪 hash/probing，再检查 key-sharing、resize 和 namespace cache。