Chapter 36: Dict Architecture

dict 是 Python 运行时最常见的容器之一，也是 namespace、实例属性、模块全局变量和关键字参数等机制背后的基础结构。读完本章后，读者应能追踪一次键查找如何从 key、hash、索引槽、entry 和 equality 比较进入结果判断，也能区分普通字典、实例属性字典和 namespace 字典在存储目标上的差异。

本章以一个贯穿片段为材料。它同时覆盖三类 dict 使用场景：普通映射、实例属性存储、module globals。正文会持续回到这个片段，用它解释插入顺序、探测、扩容、split table、combined table、globals lookup 和 attribute storage 的 runtime 关系。

class Profile:
    pass

profile_a = Profile()
profile_b = Profile()

profile_a.name = "Ada"
profile_a.score = 10
profile_b.name = "Guido"
profile_b.score = 99

record = {"name": "Ada", "score": 10}
record["score"] = 11
del record["name"]
record["name"] = "Grace"

globals()["threshold"] = 10
result = record["score"] > threshold

这段代码中的 record 是显式创建的普通 dict，profile_a.__dict__ 和 profile_b.__dict__ 是实例属性存储，globals() 返回当前模块的 global namespace 字典。三者都使用键到值的映射语义，但它们服务的上层语义不同：record 服务业务数据，实例字典服务 attribute lookup，global namespace 服务名字解析。

版本边界需要先固定。Python 语言层面从 3.7 起保证普通 dict 保留插入顺序；Python 官方文档把更新已有 key、删除后重新插入的顺序行为写入 Mapping Types — dict。CPython 3.6 已经具备该实现行为，但当时属于实现细节。CPython 内部结构会随版本调整，本章只建立可迁移的阅读模型；涉及源码时以 Objects/dictobject.c 和 PEP 412 的结构说明作为方向，不声称读者本地源码具备完全相同的字段排列。

36.1 Compact hash table and insertion order

dict 的主问题可以拆成两个同时成立的目标：按 key 快速查找 value，并按插入顺序迭代。哈希表负责第一个目标，compact layout 负责把顺序信息和存储密度组织在同一套结构中。这里的 compact 指 CPython 把索引区和 entry 区分开，索引区保存“某个哈希槽指向哪一个 entry”，entry 区按插入推进保存 key、value 和必要的 hash 信息。

在贯穿片段中，record = {"name": "Ada", "score": 10} 会按源码字面顺序插入两个 key。迭代 record 时得到的是 "name" 后跟 "score"。随后 record["score"] = 11 修改已有 key 的 value，它更新原 entry 的值，顺序位置保持在原处。del record["name"] 删除 key 后，record["name"] = "Grace" 作为一次新插入发生，"name" 进入当前顺序的末尾。这个行为来自语言文档约定，读 CPython 源码时应把它视为必须被实现维持的语义结果。

可以把普通 dict 的结构理解成两层表。第一层是稀疏的 index table，它的长度通常大于实际元素数量，用来降低碰撞后继续探测的概率。第二层是紧凑的 entry table，它保存实际条目，并以插入推进的次序增长。查找时先走 index table；迭代时主要沿 entry table 的有效条目推进。这样，查找路径和迭代路径使用不同入口，却共同维护同一组 key-value 关系。

下面的图只表达阅读模型，不绑定某个 CPython 小版本的字段名。它说明一次普通查找如何从 key 走到 value。

图中的 entry 是实际保存 key-value 的位置，index slot 是哈希槽。一次命中需要两个条件同时成立：hash 值可把搜索带到候选 entry，候选 key 与目标 key 通过 equality 比较确认相等。hash 相同只能说明两个 key 进入同一候选区域，最终相等性仍由 key 的比较协议确认。

compact layout 的工程后果体现在三个地方。第一，迭代顺序由 entry 的插入次序表达，普通遍历无需按稀疏索引槽扫描。第二，小字典占用的指针和空洞数量减少，模块、对象属性、函数局部辅助结构等高频字典能获得更好的内存局部性。第三，删除会留下对探测有意义的历史状态；删除后的槽位处理必须同时服务后续查找和后续插入。

这个模型解释了贯穿片段里的顺序现象。record["score"] = 11 不追加 entry，因为 key 已存在；del record["name"] 使原 key 失效；重新写入 "name" 追加一个新的顺序位置。读到“字典有序”时，应把它定位为迭代和显示结果的语义约束；读到“哈希表”时，应把它定位为查找和更新的算法结构。

36.2 Probing, resizing, and hash randomization

哈希表查找从 hash(key) 的结果开始。hash 是把 key 映射成整数的协议入口；probe 是发生碰撞时继续检查后续槽位的过程；resize 是元素和空洞增长到阈值后重建更大表的过程。三者共同决定平均查找成本、极端碰撞成本和攻击输入下的安全边界。

贯穿片段里，record["score"] 的读取大致经历四步：计算字符串 key 的 hash；把 hash 映射到当前 index table 的一个槽位；检查槽位指向的 entry；确认 entry 中的 key 与 "score" 相等后返回 value。多数正常输入在很短 probe 链内完成。这个平均成本接近常数时间，但它依赖 hash 分布、负载因子和碰撞数量。

碰撞指两个不同 key 被映射到同一个起始槽或同一条 probe 路径。CPython 使用开放寻址类策略，碰撞后在同一个表内寻找下一个候选槽。开放寻址的含义是条目仍放在表结构内部，冲突处理通过继续探测完成。删除时会出现 dummy 状态，它表示“这里曾经有条目，查找还要继续”。如果删除直接把槽标成 empty，后续查找可能在到达真正目标前提前结束。

可以用一个短例子观察 equality 在碰撞后的作用。这个例子不要求读者运行，只用于说明查找判断顺序。

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

    def __hash__(self):
        return 42

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

left = CollidingKey("left")
right = CollidingKey("right")
table = {left: "L", right: "R"}

left 和 right 的 hash 相同，因此插入 right 时会进入碰撞处理。字典仍能同时保存两个条目，因为 equality 比较会区分 label。查找 table[right] 时，hash 先把搜索带到候选区域；遇到 left 这类 hash 相同但 equality 失败的 entry 后，probe 继续推进；遇到 right 后返回对应 value。由此可见，hash 决定候选路径，equality 决定最终命中。

扩容解决的是 probe 链变长和可用槽减少的问题。字典扩容时会分配新的索引规模，并把仍有效的 entry 重新布置到新索引表中。扩容的触发条件与“实际元素数量”和“可用槽数量”有关，删除留下的 dummy 也会影响后续表维护。业务代码看到的是键值关系和插入顺序继续成立；CPython 内部看到的是索引表、entry 表和 dummy 状态被整理。

hash randomization 解决的是另一类问题：攻击者构造大量碰撞 key 时，普通哈希表可能退化成高成本路径。Python 对 str 和 bytes 等类型使用进程级随机种子，使它们的 hash 在单个进程内稳定，在多次解释器启动之间难以预测。命令行和环境变量文档中，PYTHONHASHSEED 可固定种子，也可通过 0 关闭随机化，见 PYTHONHASHSEED。

hash randomization 不改变“同一插入序列下 dict 迭代按插入顺序”的语言结论。它改变的是内部 hash 值和 probe 路径。需要注意的是，若字典由一个无序来源构造，例如先遍历 set 再插入字典，最终插入序列本身可能受前置容器影响。排查顺序应先固定输入插入序列，再分析字典内部查找成本。

36.3 Split table, combined table, and key-sharing dict

普通 dict 和实例属性 __dict__ 的存储目标不同。普通 dict 通常把 key 与 value 放在同一套条目结构中，这类布局称为 combined table。实例属性字典常见的优化目标是“同一个类的大量实例拥有相同属性名”，因此 CPython 可以让这些实例共享 key 结构，各自保存 value 数组，这类布局来自 PEP 412 的 key-sharing dictionary 设计，见 PEP 412。

贯穿片段里的 profile_a 与 profile_b 属于同一个类，并且都写入 name 和 score。在面向对象代码中，这种模式很常见：__init__ 通常为每个实例写入同一组属性名。key-sharing 的收益来自把属性名集合从“每个实例一份”变成“同类实例共享一份 keys table”，每个实例只保留自己的 values。profile_a.name 和 profile_b.name 共享属性名 name 的结构位置，但它们的 value 分别是 "Ada" 和 "Guido"。

combined table 可以用普通业务字典来理解。record 的 key 集合和 value 集合属于同一个字典对象，"name" 与 "Grace"、"score" 与 11 一起服务当前映射。它适合显式字典、模块字典和多数非实例属性的映射场景。combined 的优势是结构直接，查找到 entry 后即可拿到 key 和 value。

split table 可以用实例属性来理解。多个实例共享一套 key 描述，每个实例的 values 数组保存对应位置的值。读取 profile_a.score 时，属性查找路径先确定实例可使用的属性存储，再根据共享 key 结构定位 score 的位置，最后从 profile_a 自己的 values 中取值。读取 profile_b.score 走相同的 key 位置，但 value 来源于另一个实例。

这种优化有明确边界。若某个实例开始写入同类其他实例没有的属性，key 集合会出现分化。CPython 可以在需要时把个别字典转换成更适合当前形态的布局。正文不依赖具体转换阈值，因为那属于实现策略；稳定结论是：实例属性字典的内存模型要把“属性名集合”和“实例自己的属性值”分开看。

下面的简化图展示 combined 与 split 的差异。图中 keys 表示 key 结构，values 表示每个字典自己的 value 存储。

图的关键点是 ownership。普通字典拥有自己的 key-value 存储；同类实例可以共享属性名结构，但实例值归各自对象所有。排查对象内存异常时，看到大量同类实例并且属性集合稳定，应优先想到 key-sharing 能降低属性名重复存储；看到大量字典 key 集合彼此差异大，应按普通 combined table 的成本分析。

36.4 Globals lookup and attribute storage

dict 在 Python runtime 中还承担 namespace 和属性存储等 runtime 角色。module globals 是字典，实例属性通常通过字典或等价存储表达，类 namespace 也以映射形式参与类型创建。名字解析和属性访问表面上属于语言语义，落到 CPython runtime 时会频繁进入 dict 查找、版本检查和缓存路径。

贯穿片段里的 globals()["threshold"] = 10 把名字 threshold 写入当前模块的 global namespace。随后表达式 record["score"] > threshold 读取 threshold 时，执行路径会把普通名字查找导向当前 frame 的 globals，再在未命中时查 builtins。这里的 globals 是一个 dict，因此全局变量读取也需要 key 查找，只是 key 通常是字符串名字。

CPython 3.11 之后的解释器具备 adaptive bytecode 和多种 inline cache。LOAD_GLOBAL 这类指令可能缓存 globals 和 builtins 的版本状态，用来减少重复字典查找成本。缓存不改变语义：当 global namespace 发生会影响查找结果的变更时，解释器需要让缓存失效或转入保守路径。工程判断应区分语义层和实现层：语义层仍是 globals 到 builtins 的名字解析；实现层可以通过版本标记和 inline cache 加速常见路径。

实例属性也把 attribute storage 带回 dict。执行 profile_a.score = 10 时，写入目标是实例的属性存储；常见情况下这个存储可通过 profile_a.__dict__ 观察。执行 profile_a.score 时，完整属性查找还要考虑 data descriptor、实例属性、class attribute 和 MRO，但实例属性命中阶段会进入实例存储。这里的 dict 不是属性查找的全部，却是存放动态实例属性的核心容器。

类 namespace 与实例 namespace 的角色不同。类体执行时会生成一个 namespace，之后 type.__new__ 用这个 namespace 构造 class object。类对象上的属性读取通常通过类型对象和 MRO 查找，并暴露为只读视图或受控映射形态。实例 __dict__ 负责每个对象自己的动态属性，类 namespace 负责类级别属性、方法和 descriptor。两者都借助映射结构，但查找入口和所有权不同。

可以用下面的顺序分析贯穿片段的最后一行。

result = record["score"] > threshold

record["score"] 是显式 mapping subscription，它调用 dict 的 key 查找路径。threshold 是普通名字读取，它先由当前 frame 的名字解析规则决定查找哪个 namespace，再进入 globals 字典。> 比较拿到两个对象后进入数值比较协议。三个动作共享同一行源码，但 runtime 入口分别是 mapping lookup、name resolution 和 comparison。把它们拆开，才能准确定位一次慢查找或异常来自哪一层。

这个区分也影响性能判断。业务字典慢，通常先看 key 的 hash/equality、碰撞、字典规模和构造方式。全局变量慢，除了字典查找，还要看解释器是否能使用稳定的缓存路径。属性访问慢，还要看 descriptor、实例布局、类层级和缓存失效。把所有现象都归因到“dict 查找慢”会丢失关键证据；稳定做法是先确认上层语义入口，再进入对应的字典存储模式。

36.5 Dict architecture checklist

阅读 dict 行为时，检查顺序应从语义入口开始，再进入内部结构。第一步确认操作类型：d[key] 是 mapping lookup，name 是 namespace lookup，obj.attr 是 attribute lookup，**kwargs 是调用协议中的关键字映射。入口不同，前置规则不同，最后进入的字典形态也可能不同。

第二步确认 key 的稳定性。可作为字典 key 的对象需要具备稳定 hash 与 equality 关系。对象放入字典后，参与 hash 或 equality 的状态应保持稳定。若自定义对象的 __hash__ 依赖可变字段，后续字段变化会让原 key 难以按同一逻辑找回。这个问题经常表现为“对象明明在字典里，读取却失败”。

第三步确认 hash 与 equality 成本。普通字符串 key 的 hash 会被缓存，比较也有高度优化；自定义 key 可能在 __hash__ 或 __eq__ 中执行昂贵逻辑。碰撞多时，equality 调用次数会上升。排查性能时，应把“hash 计算成本”“probe 次数”“equality 成本”拆开观察。

第四步确认表规模和变更模式。频繁插入会触发扩容；频繁删除会产生 dummy 状态并影响后续查找；大量短生命周期字典会把成本转移到对象分配和内存局部性。若代码反复构造相同 key 集合的对象，实例 key-sharing 可能降低属性存储成本；若代码反复构造显式业务字典，combined table 是主要分析对象。

第五步确认顺序来源。dict 保留插入顺序，更新已有 key 不改变位置，删除后重新插入会进入末尾。若最终顺序异常，应先追踪实际插入序列。由无序容器、外部输入、并发回调或不同进程 hash seed 间接影响的构造过程，可能让插入序列本身变化。字典只保存它接收到的插入历史。

第六步确认 namespace 场景。globals、builtins、class namespace 和 instance __dict__ 都可以借助字典或映射结构，但它们被 frame、type object、descriptor 和解释器缓存包裹。定位名字或属性问题时，先看语言层查找顺序，再看字典本身。这样能把 NameError、AttributeError、KeyError 和性能退化分到正确层级。

下面的最小检查表可以迁移到同类问题：

• 入口：当前操作是 mapping lookup、name lookup、attribute lookup，还是调用协议中的 keyword mapping。
• key：key 是否 hashable，hash 与 equality 是否在生命周期内保持一致。
• hash：hash 是否稳定，是否涉及随机化，是否可能集中碰撞。
• probe：碰撞后是否需要多次 equality 比较，删除历史是否让探测链变长。
• resize：插入、删除和增长模式是否导致频繁重建索引表。
• storage：当前字典更接近 combined table，还是实例属性场景下的 split/key-sharing 结构。
• order：最终顺序是否来自实际插入历史，更新、删除、重插入是否被正确区分。
• cache：globals 和 attribute 访问是否还受解释器 inline cache、版本标记或类型缓存影响。

回到贯穿片段，record 的行为用 key、hash、probe、resize 和 insertion order 就能解释；profile_a 与 profile_b 的属性存储需要加入 split/key-sharing 的内存模型；threshold 的读取需要把 frame 的 globals lookup 放在字典查找之前。这样，本章的主问题就收束为一个判断：dict 是同一套映射基础结构，但它在不同 runtime 入口下承担不同职责，分析时必须先定位入口和所有权，再进入哈希表细节。

最小自检任务

阅读下面代码，判断 data 的迭代顺序、a.x 与 b.x 的存储关系，以及 limit 的读取入口。要求说明每一步对应的 dict 行为。

class Item:
    pass

a = Item()
b = Item()
a.x = 1
a.y = 2
b.x = 10
b.y = 20

data = {"x": 1, "y": 2}
data["x"] = 3
del data["y"]
data["y"] = 4

globals()["limit"] = 2
answer = data["x"] > limit

答案要点

data 最终按 "x"、"y" 的顺序迭代。data["x"] = 3 更新已有 key 的 value，"x" 的顺序位置保持原处；删除 "y" 后重新插入 "y"，它进入当前顺序末尾。由于这里只有两个 key，最终顺序看起来仍是 "x" 后跟 "y"，但原因分别是更新保序与重插入追加。

a.x 与 b.x 属于同一个类的实例属性场景。稳定属性集合下，CPython 可以让同类实例共享属性名结构，并让每个实例保存自己的 values。x 这个属性名可以共享结构位置，a 的 value 是 1，b 的 value 是 10。这是 key-sharing 的内存优化结论，语言层可观察语义仍是两个实例拥有各自属性值。

limit 的读取入口是普通名字解析。当前 frame 先按名字解析规则查 globals，再查 builtins；在本例中 globals()["limit"] = 2 已把它写入模块 global namespace。data["x"] 是显式字典 key 查找，limit 是 namespace lookup 后进入 globals 字典。二者都可能使用 dict，但语义入口不同。

本章知识点总结

• 入口优先：分析 dict 行为要先确认 mapping、namespace、attribute 或 keyword mapping 的入口。
• 哈希定位：hash 把 key 带到候选槽位，最终命中还要经过 equality 确认。
• 探测路径：碰撞会触发 probe，dummy 槽保证删除历史不会截断后续查找。
• 扩容触发：插入增长和删除留下的历史状态会影响索引表重建与查找成本。
• 顺序语义：Python 3.7 起 dict 语言层保证插入顺序，更新保留位置，删除后重插入进入末尾。
• 紧凑布局：compact layout 用稀疏索引服务查找，用紧凑 entry 服务存储和迭代。
• combined 表：显式业务字典通常把 key 与 value 放在同一套条目结构中。
• split 表：实例属性字典可以共享属性名结构，并让每个实例保存自己的 values。
• namespace 字典：globals 和 builtins 查找会进入字典，但它们受 frame 名字解析规则控制。
• 属性存储：实例属性读取涉及属性查找规则，其中实例存储阶段常由字典或等价结构承载。
• 随机化边界：hash randomization 改变内部 hash 和 probe 路径，同一插入序列下 dict 迭代仍遵守插入顺序。
• 排查顺序：同类问题应按入口、key、hash、probe、resize、storage、order 和 cache 的顺序收集证据。