自然溢出：不是怎么老北卡啊
oyoham
·
2026-08-12 11:46:07
·
算法·理论
本篇文章可以采用初中生也会的方法讲解为什么自然溢出哈希（正文部分几位记为自然溢出）一定会被卡，如何卡自然溢出哈希及其原理。
前置知识点：
::::info[取模与同余]
若 a = qb + r （其中 0\le r<b ），则 a\bmod b=r 。a\bmod c=b\bmod c ，则 a 与 b 同余，记作 a\equiv b \pmod c
::::
::::info[奇数与偶数及其部分性质]
记 O 为奇数，E 为偶数，有：
而两个字符串的哈希冲突可以表示为 F_{\overline{S_1}}(B)\equiv F_{\overline{S_2}}(B)\pmod P 或 F_{\overline{S_1}}(B) - F_{\overline{S_2}}(B)\equiv0\pmod P ，记 A 满足 A_i=\overline{{S_1}}_i-\overline{{S_2}}_i ，则冲突时有 F_{A}(B)\equiv 0\pmod P 。
而要想找到对所有底数都适用的哈希冲突，就相当于要找到 \forall x \in \text{Base},F_{A}(x)\equiv0\pmod P ，这对存在大质因子的模数是十分困难的，而对于自然溢出…
Thue-Morse 序列
长度为 2^n 的 Thue-Morse 序列是满足 \forall 0\le i < 2^n,a_i=(-1)^{\operatorname{popcount}(i)} 。
令 P_n 为长度为 2^n 的 Thue-Morse 序列的普通生成函数，易得 P_{n+1}=P_n(1-x^{2^n}) 。
::::info[P_{n+1}=P_n(1-x^{2^n}) 的推导]
&= \sum_{i=0}^{2^{n}-1}(-1)^{\operatorname{popcount}(i)}x^i+\sum_{i=2^n}^{2^{n+1}-1}(-1)^{\operatorname{popcount}(i)}x^i\\
&= \sum_{i=0}^{2^{n}-1}(-1)^{\operatorname{popcount}(i)}x^i+\sum_{i=2^n}^{2^{n+1}-1}(-1)^{\operatorname{popcount}(i-2^n)}x^{i-2^n}(-1)(x^{2^n})\\
&=\sum_{i=0}^{2^{n}-1}(-1)^{\operatorname{popcount}(i)}x^i(1-x^{2^n})\\
&=P_n(1-x^{2^n})
\\\end{aligned}
::::
又有 P_0=1 ，我们可以推出 P_{n}=\prod_{i=0}^{n-1}(1-x^{2^{i}}) 。
2-adic 估值
记 \operatorname{v2}(x) 表示整数 x 中因子 2 的个数（等价于 __builtin_ctz()）。
::::info[什么是 __builtin_ctz()]
__builtin_ctz(x) 表示 x 二进制下末尾有多少位为 0 。
::::
有 \operatorname{v2}(P_n)=\sum_{i=0}^{n-1}\operatorname{v2}(1-x^{2^i}) 。
声明：因为自然溢出不使用偶数作为底数，所以下面的分析中认为 x 为奇数，即 x\in\{2k+1|k\in\mathbb{Z}\} 。
::::info[什么是 \{2k+1|k\in\mathbb{Z}\} ]
人话：全体奇数构成的集合。
::::
::::info[为什么自然溢出不使用偶数作为底数]
因为如果底数为偶数，那么字符串 64 位以后的字符 x 的贡献是 x\cdot B^{64}=x\cdot\left(\frac{B}{2}\right)^{64}2^{64} ，这个值对 2^{64} 取模后为 0 。这意味着你的 64 位以后的字符都没有对哈希值产生贡献，很容易哈希冲突。64 也可换成 128 或别的数（取决于你用的类型）。
::::
对于第 0 项，v2(1-x)\ge1 。
::::info[为什么 v2(1-x)\ge1 ]
因为上文说了，此处的 x 满足 x\in\{2k+1|k\in\mathbb{Z}\} ，所以 1-x\equiv0\mod2 ，所以我们有 v2(1-x)\ge1 。
::::
对于第 i 项（i\in\mathbb{N^+} ）， \operatorname{v2}(1-x^{2^i}) ，有 LTE 引理在 p=2 的特殊形式：\forall x,y\in\{2k+1|k\in\mathbb{Z}\},n\in\mathbb{N^+},\operatorname{v2}(x^{2^n}-y^{2^n})=\operatorname{v2}(x-y)+\operatorname{v2}(x+y)+n-1 。
::::info[什么是 \mathbb{N^+} ]
全体正整数构成的集合。
::::
::::info[如何证明 LTE 引理在 p=2 的特殊形式]
为简洁，本文仅证明 \forall x,y\in\{2k+1|k\in\mathbb{Z}\},n\in\mathbb{N^+},\operatorname{v2}(x^{2^n}-y^{2^n})=\operatorname{v2}(x-y)+\operatorname{v2}(x+y)+n-1 。\operatorname{v2}(ab)=\operatorname{v2}(a)+\operatorname{v2}(b) 。
:::info[为什么 \operatorname{v2}(ab)=\operatorname{v2}(a)+\operatorname{v2}(b) ]
~注意到这是个完全加性函数。~a=2^p\cdot q,b=2^r\cdot s(q,s\in\{2k+1|k\in\mathbb{Z}\}) ，ab=2^{p+r}\cdot q\cdot s 。
根据定义 \operatorname{v2}(a)=p,\operatorname{v2}(b)=s,\operatorname{v2}(ab)=p+s 。即证。
由平方差公式得：
$\begin{aligned}\operatorname{v2}(x^{2^n}-y^{2^n})&=\operatorname{v2}(x^{2^{n-1}}-y^{2^{n-1}})+\operatorname{v2}(x^{2^{n-1}}+y^{2^{n-1}})
\&=\operatorname{v2}(x^{2^{n-2}}-y^{2^{n-2}})+\operatorname{v2}(x^{2^{n-2}}+y^{2^{n-2}})+\operatorname{v2}(x^{2^{n-1}}+y^{2^{n-1}})
\&\vdots
\&=\operatorname{v2}(x-y)+\operatorname{v2}(x+y)+\sum_{i=1}^{n-1}\operatorname{v2}(x^{2^i}-y^{2^i})\end{aligned}$
对于 $2
:::info[为什么 $\forall x,y\in{2k+1
$\forall x\in{2k+1
$\therefore \forall x\in{2k+1
$\therefore \forall x,y\in{2k+1
\therefore v2(x^{n}+y^{n})=1
:::
因此 \operatorname{v2}(x^{2^n}-y^{2^n})=\operatorname{v2}(x-y)+\operatorname{v2}(x+y)+\sum_{i=1}^{n-1}1=\operatorname{v2}(x-y)+\operatorname{v2}(x+y)+n-1 。
::::
我们可以得到：\operatorname{v2}(1-x^{2^i})=v2(x-1)+v2(x+1)+i-1 。
因为我们有 $\forall x\in{2k+1
::::info[为什么 $\forall x\in{2k+1
对于 $x\in{2k+1
$x\in\{x|x\equiv1\pmod4\}$ 时有 $x-1\equiv 2\pmod4,x+1\equiv 0\pmod4$，所以有 $v2(x-1)=1,v2(x+1)\ge2$，因此得证。
::::
所以 $\operatorname{v2}(1-x^{2^i})\ge i+2$。
对上面进行求和，我们有 $\forall x\in\{2k+1|k\in\mathbb{Z}\},\operatorname{v2}(P_{n}(x))\ge\frac{n^2+3n-2}{2}$。
::::info[为什么 $\operatorname{v2}(P_{n}(x))\ge\frac{n^2+3n-2}{2}$]
$$\begin{aligned}\operatorname{v2}(P_{n}(x))&=\sum_{i=0}^{n-1}\operatorname{v2}(1-x^{2^i})
\\&=1+\sum_{i=1}^{n-1}\operatorname{v2}(1-x^{2^i})
\\&\ge1+\sum_{i=1}^{n-1}i+2
\\&=1+\frac{(n+4)(n-1)}{2}
\\&=\frac{n^2+3n-2}{2}\\\end{aligned}$$
::::
当我们取合适的 $n$ 使得 $v2(P_{n}(x))\ge64$ 时（取 $n=10$），令 $A$ 为长度为 $n$ 的 Thue-Morse 序列，即可有 $F_{A}(x)\equiv 0\pmod {2^{64}}$。
### 实际使用
取长为 $2^n$ 的两个字符串 `aaaaa...` 和 `bbbbb...`，对所有 $i<2^n$ 执行若 $i$ 的二进制下若有奇数个 $1$ 则交换两字符串第 $i$ 位。
$n=3$ 的示例：`abbabaab` 与 `baababba`。
测试代码：
```
#include<bits/stdc++.h>
using namespace std;
pair<string,string> ConstructConflictString(int bits){
assert(bits<=128);
int n=0;
while(n*n+3*n-2>>1<bits)n++;
string a,b;
for(int i=0;i<1<<n;i++){
if(__builtin_parity(i))a+='a',b+='b';
else a+='b',b+='a';
}
return {a,b};
}
unsigned __int128 CalculateHashValue(string s,int Base,int bits){
unsigned __int128 Val=0;
for(char c:s){
Val=Val*Base+c;
}
if(bits!=128){
unsigned __int128 range=-1;
range=~(range<<bits);
Val&=range;
}
return Val;
}
string tos(unsigned __int128 a){
if(a<=9)return string(1,char(a|48));
else return tos(a/10)+char(a%10|48);
}
void Test(int bits,int LEN=50){
pair<string,string>S=ConstructConflictString(bits);
string A=S.first,B=S.second;
cout<<"Constructed length="<<A.length()<<"!\n";
if(A.length()<=LEN){
cout<<"A:"<<A<<"\nB:"<<B<<endl;
}
else {
cout<<"A:"<<A.substr(0,LEN-3)<<"...\nB:"<<B.substr(0,LEN-3)<<"..."<<endl;
}
for(int Base:{31,131,79,13131,555,415411}){
cout<<"testing Base="<<Base<<endl;
unsigned __int128 hA=CalculateHashValue(A,Base,bits);
unsigned __int128 hB=CalculateHashValue(B,Base,bits);
cout<<"A:"<<tos(hA)<<endl;
cout<<"B:"<<tos(hB)<<endl;
puts(hA==hB?"Equal":"Not Equal");
}
}
signed main(){
Test(32);
Test(64);
Test(128);
}
```
### Untitled
自然溢出你怎么死了啊 qwq。