趣谈哈希表优化：从规避 Hash 冲突到利⽤ Hash 冲突
导读：本文从哈希表传统设计与解决思路入手，深入浅出地引出新的设计思路：从尽量规避哈希冲突，转向了利⽤合适的哈希冲突概率来优化计算和存储效率。新的哈希表设计表明 SIMD 指令的并⾏化处理能⼒的有效应⽤能⼤幅度提升哈希表对哈希冲突的容忍能⼒，进⽽提升查询的速度，并且能帮助哈希表进⾏极致的存储空间压缩。
哈希表是⼀种查找性能⾮常优异的数据结构，它在计算机系统中存在着⼴泛的应⽤。尽管哈希表理论上 的查找时间复杂度是 O(1)，但不同的哈希表在实现上仍然存在巨⼤的性能差异，因⽽⼯程师们对更优秀 哈希数据结构的探索也从未停⽌。
1.1 哈希表设计的核⼼
从计算机理论上来说，哈希表就是⼀个可以通过哈希函数将 Key 映射到 Value 存储位置的数据结构。那么哈希表设计的核⼼就是两点：
1. 怎样提升将Key映射到Value存储位置的效率？
2. 怎样降低存储数据结构的空间开销？
由于存储空间开销也是设计时的⼀个核⼼控制点，在受限于有限的空间情况下，哈希函数的映射算法就存在着⾮常⾼的概率将不同的 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 哈希数据结构
△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 的只读紧凑数据结构，如下图所示：
△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]，找到对应的元素。
B16 Compact 的理论额外存储开销可以通过下式算得：
其中，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 实验数据
△插⼊性能对⽐
上图中折线所示为 unordered_map、F14ValueMap 和 B16ValueMap 的插⼊性能对⽐，不同的柱⼦显示了不同哈希表的存储开销。
可以看到 B16 哈希表在存储开销明显⼩于 unordered_map 的情况下，仍然提供了显著优于unordered_map 的插⼊性能。
由于 F14 哈希表对 Load Factor 的⾃动寻优策略不同，在不同哈希表⼤⼩下 F14 的存储空间开销存在⼀定波动，但 B16 的存储开销整体仍优于 F14。B16 的插⼊性能在 100 万 Key 以下时优于 F14，但是在 1000万 Key 时劣于 F14，可能是因为当数据量较⼤时 B16 拉链式内存访问的局部性⽐ F14 差⼀些。
△查找性能对⽐
上图中折线所示为 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.31bytes/key 进⾏存储，这意味着哈希结构⾥为每个 Key 仅额外花费了 1.31 个字节。之所以没有达到 9.23bits/key 的理论开销，是因为我们的 BUCKET 数组没有使⽤ bitpack ⽅式进⾏极致压缩（这可能会影响性能），⽽是使⽤了 uint32_t。
6 总结
本⽂中我们从哈希表设计的核⼼出发，介绍了两种有趣的、不算“常⻅”的哈希冲突解决⽅法：完美哈希函数和基于 SIMD 指令的 F14 哈希表。
在 F14 的启发下，我们设计了 B16 哈希表，使⽤了更容易理解的数据结构，使得增、删、查的实现逻辑更为简单。实验表明在⼀些场景下 B16 的存储开销和性能⽐ F14 还要好。
为追求极致的存储空间优化，我们对 B16 哈希表进⾏紧致压缩，设计了⼏乎可以媲美最⼩完美哈希函数的 B16Compact 哈希表。B16Compact 哈希表的存储开销显著低于 F14 哈希表（介于40%-60%之间），但却提供了颇有竞争⼒的查询性能。这在内存紧张的场合，例如嵌⼊式设备或者⼿机上，可以发挥很⼤的作⽤。
新的哈希表设计表明 SIMD 指令的并⾏化处理能⼒的有效应⽤能⼤幅度提升哈希表对哈希冲突的容忍能⼒，进⽽提升查询的速度，并且能帮助哈希表进⾏极致的存储空间压缩。这让哈希表的设计思路从尽量规避哈希冲突，转向了利⽤合适的哈希冲突概率来优化计算和存储效率。
百度架构师
百度官方技术公众号上线啦！
技术干货 · 行业资讯 · 线上沙龙 · 行业大会
招聘信息 · 内推信息 · 技术书籍 · 百度周边
欢迎各位同学关注！