第 36 章 哈希表¶
哈希表把任意键映射到 \(O(1)\) 的存取。Python 的 dict / set 已经把这件事做到极致，
写竞赛题时基本不需要自己实现——但需要知道它什么时候会失灵：
整数键可以被构造数据卡，可变对象不能当键，值域已知时用数组比它快好几倍。
这一章讲的就是这三件事。把字符串压成一个整数、让子串比较降到 \(O(1)\) 的那套多项式哈希， 是另一副面孔，见 字符串哈希。
1 哈希表原理速览¶
哈希表 = 数组 + 哈希函数 + 冲突处理。
| 冲突处理 | 做法 | 代表 |
|---|---|---|
| 链地址法 | 每个桶挂一条链表 | C++ unordered_map、Java HashMap |
| 开放寻址 | 冲突时按某种规则探测下一个空位 | CPython 的 dict/set |
CPython 的 dict 用开放寻址，探测序列是
perturb 初值是完整的哈希值，所以哈希值的高位也参与探测顺序——
这比 C++ 那种「只取低位当桶号」的做法更难被针对性构造数据卡。
| 操作 | 平均 | 最坏 |
|---|---|---|
d[k]、k in d、d[k] = v |
\(O(1)\) | \(O(n)\)（全部冲突） |
del d[k] |
\(O(1)\) | \(O(n)\) |
| 遍历 | \(O(n)\) | \(O(n)\) |
2 Python 的哈希值：哪些安全，哪些危险¶
这是本章最实用的一节。不同类型的 hash() 安全性完全不同。
| 键类型 | hash(x) 的值 |
能否被出题人预测 | 风险 |
|---|---|---|---|
str / bytes |
SipHash，每次运行随机加盐 | ❌ 不能 | ✅ 安全 |
小整数 int |
等于 x 本身 |
✅ 能 | ⚠️ 理论可卡 |
大整数 int |
\(x \bmod (2^{61}-1)\) | ✅ 能 | ⚠️ 理论可卡 |
tuple |
各元素哈希的混合 | 取决于元素 | 视元素而定 |
float |
与等值整数一致 | ✅ 能 | ⚠️ |
>>> hash("abc") # 每次运行 Python 都不一样（PYTHONHASHSEED 随机）
>>> hash(42) # 42，永远
>>> hash(-1) # -2，唯一的特例
>>> hash(2 ** 61 - 1) # 0
字符串键：放心用¶
Python 从 3.3 起对 str/bytes 启用随机加盐的 SipHash，
每次进程启动的种子都不同。出题人无法预先构造出会冲突的字符串。
这是 Python 相对 C++ 的一个真实优势——C++ 选手要自己给 unordered_map
写自定义哈希（加随机数）来防卡，Python 什么都不用做。
整数键：理论上可卡，实践中给个便宜的保险¶
hash(int) 是完全确定的。理论上出题人可以构造一批整数，
让它们在 dict 的探测序列上大量碰撞。虽然 CPython 的 perturb 机制让这件事比
卡 unordered_map 难得多，而且出题人通常只针对 C++ 造数据，
但如果一道题专门以「哈希」命名且整数键规模巨大，加一层混淆是免费的保险：
import random
RND = random.getrandbits(61) # 每次运行都不同，出题人无法预先算出碰撞集合
def mix(x):
"""把整数键打散，防止被构造数据卡。O(1)。"""
x ^= RND # 先加随机盐，后面的搅拌才不可预测
# 下面两轮是 splitmix64 的雪崩步骤：右移让高位影响低位，乘法再把差异散开
x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9
x = (x ^ (x >> 27)) * 0x94D049BB133111EB
return (x ^ (x >> 31)) & ((1 << 64) - 1) # 截回 64 位，否则大整数会越滚越长
d = {}
d[mix(key)] = value # 存取两侧都要过 mix，不能只在一处用
代价：每次操作多两次乘法和三次移位，约慢 30%。 只在真的担心被卡时才加，模板题不必。
别用可变对象当键¶
d[(x, y)] = v # ✅ tuple 可哈希
d[[x, y]] = v # ❌ TypeError: unhashable type: 'list'
d[frozenset(s)] = v # ✅
d[set(s)] = v # ❌
3 什么时候不用 dict，改用数组¶
dict 的 \(O(1)\) 有实实在在的常数：哈希计算 + 探测 + 可能的扩容重排。
值域已知且不大时，用 list 当数组比 dict 快 2–3 倍。
| 场景 | 推荐 |
|---|---|
| 键是 \([0, 10^7]\) 内的整数 | list（cnt = [0] * (V + 1)） |
| 键是 \([0, 10^7]\) 内的整数、只要 0/1 | bytearray 或大整数位图 |
| 键是稀疏整数 / 值域未知 | dict |
| 键是字符串 / 元组 | dict |
| 键是二维坐标 \((x,y)\)，网格不大 | 展平成 x * m + y 用 list |
# ❌ 网格 BFS 用 dict 存 visited，慢 3 倍
vis = {}
vis[(x, y)] = True
# ✅ 展平成一维数组
vis = bytearray(n * m)
vis[x * m + y] = 1
判据：能算出下标就别哈希。哈希是「键无法直接当下标」时的妥协。
4 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI8 | 大整数哈希 | 简单 | 题解 |
| BISHI23 | 小红书推荐系统 | 简单 | 题解 |
| BISHI99 | 我朋友的朋友不是我的朋友 | 中等 | 题解 |
| BM50 | 两数之和 | 简单 | 题解 |
| BM51 | 数组中出现次数超过一半的数字 | 简单 | 题解 |
| BM53 | 缺失的第一个正整数 | 中等 | 题解 |
| BM101 | 设计LFU缓存结构 | 较难 | 题解 |
| LC1 | 两数之和 | 简单 | 题解 |
| LC49 | 字母异位词分组 | 中等 | 题解 |
| LC128 | 最长连续序列 | 中等 | 题解 |
| LC169 | 多数元素 | 简单 | 题解 |
BISHI8 大整数哈希（简单）¶
维护映射 \(f: [0, 2^{64}) \to [0, 2^{64})\)，初始全为 0。 \(n \le 5\times10^6\) 次操作，每次给 \((x, y)\)：先输出 \(f(x)\) 的当前值记为 \(ans_i\)， 再令 \(f(x) \leftarrow y\)。求 \(\sum_{i=1}^n i \times ans_i \pmod{2^{64}}\)。 题面见 原题。
题目名叫「大整数哈希」，本质是「键的值域是 \(2^{64}\)、开不下数组」时怎么做映射。
C++ 要手写哈希表（或给 unordered_map 加自定义哈希防卡），
Python 直接用内置 dict，f(x) 初始为 0 用 dict.get(x, 0) 天然表达。
算法零难度，全部难点在 \(n \le 5\times10^6\) 的工程实现上：
| 问题 | 解法 |
|---|---|
| 输入可达上百 MB | 不能 read().split() 一把梭 |
split() 会一次性生成约 \(10^7\) 个 bytes 对象 |
每个至少 33 字节 → 400MB+ → MLE |
改成每次读 4MB 分块，块内 split 处理完就丢 |
|
| 分块边界会把数字劈成两半 | 把「块尾未闭合的 token」留到下一块 |
| 一对 \((x, y)\) 也可能跨块 | 用 carry 存住落单的那个 |
| 每步都取模会变慢 | 中间和最多约 \(2^{113}\)（Python 大整数才 2 个 limb），最后取一次模 |
import sys
MASK = (1 << 64) - 1 # 与 mod 2^64 等价：过程中全是非负数，按位与即截断
CHUNK = 1 << 22 # 每次读 4MB
def main():
read = sys.stdin.buffer.read
f = {} # f(x) 的当前值；未出现过的键视作 0
get = f.get # 绑成局部名，5e6 次调用省下的属性查找很可观
total = 0 # 中间和最多约 2^113，不取模也只占两个大整数肢
idx = 0 # 已处理的操作数，同时就是题面里从 1 起的下标 i
n = -1 # 还没读到操作总数时为 -1
tail = b"" # 上一块尾部未闭合的半个 token
carry = None # 落单的 x（它的 y 在下一块）
while True:
chunk = read(CHUNK)
if not chunk: # 读到 EOF
break
if tail:
chunk = tail + chunk # 把上一块截断的半个数字接回来，拼成完整 token
toks = chunk.split()
if chunk[-1:].isspace(): # 块尾正好是空白，说明最后一个 token 是完整的
tail = b""
elif toks:
tail = toks.pop() # 最后一个 token 可能被截断
else:
tail = b"" # 整块都是空白，没有 token 可留
if n < 0: # 第一个 token 是操作总数，只读一次
if not toks:
continue
n = int(toks[0])
toks = toks[1:]
if carry is not None:
toks.insert(0, carry) # 上一块留下的孤零零的 x，补回队首重新配对
carry = None
if len(toks) & 1: # 个数为奇数，说明末尾的 x 还没等到它的 y
carry = toks.pop()
rest = (n - idx) * 2 # 还需要的 token 数：每次操作恰好两个
if len(toks) > rest:
del toks[rest:] # 丢掉输入尾部的多余内容，防止多算
for j in range(0, len(toks), 2): # 步长 2：每轮取出一对 (x, y)
x = int(toks[j])
idx += 1 # 先自增，因为题面的 i 从 1 开始
prev = get(x) # 取的是赋值前的旧值，顺序不能与下面的写入颠倒
if prev: # f(x) 未赋值时为 0，贡献为 0，跳过
total += idx * prev
f[x] = int(toks[j + 1])
if idx >= n >= 0: # 操作已读满，剩下的输入不必再解析
break
sys.stdout.write(str(total & MASK) + "\n") # 全程不取模，最后截一次 64 位
main()
五个坑：
- 输出的是赋值前的旧值，累加要放在赋值之前；
- \(i\) 从 1 开始计数，不是从 0；
mod 2^64是无符号截断，Python 里就是& ((1 << 64) - 1)， 过程中全是非负数，不必担心 C 里的有符号溢出 UB；- 旧值为 0（\(x\) 第一次出现）时那一项贡献为 0，可以直接跳过累加；
- 最坏情况
dict要存 \(5\times10^6\) 个大整数键值对，内存本身就很吃紧—— 这才是这题在 Python 下真正的难点（值域大到只能靠哈希表，没有别的招）。
题解见 solutions/nowcoder/BISHI8/sol.py。
本题的哈希安全性讨论：键是 \([0, 2^{64})\) 的整数，
hash(x)是确定的， 理论上可构造冲突。但本题的时限是「其他语言 6 秒」，且出题人的卡常目标显然是 C++ 的unordered_map。如果真的 TLE 且怀疑被卡， 可以对键做本章 §2 的mix()混淆——代价是慢约 30%，本题的时限扛不扛得住要实测。
BISHI23 小红书推荐系统（简单）¶
一行仅由小写字母和空格组成的字符串（长度 \(\le 10^5\)）， 输出所有出现次数不少于 3 次的单词，按频次从高到低、同频按字典序升序。 题面见 原题。
哈希计数 + 多关键字排序的最小样例：
import sys
from collections import Counter
cnt = Counter(sys.stdin.buffer.read().split()) # split() 顺带吃掉多余空格和换行
# 排序键取 (-次数, 单词)：次数取负实现降序，单词保持升序，一次给全比两趟排序更稳
res = sorted(((-c, w) for w, c in cnt.items() if c >= 3)) # 题面是「不少于」，故用 >= 3
# bytes 逐字节无符号比较，对纯小写字母就是字典序；只在输出时 decode 一次
sys.stdout.write("".join(w.decode() + "\n" for _, w in res))
复杂度 \(O(L + k \log k)\)，\(L\) 是总长度，\(k\) 是不同单词数。
三个坑：
- 输入是一整行含空格的字符串，但既然只需要按空格切词，
直接
read().split()就够了（顺带吃掉多余空格和换行）； - 排序键是
(-次数, 单词)——先按频次降序，同频按字典序升序。 一次给全 key 比「先按字典序排再按次数稳定排」更清晰不易错； - 判定是「不少于 3 次」即
>= 3，不是> 3。
为什么直接对
bytes排序就是字典序？bytes的比较是逐字节的无符号比较，对纯小写字母来说和字典序完全一致。 省掉 \(k\) 次decode()，只在输出时解一次。
题解见 solutions/nowcoder/BISHI23/sol.py。
面试题单里的四道哈希题¶
这四道题是 §3 那条判据「能算出下标就别哈希」的正反两面。
该用哈希的： 两数之和（同一道题在另一处题库里编号 LC 1. 两数之和）
一边扫一边把「已见过的值 → 下标」记进 dict，
每到一个 \(a_i\) 就查 target - a_i 在不在表里，\(O(n)\) 一趟。
先排序再用相向双指针也能做到 \(O(n\log n)\)，但题目要返回原下标，
排序后还得带着下标走，代码反而更长。
设计LFU缓存结构比 LRU 多一维：既要按访问频次淘汰，同频之间还要按时间淘汰。 标准结构是两张哈希表——「键 → 节点」与「频次 → 该频次的节点链表」—— 外加一个记录当前最小频次的整数。淘汰时直接取最小频次那条链的表尾， 所有操作 \(O(1)\)。链表那一半的细节见 链表。
不该用哈希的： 缺失的第一个正整数要求 \(O(n)\) 时间、\(O(1)\) 额外空间，
哈希表当场出局。正解是把数组自己当哈希表：
把值 \(v \in [1, n]\) 换到下标 \(v-1\) 上去，再扫一遍找第一个 a[i] != i + 1 的位置。
交换循环要写成 while 而不是 if——换进来的新值可能仍然不在自己的位置上。
它正是 §3 那句「哈希是键无法直接当下标时的妥协」的反例：这题的键就是下标。
数组中出现次数超过一半的数字介于两者之间：
Counter 一行能过，但摩尔投票法只要 \(O(1)\) 空间——
维护一个候选值与一个计数，相同则加一、不同则减一、减到零就换候选。
它的正确性依赖题目保证「众数出现次数严格超过一半」，
这个前提一旦松动（比如改成「超过 \(n/3\)」）就要改成维护两个候选。
另一处题库里的三道哈希题¶
LC 49. 字母异位词分组：键怎么设计，题就怎么解。
互为异位词的两个串排序后结果相同，
所以拿 ''.join(sorted(s)) 当键、值取一个列表即可，\(n\) 个串总长为 \(L\) 时 \(O(L \log L)\)。
只含小写字母时可以把键换成 26 个字母的计数元组，
省掉那个对数因子降到 \(O(L)\)；元组可哈希，列表不可哈希，这里换不得。
LC 128. 最长连续序列：\(O(n)\) 的关键是「只从段首起算」。
先把所有数放进集合，再遍历：只有当 x - 1 不在集合里时才从 x 往上数。
这一条判断让每个连续段只被走一次，总步数不超过 \(n\)，整体 \(O(n)\)。
去掉它就退化成 \(O(n^2)\)——段里每个元素都会把自己所在的段重数一遍。
排序解法是 \(O(n \log n)\)，题面卡 \(O(n)\) 时不达标。
LC 169. 多数元素：三条路，代价各不相同。 哈希计数最直白，\(O(n)\) 时间、\(O(n)\) 空间；排序后取下标 \(n/2\) 的元素是 \(O(n \log n)\)、\(O(1)\) 空间； 对消计数（记一个候选与一个票数，相同则加一、不同则减一，减到 \(0\) 就换候选） 同时做到 \(O(n)\) 时间与 \(O(1)\) 空间。 它成立的前提是「众数出现次数严格超过 \(n/2\)」—— 每次对消都消掉一个众数与一个非众数，而众数比其余所有数加起来还多，最后剩下的必是它。 题面若把条件放宽成「出现次数最多」，这个前提就没了，只能退回计数。
5 本章速查¶
| 要点 | 结论 |
|---|---|
str/bytes 的哈希 |
随机加盐 SipHash，不可预测，绝对安全 |
int 的哈希 |
hash(x) == x（小整数）、\(x \bmod (2^{61}-1)\)（大整数），确定 |
CPython 的 dict |
开放寻址 + perturb，比 unordered_map 难卡 |
| 担心被卡整数键 | 加一层 mix() 混淆，代价约 30% |
| 能算下标就别哈希 | 值域小时 list 比 dict 快 2–3 倍 |
| 网格坐标 | 展平成 x * m + y，别用 dict[(x,y)] |
字符串哈希的模数、base、双模、冲突概率等速查条目在 字符串哈希 章末。