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

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

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

• Python 的 dict：开放寻址 + 紧凑数组
• Go 的 map：链式哈希（bucket 数组 + overflow 链）
• Java 的 HashMap：链式哈希（链表 + 红黑树）
• Rust 的 HashMap：Swiss Table（开放寻址 + SIMD 元数据）

同一个抽象数据结构，四种截然不同的实现。每一种都有深刻的工程理由。本文将从最基本的哈希冲突解决策略出发，逐层深入三大流派——链式哈希、经典开放寻址、Robin Hood 哈希——的设计决策，然后用基准测试数据回答”到底哪个快”的问题。

一、哈希的基本操作与冲突

哈希函数的角色

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

理想情况下，所有 key 均匀分布到 \(m\) 个桶中。但现实中冲突不可避免——当两个不同的 key 映射到同一个桶时，就需要冲突解决策略。

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

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

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

基本思想

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

// 链式哈希表的基本结构
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 *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），几乎必然缓存未命中。

在我的测试中（AMD EPYC, 100 万个 64 位 key-value），链式哈希在负载因子 0.5 时的平均查找延迟是 45ns。同样负载因子的线性探测开放寻址只需要 25ns——差距完全来自缓存命中率。

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

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

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

代价是红黑树节点更大（每个节点需要颜色位、左右子指针、父指针），对正常情况有轻微的性能损失。

Go 的设计：bucket 数组

Go 的 map 是链式哈希的变体。每个 bucket 存储 8 个 key-value 对（不是链表！），满了之后链接到 overflow bucket。

bucket 0: [k0 k1 k2 k3 k4 k5 k6 k7 | tophash[8] | overflow*]
bucket 1: [k0 k1 k2 k3 k4 k5 k6 k7 | tophash[8] | overflow*]
...

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

Go 的 bucket 设计比纯链表更缓存友好（8 个 key 在连续内存中），但比开放寻址的紧凑数组还是差一些。

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

基本思想

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

三种经典探测策略：

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

线性探测：缓存最友好

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

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 碰到它的概率越高——正反馈循环。

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 加速，对抗了聚集的影响。

四、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 小的元素（“富人”，离家近）手中抢走位置。

为什么这个策略有效

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

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

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

Robin Hood 的额外福利：删除简化

传统开放寻址的删除很麻烦——不能直接清空桶（会破坏探测链），必须使用 tombstone。tombstone 会降低性能并使负载因子虚高。

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

void robin_hood_delete(RobinHoodMap *map, uint64_t key) {
    size_t idx = find(map, key);
    if (idx == NOT_FOUND) return;

    // backward-shift: 后面的元素往前移
    while (1) {
        size_t next = (idx + 1) % map->capacity;
        if (map->states[next] == EMPTY || psl(map, next) == 0)
            break;  // 下一个元素在"家"的位置或为空，停止
        map->keys[idx] = map->keys[next];
        map->values[idx] = map->values[next];
        idx = next;
    }
    map->states[idx] = EMPTY;
    map->size--;
}

没有 tombstone，性能不会随着删除操作而退化。

Robin Hood 的实现

typedef struct {
    uint64_t *keys;
    uint64_t *values;
    uint8_t *psls;       // 每个位置的 PSL
    size_t capacity;
    size_t size;
} RobinHoodMap;

void robin_hood_insert(RobinHoodMap *map, uint64_t key, uint64_t value) {
    if ((double)map->size / map->capacity > 0.7)
        robin_hood_resize(map);

    size_t idx = hash(key) % map->capacity;
    uint8_t psl = 0;

    while (1) {
        if (map->psls[idx] == 0 && map->keys[idx] == 0) {
            // 空位，直接插入
            map->keys[idx] = key;
            map->values[idx] = value;
            map->psls[idx] = psl + 1;  // 存储 PSL+1，0 表示空
            map->size++;
            return;
        }
        if (psl + 1 > map->psls[idx]) {
            // Robin Hood: 新元素的 PSL 更大，抢走当前位置
            // 交换
            uint64_t tmp_key = map->keys[idx];
            uint64_t tmp_val = map->values[idx];
            uint8_t tmp_psl = map->psls[idx];
            map->keys[idx] = key;
            map->values[idx] = value;
            map->psls[idx] = psl + 1;
            key = tmp_key;
            value = tmp_val;
            psl = tmp_psl;  // 被驱逐的元素继续寻找位置
        } else {
            psl++;
        }
        idx = (idx + 1) % map->capacity;
    }
}

五、PSL 分布与负载因子的关系

不同策略在不同负载因子下的平均探测长度（成功查找）：

注意：Robin Hood 的平均探测长度与普通线性探测相同（因为总探测次数不变，只是分布更均匀）。差异在方差：

Robin Hood 的最大 PSL 远小于线性探测，使得最坏情况性能更可预测。

六、缓存行分析

为什么开放寻址在现代硬件上比链式哈希快？关键在缓存行。

CPU L1 Cache Line = 64 bytes

链式哈希:
  查找 → hash → bucket[idx] → 指针跳转 → entry1 → entry1.next → entry2
  每次指针跳转 = 1 次潜在的缓存未命中

线性探测:
  查找 → hash → slot[idx] → slot[idx+1] → slot[idx+2]
  连续的内存访问 = 硬件预取器工作
  一个缓存行可容纳多个 slot

实测 perf stat 对比（100 万次查找，负载因子 0.5）：

开放寻址的 L1 缓存未命中率不到链式哈希的 1/3。这就是为什么现代高性能哈希表几乎都选择了开放寻址。

七、扩容策略

翻倍扩容

所有哈希表都需要在负载因子达到阈值时扩容。最常见的策略是翻倍（capacity × 2），然后 rehash 所有元素。

翻倍扩容的问题：在扩容的那一刻，需要分配一个新数组并 rehash 所有 \(n\) 个元素——O(n) 操作。对于 100 万个元素的哈希表，这可能需要几毫秒。

渐进式 rehash（Redis 的做法）

Redis 的字典使用了渐进式 rehash：不在一次操作中完成所有 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;  // 不在 rehash，只查第一个表
    }
    return NULL;
}

渐进式 rehash 避免了大停顿（latency spike），代价是 rehash 期间每次操作都需要查两个表。

八、真实工作负载性能对比

测试环境：AMD EPYC 7763, GCC 12.2 -O2, 100M 个 64 位 key-value。

查找吞吐量（Mops/s）

Swiss Table（下篇文章详述）在所有负载因子下都是最快的——因为它用 SIMD 指令并行检查 16 个元素。Robin Hood 紧随其后。纯链式哈希一直垫底。

插入吞吐量（Mops/s）

高负载因子下，Robin Hood 的插入速度下降明显（需要更多交换），Swiss Table 保持平稳。

九、工程踩坑备忘

十、总结与个人思考

策略选型

我的观点

哈希表是一个已经被研究了 60 多年的数据结构，但直到 2017 年 Google 发布 Swiss Table，才真正用 SIMD 把性能推到了硬件极限。这告诉我们：“经典”不意味着”没有优化空间”。 很多我们认为已经最优的数据结构，其实还有被硬件特性重新审视的余地。

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

上一篇: （系列索引）
下一篇: Cuckoo Hashing：最坏 O(1) 查找的优雅设计

相关阅读: - Swiss Table：Google 的 SIMD 加速哈希表 - Bloom Filter 全家族 - 密码学哈希 vs 非密码学哈希