哈希（Hash）

Hash 表

Hash 表又称为散列表，一般由 Hash 函数（散列函数）与链表结构共同实现。与离散化思想类似，当我们要对若干复杂信息进行统计时，可以用 Hash 函数把这些复杂信息映射到一个容易维护的值域内。因为值域变简单、范围变小，有可能造成两个不同的原始信息被 Hash函映射为相同的值，所以我们需要处理这种冲突情况。有一种称“开散列”的解决方案是，建立一个邻接表结构，以 Hash 函的值域作为表头数组 head，映射后的值相同的原始信息被分到同一类，构成一个链表接在对应的表头之后，链表的节点上可以保存原始信息和一些统计数据。

Hash 表主要包括两个基本操作:

计算 Hash 函数的值。
定位到对应链表中依次遍历、比较。

无论是检查任意一个给定的原始信息在 Hash 表中是否存在，还是更新它在 Hash 表中的统计数据，都需要基于这两个基本操作进行。当 Hash 函数设计较好时，原始信息会被 比较均匀地 分配到各个表头之后，从而使每次查找、统计的时间降低到“原始信息总数除以表头数组长度”。若原始信息总数与表头数组长度都是 O(N)O(N) 级别且 Hash 函数分散均匀，几乎不产生冲突，那么每次查找、统计的时间复杂度期望为 O(1)O(1) 。

例如，我们要在一个长度为 NN 的随机整数序列 AA 中统计每个数出现了多少次。可以设计 Hash 函数为 H(x)=(xmodP)+1H(x)=(xmodP)+1 其中 PP 是个比较大的质数但不超过 NN 。显然，这个 Hash 函数把数列 AA 分成 PP 类，我们可以依次考虑数列中的每个数 A[i]A[i] ，定位到 head[H(A[i])]head[H(A[i])] 这个表头所指向的链表。如果该链表中不包含 A[i]A[i] 我们就在表头后插入一个新节点 A[i]A[i] ，并在该节点上记录 A[i]A[i] 出了 11 次，否则我们就直接找到已经存在的 A[i]A[i] 节点将其出现次加 11 。因为整数序列 AA 是随机的，所以最终所有的 A[i]A[i] 会比较均地分散在各个表头之后，整个算法的时间复杂度可以近
似达到 O(N)O(N) 。

上面的例子是一个非常简单的 Hash 表的直观应用。对于非随机的数列，我们可能需要设计更好的 Hash 函数来保证其时间复度。同样地，如果我们需要维护的是比大整数复杂得多的信息的某些性质(如是否存在、出现次数等)，也可以用 Hash 来解决。字符串就是一种比较一般化的信息，在本节的后半部分，我们将会介绍一个竞赛中极其常用的字符串 Hash 算法。

例题1： P6486 雪花雪花雪花 - TopsCoding

定义 Hash 函数 H(ai,1,ai,2,...,ai,6)=(∑j=16ai,j+∏j=16ai,j)modPH(ai,1,ai,2,...,ai,6)=(∑j=16ai,j+∏j=16ai,j)modP ，其中 PP 是我们自己选取的一个较大的质数。显然，对于两片形状相同的雪花，它们六个角的长度之和、长度之积都相等，因此它们的 Hash 函数值也相等。

建立一个 Hash 表，把 nn 片雪花依次插入。对于每片雪花 ai,1,ai,2,...,ai,6ai,1,ai,2,...,ai,6 ，我们直接扫描表头 H(ai,1,ai,2,...,ai,6)H(ai,1,ai,2,...,ai,6) 对应的链表，检查是否存在与 ai,1,ai,2,...,ai,6ai,1,ai,2,...,ai,6 形状相同的雪花即可。对于随机数据，期望的时间复杂度为 O((N/P)2N)O((N/P)2N) ；取 PP 为最接近 NN 的质数，期望的时间复杂度为 O(N)O(N) 。在下一节中，我们将学习循环同构串的“最小表示法”，进一步提高判断两片雪花形状是否相同的效率。

问题1：设计哈希函数时，一定要对素数取模吗？

回答1：不一定，看你对什么数据hash，以及要用来干什么。假如哈希的对象是随机均匀分布的，那么无论模数取什么，哈希后的分布仍会是均匀的，也就无所谓一定要模质数。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。因此，我们往往会让模数是一个大质数。

参考代码：

const int N = 100006, P = 99991;
int n, a[6], b[6];
struct Snow {  // 雪花int s[6];
};
vector<Snow> snow[N];  // 哈希表int H() {  // 哈希函数int s = 0, k = 1;for(int i = 0; i < 6; i++) {(s += a[i]) %= P;k = (long long)k * a[i] % P;}return (s + k) % P;
}bool pd() {for(int i = 0; i < 6; i++)for(int j = 0; j < 6; j++) {bool flag = 1;for(int k = 0; k < 6; k++)if(a[(i+k)%6] != b[(j+k)%6]) {flag = 0;break;}if (flag) return 1;flag = 1;for(int k = 0; k < 6; k++) {if(a[(i+k)%6] != b[(j-k+6)%6]) {flag = 0;break;}}if(flag) return 1;}return 0;
}bool insert() {int h = H();for(auto c : snow[h]) {memcpy(b, c.s, sizeof b);if(pd()) return 1;}Snow s;memcpy(s.s, a, sizeof s.s);snow[h].push_back(s);return 0;
}int main() {cin >> n;for(int i = 1; i <= n; i++) {for (int j = 0; j < 6; j++) cin >> a[j];if(insert()) {cout << "Twin snowflakes found.";return 0;}}cout << "No two snowflakes are alike.";return 0;
}

例题2： P6224 合肥市2022初中组牛了个牛 - TopsCoding

对异或的性质敏感的同学可以看出本题如果采用前缀区间异或去计算会比较简洁，但是如果直接做异或，会有问题，可能出现 a⊗b=c⊗da⊗b=c⊗d 的情况。于是我们可以考虑把输入的数字从值域 [1,n][1,n] 哈希后映射到一个更大的值域上之后，再做前缀异或，这样出现 a⊗b=c⊗da⊗b=c⊗d 的概率就会极大降低。

如果还是担心一次哈希后会出现上面的情况，那么可以换一个模数，再对原数组做一次哈希，如此概率就会更低。这样的处理方式叫做双哈希，是一种常见的避免哈希冲突的处理方式。

字符串哈希

有时，我们要对字符串进行查找，这时，可能会用到字符串哈希的技巧。

下面介绍的字符串 Hash 函数把一个任意长度的字符串映射成一个非负整数，并且其冲突概率几乎为 00 。

取一固定值 PP ，把字符串看作 PP 进制数，并分配一个大于 00 的数值，代表每种字符。一般来说，我们分配的数值都远小于 PP 。例如，对于小写字母构成的字符串，可以令 a=1,b=2,...,z=26a=1,b=2,...,z=26 。取一固定值 MM ，求出该 PP 进制数对 MM 的余数作为该字符串的 Hash 值。

一般来说，我们取 P=131P=131 或 P=13331P=13331 此时 HashHash 值产冲突的率极低，只要 Hash 值相同，我们就可以认为原字符串是相等的。通常我们取 M=264M=264 ，即直接使用 unsigned long long 类型存储这个 Hash 值，在计算时不处理算术溢出问题，产生
溢出时相当于自动对 264264 取，这样可以避免低效的取模( modmod ) 运算。

除了在极特殊构造的数据上，上述 Hash 算法很难产生冲突，一般情况下上述 Hash算法完全可以出现在题目的标准解答中。我们还可以多取一些恰当的 PP 和 MM 值(例如大质数)，多进行几组 Hash 运算，当结果都相同时才认为原字符串相等，就更加难
以构造出使这个 Hash 产生错误的数据。

对字符串的各种操作，都可以直接对 PP 进制数进行算术运算反映到 Hash 值上。

构造字符串哈希 ：如果我们已知字符串 SS 的 Hash 为 H(S)H(S) ，那在 SS 后添加一个字符 cc 构成的新字符串 S+cS+c 的 Hash 值就是 H(S+c)=(H(S)∗P+value[c])modMH(S+c)=(H(S)∗P+value[c])modM ，其中乘 PP 就相当于 PP 进制下的左移运算， value[c]value[c] 是我们为 cc 选定的代表数值。
取子串哈希值 ：如果我们已知字符串 SS 的 Hash 值为 H(S)H(S) ，字符串 S+TS+T 的 Hash 值为 H(S+T)H(S+T) ，那么字符串 TT 的 Hash 值 H(T)=(H(S+T)−H(S)∗Plength(T))modMH(T)=(H(S+T)−H(S)∗Plength(T))modM 。这就相当于通过 PP 进制下在 SS 后边补 00 的方式把 SS 左移到与 S+TS+T 的左端对齐，然后二者相减就得到了 H(T)H(T) 。

例如， S=S= abc， c=c= d， T=T= xyz，则：

SS 表示 PP 进制数： 1 2 31 2 3

H(S)=1∗P2+2∗P+3H(S)=1∗P2+2∗P+3

H(S+c)=1∗P3+2∗P2+3∗P+4=H(S)∗P+4H(S+c)=1∗P3+2∗P2+3∗P+4=H(S)∗P+4

S+TS+T 表示为 PP 进制数： 1 2 3 24 25 261 2 3 24 25 26

H(S+T)=1∗p5+2∗p4+3∗p3+24∗p2+25∗p+26H(S+T)=1∗p5+2∗p4+3∗p3+24∗p2+25∗p+26

SS 在 PP 进制下左移 length(T)length(T) 位： 1 2 3 0 0 01 2 3 0 0 0

二者相减就是 TT 表示为 PP 进制数： 24 25 2624 25 26

H(T)=H(S+T)−(1∗P2+2∗P+3)∗P3=24∗P2+25∗P+26H(T)=H(S+T)−(1∗P2+2∗P+3)∗P3=24∗P2+25∗P+26

根据上面两种操作，我们可以通过 O(N)O(N) 的时间预处理符所有前缀 Hash 值并在 O(1)O(1) 的时间内查询它的任意子串的 Hash 值。

问题2：如果两个字符串明明不相等，但他们取模后的结果相等，这个概率有多大？

回答2：把这个问题换一种问法: 给你 nn 个字符串，出现两个字符串明明不相等，他们对应的数字模 PP 却相等的概率超过 50%50% 的可能性有多大? 这就和我们之前学过的生日悖论完全一致了！这里可以直接给出结论——当 n>Pπ/2n>Pπ/2 时，概率就会超过 50%50% 。也就是说，当 nn 很大的时候，比如 nn 是 106106 级别的时候，模数至少要取到 10121012 才放心。但是在使用那么大的模数去进行运算的时候，会非常地不方便，所以一般情况下，我们直接利用 unsigned long long 的溢出来做取模运算，这样效率还更高。

当然，我们也可以取两个 109109 级别的质数来代替取一个 10181018 级别的质数，然后分别做哈希，分别比较。只有当两种情况哈希值都相等的情况下，我们才认为原来的字符串相等。

为什么取两个 109109 级别的质数就能代替一个 10181018 级别的质数呢? 这是因为，我们分别求出了两种情况对应的进制数在模意义下的哈希值，那就可以用中国剩余定理还原成一个 0∼10180∼1018 的模意义下的取模后的值。

例题3： P6487 兔子与兔子 - TopsCoding

属于模板题，直接用上面的思路去处理即可。

参考代码：

const int N = 1e6+5;
string s; 
int n, q;
unsigned long long f[N], p[N];  // 2^64 溢出 = 取模
int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> s >> q;n = s.size();p[0] = 1; // 131^0for (int i = 1; i <= n; i++) {f[i] = f[i-1] * 131 + (s[i-1]-'a'+1); // 前 1~i 个字符的前缀哈希值p[i] = p[i-1] * 131;                  // 131 进制下的 131^i，用于计算区间哈希值}for (int i = 1; i <= q; i++) {int l1, r1, l2, r2;cin >> l1 >> r1 >> l2 >> r2;if (f[r1] - f[l1-1] * p[r1-l1+1] == // l1~r1 的哈希f[r2] - f[l2-1] * p[r2-l2+1]) { // l2~r2 的哈希puts("Yes");} else {puts("No");}}
}

例题4： P6488 最长的回文子串（Palindrome） - TopsCoding

我们知道，回文子串有两种：长度是奇数的和长度是偶数的。

于是在本题中，我们可以枚举 SS 的回文子串的中心位置 ii ，看从这个中心位置出发向左右两侧最长可以扩展出多长的回文串。也就是说：

奇数长度的：求出一个最大的整 pp 使得 S[i−p∼i]=reverse(S[i∼i+p])S[i−p∼i]=reverse(S[i∼i+p]) ，那么以 ii 为中心的最长奇回文子的长度就是 2∗p+12∗p+1 。
偶数长度的：求出一个最大的整数 qq 使得 S[i−q∼i−1]=reverse(S[i∼i+q])S[i−q∼i−1]=reverse(S[i∼i+q]) ，那么以 i−1i−1 和 ii 之间的夹缝为中心的文子的度就是 2∗q2∗q 。

根据上一道题目，我们已经知道在 O(N)O(N) 预处理前缀 Hash 值后，可以 O(1)O(1) 计算任意子串的 Hash 值。类似地，我们可以着做一预处理，就可以 O(1)O(1) 计算任意子串倒着读的 Hash 值。于是我们可以对 pp 和 qq 进行二分答案查找。用 Hash O(1)O(1) 比较一个正着读的子串和一个倒着读的子串是否相等，从而在 O(log⁡N)O(logN) 时间内求出最大的 pp 和 qq 。在枚举过的所有中心位置对应的奇偶回文子串长度中取 max 就是整道题目的答案，时间复杂度为 O(Nlog⁡N)O(NlogN) 。

有一个名为 Manacher 的算法可以 O(N)O(N) 解该问题，感兴趣的读者可以自行查阅相关资料，推荐阅读 Manacher - OI Wiki (oi-wiki.org)。