Hash Table Benchmark - 分析与结论

这篇把前面 benchmark 的结果完整梳理一遍，涵盖整数和字符串 key、小 value 和大 value，并讨论针对具体的 workload 该怎么选哈希表和哈希函数。

没有最好的哈希表

这组 benchmark 覆盖了插入、删除、查询（命中、未命中，以及 50% 混合）和遍历。测试在多种分布的整数 key、以及 12、24、64 字节的字符串 key 上进行，value 分别为 8 字节和 56 字节（因此存储的 pair 为 16 或 64 字节），规模从 32 一直到 10^7 个元素，跑在两台差别很大的机器上——Intel Xeon E-2388G（Rocket Lake）和 Apple M1 Max。在这么多变化中始终成立的一条经验是：没有哪个组合能一直最快——快慢会随 workload 中占主导的操作、key 的类型和分布、value 的大小、表相对于 cache 的大小，以及平台而变。

第二条值得先讲的经验是：哈希表和哈希函数必须一起选。有些表假定哈希已经把 key 均匀打散，一旦不是这样就会严重退化；另一些表自己会做混淆，因此更适合搭配计算代价尽可能低的哈希。因此每张图比较的都是 表 + 哈希 的组合，而不是孤立地比较表。

查询

查询往往是大家最关心的操作，也是表的设计最能体现差异的地方。一次查询可以拆成三部分：计算哈希、把它映射到 slot，以及加载并比较 key。哪一部分占主导，取决于 key 的类型，以及表里有多少数据能放进 cache。

整数 key

对整数 key，一次查询的时间分摊在计算并映射哈希、以及随后的访存之间，哪一项占主导取决于表有多少在 cache 里。哈希本身的开销不一定低：identity 的 std::hash 几乎不花成本，在 key 本身已经分布均匀时没问题，但如果 key 的信息只集中在少数几个 bit 上——比如指针和对齐地址（低位总是 0）或较小的连续 ID（高位总是 0）——在 identity hash 下就会严重冲突，需要一个真正做混淆的哈希，比如 absl::Hash（一次 128 位乘法加 xor-shift）把它们打散到表里。因此该选哪个哈希取决于 key（下文还会展开）。随着表增大，排名会经历三个阶段。当表能放进 L1/L2 cache 时，访存很快——只有几纳秒——所以每次探测的指令数（哈希加 slot 映射）和访存相当，正是它拉开了各表的差距；最精简的组合胜出，ska::flat_hash_map 搭配 identity 的 std::hash 在小规模下最快（两台机器上 1,024 个元素时每次命中约 1.3 ns），M1 上 fph::DynamicFphMap 紧随其后，只落后约 0.1 ns。在中间区间，表位于 L2/L3 cache 里时， fph::DynamicFphMap 领先（Xeon 上 200,000 时约 3.4 ns，1.2M 时 10.9 ns），因为它有上界的探测次数让碰到的 cache line 很少。在最大的规模下，每次查询都 cache miss、访存占主导， ska::flat_hash_map 又重新最快（10^7 时 Xeon 上约 14.7 ns，M1 上 9.3 ns），因为读取 cache line 最少的表——单个紧凑的 slot 数组——无论用什么哈希都会胜出。

未命中则更能区分高下。要证明一个 key 不存在，表必须排除它可能占据的每一个 slot，而每个 slot 存了一字节 metadata 的表，无需碰完整的 key 就能做到。fph::MetaFphMap 自成一档：它基本只用一次访存就能排除一个不存在的 key，从约 6,000 个元素起就有最好的平均未命中时间，长尾也紧得多——在 1.2M 个元素时它的 P99 未命中延迟约为 34 ns，而 r_h::unordered_flat_map / absl::flat_hash_map 约为 106-111 ns，需要走探测链的 ska::flat_hash_map 和 tsl::robin_map 则为 440-465 ns。这个优势一直保持到 metadata 数组本身离开 L3 cache（这里大约在 10^7），之后它也要多一次 DRAM 访问。在未命中上，常规表里 absl::flat_hash_map 最好，因为它正是围绕同样的 metadata 思路构建的。50% 命中的情况大致是两者的平均，而结果不断交替会带来分支预测失败的惩罚，使所有差距都缩小。

字符串 key

字符串 key 改变了局面，因为哈希的成本高得多——要哈希和比较的是整个字符串，而不是单个 64 位字——而且较长的字符串可能存放在堆上。有两个效应特别突出。

第一，面向字节的 xxHash_xxh3 成为几乎每个表最优的哈希，而且字符串越长越是如此：哈希占主导，所以一个快的字节哈希比表本身更重要。第二，cache 内查询的下限随长度急剧上升。在 Xeon 上，一次命中的 cache 内查询，整数 key 约 1.3 ns，12 字节字符串约 6.5 ns，定长 24 字节字符串约 13 ns，64 字节字符串约 16 ns。12 到 24 字节之间的跳变主要来自小字符串优化（SSO）：长度不超过约 15 字节的字符串会内联存放在 std::string 对象内，更长的则分配在堆上，于是查询必须跟着一个指针到另一条 cache line 上去比较字符。这一点在数据里直接体现出来——变长 24 字节的 key 大多短到能内联，比定长 24 字节（全部分配在堆上）快约一倍（小规模下约 7 ns 对 13 ns）。

除了下限更高，排名和整数情况一致：perfect hash table 在 cache 内领先（对 64 字节 key，命中时 fph::DynamicFphMap 和 fph::MetaFphMap 搭配 xxHash_xxh3 最快），robin hood 系的 tsl::robin_map 和 ska::flat_hash_map 在变成访存受限后反超，而 fph::MetaFphMap 又一次在未命中上占据主导（64 字节 key，1,024 时约 8 ns，1.2M 时 60 ns，而紧随其后的表约为 63-68 ns）。

value 大小的影响

把 value 从 8 字节增大到 56 字节（64 字节的 pair）会让每个 slot 大四倍，于是每一层 cache 能放下的条目更少，每个表都更早变成访存受限；在 10^7 时，8 字节 value 下约 15 ns 的一次命中，到 56 字节 value 下要约 21 ns。这把天平进一步推向碰 cache line 最少的表： fph::DynamicFphMap 凭借有上界的探测次数，在大 value 下领先的区间比小 value 下更宽。如果 value 较大，就应该给中等和大规模的结果比小规模更高的权重。

构造和修改表

对 perfect hash table，插入把查询的排名整个反转了过来。flat 系的表——absl::flat_hash_map、 ska::flat_hash_map、emhash::hash_map7、tsl::robin_map、ankerl::unordered_dense_map ——填充最快（预留容量时，小规模下每次插入约 4-6 ns，10^7 时 25-35 ns），而 std::unordered_map 慢得多（10^7 时接近 125 ns），因为它为每个元素分配一个节点。perfect hash table 则以很大差距垫底：在 Xeon 上，构建 perfect hash 让 fph::DynamicFphMap 和 fph::MetaFphMap 在 10^7 时每个元素大约要 1,450-1,900 ns，约为 std::unordered_map 的 12-15 倍（M1 上为 11-12 倍）。去掉 reserve 调用会让每个表的插入时间大致翻倍，因为扩容会触发反复的 rehash。

删除-插入测试交替执行一次删除和一次插入以保持表大小不变，它偏好 flat 系的表（ska::flat_hash_map、tsl::robin_map、absl::flat_hash_map）；开放寻址的表会在删除的条目处留下墓碑（tombstone），而 perfect hash table 表现最差，在最大规模下会超时，因为它们无法低成本地应对频繁的增删。

key 的类型和 value 的大小在这里同样重要。对字符串 key，每次插入和删除还要多算一次字符串哈希，对超过 SSO 上限的字符串，还要为字符做一次堆分配和释放——所以 12 字节和 64 字节字符串 workload 之间差距很大，而整数插入则纯粹由表本身的机制主导。和查询一样，更大的 value 会把访存受限的区间更早地推到前面。

遍历

遍历几乎完全由存储布局决定，与哈希函数无关，也几乎与 key 的类型无关（迭代器访问的是固定大小的表 slot；它不会重新哈希，对内联存储的条目也不会解引用 key）。 ankerl::unordered_dense_map 和 emhash::hash_map7 把条目存放在一个紧凑、连续的数组里，无论 load factor 如何，每个元素的遍历时间都近似常数——Xeon 上约 0.22 ns，M1 上约 2.0 ns，在整个规模范围内都很平。内联的开放寻址表必须扫描一个稀疏的 slot 数组并跳过空 slot，所以代价随规模上升；基于节点的 std::unordered_map 最慢，要追那些会 cache miss 的指针（Xeon 上 10^7 时每个元素约 35 ns）。perfect hash table 在这里没有特别的好处，因为它们遍历的也是稀疏布局。

内存占用和 load factor

在整数 key-value 上测得的内存占用，在 10^7 个元素时把这些表分成三组。每个 slot 一字节 metadata 的 SwissTable——absl::flat_hash_map 和 ska::bytell_hash_map——最紧凑，约 272 MB；基于节点的 std::unordered_map 和 absl::node_hash_map 次之（约 308 MB 和 297 MB）；fph 系的表为了那个加速查询的索引，占用约为最紧凑者的两倍（约 556-572 MB）；而 ska::flat_hash_map 和 tsl::robin_map 最大，约 768 MB，因为它们保持较低的最大 load factor，并在每个 slot 里存放经过对齐填充的完整 value。

load factor 图能解释这一点。开放寻址的表按翻倍扩容，所以占用率在大约 0.4 到 0.9 之间呈锯齿状起伏；ska::flat_hash_map 和 tsl::robin_map 稳定在最低值（大规模下约 0.30），用空槽换速度，而 std::unordered_map 接近 1.0（每个元素一个节点，没有空槽）。提高 max_load_factor 会把 flat 表排得更紧——ska::flat_hash_map 在 10^7 时从约 0.30 升到 0.60，空间利用率大致翻倍——代价是探测更长。由于内存占用决定了一个表何时跨过各级 cache 的边界，这正是查询结果里那些 cache 层级背后的结构性原因：更臃肿的表会在更小的元素数量上就掉出 cache。

哈希函数和表一样重要

对整数 key，std::hash 是 identity 函数。自己会做混淆的表——最典型的是 ska::flat_hash_map——可以安全地使用它，并享受它的零成本。但对不是均匀随机的 key——那些信息只集中在少数几个 bit 上的 key，比如指针或较小的连续 ID——假定哈希已经均匀的表（absl::flat_hash_map、emhash::hash_map7、tsl::robin_map）在 identity hash 下会发生灾难性的冲突，严重到某些组合会在构造时超时，所以它们需要一个好的混淆哈希，比如 absl::Hash。即使是好的哈希也可能有弱点：robin_hood::hash 对某些这类 key 模式打散得不好，使 tsl::robin_map 搭配它时在中等规模出现一段不规则的塌陷。对字符串 key，xxHash_xxh3 全面胜出。

平台差异：Rocket Lake 与 M1 Max

两台机器的内存系统差别很大。Xeon E-2388G（Rocket Lake）有 48 KB L1、512 KB L2 和 16 MB L3，页大小 4 KB；M1 Max 有 128 KB L1、12 MB L2 和 48 MB 系统级 cache，页大小 16 KB。M1 更大的 cache 和页把每一级 cache 的边界都向右推，并减轻了 TLB 压力，所以虽然各表的排名 在不同平台上大体一致，但一个表反超另一个的规模点并不相同。有一个怪现象：M1 上 libc++ 的 std::unordered_map 用取模来索引 bucket，当 bucket 数量是 2 的幂时，取模退化成一个 2 的幂掩码，丢掉了哈希的高位，这使得这个组合在元素数量恰好是 2 的幂时慢得反常。

如何选择哈希表

有两个实际问题基本决定了大部分选择：表被写的频率相对读有多高，以及它相对于实际能用到的 cache 有多大。

关于第一个问题：如果表构造一次之后，被查询的次数远多于被修改，那么 perfect hash 的 fph::DynamicFphMap（未命中常见时用 fph::MetaFphMap）能给出最好的查询性能——代价是构造慢、无法应对频繁更新，以及大约是最紧凑表两倍的内存，所以它远比一个不断变化的表更适合做静态字典、以读为主的索引，或成员集合。如果插入、删除和查询混合，flat 表是更均衡的全能选手，而 absl::flat_hash_map 搭配 absl::Hash（字符串则用 xxHash_xxh3）是一个快速、紧凑、对分布稳健的默认选择。

第二个问题需要把“cache 内很快”这句话拆开来看。一个表“在 cache 里”，指的是它的整个内存占用——而不只是元素数量——能放进某一级 cache：在 Xeon 上，L2 大约能放 16,000 个小（16 字节）条目，L3 大约能放一百万个，而当 value 较大或 key 是堆分配的字符串时，能放的数量会成比例地减少。因此，ska::flat_hash_map——在所有数据都驻留时最快的表——主要适合真正小的表，或者内存足够宽裕的场景。问题在于 ska::flat_hash_map 同时也是所有表里内存占用最大的（它之所以快，正是因为 load factor 低），所以在相同元素数量下，它比紧凑的表更早离开 cache，也会更激烈地与程序其余部分争用 cache。在真实应用里，cache 要和同时运行的一切共享，所以有效的阈值远低于裸 cache 大小；如果内存紧张、cache 有争用，或者表很大，那么紧凑的 absl::flat_hash_map 或 ska::bytell_hash_map 通常会胜过它——尽管在独占整个 cache 的 benchmark 里 ska::flat_hash_map 略有优势。对以遍历为主的工作，无论规模大小， ankerl::unordered_dense_map 都是明确的选择。

最后的建议

std::unordered_map 在几乎每一项吞吐测试里都是最慢的表，原因是它每个元素一个节点的布局，所以它主要值得在确实需要其迭代器和指针稳定性保证时保留。除此之外，上面这张表是一个起点，而不是定论：表、哈希、key 分布、value 大小、表大小和平台所构成的完整空间极其庞大，真实 workload 可能落在这里测过的各种情况之间。最可靠的答案永远是：在真实的数据和操作组合上，对两三个最有希望的候选做一次 benchmark。

← 返回 Hash Table Benchmark 目录