常用数据结构之集合
# 常用数据结构之集合
## 集合基础
集合（set）是无序且不包含重复元素的容器，跟数学中的集合概念一致：
- **无序性**：元素没有固定顺序，不支持索引运算
- **互异性**：元素不重复，自动去重
- **确定性**：元素要么在集合中，要么不在
## 创建集合
```python
# 基础创建
set1 = {1, 2, 3, 3, 2} # {1, 2, 3}，自动去重
set2 = {'apple', 'banana', 'apple'} # {'apple', 'banana'}
# 从序列转换
set3 = set('hello') # {'h', 'e', 'l', 'o'}，自动去重
set4 = set([1, 2, 2, 3, 3]) # {1, 2, 3}
# 集合生成式
set5 = {x for x in range(1, 20) if x % 3 == 0 or x % 7 == 0}
```
> **注意**：`{}` 表示空字典，不是空集合。空集合用 `set()`。
> **注意**：集合元素必须是可哈希类型（不可变类型），如 `int`、`str`、`tuple`，不能用 `list`、`set`、`dict`。
## 集合运算
### 交集、并集、差集、对称差
```python
set1 = {1, 2, 3, 4, 5, 6, 7}
set2 = {2, 4, 6, 8, 10}
print(set1 & set2) # 交集: {2, 4, 6}
print(set1 | set2) # 并集: {1, 2, 3, 4, 5, 6, 7, 8, 10}
print(set1 - set2) # 差集: {1, 3, 5, 7}
print(set1 ^ set2) # 对称差: {1, 3, 5, 7, 8, 10}
```
### 子集和超集
```python
a = {1, 3, 5}
b = {1, 2, 3, 4, 5}
print(a < b) # True（a是b的真子集）
print(a <= b) # True（a是b的子集）
print(b > a) # True（b是a的超集）
print(a == {5, 3, 1}) # True（元素相同即相等）
```
## 集合方法
```python
s = {1, 10, 100}
# 添加元素
s.add(1000) # 添加（重复则忽略）
s.update({5, 50}) # 批量添加
# 删除元素
s.discard(10) # 删除（不存在不报错）
s.remove(100) # 删除（不存在抛KeyError）
popped = s.pop() # 随机删除并返回
# 判断
print(s.isdisjoint({3, 6})) # True（无交集）
```
> **建议**：删除元素用 `discard()` 比 `remove()` 更安全。
## 不可变集合
`frozenset` 是不可变版本，可作为其他集合的元素：
```python
fset = frozenset({1, 3, 5, 7})
print(fset | frozenset({2, 4})) # frozenset({1, 2, 3, 4, 5, 7})
```
## 总结
- 集合：无序、去重、支持交集/并集/差集/对称差运算
- 集合不支持索引和切片
- 集合元素必须是不可变类型
- `frozenset` 是不可变集合，可作为字典键或嵌套使用