📖 第 3.7 章
⏱️ 约 50 分钟
🎯 中级
第 3.7 章：哈希技术
📝 前置条件： 了解 STL 容器（第 3.1 章）和字符串基础（第 2.3 章）。本章涵盖哈希原理和竞赛编程的进阶用法。
哈希是竞赛编程中最重要的「工具」之一：它能把复杂的比较问题变成 O(1) 的数值比较。但哈希也是最容易被「hack」的技术——本章既教你如何用好哈希，也教你如何防止被 hack。
3.7.1 unordered_map vs map：内部实现与性能
内部实现对比
| 特性 | map | unordered_map |
|---|---|---|
| 内部结构 | 红黑树（平衡 BST） | 哈希表 |
| 查找时间 | O(log N) | 平均 O(1)，最坏 O(N) |
| 插入时间 | O(log N) | 平均 O(1)，最坏 O(N) |
| 遍历顺序 | 有序（按键升序） | 无序 |
| 内存占用 | O(N)，常数较小 | O(N)，常数较大 |
| 最坏情况 | O(log N)（稳定） | O(N)（哈希碰撞） |
📄 C++ 完整代码
#include <bits/stdc++.h>
using namespace std;
int main() {
// map：有序，O(log N)
map<int, int> m;
m[3] = 30; m[1] = 10; m[2] = 20;
for (auto [k, v] : m) cout << k << ":" << v << " ";
// 输出：1:10 2:20 3:30 ← 有序！
// unordered_map：无序，平均 O(1)
unordered_map<int, int> um;
um[3] = 30; um[1] = 10; um[2] = 20;
// 遍历顺序不确定，但查找非常快
// 性能差异：N=10^6 次操作
// map: ~300ms；unordered_map: ~80ms（大概）
}
怎么选？
- 用
map： 需要有序遍历、需要lower_bound/upper_bound、键范围极端（高哈希碰撞风险） - 用
unordered_map： 只需查找/插入、键是整数或字符串、N 较大（> 10^5）
3.7.2 防 Hack：自定义哈希
问题： unordered_map 的默认整数哈希本质上是 hash(x) = x，攻击者可以构造大量哈希碰撞，使操作退化到 O(N) 从而 TLE。
在 Codeforces 等平台上，这是常见的 hack 技术。
解决方案：splitmix64 哈希
📄 查看代码：解决方案：splitmix64 哈希
// 防 hack 自定义哈希器 — 使用 splitmix64
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
// 用法：
unordered_map<int, int, custom_hash> safe_map;
unordered_set<int, custom_hash> safe_set;
⚠️ 竞赛技巧： 在 Codeforces 上用
unordered_map时，始终加上custom_hash。USACO 测试数据不会故意构造 hack，但这是个好习惯。
3.7.3 字符串哈希（多项式哈希）
字符串哈希将字符串映射为整数，把字符串比较变成数值比较（O(1)）。
核心公式
对字符串 s[0..n-1]，定义哈希值为：
hash(s) = s[0]·B^(n-1) + s[1]·B^(n-2) + ... + s[n-1]·B^0 (mod M)
其中 B 是底数（通常取 131 或 131117），M 是大质数（通常取 10⁹+7 或 10⁹+9）。
前缀哈希 + O(1) 子串哈希
📄 查看代码：前缀哈希 + O(1) 子串哈希
// 字符串哈希：O(N) 预处理，O(1) 子串哈希查询
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BASE = 131;
// 使用 unsigned long long 自然溢出（等价于 mod 2^64）
struct StringHash {
int n;
vector<ull> h, pw;
StringHash(const string& s) : n(s.size()), h(n + 1, 0), pw(n + 1, 1) {
for (int i = 0; i < n; i++) {
h[i + 1] = h[i] * BASE + (s[i] - 'a' + 1); // 1-indexed 前缀哈希
pw[i + 1] = pw[i] * BASE; // BASE^(i+1)
}
}
// 获取子串 s[l..r]（0-indexed）的哈希值
ull get(int l, int r) {
return h[r + 1] - h[l] * pw[r - l + 1]; // ← 关键公式
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s = "abcabc";
StringHash sh(s);
// 比较两个子串是否相等
// s[0..2] = "abc"，s[3..5] = "abc"
cout << (sh.get(0, 2) == sh.get(3, 5) ? "相等" : "不相等") << "\n"; // 相等
// 比较 s[0..1] = "ab" vs s[3..4] = "ab"
cout << (sh.get(0, 1) == sh.get(3, 4) ? "相等" : "不相等") << "\n"; // 相等
}
公式推导：
h[r+1] = s[0]*B^r + s[1]*B^(r-1) + ... + s[r]*B^0
h[l] = s[0]*B^(l-1) + ... + s[l-1]*B^0
h[r+1] - h[l] * B^(r-l+1)
= s[l]*B^(r-l) + s[l+1]*B^(r-l-1) + ... + s[r]*B^0
= hash(s[l..r]) ✓
下图直观展示了前缀哈希数组的构建过程，以及如何用 get(l, r) 公式在 O(1) 内提取任意子串的哈希值：
3.7.4 双重哈希（避免碰撞）
单重哈希（mod M）的碰撞概率约 1/M。对 N 次子串比较，预期碰撞次数约 N²/(2M)。
下图展示了两种经典的碰撞处理方式——链式法（unordered_map 内部使用）和线性探测：
- 若
M = 10⁹+7，N = 10⁶：碰撞概率约10¹²/(2×10⁹) = 500次！不安全。 - 解决方案：双重哈希，同时使用两对不同的 (B, M)，碰撞概率降至
1/(M₁×M₂) ≈ 10⁻¹⁸。
📄 C++ 完整代码
// 双重哈希：同时用两对 (BASE, MOD)，碰撞概率极低
struct DoubleHash {
static const ull B1 = 131, M1 = 1e9 + 7;
static const ull B2 = 137, M2 = 1e9 + 9;
int n;
vector<ull> h1, h2, pw1, pw2;
DoubleHash(const string& s) : n(s.size()),
h1(n+1,0), h2(n+1,0), pw1(n+1,1), pw2(n+1,1) {
for (int i = 0; i < n; i++) {
ull c = s[i] - 'a' + 1;
h1[i+1] = (h1[i] * B1 + c) % M1;
h2[i+1] = (h2[i] * B2 + c) % M2;
pw1[i+1] = pw1[i] * B1 % M1;
pw2[i+1] = pw2[i] * B2 % M2;
}
}
// 返回 pair<ull,ull> 作为子串 s[l..r] 的哈希「指纹」
pair<ull,ull> get(int l, int r) {
ull v1 = (h1[r+1] - h1[l] * pw1[r-l+1] % M1 + M1) % M1;
ull v2 = (h2[r+1] - h2[l] * pw2[r-l+1] % M2 + M2) % M2;
return {v1, v2};
}
};
3.7.5 应用：字符串匹配（Rabin-Karp）
📄 查看代码：3.7.5 应用：字符串匹配（Rabin-Karp）
// Rabin-Karp 字符串匹配：找 T 中所有 P 的出现位置
// 时间：平均 O(N+M)，最坏 O(NM)（实际非常快）
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
vector<int> rabinKarp(const string& T, const string& P) {
int n = T.size(), m = P.size();
if (m > n) return {};
const ull BASE = 131;
ull patHash = 0, textHash = 0, pow_m = 1;
// 计算 BASE^m（自然溢出）
for (int i = 0; i < m - 1; i++) pow_m *= BASE;
// 初始哈希
for (int i = 0; i < m; i++) {
patHash = patHash * BASE + P[i];
textHash = textHash * BASE + T[i];
}
vector<int> result;
for (int i = 0; i + m <= n; i++) {
if (textHash == patHash) {
// 哈希匹配时验证（避免碰撞导致的误判）
if (T.substr(i, m) == P) result.push_back(i);
}
if (i + m < n) {
// 滚动哈希：去掉最左边的字符，加入最右边的字符
textHash = textHash - T[i] * pow_m; // 移除最左
textHash = textHash * BASE + T[i + m]; // 加入最右
}
}
return result;
}
3.7.6 应用：最长公共子串
题目： 给定字符串 S 和 T，找最长公共子串的长度。
做法： 二分答案（最长公共子串的长度 L），然后用哈希集合检查是否有长度为 L 的子串同时出现在两个字符串中。
📄 C++ 完整代码
// 最长公共子串：O(N log N) — 二分查找 + 哈希
int longestCommonSubstring(const string& S, const string& T) {
StringHash hs(S), ht(T);
int ns = S.size(), nt = T.size();
auto check = [&](int len) -> bool {
unordered_set<ull> setS;
for (int i = 0; i + len <= ns; i++)
setS.insert(hs.get(i, i + len - 1));
for (int j = 0; j + len <= nt; j++)
if (setS.count(ht.get(j, j + len - 1)))
return true;
return false;
};
int lo = 0, hi = min(ns, nt);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (check(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
⚠️ 常见错误
-
模数选择不当： 不要用
10⁹+7以外的数；尤其避免非质数模数（碰撞率高）。推荐：10⁹+7和10⁹+9作为双重哈希对。 -
unordered_map被 hack： 在 Codeforces 等平台上，默认哈希可被攻击。始终使用custom_hash。 -
子串哈希相减下溢：
h[r+1] - h[l] * pw[r-l+1]在有符号整数下可能为负。使用unsigned long long自然溢出，或用(... % M + M) % M确保非负。 -
底数与字符集不匹配： 对仅含小写字母（26 种）的情况，BASE 必须 > 26（通常用 31 或 131）。对全 ASCII 字符（128 种），BASE 必须 > 128（用 131 或 137）。
-
哈希碰撞导致 WA： 即使双重哈希，理论上仍可能碰撞。不确定时，哈希匹配后加直接字符串比较。
本章总结
📌 核心对比表
| 工具 | 时间复杂度 | 使用场景 |
|---|---|---|
map<K,V> | O(log N) | 需要有序性，需要范围查询 |
unordered_map<K,V> | O(1) 均摊 | 只需查找/插入，不需要键的顺序 |
| 字符串哈希（单重） | O(N) 预处理，O(1) 查询 | 子串比较、模式匹配 |
| 字符串哈希（双重） | O(N) 预处理，O(1) 查询 | 高精度场景，避免碰撞 |
❓ 常见问题
Q1：ull 自然溢出双重哈希和手动 mod 哈希哪个更好？
A：
ull自然溢出（等价于 mod 2⁶⁴）代码更简单，2⁶⁴ 足够大以至于单重哈希碰撞概率已经极低（约 10⁻¹⁸）。但精心构造的数据可以故意触发碰撞——此时双重哈希更安全。两种方式在竞赛中都有效；ull更常见。
Q2：字符串哈希能做什么 KMP 做不到的事？
A：字符串哈希擅长多字符串比较（如最长公共子串、回文子串），而 KMP 只擅长单模式匹配。哈希 + 二分查找可以用 O(N log N) 解决许多需要更复杂 KMP 实现的字符串问题。
Q3：底数该用 31 还是 131？
A：只有小写字母时用 31（小于 37 的质数，避免哈希空间太小）。混合大小写或含数字时用 131（大于 128 的质数，覆盖完整 ASCII）。关键是：BASE 必须大于字符集大小，最好是质数。
练习题
题目 3.7.1 — 哈希两数之和 🟢 简单 给定数组 A，判断是否存在两个不同元素之和等于目标值 X。
提示
对每个 A[i]，检查 (X - A[i]) 是否已经在哈希集合中。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, X; cin >> n >> X;
vector<int> a(n); for (int& x : a) cin >> x;
unordered_set<int> seen;
for (int x : a) {
if (seen.count(X - x)) { cout << "YES\n"; return 0; }
seen.insert(x);
}
cout << "NO\n";
}
复杂度： O(N) 均摊。
题目 3.7.2 — 子串查找 🟢 简单 给定文本 T 和模式 P，打印 P 在 T 中所有出现位置的起始下标。
提示
滚动哈希：用前缀哈希在 O(1) 计算 T 的每个 |P| 长度窗口的哈希值。✅ 完整题解（滚动哈希）
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BASE = 131, MOD = (1ULL<<61)-1;
int main() {
string T, P; cin >> T >> P;
int n = T.size(), m = P.size();
vector<ull> h(n+1,0), pw(n+1,1);
for(int i=0;i<n;i++) { h[i+1]=(h[i]*BASE+T[i])%MOD; pw[i+1]=pw[i]*BASE%MOD; }
ull hp=0; for(char c:P) hp=(hp*BASE+c)%MOD;
for(int i=0;i+m<=n;i++){
ull wh=(h[i+m]-h[i]*pw[m]%MOD+MOD*2)%MOD;
if(wh==hp) cout<<i<<"\n";
}
}
复杂度： O(N + M)。
题目 3.7.3 — 最长回文子串 🟡 中等 找最长回文子串的长度。
提示
对长度二分查找。s[l..r] 是回文串当且仅当 hash(s[l..r]) == hash(rev(s)[n-1-r..n-1-l])。✅ 完整题解（哈希 + 二分查找）
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BASE=131;
struct Hasher {
vector<ull> h,pw;
Hasher(const string&s){
int n=s.size(); h.resize(n+1,0); pw.resize(n+1,1);
for(int i=0;i<n;i++){h[i+1]=h[i]*BASE+s[i];pw[i+1]=pw[i]*BASE;}
}
ull get(int l,int r){return h[r+1]-h[l]*pw[r-l+1];}
};
int main(){
string s; cin>>s;
string r(s.rbegin(),s.rend());
Hasher hs(s),hr(r);
int n=s.size(), ans=1;
auto check=[&](int len)->bool{
for(int i=0;i+len<=n;i++){
int j=i+len-1;
if(hs.get(i,j)==hr.get(n-1-j,n-1-i)) return true;
}
return false;
};
int lo=1,hi=n;
while(lo<=hi){int mid=(lo+hi)/2;if(check(mid)){ans=mid;lo=mid+1;}else hi=mid-1;}
cout<<ans<<"\n";
}
复杂度： O(N log N)。
题目 3.7.4 — 统计不同子串 🟡 中等 给定长度为 N 的字符串 S（N ≤ 5000），统计不同子串的个数。
提示
将所有 O(N²) 个子串的哈希值插入 unordered_set，用双重哈希避免碰撞。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int main(){
string s; cin>>s;
int n=s.size();
const ull B1=131,B2=137,M1=1e9+7,M2=1e9+9;
unordered_set<ull> seen;
for(int i=0;i<n;i++){
ull h1=0,h2=0;
for(int j=i;j<n;j++){
h1=(h1*B1+s[j])%M1;
h2=(h2*B2+s[j])%M2;
seen.insert(h1*M2+h2); // 合并两个哈希值
}
}
cout<<seen.size()<<"\n";
}
复杂度： O(N²) 时间和空间（适用于 N ≤ 5000）。
题目 3.7.5 — 字符串周期 🔴 困难 找字符串 S 的最小周期（最小的 k 整除 n，使得 S = S[0..k-1] 的重复）。
提示
对 n 的每个因数 k，验证 s[0..k-1] 重复后是否等于 s，用哈希比较，每次检查 O(n/k)。✅ 完整题解
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BASE=131,MOD=1e9+7;
int main(){
string s; cin>>s;
int n=s.size();
vector<ull> h(n+1,0),pw(n+1,1);
for(int i=0;i<n;i++){h[i+1]=(h[i]*BASE+s[i])%MOD;pw[i+1]=pw[i]*BASE%MOD;}
auto getHash=[&](int l,int r){return (h[r+1]-h[l]*pw[r-l+1]%MOD+MOD*2)%MOD;};
vector<int> divs;
for(int i=1;i*i<=n;i++) if(n%i==0){divs.push_back(i);if(i!=n/i)divs.push_back(n/i);}
sort(divs.begin(),divs.end());
for(int k:divs){
bool ok=true;
for(int i=0;i+k<=n&&ok;i+=k)
if(getHash(i,i+k-1)!=getHash(0,k-1)) ok=false;
if(ok){cout<<k<<"\n";return 0;}
}
}
复杂度： O(d(N) × N) ≈ 典型输入 O(N log N)。