⚠ 转载请注明出处：作者：ZobinHuang，更新日期：June 16 2022

本作品由 ZobinHuang 采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

链式哈希方法 (Hash With Chaining) 是一种用于解决哈希冲突的方法。如上图所示，我们定义一个集合$u$ (i.e. Universe)，它里面包括了所有可能的 Key 值，也即 Keyspace。在 $u$ 中，我们假设已经存在着 $n$ 个已经被存储在 Hash Table 中的 Key 值。我们还定义了一个哈希函数，各个 Key 值经过该哈希函数，将会被投影到 Hash Table 的一个 Slot 中，我们假设 Hash Table 中一共有 $m$ 个 Slot。每一个 Slot 实际上就是一个链表，对于发生 Hash Collision 的 Key，它们将被组织成链表的形式。

性能分析内容与分析思路

hash_performace_analyse_method

分析内容

我们为什么部署 Hash 系统的很重要的原因是:

Hash 理论上将能够占用更小的内存用于存储数据;
Hash 理论上能够带来常数时间的搜索性能，这于直接使用搜索表进行存储相比，性能得到了很大的提升

这两点将成为我们下面讨论 Hash 系统性能的重点。其中，对于第二小点，我们下面进行分析的思路是:

首先我们基于一定的概率分布假设，讨论发生哈希碰撞的概率;
然后我们基于发生哈希碰撞的概率，可以推导得出 Hash Table 单个 Slot 下挂链表的平均长度;
基于 Hash Table 单个 Slot 下挂链表的平均长度，我们可以求出一次哈希搜索平均所需要的时间

分析思路

事实上，对 Hash 方法的性能进行分析，归根结底是在分析其随机性 (Randomness)。如上图所示，我把 Hash 系统涉及到的随机性分为两个部分:

Hash 系统面对的输入的所有可能性来自于 Keyspace $u$。$u$ 中各个 Key 值输入 Hash 系统的概率分布是具有随机性的，我称之为输入的随机性;
由于 Hash Function 的选取具有随机性，或者说 Hash Function 中的某些参数的概率分布具有一定的随机性。Hash 系统在部署的时候将会从一个 Hash Function 集合 $H$ 中随机抽取一个 Hash Function $h$。因此对于一个输入 Key 值，其经由 Hash Function 被投射到各个 Slot 的概率分布是具有随机性的。我称之为 Hash Function 的随机性

有的读者可能会对第二个小点存在一个疑问: 为什么需要随机抽取 Hash Function，而不是使用一个确定的 Hash Function 呢？答案可以总结为: 为了理论分析，下面给出具体原因:

首先，第一个原因是: 我们必须保证 Hash 系统的随机性。在不对输入 Key 值的分布进行假设的情况下，如果我们对一个已经确定的 (deterministic) Hash Function 展开研究，我们无法给出任何的概率性的保证，这不利于算法的分析。因此在不对输入 Key 值的分布进行假设的情况下，我们必须引入 Hash 系统的随机性，方法是在 Hash Function 中的一些参数上设置随机性，并且基于它们的随机性分析 Hash 系统的性能: 一个 Hash 系统的随机性越好，说明输入的 Key 值被分布到 Hash Table 各个 Slot 的个数就更加均匀，Hash 冲突的概率就更小，完成一次基于 Hash 查找的时间复杂度就更低，我们在下面将会看到基于一定假设的 Hash 系统的查找时间复杂度是常数时间复杂度。wikipedia_univeral_hashing

另一个原因是: 既然我们需要随机性，一个最简单粗暴的办法就是直接部署一个随机函数 (Completely Hash Function)，比如每来一个 Key 值，我们就抛一次 $\log_2m$-bits 的硬币，以决定将该 Key 值哈希到哪个 Slot 上去。这样做是否合理呢？实际上是不合理的，因为我们必须保证 Insert 一个 Key 的时候的哈希值和 Query 一个 Key 的时候的哈希值是相等的，这样 Hash Table 才有意义，这样就意味着我们必须存储针对各个 Key 值的哈希结果。因此，如果采用随机函数的方案，我们将花费一个很大的空间来存储各个 Key 值抛硬币的结果，这是得不偿失的。替代的方案是在不对输入 Key 值的分布进行假设的情况下，我们在 Hash Function 中设置一定的概率性参数，这些参数的概率分布使得我们可以像分析随机函数那样来分析这个 Hash 系统，尽管这些参数在部署 Hash 系统的那一刻开始就已经被确定，但是在部署之前我们仍然可以基于这些参数的概率特性来分析整个系统的性能。

在对 Hash 系统进行分析的时候，为了更加简单和合理，我们应该只保留两个随机性的其中一个。我们在下面将分别对这两个随机性进行讨论: 在 hash_performace_analyse_random_input 中看到对输入 Key 值随机性的讨论，在 hash_performace_analyse_hash_function 中看到对 Hash Function 随机性的讨论。

基于输入分布的性能分析

hash_performace_analyse_random_input

本小节主要参考自 mit6006hashing。

在本小节的分析中，我们将基于输入随机性进行讨论，换句话说，我们将忽略 Hash Function 的随机性，我们暂时假设 Hash Function 是一个确定的函数，转而我们对输入 Key 值的分布作出一定假设，使得基于一个已知 Hash Function 的系统满足如下性质:

均匀性 (Uniformity): 基于输入 Key 值的分布，从 Keyspace 中抽取出一个 Key，它经过 Hash Function 被哈希到 Hash Table 中的任意一个 Slot 的可能性是相等的 $\frac{1}{m}$，其中 $m$ 为 Hash Table 中 Slot 的个数;
独立性 (Independence): Keyspace 的每个 Key 值在 Hash Table 中的投射都是相互独立的，也就是说对于各个 Key 的投射都满足上述的均匀性，一个 Key 的哈希投射不会受到其他 Key 的哈希投射结果的影响

我们把上面的这两个针对输入 Key 值的分布的假设称为 Simple Uniform Hashing，其基本思路可以概括为下图，即通过控制输入 Key 值的概率分布来实现均匀 Hash。

哈希碰撞的概率

hash_collision_simple_uniform_hashing

我们知道，基于 Key 值的分布，我们抽取一个 Key 值 $k_1$ 使其落入某个 Slot 的概率为:

$\mathcal{P}_{k_1 \in n}[h(k_1)=S_j] = \frac{1}{m}$, $j = 0, 1, ..., m-1$

Keyspace 的每个 Key 值在 Hash Table 中的投射都是相互独立的，因此，我们可以得到，基于 Key 值的分布，Keyspace 中不同的两个 Key 值 $k_1$ 和 $k_2$ 被映射入同一个 Slot 的概率为:

$\mathcal{P}_{k_1 \ne k_2 \in n}[h(k_1) = h(k_2)] = \sum\limits_{j=0}^{m-1}\{ \mathcal{P}_{k_1 \in n}[h(k_1)=S_j] \cdot \mathcal{P}_{k_2 \in n}[h(k_2)=S_j]\} = m \cdot \frac{1}{m} \cdot \frac{1}{m} = \frac{1}{m}$

单 Slot 的 Hash Chain 长度期望

如果当前 Hash Table 中一共已经投射了 $n$ 个 Key，基于上述假设，这个 $n$ 个 Key 中的每个 Key 投射到各个 Slot 的概率分别为 $\frac{1}{m}$，并且各个 Key 值的投射是相互独立的。因此，对于一个 Slot 来说，它被投射的 Key 的个数的期望为:

$\alpha = n \cdot \frac{1}{m} = \frac{n}{m}$

我们把这个值称为 load factor。这个值可以被理解为在当前 Slot 上发生过的 Hash Collision 的次数的期望。

基于这个分析结果我们可以发现，如果 $m=\Theta(n)$，也即 Slot 个数的数量级和存在于 Hash Table 中的表项的个数的数量级相当，那么 $\alpha = \Theta(1)$，也即 Slot 上的链表的长度的期望将为常数值，也即 Hash Collision 发生的次数将为常数值。

查找操作的复杂度

对于一次查找操作，首先需要进行 $1$ 次哈希运算，然后在最坏情况下需要遍历对应 Slot 上的整条链表，因此查找操作的复杂度是:

$O(1+|\text{Chain}|) = O(1+\alpha)$

如果我们有 $m=\Theta(n)$，也即 $\alpha = \Theta(1)$，那么查找操作的复杂度将是 $O(1+|\text{Chain}|) = O(1+\alpha) = O(1)$，也即一次哈希查找操作将花费常数时间复杂度。

基于 Hash Function 分布的性能分析

hash_performace_analyse_hash_function

本小节主要参考自 mit6046hashing。

在 hash_performace_analyse_random_input 阐述的思路中，我们使用的思路是通过控制输入 Key 值的概率分布来实现均匀 Hash。这种对输入进行假设的分析方法实际上是为了我们在进行概率分析的时候方便所作出的假设。实际上，我们对一个系统进行分析的时候，我们不应该对输入做任何假设，特别是在算法分析中，我们更习惯于考虑最坏的系统输入的情况，来分析系统性能的下限。因此，在本节中，我们将把对随机性的讨论转移到 Hash Function 本身。把随机性转移到 Hash Function 的做法是：我们不再像 hash_performace_analyse_random_input 那样中假定一个固定的 Hash Function，而是从一个 Hash Function 集合 $\mathcal{H}$ 中随机选取一个 Hash Function $h$，以此将随机性引入系统分析中，如上图所示。

基于上述的说法，我们有两种办法以哈希分布的方式来对 Hash Function 展开分析，分别是 Universal Hashing (全域哈希) 和 Perfect Hashing (完全哈希)。这两者都不对输入展开假设，区别在于:

Universal Hashing 更加实用，因为它不对输入以及存在于哈希表中的键值有任何先验的假设，可以视为一种在线的哈希算法;
Perfect Hashing 展示了更加漂亮的理论结果，因为它虽然不对输入进行假设，但是它假设了存在于哈希表中的键值是固定不变的，可以视为一种离线的哈希算法

下面我们分别对他们展开进行分析。

Universal Hashing

Universality

对于 Hash Function 集合 $\mathcal{H}$，我们说集合 $\mathcal{H}$ 是 Universal (全域的)，当: 对于 $\mathcal{H}$ 中的任意 $h$，都必须保证发生哈希冲突的概率要小于等于 $\frac{1}{m}$。这个性质可以表达为下式:

$P_{h \in \mathcal{H}}\{h(k)=h(k')\} \leq \frac{1}{m}$, $\forall k,k' \in u$ ($k$ 和 $k'$ 是不同的 Key 值)

基于输入分布假设得到的的 equ_input_distribution_hash_collision 和基于哈希分布假设得到的 equ_universality 看起来似乎有相同的形式，但是实际上其背后的含义并不相同:

equ_input_distribution_hash_collision 是基于「对输入进行了均匀性和独立性的假设」得出来的;
equ_universality 是对具有 Universality 性质的 $\mathcal{H}$ 中的任意哈希函数 $h$ 所做出的假设，并没有对输入进行任何假设，也就是说对于任意输入 $k, k' \in u$ 成立

Universality 的探究范围可以总结为下图，实际上规定的是两个不同的 Key 值在同一个 Slot 上发生碰撞的概率。

基于 equ_universality 的定义，我们可以求出 Universal Hashing 的平均 Slot 长度为:

$E[\text{各个 Slot 的长度}] \le 1 + \alpha$ (p.s. $\alpha$ 是 load factor，在 equ_load_factor 中被定义)

证明:

假设哈希表中的 $m$ 个 Slots 已经装载了 $n$ 条键值表项。对于任意键值 $k_i$ 和 $k_j$，我们定义 indicator valuable:

$I_{i,j} = \begin{cases} 1, \text{i 和 j 映射在同一个 Slot 中} \\ \\ 0, \text{else}\end{cases}$

则我们可以求出:

\begin{aligned} E[k_i \text{所在的 Slot 的长度}] &= E[\sum\limits_{j \ne i} I_{i,j} + I_{i,i}] \\ &= \sum\limits_{j \ne i} E[I_{i,j}] + 1 \\ &= \sum\limits_{j \ne i} \mathcal{P}\{I_{i,j} = 1\} + 1 \\ &= \sum\limits_{j \ne i} \mathcal{P} \{ h(k_i) = h(k_j) \} + 1 \\ &\le \sum\limits_{j \ne i} \frac{1}{m} + 1 \\ &\le \frac{n}{m} + 1 \end{aligned}

Uniform Difference Property

对于 Universal Hashing，存在一个更加严格的定义: Uniform Difference Property，其含义是: 对于 $H$ 中的任意 $h$，都必须保证 $[h(k)-h(k')] \mod m$ 的结果在 $[m]$ 上均匀分布。Uniform Difference Property 的探究范围可以总结为下图，实际上规定的是在一个 Key 值映射到一个 Slot 的情况下，另一个 Key 值在其它 Slot 上发生映射的分布情况。

Pairwise Independence

Universal Hashing 更加严格的定义是 Pairwise Independence (或称为 Strong Universality)，其含义是:

$Pr[h(x)=z_1 \wedge h(y)=z_2] = (\frac{1}{m})^2$

Pairwise Independence 的探究范围可以总结为下图，实际上其规定的就是 2 个 Key 值分别映射到自己对应的 Slot 的概率分布情况。$(\frac{1}{m})^2$ 的概率结果形成的效果就好像这 2 个 Key 真的被进行了一次完美的随机 Hash 一样 (i.e. 实际上不是，只是概率分析结果)。

除了 Pairwise Independence，可以想象的是我们还会有 K-wise Independence，它们对 Hash Function Family 的要求就变得更加严格。它们形成的 $(\frac{1}{m})^k$ 的概率结果形成的效果就好像 k 个 Key 真的被进行了一次完美的随机 Hash 一样 (i.e. 实际上不是，只是概率分析结果)。

Perfect Hashing

基本介绍

和 Universal Hashing 不同，Perfect Hashing 假设映射到 Hash 表中的表项已经固定不变了，也即一种离线的哈希方法。可以理解为构建出来的哈希表仅仅有查询的功能，而不具有增删的功能。

Peferct Hashing 的目标是:

在很大概率下实现多项式时间的构建时间;
在最坏情况下，仍然实现 $O(1)$ 的搜索时间;
在最坏情况下，仍然实现 $O(n)$ 的存储复杂度;

构建过程

Perfect Hashing 的构建方法如下所示:

从上述介绍的 Universal Hash Family 中选取出一个哈希函数 $h_1: \{0, 1, ..., u-1\} \rightarrow \{0, 1, ..., m-1\}$，保证 $m=\Theta(n)$，然后将所有的 $n$ 个待映射的 key 值映射到 $h_1$ 对应的 $m$ 个哈希桶中去;
对于哈希函数 $h_1$ 对应的各个 Slot $j \in \{0, 1, ..., m-1\}$:
- 使用 $l_j$ 代表第 $j$ 个哈希桶中存储的表项的个数;
- 对于 Slot $j$，从 Universal Hash Family 中选取出一个哈希函数 $h_{2,j}: \{0, 1, ..., u-1\} \rightarrow \{0, 1, ..., m_j\}$，其中 $l_j^2 \le m_j \le O(l_j^2)$;
- 将第 1 步构建的 Hash with Chaining 的各个 Slot $j$ 上的链表替换为 $h_{2,j}$ 对应的哈希表;

综上，我们可以得到，整个结构占用的空间大小为:

$\text{Space} = O(n+\sum\limits_{j=0}^{m-1})$

为了保证整体结构的存储复杂度是 $O(n)$，使用 $l_j$ 代表哈希函数 $h_1$ 对应的哈希表中，第 $j$ 个哈希桶中存储的表项的个数，如果 $\sum\limits_{j=0}^{m-1}l_j^2 > cn$，则重复第 1 步 (p.s. $c$ 是一个人为设置的参数);

另外，我们可以得到整体的搜索时间为:

$\text{Search Time} = \underbrace{O(1)}_{\text{第一张哈希表} h_1 \text{对应的搜索时间}} \; + \; \underbrace{O(\text{第二张哈希表中最长的 Chain 的长度})}_{\text{第二张哈希表} h_{2,j} \text{对应的搜索时间}}$

为了保证搜索时间的复杂度为 $O(1)$，我们必须让第二张哈希表的搜索时间同样降低为 $O(1)$，因此在第二张哈希表中，当发生 Hash Collision，也即 $h_{2,j}(k_i) = h_{2,j}(k_{i'})$ 发生时，Perfect Hashing 需要对 $h_{2,j}$ 进行重新选择，并且重新哈希 $h_1$ 对应 Slot 中记录的 Key 值，直到没有冲突产生。

Zobin

哈希方法的概率性分析