# 集合

Source: https://codewiki.com/zh/python/sets/

> - **what**: `set` 保存互不相等的可哈希元素，适合表达唯一成员、成员关系以及并集、交集、差集等集合运算。
> - **trap**: 集合没有可依赖的迭代顺序，而且相等且哈希值相同的对象会合并；把列表直接转成集合可能同时丢失顺序和出现次数。
> - **fix**: 需要稳定输出时显式排序，需要保留顺序或计数时选择列表、字典或 `Counter`；修改集合前先确认是否允许改变原对象。

## 是什么，为什么存在

Python 集合是一组互不相等的可哈希元素（hashable element）。`set` 可以修改，`frozenset` 不能修改；两者都不支持按位置索引，也不承诺迭代顺序。集合字面量会自动合并重复项，但这种合并只保留成员关系，不保留原始位置或出现次数。

集合解决的是「某个值是否属于这一组」以及「两组成员如何组合」的问题。权限名、功能开关、已访问节点和两份配置的键，通常都天然是集合。订单序列、事件日志或排行榜则不是，因为这些数据的顺序和重复次数本身有意义。

集合运算把容易写错的嵌套循环变成明确的代数。`required - granted` 表示缺少的权限，`old & new` 表示两边共有的成员，`left ^ right` 表示只出现在一边的成员。表达式说明了关系，也迫使你先决定结果是否应当去重。

`set` 与其他常见容器的边界如下。这里的「无顺序」不是说每次迭代一定变化，而是说程序不能把观察到的顺序当成契约。

| 特性 | `set` | `frozenset` | `list` |
| --- | --- | --- | --- |
| 元素是否唯一 | 是 | 是 | 否 |
| 是否承诺顺序 | 否 | 否 | 是 |
| 能否修改成员 | 是 | 否 | 是 |
| 能否作为集合元素 | 否 | 是 | 否 |

## 工作原理

集合用元素的哈希值和相等关系组织成员。插入或查询对象时，Python 先取得哈希值，再在可能匹配的位置检查相等性。两个对象只有在比较相等并满足相同哈希约束时才代表同一个成员；哈希碰撞本身不会让不同对象被错误合并。

创建非空集合可以使用 `{value1, value2}`，创建空集合必须使用 `set()`，因为 `{}` 表示空字典。`set(iterable)` 会消费一个可迭代对象（iterable）并加入其中的成员。集合推导式 `{transform(item) for item in source if condition(item)}` 则把转换、筛选和去重放在一次构造中。

### 构造与复制

集合字面量会先计算各个元素表达式，再按哈希与相等规则加入成员。某个元素不可哈希时，构造立即抛出 `TypeError`，不会返回一个只包含前面元素的集合。推导式也可能在处理到不可哈希结果时中止。

`set(source)` 的输入遵循普通迭代规则，而不是为每种容器猜测业务含义。字符串会产出字符，字典会产出键，字典视图则按其视图类型产出键、值或键值对。调用者应明确传入的迭代单位是否就是集合成员。

- `set(existing_set)` 创建一个新的可变集合。
- `frozenset(existing_frozenset)` 可以返回原来的不可变对象。
- `set(mapping)` 收集映射的键，不收集值。
- 集合构造是浅层的，不会复制成员对象。

浅层构造意味着新旧集合的成员关系可以独立变化，但两边可能仍引用同一个成员对象。由于成员必须可哈希，内置可变容器不能直接成为这种共享成员；默认按对象标识哈希的自定义实例仍可能出现这种别名关系。

### 修改成员

`set` 的修改方法作用于原对象。任何指向该对象的别名都会观察到变化，所以选择原地方法之前要先确认所有权。

| 操作 | 含义 | 缺失成员时的行为 |
| --- | --- | --- |
| `items.add(value)` | 加入一个成员 | 不适用 |
| `items.update(values)` | 加入一个或多个可迭代对象中的成员 | 不适用 |
| `items.remove(value)` | 删除指定成员 | 抛出 `KeyError` |
| `items.discard(value)` | 删除指定成员 | 不执行操作 |
| `items.pop()` | 删除并返回任意成员 | 空集合抛出 `KeyError` |
| `items.clear()` | 删除全部成员 | 不适用 |

`remove()` 适合把「成员本应存在」当成不变量的代码，因为缺失会暴露错误。`discard()` 适合幂等清理，即重复执行删除仍得到相同最终状态。`pop()` 返回的是任意成员，不能把它当成队列或栈操作。

### 集合代数

四个二元运算都返回新集合，不修改左右操作数。差集有方向，对称差集没有方向。

| 表达式 | 方法形式 | 结果 |
| --- | --- | --- |
| `left | right` | `left.union(right)` | 任一集合中的成员 |
| `left & right` | `left.intersection(right)` | 两边共有的成员 |
| `left - right` | `left.difference(right)` | 只在左边的成员 |
| `left ^ right` | `left.symmetric_difference(right)` | 只在其中一边的成员 |

对应的 `update()`、`intersection_update()`、`difference_update()` 和 `symmetric_difference_update()` 会原地修改接收者。`|=`、`&=`、`-=` 和 `^=` 也表达原地修改。函数接收调用方集合时，除非契约明确允许，否则应优先返回新集合。

### 关系与操作数

`left <= right` 判断子集，`left < right` 判断真子集；`>=` 和 `>` 分别判断超集与真超集。`left.isdisjoint(right)` 在两边没有共同成员时返回 `True`。集合只定义部分顺序，因此 `sorted()` 才表示元素排序，`<` 并不表示字典序比较。

方法形式与运算符形式对操作数的要求不同。`items.intersection(sequence)` 可以接收任意可迭代对象，而 `items & sequence` 要求另一边也是集合类型。这一区别能让方法避免不必要的转换，也能让运算符及时暴露把列表误当集合的错误。

当 `set` 与 `frozenset` 混合进行二元运算时，结果类型跟随左操作数。`mutable | frozen` 得到 `set`，`frozen | mutable` 得到 `frozenset`。如果结果随后要作为字典键或另一个集合的成员，应让不可变集合位于左侧，或显式构造 `frozenset`。

### `set` 与 `frozenset` 的选择

需要逐步加入、撤销或同步成员时使用 `set`。如果成员集合构造后不应改变，或者它本身要成为字典键或集合元素，就使用 `frozenset`。冻结只阻止成员集合变化，并不会递归复制或冻结成员对象。

两种类型共享非修改型运算和关系判断。把公开配置暴露为 `frozenset` 可以表达「调用者不能通过这个接口增删成员」，但它不能替代领域验证，也不能自动让成员指向的对象变成只读。

## 示例

下面四个例子从基本构造逐步走到差异计算、策略检查和不可变集合。凡是要显示集合内容，代码都会先排序，因此记录的输出不依赖本次进程采用的集合迭代顺序。

### 去重与成员测试

这个例子把访问记录转换成唯一客户 ID 集合。原始列表仍保留请求次数和到达顺序，集合只负责唯一成员和成员测试。

<!-- quick -->

```python
# file: unique_customers.py
visits = [
    "c-101",
    "c-102",
    "c-101",
    "c-103",
    "c-102",
    "c-104",
]

unique_customer_ids = set(visits)

# 对输出排序，避免依赖集合迭代顺序。
print("requests:", len(visits))
print("unique customers:", sorted(unique_customer_ids))
print("c-103 seen:", "c-103" in unique_customer_ids)

empty_customer_ids = set()
print("empty type:", type(empty_customer_ids).__name__)
```

```text
requests: 6
unique customers: ['c-101', 'c-102', 'c-103', 'c-104']
c-103 seen: True
empty type: set
```

<!-- /quick -->

`len(visits)` 是六，因为列表保留重复请求；`len(unique_customer_ids)` 如果读取则会是四。两种容器回答不同问题，所以不要在完成计数前覆盖原始列表。

空集合使用 `set()`。如果写成 `{}`，最后一行会显示 `dict`，后续调用 `add()` 时才暴露类型错误。

### 计算部署差异

集合差异很适合描述期望状态与当前状态之间的迁移。方向写在变量名和表达式中，比单独保留一个对称差集更能说明下一步动作。

```python
# file: deployment_diff.py
deployed = {"search", "billing", "profile"}
desired = {"billing", "profile", "reports"}

added = desired - deployed
removed = deployed - desired
unchanged = deployed & desired
changed = deployed ^ desired

# 计算返回新集合，两个输入保持不变。
print("added:", sorted(added))
print("removed:", sorted(removed))
print("unchanged:", sorted(unchanged))
print("changed:", sorted(changed))
print("reports ready:", {"billing", "reports"} <= desired)
```

```text
added: ['reports']
removed: ['search']
unchanged: ['billing', 'profile']
changed: ['reports', 'search']
reports ready: True
```

`desired - deployed` 是要添加的服务，反向差集则是要移除的服务。`changed` 适合回答「哪些成员不同」，却不能单独告诉部署器应该添加还是删除。

最后的 `<=` 判断一组依赖是否都在期望状态中。它允许左右集合相等；如果业务要求右边还必须包含其他服务，才应使用真子集运算符 `<`。

### 检查访问策略

函数在边界处把输入转成集合，再分别计算缺失权限与冲突权限。返回值使用排序列表，让日志、测试和 API 响应保持稳定。

```python
# file: access_policy.py
def evaluate_access(granted, required, blocked):
    granted_set = set(granted)
    required_set = set(required)
    blocked_set = set(blocked)

    missing = required_set - granted_set
    conflicts = granted_set & blocked_set
    return {
        "missing": sorted(missing),
        "conflicts": sorted(conflicts),
        "allowed": not missing and not conflicts,
    }


result = evaluate_access(
    ["invoice.read", "invoice.export", "account.suspend"],
    ["invoice.read", "invoice.refund"],
    ["account.suspend"],
)

print("missing:", result["missing"])
print("conflicts:", result["conflicts"])
print("allowed:", result["allowed"])
```

```text
missing: ['invoice.refund']
conflicts: ['account.suspend']
allowed: False
```

`required_set - granted_set` 保留方向信息：它只列出调用方还缺什么。若改用对称差集，额外授予但并未禁止的权限也会混进结果，改变策略含义。

这个函数没有修改三个输入。即使调用方传入的本来就是集合，边界处的 `set(...)` 也会创建浅副本，使函数内部的后续修改不会泄漏给调用方。

### 用 `frozenset` 表示无序组合

一个无向组合没有「第一个」和「第二个」成员。`frozenset` 同时表达无序、唯一和不可修改，因此可以直接作为映射键。

```python
# file: frozen_groups.py
route_owners = {
    frozenset({"billing", "exports"}): "finance-platform",
    frozenset({"search", "catalog"}): "discovery",
}

requested_route = frozenset({"exports", "billing"})
print("owner:", route_owners[requested_route])

mutable_group = {"billing"}
frozen_group = frozenset(mutable_group)
mutable_group.add("audit")

print("frozen:", sorted(frozen_group))
print("mutable:", sorted(mutable_group))
print("mixed type:", type(frozen_group | {"audit"}).__name__)
print("equivalent count:", len({True, 1, 1.0}))
```

```text
owner: finance-platform
frozen: ['billing']
mutable: ['audit', 'billing']
mixed type: frozenset
equivalent count: 1
```

构造 `frozen_group` 会复制当时的成员，所以之后修改 `mutable_group` 不会改变它。混合运算的左操作数是 `frozenset`，结果也保持为 `frozenset`。

最后一行展示了集合依赖相等与哈希，而不是依赖类型名称。`True == 1 == 1.0`，这些数值也满足相等对象的哈希约束，所以集合只保留一个成员。

## 陷阱

### 用 `{}` 创建空集合

> **陷阱:** `{}` 始终创建字典。代码可能在初始化时没有报错，直到第一次调用集合方法才失败。

**修复：** 使用 `set()`，并在类型影响控制流时测试空输入。非空的 `{member}` 才是集合字面量；字典字面量包含冒号，例如 `{"id": 1}`。

### 把「不可变」当成「可哈希」

> **陷阱:** 「只有不可变对象才能进入集合」只是粗略口诀，不是 Python 的规则。包含列表的元组仍不可哈希，而用户自定义类的实例默认可能可哈希，即使其属性能够修改。

**修复：** 按可哈希协议判断：对象生命周期内哈希值必须不变，而且相等对象必须具有相同哈希值。嵌套成员集合可以使用 `frozenset`；结构化记录应选择明确、稳定的不可变键，而不是随意把外层换成元组。

### 把迭代顺序当成输出契约

> **陷阱:** 小样本中的集合经常显示为看似稳定的顺序，生成代码便直接把 `list(a_set)` 写入 JSON、快照或测试期望。这个顺序不受语言契约保证。

**修复：** 可比较的元素使用 `sorted(a_set)` 生成稳定输出；元素不能直接比较时，提供明确的排序键。若要求保留首次出现顺序，应遍历原序列并用辅助集合记录已见键，不能先转换整个序列。

### 写反差集或意外原地修改

> **陷阱:** `current - desired` 与 `desired - current` 回答相反的问题，而 `current -= desired` 还会修改可能由调用方共享的原集合。短变量名会把这两类错误藏起来。

**修复：** 使用 `added = desired - current` 和 `removed = current - desired` 这类带方向的名称。函数接收外部集合时默认使用非原地运算；只有契约声明所有权转移或允许修改时才使用更新运算。

### 迭代时改变集合大小

> **陷阱:** 在 `for member in members` 循环中调用 `add()`、`remove()` 或 `discard()` 改变同一集合的大小，会抛出 `RuntimeError`。把 `remove()` 机械换成 `discard()` 并不能解决迭代失效。

**修复：** 用集合推导式构造新结果，先计算待删除集合再执行差集更新，或迭代 `members.copy()`。需要暴露意外缺失时保留 `remove()`；只有缺失本来就允许时才用 `discard()`。

### 丢失次数和相等类型

> **陷阱:** `set(records)` 不只是删除重复行。它还删除出现次数，并可能把 `True`、`1` 和 `1.0` 这样的相等值合并为一个成员。

**修复：** 先写清楚唯一性的键和所需输出。要计数时使用 `collections.Counter`；要按业务键保留第一条记录时，遍历原序列并维护 `seen_keys`；类型必须区分时，把类型标签纳入键并测试跨类型相等值。

<!-- deep -->

## 哈希与相等性

可哈希对象必须提供一个在其生命周期内保持不变的哈希值，并且能够参与相等比较。两个比较相等的对象必须返回相同哈希值，反过来却不成立：不同对象允许发生哈希碰撞。集合会在哈希定位之后继续用相等性区分这些对象。

「内置不可变对象通常可哈希」比「不可变等于可哈希」更准确。数字、字符串和只含可哈希成员的元组可以进入集合；列表和字典等可变容器不可以。元组本身没有修改方法，但只要其中包含列表，它就仍然不可哈希。

用户自定义类增加了另一层约束。类实例默认通常按对象标识参与哈希与相等；一旦实现基于字段的 `__eq__()`，就必须一起设计与它一致的 `__hash__()`。绝不能在对象已经成为集合成员后，修改参与哈希或相等判断的字段，否则查询和删除可能再也找不到逻辑上仍在集合里的对象。

集合判断的是值是否相等，不要求类型相同。`bool` 是 `int` 的子类，`True` 与 `1` 比较相等；整数 `1` 与浮点数 `1.0` 也比较相等。它们满足相同哈希约束，因此放进同一个集合时只形成一个成员。领域需要区分这些输入时，可以使用 `(type(value), value)` 这样的复合键，但先要确认类型对象本身就是预期的领域标签。

`frozenset` 的不可变性只覆盖成员关系：创建后不能加入或删除成员。构造它时，所有成员仍须可哈希。一个默认按对象标识哈希的自定义实例可能拥有可变属性，所以 `frozenset` 不能保证整个对象图深度不可变。

集合之间的相等只比较成员，不比较可变性。因此，成员相同的 `set` 与 `frozenset` 可以比较相等，但只有 `frozenset` 能作为映射键或集合成员。选择类型时应根据所有权和后续用途，而不是期望两者表达不同的数学值。

## 集合形数据的边界

集合最适合作为程序内部的关系模型，但外部输入与输出通常是序列或对象。边界代码需要决定如何处理重复项、顺序、错误和所有权；直接调用 `set(...)` 只是实现选择，不是完整的数据契约。

### 规范化输入

先验证还是先去重会产生不同结果。如果重复权限表示上游配置错误，立即转换为集合会掩盖该错误；如果重复事件应累计次数，转换会永久丢失计数。只有在重复确实没有领域含义时，入口处去重才正确。

规范化还应发生在建立集合之前。邮箱、文件扩展名或不区分大小写的标识符，可能要先去除空白并统一大小写。否则，语法不同但领域等价的输入会成为不同成员。

- 声明空输入是有效空集合，还是缺失配置。
- 声明重复项应合并、计数，还是拒绝。
- 声明大小写、空白和 Unicode 规范化规则。
- 在转换前报告无法哈希或格式无效的成员。

错误信息应指向原始输入位置，而不是只转发 `unhashable type`。先枚举并验证记录，再构造集合，通常比在一个推导式中同时解析、转换和去重更容易给出有用诊断。

### 稳定的外部表示

集合没有 JSON 原生表示，因为 JSON 数组有顺序并允许重复。把集合暴露为数组时，API 必须额外声明顺序：按值排序、按领域键排序，或保留另一份原始序列的首次出现顺序。客户端不应从一次响应猜测规则。

| 边界需求 | 合适的表示 |
| --- | --- |
| 只需成员关系 | 内部使用 `set` |
| 稳定且可比较的输出 | `sorted(members)` |
| 保留首次出现顺序 | 原序列加 `seen` 集合 |
| 需要出现次数 | `Counter` 或显式映射 |
| 无序组合作为键 | 内部使用 `frozenset` |

缓存键需要同样的明确性。成员已经可哈希且无序组合就是业务含义时，`frozenset` 是合适的进程内键；跨进程存储时，应使用带排序和编码规则的稳定序列化格式，不能依赖 Python 的集合显示文本。

### 返回值与所有权

返回内部 `set` 会把修改能力交给调用方。调用方执行 `clear()` 或 `|=` 后，拥有该内部集合的对象也可能被改变。需要快照语义时返回副本，需要只读且可哈希的成员快照时返回 `frozenset`。

返回副本只隔离外层成员关系，不复制成员对象。成员对象有可变属性时，调用方仍可能通过这些对象改变共享状态。API 必须分别说明集合本身和成员对象的所有权。

- 参数是否会被原地修改。
- 返回值是否与内部状态共享同一个集合对象。
- 成员对象是否由调用方继续拥有。
- 并发访问时由哪一层负责同步。

类型注解 `set[str]` 与 `frozenset[str]` 能表达成员类型和可变性意图，但普通 Python 调用不会在运行时执行这些检查。外部数据仍需显式验证，内部接口仍需测试别名和修改行为。

### 选择唯一性键

记录通常不能整条放进集合，而且「整条记录相等」往往也不是业务上的重复定义。客户可能按规范化邮箱唯一，订单可能按订单 ID 唯一，文件可能按内容摘要唯一。选择键时要写出哪些字段参与相等判断，以及发生冲突时保留哪一条记录。

保序去重通常维护一个键集合和一个结果列表。遍历每条记录，计算并验证键；键未出现时，同时加入 `seen_keys` 和结果。这个结构保留首次出现位置，也为「保留最后一条」或「重复即报错」留下明确的修改点。

不要只用样例中的普通字符串验证唯一性代码。空字符串、缺失键、大小写差异、规范化后碰撞以及不同 Python 类型之间的相等，都可能改变最终成员数。测试应直接断言冲突策略，而不只是断言结果长度。

<!-- /deep -->

[检查点: python/sets](https://codewiki.com/zh/python/sets/#checkpoint)

## 延伸阅读

以下链接均指向本主题验证时使用的 Python 3.14 官方文档。

- [内置类型中的 `set` 与 `frozenset`](https://docs.python.org/3.14/library/stdtypes.html#set-types-set-frozenset)
- [Python 教程中的集合](https://docs.python.org/3.14/tutorial/datastructures.html#sets)
- [Python 术语表中的 `hashable`](https://docs.python.org/3.14/glossary.html#term-hashable)