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

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

取一固定值 P，把字符串看作 P 进制数，并分配一个大于 0 的数值，代表每种字符。一般来说，我们分配的数值都远小于 P。例如，对于小写字母构成的字符串，可以令 a=1,b=2,...,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^length(T))mod M。这就相当于通过 P 进制下在 S 后边补 0 的方式，把 S 左移到与 S+T 的左端对齐，然后二者相减就得到了 H(T)。

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