哈希

引入#

现在有 $n$ 个数字 $\{a_i\}$，另外给一个数字 $b$，询问 $b$ 是否在 $\{a_i\}$ 中出现过。最朴素（也是最优）的做法是遍历一遍 $a_i$，依次比较然后给出判断，复杂度 $O(n)$.

问题升级#

现在有 $n$ 个数字 $\{a_i\}$，另外给 $m$ 个数字 $\{b_i\}$，询问每个 $b_i$ 是否在 $\{a_i\}$ 中出现过。仍然按照刚刚的做法，复杂度变为 $O(mn)$.

但是，如果我们提前对 $\{a_i\}$ 排序，然后每次在 $\{a_i\}$ 中二分查找每个 $b_i$，那么预处理和查找的总体复杂度变为 $O((n+m)\log n)$.

问题再次升级#

现在有 $n$ 个数字 $\{a_i\}$ 和 $m$ 个数字 $\{b_i\}$，但是交替给出，并且每次给出 $b_i$ 之后，必须立刻回答已经给出的 $a_i$ 中是否存在过 $b_i$.

这是一个强制在线的问题，我们没法「提前排序」了。如果每次查询之前都重新排序，复杂度可能达到 $O(nm\log n)$. 学过高级数据结构的同学们可能会说：“这题我会，一个平衡树搞定。”

但如果我们换一种思考方式？#

回到刚刚，如果我们换一条技术路线，直接对 $\{a_i\}$ 的值域开一列桶 $\mathrm{buk}$，一旦输入一个 $a_i$，就把 $\mathrm{buk}[a_i]$ 增加 $1$，然后查询的时候只需要判断 $\mathrm{buk}[b_i]$ 是否大于零即可。时间复杂度直接变成 $O(n+m)$，并且完全支持在线。这种做法被称为“桶”。

然而，相比前面的方法，这种方法也有诸多限制：它必须要求 $\{a_i\}$ 的值域不能过大，如果 $\{a_i\}$ 的值域范围超过 $10^7$ 就会有内存爆炸的问题；并且 $\{a_i\}$ 必须是整数，不能是小数。

再进一步#

但没关系，针对桶的这些问题，人们又开发了一种算法——哈希。

定义#

哈希函数是一类将任意输入映射到有限整数区间的函数。

由于定义域的大小一般远大于值域的大小，因此哈希函数通常不是单射。我们把两个不同的输入被哈希函数映射到同一个整数的现象叫做“哈希冲突”

回到刚刚的问题中，如果我们构造一个哈希函数 $h(x)$，把 $\{a_i\}$ 映射到一个有限整数区间 $[0,N)$ 中，再对 $[0,N)$ 开桶，那么无论 $\{a_i\}$ 是多么大的整数或者实数，都能对应到一个桶，查询的时候只需要在桶里查询 $h(b_i)$ 即可。但是，由于哈希冲突的存在，两个不同的数有概率被分配到一个桶，从而出现 $a_i \ne b_i$ 但 $h(a_i) = h(b_i)$ 的情况，导致出错。

使用鸽巢原理容易证明，如果 $\{a_i\}$ 的长度大于 $N$，那么 $\{a_i\}$ 之间的哈希冲突必然发生。因此实践中要保证 $N$ 不小于 $\{a_i\}$ 的长度。

此外，哈希函数的设计对于减小哈希冲突的概率也十分关键。一个好的哈希函数通常希望输出分布尽量均匀，避免映射结果集中在个别值上。

应用#

哈希的上述性质，使得它非常适合“大值域稀疏数据”的索引任务。所谓大值域，就是原始数据较为复杂，难以直接当做索引；所谓稀疏，就是数据的数目不多，映射到 $[0,N]$ 之后发生冲突的概率较小。

此外，哈希常被用于构造“摘要”。我们十分确信：哈希值如果不同，输入数据就一定不同。因此可以用哈希值代表原数据，进行快速比较、校验。

很多哈希函数降低冲突的方式是引入随机化，但随机化并不是哈希必须的要素。确定性哈希函数应用也很广泛，尤其是在处理线性区间查询问题时。

局部敏感哈希（Locality-Sensitive Hashing, LSH）是一类特殊的哈希方法，其目标不是尽可能避免碰撞，而是让“相似”的对象更容易映射到相同或相近的位置。因此，它常用于近似最近邻搜索、相似图片检索等问题。

由于哈希通常不是单射，因此一般不可逆。这使得哈希在密码学中有广泛应用。不过，如果输入空间较小，或者输入具有明显结构，仍可能通过暴力枚举、字典攻击等方式尝试恢复原始输入。

例题#

大量有关哈希的例题可见【每日一题】第一周 ↗ 的 P1102 A-B 数对 ↗，P2580 于是他错误的点名开始了 ↗，P10468 兔子与兔子 ↗，P1381 单词背诵 ↗。