Python 集合：去重、集合运算与哈希约束

集合 set 保存不重复的可哈希元素，适合成员判断、去重和集合运算。它不是序列，不记录可供业务依赖的插入次序，也不支持按下标取第几个元素。空集合用 set() 创建，{} 创建的是空字典。

本文使用 Python 3.11。各段程序可独立运行，断言检查需要保留，运行时不要使用 -O。

创建、去重与哈希边界

empty = set()
assert type(empty) is set and type({}) is dict
nums = set([1, 2, 2, 3, 3, 3, 4])
assert nums == {1, 2, 3, 4} and len(nums) == 4
letters = {char for char in "abracadabra" if char not in "abc"}
assert letters == {"r", "d"}
assert 2 in nums and 99 not in nums
assert set(iter(nums)) == nums

mapping = {(1, 3): {3, (4, 5), 3, (4, 5)}}
assert mapping[(1, 3)] == {3, (4, 5)}
groups = {frozenset({1, 2}), frozenset({2, 1})}
assert len(groups) == 1
for operation in [lambda: set([[1]]), lambda: hash(set()), lambda: nums[0]]:
    try:
        operation()
    except TypeError:
        pass
    else:
        raise AssertionError("invalid set operation succeeded")
assert sorted(nums) == [1, 2, 3, 4]
print("set creation and hashability checks passed")

这保留了原笔记中“元组作字典键、集合同时包含整数和元组”的例子。集合本身可变且不可哈希，若要把一个集合值放入另一个集合，可以使用不可变的 frozenset。元组也只有在成员全部可哈希时才能作为元素。

把集合转成 list 后虽然能够索引，所得位置却不代表原输入的第几个元素。确实需要确定顺序时，按明确规则排序；混合类型也未必可以直接排序。需要保留首次出现顺序的去重方式，见列表去重。

交、并、差与包含关系

操作	方法	结果含义
a & b	intersection	同时属于两边的元素
a | b	union	属于任意一边的元素
a - b	difference	属于 a 而不属于 b，方向不能颠倒
a ^ b	symmetric_difference	只属于其中一边的元素
a <= b、a < b	issubset，以及额外的不相等判断	子集、真子集
a >= b、a > b	issuperset，以及额外的不相等判断	超集、真超集
无直接对应运算符	isdisjoint	没有共同元素

< 和 > 比的是包含关系，不是元素个数，也不是序列的字典序。不相等的两个集合可能互不包含。

a, b = {1, 2, 3}, {3, 4}
assert a & b == a.intersection(b) == {3}
assert a | b == a.union(b) == {1, 2, 3, 4}
assert a - b == a.difference(b) == {1, 2}
assert b - a == {4}
assert a ^ b == a.symmetric_difference(b) == {1, 2, 4}
assert {1, 2} < a and {1, 2}.issubset(a)
assert a >= {1, 2} and a.issuperset({1, 2})
assert a <= a and not a < a
assert {1}.isdisjoint({2})
assert not ({1} < {2}) and not ({1} > {2}) and {1} != {2}
assert a == frozenset({1, 2, 3})

assert a.intersection([2, 4]) == {2}
assert a.union([5]) == {1, 2, 3, 5}
try:
    a | [5]
except TypeError:
    pass
else:
    raise AssertionError("set operator accepted a list operand")
assert a == {1, 2, 3} and b == {3, 4}
print("set algebra and relation checks passed")

普通 set 的这些运算符要求集合操作数，而对应方法可以接收其他可迭代对象，例如列表。上面非原地运算保留 a、b；具体规则见 Python 集合类型。

修改原集合与删除元素

方法	行为	返回值或失败条件
add(x)	加入一个元素	返回 None；x 必须可哈希
update(iterable)	加入可迭代对象中的各元素	返回 None，字符串会逐字符加入
difference_update	删除其他输入中存在的元素	原地差集
intersection_update	只保留共同元素	原地交集
symmetric_difference_update	只保留两边不共同的元素	原地对称差
remove(x)	删除一个元素	不存在时抛出 KeyError
discard(x)	删除一个元素	不存在也不报错
pop()	删除并返回某个元素	选择任意元素，不保证随机分布或固定次序；空集合抛出 KeyError
clear()	清空集合	返回 None
copy()	返回浅拷贝	新的外层集合，元素引用保留

s = {1, 2}
alias = s
assert s.add(3) is None
assert s.update([3, 4]) is None
assert s == {1, 2, 3, 4}
assert s.difference_update([1]) is None
assert s.intersection_update([2, 3, 9]) is None
assert s == {2, 3}
assert s.symmetric_difference_update([3, 4]) is None
assert s == {2, 4} and alias is s
assert s.discard(99) is None
assert s.remove(2) is None and s == {4}
try:
    s.remove(99)
except KeyError:
    pass
else:
    raise AssertionError("remove accepted a missing element")

s |= {5, 6}
s &= {4, 5}
s ^= {5, 7}
s -= {4}
assert s == {7} and alias == {7}
copied = s.copy()
assert copied == s and copied is not s
before = copied.copy()
removed = copied.pop()
assert removed in before and copied == before - {removed}
try:
    copied.pop()
except KeyError:
    pass
else:
    raise AssertionError("pop succeeded on an empty set")
assert s.clear() is None and alias == set()
print("set mutation and removal checks passed")

add([1, 2]) 不能用来批量加入两个整数，因为传入的是一个不可哈希列表；这里应使用 update([1, 2])。若想加入元组本身，则使用 add((1, 2))。

原表的特殊名称如何对应操作

入口或用途	涉及名称	说明
类型、文档和属性清单	__class__、__doc__、__dir__	对应 type、文档字符串和 dir
长度与表示	__len__、__str__、__repr__	不应据输出次序推断顺序保证
泛型类型写法	__class_getitem__	set[int] 描述参数化类型，不负责验证已存元素
成员与遍历	__contains__、__iter__	in 与 iter
相等与包含	__eq__、__ne__、__ge__、__gt__、__le__、__lt__	相等与子集、超集关系
二元与反向操作	__and__、__rand__、__or__、__ror__、__xor__、__rxor__、__sub__、__rsub__	反向方法参与对应运算符的分派；差集尤其要注意左右顺序
原地操作	__iand__、__ior__、__ixor__、__isub__	对应四种增强赋值
pickle 重建	__reduce__、__reduce_ex__	通常通过 pickle 调用
直接归属内存	__sizeof__	原文 __size__ 拼写不对应标准 set 方法；推荐 sys.getsizeof

import pickle
import sys
from types import GenericAlias

s = {1, 2}
assert s.__class__ is set and isinstance(set.__doc__, str)
assert "union" in dir(s)
assert not hasattr(s, "__size__")
assert sys.getsizeof(s) >= s.__sizeof__()
alias = set[int]
assert isinstance(alias, GenericAlias) and alias.__origin__ is set
assert alias.__args__ == (int,)
unchecked = set[int](["text"])
assert unchecked == {"text"}
assert pickle.loads(pickle.dumps(s, protocol=2)) == s
print("set metadata and annotation checks passed")

内存大小不包含对所有元素的递归求和，见 sys.getsizeof。参数化类型的边界见类型注解与 typing，对象协议与可信 pickle 的限制见特殊方法。