每秒十亿次查表的完美哈希：把字符串查找压到五个周期
来源：lemire.me — 2026-10-26
📋 概述
当键在写代码时就已经确定，运行时为处理碰撞付出的代价全是浪费。Daniel Lemire 介绍了与微软 Francisco Geiman Thiesen 合作的 C++23 单头文件库：用 constexpr 在编译期搜索完美哈希函数，运行时算哈希只要四条指令，再用 16 字节向量比较一次完成键校验。在 Apple M3 Max 上查 20 个 HTTP 头名约 1.3 纳秒（约 5 个周期），gperf 要 7.7 纳秒，Abseil flat_hash_map 要 10.9 纳秒，std::unordered_map 要 16.6 纳秒。在 M4 上处理 URL 协议集时突破每秒十亿次。
🔑 核心要点
- 槽位算得极便宜：长度加上字符关联表里几个值再按 2 的幂取模，取模就是一次按位与
- 关联值靠贪心搜索：按字符覆盖的键数排序，逐个试 0、1、2… 直到不冲突，定了就不改
- 字符串比较也向量化：无条件读 16 字节，用 shuffle 把键尾之后清零，一次比较搞定整个键
- 越界读的处理很讲究：只在与页尾相距不足 16 字节时走慢路径，把多个难预测分支换成一个几乎总走同一方向的分支
- 实测差距明显：20 个 HTTP 头名上比标准库快十三倍，gperf 慢约六倍，flat_hash_map 慢约八倍
- 为什么标准库慢：C++ 标准实质上要求链式哈希，要整串哈希、跟指针、走链表，而这段代码每周期能提交八条以上指令
- 局限说得很直白：完美哈希不能判存在性，命中槽位后仍必须做一次键比较
💡 金句
If your keys are known at compile time, you should not pay for collision handling at runtime. A perfect hash function gets you down to one comparison.
👍 0
👎 0
← 返回 Lobsters 首页