哈希

本小节讨论哈希相关的算法和数据结构。

哈希表

哈希表（hash table）是一种基于哈希函数的数据结构，用于实现快速的数据存储和检索。哈希表通过将键映射到数组中的索引来存储数据，通常插入、删除和查找操作的平均时间复杂度为 $O(1)$ 。这里“通常”的前提是正确实现了哈希表，有好的哈希函数，很好的处理了哈希碰撞，表的大小是合适的。

哈希函数

哈希表存储键值的集合 $S$ ，这里假定所有可能的键值的集合是 $U$ 。我们希望存储数据的数组大小 $n$ 正比于 $|S|$ 而不是 $|U|$ ，因为 $|U|$ 可能非常大。

哈希函数（hash function）是一个函数 $h: U \to \{0, 1, \ldots, n-1\}$ ，它将键值映射到数组的索引。

不管哈希函数如何设计，存在一个集合 $S$ ，大小是 $|U|/n$ ，使得对所有 $k_1,k_2\in S$ 都有 $h(k_1) = h(k_2)$ 。使用鸽巢原理（pigeonhole principle）可以证明这一点。

一个好的哈希函数时间复杂度是 $O(1)$ ，空间复杂度也是 $O(1)$ ，并且能够将键值均匀地分布在数组索引空间中。教科书中比较好的哈希函数是 $h(k)=(ak+b)\mod n$ ，如果 $a,b,n$ 选择的足够好，这个哈希函数可以用于快速的原型实现。这个哈希函数计算简单，时间复杂度是 $O(1)$ ，空间复杂度也是 $O(1)$ ，只需要存储 $a,b,n$ 这三个参数。

哈希碰撞

由于哈希函数将一个大的键值空间映射到一个较小的数组索引空间，可能会发生哈希碰撞（hash collision），即不同的键值被映射到同一个索引。用数学语言表示就是说存在两个不同的键值 $k_1$ 和 $k_2$ ，使得 $h(k_1) = h(k_2)$ 。

理想中的哈希函数是将每一个键值独立且均匀的分配到 $\{0, 1, \ldots, n-1\}$ 中的一个索引上。但是在实际应用中，这种哈希函数是不存在的，不过这种随机函数是评价哈希函数好坏的黄金标准。

处理哈希碰撞的方法

常见的处理哈希碰撞的方法有两种：链地址法（separate chaining）和开放地址法（open addressing）。

链地址法的核心思想是使用一个链表来存储所有被映射到同一个索引的键值对。使用链地址法，我们将数组的位置看作一个桶（bucket），每个桶中存储一个链表，链表中存储所有被映射到该索引的键值对。因此插入、删除和查找操作就是计算哈希值和链表操作的组合。

假定计算哈希值的时间复杂度为 $O(1)$ ，插入操作将数据放到链表头部即可，因此时间复杂度也是 $O(1)$ 。查找和删除操作需要遍历链表，为了时间复杂度是常量时间，需要确保每个桶的列表非常短，长度最坏情况下也是一个很小的常量。

开放地址法对插入和查找很友好，但是删除操作比较麻烦，不过好在相当多的应用中并不需要删除操作。开放地址法的核心思想是当发生哈希碰撞时，继续在数组中寻找下一个空闲位置来存储数据。常见的开放地址法有线性探测（linear probing）和双重哈希（double hashing）等。

线性探测就是顺序向后查找，直到找到一个空闲位置。假定键 key 的哈希值为 $h(key)$ ，如果位置 $h(key)$ 已经被占用，我们就检查位置 $h(key) + 1$ ，如果仍然被占用，就继续检查 $h(key) + 2$ ，以此类推，直到找到一个空闲位置。

双重哈希使用两个哈希函数，第一个哈希函数 $h_1$ 用于计算初始位置，第二个哈希函数 $h_2$ 用于计算步长。当发生哈希碰撞时，我们使用第二个哈希函数来计算下一个位置。具体来说，如果位置 $h_1(key)$ 已经被占用，我们就检查位置 $h_1(key) + h_2(key)$ ，如果仍然被占用，就继续检查 $h_1(key) + 2 \cdot h_2(key)$ ，以此类推，直到找到一个空闲位置。

开放地址法的性能分析稍微困难一些，直观地看如果哈希表比较满的话性能会变差，如果哈希函数不足够好，碰撞很多也会导致性能比较差。如果选择合适的哈希表大小和哈希函数，开放地址法的平均时间复杂度也是 $O(1)$ 。

装载因子

装载因子（load factor）是哈希表中一个重要的概念，定义是 $\alpha = \frac{n}{m}$ ，其中 $n$ 是哈希表中存储的键值对的数量， $m$ 是哈希表的大小（即数组的长度）。装载因子反映了哈希表的使用程度，较高的装载因子可能会导致更多的哈希碰撞，从而降低性能。

对于链地址法，装载因子 $\alpha$ 表示平均每个桶中的元素数量。因此，链地址法的平均时间复杂度为 $O(1 + \alpha)$ ，也可以写作 $O(\lceil \alpha \rceil)$ 。为了让这些操作是常量时间复杂度，那么需要保证 $\alpha=O(1)$ 。

对于开放地址法，装载因子是 $\alpha$ ，那么没有被占用的桶的比例是 $1-\alpha$ ，假定两次寻址之间没有关联，那么找到没有被占用的桶的过程是几何分布的，平均需要 $O(\frac{1}{1-\alpha})$ 的时间复杂度。对于不大的 $\alpha$ ，比如 70%，时间复杂度也是 $O(1)$ 的。对于线性探测来说，会占用连续的桶，操作更慢，理想情况下时间复杂度是 $\frac{1}{(1-\alpha)^2}$ ，这就要求 $\alpha$ 更小。这个结论在 Knuth 的巨著（Volume 3）中有详细的分析。

实现

参考 HashTable.h。

Bloom Filter

Bloom Filter 是一个和哈希表相关的数据结构，用于测试一个元素是否在一个集合中。Bloom Filter 支持的操作有插入和查询，但不支持删除。Bloom Filter 查询的结果不像是哈希表这样存储的元素本身，而是返回 yes/no，表示要查询的元素是否在集合中。Bloom Filter 的查询结果可能是误报（false positive），即可能会错误地报告一个元素在集合中，但不会错误地报告一个元素不在集合中，换句话说，它说一个元素在，有可能不在，但是它说不在，那么一定不在。

相比传统的哈希表，Bloom Filter 的空间效率更高，通常 8 bits 就可以存储一个元素的信息。Bloom Filter 能够保证对任意数据集的插入和查询操作都是常量复杂度。劣势也很明显，不能返回对象本身，不能删除元素（准确的说相当复杂），并且存在误报的可能性。

Bloom Filter 维护着 $n$ 个 bits 的数组，初始时所有 bits 都被设置为 0。Bloom Filter 使用 $m$ 个独立的哈希函数 $h_1, h_2, \ldots, h_m$ ，每个哈希函数将全集 $U$ 中的元素映射到 $[0, n-1]$ 的一个索引上。一般而言， $m$ 与 $n$ 成正比。

下面是插入操作的伪代码

for i in [1, m]:
    index = h_i(key)
    bits[index] = 1

查询操作需要所有位置上都是 1 才返回 yes，否则返回 no。下面是查询操作的伪代码

for i in [1, m]:
    index = h_i(key)
    if bits[index] == 0:
        return no
return yes

下面分析为什么会有误报。假定我们的 $m=3$ ，插入了三个元素 $k_1, k_2, k_3$ ，它们被哈希函数映射到 $a_1, a_2, a_3$ ， $b_1, b_2, b_3$ ， $c_1, c_2, c_3$ ，那么对应的 bits 数组中的位置都会被设置为 1。假定我们查询一个元素 $k$ ，它与 $k_1, k_2, k_3$ 都不相等，没有被插入过，但是它被哈希函数映射到 $a_1, b_2, c_3$ ，这三个位置上都是 1，那么 Bloom Filter 就会错误地报告 $k$ 在集合中。

直觉上看，增加 $n$ 能缓解上面说的问题，减少误报率，但是增加了空间。如何平衡二者呢？下面分析这个问题。

假定 $n$ 个 bits 存储集合 $S$ ，那么平均每个 key 需要 $b = \frac{n}{|S|}$ 个 bits。

这里假定对于 $k\in U$ ，每一个哈希函数 $h_i(k)$ 都是独立且均匀分布的。均匀分布意味着每个哈希函数 $h_i$ 将元素 $k$ 映射到 $[0, n-1]$ 中的每个索引的概率都是 $\frac{1}{n}$ 。独立性意味着对于不同的哈希函数 $h_i$ 和 $h_j$ ，它们的映射结果是相互独立的，那么 $h_i(k)=p,h_j(k)=q$ 的概率是 $\frac{1}{n^2}$ 。

基于上面的假设，每一个 bit 被设置为 1 的概率是 $1 - (1 - \frac{1}{n})^{m|S|}$ 这个公式比较容易懂，首先计算不被设置为 1 的概率，也就是 $1-\frac{1}{n}$ ，然后 $m|S|$ 是总的哈希函数调用次数。最后用 1 减去不被设置为 1 的概率就得到了被设置为 1 的概率。

当 $x$ 比较小的时候，那么 $e^x$ 是 $1+x$ 的好的近似，因此上面的概率可以近似为 $1 - e^{-\frac{m|S|}{n}}$ 这里 $x=-\frac{1}{n}$ ，当 $n$ 比较大的时候， $x$ 就比较小了。

前面定义了 $b=\frac{n}{|S|}$ ，因此上面的概率也可以写成 $1 - e^{-\frac{m}{b}}$ 那么误报的概率是 $\left(1 - e^{-\frac{m}{b}}\right)^m$ 当 $b\to\infty$ 的时候， $\frac{m}{b}\to 0$ ，因此 $e^{-\frac{m}{b}}\to 1$ ，所以误报率趋近于 0。反之， $b$ 很小的时候，误报率很大。比如 $b=m=1$ ，那么误报率是 $\left(1 - e^{-1}\right)^1 \approx 0.63$ ，也就是说有 63% 的概率会误报。

下面分析如何选择 $m$ 和 $b$ 来最小化误报率。令 $P=(1-e^{-\frac{m}{b}})^m$ ，两边取对数，得到 $\ln P = m \ln (1 - e^{-\frac{m}{b}})$ 假定 $b$ 是一个常数，那么 $P$ 是 $m$ 的函数。令 $x=e^{-m/b}$ ，那么 $m=-b\ln x$ ，因此上面的式子可以写成 $\ln P = -b \ln x \ln (1-x)$ 根据对称性，交换 $x$ 和 $1-x$ 不会改变 $\ln P$ 的值，因此 $x$ 和 $1-x$ 都是 $\ln P$ 的极值点。那么 $x=1-x$ ，也就是 $x=\frac{1}{2}$ 是 $\ln P$ 的极值点。也就是说当 $e^{-m/b}=\frac{1}{2}$ 的时候，误报率最小。解出 $m$ 的值，得到 $m =(\ln 2)b$ 带入误报率的公式，得到最小的误报率是 $P = \left(1 - e^{-\ln 2}\right)^{(\ln 2) b} = \left(1 - \frac{1}{2}\right)^{(\ln 2) b} = \left(\frac{1}{2}\right)^{(\ln 2) b}$ 当 $b=8$ 的时候，误报率是 $\left(\frac{1}{2}\right)^{8\ln 2} \approx 0.02$ ，也就是说有 2% 的概率会误报。如果 $b=16$ 的时候，误报率是 $\left(\frac{1}{2}\right)^{16\ln 2} \approx 0.00046$ ，也就是说有 0.046% 的概率会误报。