一、字符串哈希（Rolling Hash）简介与基础实现 🚀
在处理字符串比较、查找子串等问题时，字符串哈希 是一项高效而常用的技巧。它能将一个字符串或子串映射为一个整数（哈希值），从而在 O(1) 时间内判断两个子串是否相等。
字符串哈希本质上是将字符串看做一个进制数 用如下的公式计算哈希值：
\(\mathrm{Hash}(s) = \left(\sum_{i=0}^{n-1} (s[i] - 'a') \cdot \text{base}^i \right) \bmod \text{mod}\)
哈希函数的一般形式：
我们给一个字符串比如 "abc"，按照以下方法计算哈希值：
res = 0;
for ( c : s)
{
res = （res *base + c）% mod;
}
在 C++ 中我们用的是 ASCII 值，也就是 'a' == 97，'b' == 98，以此类推。
设base = 131，所以 "abc" 的哈希过程是：
res = 0
res = 0 * 131 + 'a' = 0 + 97 = 97
res =97 * 131 + 'b' = 12715 + 98 = 12813
res = ... * 131 + 'c' = ...
二、字符串哈希经典例题🚀
📚题目描述
如题，给定 \(N\) 个字符串（第 \(i\) 个字符串长度为 \(M_i\)，字符串内包含数字、大小写字母，大小写敏感），请求出 \(N\) 个字符串中共有多少个不同的字符串。
（链接：https://www.luogu.com.cn/problem/solution/P3370）
#include
using namespace std;
typedef unsigned long long ll; // 定义无符号长整型别名，方便后续使用
// 哈希函数参数，b是基数，m是取模数
const ll b=131;
const ll m=1e9+7;
// 字符串哈希函数，计算字符串s的哈希值
ll hash_kk(string s) {
ll res=0; // 结果变量初始化为0
for (char c : s) {
// 每个字符依次乘以基数b后加上当前字符ASCII码，再对m取模，避免溢出
res=(res*b+c)%m;
}
return res; // 返回字符串的哈希值
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n;
cin>>n; // 读取字符串个数
vector
for(ll i=0;i string s; cin>>s; // 读取字符串 kk.push_back(hash_kk(s)); // 计算哈希值并存入kk中 } ll ans=1; // 计数不同字符串的数量，至少有一个 sort(kk.begin(),kk.end()); // 将所有哈希值排序，方便去重 for(ll i=1;i // 遍历排序后的哈希值数组，统计不重复的哈希值数量 if(kk[i]!=kk[i-1]) ans++; } cout< return 0; } ⚠️ 注意事项 该模板使用的是单哈希，虽然简单高效，但存在哈希冲突风险。 在极端测试数据下可能出现错误判定（哈希碰撞），通常加双哈希/多哈希解决。 unsigned long long 自然溢出模拟模\(2^{64}\) 的效果。 三、哈希的风险与哈希冲突 ❗ 哈希冲突是什么？ 单哈希在理论上是把字符串映射到一个大整数范围内，但这个映射并不是完美的“一对一”。不同的字符串可能计算出相同的哈希值，这种现象称为哈希冲突（Hash Collision）。 我们来看一道题 BZOJ Hash Killer I 🔍 题目背景 VFleaKing 采用的是单哈希： 采用 unsigned long long（64位无符号整数）存储哈希值； 不取模，使用自然溢出模拟 模 \(2^{64}\)； 通过哈希排序去重判断子串是否相同。 🚩 风险点 这种写法存在隐患： 虽然64位空间很大，但任意输入都可能有不同子串碰撞哈希值； 一旦发生碰撞，程序会误判不同子串为相同，导致结果错误（WA）； 攻击者或测试者可以构造特殊数据，使程序在实际测试中失败。 🎯 冲突构造思路 利用以下性质： \(Hash(s)=\sum\limits_{i=0}^{l-1}(s[i]−′a′)×base^{l-1-i}\mod 2^{64}\) 若找到两个不同的字符串 s 、t，满足： \({Hash}(s) \equiv {Hash}(t) \pmod{2^{64}}, \quad s \neq t \) \({Hash}(s) -{Hash}(t)=k*{2^{64}}, \quad k \neq 0 \) 我们现在已经理解VFleaKing 的哈希逻辑，接着就是寻找哈希冲突的两个子串，（即不同的子串，哈希值相同） 可以基于数学构造”哈希冲突“ #include using namespace std; typedef unsigned long long ll; const ll base = 2; //计算无符号64位哈希 ll hashk(string s) { ll res=0; for (char c:s) { res=(res*base)+(c-'a'); } return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int l = 64; int m = 3; // 拼接次数 int n = l * m; //构造两个字符串 string s(l,'a'); s[0]='c';//'c'-'a'=2 string t(l,'a'); ll r1=hashk(s); ll r2=hashk(t); //构造哈希冲突 string k; if (r1==r2) { for (int i = 0; i < m; i++) { if (i % 2 == 0) k += s; else k += t; } cout << n << " " << l << "\n"; cout << k<< "\n"; } return 0; } 🔐 四、提高哈希稳定性的做法 — 双哈希 🧮 1. 双哈希（Double Hashing） 双哈希就是对同一字符串使用两个不同的哈希函数 计算哈希值，通常选择不同的base 和（或）不同的模数 mod。 \(hash(s)=\sum\limits_{i=0}^{n-1}s[i]⋅base^{i} \mod mod\) const int b1=131,b2=1331; const int m1=1e9+7,m2=1e9+9; ll hashk(string s,ll b,ll m) { ll res=0; for (char c:s) { res=(res*b)%m; } return res; } 以洛谷 字符串 Hash（数据加强）为例 说明/提示 设第 \(i\) 个字符串长度为 \(m_i\)。 本题评测由三个子任务构成： 第一个子任务（卡大模数 Hash）： 测试点 $n = $ $m_i = $ \(1\sim 6\) \(10^6\) \(6\) 第二个子任务（卡底数为偶数的自然溢出 Hash）： 测试点 \(n=\) \(m_i\approx\) \(m_{max}=\) \(1\sim 6\) \(10^4\) \(1000\) \(1500\) 第三个子任务：（卡奇数底数哈希） 测试点 \(n=\) \(m_i\approx\) \(1\sim 6\) \(2^{11}+1\) \(2^{11}\) 为了避免哈希冲突，我们选用双哈希 #include using namespace std; typedef unsigned long long ull; //定义两个基数和模 const ull b1=131; const ull b2=1331; const ull m1=1e9+7; const ull m2=1e9+9; //计算字符串的哈希值 ull hashf(string s,ull b,ull m) { ull res=0; for (char c:s) { res=(res*b+c)%m; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin>>n; vector int sum=1; while(n--) { string s; cin>>s; //组合双哈希，简单拼接或者异或(冲突概率高) ull ans1=hashf(s,b1,m1); ull ans2=hashf(s,b2,m2); //把两个哈希值拼成一个大数，保证组合后的的唯一 ull ans=ans1*m2+ans2; v.push_back(ans); //寻找无重复的hash值 } sort(v.begin(),v.end()); for (int i=1;i if (v[i]!=v[i-1]) { sum++; } } cout< return 0; } 📝 比较 方案 优点 缺点 单哈希 实现简单，速度快 容易碰撞，安全性较低 双哈希 碰撞概率极低，实战中最常用 稍复杂，计算开销略增 取模策略 保证数值范围，避免溢出 模运算较慢 一般来说，我们使用单哈希就足够了，双哈希的题在竞赛中出现的并不是很多。