1. 什么是完美哈希

普通哈希函数面对任意输入，冲突无法避免，所以哈希表需要链表或探测序列来处理冲突。完美哈希针对的是一个事先完全已知、固定不变的 key 集合：既然知道全部 key，就可以专门为这批 key 找出一个函数，让它们落到互不相同的槽位上，一次冲突都没有。

术语 含义
完美哈希（PHF） 对集合 S 里的 n 个 key，h(k) 两两不同
最小完美哈希（MPHF） 在此基础上，值域正好是 [0, n)，表的大小就是 n，没有空槽

怎么"找"出这个函数

最朴素的做法：给哈希函数加一个种子参数 h(k, seed)，从 0 开始逐个试种子，直到 n 个 key 两两不冲突。

问题在于，随机函数把 n 个 key 映射到 n 个槽恰好不冲突的概率是 n!/nⁿ ≈ √(2πn)·e⁻ⁿ：

  • n = 4 时约为 9.4%，平均试十来次就能找到。
  • n = 100 时基本不可能找到。

实用的做法是两级分桶加位移，即 hash-and-displace，CHD 算法就属于这一类：

第一级：bucket = h0(key) % r        把 key 分进 r 个桶（每桶平均只有几个 key）
构造时：按桶从大到小处理，给每个桶单独找一个种子 d，
        让桶里所有 key 的 h(key, d) % n 都落在还空着的槽上，然后把 d 记在 seeds[bucket]
查找时：slot = h(key, seeds[h0(key) % r]) % n     两次哈希加一次数组访问

每个桶只有几个 key，给单个桶找种子很容易。存储开销只有 seeds 这一张小表，每个 key 大约只需要几个比特。

同一类工具还有：

  • gperf：GNU 的完美哈希生成器，输出 C 代码，编译器和解析器常用它来查关键字。
  • Rust 的 phf crate：用的是 CHD 算法。
  • 大规模静态数据集用的 BBHash、RecSplit、PTHash：可以对数十亿个 key 构造最小完美哈希，每个 key 只占两三个比特。

2. 为什么运行时不分配内存

这里的"不分配"指的是运行时不申请堆内存，不是说不占内存。所有数据都在编译期算好，存放在固定大小的数组里：

  • 变量是 constexpr 全局变量时，这些数组位于 .rodata。
  • 表的大小 N 是模板参数，编译期就已确定。

对比 std::unordered_map：

  • libstdc++ 的实现里，每个元素都是一个单独在堆上分配的节点，桶数组也要在堆上分配。
  • 程序启动时还要执行构造代码来插入元素，这属于动态初始化。

下面是一个极简的实现，用来说明原理。它用暴力方式找种子，只适合很小的 N：

#include <array>
#include <cstdint>
#include <string_view>
#include <utility>

constexpr uint32_t fnv1a(std::string_view s, uint32_t seed) {
    uint32_t h = 2166136261u ^ seed;
    for (unsigned char c : s) { h ^= c; h *= 16777619u; }
    return h;
}

template <std::size_t N>
struct PerfectMap {
    std::array<std::string_view, N> keys{};    // 按槽位排好的 key
    std::array<int, N> values{};
    uint32_t seed = 0;

    constexpr int find(std::string_view k) const {
        std::size_t i = fnv1a(k, seed) % N;     // 一次哈希
        return keys[i] == k ? values[i] : -1;   // 一次比较
    }
};

template <std::size_t N>
consteval PerfectMap<N> make(const std::array<std::pair<std::string_view, int>, N>& kv) {
    for (uint32_t seed = 0;; ++seed) {          // 在编译期试种子
        std::array<bool, N> used{};
        bool ok = true;
        for (auto& [k, v] : kv) {
            std::size_t i = fnv1a(k, seed) % N;
            if (used[i]) { ok = false; break; }
            used[i] = true;
        }
        if (!ok) continue;
        PerfectMap<N> m{};
        m.seed = seed;
        for (auto& [k, v] : kv) {
            std::size_t i = fnv1a(k, seed) % N;
            m.keys[i] = k;
            m.values[i] = v;
        }
        return m;
    }
}

constexpr auto methods = make<4>({{{"GET", 1}, {"POST", 2}, {"PUT", 3}, {"DELETE", 4}}});
static_assert(methods.find("POST") == 2);
static_assert(methods.find("PATCH") == -1);

查找时仍然必须比对 key。完美哈希只保证集合内部的 key 不冲突；一个不在集合里的 key（比如 "PATCH"）也会被映射到某个槽位上，只有比对之后才知道查不到。因此表里需要存 key 本身。如果调用方能保证只查集合里的 key，才可以省掉这一步。

frozen 库的用法大致如下（未实测）：

constexpr frozen::unordered_map<frozen::string, int, 4> methods = {
    {"GET", 1}, {"POST", 2}, {"PUT", 3}, {"DELETE", 4},
};
static_assert(methods.at("GET") == 1);   // 编译期查找也能用

3. 那岂不是不能增删？

对，不能增删。 这正是它的前提条件，不算缺陷。完美哈希函数是为这一批 key 专门找出来的：

  • 加一个新 key，它很可能和已有的 key 冲突，整个函数（种子表）就得重新构造。
  • 删一个 key 虽然不会造成冲突，但如果是最小完美哈希，就会留下一个空槽，表不再"最小"。

能做的和不能做的：

操作 能否做到
查找 能，最坏情况也是 O(1)：一次哈希加一次比较，没有冲突链或探测序列
修改已有 key 对应的值 表不是 const 时可以；constexpr 实例是只读的
增加或删除 key 不能，需要整体重建

适用的场景就是 key 集合固定不变的地方：

  • 编程语言的关键字表、词法分析器
  • HTTP 方法名、常见 header 名、协议操作码
  • 命令行子命令、配置文件字段名
  • 枚举和字符串之间的互相映射
  • 构建一次、之后只读的大规模索引，比如搜索引擎的词典、生物信息学里的 k-mer 索引。这类场景是在运行时构建一次，数据变化后再整体重建。

还有一个附带的好处：因为 key 集合固定，攻击者无法构造让集合内部 key 冲突的输入，天然免疫哈希洪水攻击。

需要增删时的替代方案

需求 选择
key 固定，追求最快查找 完美哈希（frozen、gperf）
key 固定且很少（十几个） 有序数组加二分查找（frozen::map、C++23 std::flat_map），甚至线性查找，速度未必比哈希慢
需要增删，并且想减少分配次数 开放寻址哈希表，比如 absl::flat_hash_map、boost::unordered_flat_map：所有元素存在一块连续数组里，不是每个元素一个节点，但扩容时仍然要分配
需要增删，并且完全不能分配 预先分配固定容量的开放寻址表，容量写死，满了就报错。嵌入式系统常这样做

上面的代码和 frozen 的用法都没有实测。如果需要，我可以把这段极简实现放到 dev 上，用 GCC 15 编译，确认 static_assert 能通过，并打印编译期找到的种子值。

取决于完美哈希是在什么时候构造的。编译期构造，就得重新编译；运行时构造，重启进程就够了；做成热加载，连重启都不需要。

方案 文件变了之后要做什么 优点 缺点
① 编译期构造（constexpr、frozen、gperf） 重新生成代码、重新编译、重新发布、重启 零启动开销；数据放在 .rodata，多进程共享 数据和代码版本绑死
② 启动时读文件，在运行时构造 重启进程 不用重新编译 每次启动都要重新构造，数据量大时启动变慢
③ 运行时构造，再加热加载 什么都不用做：检测到变化后，在后台构建新表，然后原子地替换 不停服 需要处理新旧两张表并存的问题
④ 离线构建成二进制文件，服务用 mmap 加载 离线工具重新生成文件，服务重新 mmap 后切换 加载几乎瞬间完成；页缓存由多个进程共享；构造的开销不落在服务身上 需要自己设计文件格式

完美哈希"不分配内存"说的是查找阶段。 在运行时构造时，构造过程会分配内存，构造完成后这张表只读，查找依然不分配。完美哈希本身的性质和"在编译期构造"是两件事，编译期构造只是其中一种用法。

怎么选

  • 数据和代码版本绑在一起、几乎不变：语言关键字、协议常量、枚举名称。用 ①，改了就改代码、发版本。
  • 数据随运营变化：词典、黑名单、路由表、配置项。用 ②、③ 或 ④，不应该为了数据变化去重新编译。

用 ① 时，也可以不把数据写死在源码里：让构建系统在编译时读取文件并生成代码，或者用 C23/C++26 的 #embed 把文件内容嵌入二进制。但文件变了仍然要重新编译。

③ 热加载的写法

核心是旧表只读，新表在后台构建，最后用一次原子替换，这和 RCU 是同一个思路：

struct Table { /* 种子表 + keys + values，构造完成后只读 */ };

std::atomic<std::shared_ptr<const Table>> g_table;   // C++20

// 查询线程
int lookup(std::string_view k) {
    auto t = g_table.load(std::memory_order_acquire);   // 拿到当前这张表的快照
    return t->find(k);                                  // 这次查询期间，表不会被释放
}

// 重载线程：由 inotify、SIGHUP 或定时检查 mtime 触发
void reload(const char* path) {
    auto fresh = std::make_shared<const Table>(build_from_file(path));  // 在后台慢慢构造
    g_table.store(std::move(fresh), std::memory_order_release);        // 一次原子替换
}   // 最后一个持有旧表的查询结束后，旧表自动释放

要注意三点：

  • 构造失败要保留旧表：新文件格式错误，或者只写了一半时，不要替换。
  • 读非常频繁时，引用计数本身会成为瓶颈：每次查询都要对同一个引用计数做一次原子加和一次原子减，多核之间会反复争抢这条缓存行，就是上一个问题里讲的 cache line bouncing。而且 libstdc++ 的 atomic<shared_ptr> 内部用锁实现，不是 lock-free。读极多的场景可以改用：
    • RCU（用户态库 liburcu）
    • hazard pointer
    • C++26 标准里的 <rcu> 和 <hazard_pointer>
  • 进程级的替代方案：nginx 的 reload 是启动新的 worker 进程加载新配置，老 worker 处理完手头的请求后退出，不需要在进程内做指针替换。

④ 离线构建加 mmap

这是"静态哈希表存在文件里"的经典做法。D. J. Bernstein 的 cdb（constant database）就是这样：文件格式本身就是一张哈希表，服务直接 mmap 过来查询。更新方式是把整个文件重新生成一遍，然后原子地替换。

更新流程必须是：

生成 data.new → fsync → rename("data.new", "data")     # rename 是原子的
服务收到通知 → mmap 新文件 → 原子替换指针 → munmap 旧映射

绝不能原地修改一个正在被 mmap 的文件：

  • 正在读的进程可能看到写了一半的数据。
  • 文件被截短后，访问超出文件末尾的映射页会触发 SIGBUS。

用 rename 替换时，旧文件的 inode 仍被旧映射引用，内容保持完整，直到 munmap 之后才会真正释放。

以上是设计层面的说明，没有实测。至于构造一个最小完美哈希具体要多长时间，取决于算法和 key 的数量，这里没有给出数值。

分成两类：一类只负责构造完美哈希函数，一类是完整的只读键值库。下面的项目、算法和空间数值是凭记忆整理的，没有查证最新的维护状态，也没有实测；空间开销随参数变化，只能作为量级参考。

一、只构造完美哈希函数的库

这类库只提供 key → [0, n) 下标这个映射。key 和 value 需要你自己存进数组，再用这个下标去访问。

库 语言 算法 每个 key 的空间（量级） 特点
CMPH C CHD、BDZ、BMZ、CHM、BRZ、FCH 约 2–3 bit 老牌库，Debian 里有 libcmph 包；自带 cmph 命令行工具，能直接从"每行一个 key"的文件构造，结果可以 cmph_dump/cmph_load 存取；多年没有新版本，但很稳定
BBHash C++，仅头文件 分层位图 约 3 bit 支持多线程构造，能处理数十亿 key，生物信息学领域用得多；支持保存和加载
PTHash C++17 改进的 hash-and-displace 约 2–4 bit 查询很快；支持外存构造（key 放不进内存时也能构造）
RecSplit（在 sux 库中） C++ 递归分割 约 1.6–1.8 bit 空间接近理论下界（约 1.44 bit/key）；构造比较慢
Sux4J Java GOV、RecSplit 等 — 作者和 sux 相同，是 Java 生态里的首选
boomphf / ptr_hash / ph Rust 分别对应 BBHash、PtrHash、FMPH — Rust 的 phf crate 主要用于编译期构造
go-mph 等 Go CHD — —

对比一下：gperf 是编译期的代码生成器，它输出 C 代码，所以数据一变就得重新编译。它属于上一问里的方案 ①，不在这一类。

用这类库时的三个注意点

  1. 不在集合里的 key 也会返回一个下标。 完美哈希函数只保证集合内部的 key 不冲突，查一个陌生的 key 会得到一个随机的合法下标。要判断 key 是否存在，有两种办法：
    • 在下标对应的位置存完整的 key，查到后比对一下。
    • 只存一个 8–16 位的指纹，按概率拒绝不存在的 key，误判率约为 2⁻ᵇⁱᵗˢ。
  2. 字符串 key 通常要先哈希成 64 位整数，BBHash 这类库要求这样。key 的数量达到十亿级时，64 位哈希本身就可能冲突，概率约为 n²/2⁶⁵，n = 10⁹ 时约 2.7%。这时要换 128 位哈希，或者在构造阶段检测到冲突后换种子重试。
  3. 启动流程： 
    读文件 → 把 key 哈希成 64 位 → 构造 MPHF → 按 mphf(key) 把 key/指纹和 value 放进数组
    构造好的函数加上两个数组就是一张只读表，可以直接接上上一问的热加载（原子替换指针）方案。更好的做法是离线构造好之后序列化到文件，服务启动时只需要加载，不需要重新构造。

二、完整的只读键值库

这类库自带文件格式：构建一次，只读查询，通常用 mmap 加载。它们用的不一定是严格意义上的完美哈希，但定位相同：key 集合固定，要更新就把整个文件重新生成，再原子地替换。

库 语言 结构 特点
cdb（D. J. Bernstein）/ tinycdb C 两级哈希表 经典的常量数据库；cdb_make 生成文件，查询时一到两次磁盘访问；原版用 32 位偏移，单个文件上限 4 GB
Sparkey（Spotify） C 日志文件加哈希索引 为"一次写入、大量读取"设计，用 mmap 加载
mtbl / LevelDB 的 SSTable C / C++ 有序表 不是哈希结构，但也是只读文件；支持范围查询

怎么选

情况 选择
key 数量在百万级以下，内存充足 最省事的是启动时读文件，建一个 absl::flat_hash_map，或者排好序的数组加二分查找。完美哈希不一定划算
key 数量达到亿级，内存紧张 BBHash、PTHash、RecSplit：每个 key 只需几个比特，外加你自己存的 value 数组
要一个现成的"只读键值文件" tinycdb、Sparkey
要一个用 C 写的、带命令行工具的通用方案 CMPH

完美哈希真正的优势在两个方面：极大规模下的内存占用，以及确定的单次查找，最坏情况也只要一次哈希、一次访问。在小规模数据上，普通的开放寻址哈希表通常就够快了。