CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”

Matt Kulukundis 逐步将标准链式哈希表改造成 Swiss Table：先移除节点指针和存储哈希的空间，接受开放寻址与删除标记的权衡；再以控制字节保存空闲状态和哈希指纹，用 SIMD 并行扫描 16 个槽位。实际收益需在多种负载、键大小和缓存状态下测量。演讲也强调 C++ API 易踩临时对象和查找陷阱，并讨论迁移、兼容和实验性布局。

英文字幕轨道 · 引文按字幕原文展示，可点时间戳回看片段。

视频章节 6

1. ▶ 1:45
   设计目标与测量背景
2. ▶ 3:34
   缓存与基准条件
3. ▶ 11:57
   链表到开放寻址的取舍
4. ▶ 18:35
   Swiss Table 的控制字节
5. ▶ 27:40
   查找与 SIMD 并行探测
6. ▶ 36:37
   性能图表、API 易用性与实验

具体观点与证据 4

哈希表优化必须同时比较收益与损失，减少间接访问可能增加扫描和重哈希成本。

依赖键类型、删除模式和容量复用方式，不存在全负载最佳设计。

this "what do we gain", "what do we lose"?

▶ 12:47–12:49 探索此观点 →

控制字节保存短哈希指纹，SIMD并行筛选候选位置，可减少访问实际值的次数。

讲述Swiss Table设计，仍要求哈希位熵分布良好。

You get 16 probe length in three instructions. It's amazing.

▶ 31:12–31:16 探索此观点 →

基准应覆盖缓存冷热、占用率、命中与键大小，单个基准不足以宣称最快。

演讲另用生产采样验证迁移收益，数字属于当时Google负载。

But without running the data once, how do you know what dimensions are inconsequential?

▶ 20:19–20:25 探索此观点 →

用户会依赖可观察的实现行为，演化数据结构需要主动防止依赖偶然顺序。

演讲用哈希随机化抑制迭代顺序依赖，但并未保证完全消除Hyrum定律。

they will rely upon it, given enough users.

▶ 5:27–5:32 探索此观点 →

补充字幕原文 2

移除节点结构可减少 find 和 insert 中的一次内存访问，但会带来迭代方式的变化。

We eliminate a memory interaction, on "find" and "insert".

▶ 12:43–12:47

SIMD 控制字节扫描可在少量机器指令中并行处理长达 16 个候选位置。

You get 16 probe length in three instructions

▶ 31:12–31:14

解读边界

性能数据来自 Google 的 C++ 负载与特定硬件、实现版本；讲者承认基准空间巨大，部分变体仍属实验，且为讲解会省略哈希函数细节。