Hash 表与 Map — 从理论到工程实现

#数据结构 · #哈希表 · #冲突解决 · #扩容 · #SwissTable · #底层实现

Hash 表是计算机科学中最常用的数据结构。本文从哈希函数设计原理出发，深入 slot 选择算法、冲突解决策略、负载因子与扩容机制，最后对比 Go / C++ / Python / Redis / SwissTable 五大实现。

---

1. 核心概念

Key → Hash Function → Hash Value → Slot Index → Bucket
                               ↑
                         碰撞了怎么办？

1.1 一个 Hash 表的生命周期

1. 初始化: 分配 B 个 bucket
2. 插入: hash(key) → slot → 放入 bucket
3. 冲突: 如果 slot 已被占用 → 冲突解决
4. 扩容: 元素太多 (α > threshold) → 增加 bucket 数
5. Rehash: 所有 key 重新 hash 到新 bucket

sequenceDiagram
    participant K as Key
    participant HF as Hash Function
    participant B as Bucket Array
    participant OLD as Old Buckets
    participant NEW as New Buckets

    rect rgb(240, 248, 255)
        Note over K,NEW: 正常查找流程
        K->>HF: hash(key)
        HF->>B: index = hash & (2^B - 1)
        B->>B: 在bucket中比较 tophash → key → 返回value
    end

    rect rgb(255, 248, 240)
        Note over K,OLD: 渐进式 Rehash (Go/Redis)
        K->>HF: hash(key)
        HF->>OLD: 先查旧表 oldbuckets
        OLD->>NEW: 未找到 → 再查新表 buckets
        Note over OLD,NEW: 每次操作顺便搬1-2个旧bucket
    end

1.2 四个核心指标

指标	公式	含义	典型值
负载因子 α	n / B	每个 bucket 平均元素数	0.6~6.5
碰撞率	collisions / insertions	插入时冲突比例	越小越好
空间利用率	实际存储 / 总容量	内存效率	越高越好
平均探测长度	查找的平均步数	实际性能	α 的函数

---

2. 哈希函数设计

哈希函数决定了整个 hash 表的性能上限。一个差哈希函数 = 不管用多好的冲突策略都会退化成 O(n)。

2.1 哈希函数的两个角色

	角色 1: 打散	角色 2: 安全
目标	均匀分布	抗碰撞攻击 (HashDoS)
输入	任意数据	攻击者构造的恶意 key
要求	雪崩效应（改变 1 bit → 输出 50% bit 翻转）	不可预测性（无法预计算碰撞）
例子	MurmurHash, xxHash	SipHash, SHA-256

2.2 常用哈希函数详解

2.2.1 MurmurHash — 经典通用哈希

由 Austin Appleby 在 2008 年设计。
核心: 乘法 + 位移 + XOR 的乘法散列

uint32_t murmur3_32(const uint8_t* key, size_t len, uint32_t seed) {
    uint32_t h = seed;
    // 每个 4 字节块: h ^= block; h *= 0xcc9e2d51; h = rotl(h, 15); h *= 0x1b873593;
    // 尾部 + finalize: h ^= h >> 16; h *= 0x85ebca6b; h ^= h >> 13; h *= 0xc2b2ae35; h ^= h >> 16;
    return h;
}

特点：极快（~3-5 GB/s），分布优秀，但不是加密安全级（可预测碰撞）。

使用者：nginx、libstdc++ std::hash<std::string>、Hadoop、Apache HBase。

2.2.2 SipHash — 防 HashDoS 的标准答案

由 Jean-Philippe Aumasson 和 Daniel J. Bernstein 在 2012 年设计。
SipHash-2-4: 2 轮压缩 + 4 轮终结。

关键: 需要一个 128 位随机密钥（进程启动时生成）。
攻击者不知道密钥 → 无法预计算碰撞 → HashDoS 不可行。

使用者：Python dict（3.4+）、Redis dict、Rust HashMap、FreeBSD、OpenBSD。

2.2.3 xxHash — 极速哈希

由 Yann Collet (LZ4 作者) 设计。非加密哈希的速度天花板（~15-30 GB/s）。

xxHash64: 比 MurmurHash 快 2×，比 SipHash 快 10×+
xxHash3: 最新版本，支持 SIMD 加速和 128 位输出

使用者：ClickHouse、Presto、Apache Arrow、RocksDB（WAL 校验）。

2.2.4 Go 的 memhash — 基于 AES 指令

// runtime/alg.go
// 在支持 AES-NI 的 CPU 上，Go 用 AESENC 指令做哈希
// AESENC(state, key) → 一轮 AES 加密 → 天然具有雪崩效应

func memhash(p unsafe.Pointer, h, s uintptr) uintptr {
    // 1. 先用 h (hash0) 做种子
    // 2. 在支持 AES-NI 的机器上用 AES 指令
    // 3. 否则回退到 xxHash 风格的乘法哈希
}

2.2.5 各哈希函数对比

函数	速度 (GB/s)	抗 HashDoS	输出位	使用者
xxHash64	~15-30	❌	64	ClickHouse, RocksDB
MurmurHash3	~5-8	❌	32/128	nginx, libstdc++
SipHash-2-4	~1-2	✅	64	Python, Redis, Rust
AES-based (Go)	~10-20	✅	64	Go map
CityHash	~8-15	❌	64/128	Google 内部
SHA-256	~0.2	✅	256	需要加密安全时

2.3 哈希质量验证："雪崩效应"测试

# 一个好的 hash 函数，改变 1 bit 输入 → ~50% 输出 bit 翻转
def avalanche_test(hash_fn):
    for original in test_inputs:
        h1 = hash_fn(original)
        for bit in range(len(original)*8):
            flipped = original ^ (1 << bit)  # 翻转 1 bit
            h2 = hash_fn(flipped)
            diff_bits = bin(h1 ^ h2).count('1')
            # 期望: diff_bits / total_bits ≈ 0.5

2.4 各语言如何选择 Hash 函数

语言	整数的 hash	字符串的 hash	为什么
Go	uintptr(key) 直接映射	AES-NI memhash	快 + 防 HashDoS
Java	h ^ (h >>> 16)	h = 31*h + c	传统 + JDK 1.0 兼容
Python	hash(key) = key	SipHash	防 HashDoS (2012 年被攻击后切换)
Rust	随机种子 + 乘法	SipHash-1-3	安全和速度的折中
C++ std	std::hash 实现定义	MurmurHash (libstdc++)	标准只要求一致性
Redis	SipHash	SipHash	安全（云服务防攻击）

---

3. Slot 选择算法

3.1 核心问题

hash(key) → 一个 64 位整数 → 如何映射到 [0, B-1]？

有三大流派，各有优劣。

3.2 取模法（Modulo）：index = hash % B

// B 必须是质数
index = hash(key) % table_size;

为什么 B 必须是质数？——从数论角度的完整推导

核心问题: hash(key) % B 的分布均匀性取决于 hash 值和 B 的关系。

情况 1: hash 值有规律（非完全随机）
  假设 hash 函数产生的值有某种模式:
    hash(key_i) = c × i + offset  (线性分布，步长为 c)

  那么 hash(key_i) % B = (c × i + offset) % B

  如果 gcd(c, B) = d > 1:
    结果只能落在 B/d 个不同的 slot 上！

    例: c=6, B=12 → gcd(6,12)=6
    6×0%12=0, 6×1%12=6, 6×2%12=0, 6×3%12=6, ...
    → 只用了 2 个 slot (0 和 6)！其他 10 个 slot 空着

  如果 B 是质数:
    对任意 c (1 ≤ c < B), gcd(c, B) = 1（质数与任何小于它的数互质）
    → c×i % B 会遍历所有 B 个值（费马小定理的推论）
    → 分布均匀 ✅

情况 2: hash 值是某个数的倍数
  实际中很常见:
    - 对象地址通常是 8 的倍数（内存对齐）
    - 字符串长度可能集中在某些值
    - 时间戳的低位可能有规律

  如果 B = 2^n:
    hash % 2^n = hash 的低 n 位
    如果 hash 总是 8 的倍数 → 低 3 位总是 000
    → hash % 8 = 0（全部映射到 slot 0）
    → hash % 16: 只用了 slot 0, 8（低 4 位只有 0000, 1000）

  如果 B 是质数（如 B=13）:
    8×0%13=0, 8×1%13=8, 8×2%13=3, 8×3%13=11, 8×4%13=6, ...
    → 遍历所有 13 个 slot ✅

数学本质:
  Z/BZ（模 B 的整数环）中，乘法群 (Z/BZ)* 的阶 = φ(B)
  当 B 是质数时: φ(B) = B-1 → 乘法群最大 → 分布最均匀
  当 B 是合数时: φ(B) < B-1 → 某些乘数无法生成所有余数

结论: 质数 B 对 hash 函数的质量要求最低——即使 hash 函数有偏差，
     质数取模也能"修正"分布。代价是除法指令比位运算慢。

使用者：C++ std::unordered_map（多数实现）、Python 旧版 dict。

优点：对 hash 函数质量要求低。 缺点：取模运算 = 除法指令 → 比位运算慢 5-10×。

3.3 位掩码法（Power of Two）：index = hash & (B-1)

// B 必须是 2^n
index = hash(key) & (table_size - 1);  // 等价于 hash % B，但快得多

关键挑战：只用了 hash 值的低位 → 要求 hash 函数低位有足够的随机性。

如果 hash 函数的低位分布不均：
  hash = 0x????0000, 0x????0010, 0x????0020...  ← 低位没变化
  & (16-1) = & 0xF → 全部映射到 slot 0！

2 的幂如何解决分布不均匀？——各语言的扰动函数设计

问题: hash & (B-1) 只取低位 → 高位信息完全丢失 → 分布可能不均

解决方案: 在取低位之前，先让高位"混入"低位 → 扰动函数

═══════════════════════════════════════════════════════════════
Java HashMap 的扰动函数:
═══════════════════════════════════════════════════════════════

  static int hash(Object key) {
      int h = key.hashCode();
      return h ^ (h >>> 16);  // 高 16 位 XOR 到低 16 位
  }

  原理:
    原始 hash:  AAAA AAAA BBBB BBBB CCCC CCCC DDDD DDDD
    h >>> 16:   0000 0000 0000 0000 AAAA AAAA BBBB BBBB
    XOR 结果:   AAAA AAAA BBBB BBBB (A^C)(A^C) (B^D)(B^D)

    → 低 16 位现在包含了高 16 位的信息
    → 即使 table_size = 16 (只取低 4 位)，这 4 位也受到了全部 32 位的影响

  为什么只做一次 XOR 而不是更复杂的混合？
    - 一次 XOR + 一次移位 = 2 条指令，极快
    - 对于大多数 hashCode() 实现已经足够
    - 更复杂的混合（如 MurmurHash finalize）会更慢

═══════════════════════════════════════════════════════════════
Go map 的方案: 依赖高质量 hash 函数
═══════════════════════════════════════════════════════════════

  Go 不做额外扰动，而是保证 hash 函数本身就够好:
    - 整数: 直接用 AES 指令（硬件加速，天然雪崩效应）
    - 字符串: memhash（基于 AES-NI 或 xxHash 风格）

  AES 指令的雪崩效应:
    改变输入 1 bit → 输出 ~50% bit 翻转
    → 低位已经足够随机，不需要额外扰动

  代价: 依赖 CPU 支持 AES-NI（现代 x86/ARM 都支持）
       不支持时回退到软件 hash（稍慢但仍有好的分布）

═══════════════════════════════════════════════════════════════
Rust HashMap (SwissTable) 的方案: 用高位做索引
═══════════════════════════════════════════════════════════════

  传统方案: 用低位做 slot 索引
  SwissTable: 用 hash >> 7 做 slot 索引，低 7 位做 control byte

  为什么反过来？
    - 低 7 位作为 control byte 存在 metadata 数组中
    - 查找时先用 SIMD 比较 16 个 control byte → 批量过滤
    - 高位做索引 → 即使 hash 函数低位有偏差也不影响 slot 分布

═══════════════════════════════════════════════════════════════
总结: 质数 vs 2的幂的工程权衡
═══════════════════════════════════════════════════════════════

  | 方案 | 速度 | 对 hash 要求 | 适用场景 |
  |------|------|-------------|---------|
  | 质数取模 | 慢(除法) | 低 | hash 函数质量不可控 |
  | 2的幂+扰动 | 快(位运算) | 中 | 有好的扰动函数 |
  | 2的幂+AES hash | 快(位运算) | 低 | 有硬件 AES 支持 |
  | 高位索引(SwissTable) | 快 | 中 | SIMD 优化场景 |

  现代趋势: 用高质量 hash 函数 + 2 的幂 → 兼顾速度和分布
  传统方案: 质数取模 → 简单可靠但慢

3.4 乘法哈希（Fibonacci / Multiplicative Hashing）

// 黄金分割比法
index = (hash(key) * 2654435769ULL) >> (64 - log2(B));
// 2654435769 ≈ 2^32 / φ，φ = (√5+1)/2 ≈ 1.618

原理：乘以无理数 ≈ 把 hash 值打散后再取高位（高位比低位更均匀）。

// 一个更慢但分布更好的变体
index = (hash(key) * 11400714819323198485ULL) >> (64 - log2(B));
// ≈ 2^64 / φ

优点：对 hash 函数质量要求最低（即使 hash 函数很差，分布也不错）。 缺点：乘法 + 位移，比掩码法稍慢；需要 64 位乘法。

使用者：nginx 的 hash 表、部分 Redis 内部场景、Linux 内核的 pid hash。

3.5 Slot 算法选择总结

算法	速度	对 hash 要求	B 限制	使用者
取模法	★★☆	低	质数	C++ unordered_map
位掩码法	★★★	高	2^n	Go, Java, Redis, Rust
乘法哈希	★★☆	最低	2^n	nginx, Linux kernel

---

4. 冲突解决策略

4.1 链地址法（Separate Chaining）

bucket[0] → [k1,v1] → [k2,v2] → [k3,v3]
bucket[1] → [k4,v4]
bucket[2] → NULL

链表过长时的退化

当负载因子高或 hash 碰撞集中，单链表长度达到 O(n) → 查找退化到 O(n)。

Java 8+ 的优化：链表长度 ≥ 8 时转为红黑树。

// HashMap.java
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);  // 链表 → 红黑树
}

为什么是 8？—— 泊松分布的推导：

在负载因子为 0.75 的理想哈希函数下，单个桶中元素数量服从泊松分布：

P(k) = (λ^k / k!) × e^{-λ}
其中 λ = 0.5（负载因子 0.75 下每个桶的平均元素数）

  P(0) = 0.606     → 60.6% 的桶为空
  P(1) = 0.303     → 30.3% 的桶只有 1 个元素
  P(2) = 0.076     → 7.6%
  P(3) = 0.013     → 1.3%
  P(4) = 0.002     → 0.2%
  P(5) = 1.3×10⁻⁴  → 0.013%
  P(6) = 5.4×10⁻⁶  → 0.00054%
  P(7) = 1.9×10⁻⁷  → 0.000019%
  P(8) = 6.0×10⁻⁹  → 0.0000006%  ← 约 1/166,000,000

结论: 正常情况下一个桶出现 ≥8 个元素的概率约为 0.0000006%
      → 如果发生了，几乎不可能是"随机碰撞"的结果
      → 要么是恶意构造的 hash 冲突攻击，要么是 hash 函数设计缺陷
      → 转换为红黑树来防御 O(n) 退化

反树化阈值是 6 而非 8 的原因:
  防止在阈值附近反复树化→反树化（树化和反树化都有开销）
  8→6 的缓冲区避免了阈值附近的抖动

Go 的另一种思路: bucket 内最多存 8 个 kv
  → 超出后挂 overflow bucket
  → 比单链表更少跳转（每步跳过 8 个）
  → 不树化，保持实现简单

链地址法的时间复杂度分析

假设 hash 函数是简单均匀散列（每个 key 独立均匀地散列到 B 个 slot）：

期望链表长度 = α = n / B

查找 成功: Θ(1 + α/2) ≈ Θ(1 + α)   (平均检查一半链表)
查找 失败: Θ(1 + α)                 (遍历整个链表)
插入:     Θ(1 + α)

当 α = O(1) 时，所有操作都是 O(1) 期望。

4.2 开放寻址法（Open Addressing）

所有元素直接存在 table 数组内，碰撞时探测下一个位置。

三种探测序列对比

策略	公式	特点	问题
线性探测	h(k,i) = (h'(k) + i) mod B	缓存最优（连续访问）	一次聚集：连续占用的槽会增长
二次探测	h(k,i) = (h'(k) + c₁i + c₂i²) mod B	减少聚集	二次聚集：同 hash 的探测序列相同
双重哈希	h(k,i) = (h₁(k) + i·h₂(k)) mod B	分布最优	多一次 hash 开销

线性探测的性能公式（Knuth, 1962）

期望探测次数:
  查找成功: ½(1 + 1/(1-α))
  查找失败: ½(1 + 1/(1-α)²)

当 α=0.5: 成功≈1.5, 失败≈2.5
当 α=0.7: 成功≈2.2, 失败≈6.1
当 α=0.9: 成功≈5.5, 失败≈50.5  ← 灾难性退化！

这解释了为什么开放寻址的负载因子通常 ≤ 0.7。

删除问题：Tombstone

// 直接删除会破坏探测链
// 解决：标记为 "tombstone"（逻辑删除）
const (
    EMPTY     = 0
    OCCUPIED  = 1
    TOMBSTONE = 2  // 曾经有元素，现在已删除
)

// 查找时: 跳过 TOMBSTONE，继续探测
// 插入时: 可以重用 TOMBSTONE 的位置
// 但 TOMBSTONE 过多也会影响性能 → 需要定期清理/重建

4.3 Robin Hood Hashing — 优化开放寻址

核心思想：从"富人"（探测距离短）那里抢位置给"穷人"（探测距离远）。

插入 key=k:
  i = h(k)
  dist = 0  // 当前 key 距离理想位置的距离
  while slot is occupied:
    if 当前元素的探测距离 < dist:
        // 把当前元素踢出去，k 占这个位置
        // 被踢出去的元素继续向后找
    i = (i + 1) % B
    dist++

效果：探测距离的方差减小 → 最坏查找接近平均查找 → 性能稳定。

使用者：Rust std::collections::HashMap（SwissTable 的前身库 hashbrown 早期版本用过）、robin_hood::unordered_map（C++ 第三方库）。

4.4 Cuckoo Hashing — 保证 O(1) 最坏

使用两个 hash 函数 h₁ 和 h₂。每个 key 有两个候选位置。

Insert key=k:
  if slot[h₁(k)] is empty → 放入
  else if slot[h₂(k)] is empty → 放入
  else:
    随机踢出 slot[h₁(k)] 的旧元素 old
    把 k 放入 slot[h₁(k)]
    对 old 递归插入（用 old 的另一个 hash 位置）

问题：可能发生循环踢（需要设置最大踢出次数，超出则重建）。

变体 — Cuckoo Filter：用于替代 Bloom Filter，支持删除操作。

4.5 冲突解决对比

维度	链地址法	开放寻址（线性）	Robin Hood	Cuckoo
缓存局部性	差	最优	好	好
内存开销	每节点有指针	无额外开销	需要存探测距离	无
最大负载因子	无上限（但 α>1 性能降）	~0.7	~0.9	~0.5
删除	O(1)	需要 tombstone	tombstone + 后移	O(1) 最坏
查找最坏	O(n)	O(n)	O(n)	O(1)
实现复杂度	低	低	中	高
使用者	Go, Java, Redis	Python	Rust (旧版)	Cuckoo Filter

---

5. 负载因子与扩容机制

5.1 负载因子 α 的深度分析

α = n / B
  n = 元素数量
  B = bucket 数量

α 范围	链地址法表现	开放寻址法表现
< 0.3	浪费内存，但极快	浪费内存，但极快
0.5-0.7	良好	甜区：速度和内存的折中
0.7-1.0	开始退化	显著退化
1.0-3.0	链表变长，可接受	❌ 不可用
3.0-6.5	Go 仍可容忍（桶内 8 对 + overflow）	❌ 不可用
> 6.5	Go 触发翻倍扩容	❌

5.2 各实现的扩容阈值

实现	方法	扩容触发条件	为什么选这个值
Go map	链地址（桶内 8 对）	α > 6.5 或 overflow bucket 过多	桶内 8 对 → 即使 α=6.5 每桶也才约 6.5/8=0.8 个 overflow
Java HashMap	链地址	α > 0.75	默认值，权衡时间和空间
Python dict	开放寻址	α > 2/3 (≈0.667)	开放寻址在 0.67 以上退化明显
Rust HashMap	SwissTable (开放寻址)	α > 7/8 (≈0.875)	SIMD 探测效率高，可承受更高 α
Redis dict	链地址	α > 1 (可配置 dict_force_resize_ratio=5)	默认 1，但 BGSAVE 时提高到 5（避免 COW 内存翻倍）
C++ unordered_map	链地址	α > 1.0	标准要求 max_load_factor() 默认为 1.0

5.3 扩容策略：全量 vs 渐进式

全量扩容（一次性搬迁）

触发扩容 → 分配新数组 → 循环所有旧 bucket → rehash 到新 bucket → 释放旧数组

优点: 实现简单
缺点: 单次操作卡顿（STW），n 越大卡越久（数十毫秒到数秒）

使用者：Java HashMap, Python dict, Rust HashMap, C++ unordered_map。

渐进式扩容（Incremental Rehash）

触发扩容 → 分配新数组 → 设置 rehashidx = 0
每次增删改查时 → 顺便搬迁 1-2 个旧 bucket 到新数组
查找时 → 同时查新旧两处
全部搬完 → 释放旧数组 → rehashidx = -1

使用者：Go map, Redis dict（两个最大的开源渐进式 rehash 实现）。

5.4 渐进式 Rehash 的细节（以 Go map 为例）

// 扩容触发条件 (runtime/map.go)
func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt*(1<<B) && count > 6.5*(1<<B)
    // 即 count > 6.5 * 2^B 且 count > 8 * 2^B
    // 实际: count > 6.5 * 2^B（因为每个 bucket 存 8 个）
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    // noverflow >= 2^B（溢出桶太多，即使 α 不高）
    // 此时做等量扩容（不翻倍），整理碎片
}

搬迁流程（evacuate）

// 每次 mapassign / mapdelete 时检查是否需要搬迁
func (h *hmap) evacuate(oldbucket uintptr) {
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))

    // 对于等量扩容: 新 bucket = 旧 bucket 位置
    // 对于翻倍扩容: 根据 hash 的倒数第 (B+1) 位决定去 x 还是 y
    //   hash & (1 << oldB) == 0 → 去 x (位置不变)
    //   hash & (1 << oldB) != 0 → 去 y (位置 + oldSize)

    // 搬迁 b 中的 8 对 kv 以及所有 overflow bucket
    // ...

    if h.flags&sameSizeGrow == 0 {
        h.nevacuate++  // 一次只搬一个 bucket
    }
}

渐进式 rehash 期间的内存

扩容期间同时存在两个 bucket 数组:
  - oldbuckets (2^B 个)
  - buckets    (2^(B+1) 个)

总内存 = 1.5× 最终大小（搬迁期间）
全部搬完 → 只保留新数组

5.5 Redis 的渐进式 Rehash — 双表法

sequenceDiagram
    participant C as 客户端请求
    participant D as dict (双表)
    participant S as serverCron (定时任务)

    Note over D: 初始状态: ht[0] 使用中, ht[1]=NULL, rehashidx=-1

    C->>D: 插入触发扩容 (α>1)
    D->>D: 分配 ht[1] = new_buckets<br/>rehashidx = 0
    Note over D: 双表共存, rehashidx=0

    rect rgb(240, 248, 255)
        C->>D: 增删改查请求
        D->>D: dictRehash(d, 1) 搬1个bucket<br/>从 ht[0][rehashidx] → ht[1]
        D->>D: rehashidx++
        Note over C: 查找时: 先查 ht[0], 未命中再查 ht[1]
    end

    rect rgb(255, 248, 240)
        S->>D: serverCron 每100ms
        D->>D: dictRehashMilliseconds(1)<br/>持续搬运1ms(即使无请求)
    end

    D->>D: rehash 完成 → ht[1]成为新ht[0]<br/>释放旧ht[0], rehashidx=-1
    Note over D: ✅ 回到单表状态

// dict.h — dict 结构体
typedef struct dict {
    dictType *type;
    dictEntry **ht_table[2];     // 两张 hash 表
    unsigned long ht_used[2];    // 各表的元素数
    long rehashidx;              // rehash 进度: -1=未进行, >=0=进行中
    int16_t pauserehash;         // 暂停 rehash (>0 表示被暂停)
} dict;

// 每次操作时触发 rehash:
int dictRehash(dict *d, int n) {
    int empty_visits = n * 10;  // 最多跳过 n*10 个空桶
    while (n-- && d->ht_used[0] > 0) {
        // 找到下一个非空 bucket
        // 把该 bucket 的所有 entry rehash 到 ht[1]
        // 每搬一个 entry，ht_used[0]--, ht_used[1]++
    }
    // 如果 ht[0] 全部搬完 → ht[1] 变成 ht[0]
}

查找时的双表探测逻辑：

// 在 rehash 期间，查找需要查两张表
dictEntry *dictFind(dict *d, const void *key) {
    // 先查 ht[0]（旧表）
    uint64_t idx = hash(key) & sizemask0;
    entry = d->ht_table[0][idx];
    while (entry) { if (keycmp(entry->key, key) == 0) return entry; ... }

    // 如果没找到且正在 rehash，再查 ht[1]（新表）
    if (dictIsRehashing(d)) {
        idx = hash(key) & sizemask1;
        entry = d->ht_table[1][idx];
        while (entry) { ... }
    }
    return NULL;
}

Redis 的智能之处：

1. 定时 rehash：serverCron 中每 100ms 调用 dictRehashMilliseconds(1) 搬 1ms——即使完全没有请求也在悄悄搬，确保 rehash 最终完成
2. BGSAVE/RDB 时的内存保护：

   BGSAVE 开始时: dict_can_resize = 0
   → 扩容阈值从 α > 1 提高到 α > 5
   → 避免 fork() 后 COW 触发大量内存复制
   
   BGSAVE 结束时: dict_can_resize = 1 → 恢复 α > 1 即可扩容

3. maxmemory 限制：内存接近上限时禁止扩容，甚至缩容来释放内存
4. 删除时缩容（Go map 不支持！）：当 α < 0.1 时触发缩容（htNeedsResize），将 bucket 数减半

5.6 缩容（Shrinking）

大多数 hash 表实现了扩容但不缩容——一旦变大就不再变小（Go map 就是例子）。这导致删除大量元素后内存不释放。

那些支持缩容的：

• Redis dict：当 α < 0.1 时缩容（dictResize）
• Python dict：缩容阈值在 3.10+ 中优化为 used > 50000 && used < capacity/4
• Java HashMap：JDK 未实现自动缩容（需要手动 new HashMap<>(old)）

---

6. 各语言/系统实现

6.1 Go Map — 桶内 8 对 + 渐进式 rehash

// runtime/map.go
type hmap struct {
    count     int    // 当前元素数
    flags     uint8
    B         uint8  // bucket 数量 = 2^B
    noverflow uint16 // 溢出桶的近似数量
    hash0     uint32 // 哈希种子（随机生成 → 防 HashDoS）
    buckets    unsafe.Pointer // []*bmap
    oldbuckets unsafe.Pointer // 扩容时的旧桶
    nevacuate  uintptr        // 搬迁进度
    extra      *mapextra      // 溢出桶缓存
}

type bmap struct {
    tophash [8]uint8    // hash 值的高 8 位（快速过滤 99.6% 不匹配）
    keys    [8]keytype  // key 连续存放
    elems   [8]elemtype // value 连续存放（与 key 分开 → 避免对齐浪费）
    overflow *bmap      // 溢出桶指针
}

查找流程（mapaccess1）：

1. hash = alg.hash(key, h.hash0)
2. bucket = hash & (2^B - 1)
3. top = uint8(hash >> 56)  // 高 8 位
4. 遍历 bucket 的 8 个 tophash:
   a. tophash[i] != top → 跳过（单字节比较，极快）
   b. tophash[i] == top → 比较 key[i]（可能触发间接调用）
   c. 找到 → 返回 value
5. 如果主 bucket 没找到 → 检查 overflow bucket

为什么 "key 和 value 分开存储" 很重要？

紧密打包: [k1,v1,k2,v2,...k8,v8]
  - 不同大小的 key/value 导致对齐浪费
  - 内存访问不连续

分开存储: [k1,k2,...k8][v1,v2,...v8]
  - key 数组和 value 数组各自连续
  - CPU 预取更高效
  - 无对齐浪费

插入流程（mapassign）：

1. hash = alg.hash(key, h.hash0)
2. bucket = hash & (2^B - 1)
3. 检查是否在扩容中 → 如果是，先帮忙搬 1-2 个桶
4. 在 bucket 中找空位或相同 key:
   a. 空位 → 填入
   b. 相同 key → 覆盖
   c. 主桶满了 → 挂 overflow bucket
5. 触发扩容检查：
   a. count > 6.5 * 2^B → 翻倍扩容
   b. overflow 过多 → 等量扩容

删除流程（mapdelete）：只清除 tophash 和 key/value 的零值标记，不真正释放 overflow bucket（等扩容时一起回收）。

6.2 Python Dict — 紧凑 + 保序

Python 3.6+ dict 内部结构（PyDictObject）:

  indices (哈希索引, 稀疏):   entries (紧凑存储):
  [0] → -1                    [0] {hash, key, value}
  [1] →  0 ──────────────→    [1] {hash, key, value}
  [2] → -1                    [2] {hash, key, value}
  [3] →  1 ─────────→        ...
  [4] → -1
  [5] →  2 ───────→

查找: hash → indices[hash&mask] → entries[index] → 比较 key

保序性：entries 数组按插入顺序追加 → 遍历 dict 就是遍历 entries → 自动保持插入顺序。

6.3 Java HashMap — 红黑树兜底

HashMap 结构:
  ┌────────────────────────────┐
  │  Node<K,V>[] table (bucket)│
  │  [0] → Node → Node → ...  │ ← 链表
  │  [1] → TreeNode  (红黑树)  │ ← 长度 ≥ 8 时转红黑树
  │  [2] → null               │
  │  ...                       │
  └────────────────────────────┘

扩容: 默认 α > 0.75 → 翻倍 (newCap = oldCap << 1)
缩容: 不支持（JDK 未实现自动缩容）

6.4 Redis Dict — 双表渐进式 Rehash

// dictEntry 是最小单元，只包含 key/value/next
typedef struct dictEntry {
    void *key;
    union { void *val; uint64_t u64; int64_t s64; } v;
    struct dictEntry *next;  // 链地址法
} dictEntry;

// dict 维护两张表和一个 rehashidx
// ht[0]: 当前使用的表
// ht[1]: 扩容/缩容时的目标表
// rehashidx: -1 = 未进行, >=0 = 正在搬迁第几个 bucket

Redis 的独特设计：

• dict 作为基础组件：Redis 的 Hash、Set（小集合）、ZSet 的 hash 部分、全局 key 空间都是 dict
• 不同类型有不同的 key 比较函数：字符串用 strcmp，SDS 用 sdscmp
• 渐进式 rehash 通过 dictRehashMilliseconds(1) 在 serverCron 中定时执行

---

7. SwissTable — 现代 Hash 表标杆

7.1 核心创新

SwissTable（Google abseil 设计，2017）引入了元数据分离 + SIMD 批量探测：

传统开放寻址:
  检查 slot[0] → 不匹配 → 检查 slot[1] → ...

SwissTable:
  用 16 字节的 AVX2 指令一次检查 16 个 slot！

7.2 结构

┌──────────────┬──────────────────────┐
│  ctrl_byte[] │    slots[]           │
│  (元数据)    │    (实际数据)         │
├──────────────┼──────────────────────┤
│ 0b10000000   │  (空，从未使用)       │ ← 查找终止标记
│ 0b11111110   │  (sentinel, 已删除)   │
│ 0b0HHHHHHH   │  (hash 低 7 位)       │ ← 查找匹配
│ ...          │  ...                  │
└──────────────┴──────────────────────┘

每个 group 16 个 slot，ctrl_byte 数组每 16 字节一组。

查找流程：

// 伪代码
auto ctrl = ctrl_bytes + (hash & mask);  // 从与 hash 匹配的组开始
while (true) {
    // 1. 用 SIMD 指令比较 16 个 ctrl 字节与 hash 的低 7 位
    auto match = _mm_cmpeq_epi8(ctrl_group, hash_low7);
    // 2. 检查是否有哨兵 (sentinel)，如果有则终止
    auto sentinel = _mm_cmpeq_epi8(ctrl_group, EMPTY);
    // 3. 如果匹配且未被哨兵终止 → 在对应位置找 key
    // 4. 如果全部不匹配 → 跳到下一组 (ctrl = ctrl + 16)
}

性能：查找比 std::unordered_map 快 3-5×，内存减少 30-50%。

使用者：

• abseil：absl::flat_hash_map（Google）
• Rust：std::collections::HashMap（使用 hashbrown crate）
• Go：正在实验（Go 1.24+）

---

8. 高级哈希结构

8.1 一致性哈希（Consistent Hashing）

用于分布式缓存与数据分片场景。详细分析（环形原理、虚拟节点数学推导、多方案对比）见 一致性Hash与Raft。

8.2 Hopscotch Hashing

结合链地址和开放寻址。每个 key 的候选位置在其 ideal slot 的 "hop range"（通常是 32 个 slot）内。通过置换把远距离的元素移到近处。

---

9. 并发 Hash 表

9.1 各语言的方案

语言	方案	原理
Go	sync.Map	read map (无锁读) + dirty map (写时锁)
Java	ConcurrentHashMap	分段锁（JDK 7）→ CAS + synchronized（JDK 8）
C++	folly::ConcurrentHashMap	分段 + 乐观锁
Rust	dashmap	分段 RwLock，每段独立锁
Redis	单线程，无需并发	epoll + 事件驱动

9.2 Go sync.Map 详解 — 双 Map 无锁读设计

flowchart TD
    subgraph Read["read map (无锁 atomic.Pointer)"]
        R1["entry: key→atomic.Pointer[any]<br/>完全无锁读取"]
        R2["expunged 标记: key 已从 dirty 移除，仅在 read 中占位"]
    end

    subgraph Dirty["dirty map (mu.Lock 保护)"]
        D1["entry: key→atomic.Pointer[any]<br/>包含所有未被 expunged 的 key"]
        D2["misses 计数器: 记录 read miss 次数"]
    end

    Read <--> Dirty

    Store["Store(key,val)"] --> TryRead{"key 在 read 中<br/>且 p != expunged?"}
    TryRead -->|"是"| CAS_OK["CAS 原子更新 entry.p ✅<br/>（p==nil 也能成功）"]
    TryRead -->|"否"| Lock["加锁 mu.Lock()"]

    Lock --> CheckA{"双检查: key 在 read 中?"}
    CheckA -->|"是, p==expunged"| FixA["CAS p: expunged→nil<br/>在 dirty 中关联该 key<br/>写入新值"]
    CheckA -->|"是, p!=expunged"| FixB["直接 CAS 更新 entry.p"]
    CheckA -->|"否"| CheckDirty{"key 在 dirty 中?"}
    CheckDirty -->|"是"| FixC["直接更新 dirty 中 entry.p"]
    CheckDirty -->|"否"| FixD{"dirty == nil?"}
    FixD -->|"是"| CopyRead["从 read 复制 dirty<br/>（nil→expunged，不复制）<br/>设 amended=true"]
    CopyRead --> AddNew["在 dirty 中新增 key"]
    FixD -->|"否"| AddNew

    CAS_OK --> Done["✅ 无锁完成"]
    FixA --> Done2["✅ 加锁完成"]
    FixB --> Done2
    FixC --> Done2
    AddNew --> Done2

    style Read fill:#4CAF50,color:#fff
    style Dirty fill:#FF9800,color:#fff
    style CAS_OK fill:#4CAF50,color:#fff
    style CopyRead fill:#2196F3,color:#fff

// sync.Map 核心结构
type Map struct {
    mu     sync.Mutex          // 保护 dirty map
    read   atomic.Pointer[readOnly] // 无锁读
    dirty  map[any]*entry      // 需要加锁
    misses int                 // read miss 计数
}

type readOnly struct {
    m       map[any]*entry
    amended bool  // dirty 中包含 read 没有的 key
}

type entry struct {
    p atomic.Pointer[any] // nil=已删, expunged=已从dirty删
}

关键路径：

操作	路径	是否加锁
Load (读命中)	直接查 read map → hit	❌ 无锁
Load (读未命中)	read miss + amended=true → 加锁查 dirty → misses++	✅
Store (已有key, 非expunged)	CAS 更新 read 中 entry.p	❌ 无锁
Store (已有key, expunged)	加锁 → 解除 expunged → 关联到 dirty → 写入	✅
Store (新key, dirty存在)	加锁 → 更新 dirty 中 entry.p	✅
Store (纯新key)	加锁 → 可能从 read 复制 dirty → 新增到 dirty	✅
Delete (read中)	CAS 将 entry.p 设为 nil（惰性删除）	❌ 无锁
Delete (仅dirty中)	加锁 → 从 dirty 中 delete	✅
Range	遍历 read → amended=true 则先提升 dirty 再遍历	可能加锁

dirty 提升为 read 的时机：当 misses >= len(dirty) 时触发，dirty 直接替换 read（read.Store(readOnly{m: dirty})），同时 dirty=nil, misses=0。此时"写多"的 key 进入 read 能享受无锁读。

expunged vs nil 的微妙区别：

• nil：entry 值被删除，但 key 在 read 和 dirty 中都存在（共享同一个 entry 指针）。下次 Store 可直接 CAS 恢复。
• expunged：key 仅存在于 read 中，dirty 中已无此 key。产生时机：从 read 复制 dirty 时，将 read 中 p==nil 的 entry 标记为 expunged 并跳过不复制。下次 Store 该 key 需要加锁重新加入 dirty。

sync.Map 最佳场景：

1. ✅ entry 写一次、读很多次（缓存模式，read 命中率高）
2. ✅ 多个 goroutine 操作不相交的 key 集合
3. ❌ 频繁新增/删除不同的 key（频繁加锁）
4. ❌ 需要 len() / 迭代过程中修改（无此能力）

9.3 Java ConcurrentHashMap 演进

JDK 7 (Segment 分段锁):
  ┌─ Segment[0] (锁A) → HashEntry[] → ...
  ├─ Segment[1] (锁B) → HashEntry[] → ...
  └─ ... (默认 16 个 Segment)

JDK 8+ (CAS + synchronized):
  ┌─ Node<K,V>[0] → CAS 插入
  ├─ Node<K,V>[1] → 红黑树 (synchonized 锁桶首节点)
  └─ ...

  插入: CAS 尝试，失败则 synchonized 锁住桶首节点
  扩容: 多线程协同，每个线程认领一段旧桶搬运

---

10. 各实现对比总览

特性	Go map	Java HashMap	Python dict	Redis dict	Rust HashMap	C++ unordered_map
冲突解决	链地址(桶内8对)	链地址→红黑树	开放寻址	链地址	SwissTable(SIMD)	链地址
slot 选择	掩码法	掩码法	掩码法	掩码法	掩码法	取模法
Hash 函数	AES memhash	h^(h>>>16)	SipHash	SipHash	SipHash-1-3	MurmurHash
扩容阈值	α>6.5	α>0.75	α>0.667	α>1	α>0.875	α>1.0
扩容方式	渐进式	全量	全量	渐进式	全量	全量
缩容	❌	❌	3.10+ 支持	✅ (α<0.1)	❌	❌
保序	❌	❌	✅ (3.7+)	❌	❌	❌
并发安全	❌	❌	❌(GIL)	❌(单线程)	❌	❌
HashDoS 防护	✅ (随机种子)	❌ (可攻击)	✅ (SipHash)	✅ (SipHash)	✅ (SipHash)	❌

---

11. Hash 表与 Cache Line 的关系

11.1 为什么 Hash 表的性能瓶颈常常不在算法，而在访存

Hash 表的理论复杂度是 O(1)，但真实性能取决于每次查找触发多少次 cache miss。

一次 L1 cache hit:  ~1ns
一次 L1 cache miss: ~5ns (L2 hit)
一次 L2 cache miss: ~40ns (L3 hit)
一次 L3 cache miss: ~100ns (主存)

如果一次 hash 查找需要 3 次指针跳转（链地址法）:
  最好: 3 × 1ns = 3ns
  最坏: 3 × 100ns = 300ns
  差 100 倍！

11.2 链地址法 vs 开放寻址在 Cache 上的真实差异

flowchart LR
    subgraph CHAIN["链地址法"]
        B1["bucket 数组"] --> N1["节点1 (堆上)"]
        N1 --> N2["节点2 (堆上)"]
        N2 --> N3["节点3 (堆上)"]
    end
    subgraph OPEN["开放寻址法"]
        S1["slot[0]"] --- S2["slot[1]"] --- S3["slot[2]"] --- S4["slot[3]"]
    end

维度	链地址法	开放寻址法
数据布局	节点分散在堆上	所有数据在连续数组中
一次查找的 cache line 访问	1(bucket) + N(链表节点)	通常 1-2 个 cache line
预取效果	差（指针跳转不可预测）	好（线性探测是连续的）
插入时的分配	每次 malloc 一个节点	无额外分配
删除	简单（摘链表）	需要 tombstone

这就是为什么现代高性能 hash 表几乎都选择开放寻址（SwissTable、Python dict、Robin Hood）。

11.3 Go map 的 tophash 为什么是 8 字节

Go map 的 bucket 结构：

bmap 布局:
  tophash [8]uint8    →  8 字节，恰好 1/8 cache line
  keys    [8]keytype
  values  [8]valtype
  overflow *bmap

查找时先比较 tophash：

1. 计算 hash → 定位 bucket
2. 加载 tophash[0..7]（8 字节，通常在同一 cache line 内）
3. 逐个比较 tophash[i] == top
4. 只有 tophash 匹配时才去比较真正的 key

为什么这样设计？

• 8 个 tophash 只有 8 字节，一次 cache line 加载就全部拿到
• tophash 不匹配的概率 = 255/256 ≈ 99.6%
• 也就是说 99.6% 的不匹配 key 只需要 1 字节比较就能排除
• 避免了加载真正的 key（可能很大）来做比较

11.4 SwissTable 的 SIMD 探测为什么快

SwissTable 的核心创新不只是"一次查 16 个"，而是一次 cache line 加载就够了：

传统开放寻址:
  slot[0] → 比较 key → 不匹配
  slot[1] → 比较 key → 不匹配
  slot[2] → 比较 key → 匹配！
  每次比较可能触发一次 cache miss（如果 key 很大）

SwissTable:
  加载 16 字节 ctrl_bytes（恰好 1/4 cache line）
  用 SIMD 指令一次比较 16 个 ctrl 字节
  只有 ctrl 匹配的位置才去加载真正的 key

SwissTable 查找的 cache line 访问模式:

1. 加载 ctrl_bytes[group]  → 1 次 cache line 访问
2. SIMD 比较 → 得到匹配位掩码
3. 只对匹配位置加载 key   → 通常 0-1 次额外访问
4. 如果 group 内没找到    → 跳到下一个 group（连续内存）

总计: 通常 1-2 次 cache line 访问就能完成查找

与 Go map 的对比：

维度	Go map (tophash)	SwissTable (SIMD)
快速过滤	逐个比较 8 个 tophash	SIMD 一次比较 16 个 ctrl
过滤精度	8 bit → 99.6% 排除	7 bit → 99.2% 排除
硬件依赖	无	需要 SSE2/AVX2/NEON
负载因子上限	6.5	7/8 ≈ 0.875
查找 cache line 数	1-2 (bucket + overflow)	1-2 (ctrl + slot)

11.5 Rehash 抖动与 Cache 的关系

扩容（rehash）不只是"搬数据"，还会导致：

rehash 前:
  热点数据已经在 cache 中
  查找路径已经被 TLB 缓存

rehash 后:
  所有数据搬到新位置
  cache 中的旧数据全部失效
  TLB 中的旧映射也可能失效
  → 扩容后短时间内性能骤降

这就是为什么：

• Redis 用渐进式 rehash（每次只搬 1-2 个 bucket，cache 影响分散）
• Go map 用渐进式 rehash（同理）
• Java/Python/Rust 用全量 rehash（简单但有瞬时抖动）

线上表现：

现象	可能原因
某个接口 RT 突然飙高一次然后恢复	map 扩容触发全量 rehash
持续一段时间 RT 略高	渐进式 rehash 期间双表查找
内存突然翻倍	扩容分配新数组 + 旧数组未释放

11.6 热 Key 与 Cache Line 争用

在并发 hash 表中，如果多个线程频繁访问同一个 bucket：

Thread 1: 读 bucket[42]
Thread 2: 写 bucket[42]
Thread 3: 读 bucket[42]

bucket[42] 所在的 cache line 在多个核心间来回传输
→ MESI 协议的 cache line ping-pong
→ 即使用了 CAS / 细粒度锁，性能也上不去

应对方式：

策略	做法	适用场景
分片	多个独立 map，按 key hash 分片	Go sync.Map 替代方案
读写分离	atomic.Value 存整个 map，写时 copy	配置类、读多写少
per-CPU 计数	每个 P/worker 一个局部 map，定期合并	统计、计数

11.7 一条实战原则

Hash 表的真实性能 = O(1) × cache miss 次数 × cache line 传输成本

选择 hash 表实现时要问：
1. 查找一次需要几次 cache line 访问？
2. 数据是连续存储还是指针跳转？
3. 扩容时是全量还是渐进？对 cache 的冲击有多大？
4. 并发场景下热点 bucket 是否会导致 cache line 争用？

---

参考

• Hello 算法 — 算法基础入门
• CLRS 第 11 章 — 哈希表理论
• Go map 源码
• SwissTable 设计 (abseil)
• Cuckoo Hashing 论文
• Knuth: The Art of Computer Programming, Vol 3 - Sorting and Searching
• Redis dict 实现