HashKiller——如何优雅地卡掉单模数哈希

TLE_Automat · 2024-03-19 22:00:10 · 算法·理论

I. 起因

之前打比赛多次担心写单哈希被卡，但 N 神之前说他高中打过的所有比赛，但凡是字符串的题写 unsigned long long 自然溢出从来没被卡过。我信以为真，认为现在已经没有人素质差到卡别人单模哈希。后来我打了一些 AtCoder 的比赛也写了很多 ull 自然溢出也没事。直到 这场CF N 神 B 题 ull 自然溢出被卡到裂开，以为思路错了，直到赛后才发现是单哈希被卡了。

鉴于以上惨痛的经历，我决定学习一下毒瘤的卡单模数哈希的方法，来警示自己以及与 N 神心态类似的人：不要管出题人卡不卡，反正写双哈希就对了。（警钟撅烂（逃

II. 模 10^9 级别的大质数哈希

其实单模 10^9 级别的大质数哈希非常好卡，我们只需要随机一个长度为 10^5 级别的只包含小写字母的字符串 s，再任取一个大小为 100 左右的子串长度 k，那么 s 的所有长度为 k 的子串中大概率会存在哈希冲突的字符串。

那么概率到底有多大呢，我们可以使用生日悖论的方法来计算。

字符串 s 的长度为 k 的子串总共有 26^{k} 种可能，当 k = 100 时 s 的任意两个长度为 k 的子串几乎不可能相等，所以我们按照长度为 k 的子串均不同来考虑。（其实计算这个本身也是生日悖论）

因为 s 中总共有 10^5 - k + 1 个长度为 k 的子串，设 p 为模数，则第 1 个子串的哈希值不跟之前重复的概率为 \displaystyle{\frac{p}{p}}，第 2 个子串的哈希值不跟之前重复的概率为 \displaystyle{\frac{p - 1}{p}} ，第 n 个子串的哈希值不跟之前重复的概率为 \displaystyle{\frac{p - n + 1}{p}}。所以出现至少两个长度为 k 子串哈希冲突的概率为 \displaystyle{1 - \prod\limits_{i = 1}^{10^{5} - k + 1} \frac{p - i + 1}{p}}。当 p = 10^9 + 7, k = 100 时计算上式的值约为 0.9931958400。

根据以上结论，随便写个代码一随机就能找到两个哈希冲突的字符串，所以单模 10^9 级别的哈希千万不要写。

III. unsigned long long 自然溢出哈希

由于样本空间是 10^{18} 级别，非常大，直接采取生日悖论的方法难以卡掉。

其实我们用上面的方法算一下概率，取 p = 10^{18}，|s| = 10^{6}，k = 100，哈希冲突的概率约为 0.0000004999。（这其实也为两个 10^{9} 级别大质数的双模哈希的正确性提供了证明。）

所以我们要换一套方法来卡，这里一般的方法为构造法。

1. 对于底数为偶数的情况

构造字符串 baaa...（后面有 64 个 a）与 caaa...（后面有 64 个 a）即可卡掉。

这两个字符串的后 64​ 个字符均为 a，所以只需要关心第 1 个位置对哈希值的贡献。

对于第一个字符串，第 1 个位置对哈希值的贡献为 H(\text{"b"}) \times Base^{64} \bmod 2^{64}。

对于第二个字符串，第 1 个位置对哈希值的贡献为 H(\text{"a"}) \times Base^{64} \bmod 2^{64}。

因为 Base 为偶数，所以 Base 中至少含有一个因子 2，所以 2^{64} \mid Base^{64}，所以两个字符串的第 1 个位置对哈希值的贡献均为 0，所以两字符串哈希冲突。

2. 对于底数为奇数的情况

考虑进行如下构造：

• 定义 S_1 = \text{"a"}
• 令 \text{len}(S_i) 表示字符串 S_i 的长度
• 令 \text{not}(T) 为将字符串 T 中字符 \text{"a"} 变为字符 \text{"b"}，字符 \text{"b"} 变为字符 \text{"a"} 的函数
• S_i = S_{i - 1} + \text{not}(S_{i - 1})

可以推导出 \text{len}(S_i) = 2^{i - 1}，且

令 f_i = H(S_i) - H(\text{not}(S_{i - 1}))，上述两式相减，可得

当 f_i \bmod 2^{64} = 0 时，我们即可构造出两个哈希冲突的字符串。

注意到 Base 为奇数，所以 Base^{2^{i - 1}} - 1 必定为偶数。所以 f_{64} \bmod 2^{64} 必定为 0，但是这要构造出两个长度为 2^{63} 的字符串 S_{64} 和 \text{not}(S_{64})，理论上这两个串是哈希冲突的，但是因为长度太长，现实中显然无法进行读写。

注意到 (Base^{2^{i - 1}} - 1) = (Base^{2^{i - 2}} + 1)(Base^{2^{i-2}} - 1) = (Base^{2^{i - 2}} + 1)(Base^{2^{i - 3}} + 1) \cdots (Base^{2^{1}} + 1)(Base^{2^{1}} - 1)。容易证明，上述的每一项都是偶数，所以 f_i 中至少含有 (i - 1) + (i - 2) + \cdots + 1 = \displaystyle{\frac{(i - 1)i}{2}} 个因子 2。

由上述理论进行计算，f_{12} 中至少含有 66 个因子 2，所以 S_{12} 与 \text{not}(S_{12}) 哈希冲突，长度仅为 2^{11}​。

IV. 小结

至此，不管如何更换模数和进制，常见的单模哈希的所有情况均被上述算法卡掉。

所以一定要写双模！！！一定要写双模！！！一定要写双模！！！双模一定要改模数，不要只改进制！！！