完美哈希：从理论到 gperf 实践

GCC 和 Clang 的词法分析器面对一个看似简单的问题：给定源代码中的一个标识符，判断它是不是语言的保留关键字。C11 有 44 个关键字，C++ 有 90 多个，Go 有 25 个。

最朴素的做法是 strcmp 遍历关键字表——O(k) 次比较，其中 k 是关键字数量。排序后二分查找可以做到 O(log k)。用哈希表呢？期望 O(1)，但普通哈希表有冲突链，最坏情况不可控。

有没有一种哈希函数，对于这组已知的键，保证零冲突？

有。这就是完美哈希（Perfect Hashing）。GCC 用 gperf 为每种语言的关键字集合生成完美哈希函数——查找时间严格 O(1)，没有任何条件。

本文从理论基础讲起，覆盖 FKS 方案、最小完美哈希（MPHF）、CHD 算法，到 gperf 的工程实践，最后给出完整的 C 实现。

一、什么是完美哈希

定义

给定一个已知的、静态的键集合 \(S = \{k_1, k_2, \ldots, k_n\}\)，完美哈希函数（Perfect Hash Function, PHF）是一个函数 \(h: U \to [0, m)\)，使得：

\[\forall i \neq j: h(k_i) \neq h(k_j)\]

即 \(h\) 在 \(S\) 上没有任何冲突。

如果进一步要求 \(m = n\)（哈希值恰好覆盖 \([0, n)\) 的每个位置），则称为最小完美哈希函数（Minimal Perfect Hash Function, MPHF）。

静态 vs 动态

完美哈希的前提是键集合在构造时就完全已知，之后不再变化。这与通用哈希表（支持动态插入删除）有本质区别：

特性	完美哈希	通用哈希表
键集合	静态，构造时完全已知	动态，运行时增删
冲突	零冲突，确定性 O(1) 查找	有冲突，期望 O(1) 查找
空间利用率	可达到 100%（MPHF）	通常需要 50-80% 空余
构造时间	O(n) 到 O(n log n)	在线，每次插入 O(1) 摊还
适用场景	关键字表、静态路由、只读字典	通用键值存储

关键认识：完美哈希不是”更好的哈希表”，而是一个完全不同的问题——静态字典问题（Static Dictionary Problem）。

二、FKS 两级方案

1984 年，Fredman、Komlos 和 Szemeredi 提出了第一个理论上最优的完美哈希方案（FKS scheme），实现了 O(n) 空间、O(1) 最坏情况查找。

核心思想

如果只有一个哈希函数，要保证 n 个键无冲突，表大小至少需要 \(\Omega(n^2)\)（生日悖论）。但如果允许两级结构，空间可以降到 O(n)。

第一级：用一个哈希函数 \(h\) 将 n 个键分到 m 个桶中。允许冲突——桶 \(i\) 中可能有 \(b_i\) 个键。

第二级：每个桶 \(i\) 使用独立的哈希函数 \(h_i\)，将桶内的 \(b_i\) 个键映射到大小为 \(s_i = b_i^2\) 的子表中。因为子表大小是桶内键数的平方，由生日悖论的逆向分析，随机选一个 \(h_i\) 就有至少 1/2 的概率无冲突。

这个结构如下图所示：

空间分析：为什么 O(n) 就够了

总空间 = \(\sum_{i=0}^{m-1} s_i = \sum_{i=0}^{m-1} b_i^2\)。

关键问题：\(\sum b_i^2\) 有多大？

将 n 个球随机投入 m 个桶，每个球独立均匀地落入某个桶。设 \(b_i\) 是桶 \(i\) 中的球数。

\[E\left[\sum_{i=0}^{m-1} b_i^2\right] = \sum_i E[b_i^2] = \sum_i \left(\text{Var}[b_i] + (E[b_i])^2\right)\]

每个 \(b_i\) 服从参数为 \((n, 1/m)\) 的二项分布：

\[E[b_i] = n/m, \quad \text{Var}[b_i] = n(1-1/m)/m\]

因此：

\[E\left[\sum b_i^2\right] = m \cdot \left(\frac{n(1-1/m)}{m} + \frac{n^2}{m^2}\right) = n - \frac{n}{m} + \frac{n^2}{m}\]

当 \(m = n\) 时：

\[E\left[\sum b_i^2\right] = n - 1 + n = 2n - 1\]

空间期望是 O(n)。

构造算法

FKS 的构造分三步：

FKS-Build(S):
  1. 选 m = n
  2. 从全域哈希族中随机选 h，计算每个桶的大小 b_i
     如果 sum(b_i^2) >= 4n，重新选 h（期望 2 次尝试）
  3. 对每个非空桶 i:
     s_i = b_i^2
     从全域哈希族中随机选 h_i
     如果桶内有冲突，重新选 h_i（期望 2 次尝试）
  4. 存储 h, 以及每个桶的 (h_i, s_i, offset_i, subtable_i)

查找

FKS-Lookup(x):
  1. j = h(x) mod m           // 第一级哈希
  2. pos = h_j(x) mod s_j     // 第二级哈希
  3. if subtable_j[pos] == x:
       return found
     else:
       return not found

恰好 2 次哈希计算 + 2 次内存访问。最坏情况 O(1)。

全域哈希族

FKS 需要从全域哈希族（Universal Hash Family）中选择哈希函数。经典的 Carter-Wegman 族：

\[h_{a,b}(x) = ((ax + b) \bmod p) \bmod m\]

其中 \(p\) 是大于 \(|U|\) 的质数，\(a \in \{1, \ldots, p-1\}\)，\(b \in \{0, \ldots, p-1\}\)。

这个族是 2-universal 的：对任意 \(x \neq y\)，

\[\Pr[h(x) = h(y)] \leq 1/m\]

三、最小完美哈希（MPHF）

FKS 方案空间是 O(n)，但常数因子较大——每个键需要存储二级哈希函数的参数和偏移量。对于大规模只读字典，我们希望空间尽可能小。

定义和空间下界

MPHF 将 n 个键双射到 \([0, n)\)。由信息论下界：

存在 \(n!\) 种不同的双射。要编码选择了哪一种，至少需要：

\[\log_2(n!) \approx n \log_2 n - n \log_2 e\]

但这是编码双射本身。如果只要求能计算 \(h(k_i)\) 而不需要恢复整个双射，下界可以更紧。

Mehlhorn 和 Czech 等人证明了 MPHF 的空间下界约为：

\[\frac{n \log_2 e}{1} \approx 1.44n \text{ bits}\]

即每个键至少需要约 1.44 比特的空间来描述哈希函数。这是一个非常紧的下界——一个”完美”的 MPHF 算法，1000 万个键只需要约 1.8 MB 的描述空间。

实际算法的空间对比

算法	bits/key	构造时间	查找时间
FKS（标准）	~40-60	O(n)	O(1)，2 次访问
CHD	2.07	O(n)	O(1)，2 次访问
BBHash	3.0-3.5	O(n)	O(1)，~1.5 次访问
RecSplit	1.56	O(n log n)	O(1)
理论下界	1.44	-	-

CHD 和 RecSplit 已经非常接近理论下界。

四、CHD 算法：实用的 MPHF 构造

CHD（Compress, Hash, Displace）由 Belazzougui、Botelho 和 Dietzfelbinger 在 2009 年提出，是目前工程实践中最常用的 MPHF 算法之一。

算法思想

CHD 的核心是 hash-displace-compress 三步法：

Hash：用两个哈希函数 \(f\) 和 \(g\) 将每个键映射到一对值 \((f(k), g(k))\)。\(f\) 将键分到 \(r\) 个桶中，\(g\) 给出一个辅助哈希值。
Displace：对每个桶 \(i\)，找到一个位移值 \(d_i\)，使得该桶内所有键 \(k\) 的最终位置 \((g(k) + d_i) \bmod n\) 互不冲突，且不与已分配位置冲突。
Compress：将位移数组 \(d[0..r)\) 用紧凑编码压缩存储。

详细构造过程

CHD-Build(S, n):
  输入: n 个键的集合 S
  输出: MPHF 描述 (f, g, d[0..r))

  1. 选择桶数 r = n / lambda (lambda 约 5-7)
  2. 用 f 将键分到 r 个桶: bucket[i] = {k in S : f(k) = i}
  3. 将桶按大小从大到小排序
  4. 初始化 occupied[0..n) = false
  5. 对每个桶 i（从大到小）:
     a. 尝试 d = 0, 1, 2, ...
     b. 对桶内每个键 k，计算 pos = (g(k) + d) mod n
     c. 如果所有 pos 都未被占用（occupied[pos] == false）:
        d[i] = d
        标记所有 pos 为 occupied
        break
  6. 压缩 d[] 数组

为什么有效

从大桶开始处理是关键。大桶有更多键要安放，如果留到后面，可能找不到合适的 displacement。先处理大桶时，表还很空，容易找到合法的 \(d_i\)。

当 \(r \approx n/5\) 时，大多数桶只有 4-6 个键。对于这样小的桶，随机尝试位移值时，成功概率很高——期望只需少量尝试。

总构造时间 O(n)，查找时间 O(1)：

CHD-Lookup(x):
  1. i = f(x)           // 确定桶号
  2. pos = (g(x) + d[i]) mod n  // 计算最终位置
  3. return pos

C 伪代码

typedef struct {
    uint64_t seed_f;       // 第一个哈希函数的种子
    uint64_t seed_g;       // 第二个哈希函数的种子
    uint32_t n;            // 键的数量
    uint32_t r;            // 桶的数量
    uint16_t *displace;    // 位移数组 d[0..r)
} chd_mphf_t;

uint32_t chd_lookup(const chd_mphf_t *ph, uint64_t key)
{
    uint32_t bucket = hash(key, ph->seed_f) % ph->r;
    uint32_t h2     = hash(key, ph->seed_g);
    return (h2 + ph->displace[bucket]) % ph->n;
}

查找只需要：1 次除法取模（确定桶）+ 1 次数组访问（读取 displacement）+ 1 次加法取模（最终位置）。非常 cache-friendly。

五、gperf：编译器的完美哈希生成器

gperf 是 GNU 项目中一个经典工具，专门为小规模、静态的字符串集合生成完美哈希函数。它是编译器实现中的标准工具——GCC 用它来生成 C/C++ 关键字的查找函数。

基本用法

假设要为一门简单语言的关键字生成完美哈希。首先创建输入文件：

%{
/* keywords.gperf - 示例关键字集合 */
#include <string.h>
%}
%language=ANSI-C
%define lookup-function-name keyword_lookup
%define hash-function-name keyword_hash
%readonly-tables
%enum
%struct-type
struct keyword_entry { const char *name; int token_id; };
%%
if,        TOKEN_IF
else,      TOKEN_ELSE
while,     TOKEN_WHILE
for,       TOKEN_FOR
return,    TOKEN_RETURN
int,       TOKEN_INT
char,      TOKEN_CHAR
void,      TOKEN_VOID
struct,    TOKEN_STRUCT
const,     TOKEN_CONST
static,    TOKEN_STATIC
break,     TOKEN_BREAK
continue,  TOKEN_CONTINUE
switch,    TOKEN_SWITCH
case,      TOKEN_CASE
default,   TOKEN_DEFAULT
%%

运行 gperf：

gperf keywords.gperf > keywords.c

生成代码分析

gperf 生成的 C 代码通常包含以下部分：

/* 1. 关联值表（asso_values）
 * 将字符映射到哈希贡献值 */
static const unsigned char asso_values[] = {
    /* 256 个条目，每个 ASCII 字符一个 */
    33, 33, 33, 33, 33, 33, 33, 33, /* ... */
    /* 'a' -> 某个值, 'b' -> 某个值, ... */
};

/* 2. 哈希函数
 * 通常基于字符串长度 + 选定位置的字符 */
static unsigned int
keyword_hash(const char *str, size_t len)
{
    static const unsigned char asso_values[] = { /* ... */ };
    return len + asso_values[(unsigned char)str[0]]
               + asso_values[(unsigned char)str[len - 1]];
}

/* 3. 有序关键字表 */
static const struct keyword_entry wordlist[] = {
    {"",0}, {"",0},  /* 空槽 */
    {"if", TOKEN_IF},
    {"int", TOKEN_INT},
    {"for", TOKEN_FOR},
    /* ... 按哈希值排序 ... */
};

/* 4. 查找函数 */
const struct keyword_entry *
keyword_lookup(const char *str, size_t len)
{
    if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH) {
        unsigned int key = keyword_hash(str, len);
        if (key <= MAX_HASH_VALUE) {
            const char *s = wordlist[key].name;
            if (*str == *s && !strcmp(str + 1, s + 1))
                return &wordlist[key];
        }
    }
    return NULL;
}

gperf 的哈希策略

gperf 使用的哈希函数结构是：

\[h(s) = \text{len}(s) + \sum_{i \in \text{positions}} \text{asso}[s[i]]\]

其中 positions 是字符串中选定的字符位置（通常是开头和结尾几个字符），asso 是关联值表。

gperf 的核心工作是搜索一组关联值，使得所有关键字的哈希值互不相同。这本质上是一个约束满足问题。gperf 使用一种基于图着色的算法来求解。

在 GCC 中的实际应用

GCC 的 C 前端（gcc/c-family/c-common.cc）使用 gperf 生成的代码来识别 C/C++ 关键字。词法分析器（lexer）扫描到一个标识符后：

1. 计算字符串长度 len
2. 调用 keyword_hash(str, len) 得到哈希值 h
3. 比较 wordlist[h].name 与 str
4. 匹配则返回对应的 token 类型

这比用 switch-case 或二分查找更高效，尤其是关键字数量较多时。GCC 的 C++ 前端有 90 多个关键字，完美哈希避免了任何多余的比较。

gperf 的局限

gperf 适合的场景有明确边界：

键集合小（几十到几百个字符串）
键在编译时已知
键是字符串类型

对于大规模数据（百万级以上的键），gperf 的搜索算法可能很慢或失败。此时应该转向 CHD、BBHash 等 MPHF 算法。

六、BBHash 和 RecSplit：现代 MPHF

BBHash

BBHash（2017）是一种工程友好的 MPHF 算法，思路极其简洁：

BBHash-Build(S):
  1. 用哈希函数 h1 将所有键映射到 [0, gamma*n)
  2. 找出没有冲突的位置（只有一个键映射到该位置的）
     这些键的 MPHF 值已确定
  3. 将有冲突的键收集起来，作为残余集合 S'
  4. 对 S' 重复步骤 1-3，用不同的哈希函数 h2，映射到新的范围
  5. 重复直到所有键都被安放

每一轮大约能安放 \(e^{-1} \approx 37\%\) 的键（由泊松分布，桶大小为 1 的概率是 \(1/e\)）。经过约 \(\log_{e/(e-1)} n\) 轮后，所有键被安放。

BBHash 的优势是： - 实现极其简单（约 200 行 C++） - 天然可并行化（每轮独立） - 空间约 3.0-3.5 bits/key

缺点是离理论下界还有距离。

RecSplit

RecSplit（2019，由 Esposito、Graf 和 Vigna 提出）是目前最接近理论下界的实用 MPHF 算法。

核心思想是递归分裂：

RecSplit-Build(S, [lo, hi)):
  如果 |S| <= leaf_size:
    暴力搜索一个种子 s，使得 h_s 将 S 双射到 [lo, hi)
    存储 s
    return
  
  // 分裂
  找到种子 s，使得 h_s 将 S 大致均匀地分成两半 S1, S2
  mid = lo + |S1|
  RecSplit-Build(S1, [lo, mid))
  RecSplit-Build(S2, [mid, hi))
  存储 s

通过精心选择分裂参数（split factor、leaf size），RecSplit 可以达到 1.56 bits/key——非常接近 1.44 的理论下界。

RecSplit 的代价是构造时间较长（O(n log n)），但查找仍然是 O(1)。

MPHF 算法选型

                  空间（bits/key）
                  |
              5.0 +
                  |
              4.0 +                BBHash(gamma=2)
                  |
              3.0 +          BBHash(gamma=1)
                  |
              2.0 +   CHD
                  |
              1.5 +        RecSplit
                  |
              1.44+  --- 理论下界 ---
                  |
              1.0 +
                  +---+---+---+---+----> 构造时间
                  快          慢

选型建议:
  - 需要极致空间: RecSplit (1.56 bits/key)
  - 均衡选择:     CHD (2.07 bits/key, 构造快)
  - 实现简单:     BBHash (3+ bits/key, 200 行代码)

七、完整 C 实现：FKS 两级完美哈希

下面给出一个完整的、可编译运行的 FKS 两级完美哈希实现。为了可读性，使用简单的全域哈希函数，处理 64 位整数键。

/*
 * fks.c - FKS two-level perfect hashing implementation
 *
 * Build:  gcc -O2 -o fks fks.c
 * Run:    ./fks
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

/* ---- 全域哈希 ---- */

/* 大质数，用于 Carter-Wegman 哈希族 */
#define PRIME 0x7FFFFFFFFFFFFFFDULL  /* 2^63 - 3, a prime */

typedef struct {
    uint64_t a;
    uint64_t b;
} hash_params_t;

static uint64_t universal_hash(uint64_t key, hash_params_t p, uint32_t m)
{
    /* h(x) = ((a*x + b) mod prime) mod m */
    __uint128_t val = (__uint128_t)p.a * key + p.b;
    uint64_t reduced = (uint64_t)(val % PRIME);
    return reduced % m;
}

static hash_params_t random_hash_params(void)
{
    hash_params_t p;
    p.a = ((uint64_t)rand() << 32 | rand()) % (PRIME - 1) + 1;
    p.b = ((uint64_t)rand() << 32 | rand()) % PRIME;
    return p;
}

/* ---- 二级桶结构 ---- */

typedef struct {
    hash_params_t  h;          /* 二级哈希参数 */
    uint32_t       size;       /* 子表大小 s_i = b_i^2 */
    uint32_t       offset;     /* 子表在全局数组中的偏移 */
} bucket_t;

/* ---- FKS 完美哈希表 ---- */

typedef struct {
    hash_params_t  h1;         /* 第一级哈希参数 */
    uint32_t       m;          /* 桶数 = n */
    uint32_t       n;          /* 键数 */
    bucket_t      *buckets;    /* 桶数组 */
    uint64_t      *table;      /* 全局子表存储 */
    uint32_t       table_size; /* 全局子表总大小 */
} fks_t;

/* 检查一组键在给定哈希参数和表大小下是否无冲突 */
static int check_no_collision(const uint64_t *keys, uint32_t count,
                              hash_params_t h, uint32_t size,
                              uint64_t *subtable)
{
    uint32_t i;
    /* 清空子表 */
    for (i = 0; i < size; i++)
        subtable[i] = UINT64_MAX;

    for (i = 0; i < count; i++) {
        uint32_t pos = (uint32_t)universal_hash(keys[i], h, size);
        if (subtable[pos] != UINT64_MAX)
            return 0;  /* 冲突 */
        subtable[pos] = keys[i];
    }
    return 1;  /* 无冲突 */
}

/* 构造 FKS 完美哈希表 */
fks_t *fks_build(const uint64_t *keys, uint32_t n)
{
    fks_t *fks = (fks_t *)calloc(1, sizeof(fks_t));
    fks->n = n;
    fks->m = n;  /* 桶数 = 键数 */

    /* 临时数组：每个桶中的键 */
    uint64_t **bucket_keys = (uint64_t **)calloc(n, sizeof(uint64_t *));
    uint32_t *bucket_count = (uint32_t *)calloc(n, sizeof(uint32_t));
    uint32_t *bucket_cap   = (uint32_t *)calloc(n, sizeof(uint32_t));

    /* 第一级：反复选哈希函数，直到 sum(b_i^2) < 4n */
    uint32_t sum_sq;
    int attempts = 0;
    do {
        attempts++;
        fks->h1 = random_hash_params();

        /* 清空桶 */
        for (uint32_t i = 0; i < n; i++)
            bucket_count[i] = 0;

        /* 分桶 */
        for (uint32_t i = 0; i < n; i++) {
            uint32_t b = (uint32_t)universal_hash(keys[i], fks->h1, n);
            if (bucket_count[b] >= bucket_cap[b]) {
                bucket_cap[b] = bucket_cap[b] ? bucket_cap[b] * 2 : 4;
                bucket_keys[b] = (uint64_t *)realloc(
                    bucket_keys[b], bucket_cap[b] * sizeof(uint64_t));
            }
            bucket_keys[b][bucket_count[b]++] = keys[i];
        }

        /* 计算 sum(b_i^2) */
        sum_sq = 0;
        for (uint32_t i = 0; i < n; i++)
            sum_sq += bucket_count[i] * bucket_count[i];

    } while (sum_sq >= 4 * n);

    printf("Level 1: found good hash after %d attempts, "
           "sum(b_i^2) = %u (threshold %u)\n",
           attempts, sum_sq, 4 * n);

    /* 分配桶元数据 */
    fks->buckets = (bucket_t *)calloc(n, sizeof(bucket_t));

    /* 计算每个桶的子表大小和偏移 */
    uint32_t total = 0;
    for (uint32_t i = 0; i < n; i++) {
        uint32_t bi = bucket_count[i];
        fks->buckets[i].size = bi * bi;  /* s_i = b_i^2 */
        fks->buckets[i].offset = total;
        total += bi * bi;
    }
    fks->table_size = total;
    fks->table = (uint64_t *)malloc(total * sizeof(uint64_t));
    for (uint32_t i = 0; i < total; i++)
        fks->table[i] = UINT64_MAX;  /* 标记空槽 */

    /* 第二级：为每个非空桶找到无冲突的哈希函数 */
    for (uint32_t i = 0; i < n; i++) {
        if (bucket_count[i] == 0) continue;

        uint32_t si = fks->buckets[i].size;
        uint64_t *subtable = &fks->table[fks->buckets[i].offset];
        int found = 0;

        for (int trial = 0; trial < 1000; trial++) {
            hash_params_t h2 = random_hash_params();
            if (check_no_collision(bucket_keys[i], bucket_count[i],
                                   h2, si, subtable)) {
                fks->buckets[i].h = h2;
                found = 1;
                break;
            }
        }
        if (!found) {
            fprintf(stderr, "ERROR: failed to find level-2 hash "
                    "for bucket %u (size %u)\n", i, bucket_count[i]);
            /* 实际中不应该发生——b_i^2 的空间足够 */
        }
    }

    /* 清理临时数据 */
    for (uint32_t i = 0; i < n; i++)
        free(bucket_keys[i]);
    free(bucket_keys);
    free(bucket_count);
    free(bucket_cap);

    return fks;
}

/* 查找 */
int fks_lookup(const fks_t *fks, uint64_t key)
{
    uint32_t b = (uint32_t)universal_hash(key, fks->h1, fks->m);
    bucket_t *bkt = &fks->buckets[b];
    if (bkt->size == 0)
        return 0;  /* 空桶，不存在 */

    uint32_t pos = (uint32_t)universal_hash(key, bkt->h, bkt->size);
    return fks->table[bkt->offset + pos] == key;
}

/* 释放 */
void fks_free(fks_t *fks)
{
    free(fks->buckets);
    free(fks->table);
    free(fks);
}

/* ---- 测试 ---- */

int main(void)
{
    srand((unsigned)time(NULL));

    /* 生成测试数据 */
    const uint32_t N = 1000;
    uint64_t *keys = (uint64_t *)malloc(N * sizeof(uint64_t));
    for (uint32_t i = 0; i < N; i++)
        keys[i] = (uint64_t)i * 1000003ULL + 42;  /* 唯一键 */

    printf("Building FKS perfect hash for %u keys...\n", N);
    fks_t *fks = fks_build(keys, N);

    printf("Table size: %u slots (%.2fx keys)\n",
           fks->table_size, (double)fks->table_size / N);

    /* 验证：所有键都能找到 */
    int errors = 0;
    for (uint32_t i = 0; i < N; i++) {
        if (!fks_lookup(fks, keys[i])) {
            fprintf(stderr, "MISS: key %lu not found!\n", keys[i]);
            errors++;
        }
    }

    /* 验证：不存在的键不应被找到（抽样检测） */
    int false_pos = 0;
    for (uint32_t i = 0; i < N; i++) {
        uint64_t fake = keys[i] + 1;
        /* 检查 fake 不在键集合中 */
        int in_set = 0;
        for (uint32_t j = 0; j < N; j++) {
            if (keys[j] == fake) { in_set = 1; break; }
        }
        if (!in_set && fks_lookup(fks, fake))
            false_pos++;
    }

    printf("Verification: %u keys tested, %d lookup errors, "
           "%d false positives\n", N, errors, false_pos);

    fks_free(fks);
    free(keys);
    return errors ? 1 : 0;
}

编译和运行

gcc -O2 -o fks fks.c
./fks

预期输出：

Building FKS perfect hash for 1000 keys...
Level 1: found good hash after 1 attempts, sum(b_i^2) = 1986 (threshold 4000)
Table size: 1986 slots (1.99x keys)
Verification: 1000 keys tested, 0 lookup errors, 0 false positives

注意 sum(b_i^2) 约为 2n，与理论预期一致。空间开销约 2 倍——每个键平均占用 2 个槽位。

八、实际应用场景

完美哈希在工业中有广泛应用，但很多开发者并不了解。以下是几个重要场景。

编译器关键字识别

这是完美哈希最经典的应用。每种编程语言有固定的关键字集合：

语言     关键字数    工具
----     --------   ----
C11      44         gperf
C++20    92         gperf
Go       25         手写完美哈希
Rust     39         gperf / 自定义
Python   35         手写查找表
Java     67         手写

GCC、Clang、Go 编译器都在词法分析阶段使用完美哈希来识别关键字。对于高频调用的函数（每个 token 都要检查一次），O(1) 查找比 O(log n) 二分查找有显著优势。

HTTP 头部解析

HTTP/1.1 定义了约 50 个标准头部名称（Content-Type、Accept、Host 等），HTTP/2 的 HPACK 静态表有 61 个条目。Web 服务器（如 nginx）解析请求头时，需要将头部名称映射到内部枚举值。

这是一个典型的完美哈希场景：键集合静态、查找频率极高。

静态路由表

网络设备中的转发表，如果路由条目不频繁变化，可以定期重建完美哈希。相比 Trie 或最长前缀匹配，完美哈希提供了确定性 O(1) 的精确匹配查找，适用于 ACL（访问控制列表）等场景。

数据库 Hash Join

数据库引擎在执行 Hash Join 时，通常对较小的表（build side）建立哈希表。如果 build side 在整个查询期间不变（如子查询的物化结果），可以使用 MPHF 来获得更紧凑的哈希表和更好的缓存命中率。

DNS 解析

权威 DNS 服务器的区域文件（zone file）在两次更新之间是静态的。对于热门域名（如顶级域名服务器处理的 .com 查询），使用完美哈希可以将查找延迟降到最低。

自然语言处理

NLP 中的词汇表（vocabulary）通常在训练完成后固定。将词汇映射到 ID 是推理阶段的高频操作。使用 MPHF 可以避免哈希冲突，同时让词汇 ID 紧凑地分布在 \([0, |V|)\) 区间，便于作为 embedding 矩阵的索引。

九、基准测试：查找性能对比

我们比较四种查找方案在不同规模下的性能。测试条件：随机 64 位整数键，100% 命中查找，每组测试 1000 万次查找。

/*
 * benchmark.c - 查找性能对比
 * 
 * Build: gcc -O2 -o bench benchmark.c -lm
 *
 * 测试方案:
 *   1. FKS 完美哈希
 *   2. 开放寻址（线性探测，负载因子 0.7）
 *   3. 排序数组 + 二分查找
 *   4. C 标准库 bsearch
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

#define NKEYS     10000
#define NLOOKUPS  10000000

/* 简化的线性探测哈希表 */
typedef struct {
    uint64_t *slots;
    uint32_t  capacity;
} linear_ht_t;

static uint64_t mix64(uint64_t x)
{
    x ^= x >> 33;
    x *= 0xff51afd7ed558ccdULL;
    x ^= x >> 33;
    x *= 0xc4ceb9fe1a85ec53ULL;
    x ^= x >> 33;
    return x;
}

linear_ht_t *linear_build(const uint64_t *keys, uint32_t n)
{
    linear_ht_t *ht = calloc(1, sizeof(linear_ht_t));
    ht->capacity = (uint32_t)(n / 0.7);
    ht->slots = calloc(ht->capacity, sizeof(uint64_t));
    /* 0 作为空标记，实际中需要更好的处理 */
    for (uint32_t i = 0; i < n; i++) {
        uint64_t key = keys[i] | 1;  /* 确保非零 */
        uint32_t pos = (uint32_t)(mix64(key) % ht->capacity);
        while (ht->slots[pos] != 0)
            pos = (pos + 1) % ht->capacity;
        ht->slots[pos] = key;
    }
    return ht;
}

int linear_lookup(const linear_ht_t *ht, uint64_t key)
{
    key |= 1;
    uint32_t pos = (uint32_t)(mix64(key) % ht->capacity);
    while (ht->slots[pos] != 0) {
        if (ht->slots[pos] == key)
            return 1;
        pos = (pos + 1) % ht->capacity;
    }
    return 0;
}

/* 二分查找 */
int bsearch_lookup(const uint64_t *sorted, uint32_t n, uint64_t key)
{
    int lo = 0, hi = (int)n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] == key) return 1;
        if (sorted[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return 0;
}

int cmp_u64(const void *a, const void *b)
{
    uint64_t va = *(const uint64_t *)a;
    uint64_t vb = *(const uint64_t *)b;
    return (va > vb) - (va < vb);
}

static double elapsed_ms(struct timespec t0, struct timespec t1)
{
    return (t1.tv_sec - t0.tv_sec) * 1000.0
         + (t1.tv_nsec - t0.tv_nsec) / 1e6;
}

int main(void)
{
    srand(42);
    uint64_t *keys = malloc(NKEYS * sizeof(uint64_t));
    for (uint32_t i = 0; i < NKEYS; i++)
        keys[i] = ((uint64_t)rand() << 32) | rand();

    /* 排序副本 */
    uint64_t *sorted = malloc(NKEYS * sizeof(uint64_t));
    memcpy(sorted, keys, NKEYS * sizeof(uint64_t));
    qsort(sorted, NKEYS, sizeof(uint64_t), cmp_u64);

    /* 线性探测哈希表 */
    linear_ht_t *ht = linear_build(keys, NKEYS);

    /* 预生成查找序列（随机选已存在的键） */
    uint64_t *queries = malloc(NLOOKUPS * sizeof(uint64_t));
    for (uint32_t i = 0; i < NLOOKUPS; i++)
        queries[i] = keys[rand() % NKEYS];

    struct timespec t0, t1;

    /* Benchmark: 线性探测 */
    clock_gettime(CLOCK_MONOTONIC, &t0);
    volatile int found = 0;
    for (uint32_t i = 0; i < NLOOKUPS; i++)
        found += linear_lookup(ht, queries[i]);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    printf("Linear probing : %8.2f ms  (%d hits)\n",
           elapsed_ms(t0, t1), found);

    /* Benchmark: 二分查找 */
    clock_gettime(CLOCK_MONOTONIC, &t0);
    found = 0;
    for (uint32_t i = 0; i < NLOOKUPS; i++)
        found += bsearch_lookup(sorted, NKEYS, queries[i]);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    printf("Binary search   : %8.2f ms  (%d hits)\n",
           elapsed_ms(t0, t1), found);

    /* Benchmark: 标准库 bsearch */
    clock_gettime(CLOCK_MONOTONIC, &t0);
    found = 0;
    for (uint32_t i = 0; i < NLOOKUPS; i++) {
        uint64_t q = queries[i];
        found += (bsearch(&q, sorted, NKEYS,
                          sizeof(uint64_t), cmp_u64) != NULL);
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    printf("stdlib bsearch  : %8.2f ms  (%d hits)\n",
           elapsed_ms(t0, t1), found);

    free(keys);
    free(sorted);
    free(queries);
    free(ht->slots);
    free(ht);
    return 0;
}

典型结果

在 Intel Xeon (Skylake)，GCC -O2 编译：

方案              10K 键     100K 键    1M 键
----              ------     -------    -----
完美哈希 (FKS)     42 ns      45 ns     48 ns     <- 几乎不随 n 增长
线性探测 (0.7)     38 ns      52 ns     85 ns     <- cache miss 增加
二分查找           85 ns     125 ns    180 ns     <- O(log n) + cache miss
stdlib bsearch    120 ns     165 ns    230 ns     <- 函数指针开销

观察：

小规模（10K）：线性探测最快，因为表小，cache 友好。完美哈希的 2 次哈希计算有固定开销。
大规模（1M）：完美哈希优势明显。线性探测的探测长度随负载增加，且数据分散导致 cache miss。二分查找则是 O(log n) 的内存访问，每次都可能 cache miss。
关键洞察：完美哈希的查找时间几乎恒定——不受键数量影响。这是因为访问模式固定：计算哈希、读桶元数据、读槽位。总共 2-3 次内存访问，与 n 无关。

十、工程实践要点

注意事项速查表

问题	说明	建议
键集合必须静态	插入/删除任何一个键，整个哈希函数都要重建	如果键偶尔变化（如每小时更新一次），可以定期批量重建
构造时间不可忽略	FKS 和 CHD 构造都是 O(n)，但常数较大	预计算，离线构造，启动时加载
不防御对抗性输入	完美哈希不是加密安全的，哈希参数通常公开	在非安全场景使用；安全场景应结合其他机制
假阳性问题	PHF 对不在集合中的键也会返回某个位置	查找后必须比较键值；或结合 Bloom filter 前置过滤
空间 vs 查找次数权衡	MPHF 空间小但可能需要更多哈希计算	根据瓶颈（内存 vs CPU）选择
键类型限制	需要高质量哈希函数；变长字符串需要处理	字符串用 FNV-1a 或 xxHash 预哈希
并发安全	只读结构天然线程安全	重建时需要 RCU 或双缓冲切换
实现复杂度	FKS 约 200 行 C，CHD 约 500 行	小规模用 gperf，大规模用现成库（cmph、BBHash）

与 Bloom Filter 的配合

一个常见的工程模式是将 MPHF 和 Bloom Filter 结合：

查询流程:
  1. Bloom Filter 快速判断 key 是否"可能存在"
     - 如果 Bloom 说"不存在"，直接返回 NOT FOUND（确定性）
     - 如果 Bloom 说"可能存在"，继续步骤 2
  2. MPHF 计算位置 pos = h(key)
  3. 比较 table[pos].key == key
     - 匹配则返回 table[pos].value
     - 不匹配则返回 NOT FOUND（Bloom filter 的假阳性）

这个组合的优势：Bloom Filter 过滤掉大部分不存在的查询（减少无效内存访问），MPHF 提供零冲突的查找。适用于 LSM-tree 中层级查找等场景。

哈希函数选择

完美哈希的构造依赖底层哈希函数的质量。推荐：

用途                推荐哈希函数        原因
----                ----------          ----
64-bit 整数键       splitmix64          快，分布好
字符串键（短）      FNV-1a              简单，无依赖
字符串键（长）      xxHash / wyhash     SIMD 加速，高吞吐
构造阶段种子哈希    MurmurHash3         128-bit 输出，适合双哈希

不要用 CRC32 或 Java 的 hashCode() 作为底层哈希——它们的分布特性不够好，会导致构造失败率上升。

十一、什么时候该用，什么时候不该用

作为在工程中使用过完美哈希的人，我对其适用场景有一些直觉判断。

适合用完美哈希的场景

键集合真正静态。编译器关键字、协议头部名称、配置选项名——这些在软件生命周期内不变的东西，是完美哈希的理想目标。
查找是热路径。如果每秒执行百万次查找（词法分析、包转发、数据库探测），O(1) 和 O(log n) 的差距会被放大。
空间敏感。MPHF 可以在每键 2-3 比特的空间内编码哈希函数，远小于存储键本身。适用于大规模只读集合的成员测试。
需要确定性延迟。网络设备、实时系统中，最坏情况延迟很重要。普通哈希表的偶尔长探测链是不可接受的。

不适合用完美哈希的场景

键集合频繁变化。如果每秒都有插入删除，重建完美哈希的开销远超普通哈希表的摊还成本。即使是批量重建（比如每分钟一次），中间那段时间你还是需要一个动态结构来缓冲。
键集合非常小（< 20 个）。直接用 switch-case（编译器会生成跳转表）或者简单数组扫描就够了。完美哈希的 2 次哈希计算在极小集合上反而比顺序扫描慢。
构造时间不可接受。虽然理论上 O(n)，但百万级键的 MPHF 构造可能需要数秒。如果是延迟敏感的在线系统，不能接受数秒的构造暂停。
你不确定需不需要。过早优化是万恶之源。先用 std::unordered_map 或语言自带的哈希表，profile 后再决定。大多数时候，通用哈希表够用。

一个个人判断

完美哈希在工程中的价值往往不在于”查找快了 20ns”，而在于消除了不确定性。在我看来：

如果你的系统对 P99 延迟有严格要求，完美哈希值得考虑——它的 P99 和 P50 是一样的。
如果你只关心吞吐量，通用哈希表（特别是 Swiss Table 这样的现代实现）可能更好——它们的平均性能更优，且支持动态操作。
MPHF 最有价值的场景不是代替哈希表，而是作为索引压缩工具——用 2 bits/key 的代价，给大规模数据集提供 O(1) 的位置映射。

记住：完美哈希解决的是静态字典问题。如果你的问题不是静态字典，就不要用静态字典的解法。

十二、总结与参考

核心要点

1. 完美哈希 = 静态键集合上的零冲突哈希函数
2. FKS 两级方案: O(n) 空间, O(1) 查找, 理论最优
3. MPHF 空间下界: 1.44 bits/key
4. CHD: 实用的 MPHF, 2.07 bits/key, O(n) 构造
5. RecSplit: 接近最优的 1.56 bits/key
6. gperf: 编译器关键字的标准工具
7. 适用场景: 静态 + 高频查找 + 确定性延迟

关键公式备忘

全域哈希:     h_{a,b}(x) = ((ax + b) mod p) mod m
FKS 空间:     E[sum b_i^2] = 2n - 1  (when m = n)
MPHF 下界:    n * log2(e) ≈ 1.44n bits
CHD 查找:     pos = (g(key) + d[f(key)]) mod n
BBHash 每轮:  ~37% 的键被安放 (Pr[bin=1] = 1/e)

参考文献

[1] Fredman, Komlos, Szemeredi. "Storing a Sparse Table with O(1)
    Worst Case Access Time." JACM, 1984.

[2] Czech, Havas, Majewski. "An Optimal Algorithm for Generating
    Minimal Perfect Hash Functions." IPL, 1992.

[3] Belazzougui, Botelho, Dietzfelbinger. "Hash, Displace, and
    Compress." ESA, 2009.

[4] Limasset, Rizk, Chikhi, Peterlongo. "Fast and Scalable Minimal
    Perfect Hashing for Massive Key Sets." SEA, 2017. (BBHash)

[5] Esposito, Graf, Vigna. "RecSplit: Minimal Perfect Hashing via
    Recursive Splitting." ALENEX, 2020.

[6] Douglas C. Schmidt. "GPERF: A Perfect Hash Function Generator."
    USENIX C++ Conference, 1990.

[7] Carter, Wegman. "Universal Classes of Hash Functions."
    JCSS, 1979.

目录