本文首发于“百度架构师”公众号：https://mp.weixin.qq.com/s/oeuExiW3DYQnBG8HvDgBAg
1 背景
哈希表是一种查找性能非常优异的数据结构，它在计算机系统中存在着广泛的应用。尽管哈希表理论上的查找时间复杂度是 O(1)，但不同的哈希表在实现上仍然存在巨大的性能差异，因而工程师们对更优秀哈希数据结构的探索也从未停止。
1.1 哈希表设计的核心
从计算机理论上来说，哈希表就是一个可以通过哈希函数将 Key 映射到 Value 存储位置的数据结构。那么哈希表设计的核心就是两点：
- 怎样提升将 Key 映射到 Value 存储位置的效率？
- 怎样降低存储数据结构的空间开销？
由于存储空间开销也是设计时的一个核心控制点，在受限于有限的空间情况下，哈希函数的映射算法就存在着非常高的概率将不同的 Key 映射到同一个存储位置，也就是哈希冲突。大部分哈希表设计的区别，就在于它如何处理哈希冲突。
当遇到哈希冲突时，有几种常见的解决方案：开放寻址法、拉链法、二次哈希法。但是下面我们介绍两种有趣的、不常见的解决思路，并且引出一个我们新的实现方案 - B16 哈希表。
2 规避哈希冲突
传统哈希表对哈希冲突的处理会增加额外的分支跳转和内存访问，这会让流水线式的 CPU 指令处理效率变差。那么肯定就有人考虑，怎么能完全规避哈希冲突？所以就有了这样一种函数，那就是完美哈希函数（perfect hash function）。
完美哈希函数可以将一个 Key 集合无冲突地映射到一个整数集合中。如果这个目标整数集合的大小与输入集合相同，那么它可以被称为最小完美哈希函数。
完美哈希函数的设计往往非常精巧。例如 CMPH （http://cmph.sourceforge.net/）函数库提供的 CDZ 完美哈希函数，利用了数学上的无环随机 3-部超图概念。CDZ 通过 3 个不同的 Hash 函数将每个 Key 随机映射到 3-部超图的一个超边，如果该超图通过无环检测，再将每个 Key 映射到超图的一个顶点上，然后通过一个精心设计的与超图顶点数相同的辅助数组取得 Key 最终对应的存储下标。
完美哈希函数听起来很优雅，但事实上也有着实用性上的一些缺陷：
- 完美哈希函数往往仅能作用在限定集合上，即所有可能的 Key 都属于一个超集，它无法处理没见过的 Key；
- 完美哈希函数的构造有一定的复杂度，而且存在失败的概率；
- 完美哈希函数与密码学上的哈希函数不同，它往往不是一个简单的数学函数，而是数据结构+算法组成的一个功能函数，它也有存储空间开销、访问开销和额外的分支跳转开销；
但是在指定的场景下，例如只读的场景、集合确定的场景（例如：汉字集合），完美哈希函数可能会取得非常好的表现。
3 利用哈希冲突
即便不使用完美哈希函数，很多哈希表也会刻意控制哈希冲突的概率。最简单的办法是通过控制 Load Factor 控制哈希表的空间开销，使哈希表的桶数组保留足够的空洞以容纳新增的 Key。Load Factor 像是控制哈希表效率的一个超参数，一般来说，Load Factor 越小，空间浪费越大，哈希表性能也越好。
但近年来一些新技术的出现让我们看到了解决哈希冲突的另一种可能，那就是充分利用哈希冲突。
3.1 SIMD 指令
SIMD 是单指令多数据流（Single Instruction Multiple Data）的缩写。这类指令可以使用一条指令操作多个数据，例如这些年非常火的 GPU，就是通过超大规模的 SIMD 计算引擎实现对神经网络计算的加速。
目前的主流 CPU 处理器已经有了丰富的 SIMD 指令集支持。例如大家可接触到的 X86 CPU 大部分都已经支持了 SSE4.2 和 AVX 指令集，ARM CPU 也有 Neon 指令集。但科学计算以外的大部分应用程序，对 SIMD 指令的应用还都不太充分。
3.2 F14 哈希表
Facebook 在 Folly 库中开源的 F14 哈希表有个非常精巧的设计，那就是将 Key 映射到块，然后在块里使用 SIMD 指令进行高效过滤。因为分块的数量比传统的分桶要更小，这相当于人为增加了哈希冲突，然后在块中用 SIMD 指令再解决冲突。具体的做法是这样的：
- 通过哈希函数对 Key 计算出两个哈希码：H1 和 H2, 其中 H1 用来确定 Key 映射到的块，H2 只有 8 bits，用来在块内进行过滤；
- 每个块里最多存放 14 个元素，块头有 16 个字节。块头的前 14 个字节，存放的是 14 个元素对应的 H2，第 15 字节是控制字节，主要记录该块里有多少个元素是从上一个块溢出的，第 16 字节是越界计数器，主要记录如果该块空间足够大，应该会被放置多少个元素。
- 在插入时，当 Key 映射到的块中 14 个位置还有空时，就直接插入；当块已经满时，就增加越界计数器，尝试插入下一个块中；
- 在查询时，通过待查找 Key 计算得到 H1 和 H2。通过 H1 对块数取模确定其所属的块后，首先读取块头，通过 SIMD 指令并行比较 H2 与 14 个元素的 H2s 是否相同。如果有相同的 H2，那么再比对 Key 是否相同以确定最终结果；否则根据块头的第 16 字节判断是否还需要比对下一个块。
F14 为了充分利用 SIMD 指令的并行度，在块内使用了 H2 这种 8 bits 的哈希值。因为一个 128 bits 宽度的 SIMD 指令可以进行最多 16 个 8 bits 整数的并行比较。虽然 8 bits 哈希值的理论冲突概率 1/256 并不低，但也相当于有 255/256 的可能性省去了逐个 Key 对比的开销，使哈希表能够容忍更高的冲突概率。
4 B16 哈希表
不考虑分块内部的设计，F14 本质上是一个开放寻址的哈希表。每个块头的第 15、16 字节被用于开放寻址的控制策略，只剩 14 个字节留给哈希码，也因而被命名为 F14。
那么我们考虑能不能从另一个角度出发，使用拉链法来组织分块。由于省去了控制信息，每个分块中可以放置 16 个元素，我们把它命名为 B16。
4.1 B16 哈希数据结构
图 1：B16 哈希表数据结构（3元素示例）
上图所示就是用每个分块 3 个元素展示的 B16 哈希表的数据结构。中间绿色的是常见的 BUCKET 数组，存放的是每个分桶中 CHUNK 拉链的头指针。右侧的每个 CHUNK 与 F14 相比，少了控制字节，多了指向下一个 CHUNK 的 next 指针。
B16 也是通过哈希函数对 Key 计算出两个哈希码：H1 和 H2。例如 “Lemon” 的两个哈希码是 0x24EB 和 0x24，使用 H1 的高位作为 H2 一般来说足够了。
在插入时，通过 H1 对桶大小取模计算 Key 所在的分桶，例如 "Lemon" 所在的分桶是 0x24EB mod 3 = 1。然后在 1 号分桶的分块拉链中找到第一个空位，将 Key 对应的 H2 和元素写入该分块。当分块拉链不存在，或者已经装满时，为拉链创建一个新的分块用于装载插入的元素。
在查找时，先通过 H1 找到对应的分桶拉链，然后对每个块进行基于 SIMD 指令的 H2 对比。将每个块的块头 16 字节加载到 128 bits 寄存器中，里面包含了 16 个 H2'，把 H2 也重复展开到 128 bits 寄存器中，通过 SIMD 指令进行 16 路同时比对。如果都不同，那就对比下一个块；如果存在相同的 H2，就继续对比对应元素的 Key 是否与查找的 Key 相同。直到遍历完整条拉链，或者找到对应的元素。
在删除时，首先查找到对应的元素，然后用块拉链最尾部的元素覆盖掉对应的元素即可。
当然，B16 哈希表每个块的元素个数可以根据 SIMD 指令的宽度进行灵活调整，例如使用 256 bits 宽度指令可以选择 32 元素的块大小。但影响哈希表性能的不仅仅是查找算法，内存访问的速度和连续性也非常重要。控制块大小在 16 以内在大多数情况下能充分利用 x86 CPU 的 cache line，是一个较优的选择。
普通的拉链式哈希表，拉链的每个节点都只有一个元素。B16 这种分块式拉链法，每个节点包含 16 个元素，这会造成很多空洞。为了使空洞尽可能的少，我们就必须增加哈希冲突的概率，也就是尽量地缩小 BUCKET 数组的大小。我们经过试验发现，当 Load Factor 在 11-13 之间时，B16 的整体性能表现最好。其实这也相当于把原来存在于 BUCKET 数组中的空洞，转移到了 CHUNK 拉链中，还省去了普通拉链式每个节点的 next 指针开销。
4.2 B16Compact 哈希数据结构
为了进一步压榨哈希表的存储空间，我们还设计了 B16 的只读紧凑数据结构，如下图所示：
图 2：B16Compact 哈希表数据结构（3元素示例）
B16Compact 对哈希表结构做了极致的压缩。
首先它省去了 CHUNK 中的 next 指针，把所有的 CHUNK 合并到了一个数组中，并且补上了所有的 CHUNK 空洞。例如【图 1】中 BUCKET[1] 的拉链中本来有 4 个元素，包含 Banana 和 Lemon，其中头两个元素被补到了【图 2】的 CHUNK[0] 中。以此类推，除 CHUNK 数组中最后一个 CHUNK 外，所有的 CHUNK 均是满的。
然后它省去了 BUCKET 中指向 CHUNK 拉链的指针，只保留了一个指向原拉链中第一个元素所在 CHUNK 的数组下标。例如【图 1】中 BUCKET[1] 的拉链第一个元素被补到了【图 2】的BUCKET[0] 中，那么新的 BUCKET[1] 中仅存储了 0 这个下标。
最后增加了一个 tail BUCKET，记录 CHUNK 数组中最后一个 CHUNK 的下标。
经过这样的处理以后，原来每个 BUCKET 拉链中的元素在新的数据结构中依然是连续的，每个 BUCKET 依然指向第一个包含其元素的 CHUNK 块，通过下一个 BUCKET 中的下标依然可以知道最后一个包含其元素的 CHUNK 块。不同的是，每个 CHUNK 块中可能会包含多个 BUCKET 拉链的元素。虽然可能要查找的 CHUNK 变多了，但由于每个 CHUNK 都可以通过 SIMD 指令进行快速筛选，对整体查找性能的影响相对较小。
这个只读哈希表只支持查找，查找的过程跟原来差异不大。以 Lemon 为例，首先通过 H1=24EB 找到对应的分桶 1，获得分桶对应拉链的起始 CHUNK 下标为 0，结束 CHUNK 下标为 1。使用与 B16 同样的算法在 CHUNK[0] 中查找，未找到 Lemon，然后继续查找 CHUNK[1]，找到对应的元素。
B16Compact 的理论额外存储开销可以通过下式算得：
其中，n 是只读哈希表的元素个数。
当 n 取 100 万，Load Factor 取 13 时，B16Compact 哈希表的理论额外存储开销是 9.23 bits/key，即存储每个 key 所支出的额外开销只有 1 个字节多一点。这几乎可以媲美一些最小完美哈希函数了，而且不会出现构建失败的情况。
B16Compact 数据结构仅包含两个数组，BUCKET 数组和 CHUNK 数组，也就意味着它的序列化和反序列化可以做到极简。由于 BUCKET 中存储的是数组下标，用户甚至不需要将哈希表整个加载到内存中，使用文件偏移即可进行基于外存的哈希查找，对于巨大的哈希表来说可以有效节省内存。
5 实验
5.1 实验设定
实验使用的哈希表的 Key 和 Value 类型均取 uint64_t，Key、Value 对的输入数组由随机数生成器预先生成。哈希表均使用元素个数进行初始化，即插入过程中不需要再 rehash。
- 插入性能：通过 N 个元素的逐一插入总耗时除以 N 获得，单位是 ns/key；
- 查询性能：通过对随机的 Key 查询 20 万次（全命中） + 对随机的 Value 查询 20 万次（有可能不命中）获得总耗时除以 40 万获得，单位是 ns/key；
- 存储空间：通过总分配空间除以哈希表大小获得，单位是 bytes/key。对于总分配空间来说，F14 和 B16 均有对应的接口函数可直接获取，unordered_map 通过以下公式获取：
// 拉链节点总大小
umap.size() * (sizeof(uint64_t) + sizeof(std::pair<uint64_t, uint64_t>) + sizeof (void*))
// bucket 总大小
+ umap.bucket_count() * sizeof (void *)
// 控制元素大小
+ 3 * sizeof(void*) + sizeof(size_t);Folly 库使用 -mavx -O2 编译，Load Factor 使用默认参数；B16 使用 -mavx -O2 编译，Load Factor 设定为 13；unordered_map 使用 Ubuntu 系统自带版本，Load Factor 使用默认参数。
测试服务器是一台 4 核 8G 的 CentOS 7u5 虚拟机，CPU 是 Intel(R) Xeon(R) Gold 6148 @ 2.40GHz，程序在 Ubuntu 20.04.1 LTS Docker 中编译执行。
5.2 实验数据
图 3：插入性能对比
上图中折线所示为 unordered_map、F14ValueMap 和 B16ValueMap 的插入性能对比，不同的柱子显示了不同哈希表的存储开销。
可以看到 B16 哈希表在存储开销明显小于 unordered_map 的情况下，仍然提供了显著优于 unordered_map 的插入性能。
由于 F14 哈希表对 Load Factor 的自动寻优策略不同，在不同哈希表大小下 F14 的存储空间开销存在一定波动，但 B16 的存储开销整体仍优于 F14。B16 的插入性能在 100 万 Key 以下时优于 F14，但是在 1000 万 Key 时劣于 F14，可能是因为当数据量较大时 B16 拉链式内存访问的局部性比 F14 差一些。
图 4：查找性能对比
上图中折线所示为 unordered_map、F14ValueMap、B16ValueMap 和 B16Compact 的查找性能对比，不同的柱子显示了不同哈希表的存储开销。
可以看到 B16、B16Compact 哈希表在存储开销明显小于 unordered_map 的情况下，仍然提供了显著优于 unordered_map 的查找性能。
B16 与 F14 哈希表的查找性能对比与插入性能类似，在 100 万 Key 以下时明显优于 F14，但在 1000 万时略劣于 F14。
值得注意的是 B16Compact 哈希表的表现。由于实验哈希表的 Key 和 Value 类型均取 uint64_t，存储 Key, Value 对本身就需要消耗 16 字节的空间，而 B16Compact 哈希表对不同大小的哈希表以稳定的约 17.31 bytes/key 进行存储，这意味着哈希结构里为每个 Key 仅额外花费了 1.31 个字节。之所以没有达到 9.23 bits/key 的理论开销，是因为我们的 BUCKET 数组没有使用 bitpack 方式进行极致压缩（这可能会影响性能），而是使用了 uint32_t。
6 总结
本文中我们从哈希表设计的核心出发，介绍了两种有趣的、不算“常见”的哈希冲突解决方法：完美哈希函数和基于 SIMD 指令的 F14 哈希表。
在 F14 的启发下，我们设计了 B16 哈希表，使用了更容易理解的数据结构，使得增、删、查的实现逻辑更为简单。实验表明在一些场景下 B16 的存储开销和性能比 F14 还要好。
为追求极致的存储空间优化，我们对 B16 哈希表进行紧致压缩，设计了几乎可以媲美最小完美哈希函数的 B16Compact 哈希表。B16Compact 哈希表的存储开销显著低于 F14 哈希表（介于40%-60%之间），但却提供了颇有竞争力的查询性能。这在内存紧张的场合，例如嵌入式设备或者手机上，可以发挥很大的作用。
新的哈希表设计表明 SIMD 指令的并行化处理能力的有效应用能大幅度提升哈希表对哈希冲突的容忍能力，进而提升查询的速度，并且能帮助哈希表进行极致的存储空间压缩。这让哈希表的设计思路从尽量规避哈希冲突，转向了利用合适的哈希冲突概率来优化计算和存储效率。