Chapter 4: 哈希表

在上个章节我们了解到，在一个数组中作搜索通常效率感人。如果在一个未排序的数组里做搜索，则时间复杂度为$O(n)$。排序过的数组还好点，可以用二分搜索达成$O(\log(n))$的时间复杂度。

那么哈希与哈希表就是实现更高效增删改查操作的一次尝试。哈希表能够将增删改查的时间复杂度统统降至$O(1)$！我们管这种数据结构叫做字典 (Dictionary)。

哈希

要了解哈希表是如何做到这一点的，我们首先需要了解哈希函数。

假设你的大学学号是202599。如果想要在你的大学信息系统里找到你的有关信息，假设你的信息使用一个数组进行存储，那么你就直接找到第Array[202599]个项就可以了。非常轻松的一集。

但是我们总不能到处都使用像这样的数组实现方式来存储信息吧。假如有其他的数据只包含了50个学生的信息，那么显然使用数组就不是很合适了，因为会占用过大的存储空间。

现在我们的解决思路是将上万个学生的key (值)，缩减到一个较小的，大小为$m$的表格中。我们可以通过哈希函数来做到这一点：

$$h(k) = k \text{ mod } m$$

其中：

• $k$是key
• $m$是表格大小
• $h(k)$就是哈希值了，也就是我们用于存放值的新index。

要实现一个高效率的哈希表，你首先需要根据你要存储的数据按照特征设计一个合理的哈希函数。

例如我们要存储的数据是短英文字符串。例如"BEN"，我们就可以使用Base-128，aka ASCII来进行编码：

$$\text{"BEN"} = \text{'B'} \times 128^2 + \text{'E'} \times 128^1 + \times{'N'} \times 128^0$$

最后，将这个得到的数对$m$取模即可得到index。

除了选用合适的编码方式，我们还需要选取合理的$m$值来确保绝大多数的数据不会被分配到同一批index。
首先，尽量不要选取$2^n$ 作为m的值，例如1024。这样的话你的哈希值基本就是key的后几位信息。

我们一般选择质数 作为m的值，并且这个质数不要贴近任何$2^n$。这种数字分配出来的哈希值是比较平均的。

就像我们刚才所说的，我们可以使用Base-128来计算：

$$\text{Key} = c_0 \cdot R^{n-1} + c_1 \cdot R^{n-2} + ... + c_{n-1} \cdot R^0$$

其中$R$代表你要用于计算的根值。在这里由于我们使用Base-128，因此$R = 128$
别忘了到最后还要选一个合适的m值，来进行%m。

用ASCII编码的话，我们可以很轻松地得出这些字母对应的编码值：'C'(67), 'A'(65), 'T'(84). $R = 128$, $m = 100$

$$h = [67 \cdot 128^2 + 65 \cdot 128^1 + 84 \cdot 128^0] (\text{mod } 100)$$

哈希表

你可以想象一个基础的哈希表由很多小单元格组成。每个单元格都有一个按顺序排列的唯一编号，同样每个单元格都可以存入信息。

哈希冲突

那么我们这样做的目的是什么？为啥要对选用的m值这么讲究？这样做的目的是尽可能避免哈希值冲突，导致哈希表使用不平均，或者解决数据丢失问题。

如果我们没有使用进阶解决方案（例如一会会讲到的链式哈希和开放寻址），则如果两个值被分配到了一样的哈希值，则这两个值就产生了冲突。你应该存入哪个值呢？

如果我们选用了一些进阶解决方案，则如果选用的m值没办法把所有的数据尽可能平均地分配哈希值，那么到时候在哈希表中，数据就更倾向于在这些地方“堆积”起来，形成团簇。我们管这个现象叫做Clusteing。

换句话说，就是：

$$k_1 \neq k_2 \text{ but } h(k_1) = h(k_2)$$

Clustering会影响到哈希表的性能，因此我们需要尽可能将哈希值平均地分配给不同的key。好在我们有的是手段来解决这个问题！

链式哈希（开放哈希）

中文译名可能不准确，总之链式哈希 叫做Chaining，外号Open Hashing。

链式哈希的解决方案是，与其将值直接存入哈希表的单元格中，我们在这些位置内存入一个指向链表的指针。例如：

• "Ben"通过哈希函数算出来的哈希值是5，则在哈希表中找到第五个格子，插入到第五个格子指针所指的链表中。
• "Jerry"同样被分配到了一样的哈希值5，于是我们就在对应链表后面（Ben所在的链表）后方直接插入进去。

这样一来，即使不同的值分配到了一样的位置，我们也可以将它们的值存下来，查询的时候也可以按照哈希函数追寻到他们的位置。

链式哈希做法的性能如何？

我们引入一个概念叫做负载系数 (Load Factor, $\alpha$) 。负载系数衡量的是在链式哈希系统内，这些链表的平均长度。也就是:

$$\alpha = \frac{n}{m}$$，其中：

• $\alpha$为负载系数
• $n$为哈希表中存入的值的数量
• $m$为哈希表单元格的总数。

对于这样一个系统，插入值的复杂度始终是$O(1)$。你只要算出哈希值，找到链表，头插即可。
搜索的性能情况要分情况讨论：

• 完成一次成功搜索，即你在哈希表内找到了你想要的值，则你需要平均遍历$1 + \frac{\alpha}{2}$个节点。
• 完成一次未成功搜索，也就是元素不在哈希表内，你就需要遍历$\alpha$个节点。

结论是，只要哈希表的尺寸没有太小，则这样结构的哈希表的性能还是挺不赖的。不过对于对存储有要求的使用场景来说，要注意实现链表的指针也是要占空间的。

开放寻址（封闭哈希）

开放寻址，aka Open Addressing，外号Closed Hashing，是另一种解决冲突问题的手段。

这种方法与其像链式哈希那样使用链表，开放寻址不使用指针，不使用链表，就使用哈希表的单元格来存储数据。让开放寻址能够解决碰撞问题的关键是，我们可以使用不同的方法来规划当碰撞出现后，后来的元素去存到哪里。

线性探测

我们叫Linear Probing，是一个非常简单的方案：

如果元素即将存入的格子$j$已经被占用了，则我们就直接往下找它的下一个格子$j+1$，再接着是$j+2$，如果到了哈希表的最低端就从头开始继续找，直到我们找到了空格子来存下数据。

这种方法带来的一个关键问题就是会形成团簇，这里叫做Primary Clustering。如果在一个位置发生Probing的次数越多，那么连续被占满的格子就会越来越多。在这种情况下如果我们碰到了一个大长串，则我们就只能从那个位置一直往下遍历，直到我们走到了这串团簇的尾部才能将数据存下。这无疑是影响性能的。

二次探测

也就是Quadratic Probing。

这个方案的相比线性探测的区别在于，预期向下按照+1的步长寻找空位，二次探测则是按照这样的顺序寻找空位：

如果$j$已被填满，则首先找到$j+1^2$，然后是$j+2^2$, $j+3^2$，触底后从头开始，直到我们找到了合适的位置存下数据。

但是这样的方案仍然会带来团簇，只不过这些团簇没有聚集在一起，而是按照二次距离分布在各处。我们叫做Secondary Clustering。由于每个元素向下遍历的步长是一样的（按照平方增长次序），所以我们还是很有可能形成团簇的。

又聪明的人就要问了，啊既然我们用二次的步长向下找空位，到头了就从头再找，我们会不会碰见“遍历顺序完美跳过空格子的现象”啊？答案是会。所以我们会将$m$的值定为质数。这样如果表格至少有一半是空的，则二次探测法保证能找到一个空槽位。

双重哈希

双重哈希 (Double Hashing) 不同于一二次探测法。它的做法是使用两个不同的哈希函数来计算元素将要存入的位置：

$$\text{Next slot} = (h_1(k) + i \times h_2(k)) \text{ mod }m$$

程序会先按照$h_1(k)$使用第一个哈希函数计算哈希值。如果碰撞出现，则我们从1往后开始遍历i的值，使用$h_2(k)$计算出一个哈希值，然后累加到$h_1(k)$上计算出新的哈希值，由此循环。

这样做的是好处是如果两个值发生了碰撞，那么这两个值会按照不同的规律向下寻找空位，因为对于$h_2(k)$来说，这两个元素又很小的概率使用完全一样的遍历逻辑。

双重哈希有一个小要求就是，$h_2(k) \neq 0$。因为如果在这种情况下，序列就变成这个样子：

$$h(k, i) = h_1(k) \text{ mod }m$$

那这就说明在发生碰撞后，我们实际上没有往下去寻找空位。

另外$h_2(k)$需要与$m$保持质数关系。如果$gcd(h_2(k), m) = d > 1$，则遍历序列向下寻找空格的范围将不会是整个哈希表。

例如我们设$m = 10$，$h_2(k) = 2$，则遍历序列实际上就只会往下按照0, 2, 4, 6, 8的规律进行遍历。这意味着有部分格子永远不会被遍历到，所以即便空格子存在，按照算法的缘由你不可能遍历到它们。

反过来如果$gcd(h_2(k), m) = 1$，那么这就说明遍历序列会在重复之前遍历哈希表中所有m个格子。

来做个题。

不难得出哈希函数即是$h_1(k) = k (\text{mod } 10)$

Linear Probing

1. 插入12：
   • $12 \text{ mod } 10 = 2$
   • 由于第二个单元格为空，直接插入：[2] = 12
2. 插入22:
   • $22 \text{ mod } 10 = 2$
   • 由于第二个单元格不为空，则调用probing序列：$(2 + 1) \text{ mod } 10 = 3$
   • 由于第三个单元格为空，直接存入: [3] = 22
3. 插入32:
   • $32 \text{ mod } 10 = 2$
   • 直接调用Probing序列：$(2 + 1) \text{ mod } 10 = 3$, $(2 + 2) \text{ mod } 10 = 4$
   • 存入第四个单元格: [4] = 32

像这样[2] - [4]形成的连成片的值，我们管这个叫Cluster，也就是团簇。

Quadratic Probing

1. 插入12：
   • $12 \text{ mod } 10 = 2$
   • 由于第二个单元格为空，直接插入：[2] = 12
2. 插入22:
   • $22 \text{ mod } 10 = 2$
   • 由于第二个单元格不为空，则调用probing序列：$(2 + 1^2) \text{ mod } 10 = 3$
   • 由于第三个单元格为空，直接存入: [3] = 22
3. 插入32:
   • $32 \text{ mod } 10 = 2$
   • 直接调用Probing序列：$(2 + 1^2) \text{ mod } 10 = 3$, $(2 + 2^2) \text{ mod } 10 = 6$
   • 存入第六个单元格: [6] = 32

Double Hashing

在计算之前，我们需要先确定好哈希函数$h_1(k)$和$h_2(k)$都是什么。由于我们已经定义好了$h_1(k)$，再定义一个$h_2(k)$也不难：

$$h_2(k) = 7 - (k (\text{mod } 7))$$

注意我们选的$h_2(k)$得出的值不能为零。

1. 插入12：
   • $12 \text{ mod } 10 = 2$
   • 由于第二个单元格为空，直接插入：[2] = 12
2. 插入22:
   • $22 \text{ mod } 10 = 2$
   • 由于第二个单元格不为空，则调用probing序列：$h_2(22) = 7 - (22 \text{ mod } 7) = 6$
   • $i = 1: (2 + 1 \cdot 6) \text{mod }10 = 8$，存入第八个单元格: [8] = 22
3. 插入32:
   • $32 \text{ mod } 10 = 2$
   • 直接调用Probing序列：$h_2(32) = 7 - (32 \text{ mod } 7) = 7 - 4 = 3$,
   • $i = 1: (2 + 1 \cdot 3) \text{mod } 5$，存入第五个单元格: [5] = 32

删除元素

对于开放寻址来讲，需要关注一下我们如何删除哈希表内的元素。

假如我们在进行添加元素时，经过了这样一个步骤：

1. 于槽位5插入A
2. B同样定位于槽位5，于是按照线性探测规则插入于槽位6
3. C同理与A冲突，则在7插入内容

那么如果我们要删除元素B该怎么办？

首先我们直接删除槽位6，将内容改写为NULL，那么C就没有办法按照既定的序列被访问到了。如果我们想要寻找C，我们会先根据哈希函数算到槽位5，然后根据probing序列找到槽位6。但由于此时槽位6是空的，所以我们认为C不在哈希表里，而实际上我们想要的东西就在槽位7。

于是我们采用一个“墓碑”系统：

删除B的时候，将槽位6标为“已删除”，或者DELETED。这样一来当我们的算法按照既定序列访问到槽位6的时候，你就知道后面还是有元素的，于是程序会按照序列继续找下去，直到我们找到想要的元素。

当然墓碑可以被改写。如果插入元素时遇见了DELETED，你可以将它改写为你要存入的元素。

哈希表的性能

对于开放寻址哈希表来讲，负载系数($\alpha$)的值必须始终$< 1$。因为超出100%就说明塞不下了。

一般来讲，我们希望将负载系数的值约束在$< 0.5$之内。如果哈希表太满了($\alpha > 0.5$)，则我们就要创建一张新的，尺寸取原来哈希表两倍附近的质数作为新的表大小，重新计算所有元素的哈希值，然后重新插入这张新表。这个过程叫做Rehashing。

不同Probing方式的性能也不一样：

但是在合理的负载系数下，这些操作的时间复杂度都是$O(1)$。

首先我们重温一下二次探测法的一些规则：

1. 对于二次探测法来讲，$m$必须是质数。
2. 为保持性能，我们要求$\alpha < 0.5$。

因为我们选择的值$m = 100$不为质数，这就导致二次探测过程中无法保证一定能找到可用的空格子。因此这不合适。