Chapter 38: Set Architecture

读完本章后，读者应能追踪一个元素进入 set、被 in 查询、参与并集或交集、再被迭代输出时的 runtime 路径，并据此判断什么时候选择 set，什么时候保留 list、tuple 或 dict。本章的主问题是：set 为什么能把唯一性、成员查询和集合运算压到一套哈希表结构里，同时它又对元素、顺序和可变性提出了哪些约束。

Python 3.14 的 set types 文档把 set 和 frozenset 定义为由 hashable 对象组成的无序、去重集合，典型用途包括 membership testing、去重、交集、并集、差集和对称差集。这个语义描述决定了本章的两条主线：一条是语言层面的唯一性，另一条是 CPython 层面的 hash table 查找路径。语言文档给出接口契约，CPython 的 Objects/setobject.c 给出一种主流实现策略；二者需要分层阅读。

本章使用下面这段代码作为贯穿材料。它看起来只是把重复标签去掉，并检查一个候选标签是否存在；实际路径会经过 __hash__、__eq__、哈希槽位、collision probing、resize、集合运算和迭代顺序边界。

from dataclasses import dataclass

@dataclass(frozen=True)
class FeatureTag:
    namespace: str
    name: str

raw_tags = [
    FeatureTag("compiler", "ast"),
    FeatureTag("runtime", "frame"),
    FeatureTag("compiler", "ast"),
]

active_tags = set(raw_tags)
query_tag = FeatureTag("compiler", "ast")
required_tags = {FeatureTag("compiler", "ast"), FeatureTag("memory", "gc")}

print(query_tag in active_tags)
print(active_tags & required_tags)

FeatureTag 使用 frozen=True，所以它的比较字段稳定，dataclass 能为它生成可用的 hash。set(raw_tags) 会把两个值相等的 FeatureTag("compiler", "ast") 合并为一个元素；query_tag in active_tags 会复用同一套 hash/equality 路径。这个例子后续会不断回到同一个问题：集合里的“相同元素”由 equality 判断确认，但快速定位先依赖 hash。

38.1 Hash set layout and probing strategy

set 的底层目标是用一张哈希表表达“唯一元素集合”。它保存元素对象引用，并保存与元素相关的 hash，用槽位状态区分空槽、活动元素和删除后留下的占位。与 dict 相比，set 没有 value 字段；它关心的答案是“这个元素是否已经出现”，所以槽位中最关键的信息是 key 与 hash。

在贯穿例子中，构造 active_tags 时，解释器会依次处理 raw_tags 中的三个对象。每个对象先得到 hash 值，hash 的低位配合表的 mask 定位初始槽位；槽位为空时可以插入，槽位已有元素时先比较 hash，再在必要时执行 equality 比较。第三个 FeatureTag("compiler", "ast") 的 hash 与第一个相同，并且 equality 返回 True，所以集合保留一个活动元素。

下面的图只描述成员查询和插入共享的主路径，省略引用计数、错误传播和 free-threaded 分支；这些实现细节会影响性能和并发边界，但不改变本节要建立的对象关系。

这条路径解释了 set 的两个外部现象。第一，x in s 通常比在 list 中线性扫描更适合高频成员查询，因为它先用 hash 缩小候选槽位范围。第二，元素必须 hashable，因为表的入口位置来自 hash；如果对象无法提供稳定 hash，集合无法把后续查询导向插入时的位置。

CPython 当前源码在 Objects/setobject.c 中使用 hybrid probing：先做一段连续槽位探测，再用 hash 的高位和扰动公式跳到新的位置。源码注释说明连续访问有利于内存局部性，随机化式探测有助于打散长 collision chain。阅读源码时可以从 set_do_lookup、set_add_entry_takeref 和 set_table_resize 这几个名字建立路径：lookup 找槽位，add 处理插入和重复命中，resize 重建表。

这个实现属于 CPython 策略，语言层只承诺集合语义和操作结果。PyPy、MicroPython 或未来 CPython 版本可以使用不同布局，只要保持 set 的语义契约。工程判断应写成“依赖 set 的成员查询语义与预期哈希性能”，少把某个版本的槽位公式写进业务正确性。

38.2 Collision handling and resizing

collision 是多个元素经过 hash 和 mask 后进入同一段候选槽位的情况。collision 本身不表示元素相等，它只表示这些元素需要在同一条 probe 路径上接受进一步检查。真正的命中条件仍然是 hash 相同且 equality 确认相等；hash 不同的对象可以共享初始槽位，hash 相同的对象也可以在 equality 上分开。

用贯穿例子改造一个场景更容易看出边界。假设某个类型的 __hash__ 把所有对象都返回同一个整数，set 仍然能保持去重语义，因为 equality 还能区分对象；但每次查询都要沿着更长的 probe 路径检查候选元素，成员查询会接近线性扫描。语义仍正确，性能模型已经退化。

class SlowHashTag:
    def __init__(self, namespace: str, name: str):
        self.namespace = namespace
        self.name = name

    def __eq__(self, other):
        if not isinstance(other, SlowHashTag):
            return NotImplemented
        return (self.namespace, self.name) == (other.namespace, other.name)

    def __hash__(self):
        return 1

items = {SlowHashTag("compiler", str(index)) for index in range(1000)}
probe = SlowHashTag("compiler", "999")
print(probe in items)

这段代码的结果仍是 True，因为 equality 能找到值相等的对象。成本增加来自 collision path：所有对象进入相似的探测区域，表需要执行更多槽位检查和更多 equality 调用。这个例子说明了 hash 的工程职责：它不直接决定相等性，但它决定候选范围是否足够分散。

删除也会影响后续探测。开放寻址哈希表在删除元素时通常会留下 dummy slot，因为一个失败查询需要沿着插入时可能经过的路径继续向后找。如果删除后直接把槽位清成空槽，后续查询可能提前停下，导致已经存在的元素被判为缺失。CPython 使用 fill 和 used 区分“活动元素数量”和“活动元素加 dummy 数量”，源码中的 resize 逻辑会在表变稠或 dummy 过多时重新分配并重插活动元素。

resize 的意义是恢复 probe 路径质量。随着元素增加，表的空槽减少，失败查询和插入需要检查更多位置；随着删除增加，dummy 会延长失败路径。CPython 源码中可以看到根据 fill 与 mask 的关系触发 set_table_resize，并在重建时清理 dummy。这个策略让平均成员查询保持接近常数时间，但它同时引入扩容时的批量重建成本。

对工程代码来说，collision 和 resize 带来的结论很直接：高频 membership 场景适合使用 set，前提是元素 hash 分布合理；批量构建比边查边改更容易形成稳定成本；删除很多元素后的集合可能经历重建，内存占用和一次操作耗时都可能出现阶段性变化。

38.3 Set operations and hash invariant

集合运算把成员查询扩展成批量路径。并集把多个输入的元素插入新集合或当前集合；交集保留同时出现在多个集合中的元素；差集保留左侧集合中没有出现在右侧输入里的元素；对称差集保留只出现在其中一侧的元素。Python 文档把这些操作作为 set 与 frozenset 的共同能力，并说明方法形式可以接受 iterable，运算符形式要求集合操作数。

贯穿例子中的 active_tags & required_tags 会得到只包含 FeatureTag("compiler", "ast") 的集合。运行时可以把这件事理解为：遍历某一侧的元素，把每个元素拿到另一侧执行 membership 测试，命中则加入结果。实际 CPython 会根据操作类型、对象类型和大小做不同优化，但稳定模型是“批量遍历 + 哈希成员判断 + 构造结果或原地更新”。

hash invariant 是集合正确性的核心约束：相等对象必须拥有相同 hash，并且对象作为集合元素期间，参与 hash 和 equality 的状态应保持稳定。Python data model 的 __hash__ 文档对 __hash__ 的要求也沿着这个方向定义：被 hash collection 使用的对象，如果 equality 认为相等，就需要给出相同 hash；可变且按值比较的对象通常不应暴露 hash。

下面的对象展示了破坏稳定性的后果。这个例子不追求跨版本输出一致，它用来说明对象状态变化如何让集合中的元素留在旧的 hash 位置。

class MutableTag:
    def __init__(self, namespace: str, name: str):
        self.namespace = namespace
        self.name = name

    def __eq__(self, other):
        if not isinstance(other, MutableTag):
            return NotImplemented
        return (self.namespace, self.name) == (other.namespace, other.name)

    def __hash__(self):
        return hash((self.namespace, self.name))

key = MutableTag("compiler", "ast")
items = {key}

key.name = "parser"
print(key in items)
print(MutableTag("compiler", "parser") in items)

这段代码的判断结果容易让读者误判。key 对象仍然被集合引用着，但它插入时使用的是旧 hash；修改字段后，再次查询会根据新 hash 走另一条 probe 路径。集合没有机会自动搬迁这个对象，因为普通属性赋值和集合内部槽位之间没有回调关系。稳定做法是把集合元素设计成不可变值对象，例如 FeatureTag 使用 frozen=True，或使用不可变字段组成 tuple。

set 与 frozenset 的区别也落在这个约束上。set 是可变容器，自身没有 hash，因而无法作为另一个集合的元素；frozenset 内容固定，满足 hash collection 对稳定性的要求，可以作为 dict key 或 set element。表示“集合的集合”时，内部集合应使用 frozenset，外层容器再根据是否需要修改选择 set 或 frozenset。

集合运算的性能判断也要回到 hash invariant。交集、差集和 subset 判断通常依赖大量 membership 测试，元素 hash 分布差或 equality 成本高时，批量操作会被放大。把一个大对象图塞进 __eq__，或让 __hash__ 每次重新计算昂贵结构，都会把集合操作的成本从表结构转移到对象协议上。

38.4 Set iteration and ordering boundary

set 是 unordered collection，语言层没有插入顺序承诺。Python 文档明确说明集合不记录元素位置或插入顺序，也不支持 indexing、slicing 或序列式行为。这个边界需要和 dict 分开记忆：现代 dict 保留插入顺序，set 的接口契约仍然围绕成员关系和集合代数展开。

迭代 active_tags 时，解释器遍历的是哈希表中的活动槽位，所以输出顺序会受到 hash、表大小、插入和删除历史、resize 以及实现版本影响。对同一个未修改集合，在同一个 CPython 进程里多次迭代经常会观察到相同顺序；这个观察属于当前实现表现，工程契约应写成：需要稳定输出时显式调用 sorted()，或在业务层保留一个顺序容器。

字符串和 bytes 的 hash randomization 进一步扩大了跨进程顺序差异。Python data model 说明 str 和 bytes 的 hash 默认带随机盐，在单个进程内保持常量，但在不同解释器启动之间不可预测；文档同时说明 hash 变化会影响 set iteration order，并且 Python 从未保证这个顺序。由此可得出一个直接判断：测试断言和序列化输出不应依赖 set 的遍历顺序。

下面的代码适合说明“内容相同”和“输出顺序稳定”是两个问题。

tags = {"ast", "frame", "gc", "dict"}

print(tags)
print(sorted(tags))

第一行展示集合自身的 repr，它可以在不同进程、不同版本或不同构建上呈现不同顺序。第二行把集合内容转成有序列表，排序规则由元素比较决定，适合日志、快照测试、文档输出和可复现构建。这里的关键判断是：set 负责成员关系，排序应由调用方显式表达。

迭代期间修改集合还会触发运行时边界。Python 容器迭代通常要求结构在迭代期间保持稳定；对 set 边迭代边增删元素会引发错误或得到难以维护的控制流。稳定写法是先收集待变更元素，再在迭代结束后执行更新，或使用集合表达式构造新集合。

current = {"ast", "frame", "gc"}
removed = {tag for tag in current if tag.startswith("g")}
current -= removed

这段写法把“选择哪些元素”和“修改集合结构”分成两个阶段。第一阶段只读取 current，第二阶段批量修改 current。这个顺序和哈希表内部 resize、dummy cleanup、probe path 都保持清晰边界，也让读者在排查时更容易定位状态变化。

38.5 Set architecture checklist

选择 set 时先看语义目标。目标是去重、成员查询、交集、并集、差集、subset 判断时，set 的模型正好匹配；目标是保留位置、按插入顺序输出、按下标访问、保存 key 到 value 的映射时，应把 list、tuple 或 dict 放进比较范围。容器选择先由语义决定，再由性能验证补充。

第二步检查元素协议。元素必须 hashable；相等对象必须返回相同 hash；对象进入集合后，参与 hash 与 equality 的状态应保持稳定。值对象优先使用 tuple、frozenset、frozen dataclass 或只读字段组合。按值比较的可变对象进入集合，会把普通属性修改变成哈希表定位错误。

第三步检查查询模式。大量 x in s、去重和批量集合运算通常适合 set；一次性小列表、顺序很重要的扫描、需要保留重复次数的统计场景，可能由 list 或 collections.Counter 表达得更清楚。set 的优势来自 hash 定位，hash 质量差或 equality 成本高时，需要重新评估对象设计。

第四步检查修改模式。持续插入会触发 resize，持续删除会制造 dummy slot，批量更新可能先扩容再重插。对热点集合来说，批量构建、批量差集和新集合替换通常比在复杂循环里交错增删更容易分析。需要长期驻留的大集合时，还要关注内存占用、峰值扩容和删除后的表重建。

第五步检查顺序边界。for x in s 的顺序不写入业务契约；日志、测试快照、缓存 key、网络输出和持久化文件需要稳定顺序时，显式转换为排序后的序列。排序成本应在调用点承担，因为它代表一个新的需求：从集合关系转向有序表示。

最后把源码阅读顺序固定下来：先从 Python 现象确认操作种类，再看元素的 __hash__ 与 __eq__，接着判断是否会进入大量 membership 测试，然后分析 collision、resize、dummy 和迭代顺序。源码层可沿 set_do_lookup、set_add_entry_takeref、set_table_resize 阅读；语言层以 Python 3.14 的 set / frozenset 文档和 data model 的 __hash__ 约束作为接口边界。

最小自检任务

阅读下面的代码，判断三次 print 分别表达什么内容边界，并说明为什么 Tag 可以安全进入 set。不要求写出集合 repr 的具体顺序。

from dataclasses import dataclass

@dataclass(frozen=True)
class Tag:
    name: str
    version: int

raw = [Tag("parser", 1), Tag("vm", 1), Tag("parser", 1)]
seen = set(raw)
required = {Tag("parser", 1), Tag("gc", 1)}

print(len(seen))
print(Tag("parser", 1) in seen)
print(seen & required)

答案要点

len(seen) 的结果是 2，因为两个 Tag("parser", 1) 在 equality 上相等，并且 frozen dataclass 会生成与这些字段一致的 hash。Tag("parser", 1) in seen 的结果是 True，查询对象虽然是新创建的对象，但它的 hash 与 equality 都和集合中已有元素匹配。seen & required 的结果内容只包含 Tag("parser", 1)，因为交集保留两侧都能通过 membership 判断的元素。

这段代码中 Tag 可以进入 set，因为它是不可变值对象，参与 hash 与 equality 的字段在对象生命周期内保持稳定。集合 repr 的元素顺序不进入答案；需要稳定输出时，应写成 sorted(seen, key=lambda tag: (tag.name, tag.version)) 之类的显式排序。

本章知识点总结

• 集合语义：set 表达无序、去重、可变的元素集合，核心能力是成员查询和集合代数操作。
• 槽位结构：CPython 的 set 使用哈希表保存元素引用和 hash，查询先定位槽位，再按 hash 与 equality 确认命中。
• 探测路径：collision 会让查询沿 probe 路径继续检查槽位，hash 分布越集中，候选检查成本越高。
• 相等判定：hash 负责缩小候选范围，equality 负责确认对象是否代表同一个集合元素。
• 扩容重建：插入增加表负载，删除留下 dummy slot，resize 通过重建表恢复查询路径质量。
• hash 约束：相等对象必须拥有相同 hash，集合元素在驻留期间应保持参与 hash 和 equality 的状态稳定。
• 可变风险：按值比较的可变对象进入集合后，如果字段改变，后续查询可能走向错误槽位路径。
• frozenset 边界：frozenset 内容固定且可 hash，适合表示集合元素或 dict key 中的集合值。
• 批量运算：并集、交集、差集和对称差集可以理解为批量遍历加 membership 判断。
• 顺序边界：set 迭代顺序不属于语言契约，稳定输出需要调用方显式排序或保留顺序容器。
• 选择顺序：容器选择先判断语义目标，再检查元素 hashability、查询模式、修改模式和顺序需求。
• 源码入口：阅读 CPython set 可以从 lookup、add 和 resize 三条路径建立最小充分模型。