Hash Table Benchmark

这是一组关于 C++ 哈希表和哈希函数的 benchmark。测试内容包括查询、插入、删除、遍历等操作，也覆盖了多种数据分布。

结果主要用来比较“哈希表 + 哈希函数”这个组合在不同操作、不同数据类型、不同数据规模下的表现。实际选择时，可以根据自己的应用场景，在这些结果里找更合适的哈希表和哈希函数。

测试数据采集于 2022 至 2023 年（机器配置见下文），文章整理发布于 2026 年。

阅读结果前须知

不同哈希表对 key 的分布和操作类型都很敏感，同一个实现换一组数据后，性能排名就可能变化很大。换句话说，不存在一个哈希表在所有数据、所有操作上都是最快的。

选择哈希表时，比较好的做法是把数据特征、操作类型、业务要求和哈希函数一起考虑。

这个 benchmark 主要测试一些常见数据分布下，哈希表不同操作的性能。不过，真实数据分布总可能和这里测试的数据有很大差别，不同场景对不同指标的要求也不一样。因此，最可靠的做法仍然是在真实应用里测试。

测试方法

测试项目

测试对象是不同哈希表和不同哈希函数的组合。对于每一种组合，测试插入、删除、查询（包括命中和未命中）以及遍历在不同数据上的性能。更详细的测试项目如下。

上面的项目里可以看到，几个查询测试会使用更大的 max_load_factor。load_factor 表示哈希表被填满的程度，max_load_factor 是 STL 中控制其上界的 API。这样做是因为不同哈希表可能有不同的扩容策略和 max_load_factor，即使元素数量一样，不同表也可能选择不同的 load_factor，占用不同大小的内存。load_factor 和内存占用会很大程度上影响查询性能，所以使用较小 max_load_factor 的哈希表，查询性能可能变好，也可能变差。另一方面，更高的 load_factor 可能带来更高的冲突概率，从而降低查询性能。

另外，追求极限查询性能时往往要求哈希表尽量少占空间，以降低 cache miss 率。当可用内存非常有限时，也可能更希望使用较高的 load_factor。一个做法是设置更高的 max_load_factor，然后 rehash；或者在主要构造过程之前就把 max_load_factor 设大。

对上面每一种测试，都会测试吞吐和延迟（在测试平台满足延迟测试条件时）。吞吐测试的结果通常更有代表性，因为现代软件运行在流水线 CPU 上，几乎所有操作前后都会有其他指令，能够充分利用流水线。不过在一些特定场景下，延迟数据也很重要。这里的延迟测试结果主要供有特殊需求的场景参考，它本身有比较大的局限性。

测试数据

benchmark 中使用的数据都是随机生成的，测试数据可以选择不同的随机种子。每种哈希表会在 32 到 10^7 的不同数据规模下测试。

测试 key 包括不同分布的 64 位整数，以及不同长度的字符串。详细的数据类型如下表。

在 uint64_t 能表示的范围内，我们选择了几种不同分布作为 key。uint64_t 范围内的均匀随机整数最容易用伪随机数生成，但在真实场景中并不常见。

如果关心整数 key 下的性能，强烈建议重点看第一组数据的结果，而不是第二组均匀随机分布的数据。第一组数据更能检查哈希表和哈希函数处理多样化模式的能力；均匀随机分布的测试，基本只能说明它们对均匀随机分布本身的处理能力。而真实数据里，很少有 key 恰好在 [0, 2^63 - 1] 范围内均匀随机分布。

基于这个考虑，整数 key 的分析主要关注第一组数据。为了让文章不至于太长，其余整数数据集（包括第二组均匀随机分布，以及高位、低位被 mask 的数据）大多只在各测试文章的附录里给出图，不再展开分析。

字符串数据使用了不同字符集。对于定长字符串，其模式和第一组整数数据类似：只有某些位置上的 bit 可能不同，其余 bit 都是固定的。这个模式主要用来测试哈希函数的质量。

对于变长字符串，字符串中可以出现可打印字符的一个子集。

真实数据分布常常是有偏的。如果一种哈希函数和哈希表的组合只能处理一种分布，却不能处理其他分布，那么这个组合面对未知分布时就不够稳健。如果数据分布是提前知道的，则可以为这类数据选择最快且稳定的哈希表。

测试的哈希函数和哈希表

下面是测试中使用的哈希函数。

最早的测试里还包含一些 seed hash function，也就是同时接收 key 和 seed 作为参数的哈希函数。为了让测试对象更简单，后来删除了这些哈希函数，并且所有哈希表都使用无 seed 版本。

整数 key 的测试不会展示 xxHash_xxh3 的结果。早期版本的 absl::Hash 在 arm64 平台和 x86-64 平台上行为不一致，导致在某些数据集上表现很差。因此以前还放过一个 uint128_mul::hash 作为对照，它和 x86-64 平台上的 absl::Hash 类似。新版 absl::Hash 已经修复了这个问题，所以这里删除了 uint128_mul::hash。

下面列出测试的哈希表。这里有些哈希表依赖“好的”哈希函数才能正常工作，也就是哈希函数需要在不均衡 key 上也尽量生成均匀分布的 hash value。如果用了不具备这种性质的哈希函数（比如 identity hash），这些哈希表的性能可能会明显下降。这些哈希表可能默认 key 的 hash value 已经在输出范围内均匀分布，因此要求哈希函数具有比较好的均匀性或扩散性。

这里的含义是，“好的”哈希函数往往比最简单的哈希函数（identity hash）复杂，需要更多指令才能完成计算。有些哈希表并不依赖很好的哈希函数，也许是因为它们自己会对 hash value 再做一次混淆来改善均匀性。对于这样的哈希表，哈希函数越简单越好，最好就是 identity hash。因此比较时应该始终比较“哈希表 + 哈希函数”的组合，而不是固定哈希函数比较哈希表，或者固定哈希表比较哈希函数。

测试的哈希表如下。

* 注：在测试的 libc++ 和 libstdc++ 版本中，libc++ 的实现需要好的哈希函数，而 libstdc++ 没有这个要求。如果使用 std::hash，libc++ 在大小为 2 的幂时性能可能很差。

粗略看一下就会发现，上面很多哈希表为了追求速度，都使用了 robin hood hashing 技术。

实验和结果

这个 benchmark 的代码在 https://github.com/renzibei/hashtable-bench。

测试平台

平台 1：Intel Xeon E-2388G CPU @ 3.20 GHz，最高 boost 到 5.1 GHz；x86-64；Rocket Lake。

平台 2：M1 Max Macbook Pro 16 inch, 2021；arm64；Firestorm。

由于 arm64 平台（M1 Max）缺少高精度的时间戳计数器，延迟只在 x86-64 平台上测试（AMD CPU 在使用 TSC 测延迟时也会有一些问题，所以延迟只测试 Intel CPU）。另外，对于 x86-64 平台，也做了一些设置来保证测试结果稳定，包括：

1. 使用 taskset 命令设置 CPU core affinity
2. 关闭超线程
3. 在 /etc/default/grub 的 GRUB_CMDLINE_LINUX 中加入 isolcpus= 和 rcu_nocbs= 来隔离核心
4. 关闭部分省电选项，包括禁用 ondemand systemd service，并在 grub command line 中设置 idle=poll 和 intel_idle.max_cstate=0
5. 关闭 timer tick interrupt，重新编译内核并设置 CONFIG_NO_HZ_FULL=y，同时在 grub command line 中设置 nohz_full=
6. 其他一些降低系统延迟抖动的设置，可以参考 https://rigtorp.se/low-latency-guide/

这些设置在 macOS 上无法完成。不过 macOS 上不测操作延迟，所以影响不大。

结果

吞吐数据会用每次操作的平均时间表示。图中展示不同数据规模下的平均单次操作时间，时间越短，性能越好。

延迟数据由于篇幅限制，在大多数测试中只展示 99 分位延迟。这个指标可以帮助观察哈希表的最坏时间复杂度和长尾延迟，但它甚至还不足以反映真正的最坏情况。对于有长尾特征的分布，0.99、0.999、0.9999 分位的值都可能差别很大。如果应用对实时性和尾延迟有严格要求，比如游戏或高频交易，那么这类指标值得重点关注。

如果某项测试耗时过长，就会被记为 timeout，并把时间设为 0；这样的数据点不会画出来。

可以点击图例中的标签，隐藏或显示特定哈希表和哈希函数对应的数据线。

结果按照数据类型和操作类型分成下面几组。

• 整数 Key
  • 整数插入和构造
  • 整数删除和插入
  • 整数查询吞吐
  • 整数查询延迟
  • 整数遍历
• 字符串 Key
  • 字符串插入和构造
  • 字符串删除和插入
  • 64 byte 字符串查询
  • 24 byte 字符串查询
  • 12 byte 字符串查询
  • 字符串遍历
• 内存占用和 load factor
• 分析与结论

结论

简单说，没有一个哈希表适合所有 workload。应该选哪一个，取决于主要操作是什么、key 长什么样、以及可用内存有多少。如果查询占主导，并且表构造一次后主要用于查询，那么 perfect hash table fph::DynamicFphMap 很难被超过；如果 miss 很常见，fph::MetaFphMap 也值得考虑，代价是构造较慢。对于插入和查询混合的一般用途，absl::flat_hash_map 搭配 absl::Hash 是一个快速、紧凑且稳健的默认选择；ska::flat_hash_map 在数据还留在 cache 里时最快；如果频繁遍历，ankerl::unordered_dense_map 是更该优先考虑的选择。std::unordered_map 在大多数测试中都偏慢，主要价值是指针稳定性。

更完整的选择理由，以及各测试和各 workload 下的对比，可以看 分析与结论。

局限

资源独占

测试中，测试程序几乎可以独占所有计算机资源，尤其是 cache 资源。这在实际应用中相对少见。真实应用里，其他进程和任务可能会占用一部分 cache。因此在实际场景中，应该预期可用 cache 会更少。

warm cache 与 cold memory

测试中既没有做 warmup，也没有专门测试 cold start 场景。这里会在一段数据范围内反复测试某个操作很多次。因此，当操作次数远大于数据量时，可以认为大多数操作访问的是 warm cache；当操作次数小于数据量时，大多数操作访问的是 cold memory。在测试中受限于测试时间，数据量较小时，操作次数会远大于数据量；数据量较大时，操作次数会等于数据量。

庞大的测试空间

测试空间至少包含：

1

|hash table set| x |hash function set| x |data sets| x |operation set| x |hardware platform set| x |compiler set|

可以看到，可测试空间相当大。任何一个哈希表集合或哈希函数集合的增加，都会明显增加测试工作量。受时间和资源限制，这里只探索了一部分组合，还有许多组合和空间没有测试。

因此，如果要为某个具体用途选择最合适的哈希表和哈希函数，仍然应该在实际应用场景里做真实测试。

后记

这个 hash table benchmark 系列前后拖了至少四年。第一版数据 2022 年就有了，当时 M1 Max 还是很新的 CPU，现在 M5 都出来了。之所以花了这么长时间，是因为整理这么多图表和分析实在太繁琐了。我大概 2022 年到 2023 年间就完成了主体文章的撰写，但是很多收尾工作因为懒一直没做。并且由于这件事一直拖着，博客也陷入了 head-of-line blocking 的境地：总想着“我还没有完成这个系列的文章”，于是一直没有更新其他文章。

这几年里，很多东西都变了。CPU 更新了很多代，也有了一些新的 hash function / hash table 面世， LLM 技术也在这段时间飞速发展。这些博客里讲的很多东西可能已经有些过时了。只能感叹一句，逝者如斯夫，不舍昼夜。

不管这个评测系列的文章质量如何，我决定结束迭代，就此发出吧。