Cuckoo Hashing：用两个位置换取最坏情况常数查找

关于 cuckoo hashing，流行的说法有三条：“所有操作都是最坏 \(O(1)\)”；“负载因子上限是 50%”；“它比线性探测快”。三条都要打折扣。最坏 \(O(1)\) 只属于查找和删除，插入是期望常数时间，而且可能失败、触发整表重哈希；50% 只是两张表、每格一个键时的阈值，把格子换成 4 路桶，理论阈值升到约 98%，但生产实现因为限制了搜索长度，实际停在 95% 上下；至于速度，Pagh 和 Rodler 自己在原始论文里测到的是线性探测平均更快。

本文按”查找保证 → 插入与失败 → cuckoo 图 → 负载阈值 → 插入搜索 → 哈希函数 → 并发 → 指纹变体”的顺序展开。所有探测次数、踢出次数和失败概率都来自同目录下的 reproduce/cuckoo_sim.c（环境见第一节），没有计时数据；DPDK、OVS、libcuckoo 的行为以钉住版本的源码为准。

线性探测（linear probing）和 Robin Hood 哈希的查找是期望常数：平均探测几次就够，但探测序列的最长长度会随表大小增长。上一篇已经推导了线性探测的 Knuth 公式和 Robin Hood 的 \(\log\log n\) 结论，这里只看”最坏的那一次”。

cuckoo hashing 的承诺更硬：每个键只可能待在 \(d\) 个固定位置之一（基本版本 \(d=2\)），查找最多读 \(d\) 个位置，与表大小和负载无关。下图左边是 \(2^{20}\) 个槽、8 字节键时，一次未命中查找最多要比较多少个槽；右边固定负载 0.9，看命中查找的最长探测随表大小怎么变。

对应的数字（./cuckoo_sim e2、e3）：

记号 \((d,k)\) 表示每个键有 \(d\) 个候选桶、每桶 \(k\) 个槽。cuckoo 一栏按”读到哪个桶就比较整桶”计数，所以命中平均介于 \(k\) 与 \(2k\) 之间，未命中恒为 \(2k\)；每桶最多 8 个 8 字节键，按 64 字节对齐时一个桶落在一条缓存行内，因此 (2,4)、(2,8) 的任何查找最多碰 2 条缓存行。线性探测和 Robin Hood 的命中平均相同（二者只是换了键的排列，总位移不变），差别全在最长探测和未命中上。

cuckoo 付出的代价有两处：插入要”搬家”，而且可能搬不下去；两个候选位置在内存里互不相邻，命中第二个桶就要多读一条缓存行。Pagh 和 Rodler 强调，这两次访存互相独立，可以同时发出。这并不意味着查找”没有条件分支”：比较两个位置的键仍然要判断，只是分支次数有上界。

“最坏常数时间查找”本身不新。Fredman、Komlós、Szemerédi（1984）给出静态集合上的两级完美哈希（见完美哈希）；Dietzfelbinger 等人（SIAM J. Comput. 1994）的动态完美哈希把它推广到可插入删除，但常数大，Pagh 和 Rodler 引用的空间开销是最多约 \(35n\) 个字。Pagh 和 Rodler 的 cuckoo hashing（ESA 2001；Journal of Algorithms 2004）用两张各 \(r \ge (1+\epsilon)n\) 格的表达到同样的查找保证，每个键只占一格，算法短到可以写在半页纸上。

两张表 \(T_1, T_2\)，各 \(r\) 格；两个哈希函数 \(h_1, h_2\)。不变量只有一条：键 \(x\) 要么在 \(T_1[h_1(x)]\)，要么在 \(T_2[h_2(x)]\)。于是

插入 \(x\) 时先查找，已存在就返回。否则把 \(x\) 放进 \(T_1[h_1(x)]\)；若那格原来有键 \(y\)，就把 \(y\) 踢出来放进它在 \(T_2\) 的位置 \(T_2[h_2(y)]\)；若又踢出 \(z\)，再把 \(z\) 放回 \(T_1[h_1(z)]\)……如此在两张表之间交替，直到某次落进空格。被踢出、暂时无处可去的键叫”无巢键”（nestless key）。复现程序里的实现就是论文伪代码的直译（reproduce/cuckoo_sim.c 的 toy_insert()，删去了打印语句）：

static int toy_insert(char x, int maxloop)
{
    for (int it = 0; it < maxloop; it++) {
        int p = toy_h1(x);
        char y = toy_t1[p];          /* x takes T1[h1(x)] */
        toy_t1[p] = x;
        if (!y) return 1;
        x = y;                       /* the evicted key goes to T2 */
        p = toy_h2(x);
        y = toy_t2[p];
        toy_t2[p] = x;
        if (!y) return 1;
        x = y;                       /* and back to T1 */
    }
    return 0;                        /* MaxLoop reached: rehash */
}

下面用一个手工构造的例子跟踪一遍。两张表各 4 格，五个键的哈希值为 \(A:(0,2)\)、\(B:(1,1)\)、\(C:(0,2)\)、\(D:(0,3)\)、\(E:(0,2)\)，其中第一个数是 \(h_1\)，第二个是 \(h_2\)。先插入 A、B，都直接落进 \(T_1\)；插入 C 时它和 A 争 \(T_1[0]\)，A 被踢到 \(T_2[2]\)。下图从这个状态开始插入 D（./cuckoo_sim e1 的输出）：

四步里发生了三次踢出，关键在第 3 步：A 回到 \(T_1[0]\)，把刚放进去的 D 又踢了出来，D 这才转向它的另一个位置 \(T_2[3]\)。踢出链可以经过同一个格子两次、甚至把新键自己踢出去，这正是插入会”绕圈”的根源，第三节用 cuckoo 图解释它什么时候绕得出来。

如果踢出链一直不落空格，插入必须在有限步内放弃：Pagh 和 Rodler 设上限 \(\mathrm{MaxLoop}\)，到达上限就换一对新的哈希函数，把所有键重新插入（rehash）。例子里的第五个键 E 与 A、C 争同两格，8 次踢出后在 \(\mathrm{MaxLoop}=4\) 轮处停下，无巢键是 C。

论文的分析（BRICS RS-01-32 第 3 节）是这样的：插入循环跑满 \(t\) 轮，意味着存在一条长度至少 \((2t-1)/3\) 的、由不同键组成的碰撞序列。若哈希函数取自 \((c,m)\)-universal 族，这种序列存在的概率不超过

\[ 2c\,(1+\epsilon)^{-\frac{2t-1}{3}+1}. \]

这个界随 \(t\) 按 \((1+\epsilon)^{-2t/3}\) 衰减，底数由表的富余量 \(\epsilon\) 决定，不是固定的 \(1/2\)。取 \(\mathrm{MaxLoop} = 3\log_{1+\epsilon} n\) 时，循环超过上限的概率是 \(O(1/n^2)\)；不发生重哈希时插入的期望轮数为 \(O(1+1/\epsilon)\)。再加上”所有键根本无法安放”的概率为 \(O(1/n)\)，而一次重哈希期望花 \(O(n)\)，摊到每次插入上仍是期望 \(O(1)\)。

这就是 cuckoo hashing 的真实复杂度：查找、删除最坏 \(O(1)\)；插入期望摊还 \(O(1)\)，单次插入可能触发 \(O(n)\) 的重哈希。

cuckoo 图（cuckoo graph）以格子为顶点，每个键 \(x\) 是一条连接 \(T_1[h_1(x)]\) 与 \(T_2[h_2(x)]\) 的边。一种合法摆放就是给每条边选一个端点、使每个顶点最多被选一次，也就是把边定向，每个顶点入度不超过 1。

对一个连通分量，设它有 \(v\) 个顶点、\(e\) 条边。每个键占一格，所以 \(e \le v\) 是必要条件；反过来，连通图满足 \(e \le v\) 时只有两种形状：树（\(e = v-1\)）和恰好一个环的单环图（unicyclic，\(e = v\)），两者都能定向。于是：

用前面的例子看：

A 和 C 的哈希值完全相同，构成一对平行边，本身就是一个长度为 2 的环；D 是挂在环上的树边。插入 D 时的踢出链沿环走了一圈（D→C→A→D），回到起点后转向树的方向，落进空格 \(T_2[3]\)。这就是 Pagh 和 Rodler 分析里的情形：踢出链进入环后会”原路返回”，只要分量里没有第二个环，就能走出去。E 给这个分量加上第四条边，3 个格子装不下 4 个键，无论怎么踢都不可能成功，踢出链只会在环上无限循环，MaxLoop 的作用就是尽早发现这一点。

设两张表各 \(m\) 格、有 \(n\) 个键，cuckoo 图就是 \(2m\) 个顶点、\(n\) 条随机边的二部多重图。按随机图理论，当 \(n \le (1-\epsilon)m\) 时，以 \(1 - O(1/m)\) 的概率每个分量至多一个环；一旦 \(n \ge (1+\epsilon)m\)，巨型连通分量出现，它的边数以高概率超过顶点数。\(n/m = 1\) 对应的负载因子是 \(n/(2m) = 1/2\)，这就是”50%“的出处。Pagh 和 Rodler 要求每张表 \(r \ge (1+\epsilon)n\)，也就是负载不超过 \(1/(2(1+\epsilon))\)。

Drmota 与 Kutzelnigg（ACM TALG 2012）给出了失败概率的精确常数。取 \(n = \lfloor (1-\epsilon)m \rfloor\)，所有键都能放下的概率是

\[ 1 - \frac{(2\epsilon^2 - 5\epsilon + 5)(1-\epsilon)^3}{12(2-\epsilon)^2\epsilon^3}\cdot\frac{1}{m} + O\!\left(\frac{1}{m^2}\right). \]

失败概率是 \(\Theta(1/m)\)，但常数按 \(\epsilon^{-3}\) 放大：\(\epsilon = 0.2\) 时常数约 6.7，\(\epsilon = 0.1\) 时约 76。他们也证明了在临界点 \(n = m\) 处成功概率趋于 \(\sqrt{2/3}\)，不是 0。更早 Devroye 与 Morin（IPL 2003）只给出 \(1 - O(1/m)\) 的形式。

用并查集直接在随机 cuckoo 图上判定”有没有边多于点的分量”（./cuckoo_sim e4，不经过插入过程，所以测到的是”不存在合法摆放”的概率）：

\(m\) 增大时实测值向主项收敛；\(\epsilon = 0.1\)、\(m = 1000\) 时差了三倍，说明 \(O(1/m^2)\) 项在富余量小、表又不大时并不可忽略。\(m = 20000\) 的两行只有 16 次和 164 次失败，统计误差分别约 25% 和 8%，只能说明趋势。

Kirsch、Mitzenmacher、Wieder（ESA 2008；SIAM J. Comput. 2009）的观察是：失败几乎总是只多出一两条边。在表外放一个容量为 \(s\) 的小数组 stash，放不下的键进 stash，查找时额外扫一遍它。一个图需要的最小 stash 大小是

\[ S = \sum_{C} \max(0,\ e_C - v_C), \]

即每个分量多出来的边数之和。他们在完全随机哈希假设下证明 \(\Pr[S \ge s] = O(n^{-s})\)（论文 Theorem 2.1）：多一格 stash，失败概率就多降一个 \(n\) 的量级。

复现程序按同样的参数计算 \(S\) 的分布（./cuckoo_sim e5），与论文 Table 1 对照：

KMW 的数字来自带 100 次踢出上限的实际插入过程，本文算的是图上的理论最小值，口径不同：实际插入可能在存在合法摆放时也放弃，所以只会比最小值多。第一组 \(S \ge 1\) 的比例几乎相同（本文 0.718%，KMW 0.719%）；第二组本文 0.073%（73 次，统计误差约 12%），KMW 为 0.101%，差距超出统计误差，本文没有进一步分析原因。无论看哪个来源，表大 10 倍时需要 stash 的比例都下降到原来的约十分之一到七分之一，与 \(\Pr[S \ge 1] = O(1/n)\) 一致。

50% 的空间利用率太浪费，有两种推广：

这两个界都是充分条件，给出的是 \(\epsilon\) 与 \(d\)、\(k\) 的数量级关系，不是精确阈值。

精确阈值要到 2010 年前后才确定。对 \(d \ge 3\)、桶大小 1，Dietzfelbinger、Goerdt、Mitzenmacher、Montanari、Pagh、Rink（ICALP 2010）把问题对应到随机 XORSAT，Fountoulakis 与 Panagiotou、Frieze 与 Melsted 独立给出证明（两篇均发表于 Random Structures & Algorithms 41(3), 2012）。阈值 \(c_{d,2}\) 的含义是：负载超过它时，超图的 2-core 里边密度大于 1，2-core 中的键已经比格子多（XORSAT 论文 Theorem 2 的证明）。

这里容易和另一个阈值混淆。peeling 阈值是 2-core 开始出现的密度，它比 \(c_{d,2}\) 低，决定的是”能不能一个个剥掉度为 1 的顶点”，这是 XOR filter 和某些完美哈希构造关心的条件。cuckoo hashing 允许 2-core 存在，只要 2-core 里边不多于点就能定向，所以阈值更高。

对分桶的情形，XORSAT 论文推测 \(d\) 个候选桶、每桶 \(k\) 槽时的阈值是 \(c_{d,k+1}\)（按”每桶键数”计），负载阈值再除以 \(k\)；这个推测对 \(d \ge 3\) 由 Fountoulakis、Khosla、Panagiotou（SODA 2011；CPC 2016）证明，\(d = 2\) 由 Cain、Sanders、Wormald 与 Fernholz、Ramachandran（均为 SODA 2007）证明。记 \(\ell = k+1\)，\(\mathrm{Po}(\beta)\) 为 Poisson 变量，\(\beta^*\) 解方程

\[ \frac{\beta\,\Pr[\mathrm{Po}(\beta) \ge \ell-1]}{d\,\Pr[\mathrm{Po}(\beta) \ge \ell]} = \ell - 1, \]

则

\[ c_{d,\ell} = \frac{\beta^*}{d\,\Pr[\mathrm{Po}(\beta^*) \ge \ell-1]^{\,d-1}},\qquad \text{负载阈值} = \frac{c_{d,k+1}}{k}. \]

复现程序按这个公式数值求解（threshold()），得到 \(c_{3,2}=0.9179\)、\(c_{4,2}=0.9768\)，与 XORSAT 论文表中的 0.9179352767、0.9767701649 一致。

阈值是”存在合法摆放”的界，实际插入算法未必找得到。./cuckoo_sim e6 在 \(2^{18}\) 个槽的表里逐个插入随机键，记录第一次插入失败时的负载，三种搜索策略各跑 5 个种子，报告中位数：

表里的 (2,1) 是单张表、每键两个候选格的版本，与两张表的原始版本阈值相同。几点观察：

分桶比增加候选位置更受工程欢迎，原因在访存：(2,4) 负载阈值 98.0%，查找最多读 2 条缓存行；(4,1) 阈值 97.7%，却要读 4 条。第一节的表也显示，(2,4) 在 0.95 负载下命中平均只碰 1.29 条缓存行。

libcuckoo 论文（Li 等，EuroSys 2014）给出了 BFS 在检查 \(M\) 个槽以内时的最长路径：

\[ L_{\mathrm{BFS}} = \left\lceil \log_B\!\left(\frac{M}{2} - \frac{M}{2B} + 1\right) \right\rceil, \]

其中 \(B\) 是桶的路数。\(B = 4\)、\(M = 2000\) 时 \(L_{\mathrm{BFS}} = \lceil \log_4 751 \rceil = 5\)，而 MemC3 沿单条路径深度优先地走，同样的槽数预算下路径最长 250。路径短的意义在并发：每一步搬动都要让读者看到一致的状态（第七节），搬 5 次和搬 250 次，临界区长度差约 50 倍。

./cuckoo_sim e7 在同一组键上并排比较两种策略，(2,4) 配置、\(2^{20}\) 个槽，按插入时的负载分段统计：

BFS 在 0.95 负载以内最多只搬 4 个键，随机游走最坏要踢 270 次，平均也差 10 倍。代价在于 BFS 要读更多桶：高负载时平均检查 51 个槽、最坏 1240 个。随机游走写得多、读得少，BFS 读得多、写得少，而在并发表里写才是贵的那一方。

BFS 带来的另一个结构性变化是把”找路径”和”搬键”分开：

搬动从路径的空闲端开始，每一步都是把一个键复制到已经空出来的槽，然后它的旧槽才会被下一步覆盖。复现程序里对应的循环（ct_insert_bfs()，有删减）：

/* cur: BFS node whose bucket b has a free slot f */
uint32_t eb = b; int es = f;
for (int32_t n = cur; t->qparent[n] >= 0; n = t->qparent[n]) {
    uint32_t pb = t->qb[t->qparent[n]];      /* bucket one step closer to x */
    int ps = t->qslot[n];                    /* slot whose key can move to eb */
    *ct_at(t, eb, es) = *ct_at(t, pb, ps);   /* move the hole backwards */
    eb = pb; es = ps;
}
*ct_at(t, eb, es) = key;                     /* the hole reached a candidate bucket of x */

libcuckoo 论文把这种做法概括为”移动空洞，而不是移动键”：正在被搬的键可能在表里出现两次，但永远不会消失。

DPDK 的 BFS 队列不记录访问过的桶，所以 1000 这个上限是队列节点数，不是深度，也不是不同桶的数目。

前面所有分析都假设哈希函数完全随机。实际能用多弱的哈希函数，是 cuckoo hashing 文献里持续最久的争论。

所以”cuckoo hashing 需要好的哈希函数”有具体含义：对抗性或高度结构化的键集会让弱哈希失效，失败的代价是重哈希甚至插入失败。生产实现通常先把键映射成一个高质量的 32 或 64 位哈希值，再从这个值导出两个桶号，两个桶号因此并不独立：

/* DPDK v24.11, lib/hash/rte_cuckoo_hash.c */
static inline uint16_t
get_short_sig(const hash_sig_t hash)
{
    return hash >> 16;
}

static inline uint32_t
get_prim_bucket_index(const struct rte_hash *h, const hash_sig_t hash)
{
    return hash & h->bucket_bitmask;
}

static inline uint32_t
get_alt_bucket_index(const struct rte_hash *h,
            uint32_t cur_bkt_idx, uint16_t sig)
{
    return (cur_bkt_idx ^ sig) & h->bucket_bitmask;
}

DPDK 用 32 位哈希值的低位选主桶，高 16 位作签名（signature），次桶等于主桶异或签名。异或的好处是对称：只凭当前桶号和桶里存的签名就能算出另一个桶，搬家时不必重新读键、重新哈希。代价是两个桶号完全由同一个 32 位值决定，32 位哈希值相同的键必然争同一对桶；桶数超过 \(2^{16}\) 时，次桶与主桶只在低 16 位不同。后一点对可达负载有没有影响，本文没有测量。

Pagh–Rodler 的插入是”先写新键、再给被踢出的键找地方”。在这两次写之间，被踢出的键不在任何一格里，并发的读者会得到错误的未命中：

sequenceDiagram
    participant W as Writer
    participant B1 as Bucket b1
    participant B2 as Bucket b2
    participant R as Reader
    Note over B1: holds y
    W->>B1: write x over y (y kept in a register)
    R->>B1: lookup y: not here
    R->>B2: lookup y: not here yet
    R-->>R: returns "absent" although y was never deleted
    W->>B2: write y

MemC3 和 libcuckoo 的论文都把消除这种假未命中（false miss）作为并发设计的第一步，方法就是第五节的”先找路径、从空闲端反向搬”：键在搬动过程中会被复制到新位置之后才从旧位置消失。但仅此还不够，读者可能先读了新位置（尚未写入）、再读旧位置（刚被覆盖），两次读之间键完成了搬家，所以还需要一种检测机制。

MemC3（Fan、Andersen、Kaminsky，NSDI 2013）是一个 memcached 替代品，它的做法（论文 3.2 节）：

用伪代码写读者一侧（按论文描述整理，不是 MemC3 源码）：

lookup(key):
    c = counter[hash(key) mod 8192]
    loop:
        v1 = atomic_load(c)
        if v1 is odd: pause; continue
        result = search(bucket1(key), bucket2(key))
        v2 = atomic_load(c)
        if v1 == v2: return result

MemC3 的搜索是随机选择的单条路径，论文还测试了同时沿多条路径搜索，2 条最好：95% 负载下插入延迟从 1 条路径的 1.3 µs 降到 0.84 µs。

MemC3 的读者很快，但只有一个写者。libcuckoo（Li、Andersen、Kaminsky、Freedman，EuroSys 2014）要支持多写者，问题在于 MemC3 的路径可能长到几百步，一条路径上的锁很难按固定顺序全部拿到。它的改动：

当前 libcuckoo 源码（master 6a2555d）里读操作 find_fn() 也会通过 snapshot_and_lock_two() 锁住两个桶，与 MemC3 的无锁读不同；源码里锁的上限是 kMaxNumLocks = 1 << 16。

DPDK 的 rte_hash 在创建时可以选择多写者支持和无锁读（RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF）。v24.11 源码的结构是：

/* DPDK v24.11, lib/hash/rte_cuckoo_hash.c, __rte_hash_lookup_with_hash_lf()（有删减） */
do {
    cnt_b = rte_atomic_load_explicit(h->tbl_chng_cnt,
            rte_memory_order_acquire);

    bkt = &h->buckets[prim_bucket_idx];
    ret = search_one_bucket_lf(h, key, short_sig, data, bkt);
    if (ret != -1)
        return ret;

    bkt = &h->buckets[sec_bucket_idx];
    FOR_EACH_BUCKET(cur_bkt, bkt) {
        ret = search_one_bucket_lf(h, key, short_sig,
                    data, cur_bkt);
        if (ret != -1)
            return ret;
    }

    rte_atomic_thread_fence(rte_memory_order_acquire);
    cnt_a = rte_atomic_load_explicit(h->tbl_chng_cnt,
                rte_memory_order_acquire);
} while (cnt_b != cnt_a);

return -ENOENT;

命中一定是真命中，所以不必校验；只有未命中可能是”键正在搬家”造成的假象，这时若计数器变过就重查。和 MemC3 相比，DPDK 用一个全局计数器换来了读者路径上的简单，代价是任何一次搬动都会让所有并发的未命中查找重试。

Open vSwitch 的 cmap（v3.4.0，lib/cmap.c）是单写者、多读者的并发 cuckoo 表，写者之间的互斥由调用方负责。每个桶带一个计数器，写者修改桶时它为奇数；读者在 read_even_counter() 里等计数器变成偶数，读完桶再用 counter_changed() 确认计数器没变，否则重读这个桶。与 MemC3 的按键条带、DPDK 的全局计数相比，这是按桶粒度的同一种乐观读。它的每桶项数按缓存行选取（64 位平台 5 项），负载超过 85% 时扩容、低于 20% 时收缩。源码注释引用 Erlingsson 等人（WDAS 2006）作为最大负载约 93% 的依据。

MemC3 的键值对存放在表外，桶里只放一个 1 字节的标签（tag）和指针。搬家时要算键的另一个桶，如果每次都去读表外的完整键，访存代价就回来了。MemC3 的做法是让另一个桶只依赖当前桶号和标签：

\[ b_2 = b_1 \oplus \mathrm{hash}(\mathrm{tag}). \]

这就是部分键 cuckoo hashing（partial-key cuckoo hashing）：两个候选桶由完整哈希的一部分决定，另一个桶可以由任意一个桶和标签互相推出。标签还有第二个作用：查找时先比较标签，只有标签相等才去读表外的键。DPDK 的 16 位签名是同一思路，只是不再对签名做哈希。

Fan、Andersen、Kaminsky、Mitzenmacher（CoNEXT 2014）把这个思路推到极致：表里只存指纹 \(f\)，不存键，得到一个支持删除的近似成员查询结构。两个候选桶为

\[ i_1 = \mathrm{hash}(x),\qquad i_2 = i_1 \oplus \mathrm{hash}(f). \]

要注意几点：

它与 Bloom 家族其他成员的比较见 Bloom Filter 全家族。

Pagh 和 Rodler 的实验结论并不偏袒自己（论文第 4 节）：平均意义上线性探测最快，cuckoo hashing 在大 \(n\) 时慢约 40 个时钟周期；在 DIMACS 字典测试上线性探测快 20% 到 30%。第一节的数据也显示，负载 0.9 时线性探测的命中平均只要 5.5 次比较、1.56 条缓存行，大部分查找并不需要最坏情况保证。

反方的依据在尾部和未命中：同样负载 0.9，线性探测一次未命中平均 50 次比较、最坏 982 次；若查找的截止时间是硬的（网络数据面按包处理、硬件查表），或未命中很多（过滤、去重），固定两次访存的价值就体现出来。DPDK、OVS 选 cuckoo 正是这种场景。而 Swiss Table 用元数据分组探测把开放寻址的平均代价进一步压低，争论的天平取决于负载、未命中比例和对尾延迟的要求，没有一个脱离场景的赢家。

MemC3 选随机游走加多路径，libcuckoo 论证 BFS 更适合细粒度加锁，DPDK 和 OVS 都采用 BFS。第五节的实验把分歧量化了：BFS 搬得少、读得多。在单线程表里，读 1000 多个槽的最坏插入未必比踢 270 次便宜；在并发表里，写的次数决定临界区长度和读者重试概率，BFS 更占优势。

选型可以按下面的顺序判断：

源码

核心论文

其他论文

实验

系列导航： - 上一篇：哈希表内部：链式、线性探测、Robin Hood 与生产实现的取舍 - 下一篇：Swiss Table：控制字节、分组探测与墓碑

相关阅读： - 完美哈希：从 FKS 两级表到 gperf 与现代 MPHF - Bloom Filter 全家族 - 并发哈希表：从分段锁到无锁设计

优先读同系列或同问题的下一篇，把单篇消费变成主题集群。

2026-04-10 · algorithms

用可复现实验测量 Bloom、分块 Bloom、cuckoo、xor 与 Ribbon 的每键位数和误判率，对照 log2(1/ε) 下界解释 1.44 倍从何而来、经典 FPR 公式偏在哪里，并核对 RocksDB 9.10 的 FastLocalBloom 与 Ribbon 实现。

2025-07-15 · algorithms

用可复现的探测次数模拟核对 Knuth 的线性探测公式，比较链式、线性探测、Robin Hood、双重哈希与 SwissTable 分组探测的探测分布和删除策略，再对照 CPython 3.13、JDK 21、Go 1.23/1.24、Abseil、Redis 7.4 的源码说明各自的取舍。

2026-04-27 · algorithms / database

从数据库缓冲池的 fix/unfix、脏页和扫描污染出发，对照 LRU-K、2Q、CLOCK-Pro 的学术脉络，以及 PostgreSQL 16 与 InnoDB 8.0 的源码实现，用可复现 trace 比较命中率和元数据开销。

2025-07-15 · algorithms

对照 CPython 与 OpenJDK 源码拆解 TimSort 的 run 检测、minrun、galloping 与合并，梳理 2015 年栈不变量 bug 和改用 Powersort 的原因；比较次数来自与 CPython 逐次一致的 C 移植。