哈希

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

哈希表

哈希表（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），即可能会错误地报告一个元素在集合中，但不会错误地报告一个元素不在集合中。