Python►数据结构

集合 Set 与集合运算

集合（set）是 Python 中经常被”低估”的容器。很多人只知道它”能去重”，但其实它还是判断存在性最快的数据结构，也是数学意义上”集合运算”（交并差）的最佳载体。这一篇把 set 与 frozenset 讲透，让你知道它什么时候比列表和字典都好用。

一、什么是集合

集合是一个 可变、无序、不重复 的容器：

1
2
s = {1, 2, 3, 4, 3, 2}    # 自动去重
print(s)                  # {1, 2, 3, 4}

关键约束：

  • 元素必须可哈希：跟 dict 的 key 一样，list/dict/set 不能进 set；
  • 元素唯一：重复元素自动合并；
  • 无序：for x in s 的顺序没有保证（跟 dict 不同，set 不保证插入顺序）。

二、创建集合

1
2
3
4
5
6
7
8
9
10
11
12
# 字面量
s1 = {1, 2, 3}

# 空集合注意：不能写 {}，那是空字典！
empty_set = set()

# 从可迭代对象
s2 = set("hello")         # {'h', 'e', 'l', 'o'}
s3 = set([1, 2, 2, 3])    # {1, 2, 3}

# 集合推导式（第 15 篇）
s4 = {x*x for x in range(5)}   # {0, 1, 4, 9, 16}

三、增删改查

增

1
2
3
4
s = {1, 2, 3}
s.add(4)                       # {1, 2, 3, 4}
s.update([5, 6, 7])            # 批量添加，可以传任何可迭代对象
s.update({8, 9}, [10])         # 多个也行

删

1
2
3
4
s.remove(1)          # 不存在会抛 KeyError
s.discard(999)       # 不存在也不报错，推荐用它
popped = s.pop()     # 弹出任意一个元素（因为无序，"任意"就是任意）
s.clear()            # 清空

查

1
2
3
2 in s          # O(1)，超快
9 not in s      # 也 O(1)
len(s)          # 元素个数

四、集合运算

这是 set 的真正杀手锏——数学意义上的集合操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a | b)     # 并集 {1, 2, 3, 4, 5, 6}
print(a & b)     # 交集 {3, 4}
print(a - b)     # 差集 {1, 2}
print(a ^ b)     # 对称差 {1, 2, 5, 6}

# 也可以用方法名
a.union(b)
a.intersection(b)
a.difference(b)
a.symmetric_difference(b)

方法名版本比运算符更强：可以接受任何可迭代对象，不必是 set：

1
2
a.union([5, 6, 7])           # 传列表 OK
a & b                        # 只能是集合

就地版

1
2
3
4
5
6
7
8
9
a |= b       # a = a | b
a &= b
a -= b
a ^= b

a.update(b)
a.intersection_update(b)
a.difference_update(b)
a.symmetric_difference_update(b)

子集与超集

1
2
3
4
5
{1, 2}.issubset({1, 2, 3})       # True
{1, 2, 3}.issuperset({1, 2})     # True
{1, 2}.isdisjoint({3, 4})        # True，无交集
{1, 2} <= {1, 2, 3}              # True，子集
{1, 2} < {1, 2, 3}               # True，真子集

五、去重的三种姿势

list → set → list 是 Python 里最短的去重代码：

1
2
3
lst = [1, 2, 2, 3, 3, 3]
unique = list(set(lst))
print(unique)                # [1, 2, 3]，但顺序不保证！

如果要保序去重（Python 3.7+）：

1
2
3
4
5
6
7
8
9
10
# 利用 dict 的插入顺序
unique = list(dict.fromkeys(lst))   # [1, 2, 3]，顺序保留

# 或者手写
seen = set()
result = []
for x in lst:
    if x not in seen:
        seen.add(x)
        result.append(x)

六、set 用于快速查找

set 的 in 是 O(1) 平均，比 list 的 O(n) 快得多：

1
2
3
4
5
6
7
8
9
10
11
# ❌ 慢
def has_dupes(items):
    for i, x in enumerate(items):
        for j, y in enumerate(items):
            if i != j and x == y:
                return True
    return False

# ✅ 快
def has_dupes(items):
    return len(set(items)) != len(items)

处理”两个大列表的共同项”、”某个 id 是否在黑名单里”，都应该先把小的一方转成 set。

七、frozenset：不可变集合

frozenset 是 set 的不可变版本——一旦创建不能改：

1
2
fs = frozenset([1, 2, 3])
fs.add(4)         # ❌ AttributeError

用途：

  • 可以作为 dict 的 key（普通 set 不行，因为可变）；
  • 可以作为另一个 set 的元素；
  • 表示”这份集合是配置常量，不许改”。
1
BAD_WORDS = frozenset({"spam", "junk"})

八、性能特性

  • in、add、remove、discard：平均 O(1)；
  • 集合运算 O(|a| + |b|)；
  • 每个 set 起步内存约 200 字节；
  • 元素必须可哈希，且 __hash__ 和 __eq__ 一致（自定义类要小心）。

九、一个综合例子：日活跃用户分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# users.py
"""对每天登录用户做集合分析。"""

# 日 → 登录用户 id 集合
daily = {
    "2025-09-01": {1, 2, 3, 4, 5},
    "2025-09-02": {2, 3, 5, 6, 7},
    "2025-09-03": {1, 3, 6, 7, 8},
}


def total_users(daily: dict) -> set:
    """全部有过登录的用户。"""
    result = set()
    for users in daily.values():
        result |= users
    return result


def core_users(daily: dict) -> set:
    """所有日子都登录的用户（交集）。"""
    days = list(daily.values())
    return days[0].intersection(*days[1:])


def new_users(daily: dict) -> dict:
    """每一天相比前一天新增的用户。"""
    dates = sorted(daily)
    seen = set()
    result = {}
    for date in dates:
        result[date] = daily[date] - seen
        seen |= daily[date]
    return result


def churn(daily: dict) -> dict:
    """每一天相比前一天流失的用户。"""
    dates = sorted(daily)
    result = {}
    for prev, curr in zip(dates, dates[1:]):
        result[curr] = daily[prev] - daily[curr]
    return result


if __name__ == "__main__":
    print("总用户：", total_users(daily))
    print("核心用户：", core_users(daily))
    print("新用户：", new_users(daily))
    print("流失：", churn(daily))

十、常见陷阱

陷阱 1：{} 是空字典不是空集合

1
2
e1 = {}         # 空字典
e2 = set()      # 空集合

陷阱 2：不可哈希元素

1
2
{[1, 2]}        # ❌ TypeError: unhashable type: 'list'
{(1, 2)}        # ✅ 元组可以

陷阱 3：set 不保证顺序

1
2
3
s = {"a", "b", "c"}
for x in s:
    print(x)        # 输出顺序在不同版本/进程里可能变

需要顺序，用有序容器（list、dict）。

陷阱 4：集合运算的”就地”版本容易搞错

1
2
3
a = {1, 2, 3}
b = a & {2, 3, 4}       # b 是新集合，a 不变
a &= {2, 3, 4}          # a 就地更新

陷阱 5：修改 set 里的可变元素后，哈希失效

自定义类如果 __hash__ 依赖可变字段，改了字段后 set 的行为会崩坏：

1
2
3
4
5
6
7
8
class User:
    def __init__(self, id): self.id = id
    def __hash__(self): return hash(self.id)
    def __eq__(self, o): return self.id == o.id

u = User(1)
s = {u}
u.id = 2         # ❌ 改了 hash 依赖的字段，s 里再也找不到 u

结论：可哈希对象的哈希应该基于不可变字段。

十一、set 与 dict 的关系

set 可以理解为”只有 key 没有 value 的 dict”：

  • 都用哈希表实现；
  • 元素/key 都要可哈希；
  • in 都是 O(1)。

甚至 Python 内部的实现，set 就是从 dict 简化来的。

十二、小结与延伸阅读

  • set 是可变、无序、不重复的容器；
  • 元素必须可哈希；
  • 支持并集/交集/差集/对称差；
  • 空集合用 set()，不是 {}；
  • 大量查找用 set 而不是 list；
  • 不可变版本 frozenset 可以做 dict key；
  • 保序去重用 dict.fromkeys。

延伸阅读：

下一篇 列表推导式与生成表达式 我们讲 Python 里最优雅的语法糖之一。