趣谈哈希表优化：从规避Hash冲突到利Hash冲突

见贤思齐

导读：本文从哈希表传统设计与解决思路入手，深入浅出地引出新的设计思路：从尽量规避哈希冲突，转向了利?合适的哈希冲突概率来优化计算和存储效率。新的哈希表设计表明 SIMD 指令的并?化处理能?的有效应?能?幅度提升哈希表对哈希冲突的容忍能?，进?提升查询的速度，并且能帮助哈希表进?极致的存储空间压缩。1? 背景哈希表是?种查找性能?常优异的数据结构，它在计算机系统中存在着?泛的应?。尽管哈希表理论上 的查找时间复杂度是 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)?+?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 指令的并?化处理能?的有效应?能?幅度提升哈希表对哈希冲突的容忍能?，进?提升查询的速度，并且能帮助哈希表进?极致的存储空间压缩。这让哈希表的设计思路从尽量规避哈希冲突，转向了利?合适的哈希冲突概率来优化计算和存储效率。----------? END? ----------百度架构师百度官方技术公众号上线啦！技术干货?·?行业资讯 ·?线上沙龙?·?行业大会招聘信息 ·?内推信息 ·?技术书籍?·?百度周边欢迎各位同学关注！?