一、先搞懂底层：什么是「哈希」？
想象你去超市存包：
- 普通列表（list）：像一排没有号码的柜子。你要找一个包，只能逐个打开看，最坏情况下要翻遍所有柜子。查找速度 O(n)。
- 哈希表（Hash Table）：像智能存包柜。你输入手机号，系统立刻算出「3号柜」，你直接去3号柜取包。查找速度接近 O(1)。
核心原理：通过一个「哈希函数」，把任意数据（字符串、数字、元组等）转换成固定长度的数字（哈希值），这个数字就是数据的「门牌号」。Python 的 dict 和 set 底层都是基于哈希表实现的。
二、字典（dict）—— 带「门牌号」的储物柜
1. 一句话定义
字典是键值对（key-value）的集合。每个 key 必须唯一且不可变，通过 key 可以在常数时间内找到对应的 value。
2. 生活中的类比
就像一本通讯录：
# 创建字典的多种方式
phone_book = {"Alice": "13800138000", "Bob": "13900139000"}
phone_book = dict(Alice="13800138000", Bob="13900139000")
phone_book = dict([("Alice", "13800138000"), ("Bob", "13900139000")])
# 空字典
empty = {}
empty = dict()
3. 核心操作详解
增 & 改
phone_book = {"Alice": "13800138000"}
# 新增：key 不存在就添加
phone_book["Charlie"] = "13700137000"
# 修改：key 存在就覆盖
phone_book["Alice"] = "15000150000"
# 批量更新
phone_book.update({"David": "13600136000", "Alice": "99999999999"})
查
# 方式1：直接索引（key 不存在会报错 KeyError）
num = phone_book["Alice"]
# 方式2：get()（key 不存在返回 None 或默认值，不会报错）
num = phone_book.get("Eve") # None
num = phone_book.get("Eve", "未知") # "未知"
# 方式3：判断是否存在
if"Alice"in phone_book: # 这里底层就是哈希查找，速度极快
print("找到了！")
删
# 删除并返回值
num = phone_book.pop("Alice")
# 删除不报错
phone_book.pop("Eve", None)
# 清空
phone_book.clear()
4. 遍历字典
info = {"name": "小明", "age": 18, "city": "北京"}
# 遍历键（默认）
for key in info:
print(key)
# 遍历值
for value in info.values():
print(value)
# 遍历键值对
for key, value in info.items():
print(f"{key}: {value}")
5. 对 key 的严格要求
key 必须是不可变类型（hashable）：
- ✅ 可用：字符串、数字、元组（元组内部元素也必须是不可变的）
# 正确
d = {(1, 2): "坐标点"} # 元组可以
d = {3.14: "圆周率"} # 浮点数可以
# 错误！会报错
# d = {[1, 2]: "列表"} # TypeError: unhashable type: 'list'
为什么列表不能当 key？因为列表是可变的——如果允许列表当 key，你后面改了列表里的元素，它的哈希值就变了，字典就找不到它了，整个哈希表会乱套。
三、集合（set）—— 只存「门牌号」的储物柜
1. 一句话定义
集合是无序、不重复的元素集合。它只关心「某个元素在不在集合里」，不存储额外的 value。
2. 生活中的类比
- 黑名单系统：手机号要么在黑名单里，要么不在。不关心这个手机号对应什么信息。
- 去重工具：把一堆重复的数据扔进去，出来就是唯一值。
# 创建集合
s = {1, 2, 3, 3, 3} # 自动去重，结果是 {1, 2, 3}
s = set([1, 2, 2, 3, 3]) # 从列表转换，结果也是 {1, 2, 3}
# 空集合（注意：{} 是空字典！）
empty = set() # 正确
# empty = {} # 错误！这是字典
3. 核心操作详解
增删查
s = {1, 2, 3}
# 添加元素
s.add(4) # {1, 2, 3, 4}
s.add(3) # 重复添加无效，仍然是 {1, 2, 3, 4}
# 删除
s.remove(3) # 元素不存在会报错 KeyError
s.discard(3) # 元素不存在也不报错（更安全）
# 随机删除并返回一个元素
elem = s.pop()
# 判断是否存在
if2in s: # O(1) 速度
print("存在")
集合运算（set 的杀手锏）
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
# 并集：所有出现的元素（A ∪ B）
a | b # {1, 2, 3, 4, 5, 6}
a.union(b)
# 交集：共同拥有的元素（A ∩ B）
a & b # {3, 4}
a.intersection(b)
# 差集：在 A 但不在 B（A - B）
a - b # {1, 2}
a.difference(b)
# 对称差集：只在 A 或只在 B，不同时在两边（A △ B）
a ^ b # {1, 2, 5, 6}
a.symmetric_difference(b)
# 子集判断
{1, 2}.issubset(a) # True
a.issuperset({1, 2}) # True
4. 经典应用场景
场景1：去重（最常用）
nums = [1, 2, 2, 3, 3, 3, 4]
unique_nums = list(set(nums)) # [1, 2, 3, 4]
场景2：快速判断「是否已存在」
# 检查用户是否重复投票
voted = set()
defvote(user_id):
if user_id in voted:
return"您已经投过票了"
voted.add(user_id)
return"投票成功"
场景3：找两个列表的共同元素
list_a = ["apple", "banana", "cherry"]
list_b = ["banana", "date", "fig"]
common = set(list_a) & set(list_b) # {'banana'}
四、dict 和 set 的底层原理
1. 哈希函数的工作流程
以 d = {"apple": 100} 为例：
- 计算
"apple" 的哈希值：hash("apple") → 得到一个很大的整数 - 对这个整数取模，映射到数组的某个索引位置：
index = hash("apple") % array_size - 把
"apple" 和 100 打包成一个条目，放到数组的 index 位置 - 下次查找
"apple" 时，重复步骤 1-2，直接定位到同一个位置，取出 100
2. 哈希冲突（Collision）
不同 key 的哈希值可能相同（就像两个人手机号不同但存包柜算出来都是3号）。Python 解决冲突的方法是开放寻址法（Open Addressing）：
- 如果3号柜被占了，就按固定规则试4号、5号……直到找到空位。
- 查找时也一样：先算3号，不对就继续试下一个，直到找到或遇到空位。
3. 动态扩容
当字典/集合里的元素越来越多，冲突概率上升，Python 会自动扩容（把数组变大，重新分配所有元素）。扩容时所有元素要重新计算位置，所以偶尔某次插入会变慢，但平均下来仍然是 O(1)。
五、dict vs set 对比总结
| | |
|---|
| 存储内容 | | |
| key/元素要求 | | |
| 查找速度 | | |
| 有序性 | | |
| 重复处理 | | |
| 主要用途 | | |
六、常见坑与注意事项
坑1：用可变对象当 key
# 错误
d = {["a"]: 1} # TypeError: unhashable type: 'list'
# 解决：把列表转成元组
d = {tuple(["a"]): 1} # 正确
坑2：自定义对象作为 key 的问题
classPerson:
def__init__(self, name):
self.name = name
p = Person("Alice")
d = {p: "员工"}
# 如果修改了 p 的属性，可能导致字典找不到它
# 因为哈希值是基于对象创建时的状态计算的
坑3：集合不能存列表、字典
s = {[1, 2], [3, 4]} # TypeError
s = {(1, 2), (3, 4)} # 正确，元组可以
坑4：set() 和 {} 的区别
a = {} # 这是空字典！
b = set() # 这才是空集合
七、一句话记忆口诀
字典是「查字典」：给一个词（key），找到释义（value）。
集合是「查名单」：只看某个人在不在名单里，不关心他具体是干嘛的。
两者底层都是哈希表，所以查找都飞快，但key/元素必须不可变。
