0x14 Hash

Hash表

Hash 表又称为散列表，一般由 Hash 函数（散列函数）与链表结构共同实现。与离散化思想类似，当我们要对若干复杂信息进行统计时，可以用 Hash 函数把这些复杂信息映射到一个容易维护的值域内。因为值域变简单、范围变小，有可能造成两个不同的原始信息被 Hash 函数映射为相同的值，所以我们需要处理这种冲突情况。

有一种称为“开散列”的解决方案是，建立一个邻接表结构，以Hash函数的值域

作为表头数组head，映射后的值相同的原始信息被分到同一类，构成一个链表接在对应的表头之后，链表的节点上可以保存原始信息和一些统计数据。

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

1. 计算 Hash 函数的值。

2.定位到对应链表中依次遍历、比较。

无论是检查任意一个给定的原始信息在 Hash 表中是否存在，还是更新它在 Hash 表中的统计数据，都需要基于这两个基本操作进行。

当 Hash 函数设计较好时，原始信息会被比较均匀地分配到各个表头之后，从而使每次查找、统计的时间降低到“原始信息总数除以表头数组长度”。若原始信息总数与表头数组长度都是 $O(N)$ 级别且 Hash 函数分散均匀，几乎不产生冲突，那么每次查找、统计的时间复杂度期望为 $O(1)$ 。

例如，我们要在一个长度为 $N$ 的随机整数序列 $A$ 中统计每个数出现了多少次。当数列 $A$ 中的值都比较小时，我们可以直接用一个数组计数（建立一个大小等于值域的数组进行统计和映射，其实就是最简单的Hash思想）。当数列 $A$ 中的值很大时，我们可以把 $A$ 排序后扫描统计。这里我们换一种思路，尝试一下Hash表的做法。

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

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

【例题】Snowflake Snow Snowflakes POJ3349

有 $N$ 片雪花，每片雪花由六个角组成，每个角都有长度。第 $i$ 片雪花六个角的长度从某个角开始顺时针依次记为 $a_{i,1}, a_{i,2}, \dots, a_{i,6}$ 。

因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。例如 $a_{i,1}, a_{i,2}, \dots, a_{i,6}$ 和 $a_{i,2}, a_{i,3}, \dots, a_{i,6}, a_{i,1}$ 就是形状相同的雪花。 $a_{i,1}, a_{i,2}, \dots, a_{i,6}$ 和 $a_{i,6}, a_{i,5}, \dots, a_{i,1}$ 也是形状相同的雪

花。

我们称两片雪花形状相同，当且仅当它们各自从某一个角开始顺时针或逆时针记录长度，能得到两个相同的六元组。求这 $N$ 片雪花中是否存在两片形状相同的雪花。

定义Hash函数 $H\big(a_{i,1},a_{i,2},\dots ,a_{i,6}\big) = \left(\sum_{j = 1}^{6}a_{i,j} + \prod_{j = 1}^{6}a_{i,j}\right)\mathrm{mod}P$ ，其中 $P$ 是我们自己选取的一个较大的质数。显然，对于两片形状相同的雪花，它们六个角的长度之和、长度之积都相等，因此它们的Hash函数值也相等。

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

const int SIZE = 100010;  
int n, tot, P = 99991;  
int snow[SIZE][6], head[SIZE], next[SIZE];  
int H(int *a) {  
    int sum = 0, mul = 1;  
    for (int i = 0; i < 6; i++) {  
        sum = (sum + a[i]) % P;  
        mul = (long long)mul * a[i] % P;  
    }  
    return (sum + mul) % P;  
}  
bool equal(int *a, int *b) {  
    for (int i = 0; i < 6; i++) {  
        bool eq = 1;  
        for (int k = 0; k < 6; k++) {  
            if (a[(i+k)%6] != b[(j+k)%6]) eq = 0;  
            if (eq) return 1;  
            eq = 1;  
            for (int k = 0; k < 6; k++) {  
                if (a[(i+k)%6] != b[(j-k+6)%6]) eq = 0;  
                if (eq) return 1;  
            }  
        }

return 0;   
}   
bool insert(int \*a){ int val  $=$  H(a); //遍历表头head[val]指向的链表，寻找形状相同的雪花 for (int i = head[val];i;i  $=$  next[i]) { if (equal(snow[i],a)) return 1; } //未找到形状相同的雪花，执行插入 ++tot; memcpy(snow[tot],a,6\*sizeof(int)); next[tot]  $=$  head[val]; head[val]  $=$  tot; return 0;   
}   
int main(){ cin >> n; for (int i  $= 1$  ;i  $<   =$  n;i++){ int a[10]; for (int j  $= 0$  ;j  $<  6$  ;j++) scanf("%d",&a[j]); if (insert(a)){ puts("Twin snowflakes found."); return 0; } } puts("No two snowflakes are alike.");   
}

字符串Hash

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

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

串的Hash值。

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

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

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

如果我们已知字符串 $S$ 的Hash值为 $H(S)$ ，那么在 $S$ 后添加一个字符 $c$ 构成的新字符串 $S + c$ 的Hash值就是 $H(S + c) = (H(S)*P + value[c]) \mod M$ 。其中乘 $P$ 就相当于 $P$ 进制下的左移运算，value[c]是我们为 $c$ 选定的代表数值。

如果我们已知字符串 $S$ 的Hash值为 $H(S)$ ，字符串 $S + T$ 的Hash值为 $H(S + T)$ ，那么字符串 $T$ 的Hash值 $H(T) = (H(S + T) - H(S)*P^{\mathrm{length}(T)})\bmod M$ 。这就相当于通过 $P$ 进制下在 $S$ 后边补0的方式，把 $S$ 左移到与 $S + T$ 的左端对齐，然后二者相减就得到了 $H(T)$ 。

例如， $S = \mathrm{"abc"}$ ， $c = \mathrm{"d"}$ ， $T = \mathrm{"xyz"}$ ，则：

$S$ 表示为 $P$ 进制数：123

$S + T$ 表示为 $P$ 进制数：123242526

$S$ 在 $P$ 进制下左移 $\mathrm{length}(T)$ 位：123000

二者相减就是 $T$ 表示为 $P$ 进制数：24 25 26

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

【例题】兔子与兔子

很久很久以前, 森林里住着一群兔子。有一天, 兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列 (小兔子是外星生物, DNA 序列可能包含 26 个小写英文字母), 然后我们每次选择两个区间, 询问如果用两个区间里的 DNA 序列分别生产出来两只兔子, 这两只兔子是否一模一样。注意两只兔子一模一样只可能是它

们的 DNA 序列一模一样。 $1 \leq \operatorname{length}(S), Q \leq 10^{6}$ 。

记我们选取的DNA序列为 $S$ ，根据我们刚才提到的字符串Hash算法，设 $F[i]$ 表示前缀子串 $S[1\sim i]$ 的Hash值，有 $F[i] = F[i - 1]*131 + (S[i] - "a" + 1)$

于是可以得到任一区间 $[l, r]$ 的 Hash 值为 $F[r] - F[l - 1] * 131^{r - l + 1}$ 。当两个区间的 Hash 值相同时，我们就认为对应的两个子串相等。整个算法的时间复杂度为 $O(|S| + Q)$ 。

char s[1000010];   
unsigned long long f[1000010], p[1000010];   
int main(){ int n, q; cin >> n >> q; scanf("%s", s + 1);  $\mathsf{p}[\mathsf{0}] = \mathsf{1}$  //  $131^{\wedge}0$  for (int i = 1; i <= n; i++) {  $\mathsf{f}[\mathsf{i}] = \mathsf{f}[\mathsf{i - 1}] * 131 + (\mathsf{s}[\mathsf{i}] - 'a' + 1)$  ; // hash of 1~i  $\mathsf{p}[\mathsf{i}] = \mathsf{p}[\mathsf{i - 1}] * 131$  //  $131^{\wedge}\mathsf{i}$  } for (int i = 1; i <= q; i++) { int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2); if (f[r1] - f[l1-1] * p[r1-l1+1] == // hash of l1~r1 f[r2] - f[l2-1] * p[r2-l2+1]) { // hash of l2~r2 puts("Yes"); } else { puts("No"); } }

【例题】Palindrome POJ3974

如果一个字符串正着读和倒着读是一样的，则称它是回文的。给定一个长度为 $N$ 的字符串 $S$ ，求它的最长回文子串。

写几个回文串观察它们的性质，我们可以发现回文串分为两类：

奇回文串 $A[1 \sim M]$ ，长度 $M$ 为奇数，并且 $A[1 \sim M / 2 + 1] = \text{reverse}(A[M / 2 + 1 \sim M])$ ，它的中心点是一个字符。其中 $\text{reverse}(A)$ 表示把字符串 A 倒过来。

偶回文串 $B[1\sim M]$ ，长度 $M$ 为偶数，并且 $B[1\sim M / 2] = \mathrm{reverse}(B[M / 2 + 1\sim M])$

它的中心点是两个字符之间的夹缝。

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

1. 求出一个最大的整数 $p$ 使得 $S[i - p \sim i] = \text{reverse}(S[i \sim i + p])$ ，那么以 $i$ 为中心的最长奇回文子串的长度就是 $2 * p + 1$ 。

2. 求出一个最大的整数 $q$ 使得 $S[i - q \sim i - 1] = \text{reverse}(S[i \sim i + q])$ , 那么以 $i - 1$ 和 $i$ 之间的夹缝为中心的最长偶回文子串的长度就是 $2 * q$ 。

i 奇回文子串：aabbcaacbbab Hash(4,7) $= =$ HashReverse(7,10)

偶回文子串：acabcdcbabc Hash(3,6) $= =$ HashReverse(7,10)

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

有一个名为Manacher的算法可以 $O(N)$ 求解该问题，感兴趣的读者可以自行查阅相关资料。

【例题】后缀数组

后缀数组 $(\mathrm{SA})^{\text{①}}$ 是一种重要的数据结构，通常使用倍增或者DC3算法实现，这超出了我们的讨论范围。在本题中，我们希望使用快排、Hash与二分实现一个简单的 $0(n\log^2 n)$ 的后缀数组求法。

详细地说，给定一个长度为 $n$ 的字符串 $S$ （下标 $0 \sim n - 1$ ），我们可以用整数 $k (0 \leq k < n)$ 表示字符串 $S$ 的后缀 $S(k \sim n - 1)$ 。把字符串 $S$ 的所有后缀按照字典序排列，排名为 $i$ 的后缀记为 SA $[i]$ 。额外地，我们考虑排名为 $i$ 的后缀与排名为 $i - 1$ 的后缀，把二者的最长公共前缀的长度记为 Height $[i]$ 。我们的任务就是求出 SA 与 Height 这两个数组。

$S$ 的所有后缀的总长度在 $O(n^{2})$ 级别，如果我们直接对这 $n$ 个后缀进行快排，对于两个字符串的大小比较采取逐字符扫描的方式，最坏情况下时间复杂度将达到

$\mathrm{O}(n^{2}\log n)$

在上一道题目中，我们已经知道如何求出一个字符串的所有前缀Hash值，并进一步在O(1）的时间内查询任意一个区间子串的Hash值。所以在快速排序需要比较两个后缀 $p$ 和 $q$ 时，我们就可以使用二分法，每次二分时利用Hash值O(1）地比较 $S[p\sim p + mid - 1]$ 与 $S[q\sim q + mid - 1]$ 这两段是否相等，最终求出 $S[p\sim n]$ 与 $S[q\sim n]$ 的最长公共前缀的长度，记为len。于是 $S[p + len]$ 和 $S[q + len]$ 就是这两个后缀第一个不相等的位置，直接比较这两个字符的大小就可以确定 $S[p\sim n]$ 与 $S[q\sim n]$ 的大小关系。从而每次比较的总复杂度就是 $\mathrm{O}(\log n)$ ，整个快排求出SA数组的过程的复杂度就是 $\mathrm{O}(n\log^2 n)$ 。在排序完成后，我们对于每对排名相邻的后缀执行与上述相同的二分过程，就可以求出Height数组了。