CMU 15445 学习笔记—5 Hash Table

前面的几篇文章已经将磁盘管理和内存 buffer pool 管理的内容都介绍完了，接下来继续向上一层，来介绍关于 access method 的内容。

access method 主要是介绍一些数据结构，例如 Hash Table 和 Tree。这些数据结构可以用来做表的索引，以及一些在 sql 计算时的临时数据结构。

在设计和使用这些数据结构时，需要注意两个问题，一是数据的组织，怎样将数据组织在内存或者磁盘中，并且能够高效的访问；二是数据结构的并发访问问题，需要保证其在多线程环境下的数据安全。

今天先来看一下在数据库里面频繁被使用，以及数据结构中也会经常涉及到的哈希表。

Hash Table 概念

Hash Table 是一个无序的 key 到 value 的映射实现，它使用一个哈希函数计算数据存储到数组中（槽位）的位置，并且平均情况下，能够在 O(1) 的时间内访问元素。

如下图所示，我们通过一个 hash 函数，计算 key 在数组中中的下标，然后 key 对应了具体的 value。当查找数据时，也需要计算哈希值，然后定位到 key 所在的位置进行取值。

Hash 函数

从前面的描述中可以看到，哈希函数在 Hash Table 中的作用至关重要。

哈希函数可以将任意类型的 key 转换为一个代表这个 key 的整数，在理想的情况下，我们希望任意不同的 key 经过哈希函数计算出来的值都是不同的，但在实际的哈希函数实现中，这几乎是不太可能的。

如果不同的 key 通过哈希函数计算出来的值是一样的，这种情况叫做哈希冲突（conflict），又叫哈希碰撞（collision）。

一般来说，计算哈希的速度越快，哈希冲突的概率越大，反之则越低，这就需要在实际设计时进行权衡。

数据库中常见的哈希函数实现有下列这几种：

• crc64：https://create.stephan-brumme.com/crc32/
• MurmurHash：https://github.com/aappleby/smhasher
• Google CityHash：https://github.com/google/cityhash
• Facebook XXHash：http://cyan4973.github.io/xxHash/
• Google FarmHash：https://github.com/google/farmhash

Static Hash Scheme

接下来了解一下几种静态哈希的实现方式，所谓静态，一般是指哈希表的容量大小是固定的，所以能够存储数据的上限也是确定的，实际使用并不多，可以做参考。

Linear Probe Hash

线性探测（Linear Probe）是一种比较直观简洁的 Hash Table 实现方式了。

其基本思路是如果映射之后的 key 存储的位置已经被占用了，那么它会依次遍历数组，直到找到一个空闲的位置插入数据。

如下，新插入的数据 E 通过计算后，其位置在 A 的位置。

但是 A 处已经有数据了，此时发生了冲突，所以会向后遍历，然后找到 D 之后的空闲位置插入。

删除的逻辑比较类似，也是通过哈希函数计算 key 的位置，然后找到对应的数据并删除。如果 key 并不在原来的位置上，那么需要像插入一样遍历，直到找到目标 key。

删除一般有两种做法，一是直接在删除的位置设置一个墓碑值，表示其已被删除，二是移动其他的元素来填充删除的位置，这种方式并不常用。

重复 key 哈希表中对于重复的 key 的处理方式一般有两种，一是通过一个 value 链表的方式，将同一个 key 的多个元素串联起来。

这种方式比较简单直观，另一种方式是重复存储，把每个 key 都当做是独立的，插入方式和上面描述的完全一致。

Robin Hood Hash

robin hood 哈希类似于线性探测，并有一定的改进。

它会记录每个 key 与其原始 hash 映射的位置的距离，例如下图中的 A，因为插入前没有任何数据，不存在哈希冲突，所以 A 记录的距离是 0。

如果此时插入数据 C，如果 C 映射的位置也是 A，这样就产生了哈希冲突，于是向下探测一位，将 C 插到 A 之后的位置，这时候 C 与其原始映射位置的距离就是 1。

当又有新的 key 插入时，如果产生了冲突，那么继续向后探测，并且比较映射距离的值，如果新插入的 key 的距离大于该位置的值，则将新的 key 插入。

例如上面的这个例子，如果新插入的 E 映射到了 A 的位置，此时 E 的距离是 0，和 A 的距离相等，继续向下，此时 E 的距离是 1，和 C 相等，又继续，此时 E 变为 2，大于了 D 的距离 1，于是将 E 插入到 D 的位置，并且将 D 挪到到下一个空闲的位置。

Cuckoo Hash

cuckoo hash 使用多个哈希表，并且每个哈希表使用一个不同 seed （随机种子）的哈希函数。当插入数据时，对 key 轮流用每个哈希函数都计算哈希值，如果对应的哈希表有空闲空间，则直接插入。

例如下面的例子，使用了两个哈希表，插入 key A 的时候，计算两个哈希值，并且查询到第一个哈希表有空闲，则直接将数据插入到哈希表 1 中。

如果此时在插入一条数据 B，如果在哈希表 1 中有冲突，但是在哈希表 2 中没有冲突，则将数据插入到哈希表 2 中。

如果此时再插入一个 key C，经过哈希函数计算后，发现它和两个哈希表都有冲突。

这时候需要选择一个哈希表，将其中的 key 先拿出来，腾一个位置给 C，例如可以将 C 插入到 A 的位置。 然后对 A 再计算哈希值，如果 A 在哈希表 2 中没有冲突，则直接将 A 插入到哈希表 2 中。

cuckoo hash 在 Github 上也有对应的一些实现：https://github.com/efficient/libcuckoo

Dynamic Hash Scheme

前面提到的这几种哈希表的实现方式，都可以认为是静态的，即哈希表中能存储多少数据，是一开始就确定下来的，并不会涉及到扩容。

但实际环境中，我们大多数时候都希望哈希表是可以随着数据量的增长而扩张的，下面再介绍几种更常用的，可以自动动态扩容的哈希表实现。

Chained Hash

链式哈希将一个哈希表通过多个 bucket 来维护，如果出现了哈希冲突，则将相同的 key 放到同一个 bucket 中，如果 bucket 超过了规定的容量，则以链表串联起一个新的 bucket。

每个 bucket 一般会有一个指针，标识其位置，当一个 key 经过 hash 之后，可以通过这个指针找到它所属的 bucket。

Extendible Hash

extendible hash（可扩展哈希）和 chained hash 比较类似，都使用到了bucket 这个概念，同时也会有一个执行 bucket 的指针数组。

与之不同的是，extendible hash 将 key 计算哈希值后，会将其值转换为一个二进制表示，然后它会维护一个 global counter，记录定位到 bucket 指针数组，需要取 key 的二进制的多少位；每个 bucket 也有一个 counter，记为 local counter，表示的是定位到该 bucket 需要二进制的多少位。

例如上面的例子，第一个 bucket 的 counter 是 1 ，当 key 定位到该 bucket 的时候，需要取 key 的前一位。而 bucket 2 和 3 的 counter 都是 2，需要取二进制的前两位。

如果需要查询数据，先对 key 计算哈希值，例如下图中的 A，计算其哈希值后，global counter 是 2，所以只需要取前两位即可，然后通过 bucket 的指针获取到 bucket 的位置，遍历其中的数据进行查找。

如果需要新插入数据，则和查找的过程类似，同样计算哈希值，然后找到对应的 bucket，将数据放到 bucket 的空闲位置即可。

如果对应的 bucket 没有空闲的位置了，这时候需要进行 split 分裂操作。

首先将 global counter 的值增加 1，然后新建一个 bucket，将旧的对应的那个 bucket 的 counter 也增加 1，并且让新的 bucket 的 counter 等于这个值。然后重新通过这个 key 的二进制位来移动旧的 bucket 中的数据。

例如下面的例子，需要插入 key C，但是它所映射的 bucket 已经满了。

此时将 global counter 增加为 3，并且新增一个 bucket，counter 为旧的值加一，也为 3。然后将旧的那个 bucket 按照新的进制位重新存放，此时 bucket 中就有空闲的位置了。

更详细内容可以参考： https://zhuanlan.zhihu.com/p/375039823

Linear Hash

前面提到的 extendible hash 在分裂的时候，需要扩展 bucket 指针数组（又叫 slot array），这时候一般需要对哈希表加全局锁，以防止并发读写冲突。但是这样锁的粒度较大，容易造成哈希表的读写瓶颈。

另一种 linear hash 会维护一个分裂指针 split pointer，当有任意的 bucket 分裂时，split pointer 指向的 bucket 也会分裂。这种方式介绍不多，实际使用应该也较少，就不详细介绍了。

Conclusion

哈希表是一个高效的数据结构，大多时候能够在 O(1) 的情况下插入和查询数据，在数据库系统中，有很多地方都使用到了哈希表，例如前面提到的 page table，page directory，以及执行 sql 查询时一些用于 join 的临时数据结构。

但是哈希表的应用场景也有限，因为它存储的所有 key 都是无序的，这样虽然适合点查，但是无法进行范围扫描，在更加通用的场景下，数据库中的表索引使用最广泛的还是 B+ 树。