【算法】哈希学习笔记

1. 哈希（hash）简介

1.1 前言

又来写算法总结了qwq。

今天是 2023/7/8，期末考试已经考完了。初二下注定是一个煎熬的学期，所以我在这一学期并没有学什么新算法，OI 也没什么长进。但倒是深造了几个算法，比如：dp，hash，线段树。

之前一直想写一篇 hash 的学习笔记，但由于种种原因，并没有写成。于是，就在今天，卷完了一天的 whk 过后，我便开始肝 hash 的学习笔记。

本篇主要介绍 hash 的进阶用法，不过也适合 hash 入门（不知道哪来的自信）。如果写假了，就图一乐子qwq。

感谢 @ben093002 对此学习笔记给予结论证明以及鼓励与支持！

好了，正片开始！

1.2 什么是哈希？

哈希算法（Hash Algorithm），又称散列算法。有两种用法，第一种就是将一字符串转化成任意进制的数，目的是方便存储。第二种就是将大范围的数映射成小范围的数，目的也是方便存储。

用第一种打一个比方：

比如要将 ioiakyzy 转成 29 进制的数：

1. 将每一位字母偏移，设偏移量为字母 a 所对应的 ASCLL码 - 1，则字母 a 的原数为 1，字母 b 的原数为 2，字母 c 的原数为 3，(dots)，以此类推；

2. 通过 1 可知，原字符串可转化为 9(15)91(11)(25)(26)(25)；

3. 将 9(15)91(11)(25)(26)(25) 转成 29 进制数：

$9 times 29^7 + 15 times 29^6 + 9 times 29^5 + 1 times 29^4 + 11 times 29^3 + 25 times 29^2 + 26 times 29^1 + 25 times 29^0 = 164356834301$

所以 ioiakyzy 在 29 进制下的 hash 值为 164356834301。

操作 1 的 “字母偏移” 完全可以不需要，设偏移量仅仅是使哈希值的值域变小，方便存储而已。

第二种的话就不用所说了，因为第二种就是我们熟知的离散化，c++ 的 STL 库中的 map 就有体现。

离散化严格意义上是一种哈希。

2. 哈希冲突

2.1 如何解决哈希冲突

在做字符串转哈希值的时候可能会发生一些突发状况。比如哈希值太大了，long long 已经装不下了。怎么办？第一时间会想到对此哈希值取模。但万一有两个不同的字符串所转出来的哈希值取模过后相同，那可就麻烦了。因为这样，在进行对字符串哈希的一系列操作时正确性无法保证了。

这时，就有两种处理方法：

1. 将模数增大；
2. 将模数数量增多；

证明法1的可行性：（模数为质数）

设 (mod1 < mod2)，且 (mod1 = mod2 - x (x in mathbb{N^+}))

因为 (p1 in mathbb{N^+}，forall p1in [0,mod1-1] pmod{mod1})

且 (p2 in mathbb{N^+}，forall p2in [0,mod2-1] pmod{mod2})

所以，在模 (mod1) 意义下的哈希值冲突的概率为 (sumlimits_{i=1}^ndfrac{1}{mod1^2}=dfrac{mod1}{mod1^2}=dfrac{1}{mod1})，模 (mod2) 意义下下的哈希值冲突的概率为 (dfrac{1}{mod2})

因为 (mod1 < mod2)，所以 (dfrac{1}{mod1} > dfrac{1}{mod2})。

所以模数越大，哈希冲突的概率越小。

证毕。

证明法2的可行性：（模数为质数）

设 (n1 < n2)，且有 (mod1_1,mod1_2, mod1_3, dots, mod1_{n1}) 和 (mod2_1, mod2_2, mod2_3, dots, mod2_{n2}) （(forall i leq n1,mod1_i in mathbb{N^+})，(forall j leq n2,mod2_j in mathbb{N^+})，(forall mod1_i ne forall mod2_i)）

由证明1可知，模 (mod1) 意义下的哈希值值域为 (prodlimits_{i=1}^{n1}mod1_i)，模 (mod2) 意义下下的哈希值值域为 (prodlimits_{i=1}^{n2}mod2_i)

所以，模 (mod1) 意义下的哈希值冲突的概率为 (dfrac{1}{prodlimits_{i=1}^{n1}mod1_i})，在模 (mod2) 意义下的哈希值冲突的概率为 (dfrac{1}{prodlimits_{i=1}^{n2}mod2_i})

因为 (prodlimits_{i=1}^{n1}mod1_i < prodlimits_{i=1}^{n2}mod2_i)，所以 (dfrac{1}{prodlimits_{i=1}^{n1}mod1_i} > dfrac{1}{prodlimits_{i=1}^{n2}mod2_i})

所以，模数越多且互不相同的情况下，哈希冲突的概率越小。

证毕。

2.2 解决哈希冲突的注意事项

在 2.1 的一系列证明中都加了一句话：模数为质数。说明模数为质数很重要。

事实也是如此，如果模数为合数，哈希冲突的概率会增加，具体的证明可以看这里。不过没看懂也没关系，这并不影响哈希的学习。就像学习并查集（路径压缩 + 按秩合并）的时候你也不会证明其时间复杂度。

但是要注意，哈希更像是一种骗分的工具，因为它有许多的不确定性在里面，跟模拟退火差不多（或者你写哈希的时候不用模数）。

3. 多种哈希的实现

3.1 字符串哈希

字符串哈希是一种很常见的哈希函数。

现在给你一个问题：给定两个字符串 (S)，(T)，长度别为 (n), (m)。求 (T) 是否是 (S) 的子串。

暴力做法很简单，扫 (S)，(T) 再 check 即可。时间复杂度 (O(nm))。

其实还能更优，用 KMP 算法可以做到 (O(n))。

但 KMP 不会怎么办。用哈希！！

设 (sum_i) 表示字符串 (S) 子串 ([1, i]) 的哈希值。结合 1.2 对哈希的概论，可得：

设哈希进制为 (H)，模数为 (mod)。可得字符串 (S) 的子串哈希通项公式为 $sum_i = sumlimits_{j=1}^i S_j times H^{i-j} $

递推式为：

(begin{cases}sum_0=0\sum_i=sum_{i-1}*H+S_iend{cases})

代码实现：

sum[0] = 0; for (int i = 1; i <= n; i++) {   sum[i] = sum[i-1] * H + S[i] % mod; } 

OK！哈希预处理完成。

现在可以用 (sum) 这个字符串哈希做很多很多的操作，比如：

3.1.1 截取子串哈希

怎样截取子串哈希值呢？手推一下就行了。

截取 ([l,r]) 的哈希值，可以类比前缀和。

(sum_{i=l}^r s_i times H^{r-i})

(= H^{r-i} times (sum_{i=1}^r s_i - sum_{i=1}^{l-1} s_i))

(= sum_{i=1}^r s_i times H^{r-i} - sum_{i=1}^{l-1} s_i times H^{r-i})

(= sum_{i=1}^r s_i times H^{r-i} - H^{r-l+1} times sum_{i=1}^{l-1} s_i H^{l-i-1})

(= sum_r - sum_{l-1} times H^{r-l+1})

所以 ([l,r]) 的哈希值为 (sum_r - sum_{l-1} times H^{r-l+1})。

不过 (H^{r-l+1}) 要快速幂，太麻烦了。所以直接预处理一下 H 的任意次方即可。

由于可能会减出负数，所以减完之后先加mod再模mod就行了。具体实现看代码。

时间复杂度 (O(1))。

代码实现：

预处理

int p[N] = {0}; for (int i = 1; i <= n; i++) {   p[i] = p[i-1] * H % mod; } 

截取子串

int get(int l, int r) {   return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod; } 

3.1.2 对比两段子串是否相同

很简单，只要结合截取子串操作便能完成。

时间复杂度 (O(1))。

代码实现：

int get(int l, int r) {   return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod; } bool check(int l, int r, int L, int R) {   return get(l,r) == get(L,R); } 

回到最初的问题：给定两个字符串 (S)，(T)，长度别为 (n), (m)。求 (T) 是否是 (S) 的子串。

这下不就很简单了吗？

核心代码实现：

int get(int l, int r) {   return (sum[r] % mod - sum[l-1] * p[r-l+1] + mod) % mod; }  int main() {   int n, m, sum[N], SUM[N];   char S[N], T[N];   cin >> n >> m;   cin >> S + 1 >> T + 1;   sum[0] = 0;   for (int i = 1; i <= n; i++) {     sum[i] = sum[i-1] * H + S[i] % mod;   }   for (int i = 1; i <= m; i++) {     SUM[i] = SUM[i-1] * H + T[i] % mod;   }   for (int i = 1; i + m - 1 <= n; i++) {     if(get(i, i + m - 1) == SUM[m]) puts("Yes");     else puts("No");   }   return 0; } 

3.1.3 字符串哈希的运用

假如你忘记了马拉车，kmp等字符串算法怎么写了，不妨试一试字符串哈希。

还有就是你可以用其优化 dp，比如这一道题 —— gym104081，可以试着做一做，做完后可能你会对字符串哈希有更深刻的理解。

3.1.4 关于字符串哈希的几种优化方式

3.1.4.1 单哈希

容错率较高，但相对来说代码易实现。

具体证明可参考 2.2 如何解决哈希冲突 这一章的相关证明。

3.1.4.2 双哈希

发现单哈希在某种情况下会寄掉。这时使用双哈希是最好的选择。

可以证明，模数增多可以降低哈希的容错率（冲突概率），此在上文已经证明。

不过写多重哈希可能会导致空间承受不起（不过你不写哈希表就没有关系）。所以，正常哈希不建议写模数数量大于二的哈希。

可以证明，当模数增加一个，离散值域会增加一倍，容错率便会大大下降。

具体实现为用一个 (pair) 。第一维记录在模第一个模数的意义下的哈希值，第二维记录在模第二个模数的意义下的哈希值。当两维都对应相等时，哈希值才有可能相等。（其实根本不需要证明，感性理解一下也可以）。

3.1.4.3 自然溢出

你还在因为选不定模数而烦恼吗？你还在因为每次计算都要取模而烦恼吗？

有了自然溢出，你还在担心什么？

如果你把存储哈希值的数组的数据类型改成 unsigned long long。首先，这个东西不支持存储负数，处理方法为将哈希值模一个超大的非素数，使其不会爆 (long long) 的符号位。

其实这一步就相当于再给哈希取模的过程。不仅短而好写，而且很简单，每次计算不需要模数。

必须注意的是，自然溢出模的数不是质数这意味着它的冲突率高于质数，不过，由于这个模数足够大，所以可忽略这点区别。

不过缺点就是麻仁，CF 卡这玩意卡出了花样。（在 CF 和 AT 手上自然溢出容错率接近于 (100%)）

3.1.4.4 无错哈希

其实原理很简单，就是我们要记录每一个已经诞生的哈希值，然后对于每一个新的哈希值，我们都可以来判断是否和已有的哈希值冲突，如果冲突，那么可以将这个新的哈希值不断加上一个大质数，直到不再冲突。

比如这一题：P3370 【模板】字符串哈希

就用一个 vector 存储每一次冲突的哈希值，再暴力扫即可。

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <climits> #include <map> #include <queue> #include <set> #include <cmath> #include <string> #define int long long #define H 19260817 #define rint register int #define For(i,l,r) for(int i=l;i<=r;i++) #define FOR(i,r,l) for(int i=r;i>=l;i--) #define mod 1000003  using namespace std;  inline int read() {   rint x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}   return x*f; }  void print(int x){   if(x<0){putchar('-');x=-x;}   if(x>9){print(x/10);putchar(x%10+'0');}   else putchar(x+'0');   return; }  const int N = 100010;  int n = read(), x, ans;  string s;  vector <string> h[mod];  bool F(int x, const string &s) {   for (auto t : h[x]) {     if(t == s) return 0;   }   h[x].push_back(s);   return 1; }  signed main() {   For(i,1,n) {     cin >> s;     x = 0;     For(j,0,s.size()-1) {       x = (1ll * x * H + s[j]) % mod;     }     ans += F(x, s);   }   cout << ans << 'n';   return 0; } 

3.2 桶哈希

桶哈希的本质是一个“桶”，这个桶很特殊，接下来看看普通桶和桶哈希的时间复杂度区别：

操作	普通桶	桶哈希
单点修改	(O(1))	(O(1))
区间修改	(O(n))	最坏(O(n))
单点查询	(O(1))	不支持
区间查询	(O(n))	不支持
全局查询	(O(n))	(O(1))

这样，桶哈希和普通桶的优势与劣势显而易见。

Q：啊？这样看来，普通桶大胜桶哈希？

是的，这样看来，普通桶大胜桶哈希。但换个角度看就不是了：桶哈希实现起来困难，常数大，且正确率不能保障，但全局查询为 O(1)。

不过，它也不是一无是处。如果它的全局查询可以做到 (O(1))。这也证明，桶哈希可以在一些特殊的题中扮演决定性的角色。

比如，桶哈希可以 (O(1)) 的时间比较两个桶的状态。但是普通的桶做到这一点要 (O(n))。

其实有一个两者的综合版——权值线段树。它的单点/区间修改/查询单次时间复杂度为 (O(log n))，可谓是非常的优秀！

桶哈希：啊？？真的如此吗？。

3.2.1 单点修改

设 (b) 桶哈希第 (i) 位表示 (i) 这个数的出现的次数，(H) 为进制。(x) 为我要在桶中插入的数。

于是就仿照二进制状压的写法，(b = b + H^{x})。然后就没了。

Code:

b += p[x]; 

ps: 省去了取模操作，(p_i) 为预处s理好的 (H^i) 的值。

如果要插入多个数，则在 (p_x) 前面乘上一个系数即可。

3.2.2 区间修改

重复单点修改操作，时间复杂度为 (O(n))。

但是有些时候区间修改的只是固定的，便可考虑离线记录改变的值。这样可以做到期望 (O(1))。

比如我要说的下一道题目。

3.2.3 经典例题 P8819 [CSP-S 2022] 星战

分析得：每一个点的入度都为 (1)，则输出 "YES"，否则输出："NO"。

设一个标准桶 (POS) 为 (111dots11) 这样的全 (1) 桶。设第 (i) 个点的入度为 (r_i)，实际桶 (Hash) 为当前所有节点的入度个数，显然其长度为 (n)，初始第 (i) 位为 (r_i)。在一次操作后只要 (POS = Hash)。则说明其合法。

这一步就体现了桶哈希的强大之处——全局查询为 (O(1)) 时间复杂度。

最后附上代码：

#include <bits/stdc++.h> #define ll long long #define H 500005 #define rint register int #define For(i,l,r) for(rint i=l;i<=r;++i) #define FOR(i,r,l) for(rint i=r;i>=l;--i) #define MOD 1000000007 #define mod 1000000007  using namespace std;  inline int read() {   rint x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}   return x*f; }  void print(int x){   if(x<0){putchar('-');x=-x;}   if(x>9){print(x/10);putchar(x%10+'0');}   else putchar(x+'0');   return; }  const int N = 5e5 + 10;  vector<int> e[N];  ll n, m, q, p[N], POS, Hash, sum[N], rem[N], r[N];  signed main() {   n = read(), m = read();   p[0] = 1;   For(i,1,n) {     p[i] = (p[i - 1] * H) % MOD;     }   For(i,1,n) POS = POS + 1 * p[i];   For(i,1,m) {     int u = read(), v = read();     e[u].push_back(v);     r[u]++;   }   For(i,1,n) {     for (int j = 0; j < e[i].size(); j++) {       int y = e[i][j];       sum[y] += p[i];     }   }   For(i,1,n) rem[i] = sum[i], Hash += sum[i];   q = read();   while(q--) {     int op = read();     if(op == 1) {       int u = read(), v = read();       Hash -= p[u];       rem[v] -= p[u];     } else if(op == 3) {       int u = read(), v = read();       Hash += p[u];       rem[v] += p[u];     } else if(op == 2) {       int u = read();       Hash -= rem[u];       rem[u] = 0;     } else {       int u = read();       Hash -= rem[u] - sum[u];       rem[u] += sum[u];     }     if(Hash == POS) cout << "YES" << 'n';     else cout << "NO" << 'n';   }   return 0; } 

2. 哈希相关例题

2.1 CF1326D2 Prefix-Suffix Palindrome (Hard version)

Problem

给定若干个字符串 (S), 对于每一个字符串，要求选取他的一个前缀（可以为空）和与该前缀不相交的一个后缀（可以为空）拼接成回文串，且该回文串长度最大。求生成的最长回文串是什么。

Solve

可以先做一下小小的分类讨论：

若 (S) 有回文前后缀，并且长度相等（比如：abcdfdcecba，abccba就是长度相等的回文前后缀），那么，肯定取这一段前后缀最优。

把 (s) 的回文前后缀拿掉后，剩下的部分要么是回文前缀，要么是回文后缀。再把其中长度较长的拼接再回文前后缀的中间即可。

比如：abcdfdcecba，先找出其回文前后缀abccba，剩下的部分为 dfdce，发现有一个回文前缀 dfd，于是把其插入 abccba 的中间，最后答案为：abcdfdcba

再比如：abbaxyzyx，它没有回文前后缀，于是要找回文前缀或后缀就行了。答案为：xyzyx。

找回文前后缀可以用双指针，找回文前缀或后缀可以用 hash，时间复杂度 (O(Tn))，也就是 (O(sum |S|))。

Code

#include <bits/stdc++.h> #define int long long  #define H 449 #define rint register int  #define For(i,l,r) for(int i=l;i<=r;++i) #define FOR(i,r,l) for(int i=r;i>=l;--i) #define mod 436522843  using namespace std;  const int N = 1e6 + 10;  int T, n, sum[N], pre[N], p[N];  char a[N];  void solve() {   cin >> a + 1;   n = strlen(a + 1);   p[0] = 1;   For(i,1,n) {     p[i] = p[i-1] * H % mod;   }   int l = 0, r = n+1;   while(a[l+1] == a[r-1] && l <= r) {     l++, r--;   }   if(l > r) {     For(i,1,n) cout << a[i];     cout << 'n';     return ;   }   l++, r--;   sum[l-1] = 0, pre[r+1] = 0;   For(i,l,r) {     sum[i] = sum[i-1] * H % mod + (a[i] - 'a' + 1);     sum[i] %= mod;   }   FOR(i,r,l) {     pre[i] = pre[i+1] * H % mod + (a[i] - 'a' + 1);     pre[i] %= mod;   }   int ansl = 0, ansr = 0;   For(i,l,r) {     if(sum[i] == (pre[l] % mod - pre[i+1] * p[i-l+1] % mod + mod) % mod) {       ansl = l, ansr = i;     }   }   FOR(i,r,l) {     if(pre[i] == (sum[r] % mod - sum[i-1] * p[r-i+1] % mod + mod) % mod) {       if(ansr - ansl + 1 < r - i + 1) {         ansl = i, ansr = r;       }     }   }   For(i,1,l-1) cout << a[i];   For(i,ansl,ansr) cout << a[i];   For(i,r+1,n) cout << a[i];   cout << 'n'; }  signed main() {   cin >> T;   while(T--) {     solve();   }   return 0;  }   /* 1 abbaxyzyx */ 

2.2 P4503 [CTSC2014] 企鹅 QQ

Problem

定义若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。求在给定的 (n) 个账户名称中，有多少对是相似的。

Solve

组合数学 + Hash

预处理出每一个字符串的前后缀 (Hash)，再枚举每一位，用组合数学统计合法数对就行。

Code

#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define H 27 #define rint register int #define For(i,l,r) for(rint i=l;i<=r;++i) #define FOR(i,r,l) for(rint i=r;i>=l;--i) #define MOD 1000003 #define mod 1000000007  using namespace std;  inline int read() {   rint x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}   return x*f; }  void print(int x){   if(x<0){putchar('-');x=-x;}   if(x>9){print(x/10);putchar(x%10+'0');}   else putchar(x+'0');   return; }  const int N = 3e4 + 10, M = 205;  int n, L, S;  ull pre[N][M], nxt[N][M], p[N], ans;  char s[N][M];  pair<ull, ull> k[N];  signed main() {   n = read(), L = read(), S = read();   p[0] = 1;   For(i,1,L) p[i] = p[i - 1] * H;     For(i,1,n) {     For(j,1,L) cin >> s[i][j];     For(j,1,L) pre[i][j] = pre[i][j - 1] * H + s[i][j];     FOR(j,L,1) nxt[i][j] = nxt[i][j + 1] * H + s[i][j];   }   For(i,1,L) {     For(j,1,n) {       k[j].first = pre[j][i-1];        k[j].second = nxt[j][i+1];     }     sort(k + 1, k + n + 1);     int l = 1, r = 1;     while(r <= n) {       while(k[l] == k[r] && r <= n) r++;       r--;       ans += (((r - l + 1) * (r - l)) >> 1);       l = r + 1, r++;     }   }   cout << ans << 'n';   return 0; }  

2.3. P7469 [NOI Online 2021 提高组] 积木小赛

Problem

给定两个长度为 (n) 的小写字母串 (s) 和 (t)。求在不同情况下从 (s) 中选出一个子序列与 (t) 中选出一个子串对应相同的方案数（两种情况不同，当且仅当两序列所选出的字符串在两种情况中不同）。

Solve

枚举 (t) 的子串，固定左端点 (L)，右端点 (r) 递增。同时在 (s) 中找是否有子序列与所枚举的字串对应相同。为了方便统计方案数，可以用 (Hash) 来判断两种情况是否相同。把 (Hash) 值丢到 (unordered)_(set)，(set)，或随便搞一个数组（之后进行 sort 和 unique）里面去。实测只有最后一个方法可以通过。

时间复杂度 (O(N^2log n))。

Code

#include <bits/stdc++.h> #define int long long #define H 37 #define rint register int #define For(i,l,r) for(rint i=l;i<=r;++i) #define FOR(i,r,l) for(rint i=r;i>=l;--i) using namespace std;  inline int read() {   rint x=0,f=1;char ch=getchar();   while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}   return x*f; }  void print(int x){   if(x<0){putchar('-');x=-x;}   if(x>9){print(x/10);putchar(x%10+'0');}   else putchar(x+'0');   return; }  const int N = 3e3 + 10; const int M = 9e6 + 10;  int n, hs, nxt[N][156], res[M], tot;  char s[N], t[N];  signed main() {   n = read();   For(i,1,n) cin >> s[i];   For(i,1,n) cin >> t[i];   For(i,1,n) {     For(j,i,n) {       if(!nxt[i][s[j]]) nxt[i][s[j]] = j;     }   }   For(i,1,n) {     hs = 0;     int k = 1;     For(j,i,n) {        k = nxt[k][t[j]];       if(!k) break;        hs = 1ll * (hs * H) + (t[j] - 'a' + 1);       res[++tot] = hs;       k++;     }   }   sort(res + 1, res + 1 + tot);   cout << ((unique(res + 1, res + 1 + tot)) - res - 1) << 'n';   return 0; }