为什么字典查得那么快

上一课的实测表里有一行值得再看一眼：n = 10^6 时，在列表里查一个元素在不在要约 1.5 秒；同样查两百次，在集合里只要约 0.000018 秒。第 3 课 lab 的任务 3 里同一件事又出现了一次：把一段两万个元素的查重逻辑从列表换成集合，耗时从约 0.3 秒掉到约 0.002 秒。

两行都是本机实测、非通用值：换一台机器、换一个 Python 版本，秒数会变，「差好几个数量级」这个结论不变。

奇怪的地方在于改动的量级。查重那两版代码里换掉的只有容器——seen = [] 改成 seen = set()，append 改成 add，x in seen 一个字没动；跑出来结果一模一样（第 3 课 lab 打印的 结果一致 True）。同一行 in，凭什么差这么多？

列表为什么慢，上一课已经说清：元素一个挨一个放着，查一个元素在不在，只能从第 0 个开始逐个比较，最坏把整个列表扫完，代价 O(n)——n 放大十倍，它就慢十倍。集合与字典省下的正是这 n 次比较：它们先由键算出一个位置，再到那个位置上去找。这一课要回答的，就是这个位置怎么算出来、这份便宜在什么条件下成立。

桶与哈希函数

字典与集合的内部是一张表，表被划分成若干个桶（bucket），每个桶是存放键值对的一格。要让「键 → 位置」这一步不需要比较，需要一样东西：一个能把任意键变成整数的函数。

哈希函数（hash function）h 是把任意一个键映射成一个整数的函数，算出的这个整数叫键的哈希值。hash 这个词的本义上一课给过一句，这里给出形式化的定义。由哈希值到桶号只需一步：

h = hash(key)     # 第一步：把键算成一个整数
b = h % m         # 第二步：对桶数 m 取模，得到桶号

教材把这种取模定位置的做法叫除法散列（《算法导论》第 11 章散列表）。本课程统一用术语表里的叫法「哈希表」；这本教材的中译把同一结构叫「散列表」，读到对上即可。

查找因此分两步：算出桶号，到那个桶里找。这里出现全课最关键的一个量。设表里有 m 个桶、一共装了 n 个键，那么每个桶平均装着 n/m 个键。一次查找要比较的次数，取决于目标桶里有多少个键：

• 算哈希值与取模是固定几步，与表里装了多少个键无关；
• 桶里的比较次数取决于桶里装了几个键。

于是只要桶数 m 与键数 n 保持同一量级，n/m 就是一个常数，一次查找的代价不随 n 增长——这就是「平均 O(1)」的全部内容。反过来，一个桶数被写死成 16 的表装了 20000 个键，每桶平均 1250 个键，查找就退化成 O(n)。桶数够不够，是这份便宜的第一个条件；「亲手实现一张哈希表」一节会把这两档的差别量出来。

撞到同一个桶怎么办

桶数终归有限，而键的种类没有上限。两个不同的键被哈希函数算到同一个存储位置，这件事叫哈希冲突（术语表口径）。冲突不可能靠调哈希函数消除，只能处理。教材给出的两条主流思路是：

两种思路的代价指向同一个量：要找的那个键所在的位置上，堆着多少个键。冲突少的时候，桶里平均只有一个键，查找就是「算一次哈希加比一两次」，平均 O(1)；若有一批键全都算到同一个桶，链的长度等于键数，查找要顺着整条链比过去，O(n)。这就是这一课反复出现的那句话：平均 O(1)，最坏 O(n)。

Python 的 dict 用的是哪一种？官方文档规定的是行为——按键存取值、键必须可哈希、取不存在的键报 KeyError；内部把键值对放在哪里、冲突时怎么处理，文档留给具体实现去定，本课也不把它当作结论。下面亲手实现的那张表用的是拉链法，图上画的也是拉链法，只因为它最容易画出来、也最容易写对。

那句「最坏 O(n)」有出处。Python 官方 wiki（已归档冻结）把 dict 的 k in d 与取值都标成平均 O(1)、均摊最坏 O(n)，并写明「平均」的前提是哈希函数足够健壮、冲突不常见。该页已停止维护，只作历史参考，当前口径以官方文档为准；它标出的两档差别与本课的推导一致。术语表「哈希冲突」条的用词也是这一套：冲突的键要顺着往下逐个比较才能区分，冲突越多越慢，这正是最坏情况的来源。

第 2 课定过一条口径：竞赛里看最坏情况，因为输入可以在数据范围内任意给定。哈希表的最坏情况要真的出现，需要一大批键撞进同一个桶；Python 内建类型（整数、字符串、元组）的哈希值分布得很开，正常数据下不会走到那一步，所以写题时按平均 O(1) 安排是可靠的。要留意的是写法上的习惯：说「字典查找平均 O(1)」，不说「字典查找永远是 O(1)」。

还有一件与桶数有关的事。键越装越多，桶数不变的话每桶平均装的键就越来越多，表必须加桶，并把已有的键重新算一遍位置放进去，这一步叫扩容（rehash）。它的代价是 O(n)，与第 3 课列表 append 时搬家是同一种偶发开销，均摊到每一次插入上仍是 O(1)。归档 wiki 还留了一条备注：这种情况下表的大小按历史上达到过的最大规模算——从表里删掉大部分键，它也不会立刻缩小。

亲手实现一张哈希表

把上面的模型写成一张能跑的表，机制就落到了具体的代码上。下面这张表按拉链法实现：桶用列表表示，桶里挂着若干 [键, 值] 对。

def make_table(n_buckets):
    return [[] for _ in range(n_buckets)]

def bucket_of(key, n_buckets, bad):
    if bad:
        return 0
    return hash(key) % n_buckets

def put(table, key, value, bad=False):
    b = bucket_of(key, len(table), bad)
    for pair in table[b]:           # 拉链法：顺着这个桶往后逐个比
        if pair[0] == key:          # 键已经在表里，改它的值
            pair[1] = value
            return
    table[b].append([key, value])   # 键不在表里，挂到链尾

def get(table, key, bad=False):
    b = bucket_of(key, len(table), bad)
    for pair in table[b]:
        if pair[0] == key:
            return pair[1]
    return None

bad 是一个开关，用来把哈希函数换成坏版本：一律返回 0，也就是所有键都算到第 0 号桶。有了它，就能把「桶数够不够」与「哈希函数好不好」这两件事分开量。这段代码只用到学过的写法：函数与默认参数出自第 4 课，列表推导式与 for _ in range(...) 出自第 5 课。

import time

keys = [str(i) for i in range(20000)]

def measure(n_keys, n_buckets, bad):
    ks = keys[:n_keys]
    table = make_table(n_buckets)
    t0 = time.perf_counter()
    for k in ks:
        put(table, k, k, bad)
    t_build = time.perf_counter() - t0
    t0 = time.perf_counter()
    for k in ks[-200:]:             # 查最后 200 个键，各查一次
        get(table, k, bad)
    t_take = time.perf_counter() - t0
    return t_build, t_take

for n_keys, n_buckets, bad in ((20000, 16, False), (20000, 32768, False),
                              (2000, 32768, True), (2000, 32768, False)):
    t_build, t_take = measure(n_keys, n_buckets, bad)
    print(n_keys, '键', n_buckets, '桶', '坏哈希' if bad else '好哈希',
          f'装入 {t_build:.4f} 秒 查 200 次 {t_take:.6f} 秒')

本机（Python 3.14.7，free-threading 构建）实测四行：

前两行只改了桶数，同一个哈希函数、同一批键：装入快了 50 倍以上，查两百次快了 100 倍以上。后两行只改了哈希函数，同一批键、同样多的桶：装入快了 60 倍以上，查两百次快了 200 倍以上。四行读下来是一条结论——决定一次查找要比较几次的，是目标桶里堆着多少个键；桶数由键数决定（n/m 保持常数），哈希函数决定这些键是不是均匀落进各个桶。两样缺一，O(1) 就不成立。

第 3 行就是最坏 O(n) 的实物：表里有 32768 个桶，键只装了 2000 个，桶数绰绰有余，可它们全在第 0 号桶里排成一队，每查一次要顺着上千个键比过去。这个场面是自己写一个坏哈希函数造出来的，可见最坏情况确实存在，不能因为它不常发生就把它从复杂度分析里划掉。

标准库的 dict 把前面这些事都做在了内部。同一批两万个键，自己这张表与 dict 各跑一遍，作为对照：

两者同一档，dict 快约 3 倍。差的这几倍是常数因子：dict 是用 C 写的内建类型，键值对存得更紧凑。选桶数、扩容、给字符串哈希加随机种子这些事，它也都在内部替你做了。自己写一遍的价值在于看清机制，写题时该用的仍是 dict 与 set。

键必须可哈希

上一节那张表能装下字符串，装不进列表。键要满足一个条件，官方术语表把它定义得很清楚：

可哈希：一个对象在它的一生中哈希值不变（它需要一个 __hash__ 方法，也就是 Python 内部负责算哈希值的那段代码），并且能与其他对象比较是否相等；相等且可哈希的两个对象必须有相同的哈希值。可哈希正是「能当字典的键、能进集合」的条件——术语表对这件事的说明是，这两类结构内部都要用到哈希值。

列表过不了这一关。官方教程在讲字典时写得很直接：键可以是任何不可变类型，字符串和数字总是可以作为键；你不能使用列表作为键，因为列表可使用索引赋值、切片赋值或 append 和 extend 等方法进行原地修改。第 3 课量过的 lst[0] = v、lst.append(x) 就是这些原地修改：内容改得动，「一生不变」就保不住。运行时看到的是一个报错：

d = {}
d[[1, 2]] = 1

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

集合那边是同一件事，只是措辞不同：

print([1, 2] in {1, 2})

TypeError: cannot use 'list' as a set element (unhashable type: 'list')

本机 Python 3.14 把这条错误信息改得更直白了，官方「Python 3.14 有什么新变化」里专门列了这一条改进；旧版本报的是短句 TypeError: unhashable type: 'list'。两代说法指的是同一个错误，看到 unhashable type 就知道是把不可哈希的东西当键用了。

元组可以当键，前提是它里面的元素都可哈希：

print({(1, 2): 'ok'})       # {(1, 2): 'ok'}
print({('a', 1): 'ok'})     # {('a', 1): 'ok'}

元组本身不可变，但它可以装着可变对象，这时照样不行：

d = {(1, [2]): 'x'}

TypeError: cannot use 'tuple' as a dict key (unhashable type: 'list')

注意报错里点的是 'list'：出问题的是元组里面那个列表。要让一组数一起当键（网格题里的行与列、查重时的一对数），把可变的东西换成元组或整数即可。

浮点数当键是第三个坑，而且它不报错，只是悄悄地查不到：

print(0.1 + 0.2)            # 0.30000000000000004
print(0.1 + 0.2 == 0.3)     # False

d = {0.3: '零点三'}
print(d.get(0.1 + 0.2))     # None

0.1 与 0.2 用二进制都写不精确，加起来得到的是 0.30000000000000004。键是否为同一个，由「相等」这一条判定（相等的对象哈希值一定相同，所以先比哈希值、再比相等就够），这两个数不相等，于是各占一个键。反过来看同一件事：{1: 'a', 1.0: 'b'} 在字典里只剩一个键，本机打印是 {1: 'b'}——按数值相等判定，整数 1 与浮点 1.0 是同一个键。可见判据只有「相等」这一条，写法看着一样、数值看着一样，都不算数。

修法有两条：需要精确匹配的数值改用整数当键（金额按分存），或者先截掉误差再当键——round(x, 10) 把 x 保留到小数点后 10 位，上面那个多出来的尾巴正好被截掉。

d = {0.3: '零点三'}
print(d.get(round(0.1 + 0.2, 10)))    # 零点三

字符串哈希值每次都不一样

把 hash('abc') 打印两次运行，会得到两个不同的整数。本机同一条命令跑两遍的输出：

3664524074659801444
-9178664860088180506

同一个进程里连着打印两次，结果相同；换个进程就换一个值。这是有意设计的。官方 sys.hash_info 给出哈希的实现参数，其中 algorithm 是对字符串、字节串与内存视图进行哈希的算法名称，seed_bits 是哈希算法种子密钥的大小；本机这两个值是 algorithm='siphash13'、seed_bits=128。字符串用一个带随机种子的算法算哈希值，解释器每次启动换一个种子，同一个字符串的哈希值跟着变。

这样做防的正是上一节那条最坏情况：哈希值若可以预测，别人就能提前构造一大批撞进同一个桶的键，把每一次查找都拖成 O(n)。加了随机种子，构造出来的键在下一次运行里就换了桶。

由此得到两条写题时的规矩：hash('abc') 的具体数值不要记，更不要写进代码或答案里（下次运行就对不上）；要观察冲突，让程序把桶号打印出来。

words = ['apple', 'banana', 'cherry', 'date', 'fig',
         'grape', 'kiwi', 'lemon', 'mango', 'nut']

seen = {}
for w in words:
    b = hash(w) % 8
    print(w, '->桶', b)
    if b in seen:
        print('   冲突：', seen[b], '与', w, '都落在桶', b)
    else:
        seen[b] = w

某一次运行的前几行：

apple ->桶 1
banana ->桶 5
cherry ->桶 0
date ->桶 3
fig ->桶 1
   冲突： apple 与 fig 都落在桶 1

哪两个词撞在一起，每次运行都可能不同——种子换了，桶号跟着换。可以确定的是冲突一定存在：10 个键放进 8 个桶，按抽屉原理（10 样东西放进 8 个格子，必有一格装着不止一样），一定有桶里堆着两个以上的键。把桶数加到 16、词加到二十几个，仍然会有桶堆着两个键以上；想让冲突彻底消失，只能让桶数远超键数，而键数没有上限。哈希表要做的是把冲突控制得足够少。

统计与查重的写法

机制说完了，回到写题。需要哈希表的地方集中在三类动作上：数每个东西出现了几次、判断一个东西是不是已经出现过、把一个值当索引查回它对应的位置。这三类用字典或集合写都是 O(n)；写成在列表里逐个扫，就是 O(n^2)（第 3 课的口径）。

统计出现次数

def count_items(data):
    cnt = {}
    for x in data:
        cnt[x] = cnt.get(x, 0) + 1
    return cnt

print(count_items(['a', 'b', 'a', 'c', 'a', 'b']))

{'a': 3, 'b': 2, 'c': 1}

cnt[x] = cnt.get(x, 0) + 1 这一行的读法：先问字典「x 现在是几」，没有就当 0；官方教程给的 get 口径是，取不存在的键会报 KeyError，想避开就用 get()，它在键不存在时返回 None 或你指定的默认值。加 1 再写回去。第一次见到 x 写入 1，之后再见到就往上加。计数逻辑在题目里出现得太多，值得抽成一个函数（第 4 课）：调用处只写 count_items(data)，一眼看出在做什么。

标准库里有现成的计数工具，拿来对照：

import collections

c = collections.Counter('abracadabra')
print(c)                  # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
print(c['a'], c['z'])     # 5 0
print(c.most_common(2))   # [('a', 5), ('b', 2)]

官方对 Counter 的定位是「用于计数可哈希对象的字典子类」：元素存成字典的键，它们的计数存成值。它比手写字典多两条便利——查一个没出现过的键返回 0 而不报 KeyError（上面 c['z'] 得 0 就是这个原因），按出现次数从多到少取用 most_common。两种写法结果一样：手写版每一步都看得见，Counter 版少写三行。做题时挑一个顺手，另一个要认得出。

找第一个重复元素

def first_repeat(data):
    seen = set()
    for x in data:
        if x in seen:
            return x
        seen.add(x)
    return None

print(first_repeat([3, 1, 4, 1, 5]))    # 1
print(first_repeat([1, 2, 3]))          # None

这与第 3 课的查重是同一段写法，动作多了一步：一发现重复就返回，后面的元素不用再看。只看「在不在」用集合就够（不需要附带的值），要连同出现位置或次数一起拿出来，就把 seen 换成字典。有一处题意要读准：「第一个」是按扫描顺序算的，题目要从右边数或按别的顺序找，就得换扫描方向。

两数之和

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    return -1, -1

print(two_sum([2, 7, 11, 15], 9))    # (0, 1)
print(two_sum([3, 3], 6))            # (0, 1)
print(two_sum([1, 2], 100))          # (-1, -1)

这一题是「把值当索引查回去」的样板：一路扫过去，每见到一个数 x，先算它要配的那个数 target - x，再问「这个需要的数刚才见过吗」。见过就交出它的下标与当前下标；没见过就把 x 与它的下标存进字典，留给后面的元素用。字典在这里存的是「值 → 下标」，enumerate（第 5 课）一次给出下标与值。

规模上的差别正是这一课的主题：两层循环的写法要比较 \dfrac{n(n-1)}{2} 次，O(n^2)；这一版每个元素只做一次「算需要谁、查一下」，O(n)。n = 10^5 时前者约 5\times10^9 次比较，按第 2 课那把尺子根本跑不完；后者 10^5 次，远在时限之内。省下的就是那 n 次「逐个比」。

还有一处边界写在这一版里：先查后存。[3, 3] 的答案是 (0, 1) 而不是 (0, 0)——查到的是前面存进去的那个下标，当前元素还没入表，配不上自己。

这一课用到的 Python

配套项目「AI 刷题助手」在给候选解法挑容器时，用的也是这一课的三条动作：题目里出现「统计次数」「判断是否出现过」「按值找回下标」，就把候选解里的列表扫描换成字典或集合，复杂度从 O(n^2) 降到 O(n)。这类题在省赛里出现得极密——判重、计数、把值当索引查回去，几乎每套题都有至少一道。

• Python 官方教程 · 数据结构5.4 集合与 5.5 字典：键可以是任何不可变类型、列表不能当键的原因、get() 的用法，本课这两节的口径出自这里
• Python 官方文档 · 内置类型（映射类型 dict）映射类型 dict 的官方定义与各方法：in、按键取值、get、取不存在的键报 KeyError 的口径
• Python 官方文档 · collections.Counter计数工具的官方口径：元素是键、计数是值，查不存在的键返回 0，most_common 的排序规则
• Python 官方文档 · sys.hash_info字符串哈希的算法名与种子密钥位数（本机 algorithm='siphash13'、seed_bits=128）
• Python 3.14 有什么新变化「向 dict 或 set 添加不可哈希类型时的错误信息已改进」这一条，本课引的那句报错就是它
• Python 官方文档 · 术语表（hashable）可哈希的定义：哈希值一生不变、能比较相等、相等的对象哈希值相同
• OI Wiki · 复杂度最坏时间复杂度与平均（期望）时间复杂度的口径，第 2 课与本课都用这一套说法
• TimeComplexity（python.org 官方 wiki）dict/set 各操作的平均与最坏复杂度对照及「平均」的前提；该页已归档冻结，只作历史参考，当前口径以官方文档为准
• 《算法导论（第 3 版）》第 11 章 散列表哈希函数、除法散列、拉链法与开放寻址两种冲突处理思路，本课这一节的模型与顺序照它走
• 《Python 编程：从入门到实践（第 2 版）》第 6 章 字典本地教材：字典的建立、取值与遍历，Python 侧写法可对照它