第 36 章　哈希与字符串哈希¶

配套例题：BISHI7 字符串哈希、BISHI8 大整数哈希、BISHI23 小红书推荐系统（题解均已通过官方样例）前置：07-字典、08-集合、04-字符串

哈希在竞赛里有两副面孔：

哈希表——把任意键映射到 \(O(1)\) 的存取。Python 的 dict/set 已经做到极致，基本不需要你操心；
字符串哈希——把一个字符串压缩成一个整数，让 \(O(n)\) 的比较降到 \(O(1)\)。这个必须自己写。

本章先讲清楚第一副面孔在 Python 下有什么特殊之处，再给第二副面孔的完整模板。

36.1　哈希表原理速览¶

哈希表 = 数组 + 哈希函数 + 冲突处理。

\[\text{key} \xrightarrow{\ h(\cdot)\ } \text{数组下标} \longrightarrow \text{存储位置}\]

冲突处理	做法	代表
链地址法	每个桶挂一条链表	C++ `unordered_map`、Java `HashMap`
开放寻址	冲突时按某种规则探测下一个空位	CPython 的 `dict`/`set`

CPython 的 dict 用开放寻址，探测序列是

j = (5 * j + 1 + perturb) % table_size;  perturb >>= 5

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)\)

36.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          # ❌

36.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

判据：能算出下标就别哈希。哈希是「键无法直接当下标」时的妥协。

36.4　字符串哈希：原理¶

目标：把长度 \(n\) 的字符串预处理成数组，之后任意子串的比较都是 \(O(1)\)。

多项式哈希：把字符串看成 \(base\) 进制的数，对大素数 \(M\) 取模：

\[H(s) = \left(\sum_{i=0}^{n-1} s_i \cdot base^{\,n-1-i}\right) \bmod M\]

前缀哈希 \(h_i = H(s_0 \dots s_{i-1})\) 满足递推

\[h_0 = 0, \qquad h_{i+1} = (h_i \cdot base + s_i) \bmod M\]

于是子串 \(s[l..r)\)（左闭右开）的哈希是

\[H(s[l..r)) = \left(h_r - h_l \cdot base^{\,r-l}\right) \bmod M\]

这个式子和「\(10\) 进制下从 \(123456\) 里取出 \(345\) 要减去 \(12 \times 10^3\)」是同一回事。

参数怎么选¶

参数	建议	理由
\(base\)	随机取 \([131, 10^9]\) 内的素数	固定 base 会被针对性卡
\(M\)	\(2^{61}-1\)（梅森素数）或 \(10^9+7\)	模数越大冲突概率越低
单模 vs 双模	\(M = 2^{61}-1\) 时单模足够；\(M \approx 10^9\) 时必须双模	见下面的生日悖论分析
自然溢出（\(\bmod 2^{64}\)）	❌ 不要用	有经典的 Thue–Morse 反例可以必然卡掉

冲突概率（生日悖论）：比较 \(q\) 个串两两之间是否相等，出现假阳性的概率约 \(\dfrac{q^2}{2M}\)。

\(M\)	\(q = 10^5\)	\(q = 10^6\)
\(10^9+7\)	约 \(0.5\%\)	约 \(40\%\) ← 危险
\((10^9+7)^2\)（双模）	\(\approx 10^{-9}\)	\(\approx 10^{-7}\)
\(2^{61}-1\)	\(\approx 2\times10^{-9}\)	\(\approx 2\times10^{-7}\)

Python 的优势：模数取 \(2^{61}-1\) 时，中间值 \(h \cdot base\) 最大约 \(2^{91}\)， C++ 需要 __int128 或手写快速乘，Python 原生大整数直接算就行。所以在 Python 里单模 \(2^{61}-1\) 是最优选择：只算一遍，还比双 \(10^9\) 更安全。

36.5　模板：字符串哈希类¶

import random


class StringHash:
    """多项式前缀哈希，支持 O(1) 取任意子串哈希。

    模数取梅森素数 2^61 - 1：
      - 冲突概率约 q^2 / 2^62，10^6 次比较也只有 1e-7 量级；
      - Python 原生大整数直接算 h * base，不需要 C++ 的 __int128。
    base 随机化，防止被针对性构造数据卡。
    兼容 Python 3.9。
    """

    MOD = (1 << 61) - 1                  # 梅森素数；模数是素数，哈希值才在整个区间上均匀

    def __init__(self, s, base=None):
        """s 可以是 str 或 bytes。预处理 O(n)。"""
        if base is None:
            base = random.randrange(131, 1 << 40) | 1    # 或上 1 保证 base 为奇数
        self.base = base                 # 存下来：判回文时反串必须复用同一个 base
        M = self.MOD
        n = len(s)
        if isinstance(s, str):
            s = s.encode()               # 转 bytes 后 s[i] 直接是 0..255 的整数，省掉 ord()
        h = [0] * (n + 1)                # h[i] 是前 i 个字符的哈希；h[0] = 0 代表空串
        p = [1] * (n + 1)                # p[k] = base 的 k 次幂模 M，p[0] = 1
        for i in range(n):
            # 递推等价于在 base 进制数末尾追加一位：整体左移一位，再加上新字符
            h[i + 1] = (h[i] * base + s[i]) % M          # 下标错开一位，故写 h[i+1]
            p[i + 1] = p[i] * base % M   # 幂表顺手递推，查询时就不必再做快速幂
        self.h = h
        self.p = p
        self.n = n

    def get(self, l, r):
        """子串 s[l:r] 的哈希（左闭右开），O(1)。"""
        # h[r] 覆盖前 r 个字符，h[l] 覆盖前 l 个字符。两者位数差 r-l，
        # 所以 h[l] 要乘 base^(r-l) 才能和 h[r] 的高位对齐，相减剩下的正是 s[l:r]。
        # 同 10 进制下从 123456 里取出 345 要减去 12 * 10^3。
        # 差可能为负，Python 的 % 直接返回 [0, MOD) 内的结果，不必再补一个 MOD。
        return (self.h[r] - self.h[l] * self.p[r - l]) % self.MOD

    def equal(self, l1, r1, l2, r2):
        """判断两个子串是否相等，O(1)。"""
        if r1 - l1 != r2 - l2:           # 长度不等直接否掉：哈希只在等长时才有可比性
            return False
        return self.get(l1, r1) == self.get(l2, r2)

用法示例¶

h = StringHash("abcabc")
h.equal(0, 3, 3, 6)         # True  —— "abc" == "abc"
h.get(1, 4)                 # "bca" 的哈希值

双模版本（模数只有 \(10^9\) 级时用）¶

class DoubleHash:
    """双模哈希：把两个模数下的哈希打包成一个元组/整数，
    冲突概率降到 (q^2) / (2 * M1 * M2)。

    Python 里通常不需要 —— 直接用 2^61-1 单模更快也更安全。
    这里给出是为了对照 C++ 的常见写法。
    """

    M1 = 1000000007                   # 两个模数必须互不相同，否则等同于单模
    M2 = 998244353

    def __init__(self, s, b1=131, b2=13331):
        if isinstance(s, str):
            s = s.encode()
        n = len(s)
        h1 = [0] * (n + 1); p1 = [1] * (n + 1)   # 第一套：前缀哈希 + 幂表
        h2 = [0] * (n + 1); p2 = [1] * (n + 1)   # 第二套：模数与 base 都换一组
        M1, M2 = self.M1, self.M2
        for i in range(n):                # 两套放在同一个循环里，字符串只遍历一遍
            h1[i + 1] = (h1[i] * b1 + s[i]) % M1
            p1[i + 1] = p1[i] * b1 % M1
            h2[i + 1] = (h2[i] * b2 + s[i]) % M2
            p2[i + 1] = p2[i] * b2 % M2
        self.h1, self.p1, self.h2, self.p2 = h1, p1, h2, p2

    def get(self, l, r):
        # 与单模同一个式子，只是在两个模数下各算一遍
        a = (self.h1[r] - self.h1[l] * self.p1[r - l]) % self.M1
        b = (self.h2[r] - self.h2[l] * self.p2[r - l]) % self.M2
        return a * self.M2 + b        # 打包成一个整数，方便丢进 set
        # b < M2 保证打包是单射：只有两个模下都相等，打包值才相等

36.6　字符串哈希的典型用法¶

问题	做法	复杂度
判两个子串是否相等	直接比哈希	\(O(1)\)
统计有多少个不同的长度 \(k\) 子串	全部子串哈希扔进 `set`	\(O(n)\)
判回文	正串哈希 == 反串对应位置哈希	\(O(1)\)
求最长公共前缀 (LCP)	二分长度 + 哈希比较	\(O(\log n)\)
字符串匹配	枚举起点比哈希	\(O(n)\)

但要注意： - 字符串匹配有 \(O(n)\) 且无冲突风险的 KMP（71-字符串匹配KMP）； - 判回文有 \(O(n)\) 的 Manacher（72-回文）。

哈希的价值在于「通用」：它能 \(O(1)\) 比较任意两个子串，这是 KMP 和 Manacher 都做不到的。所以哈希是万金油，不是最优解。

判回文的哈希写法¶

def build_palindrome_checker(s):
    """返回一个 O(1) 判定 s[l:r] 是否回文的函数。"""
    fwd = StringHash(s)
    rev = StringHash(s[::-1], base=fwd.base)    # ★ 必须用同一个 base
    n = len(s)

    def is_pal(l, r):
        # 反转把下标 i 送到 n-1-i，所以 s[l:r] 的字符在反串里占 [n-r, n-l)。
        # 回文即「这一段正着读等于反着读」，比较两段哈希即可。
        return fwd.get(l, r) == rev.get(n - r, n - l)

    return is_pal

陷阱：正串和反串必须用同一个 base 和同一个模数，否则完全没有可比性。上面 base=fwd.base 那一行是全部关键。

36.7　例题¶

BISHI7 字符串哈希（简单）¶

给定 \(N \le 10^4\) 个字符串（仅含数字和大小写字母，\(1 \le |s_i| \le 1500\)），求其中不同字符串的个数。题面见 BISHI7 原题（牛客）。

题目名叫「字符串哈希」，C++ 的标准做法是给每个串算多项式哈希再去重，避免 \(O(N^2 |s|)\) 的两两比较。

但在 Python 里这题是一行：

import sys


def main():
    data = sys.stdin.buffer.read().split()   # bytes 本身可哈希，全程不 decode
    n = int(data[0])
    # 只取前 n 个 token：输入尾部若有多余空行或脏数据，切片会把它们挡在外面
    sys.stdout.write(str(len(set(data[1:1 + n]))) + "\n")


main()

因为 bytes 本身就是可哈希的，set 内部就是哈希表，而且哈希计算是 C 实现的 SipHash——比手写多项式哈希又快、又不会被卡冲突（而且冲突后 set 会真的做一次字节比较，结果永远正确，不像多项式哈希有假阳性风险）。

复杂度 \(O(\sum |s_i|)\)，总字符量最多 \(1.5\times10^7\)，比两两比较的 \(O(N^2|s|) = 1.5\times10^{11}\) 快四个数量级。

四个坑：

区分大小写，不能 lower()：样例里 Hello / hello / HELLO 算 3 个不同串；
串里只有数字和字母（无空格），所以可以放心 split() 按空白切 token；
只取前 \(N\) 个 token，防止输入尾部有多余空行 / 脏数据；
直接对 bytes 去重，省掉 \(10^4\) 次 decode()。

题解见 solutions/BISHI7.py。

教学要点：这题揭示了一条通用原则—— 凡是「Python 内置类型已经可哈希」的对象，就不要自己写哈希函数。 手写多项式哈希只在需要「子串」哈希（\(O(1)\) 取任意区间）时才有价值。

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}}\)。题面见 BISHI8 原题（牛客）。

题目名叫「大整数哈希」，本质是「键的值域是 \(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/BISHI8.py。

本题的哈希安全性讨论：键是 \([0, 2^{64})\) 的整数，hash(x) 是确定的，理论上可构造冲突。但本题的时限是「其他语言 6 秒」，且出题人的卡常目标显然是 C++ 的 unordered_map。如果真的 TLE 且怀疑被卡，可以对键做 36.2 的 mix() 混淆——代价是慢约 30%，本题的时限扛不扛得住要实测。

BISHI23 小红书推荐系统（简单）¶

一行仅由小写字母和空格组成的字符串（长度 \(\le 10^5\)），输出所有出现次数不少于 3 次的单词，按频次从高到低、同频按字典序升序。题面见 BISHI23 原题（牛客）。

哈希计数 + 多关键字排序的最小样例：

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/BISHI23.py。

36.8　本章速查¶

要点	结论
`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)]`
字符串去重	直接 `set(bytes)`，不要手写多项式哈希
手写哈希的价值	只在需要 \(O(1)\) 取子串哈希时
模数选择	Python 用 \(2^{61}-1\) 单模（原生大整数，无需 `__int128`）
base	随机化，别写死 131
自然溢出 \(2^{64}\)	❌ 有 Thue–Morse 反例，必被卡
双模	\(M \approx 10^9\) 时必须；用 \(2^{61}-1\) 时不必
正串+反串判回文	必须同 base 同模数
冲突概率	约 \(q^2 / (2M)\)（生日悖论）

子串哈希公式
前缀递推	\(h_{i+1} = (h_i \cdot base + s_i) \bmod M\)
区间取值	\(H(s[l..r)) = (h_r - h_l \cdot base^{\,r-l}) \bmod M\)

第 36 章 哈希与字符串哈希¶

36.1 哈希表原理速览¶

36.2 Python 的哈希值：哪些安全，哪些危险¶