04-集合
本章代码基于 Python 3.11+ 编写
集合是无序不重复元素的容器，擅长去重和集合运算。
本章全面讲解 Python 集合的创建、操作、集合运算和高级用法。
概念铺垫
为什么需要集合？一个去重的需求场景
问题场景： 你在分析用户访问日志，需要统计有多少个不同用户访问过网站。
不使用集合的方案（列表）：
python
# 用户访问日志（可能有重复）
user_ids: list[str] = ["user1", "user2", "user1", "user3", "user2", "user4"]
# 统计不同用户
unique: list[str] = []
for uid in user_ids:
if uid not in unique:
unique.append(uid)
print(f"不同用户：{len(unique)}") # 输出：4问题：
- 需要手动检查重复
- 查找慢（每次都要遍历）
使用集合的解决方案：
python
# 用集合自动去重
user_ids: list[str] = ["user1", "user2", "user1", "user3", "user2", "user4"]
unique: set[str] = set(user_ids)
print(f"不同用户：{len(unique)}") # 输出：4这就是集合的价值：自动去除重复，快速判断存在。
集合解决了什么问题？
集合的本质是：存储唯一元素，快速判断存在性。
就像你检查列表中是否有重复项，集合自动帮你完成。
集合的优势：
- 自动去重：相同元素只保留一个
- 快速查找：O(1) 时间复杂度
- 集合运算：交集、并集、差集
- 数学建模：适合数学集合问题
L1 理解层：会用
集合的最简用法（3分钟上手）
集合的核心操作：创建、添加、判断存在。
python
# 创建集合
fruits: set[str] = {"apple", "banana", "orange"}
# 添加元素
fruits.add("grape")
# 判断存在
if "apple" in fruits:
print("有苹果")
# 自动去重
numbers: set[int] = {1, 2, 2, 3, 3, 3}
print(numbers) # {1, 2, 3}这就是集合的基本用法。接下来我们详细学习集合的操作。
第一部分：集合基础
什么是集合
集合（Set） 是无序、不重复的元素集合，支持数学集合运算。
┌─────────────────────────────────────────────────────────────┐
│ 集合的特点 │
├─────────────────────────────────────────────────────────────┤
│ │
│ ✅ 无序：元素没有固定顺序，不能通过索引访问 │
│ ✅ 不重复：自动去重，每个元素只出现一次 │
│ ✅ 可变：可以添加、删除元素 │
│ ✅ 元素可哈希：元素必须是不可变类型 │
│ ✅ 快速查找：O(1) 时间复杂度 │
│ ✅ 集合运算：支持并集、交集、差集等 │
│ │
│ 表示方法：使用花括号 {}（但空集合用 set()） │
│ 例如：{1, 2, 3} │
│ │
│ 底层实现：哈希表 │
│ • 与字典类似，只存储键，不存储值 │
│ • 查找、添加、删除平均 O(1) │
│ │
└─────────────────────────────────────────────────────────────┘创建集合
python
# 方式 1：使用花括号
fruits = {"apple", "banana", "orange"}
numbers = {1, 2, 3, 4, 5}
# 方式 2：创建空集合（必须用 set()）
empty_set = set()
# empty_set = {} # ❌ 这是空字典！
# 方式 3：从其他可迭代对象创建
from_list = set([1, 2, 2, 3, 3, 3]) # {1, 2, 3}（自动去重）
from_string = set("hello") # {'h', 'e', 'l', 'o'}
from_tuple = set((1, 2, 3)) # {1, 2, 3}
# 方式 4：集合推导式
squares = {i ** 2 for i in range(1, 6)} # {1, 4, 9, 16, 25}
# 方式 5：从字典创建（取键）
d = {"a": 1, "b": 2}
keys = set(d) # {'a', 'b'}元素类型限制
┌─────────────────────────────────────────────────────────────┐
│ 可作为集合元素的类型 │
├─────────────────────────────────────────────────────────────┤
│ │
│ ✅ 可哈希类型： │
│ • 整数、浮点数、字符串 │
│ • 元组（元素也必须可哈希） │
│ • 布尔值、None │
│ • frozenset │
│ │
│ ❌ 不可哈希类型： │
│ • 列表 │
│ • 字典 │
│ • 集合 │
│ │
│ 示例： │
│ ✅ {1, 2, 3} │
│ ✅ {"a", "b", "c"} │
│ ✅ {(1, 2), (3, 4)} │
│ ❌ {[1, 2], [3, 4]} # TypeError │
│ ❌ {{1, 2}, {3, 4}} # TypeError │
│ │
└─────────────────────────────────────────────────────────────┘python
# 有效元素
s = {1, "hello", 3.14, True, None, (1, 2)}
print(s)
# 无效元素
# s = {[1, 2]} # TypeError: unhashable type: 'list'
# s = {{1, 2}} # TypeError: unhashable type: 'set'
# 嵌套集合：使用 frozenset
inner = frozenset({1, 2})
outer = {inner, frozenset({3, 4})}
print(outer) # {frozenset({1, 2}), frozenset({3, 4})}第二部分：集合操作
添加元素
python
fruits = {"apple", "banana"}
# add() - 添加单个元素
fruits.add("orange")
print(fruits) # {'apple', 'banana', 'orange'}
# 添加已存在的元素（无效果）
fruits.add("apple") # 集合不变
# update() - 添加多个元素
fruits.update(["mango", "peach"])
fruits.update({"grape", "kiwi"})
fruits.update("ab") # 添加 'a' 和 'b'
print(fruits)
# |= 运算符（Python 3.9+）
fruits |= {"cherry"}删除元素
python
fruits = {"apple", "banana", "orange", "grape", "mango"}
# remove() - 删除元素（不存在会报错）
fruits.remove("banana")
# fruits.remove("xyz") # KeyError: 'xyz'
# discard() - 删除元素（不存在不会报错）
fruits.discard("orange")
fruits.discard("xyz") # 不报错
# pop() - 随机删除并返回一个元素
removed = fruits.pop()
print(f"删除了: {removed}")
# clear() - 清空集合
fruits.clear()
print(fruits) # set()
# 删除方法对比
┌─────────────────────────────────────────────────────────────┐
│ 删除方法对比 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 方法 返回值 元素不存在时 │
│ ───────────────────────────────────────────── │
│ remove() 无 KeyError │
│ discard() 无 不报错 │
│ pop() 元素 KeyError（空集合） │
│ clear() 无 - │
│ │
│ 建议：不确定元素是否存在时用 discard() │
│ │
└─────────────────────────────────────────────────────────────┘查找和统计
python
fruits = {"apple", "banana", "orange"}
# 成员检查（O(1) 时间复杂度）
print("apple" in fruits) # True
print("grape" in fruits) # False
print("grape" not in fruits) # True
# 获取元素数量
print(len(fruits)) # 3
# 集合不能通过索引访问
# fruits[0] # TypeError: 'set' object is not subscriptable
# 遍历集合
for fruit in fruits:
print(fruit)
# 带索引遍历
for i, fruit in enumerate(fruits):
print(f"{i}: {fruit}")第三部分：集合运算
基本运算
python
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}
# 并集（所有元素）
print(A | B) # {1, 2, 3, 4, 5, 6, 7, 8}
print(A.union(B)) # 同上
print(A.union(B, {9, 10})) # 多个集合
# 交集（共同元素）
print(A & B) # {4, 5}
print(A.intersection(B)) # 同上
# 差集（在 A 中但不在 B 中）
print(A - B) # {1, 2, 3}
print(A.difference(B)) # 同上
# 对称差集（只在一个集合中的元素）
print(A ^ B) # {1, 2, 3, 6, 7, 8}
print(A.symmetric_difference(B)) # 同上图示：
┌─────────────────────────────────────────────────────────────┐
│ 集合运算图示 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 并集 A | B： │
│ ┌─────────────────────────────────────┐ │
│ │ A: {1, 2, 3, 4, 5} │ │
│ │ B: {4, 5, 6, 7, 8} │ │
│ │ 结果: {1, 2, 3, 4, 5, 6, 7, 8} │ │
│ └─────────────────────────────────────┘ │
│ │
│ 交集 A & B： │
│ ┌─────────────────────────────────────┐ │
│ │ A: {1, 2, 3, [4, 5], 6, 7, 8} │ │
│ │ ↑ 共同部分 │ │
│ │ 结果: {4, 5} │ │
│ └─────────────────────────────────────┘ │
│ │
│ 差集 A - B： │
│ ┌─────────────────────────────────────┐ │
│ │ A 中有但 B 中没有 │ │
│ │ 结果: {1, 2, 3} │ │
│ └─────────────────────────────────────┘ │
│ │
│ 对称差集 A ^ B： │
│ ┌─────────────────────────────────────┐ │
│ │ 只在一个集合中的元素 │ │
│ │ = (A - B) | (B - A) │ │
│ │ 结果: {1, 2, 3, 6, 7, 8} │ │
│ └─────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘原地运算
python
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}
# 原地并集
A |= B
# 或
A.update(B)
# 原地交集
A = {1, 2, 3, 4, 5}
A &= B
# 或
A.intersection_update(B)
# 原地差集
A = {1, 2, 3, 4, 5}
A -= B
# 或
A.difference_update(B)
# 原地对称差集
A = {1, 2, 3, 4, 5}
A ^= B
# 或
A.symmetric_difference_update(B)子集与超集
python
A = {1, 2, 3}
B = {1, 2, 3, 4, 5}
C = {6, 7, 8}
# 子集判断
print(A.issubset(B)) # True
print(A <= B) # True
print(A < B) # True（真子集）
print(A <= A) # True
print(A < A) # False（不是真子集）
# 超集判断
print(B.issuperset(A)) # True
print(B >= A) # True
print(B > A) # True（真超集）
# 不相交判断
print(A.isdisjoint(C)) # True（没有共同元素）
print(A.isdisjoint(B)) # False
# 判断方法对比
┌─────────────────────────────────────────────────────────────┐
│ 集合关系判断 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 关系 方法 运算符 │
│ ───────────────────────────────────────────── │
│ 子集 issubset() <= │
│ 真子集 - < │
│ 超集 issuperset() >= │
│ 真超集 - > │
│ 不相交 isdisjoint() - │
│ 相等 - == │
│ │
└─────────────────────────────────────────────────────────────┘第四部分：frozenset
不可变集合
概念说明
frozenset 是不可变版本的集合，创建后不能修改，可以作为字典键或集合元素。
python
# 创建 frozenset
fs = frozenset([1, 2, 3, 4, 5])
print(fs) # frozenset({1, 2, 3, 4, 5})
# 从集合创建
s = {1, 2, 3}
fs = frozenset(s)
# 空 frozenset
empty_fs = frozenset()
# frozenset 的特点
fs = frozenset([1, 2, 3])
# fs.add(4) # AttributeError
# fs.remove(1) # AttributeError
# frozenset 支持集合运算
a = frozenset([1, 2, 3])
b = frozenset([2, 3, 4])
print(a | b) # frozenset({1, 2, 3, 4})
print(a & b) # frozenset({2, 3})
# 作为字典键
d = {frozenset([1, 2]): "value"}
print(d[frozenset([1, 2])]) # value
# 作为集合元素
nested = {frozenset([1, 2]), frozenset([3, 4])}
print(nested)set vs frozenset
┌─────────────────────────────────────────────────────────────┐
│ set vs frozenset 对比 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 特性 set frozenset │
│ ───────────────────────────────────────────── │
│ 可变性 可变 不可变 │
│ 可哈希 ❌ ✅ │
│ 作为字典键 ❌ ✅ │
│ 作为集合元素 ❌ ✅ │
│ 添加/删除 ✅ ❌ │
│ 集合运算 ✅ ✅ │
│ │
│ 使用场景： │
│ set：需要修改、去重、快速查找 │
│ frozenset：需要不可变、作为键、作为元素 │
│ │
└─────────────────────────────────────────────────────────────┘第五部分：集合应用
去重
python
# 列表去重
numbers = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
unique = list(set(numbers))
print(unique) # [1, 2, 3, 4]（顺序可能改变）
# 保持顺序的去重
def dedupe_ordered(items):
seen = set()
result = []
for item in items:
if item not in seen:
seen.add(item)
result.append(item)
return result
numbers = [3, 1, 2, 1, 3, 2, 4]
print(dedupe_ordered(numbers)) # [3, 1, 2, 4]
# 字符串去重
text = "hello world"
unique_chars = "".join(set(text)) # 顺序不确定
print(unique_chars)
# 保持顺序的字符串去重
unique_chars = "".join(dedupe_ordered(text))
print(unique_chars) # "helo wrd"成员检查
python
# 集合 vs 列表的成员检查性能
import timeit
large_list = list(range(100000))
large_set = set(range(100000))
# 列表查找 O(n)
list_time = timeit.timeit('99999 in large_list', globals=globals(), number=1000)
print(f"列表查找: {list_time:.4f}s")
# 集合查找 O(1)
set_time = timeit.timeit('99999 in large_set', globals=globals(), number=1000)
print(f"集合查找: {set_time:.4f}s")
# 集合查找快几个数量级！
# 实际应用：验证有效用户
valid_users = {"alice", "bob", "charlie", "david"}
def is_valid_user(username):
return username in valid_users
print(is_valid_user("alice")) # True
print(is_valid_user("eve")) # False数据分析
python
# 找出两个列表的共同元素
list1 = [1, 2, 3, 4, 5]
list2 = [4, 5, 6, 7, 8]
common = set(list1) & set(list2)
print(common) # {4, 5}
# 找出只在一个列表中的元素
only_in_list1 = set(list1) - set(list2)
only_in_list2 = set(list2) - set(list1)
print(only_in_list1) # {1, 2, 3}
print(only_in_list2) # {6, 7, 8}
# 找出所有出现过的元素
all_elements = set(list1) | set(list2)
print(all_elements) # {1, 2, 3, 4, 5, 6, 7, 8}
# 词频分析
text = "the quick brown fox jumps over the lazy dog"
words = text.split()
unique_words = set(words)
print(f"总词数: {len(words)}")
print(f"不重复词数: {len(unique_words)}")
# 标签系统
article_tags = {
"article1": {"python", "programming", "tutorial"},
"article2": {"python", "web", "django"},
"article3": {"javascript", "web", "react"}
}
# 找出所有标签
all_tags = set()
for tags in article_tags.values():
all_tags |= tags
print(all_tags)
# 找出包含特定标签的文章
def find_articles_by_tag(tag):
return {article for article, tags in article_tags.items() if tag in tags}
print(find_articles_by_tag("python")) # {'article1', 'article2'}第六部分：集合性能
时间复杂度
┌─────────────────────────────────────────────────────────────┐
│ 集合操作时间复杂度 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 操作 平均情况 最坏情况 │
│ ───────────────────────────────────────────── │
│ x in s O(1) O(n) │
│ s.add(x) O(1) O(n) │
│ s.remove(x) O(1) O(n) │
│ s.discard(x) O(1) O(n) │
│ len(s) O(1) O(1) │
│ s | t O(len(s)+len(t)) │
│ s & t O(min(len(s), len(t))) │
│ s - t O(len(s)) │
│ │
│ 最坏情况：哈希冲突严重时 │
│ │
└─────────────────────────────────────────────────────────────┘内存优化
python
import sys
# 集合 vs 列表内存占用
lst = list(range(1000))
s = set(range(1000))
print(f"列表内存: {sys.getsizeof(lst)} 字节")
print(f"集合内存: {sys.getsizeof(s)} 字节")
# 集合通常占用更多内存（哈希表开销）
# 但查找速度更快
# 小集合优化
# Python 对小集合有优化，但创建成本仍高于列表第七部分：常见错误
常见陷阱
python
# 陷阱 1：空集合创建
s = {} # ❌ 这是字典！
s = set() # ✅ 正确
# 陷阱 2：集合元素类型
# s = {[1, 2]} # TypeError: unhashable type: 'list'
s = {(1, 2)} # ✅ 元组可以
# 陷阱 3：遍历时修改
s = {1, 2, 3, 4, 5}
# ❌ 错误
# for x in s:
# if x == 3:
# s.remove(x) # RuntimeError
# ✅ 正确
to_remove = {x for x in s if x == 3}
s -= to_remove
# 陷阱 4：集合无序
s = {3, 1, 4, 1, 5, 9}
print(s) # 顺序不确定！
# 不要依赖集合的顺序
# 陷阱 5：浮点数元素
s = {0.1 + 0.2, 0.3}
print(s) # 可能有两个元素（浮点精度问题）
# 陷阱 6：布尔值和整数
s = {True, 1, False, 0}
print(s) # {False, True}（True == 1, False == 0）从简单到复杂：集合的渐进应用
层级1：去重
python
# 列表去重
numbers: list[int] = [1, 2, 2, 3, 3, 3, 4]
unique: set[int] = set(numbers)
print(unique) # {1, 2, 3, 4}层级2：成员检测
python
# 快速判断存在（O(1)）
allowed_users: set[str] = {"admin", "manager", "editor"}
user: str = "admin"
if user in allowed_users:
print(f"{user} 有权限")层级3：集合运算
python
# 交集：共同元素
group_a: set[int] = {1, 2, 3, 4}
group_b: set[int] = {3, 4, 5, 6}
common: set[int] = group_a & group_b
print(common) # {3, 4}层级4：差集应用
python
# 找出新增和删除的用户
old_users: set[str] = {"user1", "user2", "user3"}
new_users: set[str] = {"user2", "user3", "user4"}
added: set[str] = new_users - old_users # 新增
removed: set[str] = old_users - new_users # 删除
print(f"新增：{added}") # {'user4'}
print(f"删除：{removed}") # {'user1'}层级5：数据清洗
python
# 清洗重复数据
from typing import Any
def clean_data(records: list[dict[str, Any]]) -> list[dict[str, Any]]:
"""根据 id 去重"""
seen_ids: set[int] = set()
result: list[dict[str, Any]] = []
for record in records:
record_id: int = record["id"]
if record_id not in seen_ids:
seen_ids.add(record_id)
result.append(record)
return result综合应用：用户权限管理系统
这个示例综合运用集合的多个知识点：
python
# 用户权限管理系统（Python 3.11+）
from typing import Any
class PermissionManager:
"""权限管理器"""
def __init__(self) -> None:
# 角色权限映射
self._role_permissions: dict[str, set[str]] = {
"admin": {"read", "write", "delete", "manage_users"},
"editor": {"read", "write", "edit"},
"viewer": {"read"}
}
# 用户角色映射
self._user_roles: dict[str, set[str]] = {}
def assign_role(self, user: str, role: str) -> None:
"""给用户分配角色"""
if user not in self._user_roles:
self._user_roles[user] = set()
self._user_roles[user].add(role)
def get_user_permissions(self, user: str) -> set[str]:
"""获取用户所有权限（并集）"""
permissions: set[str] = set()
for role in self._user_roles.get(user, set()):
permissions |= self._role_permissions.get(role, set())
return permissions
def has_permission(self, user: str, permission: str) -> bool:
"""检查用户是否有某个权限"""
return permission in self.get_user_permissions(user)
def get_users_with_permission(self, permission: str) -> set[str]:
"""获取有某个权限的所有用户"""
users: set[str] = set()
for user in self._user_roles:
if self.has_permission(user, permission):
users.add(user)
return users
# 使用示例
pm = PermissionManager()
pm.assign_role("张三", "admin")
pm.assign_role("李四", "editor")
pm.assign_role("王五", "viewer")
print("张三权限：", pm.get_user_permissions("张三"))
print("李四能删除吗？", pm.has_permission("李四", "delete"))
print("有管理权限的用户：", pm.get_users_with_permission("manage_users"))这个示例展示了：
- 集合存储权限列表
- 集合并集运算（|=）
- 集合成员检测
- 集合与字典的组合使用
- 类型提示的现代语法
L2 实践层：用好
最佳实践
集合方法选择指南
| 场景 | 推荐方法 | 原因 |
|---|---|---|
| 添加单个元素 | add() | 简洁，语义明确 |
| 添加多个元素 | update() | 一次添加多个 |
| 删除元素（确定存在） | remove() | 语义明确，不存在时报错 |
| 删除元素（不确定存在） | discard() | 安全，不报错 |
| 清空集合 | clear() | 比 s = set() 更明确 |
| 并集（不修改原集合） | `s1 | s2` |
| 交集（不修改原集合） | s1 & s2 | 创建新集合 |
| 原地修改 | ` | =, &=, -=` |
| 快速去重 | set(list) | 一行完成 |
| 保持顺序去重 | 遍历 + seen集合 | 保留原顺序 |
反模式：不要这样做
python
# ❌ 反模式 1：用 {} 创建空集合
s = {} # 这是字典！
type(s) # <class 'dict'>
# ✅ 正确做法
s = set() # 空集合
type(s) # <class 'set'>python
# ❌ 反模式 2：依赖集合顺序
s = {3, 1, 4, 1, 5}
first = list(s)[0] # 不确定是哪个元素！
# ✅ 正确做法：需要顺序时用列表
lst = [3, 1, 4, 1, 5]
unique_ordered = list(dict.fromkeys(lst)) # 保持顺序去重python
# ❌ 反模式 3：遍历时修改集合
s = {1, 2, 3, 4, 5}
for x in s:
if x > 3:
s.remove(x) # RuntimeError!
# ✅ 正确做法：先收集再删除
to_remove = {x for x in s if x > 3}
s -= to_remove
# 或遍历副本
for x in set(s):
if x > 3:
s.discard(x)python
# ❌ 反模式 4：用列表做成员检查
valid_ids = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
if 5 in valid_ids: # O(n)
# ✅ 正确做法：用集合
valid_ids = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
if 5 in valid_ids: # O(1)python
# ❌ 反模式 5：True/False 与整数混用
s = {True, 1, False, 0}
print(s) # {False, True} # True == 1, False == 0，只保留两个
# ✅ 正确做法：避免混用
s_bool = {True, False}
s_int = {0, 1, 2, 3}python
# ❌ 反模式 6：浮点数作为元素（精度问题）
s = {0.1 + 0.2, 0.3}
print(len(s)) # 可能是 2（0.1+0.2 ≠ 0.3）
# ✅ 正确做法：用 Decimal 或字符串
from decimal import Decimal
s = {Decimal('0.1') + Decimal('0.2'), Decimal('0.3')} # 确保精度适用场景
| 场景 | 是否推荐集合 | 原因 |
|---|---|---|
| 去重 | ✅ 推荐 | 自动去重 |
| 快速成员检查 | ✅ 推荐 | O(1) vs 列表 O(n) |
| 集合运算（交/并/差） | ✅ 推荐 | 内置运算符 |
| 存储唯一元素 | ✅ 推荐 | 天然不重复 |
| 需要顺序 | ❌ 用列表 | 集合无序 |
| 需要索引访问 | ❌ 用列表 | 集合不支持索引 |
| 需要键值映射 | ❌ 用字典 | 集合只有键 |
| 需要作为字典键 | frozenset | set 不可哈希 |
性能专项：集合操作 vs 列表循环
python
import timeit
list_a = list(range(1000))
list_b = list(range(500, 1500))
# ✅ 集合交集 — O(min(n, m))
set_a, set_b = set(list_a), set(list_b)
print(timeit.timeit('set_a & set_b', globals=globals(), number=10000))
# ~0.003s
# ❌ 列表循环找交集 — O(n * m)
print(timeit.timeit('[x for x in list_a if x in list_b]', globals=globals(), number=10000))
# ~0.6s（慢 200 倍！）
# 结论：求交集/差集/并集 → 先转集合再运算frozenset 最佳实践
python
# ✅ frozenset 用于常量集合
VALID_STATUSES: frozenset[str] = frozenset({"active", "pending", "completed"})
ACTIVE_STATES: frozenset[str] = frozenset({"running", "paused"})
# ✅ 作为字典键（普通 set 不行）
state_machine: dict[frozenset[str], str] = {
frozenset({"idle"}): "启动",
frozenset({"running"}): "运行中",
frozenset({"running", "error"}): "出错",
}
# ❌ 反模式：用 tuple 存储无序集合
# choices = ("read", "write", "delete") # tuple 有序，语义不对
# ✅ 正确
choices = frozenset({"read", "write", "delete"})
# ✅ frozenset 作为集合元素（实现嵌套集合）
nested = {frozenset({"a", "b"}), frozenset({"c", "d"})}
print(frozenset({"a", "b"}) in nested) # True（O(1) 查找）set 去重 vs dict.fromkeys 去重（保持顺序）
python
data = [3, 1, 2, 1, 3, 2, 4]
# set 去重 — 顺序丢失
unique_set = list(set(data)) # [1, 2, 3, 4] 顺序不确定
# dict.fromkeys 去重 — 保持顺序（Python 3.7+）
unique_ordered = list(dict.fromkeys(data)) # [3, 1, 2, 4] 保持首次出现顺序
# 结论：需要保持顺序 → dict.fromkeys()，否则 → set()L3 专家层：深入
底层原理：哈希表（与字典类似）
Python 如何实现集合
集合底层使用哈希表，与字典类似但只存储键：
集合内部结构：
┌─────────────────────────────────────────────────────────────┐
│ 哈希表原理 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 集合 = 字典只存键（值为占位符） │
│ │
│ 内存布局（简化）： │
│ ┌────────────────────────────────────────────┐ │
│ │ hash(elem1) | elem1 | placeholder │ │
│ │ hash(elem2) | elem2 | placeholder │ │
│ │ hash(elem3) | elem3 | placeholder │ │
│ └────────────────────────────────────────────┘ │
│ │
│ 与字典的区别： │
│ ───────────────────────────────────────────── │
│ • 字典：存储键和值 │
│ • 集合：只存储键（值是 dummy） │
│ • 内存：集合比字典略小 │
│ │
│ 去重原理： │
│ ───────────────────────────────────────────── │
│ 1. hash(new_elem) → 哈希值 │
│ 2. 检查该位置是否已有相同哈希 │
│ 3. 比较元素是否相等 │
│ 4. 相等 → 添加失败（已存在） │
│ 5. 不相等 → 找下一个空位（冲突处理） │
│ │
└─────────────────────────────────────────────────────────────┘性能考量
python
import sys
import timeit
# 内存对比
lst = list(range(1000))
s = set(range(1000))
d = {i: None for i in range(1000)}
print(f"列表: {sys.getsizeof(lst)} bytes") # ~9KB
print(f"集合: {sys.getsizeof(s)} bytes") # ~32KB（哈希开销）
print(f"字典: {sys.getsizeof(d)} bytes") # ~36KB
# 集合比列表内存大，但查找快
# 集合比字典内存小（无值存储）| 操作 | 集合 | 列表 | 说明 |
|---|---|---|---|
| 成员检查 | O(1) | O(n) | 集合快 1000x+ |
| 添加 | O(1) | O(1)末尾/O(n)开头 | 相同 |
| 删除 | O(1) | O(n) | 集合快 |
| 内存 | 大 | 小 | 集合哈希开销 |
| 有序性 | 无 | 有 | 需顺序用列表 |
设计动机
| 设计选择 | 原因 | 影响 |
|---|---|---|
| 哈希表 | 快速查找 | O(1) 成员检查 |
| 无序 | 简化实现 | 不保证顺序 |
| 自动去重 | 数学定义 | 符合集合概念 |
| 元素可哈希 | 哈希表要求 | list/dict/set 不能作为元素 |
知识关联
集合知识关联图：
┌─────────────────┐
│ 哈希函数 │
│ hash() │
└─────────────────┘
│
┌───────────────┼───────────────┐
│ │ │
▼ ▼ ▼
┌───────────┐ ┌───────────┐ ┌───────────┐
│ 集合 │ │ 字典 │ │ frozenset │
│ set │ │ dict │ │ 不可变 │
│ 只存键 │ │ 键+值 │ │ 可哈希 │
└───────────┘ └───────────┘ └───────────┘
│
│ 数学运算
▼
┌───────────────────────────────┐
│ 集合运算 │
│ • | 并集 │
│ • & 交集 │
│ • - 差集 │
│ • ^ 对称差集 │
│ • issubset/issuperset │
└───────────────────────────────┘
对比：
set ──→ 无序、不重复、O(1)查找
list ──→ 有序、可重复、O(n)查找
dict ──→ 键值映射、不重复键、O(1)查找字节码验证：集合 vs 列表成员检查
python
import dis
# 集合成员检查 — 直接哈希表定位
def set_membership(s):
return "target" in s
dis.dis(set_membership)
# 输出：
# LOAD_FAST 'target'
# LOAD_FAST 's'
# CONTAINS_OP 0 ← 集合专用：哈希表定位 O(1)
# 列表成员检查 — 逐个遍历比较
def list_membership(lst):
return "target" in lst
dis.dis(list_membership)
# 同样的字节码 CONTAINS_OP，但 list 内部是线性遍历
# 验证：CONTAINS_OP 是一条指令，但底层行为完全不同
import timeit
s = set(range(10000))
lst = list(range(10000))
# 集合：~0.04s（100000 次）
print(timeit.timeit('9999 in s', globals={'s': s}, number=100000))
# 列表：~5.0s（100000 次）
print(timeit.timeit('9999 in lst', globals={'lst': lst}, number=100000))
# 结论：同一条字节码指令，但时间复杂度 O(1) vs O(n)，差距 ~1000 倍哈希冲突演示与验证
python
# 集合的去重基于 __hash__ 和 __eq__
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __hash__(self):
return hash((self.x, self.y))
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
def __repr__(self):
return f"Point({self.x}, {self.y})"
s = {Point(1, 2), Point(1, 2), Point(3, 4)}
print(s) # {Point(1, 2), Point(3, 4)} — 自动去重
# 查看哈希值分布
points = {Point(i % 3, i % 3) for i in range(100)}
print(len(points)) # 3 — 只有 3 个唯一坐标
# 验证 O(1) 查找
import timeit
big_set = set(range(1_000_000))
print(timeit.timeit('999999 in big_set', globals=globals(), number=100000))
# ~0.005s — 与集合大小无关本章小结
┌─────────────────────────────────────────────────────────────┐
│ 集合 知识要点 │
├─────────────────────────────────────────────────────────────┤
│ │
│ 创建： │
│ ✓ {1, 2, 3}、set()、set(iterable) │
│ ✓ 空集合必须用 set()，不能用 {} │
│ │
│ 特点： │
│ ✓ 无序、不重复、元素可哈希 │
│ ✓ 查找 O(1) │
│ │
│ 操作： │
│ ✓ 添加：add、update、|= │
│ ✓ 删除：remove（报错）、discard（不报错）、pop、clear │
│ │
│ 运算： │
│ ✓ | 并集、& 交集、- 差集、^ 对称差集 │
│ ✓ issubset、issuperset、isdisjoint │
│ │
│ frozenset： │
│ ✓ 不可变集合 │
│ ✓ 可作为字典键、集合元素 │
│ │
│ 应用： │
│ ✓ 去重、成员检查、集合运算 │
│ │
└─────────────────────────────────────────────────────────────┘