失物报告单
LOST-012
报告人
失物保管处 韩主管
丢了什么
幽灵箱子 B 的行李。上个月登记进了失物储物柜（dict），可失主来取时，查询结果却是“没有”。储物柜 L7 至今还锁着。
结案条件
用储物柜查找格子的原理查明原因，打开 L7，用不会改变的键重新保管。
天空岛国际机场 行李中心
昨天，13 号传送带上的两个幽灵箱子被清走了。剩下的只有保管台账上的一行：上个月 B 被登记进了失物储物柜，可失主来取时，台账回答“没有”。B 又回到了传送带上，后面的事就是到昨天为止的故事了。
韩主管重新打开当时的台账给大家看。把清单打印出来，B 明明就在里面；可用 in 一问，得到的却是 False。都美兰班长接过最后一张报告单，说：“储物柜号码是由箱子决定的。放进去之后箱子变了，号码也就变了。”
== 确认（8 分钟）dict 和 set 是有很多格子的储物柜。放入或查找键时，每次都走同样的步骤：
hash(key) 求出键的哈希（储物柜号码）。== 确认是不是同一个键。不是的话，就按规定的规则去看下一格。所以需要一条约定：如果 a == b，那么 hash(a) == hash(b) 必须成立。否则相同的键从不同的格子开始找，就永远碰不上了。
print(1 == 1.0 == True, hash(1) == hash(1.0) == hash(True))
# True True
print({1: "int", 1.0: "float", True: "bool"})
# {1: 'bool'}1、1.0、True 互相 ==，所以哈希也相同，在 dict 里是同一个键。键保留的是最先放进去的 1，只有值换成了最后那个。
反过来则不必成立。哈希相同而值不同的冲突是正常的，第 4 步的 == 会把它们区分开。
print(hash(42), hash(-1), hash(-2))
# 42 -2 -2
print(hash(-1) == hash(-2), -1 == -2)
# True False
lockers = {-1: "A", -2: "B"}
print(lockers[-1], lockers[-2])
# A B在 CPython 中，小整数的哈希就是它自己。不过 -1 在 C 内部表示“出错”，所以 hash(-1) 是 -2。这是冲突，但 dict 能毫无问题地区分两者。
字符串的哈希每次运行程序都会不同。这是为了防止有人预测哈希值来发动攻击。如果需要相同的值（比如复现测试），就固定环境变量 PYTHONHASHSEED。
$ python -c "print(hash('T1'))"
# 例如：4646783657884298203
$ python -c "print(hash('T1'))"
# 例如：-1769311965495050168
$ PYTHONHASHSEED=0 python -c "print(hash('T1'))"
# 每次运行都是同一个值所以不要把哈希值存进文件，或者和别的进程交换。哈希是只在一次运行内部使用的号码。
下面的储物柜简化成了 8 个格子。从哈希除以 8 的余数那一格开始，有东西就去紧挨着的下一格。依次放入 7 和 15、-1 和 -2，制造一下冲突。
储物柜
这是一个 8 格的简化哈希表。CPython 的 dict 选格的顺序更复杂，但“用哈希找格，用 == 确认”的原理相同。
储物柜按放入时算出的号码把键放进格子，之后就不再重新计算号码。如果放进去之后键的值变了、哈希也变了，会怎样？用一个故意写错的键来确认。
class Tag:
def __init__(self, n):
self.n = n
def __eq__(self, other):
return isinstance(other, Tag) and self.n == other.n
def __hash__(self):
return hash(self.n) # 失误：用会变的值来算哈希
def __repr__(self):
return f"Tag({self.n})"
key = Tag(3)
lockers = {key: "bag B"}
print(Tag(3) in lockers)
# True
key.n = 13
print(lockers)
# {Tag(13): 'bag B'}
print(Tag(13) in lockers, Tag(3) in lockers, key in lockers)
# False False False清单里明明显示着 Tag(13)，可怎么问都是 False。
Tag(13) 找：从哈希 13 的格子开始。箱子在哈希 3 的格子里，所以碰不上。Tag(3) 找：能走到哈希 3 的格子。可那一格里的键现在是 Tag(13)，== 为 False。key 本身找：它现在的哈希是 13，走的是和第一种一样的路。# 接着上面的例子
key.n = 3
print(Tag(3) in lockers)
# True把值改回 3，又能找到了。箱子从头到尾都待在放进去的那一格里，变的只是用来找格子的号码。
储物柜
这是一个 8 格的简化哈希表。CPython 的 dict 选格的顺序更复杂，但“用哈希找格，用 == 确认”的原理相同。
所以 Python 干脆不接受值会变的内置类型作为键。list、dict、set 都没有哈希。
lockers = {}
lockers[[1, 2]] = "bag"
# TypeError: cannot use 'list' as a dict key (unhashable type: 'list')print(hash((1, 2)) == hash((1, 2)))
# True
hash((1, [2]))
# TypeError: unhashable type: 'list'元组可以做键，但里面装着列表时就算不出哈希。正如第 2 课所见，元组的不可变只是“装着的引用”不可变；里面的列表一变，哈希也就得跟着变。当作键使用时，要用 (1, (2,)) 或 frozenset 这种从里到外都不可变的值。
小钉提示
→ dict 的键和 set 的元素，必须是“放进去之后不会变的东西”。非改不可的话，就先取出来（pop），再用新键放回去。
什么都没定义的类，用 is 判断相等，哈希也按身份来算，所以实例可以当键用。可一旦只定义了 __eq__，Python 就会把 __hash__ 设成 None（第 8 课预告过）。因为相等的标准变了，还沿用旧的哈希就会破坏约定。
class Label:
def __init__(self, code):
self.code = code
def __eq__(self, other):
return isinstance(other, Label) and self.code == other.code
print(Label("T1") == Label("T1"), Label.__hash__)
# True None
{Label("T1")}
# TypeError: cannot use 'Label' as a set element (unhashable type: 'Label')需要哈希的话，有两种办法。
1. @dataclass(frozen=True)：按字段生成 __eq__ 和 __hash__，并禁止修改字段。
from dataclasses import dataclass
@dataclass(frozen=True)
class Tag:
n: int
key = Tag(3)
lockers = {key: "bag B"}
print(lockers[Tag(3)])
# bag B
key.n = 13
# dataclasses.FrozenInstanceError: cannot assign to field 'n'不加 frozen、只写 @dataclass 的话，只会生成 __eq__，所以 __hash__ 是 None。要当键用的类，就加上 frozen=True。
2. 自己写 __hash__：把 __eq__ 里比较的字段原样组成元组，再求哈希。
class Route:
def __init__(self, origin, dest):
self.origin = origin
self.dest = dest
def __eq__(self, other):
if not isinstance(other, Route):
return NotImplemented
return (self.origin, self.dest) == (other.origin, other.dest)
def __hash__(self):
return hash((self.origin, self.dest))
seen = {Route("ICN", "NRT")}
print(Route("ICN", "NRT") in seen, len({Route("ICN", "NRT"), Route("ICN", "NRT")}))
# True 1自己写的时候有三条规则：
__eq__ 比较的同样的字段来算哈希。NotImplemented 而不是 False（第 8 课）。作为最后的课题，班长拿出了中心的旧管理程序。十一次报告里遇到的 bug，全都在这一个文件里。先看运行结果。
import gc
import weakref
class Bag:
stickers = [] # 类属性上放了可变列表
def __init__(self, code, items=[]): # 默认参数列表
self.code = code
self.items = items
self.partner = None
def __eq__(self, other):
return isinstance(other, Bag) and self.code == other.code
def __hash__(self):
return hash(self.code) # 用会变的值算哈希
a = Bag("A1")
b = Bag("B1")
a.items.append("camera")
a.stickers.append("fragile")
print(b.items, b.stickers)
# ['camera'] ['fragile']
shelves = [[]] * 3 # 同一个列表三次
shelves[0].append("A1")
print(shelves)
# [['A1'], ['A1'], ['A1']]
calls = [lambda: f"gate {g}" for g in (1, 2, 3)]
print([call() for call in calls])
# ['gate 3', 'gate 3', 'gate 3']
lockers = {b: "L7"}
b.code = "B2" # 放进去之后改了键
print(Bag("B1") in lockers, Bag("B2") in lockers)
# False False
a.partner, b.partner = b, a # 互相装着对方的两个箱子
watch = weakref.ref(a)
del a, b, lockers
print(watch() is None)
# False
gc.collect()
print(watch() is None)
# True逐行找出原因，做成一份检查清单。
| 症状 | 原因 | 修正 | 课次 |
|---|---|---|---|
| 放进 A 的相机，B 里也有 | 默认参数 items=[] 只在定义时创建一次 | 用 items=None 接收，在函数里新建列表 | 4 |
| 贴纸贴到了所有箱子上 | 类属性 stickers = [] 由所有实例共用 | 在 __init__ 里改为实例属性 | 7 |
| 三层货架一起变 | [[]] * 3 是同一个列表的三个引用 | [[] for _ in range(3)] | 3 |
| 提示全都是 gate 3 | lambda 拿着的不是值，而是变量 g（延迟绑定） | lambda g=g: ... | 6 |
| 在储物柜里找不到 B | 放进去之后改了键的值，哈希变了 | 用不会变的值当键，要改时就挪键 | 12 |
| 名牌全摘了，箱子还在 | partner 之间的循环引用 | 把一边改成 weakref.ref | 11 |
这是修好的程序，输出全都变成了预期的样子。
import weakref
class Bag:
def __init__(self, code, items=None):
self.code = code
self.items = [] if items is None else list(items)
self.stickers = []
self._partner = None
@property
def partner(self):
return self._partner() if self._partner is not None else None
@partner.setter
def partner(self, other):
self._partner = weakref.ref(other)
a = Bag("A1")
b = Bag("B1")
a.items.append("camera")
a.stickers.append("fragile")
print(b.items, b.stickers)
# [] []
shelves = [[] for _ in range(3)]
shelves[0].append("A1")
print(shelves)
# [['A1'], [], []]
calls = [lambda g=g: f"gate {g}" for g in (1, 2, 3)]
print([call() for call in calls])
# ['gate 1', 'gate 2', 'gate 3']
lockers = {b.code: "L7"} # 键是不会变的字符串
lockers["B2"] = lockers.pop(b.code) # 改编号时把键挪过去
b.code = "B2"
print("B1" in lockers, "B2" in lockers, lockers[b.code])
# False True L7
a.partner, b.partner = b, a
watch = weakref.ref(a)
del a, b, lockers
print(watch() is None)
# True用 items=list(items) 把收到的东西复制一份，也是第 4 课的防御性复制。Bag 去掉了 __eq__ 和 __hash__，所以箱子本身按身份比较，键则交给字符串编号来担当。
用标签板对比一下前两个 bug（默认参数、类属性）。在 bug 中，两个实例的 items 箭头汇聚到同一个列表，stickers 则挂在规格书（class）盒子上。
标签板
步骤 1 / 0
下一行将执行: 0
正在准备实验台…
刚刚变化的
封口的箱子（不可变）
用一句话回顾这十二节课。
| 课次 | 标题 | 一句话 |
|---|---|---|
| 1 | 标签不是箱子：名字与对象 | = 把名牌挂到对象上。is 看是否同一个对象，== 看值是否相等。 |
| 2 | 封口的箱子：可变与不可变 | 不可变对象的“修改”是新对象加重新绑定。+= 随类型有两副面孔。 |
| 3 | 箱中箱：容器与复制 | 容器装的是引用。浅复制只复制一层，deepcopy 一路到底。 |
| 4 | 交出箱子的时候：函数与参数 | 函数给同一个对象多挂一个标签。默认参数只创建一次。 |
| 5 | 区域与通行证：作用域 | 名字按 L → E → G → B 的顺序查找，赋值的位置决定作用域。 |
| 6 | 随身行李：闭包 | 内层函数带着的不是值，而是变量（cell）。 |
| 7 | 箱子规格书：类与实例 | 类属性由所有实例共用。实例属性在 __init__ 里设置。 |
| 8 | 机场标准流程：双下划线方法 | 语法调用双下划线方法。len(x) 就是 type(x).__len__(x)。 |
| 9 | 规格书的规格书：继承与 MRO | 属性按 __mro__ 的顺序查找，super() 是 MRO 中的下一个类。 |
| 10 | 安检口：属性访问的秘密 | property 和描述符拦截属性访问。函数也是描述符。 |
| 11 | 无主的箱子：内存与 GC | 引用计数为 0 就清理，循环由 GC 清理。弱引用是虚线标签。 |
| 12 | 储物柜号码：哈希与相等，综合 | a == b 则 hash(a) == hash(b)。键放进去之后不能变。 |
幽灵箱子 B 是用编号 no 来算哈希的箱子。放进储物柜后，重新分类时改写了编号，于是找格子的路也变了。不用哈希、一格一格地扫，B 其实一直都在。
from dataclasses import dataclass
class Bag:
def __init__(self, no):
self.no = no
def __eq__(self, other):
return isinstance(other, Bag) and self.no == other.no
def __hash__(self):
return hash(self.no)
ghost = Bag(3)
lockers = {ghost: "L7"}
ghost.no = 13 # 重新分类时改写了编号
print(ghost in lockers)
# False
print([v for k, v in lockers.items() if k is ghost]) # 不用哈希、逐个扫描，就能找到
# ['L7']
@dataclass(frozen=True)
class BagNo:
no: int
lockers = {BagNo(13): "L7"} # 用不会变的键重新保管
print(lockers[BagNo(13)], BagNo(13) in lockers)
# L7 Trueitems() 逐个扫描不用哈希，所以能找出 B。代价是格子有多少，就要花多少时间。BagNo 带着 frozen=True，放进去之后编号就改不了。编号要变时，就新建一个 BagNo 挪过去。储物柜 L7 打开了。锁了一个月的 B 的行李被取了出来，韩主管开始联系失主。都美兰班长把那沓标签放回抽屉。“还记得第一天说的话吗？箱子只有一个，标签可以有很多个。现在，标签挂在哪里、谁抓着箱子、箱子在哪一格，你都看得见了吧？”小钉指向 13 号传送带。今天，上面什么也没在转。
结案报告 — LOST-012。B 是放进去之后哈希变了的键，所以在储物柜里找不到。用 items() 扫描找到 L7，再用 @dataclass(frozen=True) 的键重新保管。13 号传送带幽灵箱子一案全部结案。
{(1, 2): "A", (2, 1): "B"} 会用掉几个格子？分别比较两个元组的 == 和 hash，先预测再确认。Tag 加上 @dataclass(frozen=True) 重新写一遍，确认 key.n = 13 在哪里被拦下。班长的工作手册
dict、set 用哈希找格子，用 == 确认。a == b 则 hash(a) == hash(b)。
哈希冲突是正常的（hash(-1) == hash(-2)）。字符串哈希每次运行都不同（PYTHONHASHSEED）。
放进去之后键变了，用新值、旧值都找不到。键要用不可变的。
list、dict、set 不能做键。装着列表的元组也一样。
只定义 __eq__，__hash__ 就是 None。用 @dataclass(frozen=True)，或用相同字段写 __hash__。
检查清单：共享的可变对象、默认参数、延迟绑定、类属性、循环引用、变了的键。
箱子只有一个，标签可以有很多个。卡住了，就画出名牌和箱子。
订阅新课时和新课程通知
本课程新增课时或推出后续课程时，我们会发邮件通知你。
问答
关于本课有任何疑问都可以在这里留言。所有语言版本页面的提问会汇集在一起。