C++ 编译期完美哈希：键集已知时，查找可以不必为冲突买单

很多软件一辈子都在做「字符串 → 取值」：Web 服务器认 HTTP 方法与头名，URL 解析器认协议，编译器认关键字。C++ 里默认做法常是塞进 std::unordered_map。能用，但键在写代码时就已经定死、运行期也不会变——却仍要按「随时可变」付账：整串哈希、选桶、跟指针、比较，有时还要沿着链表走。

Daniel Lemire 在 2026 年 10 月 26 日的博文里，和 Microsoft 的 Francisco Geiman Thiesen 一起，介绍了单头文件库 ConstexprCore/perfect_hash：在 C++23 constexpr 下于编译期构造完美哈希（perfect hash），运行期尽量做到一次比较、无冲突处理。相关工作在 P99 CONF 2026 做过分享。

完美哈希是什么

哈希把键映射到槽位；两键落同一槽就是冲突，哈希表的复杂与变慢多半由此而来。若事先知道全部键，可以专门为这组键构造「永不冲突」的哈希函数——GNU gperf 自 1989 年起就在干这件事：喂关键字列表，吐出 C 代码。

他们沿用类似思路，槽位形如：

slot = (length + asso[key[i]] + asso[key[j]] + ...) % table_size

用键长，加上关联表 asso 里按少数选定字符位置取出的小整数；表长常取 2 的幂，取模变成按位与。查找时算槽、与槽里那一个键比较；不在集合里的键比一次即可判定。关联值用贪心、有界搜索填出——有界很重要，因为全在编译期做，编译器限制 constexpr 工作量。

在 C++ 里怎么写

库让你写普通 C++23，不必另跑外部工具：

#include <ConstexprCore/perfect_hash.h>
using namespace ConstexprCore;
enum class Method { GET, POST, PUT, DELETE, PATCH };
constexpr auto methods = make_perfect_map<
    kv<"GET",    Method::GET>,
    kv<"POST",   Method::POST>,
    kv<"PUT",    Method::PUT>,
    kv<"DELETE", Method::DELETE>,
    kv<"PATCH",  Method::PATCH>
>();

映射是编译期常量；运行期算哈希可少到约四条指令量级。比较字符串时，他们用 16 字节向量寄存器一次载入并比较（键在编译期零填充；靠近页末则走慢路径），把「逐字节循环 + 难预测分支」换成「几乎总是同一方向」的单次分支。

有多快（作者环境）

作者在 Apple M3 Max、AppleClang 15 上、键随机顺序查找，报告每次查找耗时。20 个标准 HTTP 头名约例：

多组键集（从约 6 个 URL 协议到 S&P 100 的 100 个 ticker）大致落在 1.2–2 ns/次；相对 gperf 约 3–6 倍，相对 unordered_map 约 7–13 倍（个别集合如 JS 保留字相对 gperf 差距更大）。在 Apple M4、URL 协议场景，作者称可超过 每秒十亿次查找。

这些数字来自作者机器与基准脚本，不能外推为「所有硬件、所有键集、所有负载都完胜」；库能力与接口以仓库为准。

适用边界

• 适合：编译期已知、运行期不变的中小键集（HTTP 方法/头名、协议名、关键字等）。

• 不适合：键集频繁变化、必须动态插入删除的场景——那仍是通用哈希表的活。

• 许可：仓库为 MIT。查询日 2026年10月28日，GitHub 约 91 Star、最近可见 Release 活动至 v0.3.0（2026年10月26日推送）。

说明：基准数字据 Daniel Lemire 博文所述 Apple M3 Max / M4 环境；不同 CPU、编译器与键集结果会变。勿写成「任意场景均达十亿 QPS」。

来源

[1] Billion-query-per-second lookup tables in C++，Daniel Lemire（合作：Francisco Geiman Thiesen），2026年10月26日。查询日：2026年10月28日。

[2] ConstexprCore/perfect_hash，GitHub。查询日：2026年10月28日。

[3] Hacker News：https://news.ycombinator.com/item?id=50268325

#完美哈希 #C++23 #ConstexprCore #DanielLemire #高性能 #查找表