引入（摘自 OI-wiki）
哈希表又称散列表，一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。
简单来说，对于任意类型（字符串，结构体也包含在内）的键值，向其唯一映射一个整型值，这样我们在不方便比较键值的情况下，能方便的通过对应的 value 比较。
注意 hash 只能比较是否相同而不能比大小。
哈希冲突
哈希算法的好坏取决于哈希函数 $f(S)$ 的设定，其中哈希函数的定义为：给定一个元素 $S$，通过哈希函数 $f(S)$ 得到一个整型数值，即建立 $S$ 到 $f(S)$ 的映射。
那么什么样的哈希函数是优秀的？即我们尽量保证 $S$ 和 $f(S)$ 是一一映射的，即不希望出现 $S_1\neq S_2,f(S_1)=f(S_2)$，如果出现这种情况，我们称之为哈希冲突。
开散列法
对于开散列法，我们在哈希表上的每个位置开一个链表，那么每次我们将 $S$ 存在 $f(S)$ 对应的 vector 中。
如果在一个大小为 $M$ 的哈希表向其中均匀的放入 $n$ 个元素，那么插入/查询的复杂度为 $\mathcal{O}(\dfrac{n}{M})$。
通过合理的设定哈希函数，可使复杂度达到期望 $\mathcal{O}(\dfrac{n}{M})$。
当 $M$ 略大于 $n$ 时，我们可以认定哈希算法的复杂度为 $\mathcal{O}(1)$。
闭散列法
这种写法不常用，只作介绍。
闭散列方法把所有记录直接存储在散列表中，如果发生冲突则根据某种方式继续进行探查。此时哈希表上的一个位置只存储一个元素。
常见的探查法如线性探查，如果在哈希表的 $p$ 位置产生冲突，就继续探查 $p+1,p+2,\cdots$ 直到找到空位，将其填入。
插入/查询的复杂度在探查策略设计的合理时也是期望 $\mathcal{O}(\dfrac{n}{M})$。
$\texttt{unordered map - Hash Table}$
$\texttt{c++11}$ 中提供了一个哈希表 STL，$\texttt{unordered map}$，引入头文件 #include <unordered_map> 后即能使用，方法同 $\texttt{map}$。
但此哈希表在某些情况下的表现并不优秀，甚至比复杂度 $\mathcal{O}(\log n)$ 的 $\texttt{map}$ 还慢，于是我们应该自己手写一个真正可用的 $\texttt{Hash Table}$！
一个合格的哈希表，我们希望实现如下操作：
（前置）设计哈希函数
f()，复杂度 $\mathcal{O}(1)$；插入操作
Insert()，复杂度 $\mathcal{O}(1)$；查询操作
Query()，复杂度 $\mathcal{O}(1)$；修改操作
Modify()，复杂度 $\mathcal{O}(1)$；清空操作
Clear()，复杂度 $\mathcal{O}(size)$。
代码
据此我们给出如下代码。
typedef unsigned long long ull;
const int Mod = 998244353;
const int M = , SIZE = ; // 自行设定 M 和 SIZE 的大小
struct HashTable {
struct Node { // 邻接表
ull nxt, val, key;
} data[SIZE];
int head[M], size;
int f(ull key) { // 哈希函数 O(1)
return key * key * key % M;
}
void clear() { // 清空函数 O(size)
for(int i = 1;i <= size;i++) {
head[f(data[i].key)] = 0;
data[i].nxt = data[i].val = data[i].key = 0;
}
size = 0;
}
int que(ull key) { // 查询函数 O(1)
for(int i = head[f(key)];i;i = data[i].nxt) {
if(data[i].key == key) {
return data[i].val;
}
}
return -1;
}
void modify(ull key, int val) { // 修改函数 O(1)
for(int i = head[f(key)];i;i = data[i].nxt) {
if(data[i].key == key) {
data[i].val = val;
return;
}
}
}
void ins(ull key, int val) { // 插入函数 O(1)
data[++size].nxt = head[f(key)], data[size].val = val, data[size].key = key;
head[f(key)] = size;
}
};
其中哈希函数可根据具体题目作微调，哈希表的大小为 $SIZE$，其中 $M$ 是一个略小于 $SIZE$ 的质数，是为了在哈希函数中使用。
树哈希
树哈希通过对树的结构进行哈希，来判断树之间是否同构。
一种可行的树哈希方法：子树按 hash 值排序后，以括号序字符串拼接。
注意这种做法也可能产生冲突，但冲突在于对括号序字符串的哈希，而不同的树一定对应一个不同的括号串。
习题
记几道比较典型的 Hash 题目。
红蔷薇白玫瑰（rose）
借用了学长的题目，可能会视情况保护隐私在文章中撤掉此题。
给⼀个 01-trie 和⼀个长为 $m$ 的 01 串 $S$，对于每个节点，如果按照 $S$ 能走到⼀个节点则输出该节点，否则输出 $0$。
解释一下题意：给定一棵有限节点的 01-trie，还有一个给定的长度为 $m$ 的 01 字符串，对于每一个结点 $u$，我们从 $u$ 开始，按照 01 字符串，如果是 0 往 0 儿子走，1 就往 1 儿子走，最后可能会走出 trie 或未走出 trie，如果未走出 trie，输出这个点最终到达的节点。
考场上确实被诈骗到 20min，开始的思路自然是想办法直接维护每个点到底能往下走到哪个点上，但很显然，多方向道路很难快速维护出全部答案。
那么接下来就是考虑什么情况下能走出一条唯一的路径，换句话说，一个节点的儿子可能不止一个，但每个节点的父亲当且仅当有 $1$ 个。那么我们转化成如下问题：对于节点 $u$，向上跳 $m$ 步走到 $fa$，问 $fa\rightarrow u$ 上的路径构成的 01 串是否匹配给定串。
那么这就是一个哈希可以解决的事情了，最终时间复杂度 $\mathcal{O}(n\log n)/\mathcal{O}(n)$。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int base = 131;
int n, m;
vector<pair<int, int>> adj[300005];
int str[300005];
ull Pow[300005], ha[300005], ke;
int anc[300005][20], lg2[300005], dep[300005];
int ans[300005];
void dfs(int u, int fa, ull now) {
dep[u] = dep[fa] + 1, anc[u][0] = fa;
ha[u] = now;
for(int j = 1;(1 << j) <= dep[u];j++) {
anc[u][j] = anc[anc[u][j - 1]][j - 1];
}
for(pair<int, int> e: adj[u]) {
if(e.first == fa) {
continue;
}
dfs(e.first, u, now * base + e.second);
}
}
int jump(int u, int lim) {
int cur = u, sum = 0;
for(int j = lg2[dep[u]];j >= 0;j--) {
if(anc[cur][j] != 0 && sum + (1 << j) <= lim) {
sum += (1 << j), cur = anc[cur][j];
}
}
if(sum < lim) {
return 0;
}
else {
return cur;
}
}
ull getha(int x, int y) {
return ha[y] - ha[x] * Pow[m];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
Pow[0] = 1;
lg2[0] = -1;
for(int i = 1;i <= n;i++) {
Pow[i] = Pow[i - 1] * base;
lg2[i] = lg2[i / 2] + 1;
}
for(int i = 1;i <= n - 1;i++) {
int u, v, t;
cin >> u >> v >> t;
adj[u].push_back(make_pair(v, t)), adj[v].push_back(make_pair(u, t));
}
dfs(1, 0, 0);
cin >> m;
for(int i = 1;i <= m;i++) {
cin >> str[i];
ke = ke * base + str[i];
}
for(int i = 1;i <= n;i++) {
int p = jump(i, m);
if(p != 0 && getha(p, i) == ke) {
ans[p] = i;
}
}
for(int i = 1;i <= n;i++) {
cout << ans[i] << ' ';
}
cout << '\n';
cout.flush();
return 0;
}
矩阵（matrix）
借用了模拟赛的题目，可能会视情况保护隐私在文章中撤掉此题。
总司令小 M 给你了一个由小写字母构成的长度为 $n$ 字符串。
你可以用如下的方法生成一个字符矩阵：对于某个长度 $d\in[1,n]$ ，把字符串划分成不交的 $\lfloor\dfrac{n}{d}\rfloor$ 个长度为 $d$ 的连续子串，以及一个长度为 $n \text{ mod } d$ 的连续子串。我们取出所有长度为 $d$ 的子串，然后以任意顺序排列这些子串，每行放一个子串，形成一个 $\lfloor\dfrac{n}{d}\rfloor$ 行 $d$ 列的矩阵。
请你求能通过这样的方式形成的不同的矩阵的个数，对 $998244353$ 取模。
两个矩阵不同，当且仅当矩阵的行数或列数不同，或者存在某个位置使两个矩阵对应的字符不同。
本题中我们可以枚举 $d$，根据调和级数可知这一部分复杂度为 $\mathcal{O}(n\log n)$。
不同 $d$ 之间对应的矩阵必定不同，因此我们统计每个 $d$ 的取值有多少本质不同的矩阵。
我们枚举所有从 $n$ 个矩阵选出 $\lfloor\dfrac{n}{d}{\rfloor}$ 个字符串的情况，我们可以统计字符串出现次数，然后很轻易的用组合计数统计矩阵答案，那么我们接下来需要解决的问题：如果两种不同的划分方案对应同样的字符串集合，那么此时会算重，此时就需要想到对集合进行哈希的办法了，具体来说，我们先字符串哈希将字符串转为一个数，然后对于一个字符串集合，我们定义集合的哈希值为字符串哈希值之和的三次方并对 $M$ 取模，那么我们用这个集合哈希值来盘集合是否相等就可以了，是不是十分的巧妙？
由于 $\texttt{map}$ 和 $\texttt{unordered_map}$ 均被卡掉，最终手写 $\texttt{Hash Table}$ 通过，时间复杂度 $\mathcal{O}(n\log n)$。
代码
#include <bits/stdc++.h>
using namespace std;
const int base = 131;
const int M = 1999969;
const int SIZE = 2000005;
typedef long long ll;
typedef unsigned long long ull;
const int Mod = 998244353;
int n;
char s[500005];
int frac[500005], inv[500005];
ull ha[500005], Pow[500005], sum;
int tot;
int ans;
struct HashTable {
struct Node {
ull nxt, val, key;
} data[SIZE];
int head[M], size;
int f(ull key) {
return key * key * key % M;
}
void clear() {
for(int i = 1;i <= size;i++) {
head[f(data[i].key)] = 0;
data[i].nxt = data[i].val = data[i].key = 0;
}
size = 0;
}
int que(ull key) {
for(int i = head[f(key)];i;i = data[i].nxt) {
if(data[i].key == key) {
return data[i].val;
}
}
return -1;
}
void modify(ull key, int val) {
for(int i = head[f(key)];i;i = data[i].nxt) {
if(data[i].key == key) {
data[i].val = val;
return;
}
}
}
void ins(ull key, int val) {
data[++size].nxt = head[f(key)], data[size].val = val, data[size].key = key;
head[f(key)] = size;
}
} umap, vis;
ll qpow(ll a, ll b) {
ll base = a, res = 1;
while(b) {
if(b & 1) res = res * base % Mod;
b >>= 1;
base = base * base % Mod;
}
return res;
}
inline void add(int &a, int b) {
a += b;
if(a >= Mod) {
a -= Mod;
}
}
inline void mul(int &a, int b) {
ll c = 1ll * a * b;
if(c >= Mod) {
c %= Mod;
}
a = c;
}
void calc(ull H, int v) {
int q = umap.que(H);
if(q == -1) {
umap.ins(H, 0);
q = 0;
}
mul(tot, frac[q]);
mul(tot, inv[q + v]);
umap.modify(H, q + v);
}
inline ull getha(int l, int r) {
return ha[r] - ha[l - 1] * Pow[r - l + 1];
}
bool isprime(int x) {
for(int i = 2;i * i <= x;i++) {
if(x % i == 0) {
return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> (s + 1);
n = strlen(s + 1);
Pow[0] = frac[0] = 1;
for(int i = 1;i <= n;i++) {
Pow[i] = Pow[i - 1] * base;
frac[i] = 1ll * frac[i - 1] * i % Mod;
}
inv[n] = qpow(frac[n], Mod - 2);
for(int i = n - 1;i >= 0;i--) {
inv[i] = 1ll * inv[i + 1] * (i + 1) % Mod;
}
for(int i = 1;i <= n;i++) {
ha[i] = ha[i - 1] * base + s[i];
}
for(int d = 1;d * 2 <= n;d++) {
int r = n % d, q = n / d;
tot = frac[q]; sum = 0;
umap.clear();
vis.clear();
for(int i = 1;i * d <= n;i++) {
int L = (i - 1) * d + 1, R = i * d;
calc(getha(L, R), +1);
sum += getha(L, R) * getha(L, R) * getha(L, R);
}
add(ans, tot);
vis.ins(sum, 1);
if(r != 0) {
for(int i = 1;i * d <= n;i++) {
int L = n - (i * d) + 1, R = n - ((i - 1) * d + 1) + 1;
int L0 = (q - i) * d + 1, R0 = (q - i + 1) * d;
calc(getha(L0, R0), -1);
calc(getha(L, R), +1);
sum -= getha(L0, R0) * getha(L0, R0) * getha(L0, R0);
sum += getha(L, R) * getha(L, R) * getha(L, R);
if(vis.que(sum) == -1) {
add(ans, tot);
vis.ins(sum, 1);
}
}
}
}
for(int d = n / 2 + 1;d <= n;d++) {
if(getha(1, d) == getha(n - d + 1, n)) {
add(ans, +1);
}
else {
add(ans, +2);
}
}
cout << ans << '\n';
cout.flush();
return 0;
}
P8499 [NOI2022] 挑战 NPC Ⅱ
个人认为本题是整场 NOI 中代码难度和思维难度都是最低的一题。时间复杂度其实可能会被诈骗到。
本题中出现了树同构，再根据下方提示给出的信息，不难想到此题与树哈希有关。
观察数据，$k\leq 5$，再根据题目名称，猜想此题是一个跟 $k$ 有关的非多项式算法。
定义 match(uG, uH, lim) 表示 $G$ 子树 $uG$ 和 $H$ 子树 $uH$ 是否能在删除 $lim$ 个节点后同构，这么定义的原因是：如果对于 $uG$ 和 $uH$，它们所对应的所有儿子均能同构，那么就同时会有 $uG$ 和 $uH$ 同构，也就是说，我们向下逐一去递归判断是否可行即可。
那么由于 $k\leq 5$，所以如果多于 $5/lim$ 棵子树未同构，则显然可以直接判为 false，但是所有已经能够匹配上的子树我们直接匹配是否是可行？
容易证明命题：如果存在已经匹配的子树，我们匹配后对答案是不劣的。
记 $G$ 的两棵子树为 $G_A$ 和 $G_B$，$H$ 的两棵子树为 $H_A$ 和 $H_B$，不妨设 $G_B$ 和 $H_B$ 同构，那么来比较 $G_A\rightarrow H_A$ 配对方案和 $G_A\rightarrow H_B,G_B\rightarrow H_A$ 配对方案：在删除的次数上看，$G_A\rightarrow H_A$ 删除的节点数为 $|G_A|-|H_A|$，$G_A\rightarrow H_B,G_B\rightarrow H_A$ 删除的节点数为 $|G_A|-|H_B|+|G_B|-|H_A|=|G_A|-|H_A|$，两种决策等价。
从可行性上看，如果 $G_A\rightarrow H_B,G_B\rightarrow H_A$ 有合法方案，那么 $G_A\rightarrow H_A$ 也一定有合法方案。（包含关系有传递性）
综上可知，我们认为两种决策是等价的，因此优先匹配是可以的。
最终在实现上，由上述的性质我们可以把已经匹配的子树扔掉，只看未匹配成功的子树，如果最终有解，那么必须保证当前层未匹配的子树数量不超过当前层可支持删除最多的节点数 $lim$，我们暴力分配 $lim$ 在子树中的选择并递归检查就行。
理论复杂度上界为 $\mathcal{O}(\sum n_1\cdot \prod\limits_{i=1}^k i!)$，经过合理的剪枝后可以通过。
由于当时写的代码中树哈希方法是错的，改为正确的树哈希后再放上来。
P8819 [CSP-S 2022] 星战
作为 Hash 题，它是有质量的；作为 CSP T3，它是没质量的。
本题要先使用语文阅读理解技巧，不会的请自行练习语文阅读水平，总结题意：实时修改/查询当前状态是否是内向基环森林。
内向基环森林所满足的性质：每一个节点的出度均为一，也就是如果将 $u\rightarrow v$ 的权值看作 $v$，则内向基环森林出现的条件就是边集权值的集合恰好是 $[1,n]$ 的集合。
那么我们使用 Sum Hashing 维护集合即可，具体来说：对每个点随机权值 $val_i$，将边 $u\rightarrow v$ 的边权记录为 $val_v$，那么一次查询就是判断当前边权和是否等于 $\sum\limits_{i=1}^n val_i$。这样你发现修改也是十分易于维护的。
总时间复杂度线性，为了求稳你可以随机多关键字哈希。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Mod = 410347163957; // 随机一个用来哈希的质数
mt19937 engine(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
uniform_int_distribution<ll> dist(l, r);
return dist(engine);
}
int n, m, q, lim = 5;
ll val[5][500005], node[5][500005], sum[5][500005], tot[5], chk[5];
bool isprime(ll x) {
if(x <= 1) {
return false;
}
for(ll i = 2;i * i <= x;i++) {
if(x % i == 0) {
return false;
}
}
return true;
}
void upd(ll &a, ll b) {
a += b;
if(a >= Mod) {
a -= Mod;
}
if(a < 0) {
a += Mod;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// ll Mod = rand(1e11, 1e12);
// while(isprime(Mod) == false) {
// Mod = rand(1e11, 1e12);
// }
// cout << Mod << '\n';
cin >> n >> m;
for(int j = 0;j < lim;j++) {
for(int i = 1;i <= n;i++) {
val[j][i] = rand(1, Mod - 1);
upd(chk[j], val[j][i]);
}
}
for(int i = 1;i <= m;i++) {
int u, v;
cin >> u >> v;
for(int j = 0;j < lim;j++) {
upd(tot[j], val[j][u]);
upd(sum[j][v], val[j][u]);
upd(node[j][v], val[j][u]);
}
}
cin >> q;
while(q--) {
int op, u, v;
cin >> op;
if(op == 1) {
cin >> u >> v;
for(int j = 0;j < lim;j++) {
upd(node[j][v], -val[j][u]);
upd(tot[j], -val[j][u]);
}
}
else if(op == 2) {
cin >> u;
for(int j = 0;j < lim;j++) {
upd(tot[j], -node[j][u]);
node[j][u] = 0;
}
}
else if(op == 3) {
cin >> u >> v;
for(int j = 0;j < lim;j++) {
upd(node[j][v], val[j][u]);
upd(tot[j], val[j][u]);
}
}
else {
cin >> u;
for(int j = 0;j < lim;j++) {
upd(tot[j], sum[j][u] - node[j][u]);
node[j][u] = sum[j][u];
}
}
bool ok = true;
for(int j = 0;j < lim;j++) {
if(tot[j] != chk[j]) {
ok = false; break;
}
}
if(ok == true) cout << "YES\n";
else cout << "NO\n";
}
cout.flush();
return 0;
}
总结
哈希这类题目其实实现难度不难，难就难在看出它是 Hash Algorithm，还是努力提高自己的水平吧。