关于大数据:趣谈哈希表优化从规避-Hash-冲突到利⽤-Hash-冲突

2次阅读

共计 6308 个字符，预计需要花费 16 分钟才能阅读完成。

导读：本文从哈希表传统设计与解决思路动手，深入浅出地引出新的设计思路：从尽量躲避哈希抵触，转向了利⽤适合的哈希抵触概率来优化计算和存储效率。新的哈希表设计表明 SIMD 指令的并⾏化解决能⼒的有效应⽤能⼤幅度晋升哈希表对哈希抵触的容忍能⼒，进⽽晋升查问的速度，并且能帮忙哈希表进⾏极致的存储空间压缩。

哈希表是⼀种查找性能⾮常优异的数据结构，它在计算机系统中存在着⼴泛的应⽤。只管哈希表实践上的查找时间复杂度是 O(1)，但不同的哈希表在实现上依然存在巨⼤的性能差别，因⽽⼯程师们对更优良哈希数据结构的摸索也从未停⽌。

1.1 哈希表设计的核⼼

从计算机实践上来说，哈希表就是⼀个能够通过哈希函数将 Key 映射到 Value 存储地位的数据结构。那么哈希表设计的核⼼就是两点：

怎么晋升将 Key 映射到 Value 存储地位的效率？
怎么升高存储数据结构的空间开销？

因为存储空间开销也是设计时的⼀个核⼼控制点，在受限于无限的空间状况下，哈希函数的映射算法就存在着⾮常⾼的概率将不同的 Key 映射到同⼀个存储地位，也就是哈希抵触。⼤局部哈希表设计的区别，就在于它如何解决哈希抵触。

当遇到哈希抵触时，有⼏种常⻅的解决⽅案：凋谢寻址法、拉链法、⼆次哈希法。然而下⾯咱们介绍两种乏味的、不常⻅的解决思路，并且引出⼀个咱们新的实现⽅案——B16 哈希表。

传统哈希表对哈希抵触的解决会减少额定的分⽀跳转和内存拜访，这会让流⽔线式的 CPU 指令解决效率变差。那么必定就有⼈思考，怎么能齐全躲避哈希抵触？所以就有了这样⼀种函数，那就是完满哈希函数（perfect hash function）。

完满哈希函数能够将⼀个 Key 汇合⽆抵触地映射到⼀个整数汇合中。如果这个⽬标整数汇合的⼤⼩与输⼊汇合雷同，那么它能够被称为最⼩完满哈希函数。

完满哈希函数的设计往往⾮常精美。例如 CMPH（http://cmph.sourceforge.net/）函数库提供的 CDZ 完满哈希函数，利⽤了数学上的⽆环随机 3- 部超图概念。CDZ 通过 3 个不同的 Hash 函数将每个 Key 随机映射到 3 - 部超图的⼀个超边，如果该超图通过⽆环检测，再将每个 Key 映射到超图的⼀个顶点上，而后通过⼀个精⼼设计的与超图顶点数雷同的辅助数组获得 Key 最终对应的存储下标。

完满哈希函数听起来很优雅，但事实上也有着实⽤性上的⼀些缺点：

完满哈希函数往往仅能作⽤在限定汇合上，即所有可能的 Key 都属于⼀个超集，它⽆法解决没⻅过的 Key；
完满哈希函数的结构有⼀定的复杂度，⽽且存在失败的概率；
完满哈希函数与密码学上的哈希函数不同，它往往不是⼀个简略的数学函数，⽽是数据结构 + 算法组成的⼀个性能函数，它也有存储空间开销、拜访开销和额定的分⽀跳转开销；

然而在指定的场景下，例如只读的场景、汇合确定的场景（例如：汉字汇合），完满哈希函数可能会获得⾮常好的体现。

即使不使⽤完满哈希函数，很多哈希表也会刻意管制哈希抵触的概率。最简略的方法是通过管制 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 对⽐的开销，使哈希表可能容忍更⾼的抵触概率。

不思考分块外部的设计，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.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。

本⽂中咱们从哈希表设计的核⼼登程，介绍了两种乏味的、不算“常⻅”的哈希抵触解决⽅法：完满哈希函数和基于 SIMD 指令的 F14 哈希表。

在 F14 的启发下，咱们设计了 B16 哈希表，使⽤了更容易了解的数据结构，使得增、删、查的实现逻辑更为简略。试验表明在⼀些场景下 B16 的存储开销和性能⽐ F14 还要好。

为谋求极致的存储空间优化，咱们对 B16 哈希表进⾏紧致压缩，设计了⼏乎能够媲美最⼩完满哈希函数的 B16Compact 哈希表。B16Compact 哈希表的存储开销显著低于 F14 哈希表（介于 40%-60% 之间），但却提供了颇有竞争⼒的查问性能。这在内存缓和的场合，例如嵌⼊式设施或者⼿机上，能够施展很⼤的作⽤。

新的哈希表设计表明 SIMD 指令的并⾏化解决能⼒的有效应⽤能⼤幅度晋升哈希表对哈希抵触的容忍能⼒，进⽽晋升查问的速度，并且能帮忙哈希表进⾏极致的存储空间压缩。这让哈希表的设计思路从尽量躲避哈希抵触，转向了利⽤适合的哈希抵触概率来优化计算和存储效率。

正文完