字符串哈希 · C++ 互动课

◎学完你会

把字符串算成整数哈希，O(1) 比较任意子串；
说出单模数的风险，用双模 / 随机化防卡；
写对区间哈希公式（含 pow 预处理与取模）。

1哈希是怎样递推出来的

字符串 "abc"，用 base=131、mod=1e9+7 逐位递推。每个字符对应一个数（a→1, b→2, c→3），公式 hash[i]=hash[i-1]*base+s[i]。点按钮一步步看。

// 区间哈希 get(l,r)=hash[r]-hash[l-1]*pow(base, r-l+1)

i	字符	hash[i] 计算	hash[i]
0	—	hash[0]=0	0
1	a	0*131+1	1
2	b	1*131+2	133
3	c	133*131+3	17426

点「下一步」逐行讲解。

2关键命令

要点	含义
前缀哈希	`hash[i]=hash[i-1]*base+s[i]`（mod 取模）
区间哈希	`get(l,r)=hash[r]-hash[l-1]*pow(base,r-l+1)`
pow 预处理	先算好 `p[k]=base^k`，避免查询时重复算幂
防卡	用双模 / 随机化 base，降低被构造碰撞的概率

最大的坑：① 单模数 + 固定 base 可被构造碰撞卡掉，竞赛里要双模或随机 base。② 忘预处理 pow 区间哈希必错。③ 减法取模可能为负：先 +mod 再 %mod。

?跨学科：哈希是指纹，不是内容

字符串哈希的思想和文件指纹一样——不去逐字节比内容，先各自算一个短整数，指纹相同再怀疑内容相同。Git 的 commit id、软件的安装包校验、病毒的"特征码"，全是"先比指纹、再比细节"。代价是指纹可能撞，所以要选好 base 和模数把碰撞概率压到忽略不计。

✎练一练

字符串哈希用单个固定模数时，最主要的风险是？

单模数 + 固定 base 可被人为构造"哈希相同但内容不同"的串（碰撞攻击），故用双模或随机化 base 降低风险。

双模哈希怎么做？自然溢出（unsigned long long 自动回绕）够安全吗？

双模：用两组 (base1,mod1)、(base2,mod2) 分别算，只有两对都相等才算相等，碰撞概率降到 1/(mod1·mod2)。自然溢出不是安全方案：它本质是固定模 2⁶⁴ 的确定性哈希，可被构造碰撞；最多当"一般数据下的快哈希"用，对抗恶意数据要换随机 base 的双模/大模数。