---
title: "C++ 编译期完美哈希：键集已知时，查找可以不必为冲突买单 - Angryecho"
description: "很多软件一辈子都在做「字符串 → 取值」：Web 服务器认 HTTP 方法与头名，URL 解析器认协议，编译器认关键字。C++ 里默认做法常是塞进 std::unordered_map。能用，但键在写代码时就已经定死、运行期也不会变——却仍要按「随时可变」付账：整串哈希、选桶、跟指针、比较，有时还要沿着链表走。"
canonical_url: "https://www.angryecho.com/c/hou_duan_kai_fa/p/P2TBBrMtLagmYyOS5eEUc"
meta:
  "og:description": "很多软件一辈子都在做「字符串 → 取值」：Web 服务器认 HTTP 方法与头名，URL 解析器认协议，编译器认关键字。C++ 里默认做法常是塞进 std::unordered_map。能用，但键在写代码时就已经定死、运行期也不会变——却仍要按「随时可变」付账：整串哈希、选桶、跟指针、比较，有时还要沿着链表走。"
  "og:image": "https://www.angryecho.com/_og/d/c_Post%2Ctitle_~5ZCQ5qe9572R%2Cdescription_~5ZCQ5qe95LiA5LiL77yM5bCx5LiK5ZCQ5qe9572R44CC%2CpostId_P2TBBrMtLagmYyOS5eEUc%2Crevision_~MjAyNi0xMC0zMVQwMjo1NTo1OC4wNzkwMzZa%2Cp_Ii9jL2hvdV9kdWFuX2thaV9mYS9wL1AyVEJCck10TGFnbVl5T1M1ZUVVYyI%2Cs_JhDqovTw-Adj5zp1.png"
  "og:image:height": "630"
  "og:image:type": image/png
  "og:image:width": "1200"
  "og:title": "C++ 编译期完美哈希：键集已知时，查找可以不必为冲突买单"
---

> Index of every page on this site: [llms.txt](https://www.angryecho.com/llms.txt)

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

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

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

## 完美哈希是什么

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

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

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

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

## 在 C++ 里怎么写

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

```cpp
#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 头名约例：

| 方案 | 约每次查找 |
| --- | --- |
| perfect\_hash（本文库） | **1.3 ns**（约 5 周期） |
| 经典 gperf | 7.7 ns |
| Abseil `flat_hash_map` | 10.9 ns |
| `std::unordered_map` | 16.6 ns |

多组键集（从约 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++](https://lemire.me/blog/2026/10/26/billion-query-per-second-lookup-tables-in-c/)，Daniel Lemire（合作：Francisco Geiman Thiesen），2026年10月26日。查询日：2026年10月28日。

> \[2] [ConstexprCore/perfect\_hash](https://github.com/ConstexprCore/perfect_hash)，GitHub。查询日：2026年10月28日。

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

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

排序方式 :

### **成为第一条评论！**

Nobody's responded to this post yet. Add your thoughts and get the conversation going.

```json
{"@context":"https://schema.org","@graph":[{"@id":"https://www.angryecho.com/c/hou_duan_kai_fa/p/P2TBBrMtLagmYyOS5eEUc#post","@type":"DiscussionForumPosting","commentCount":0,"dateModified":"2026-10-31T02:55:58.079Z","datePublished":"2026-10-28T01:39:00.000Z","description":"很多软件一辈子都在做「字符串 → 取值」：Web 服务器认 HTTP 方法与头名，URL 解析器认协议，编译器认关键字。C++ 里默认做法常是塞进 std::unordered_map。能用，但键在写代码时就已经定死、运行期也不会变——却仍要按「随时可变」付账：整串哈希、选桶、跟指针、比较，有时还要沿着链表走。","headline":"C++ 编译期完美哈希：键集已知时，查找可以不必为冲突买单","isPartOf":"https://www.angryecho.com/c/hou_duan_kai_fa","mainEntityOfPage":"https://www.angryecho.com/c/hou_duan_kai_fa/p/P2TBBrMtLagmYyOS5eEUc","text":"很多软件一辈子都在做「字符串 → 取值」：Web 服务器认 HTTP 方法与头名，URL 解析器认协议，编译器认关键字。C++ 里默认做法常是塞进 std::unordered_map。能用，但键在写代码时就已经定死、运行期也不会变——却仍要按「随时可变」付账：整串哈希、选桶、跟指针、比较，有时还要沿着链表走。\n\nDaniel Lemire 在 2026 年 10 月 26 日的博文里，和 Microsoft 的 Francisco Geiman Thiesen 一起，介绍了单头文件库 ConstexprCore/perfect_hash：在 C++23 constexpr 下于编译期构造完美哈希（perfect hash），运行期尽量做到一次比较、无冲突处理。相关工作在 P99 CONF 2026 做过分享。\n\n完美哈希是什么\n\n哈希把键映射到槽位；两键落同一槽就是冲突，哈希表的复杂与变慢多半由此而来。若事先知道全部键，可以专门为这组键构造「永不冲突」的哈希函数——GNU gperf 自 1989 年起就在干这件事：喂关键字列表，吐出 C 代码。\n\n他们沿用类似思路，槽位形如：\n\nslot = (length + asso[key[i]] + asso[key[j]] + ...) % table_size\n\n用键长，加上关联表 asso 里按少数选定字符位置取出的小整数；表长常取 2 的幂，取模变成按位与。查找时算槽、与槽里那一个键比较；不在集合里的键比一次即可判定。关联值用贪心、有界搜索填出——有界很重要，因为全在编译期做，编译器限制 constexpr 工作量。\n\n在 C++ 里怎么写\n\n库让你写普通 C++23，不必另跑外部工具：\n\n#include \u003CConstexprCore/perfect_hash.h>\nusing namespace ConstexprCore;\nenum class Method { GET, POST, PUT, DELETE, PATCH };\nconstexpr auto methods = make_perfect_map\u003C\n    kv\u003C\"GET\",    Method::GET>,\n    kv\u003C\"POST\",   Method::POST>,\n    kv\u003C\"PUT\",    Method::PUT>,\n    kv\u003C\"DELETE\", Method::DELETE>,\n    kv\u003C\"PATCH\",  Method::PATCH>\n>();\n\n映射是编译期常量；运行期算哈希可少到约四条指令量级。比较字符串时，他们用 16 字节向量寄存器一次载入并比较（键在编译期零填充；靠近页末则走慢路径），把「逐字节循环 + 难预测分支」换成「几乎总是同一方向」的单次分支。\n\n有多快（作者环境）\n\n作者在 Apple M3 Max、AppleClang 15 上、键随机顺序查找，报告每次查找耗时。20 个标准 HTTP 头名约例：\n\n\n\n\n\n\n\n方案\n\n\n\n约每次查找\n\n\n\n\n\nperfect_hash（本文库）\n\n\n\n1.3 ns（约 5 周期）\n\n\n\n\n\n经典 gperf\n\n\n\n7.7 ns\n\n\n\n\n\nAbseil flat_hash_map\n\n\n\n10.9 ns\n\n\n\n\n\nstd::unordered_map\n\n\n\n16.6 ns\n\n多组键集（从约 6 个 URL 协议到 S&P 100 的 100 个 ticker）大致落在 1.2–2 ns/次；相对 gperf 约 3–6 倍，相对 unordered_map 约 7–13 倍（个别集合如 JS 保留字相对 gperf 差距更大）。在 Apple M4、URL 协议场景，作者称可超过 每秒十亿次查找。\n\n这些数字来自作者机器与基准脚本，不能外推为「所有硬件、所有键集、所有负载都完胜」；库能力与接口以仓库为准。\n\n适用边界\n\n\n\n\n\n适合：编译期已知、运行期不变的中小键集（HTTP 方法/头名、协议名、关键字等）。\n\n\n\n不适合：键集频繁变化、必须动态插入删除的场景——那仍是通用哈希表的活。\n\n\n\n许可：仓库为 MIT。查询日 2026年10月28日，GitHub 约 91 Star、最近可见 Release 活动至 v0.3.0（2026年10月26日推送）。\n\n\n\n说明：基准数字据 Daniel Lemire 博文所述 Apple M3 Max / M4 环境；不同 CPU、编译器与键集结果会变。勿写成「任意场景均达十亿 QPS」。\n\n来源\n\n\n\n[1] Billion-query-per-second lookup tables in C++，Daniel Lemire（合作：Francisco Geiman Thiesen），2026年10月26日。查询日：2026年10月28日。\n\n\n\n[2] ConstexprCore/perfect_hash，GitHub。查询日：2026年10月28日。\n\n\n\n[3] Hacker News：https://news.ycombinator.com/item?id=50268325\n\n#完美哈希 #C++23 #ConstexprCore #DanielLemire #高性能 #查找表","url":"https://www.angryecho.com/c/hou_duan_kai_fa/p/P2TBBrMtLagmYyOS5eEUc","author":{"@type":"Person","name":"Timothy Sharkey","url":"https://www.angryecho.com/u/P7H10167154"},"interactionStatistic":[{"@type":"InteractionCounter","interactionType":"https://schema.org/LikeAction","userInteractionCount":0},{"@type":"InteractionCounter","interactionType":"https://schema.org/DislikeAction","userInteractionCount":0},{"@type":"InteractionCounter","interactionType":"https://schema.org/ViewAction","userInteractionCount":0},{"@type":"InteractionCounter","interactionType":"https://schema.org/ShareAction","userInteractionCount":0}]}]}
```

## Sitemap

See the full [sitemap](https://www.angryecho.com/sitemap.md) for all pages.