哈希表内部：开放寻址、链式、Robin Hood 的三国演义

哈希表可能是计算机科学中使用频率最高的数据结构。Python 的 dict、Go 的 map、Java 的 HashMap、Rust 的 HashMap——几乎所有语言的标准库都把哈希表作为核心组件。

但你有没有想过：为什么这些语言的哈希表实现完全不同？

• Python 的 dict：开放寻址 + 紧凑数组 + 二次探测变体
• Go 的 map：链式哈希（bucket 数组 + overflow 链 + 渐进式扩容）
• Java 的 HashMap：链式哈希（链表 + 红黑树退化保护）
• Rust 的 HashMap：Swiss Table（开放寻址 + SIMD 元数据 + control byte）
• C++ absl::flat_hash_map：Swiss Table 的 C++ 原版实现

同一个抽象数据结构，五种截然不同的实现。每一种都有深刻的工程理由。

本文将从最基本的”为什么不直接用数组”出发，逐层深入四大流派——链式哈希、经典开放寻址、Robin Hood 哈希、Swiss Table——的设计决策，附带一个完整的 C 语言 Robin Hood 哈希表实现（约 150 行），然后用 benchmark 数据回答”到底哪个快”的问题。

这次我把可执行代码补到了 examples/hash-table-bench/，并在当前环境重跑了一遍：x86-64 Linux，12th Gen Intel Core i9-12900K，GCC 15.2.1，单线程。下面涉及吞吐量的表格，只保留这次能在仓库里直接复现的四种实现：separate chaining、linear probing、Robin Hood、Swiss Table。

Python dict 风格、Go map、混合工作负载和内存占用表，因为当前仓库没有与正文一一对应的本地实现或测量代码，这次不再继续冒充实测结果。

代码与原始结果：bench.c | Makefile | README.md | results-current-env.csv

一、哈希表的核心问题：为什么不直接用数组

从数组到哈希表

数组是最简单的 key-value 存储：arr[key] = value。查找、插入、删除都是 O(1)。

问题在于：key 的范围可能极大。如果 key 是 64 位整数，你需要 \(2^{64}\) 个槽位——约 147 EB 的内存。如果 key 是字符串，范围更是无穷。

哈希表的核心思想：用一个哈希函数 \(h(key)\) 把无穷大的 key 空间压缩到一个有限大小的数组中。

key 空间（无穷）  →  h(key)  →  数组索引（有限）
"alice"          →  hash    →  3
"bob"            →  hash    →  7
"charlie"        →  hash    →  3   ← 冲突！

哈希函数到桶的映射

给定一个 key，通过哈希函数 \(h(key)\) 计算出一个整数，取模后得到数组索引 \(h(key) \bmod m\)（\(m\) 是桶的数量）。

好的哈希函数需要满足两个条件：

1. 均匀性：不同的 key 尽量均匀分布到 \(m\) 个桶中。
2. 确定性：相同的 key 必须映射到同一个桶。

但无论哈希函数多好，冲突不可避免——当两个不同的 key 映射到同一个桶时，就需要冲突解决策略。这是鸽巢原理（Pigeonhole Principle）的直接推论：把 \(n > m\) 个 key 映射到 \(m\) 个桶，必然有至少一个桶包含多个 key。

生日悖论：冲突比你想象的早

根据生日悖论（Birthday Paradox），当插入约 \(\sqrt{m}\) 个元素时，冲突概率就超过 50%。对于 1024 个桶的哈希表，插入约 32 个元素就很可能遇到冲突。对于 65536 个桶，只需要约 256 个元素。

这意味着哈希表从非常早期就开始处理冲突——冲突解决策略的效率几乎等同于哈希表本身的效率。

冲突解决策略分为两大流派：链式哈希（Separate Chaining）和开放寻址（Open Addressing）。

二、链式哈希：简单可靠的旧贵族

基本思想

每个桶是一个链表（或其他容器）。冲突时，新元素直接追加到对应桶的链表中。

graph LR
    subgraph buckets ["桶数组"]
        direction TB
        b0["[0]"]
        b1["[1]"]
        b2["[2]"]
        b3["[3]"]
    end
    b0 --> a["alice:1"] --> c["charlie:3"]
    b2 --> bob["bob:2"]
    b3 --> dave["dave:4"] --> eve["eve:5"]

hash("alice") % 4 = 0，hash("charlie") % 4 = 0——冲突的 key 被追加到同一个桶的链表中。桶 1 为空，桶 3 有两个元素。

// 链式哈希表的基本结构
typedef struct Entry {
    uint64_t key;
    uint64_t value;
    struct Entry *next;
} Entry;

typedef struct {
    Entry **buckets;   // 桶数组（指针数组）
    size_t capacity;   // 桶数量
    size_t size;       // 元素数量
} ChainedHashMap;

void chained_insert(ChainedHashMap *map, uint64_t key, uint64_t value) {
    size_t idx = hash(key) % map->capacity;
    // 先检查是否已存在
    Entry *e = map->buckets[idx];
    while (e) {
        if (e->key == key) { e->value = value; return; }
        e = e->next;
    }
    // 头插法
    Entry *entry = malloc(sizeof(Entry));
    entry->key = key;
    entry->value = value;
    entry->next = map->buckets[idx];
    map->buckets[idx] = entry;
    map->size++;

    if ((double)map->size / map->capacity > 0.75)
        chained_resize(map);
}

uint64_t *chained_lookup(ChainedHashMap *map, uint64_t key) {
    size_t idx = hash(key) % map->capacity;
    Entry *e = map->buckets[idx];
    while (e) {
        if (e->key == key) return &e->value;
        e = e->next;
    }
    return NULL;
}

链式哈希的优点

1. 简单可靠：实现简洁，不需要处理复杂的探测逻辑。
2. 负载因子可以超过 1.0：桶只是链表头，元素可以无限追加。
3. 删除方便：直接从链表中移除节点，不需要 tombstone。
4. 对哈希函数要求低：即使哈希函数质量不好（分布不均匀），只是某些链表更长，不会导致灾难性的性能退化。

链式哈希的致命缺点

缓存不友好。

每次查找都是一次链表遍历——每个 next 指针都可能指向内存中完全不同的位置。在现代 CPU 上，一次 L1 缓存命中约 1ns，一次缓存未命中（需要去 L3 或主内存）约 10-100ns。

平均每次查找的链表遍历长度 = 负载因子 \(\alpha = n/m\)。如果 \(\alpha = 0.75\)（Java HashMap 的默认值），平均遍历 0.75 个节点。但每个节点都是一次指针追踪（pointer chasing），几乎必然缓存未命中。

每个 Entry 节点占 24 字节（key 8 + value 8 + next 8），加上 malloc 的元数据和对齐开销，实际每个节点约 32-48 字节。对于 100 万个条目的哈希表，仅节点本身就占 32-48 MB，散布在堆内存的各处。

这也是为什么下面当前环境的实测里，链式哈希在查找吞吐量上始终落后于连续存储的开放寻址方案。差距不需要神秘解释，主要就是缓存命中率和指针追踪成本。

Java 8 的优化：链表 → 红黑树

Java 8 的 HashMap 做了一个精妙的优化：当单个桶的链表长度超过 8 时，自动转换为红黑树（treeification）。

这防止了哈希碰撞攻击（Hash DoS）：攻击者构造大量冲突 key，使所有元素集中在一个桶中，查找退化为 O(n)。转换为红黑树后，最坏情况是 O(log n)。

代价是红黑树节点更大（每个节点需要颜色位、左右子指针、父指针），对正常情况有轻微的性能损失。当元素减少到 6 个以下时，会从红黑树退化回链表（untreeification），避免小桶的额外开销。

flowchart LR
    chain["链表 O(n)\nK1 → K2 → ... → K8"] -- "len > 8 树化" --> tree["红黑树 O(log n)\n防御 Hash DoS"]
    tree -- "len < 6 退化" --> chain

Go 的设计：bucket 数组 + overflow 链 + 渐进式扩容

Go 的 map 是链式哈希中设计最精妙的变体。核心设计点：

bucket 数组而非链表。每个 bucket 存储 8 个 key-value 对（不是链表！），满了之后链接到 overflow bucket。

block-beta
  columns 1
  block:bucket
    columns 1
    tophash["tophash [8]uint8"]
    kv["keys[0..7] | values[0..7]"]
  end
  overflow["*overflow bucket"]
  bucket --> overflow

每个 bucket 有一个 tophash 数组——哈希值的高 8 位。查找时先比较 tophash（一次内存访问可以比较 8 个），命中后再比较完整 key。这把大部分不匹配过滤在第一步，减少了昂贵的全 key 比较。

内存布局的关键决策：Go 把所有 key 连续存放，所有 value 连续存放——而不是 key-value 交替。这样做是为了避免 padding。例如 map[int64]int8，如果交替存放，每个 key-value 对需要 16 字节（8 + 1 + 7 padding）；连续存放只需要 9 字节。

渐进式扩容（evacuate）。当负载因子超过 6.5（平均每个 bucket 6.5 个元素）或 overflow bucket 过多时，触发扩容。Go 不会在一次操作中 rehash 所有 bucket，而是在每次 map 操作（insert/delete）时迁移 1-2 个旧 bucket——这就是 evacuate 函数的工作。

// runtime/map.go 中扩容触发条件（概念代码）
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // ...
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
    }
    // 如果正在扩容，每次写操作迁移一个旧 bucket
    if h.growing() {
        growWork(t, h, bucket)
    }
    // ...
}

Go 的 bucket 设计比纯链表更缓存友好（8 个 key 在连续内存中），但比开放寻址的紧凑数组还是差一些。它选择链式而非开放寻址，核心原因是：Go 需要稳定的指针——map 的 value 可以被取地址（&m[key] 虽然不合法，但内部迭代器持有指针），渐进式 rehash 不能移动已有元素。

三、开放寻址：紧凑的现代选择

基本思想

开放寻址（Open Addressing）把所有元素直接存储在桶数组中，没有额外的链表。冲突时，按某种探测序列寻找下一个空桶。

三种经典探测策略：

1. 线性探测（Linear Probing）：\(h(k, i) = (h(k) + i) \bmod m\)
2. 二次探测（Quadratic Probing）：\(h(k, i) = (h(k) + c_1 i + c_2 i^2) \bmod m\)
3. 双重哈希（Double Hashing）：\(h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m\)

线性探测：缓存最友好

线性探测是最简单的开放寻址策略。冲突时检查下一个位置、再下一个、再下一个……直到找到空位。

flowchart LR
    h["插入 D\nh(D) mod 8 = 2"] --> s2["[2] A\n占用 ✗"]
    s2 -->|"+1"| s3["[3] B\n占用 ✗"]
    s3 -->|"+1"| s4["[4] C\n占用 ✗"]
    s4 -->|"+1"| s5["[5] 空\n插入 ✓"]
    style s5 fill:#90EE90,color:#000

所有元素紧凑存储在同一个数组中，没有指针、没有链表。冲突时依次检查相邻槽位，对 CPU 缓存极友好。

typedef struct {
    uint64_t *keys;
    uint64_t *values;
    uint8_t *states;    // 0=empty, 1=occupied, 2=deleted(tombstone)
    size_t capacity;
    size_t size;
} LinearProbeMap;

uint64_t *linear_probe_lookup(LinearProbeMap *map, uint64_t key) {
    size_t idx = hash(key) % map->capacity;
    for (size_t i = 0; i < map->capacity; i++) {
        size_t pos = (idx + i) % map->capacity;
        if (map->states[pos] == 0)       // 空位：key 不存在
            return NULL;
        if (map->states[pos] == 1 && map->keys[pos] == key)
            return &map->values[pos];
        // 继续探测（occupied but different key, or tombstone）
    }
    return NULL;
}

线性探测的最大优势是缓存友好性。探测序列在内存中是连续的，CPU 的硬件预取器可以提前加载后续的桶。在负载因子 0.5 时，平均探测长度约 1.5 次，而且这些探测大概率在同一个缓存行中（64 字节缓存行可以容纳 4 个 16 字节的 key-value 对）。

线性探测的痛点：聚集

线性探测有一个严重的问题：一次聚集（primary clustering）。

当多个 key 映射到相邻的桶时，它们会形成一个连续的”聚集”。新的 key 如果映射到聚集范围内的任何位置，都会被追加到聚集的末尾，使聚集更大。聚集越大，后续 key 碰到它的概率越高——正反馈循环。

初始状态:  [ ][ ][A][ ][ ][ ][ ][ ]
插入 B→2:  [ ][ ][A][B][ ][ ][ ][ ]     聚集长度: 2
插入 C→2:  [ ][ ][A][B][C][ ][ ][ ]     聚集长度: 3
插入 D→3:  [ ][ ][A][B][C][D][ ][ ]     聚集长度: 4（D 被吸入聚集）
插入 E→1:  [ ][ ][A][B][C][D][E][ ]     聚集长度: 5（即使 E 哈希到 1！）

Knuth 证明了：在线性探测中，负载因子 \(\alpha\) 下的期望探测长度（成功查找）为：

\[ E[\text{probes}] = \frac{1}{2}\left(1 + \frac{1}{1 - \alpha}\right) \]

当 \(\alpha = 0.5\) 时，期望 1.5 次探测（很好）。但 \(\alpha = 0.9\) 时，期望 5.5 次探测；\(\alpha = 0.95\) 时，期望 10.5 次。性能急剧恶化。

这就是为什么使用线性探测的哈希表，负载因子通常不超过 0.7。Google 的 flat_hash_map（Swiss Table）用 0.875 作为阈值——但它用了 SIMD 加速，对抗了聚集的影响。

二次探测与双重哈希

二次探测用 \(i^2\) 的步长代替线性步长，打散了一次聚集，但引入了二次聚集（secondary clustering）：映射到同一初始位置的 key 仍然沿着相同的探测序列走。

线性探测:  idx, idx+1, idx+2, idx+3, idx+4 ...
二次探测:  idx, idx+1, idx+4, idx+9, idx+16 ...

注意：二次探测不保证访问所有桶。当 \(m\) 是素数且负载因子低于 0.5 时，可以证明二次探测能访问至少一半的桶。当 \(m\) 是 2 的幂时，使用三角数序列 \(h(k, i) = (h(k) + \frac{i(i+1)}{2}) \bmod m\) 可以保证访问所有桶。

双重哈希用第二个哈希函数 \(h_2(k)\) 作为步长，完全消除了二次聚集。缺点是需要计算两个哈希函数，而且探测序列不连续，失去了缓存友好性。

Python dict 的实现：开放寻址 + 紧凑数组

Python 3.6+ 的 dict 使用开放寻址，但有两个独特设计：

紧凑数组分离。Python 把哈希表分成两个数组：一个索引数组（indices）存储指向紧凑条目数组（entries）的偏移。索引数组只存 int8/int16/int32/int64（取决于表大小），entries 数组按插入顺序紧凑存储。

graph LR
    subgraph indices [稀疏索引]
      direction LR
      i0[-1] --- i1[0] --- i2[-1] --- i3[2] --- i4[1] --- i5[-1] --- i6[-1] --- i7[-1]
    end
    subgraph entries [紧凑存储]
      direction TB
      e0["0: (hash_a, 'alice', 1)"]
      e1["1: (hash_b, 'bob', 2)"]
      e2["2: (hash_c, 'charlie', 3)"]
    end
    i1 --> e0
    i4 --> e1
    i3 --> e2

这个设计的好处：(1) 保持了插入顺序（Python 3.7+ 保证 dict 有序）；(2) 索引数组小（稀疏的只是小整数），减少内存浪费；(3) entries 紧凑，迭代时缓存友好。

探测策略。Python 使用的不是简单的线性或二次探测，而是一种伪随机探测：

# CPython dictobject.c 中的探测逻辑（简化）
perturb = hash_value
idx = perturb % size
while slot_not_empty:
    perturb >>= 5
    idx = (5 * idx + perturb + 1) % size

perturb 初始为完整的哈希值，每次右移 5 位。初期探测依赖完整哈希值的所有位（减少聚集），后期退化为 5 * idx + 1（保证遍历所有桶，因为 5 和 \(2^n\) 互素）。

四、Robin Hood Hashing：劫富济贫的优雅

核心思想

Robin Hood Hashing（Celis, 1986）是线性探测的一个优雅变体。核心规则：

如果新元素的探测距离（Probe Sequence Length, PSL）大于当前位置元素的 PSL，交换它们的位置。

PSL 是元素从”理想位置”（哈希值直接映射的桶）到实际位置的距离。

位置:    0   1   2   3   4   5   6   7
理想位:  0   1   0   3   3   2   6   5
PSL:     0   0   2   0   1   3   0   2

在上面的例子中，位置 2 的元素理想位是 0，PSL = 2（走了 2 步才找到空位）。位置 5 的元素理想位是 2，PSL = 3。

Robin Hood 的名字来自”劫富济贫”——PSL 大的元素（“穷人”，走了很远）可以从 PSL 小的元素（“富人”，离家近）手中抢走位置。被驱逐的元素继续向前探测，直到找到一个 PSL 比自己更小的位置或空槽。

flowchart TD
    subgraph before ["① 插入 X，理想位=0，探测到位置 2"]
        direction LR
        b0["[0] A\nPSL=0"] ~~~ b1["[1] B\nPSL=0"] ~~~ b2["[2] C\nPSL=1"] ~~~ b3["[3] 空"]
    end
    subgraph swap ["② X 的 PSL=2 > C 的 PSL=1 → 劫富济贫!"]
        direction LR
        d["X 抢占位置 2，C 被驱逐继续探测"]
    end
    subgraph after ["③ 结果：所有元素 PSL 更均匀"]
        direction LR
        a0["[0] A\nPSL=0"] ~~~ a1["[1] B\nPSL=0"] ~~~ a2["[2] X\nPSL=2"] ~~~ a3["[3] C\nPSL=2"]
    end
    before --> swap --> after

为什么这个策略有效：方差最小化

Robin Hood Hashing 不改变平均探测长度（仍然由负载因子决定），但大幅减小了探测长度的方差。

传统线性探测中，运气好的元素 PSL = 0，运气差的元素 PSL 可能达到 20+。Robin Hood 通过”劫富济贫”，把所有元素的 PSL 压缩到一个很窄的范围内。

理论结果：Robin Hood 线性探测中，最大 PSL 的期望值是 \(O(\log \log n)\)，而传统线性探测是 \(O(\log n)\)。这意味着最坏情况查找快得多。

用一个直觉解释：在 \(10^6\) 个元素的表中，\(\log n \approx 20\)，但 \(\log \log n \approx 4.3\)。最坏的那次查找从 20 步减少到不到 5 步。

Robin Hood 还有一个实践中很重要的性质：查找可以提前终止。在查找 key 时，如果当前位置的元素 PSL 小于我们已经走的距离，就可以立即确定 key 不存在——因为如果 key 在表中，它的 PSL 至少等于我们当前的探测距离（Robin Hood 保证了这一点）。

Rust 旧版 HashMap：Robin Hood 的工业级实现

Rust 1.0 到 1.36 的标准库 HashMap 使用的就是 Robin Hood 哈希。它的具体实现有几个工程细节值得一提：

1. 哈希函数：默认使用 SipHash 1-3（后改为 SipHash 2-4），牺牲少量速度换取 Hash DoS 防护。
2. 负载因子阈值：90.9%（\(\frac{10}{11}\)），比线性探测的典型 70% 高很多——Robin Hood 的低方差允许这么做。
3. PSL 存储：不额外存储 PSL 数组，而是从元素的哈希值和当前位置实时计算。节省内存但增加计算。

Rust 在 1.36 版本将 HashMap 切换到了 hashbrown（Swiss Table 实现），原因是 Swiss Table 在几乎所有基准测试中都更快——特别是在查找密集的工作负载上。

五、Swiss Table：Google 的 SIMD 加速方案

为什么需要 Swiss Table

Robin Hood 已经很好了，但它仍然有一个根本限制：每次探测都需要逐个比较 key。即使用了 PSL 提前终止，在负载因子 0.8 时平均仍需 3 次比较。

Swiss Table（Google, 2017）的核心洞察：用 SIMD 指令并行比较 16 个槽位，把探测的代价降到几乎为零。

Control Byte 设计

Swiss Table 为每个槽位维护一个 1 字节的 control byte（H2）。这个字节的含义：

bit 7 = 0  →  已占用，bit[6:0] = 哈希值的高 7 位（H2）
0xFF       →  空槽（EMPTY）
0x80       →  已删除（DELETED / tombstone）

16 个 control byte 正好 128 位——恰好是一个 SSE2 寄存器的宽度。

flowchart LR
    key["查找 key"] --> hash["hash(key)"]
    hash --> h1["H1 低位\n定位 Group"]
    hash --> h2["H2 高7位\n= 0x3A"]
    h1 --> ctrl["Group: 16 个 ctrl bytes\n3A FF 12 80 3A FF 7F FF ..."]
    h2 --> simd["SIMD 并行比较\n0x3A vs 全部 16 字节\n≈ 2 cycles"]
    ctrl --> simd
    simd --> mask["bitmask = 10001\n位 0 和位 4 命中"]
    mask --> verify["仅对命中位\n比较完整 key"]
    style simd fill:#FFD700,color:#000

SSE2 并行匹配

查找 key 时，Swiss Table 的流程：

// 概念代码：Swiss Table 查找
uint64_t *swisstable_lookup(SwissTable *t, uint64_t key) {
    uint64_t h = hash(key);
    uint8_t h2 = (h >> 57) & 0x7F;            // 高 7 位作为 control byte
    size_t group_idx = (h & t->mask) >> 4;     // 定位到 16 元素的 group

    for (size_t probe = 0; ; probe++) {
        size_t gi = (group_idx + probe) & t->group_mask;
        __m128i ctrl = _mm_loadu_si128(&t->control[gi * 16]);
        __m128i match = _mm_cmpeq_epi8(ctrl, _mm_set1_epi8(h2));
        uint32_t mask = _mm_movemask_epi8(match);

        while (mask) {
            int bit = __builtin_ctz(mask);     // 第一个匹配位
            size_t slot = gi * 16 + bit;
            if (t->keys[slot] == key)
                return &t->values[slot];
            mask &= mask - 1;                  // 清除最低位
        }

        // 检查是否有空槽（有空槽说明 key 不存在）
        __m128i empty = _mm_cmpeq_epi8(ctrl, _mm_set1_epi8(0xFF));
        if (_mm_movemask_epi8(empty))
            return NULL;
    }
}

关键的三条 SIMD 指令：

1. _mm_set1_epi8(h2)：把 H2 值广播到 128 位寄存器的所有 16 个字节。
2. _mm_cmpeq_epi8：并行比较 16 个 control byte，匹配的字节置为 0xFF，不匹配的置为 0x00。
3. _mm_movemask_epi8：把每个字节的最高位提取出来，生成一个 16 位的 bitmask。

这三条指令在现代 CPU 上总共只需要 2-3 个时钟周期。一次操作就排除了 16 个候选中的绝大多数——只有 H2 匹配的才需要进一步比较完整 key。

为什么 0.875 的负载因子也能高效

传统线性探测在 0.875 负载因子下，平均需要约 4.5 次逐个比较。但 Swiss Table 一次 SIMD 操作覆盖 16 个槽位，等效于一次操作做了 16 次比较。在 0.875 负载因子下，平均只需要约 1.2 次 group 探测——即 1.2 次 SIMD 操作。

这就是 Swiss Table 能用更高负载因子（更省内存）同时保持更高性能的秘密。

Abseil 与 Rust hashbrown

Google 在 Abseil C++ 库中开源了 Swiss Table 的 C++ 实现（absl::flat_hash_map、absl::node_hash_map）。Rust 社区的 Amanieu d’Antras 独立实现了 hashbrown crate，已成为 Rust 标准库 HashMap 的底层实现。

两者的主要区别：

在没有 SSE2 的平台（如 32 位 ARM），两者都退化为 8 字节一组的 portable 实现，用普通的位运算模拟 SIMD 匹配——性能不如 SSE2 版本但仍然快于传统方案。

六、扩容策略：负载因子选择与渐进式 Rehash

负载因子的选择：0.5 vs 0.75 vs 0.875

负载因子（load factor）\(\alpha = n / m\) 直接决定了哈希表的空间-时间权衡。不同策略选择不同的阈值：

选错负载因子的代价是巨大的。以线性探测为例：

α = 0.50 → 平均 1.5 次探测，最大约 10 次
α = 0.75 → 平均 2.5 次探测，最大约 30 次
α = 0.90 → 平均 5.5 次探测，最大约 80 次
α = 0.95 → 平均 10.5 次探测，最大约 200 次

从 0.75 到 0.95，空间只节省了约 21%，但查找性能恶化了 4 倍以上。

全量 Rehash

最简单的扩容策略：分配一个 2 倍大的新数组，把所有元素重新哈希插入。

void rehash_full(HashMap *map) {
    size_t new_cap = map->capacity * 2;
    // 分配新数组
    uint64_t *new_keys = calloc(new_cap, sizeof(uint64_t));
    uint64_t *new_values = calloc(new_cap, sizeof(uint64_t));
    uint8_t *new_states = calloc(new_cap, sizeof(uint8_t));

    // 重新插入所有元素
    for (size_t i = 0; i < map->capacity; i++) {
        if (map->states[i] == OCCUPIED) {
            size_t idx = hash(map->keys[i]) % new_cap;
            // ... 在新数组中用相同策略探测插入 ...
        }
    }

    free(map->keys); free(map->values); free(map->states);
    map->keys = new_keys;
    map->values = new_values;
    map->states = new_states;
    map->capacity = new_cap;
}

问题：对于 \(n\) 个元素的表，rehash 是 O(n) 操作。100 万个元素的表，rehash 约需 2-5 毫秒。对于延迟敏感的应用（如 Redis、游戏服务器），这个停顿不可接受。

渐进式 Rehash：Redis 与 Go 的做法

Redis 的实现。Redis 的字典使用了渐进式 rehash：维护两个哈希表 ht[0]（旧）和 ht[1]（新）。不在一次操作中完成所有 rehash，而是分摊到后续的 insert/lookup/delete 操作中。

// Redis 渐进式 rehash（概念代码）
typedef struct {
    Entry **ht[2];        // 两个哈希表
    long rehashidx;       // 当前 rehash 进度，-1 表示不在 rehash
    size_t size[2];
} RedisDict;

void *redis_lookup(RedisDict *d, void *key) {
    if (d->rehashidx != -1)
        rehash_step(d);  // 每次操作顺便 rehash 一步

    // 两个哈希表都要查
    for (int i = 0; i <= 1; i++) {
        size_t idx = hash(key) % d->size[i];
        Entry *e = d->ht[i][idx];
        while (e) {
            if (key_compare(e->key, key) == 0) return e->value;
            e = e->next;
        }
        if (d->rehashidx == -1) break;
    }
    return NULL;
}

每次 rehash_step 迁移一个旧桶的所有元素到新表。渐进式 rehash 避免了大停顿（latency spike），代价是 rehash 期间每次操作都需要查两个表。

Go 的 evacuate。Go 的渐进式扩容更精细。每次 map 写操作触发 growWork，迁移 1-2 个旧 bucket。Go 的扩容分两种：

1. 翻倍扩容（sameSizeGrow = false）：当负载因子超过 6.5 时，bucket 数量翻倍。
2. 等量扩容（sameSizeGrow = true）：当 overflow bucket 过多但负载因子不高时，不增加 bucket 数量，只是重新整理——消除 overflow 链的碎片。

等量扩容是 Go 独有的设计，目的是处理”大量插入后大量删除”的场景：元素变少了，但 overflow bucket 链很长，查找效率下降。

七、删除问题：Tombstone、Backward Shift 与 Robin Hood 的优势

Tombstone 的问题

开放寻址中，删除一个元素不能简单地标记为空（EMPTY）。因为后面的元素可能是通过这个位置”跳过去”的——把它标记为空会切断探测链，导致这些元素永远找不到。

解决方案是标记为已删除（DELETED / tombstone）。探测时，tombstone 被视为”已占用但不匹配”——跳过继续探测。

查找 key C（哈希到位置 2）:
位置:  [A][B][TOMB][D][C][ ]
              ↑ 不能停，继续探测 → 找到 C

如果把 TOMB 标为空:
位置:  [A][B][EMPTY][D][C][ ]
              ↑ 停止！认为 C 不存在 → 错误！

tombstone 的问题：

1. 虚高负载因子：tombstone 占着位置但不是有效元素。表面上负载因子低，实际上探测链很长。
2. 性能退化：大量 insert-delete 循环后，表中充满 tombstone，查找性能回到高负载水平。
3. 需要定期 rebuild：唯一的修复方法是全量 rehash，消除所有 tombstone。

Backward Shift Deletion：Robin Hood 的优势

Robin Hood Hashing 支持一种优雅的 backward-shift deletion：删除一个元素后，把后面所有”距离家太远”的元素往前移一位，填补空洞。由于 Robin Hood 保证了 PSL 的单调性（探测序列上 PSL 单调递增），移位操作在遇到 PSL = 0 的元素或空槽时停止。

删除前:
位置:  [A:0][B:0][C:2][D:0][E:1][F:3][ ]
PSL:    0    0    2    0    1    3

删除 C（位置 2）:
位置:  [A:0][B:0][ ? ][D:0][E:1][F:3][ ]

backward shift:
D 的 PSL=0 → 不移动，停止
最终:
位置:  [A:0][B:0][  ][D:0][E:1][F:3][ ]
                  ↑ 真正的空槽

等等，上面的例子 D 已经在 PSL=0 的位置，所以不需要移动。看一个更有意义的例子：

删除前:
位置:  [A:0][B:1][C:2][D:3][ ]
PSL:    0    1    2    3

删除 A（位置 0）:
step 1: B 的 PSL=1 > 0 → 移到位置 0，PSL 变为 0
step 2: C 的 PSL=2 > 0 → 移到位置 1，PSL 变为 1
step 3: D 的 PSL=3 > 0 → 移到位置 2，PSL 变为 2
step 4: 位置 4 为空 → 停止

删除后:
位置:  [B:0][C:1][D:2][ ][ ]
PSL:    0    1    2

没有 tombstone，性能不会随着删除操作而退化。这是 Robin Hood 相对于普通线性探测最大的工程优势。

Swiss Table 的删除策略

Swiss Table 使用 tombstone（control byte 置为 0x80），但通过两个机制缓解 tombstone 的问题：

1. growth_left 计数器：不仅追踪已用槽位数，还追踪”可用于新插入的槽位数”——空槽减去 tombstone。当 growth_left 降为 0 时触发 rehash，即使实际负载因子不高。
2. 插入时复用 tombstone：新插入的元素优先使用 tombstone 槽位，自然回收。
3. rehash 清除：每次 rehash 都会消除所有 tombstone。

八、完整 C 实现：Robin Hood 哈希表

以下是一个完整的、可编译运行的 Robin Hood 哈希表实现，支持插入、查找、删除和自动扩容。约 150 行。

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

#define RH_EMPTY       0
#define RH_MAX_LOAD    0.7
#define RH_INIT_CAP    16
#define RH_NOT_FOUND   SIZE_MAX

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

typedef struct {
    uint64_t *keys;
    uint64_t *values;
    uint8_t  *psl;        // PSL+1，0 表示空槽
    size_t    capacity;
    size_t    size;
} RHMap;

RHMap *rh_create(size_t cap) {
    RHMap *m = malloc(sizeof(RHMap));
    if (cap < RH_INIT_CAP) cap = RH_INIT_CAP;
    // 确保 capacity 是 2 的幂
    size_t c = 1;
    while (c < cap) c <<= 1;
    m->capacity = c;
    m->size     = 0;
    m->keys     = calloc(c, sizeof(uint64_t));
    m->values   = calloc(c, sizeof(uint64_t));
    m->psl      = calloc(c, sizeof(uint8_t));
    return m;
}

void rh_free(RHMap *m) {
    free(m->keys); free(m->values); free(m->psl); free(m);
}

static void rh_insert_inner(RHMap *m, uint64_t key, uint64_t val, uint8_t dist);
static void rh_grow(RHMap *m);

void rh_insert(RHMap *m, uint64_t key, uint64_t value) {
    if ((double)(m->size + 1) / m->capacity > RH_MAX_LOAD)
        rh_grow(m);

    size_t mask = m->capacity - 1;
    size_t idx  = rh_hash(key) & mask;
    uint8_t dist = 1;    // PSL+1，从 1 开始，0 保留给空槽

    for (;;) {
        if (m->psl[idx] == RH_EMPTY) {
            m->keys[idx]   = key;
            m->values[idx] = value;
            m->psl[idx]    = dist;
            m->size++;
            return;
        }
        if (m->keys[idx] == key) {
            m->values[idx] = value;   // 更新已有 key
            return;
        }
        if (dist > m->psl[idx]) {
            // Robin Hood：新元素的 PSL 更大，抢占当前位置
            uint64_t tk = m->keys[idx];   uint64_t tv = m->values[idx];
            uint8_t  tp = m->psl[idx];
            m->keys[idx]   = key;         m->values[idx] = value;
            m->psl[idx]    = dist;
            key = tk;  value = tv;  dist = tp;
        }
        dist++;
        idx = (idx + 1) & mask;
    }
}

uint64_t *rh_lookup(RHMap *m, uint64_t key) {
    size_t mask = m->capacity - 1;
    size_t idx  = rh_hash(key) & mask;
    uint8_t dist = 1;

    for (;;) {
        if (m->psl[idx] == RH_EMPTY || dist > m->psl[idx])
            return NULL;               // 提前终止：key 不存在
        if (m->keys[idx] == key)
            return &m->values[idx];
        dist++;
        idx = (idx + 1) & mask;
    }
}

int rh_delete(RHMap *m, uint64_t key) {
    size_t mask = m->capacity - 1;
    size_t idx  = rh_hash(key) & mask;
    uint8_t dist = 1;

    // 查找 key 的位置
    for (;;) {
        if (m->psl[idx] == RH_EMPTY || dist > m->psl[idx])
            return 0;                  // key 不存在
        if (m->keys[idx] == key)
            break;
        dist++;
        idx = (idx + 1) & mask;
    }

    // backward-shift deletion
    for (;;) {
        size_t next = (idx + 1) & mask;
        if (m->psl[next] <= 1) {       // 空槽或 PSL=0 的元素
            m->psl[idx] = RH_EMPTY;
            m->size--;
            return 1;
        }
        m->keys[idx]   = m->keys[next];
        m->values[idx] = m->values[next];
        m->psl[idx]    = m->psl[next] - 1;   // PSL 减 1（往前移了一步）
        idx = next;
    }
}

static void rh_grow(RHMap *m) {
    size_t old_cap   = m->capacity;
    uint64_t *ok     = m->keys;
    uint64_t *ov     = m->values;
    uint8_t  *op     = m->psl;

    m->capacity = old_cap * 2;
    m->size     = 0;
    m->keys     = calloc(m->capacity, sizeof(uint64_t));
    m->values   = calloc(m->capacity, sizeof(uint64_t));
    m->psl      = calloc(m->capacity, sizeof(uint8_t));

    for (size_t i = 0; i < old_cap; i++) {
        if (op[i] != RH_EMPTY)
            rh_insert(m, ok[i], ov[i]);
    }
    free(ok); free(ov); free(op);
}

几个实现细节说明：

1. PSL 编码：用 psl[i] = 0 表示空槽，psl[i] = d+1 表示 PSL 为 d。这样只用一个数组就同时编码了”是否为空”和”探测距离”。
2. 容量为 2 的幂：用位与 & mask 代替取模 % capacity，少一次除法。
3. 哈希函数：使用 splitmix64 的 finalizer，对整数 key 足够好。生产环境应使用 wyhash 或 xxhash。
4. backward-shift deletion：删除后把后续元素往前移，每移一步 PSL 减 1，遇到 PSL=0 或空槽停止。无 tombstone。

九、当前环境的真实 benchmark 结果

先说测试口径。当前仓库这次重跑的是：

• 数据类型：uint64_t -> uint64_t
• 槽位/桶数量：1,048,576
• 负载因子：0.50、0.70、0.80、0.875
• 查找：100% 命中，4,000,000 次操作，5 轮取中位数
• 插入：从空表插入到目标负载，5 轮取中位数
• 删除：把已经存在的 key 按随机顺序全部删掉，5 轮取中位数
• 链式实现是本文配套的 separate chaining，不是 glibc hsearch
• Swiss Table 条目是本文配套的简化参考实现，保留了 control byte + SIMD 匹配 + tombstone 的核心路径，不等同于 Abseil 的完整工业实现

测试环境：x86-64 Linux，12th Gen Intel Core i9-12900K，GCC 15.2.1。

先看趋势图，再看下面三张表里的精确数值。

查找吞吐量（Mops/s，越大越好）

这里最值得记住的不是某个绝对数字，而是三个趋势：

• Swiss Table 在所有负载因子下都第一，而且高负载下优势更明显。
• 线性探测在这套简单实现里一直快于 Robin Hood。理论上 Robin Hood 降低了 probe distance 的方差，但工程上它要维护 PSL、插入时更多 swap，常数因子并不免费。
• 链式哈希的下降最平缓，但绝对吞吐量始终最低。它的卖点是稳定和简单，不是峰值性能。

插入吞吐量（Mops/s）

这组数据比旧稿更能说明问题：Robin Hood 的插入代价确实随着负载升高而明显增加，原因就是它为了压低方差，在插入路径上做了更多的交换和 PSL 维护。Swiss Table 的 SIMD 过滤和高效空槽搜索，让它在高负载下依然保持了最好的插入吞吐量。

删除吞吐量（Mops/s）

这组结果顺手也纠正了旧稿的一句过度概括。如果只测 delete 本身，backward-shift 并不比 tombstone 更快。 相反，tombstone 删除只是写一个状态位，吞吐量会更高。Robin Hood 的真正优势不是“单次 delete 更快”，而是“删完以后后续查找和插入不被 tombstone 拖慢”。要验证这一点，需要单独测 mixed workload，而当前仓库这次并没有对应的可复现脚本，所以我不继续编造那张表。

这次重跑后，哪些表必须删

旧稿里的 Python dict 风格、glibc 链式、混合工作负载、内存占用和 0.90 负载因子表，这次全部删掉。原因很简单：当前仓库没有与这些表一一对应的实现、脚本或原始测量结果。没有源码和 CSV 支撑的数字，不应该继续出现在正文里。

十、工程陷阱表

十一、各语言标准库实现对比表

几个值得注意的点：

1. Python 和 Ruby 保证插入顺序——这是通过紧凑数组分离实现的，遍历紧凑数组即按插入顺序。
2. Go 故意随机化遍历顺序——每次 range map 的起始 bucket 是随机的，防止程序依赖遍历顺序。
3. Rust 从 Robin Hood 切换到 Swiss Table——这是整个行业趋势的缩影。
4. C++ std::unordered_map 是最慢的——链式 + 1.0 负载因子 + 没有任何现代优化。但它的 API 保证（指针稳定性、桶接口）使得改进极其困难。

十二、个人观点：为什么 Swiss Table 会统一天下

现状

哈希表是一个已经被研究了 60 多年的数据结构。从 1953 年 Luhn 的第一个哈希表，到 1986 年 Celis 的 Robin Hood，到 2017 年 Google 的 Swiss Table——每一次重大进步都与硬件架构的演进紧密相关。

Swiss Table 的崛起不是偶然的。它精确地利用了现代 CPU 的三个特性：

1. SIMD 无处不在。SSE2 在 2001 年引入 x86，到今天连 ARM（NEON）和 RISC-V（Vector Extension）都有了 SIMD 支持。Swiss Table 的核心操作——128 位并行字节比较——在所有主流架构上都能高效执行。
2. 缓存行仍然是 64 字节。Swiss Table 的 group 大小（16 个 control byte = 16 字节）远小于一个缓存行，意味着加载 control byte 几乎不产生额外的缓存未命中。
3. 分支预测对数据依赖的操作效率低。链式哈希的链表遍历是典型的数据依赖操作——每次 next 指针的值取决于上一次加载的结果，流水线无法推测执行。Swiss Table 的 SIMD 匹配消除了这种数据依赖。

趋势

看一下最近几年的变化：

• Rust：2019 年将标准库 HashMap 从 Robin Hood 切换到 hashbrown（Swiss Table）。
• Go：Go 1.24（2025）引入了 Swiss Table 实现，替代了沿用 10 年的 bucket 数组设计。
• Zig：标准库 HashMap 使用 Swiss Table 风格的实现。
• .NET 9：实验性的 FrozenDictionary 使用了 SIMD 加速的哈希匹配。
• abseil-cpp：Swiss Table 已成为 Google 内部所有 C++ 代码的默认哈希表。

Robin Hood Hashing 是我个人最喜欢的哈希表变体。不是因为它最快（Swiss Table 更快），而是因为它的设计理念——“劫富济贫”——太优雅了。用一个简单的 PSL 比较和交换操作，就把探测长度的方差从 \(O(\log n)\) 压缩到 \(O(\log \log n)\)。这种”用微小的额外工作换取巨大的最坏情况改善”的思路，在系统设计中到处适用。

但优雅不等于最优。至少在当前仓库这套实现和当前环境下，Swiss Table 在查找、插入、删除三项吞吐量上都领先。至于长期 mixed workload 下 tombstone 的尾部影响、以及更完整的内存占用对比，应该单独测，而不是靠想象补表。

未来

Swiss Table 可能不是终点。几个可能的方向：

1. 更宽的 SIMD：AVX-512 可以一次比较 64 个 control byte。ARM SVE 支持可变长度向量。更宽的 SIMD 意味着更大的 group，更高的匹配效率。
2. 硬件加速哈希：Intel 的 CRC32 指令已经被广泛用于哈希计算，未来可能出现专用的哈希表指令。
3. 持久化内存（CXL/PMEM）上的哈希表：需要不同的 crash consistency 策略，Swiss Table 的设计可能需要调整。
4. GPU 哈希表：CUDA 上的并行哈希表（如 cudf 的 concurrent_unordered_map）面临完全不同的权衡——上千个线程同时操作，冲突解决策略需要 lock-free 或 cooperative 设计。

但无论硬件怎么变，Swiss Table 建立的范式——分离元数据 + SIMD 并行匹配 + 高负载因子——很可能会持续主导未来十年的哈希表设计。

系列导航： - 上一篇：排序基准测试：用数据说话 - 下一篇：Cuckoo Hashing：最坏 O(1) 查找的优雅设计

相关阅读： - Swiss Table：Google 的 SIMD 加速哈希表 - 密码学哈希 vs 非密码学哈希