导读：

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

1  背景

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

1.1 哈希表设计的核⼼

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

1. 怎样提升将Key映射到Value存储位置的效率？

2. 怎样降低存储数据结构的空间开销？

哈希冲突

B16 哈希表。

2  规避哈希冲突

传统哈希表对哈希冲突的处理会增加额外的分⽀跳转和内存访问，这会让流⽔线式的CPU指令处理效率变差。那么肯定就有⼈考虑，怎么能完全规避哈希冲突？所以就有了这样⼀种函数，那就是完美哈希函数（perfect hash function）。

http://cmph.sourceforge.net/

⽆环随机 3-部超图

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

完美哈希函数往往仅能作⽤在限定集合上，即所有可能的 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 指令再解决冲突。

H1

H2

H1

H2

每个块⾥最多存放 14 个元素，块头有 16 个字节。

H2

在插⼊时，当 Key 映射到的块中 14 个位置还有空时，就直接插⼊；

当块已经满时，就增加越界计数器，尝试插⼊下⼀个块中；

H1

H2

H1

H2

H2s

H2

否则根据块头的第 16 字节判断是否还需要⽐对下⼀个块。

H2

4  B16 哈希表

不考虑分块内部的设计，F14 本质上是⼀个开放寻址的哈希表。每个块头的第 15、16 字节被⽤于开放寻址的控制策略，只剩 14 个字节留给哈希码，也因⽽被命名为 F14。

那么我们考虑能不能从另⼀个⻆度出发，使⽤拉链法来组织分块。由于省去了控制信息，每个分块中可以放置 16 个元素，我们把它命名为 B16。

4.1 B16 哈希数据结构

△

上图所示就是⽤每个分块 3 个元素展示的 B16 哈希表的数据结构。中间绿⾊的是常⻅的 BUCKET 数组，存放的是每个分桶中 CHUNK 拉链的头指针。右侧的每个 CHUNK 与 F14 相⽐，少了控制字节，多了指向下⼀个 CHUNK 的 next 指针。

H1

H2

H1

H2

H1

H2

H1

H2

H2'

H2

H2

在删除时，⾸先查找到对应的元素，然后⽤块拉链最尾部的元素覆盖掉对应的元素即可。

当然，B16 哈希表每个块的元素个数可以根据 SIMD 指令的宽度进⾏灵活调整，例如使⽤ 256 bits 宽度指令可以选择 32 元素的块⼤⼩。但影响哈希表性能的不仅仅是查找算法，内存访问的速度和连续性也⾮常重要。控制块⼤⼩在 16 以内在⼤多数情况下能充分利⽤ x86 CPU 的 cache line，是⼀个较优的选择。

普通的拉链式哈希表，拉链的每个节点都只有⼀个元素。B16 这种分块式拉链法，每个节点包含 16 个元素，这会造成很多空洞。为了使空洞尽可能的少，我们就必须增加哈希冲突的概率，也就是尽量地缩⼩BUCKET 数组的⼤⼩。我们经过试验发现，当 Load Factor 在 11-13 之间时，B16 的整体性能表现最好。其实这也相当于把原来存在于 BUCKET 数组中的空洞，转移到了 CHUNK 拉链中，还省去了普通拉链式每个节点的 next 指针开销。

4.2 B16Compact 哈希数据结构

△

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个字节多⼀点。这⼏乎可以媲美⼀些最⼩完美哈希函数了，⽽且不会出现构建失败的情况。

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 通过以下公式获取：

// 拉链节点总⼤⼩

sizeof

uint64_t

sizeof

std

uint64_t

uint64_t

sizeof

void

// bucket 总⼤⼩

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。

6  总结

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

新的哈希表设计表明 SIMD 指令的并⾏化处理能⼒的有效应⽤能⼤幅度提升哈希表对哈希冲突的容忍能⼒，进⽽提升查询的速度，并且能帮助哈希表进⾏极致的存储空间压缩。这让哈希表的设计思路从尽量规避哈希冲突，转向了利⽤合适的哈希冲突概率来优化计算和存储效率。

- EOF -

推荐阅读

点击标题可跳转

经典逻辑面试题：高楼扔鸡蛋

智能优化算法：灰狼优化算法

经典算法：杨辉三角

觉得本文有帮助？请分享给更多人

推荐关注「算法爱好者」，修炼编程内功

点赞和在看就是最大的支持

❤️

---

原文链接

2021年1月21日，北京大学环境科学与工程学院发文正式通知成立环境健康系。 环境健康系的成立，将进一步强化北京大学环境科学与工程一级学科的“科学-工程-健康-管理”全链条创新机制，同时促进高素质环境健康人才的培养。 > > > > 2015年在环境科学与工程一级学科下设立国内首个环境健康二级学科，招收和培养环境健康方向的硕士与博士研究生。 经过20余年的发展，一支小而精、具有国际影响的师资队伍成为环境健康系的首批成员。其中全职教研系列人员7名、研究系列和工程技术人员2名，包括国家杰出青年科学基金获得者1人，北京大学博雅特聘教授1人，国家青年人才计划入选者5人。作为环境“科学-工程-健康-管理”的全链条创新的一个关键环节，环境健康系将秉承学科交叉融合理念，依托前沿交叉学科研究院“环境健康研究中心”平台，加强与校内其它院系尤其是医学部多个学科的交叉融合，以及与国际一流学者专家的合作。在国家111引智基地、“未来地球计划-亚洲季风区可持续发展集成研究”（FutureEarth-MAIRS）的支持下，环境健康系的教师与欧美顶尖团队开展多个项目合作，国际合作卓有成效。 北京大学环境科学与工程学院 北京大学是我国最早开展环境学科教学和科研的机构之一 ，经过40余年的快速发展，形成了在国内环境学科领域的整体优势地位，成为国际环境科学与工程领域具有一定影响的教学与科研机构。在最新的US News、QS等国际学科评估中，北京大学环境学科分别位列全球58位和全球21位。按基本科学指标（ESI）的数据，

（给 算法爱好者 加星标，修炼编程内功 ） 来源：CSDN 面向对象编程的流行是计算机科学领域的不幸，它对现代经济造成了极大的破坏，造成了数万亿美元的间接损失。在过去的三十年中，几乎所有行业都因潜在的面向对象编程危机而受到影响。 C++和 Java 可能是计算机科学领域最大的错误。就连面向对象的创建者 Alan Kay 都曾对这两门语言提出了严厉的批评。然而，C++和 Java 都是比较主流的面向对象语言。 面向对象编程的流行是计算机科学领域的不幸，它对现代经济造成了极大的破坏，造成了数万亿美元的间接损失。在过去的三十年中，几乎所有行业都因潜在的面向对象编程危机而受到影响。 为什么面向对象编程如此危险？下面我们一起来寻找答案。 2007 年 9 月，美国 Jean Bookout 驾驶的 2005 款凯美瑞突然失控，Bookout 尝试刹车但是失败，最终发生了碰撞事故，