SwissTable 哈希表详解：从 Go 1.24 引入说起（更新版） SwissTable 是一种高效的开放地址哈希表设计，最初来自 Google 的 Abseil 库，计划在 Go 语言 1.24 版本中采用相关优化，用于改进内置的 map 类型。它通过分组、指纹匹配和智能探测，显著提升了性能和内存效率。下面是基于我们对话的总结，结构化整理，便于你记录到博客。整个解释用“停车场”比喻来形象化，帮助初学者理解。我已将新问题（关于 H2 的实际位置和 Go 中 SIMD 实现）整合到相应部分，并新增了一个小节详细说明。
什么是哈希表？：像一个快速查找的“字典”，用键（key）找到值（value）。传统开放地址法用线性探测处理碰撞（槽位占用），但容易“簇聚”（clustering），导致速度慢。 SwissTable 的创新：不是一个个槽位处理，而是分成组（通常 8 或 16 个槽一组）。每个组有一个“控制字节数组”（metadata），记录每个槽的指纹（H2）和状态（空、满、已删）。 停车场比喻：整个哈希表像一个大停车场，分成多个”区”（group）。每个区有 8 个车位（槽位）和一个”智能门卫屏”（控制字节），显示每辆车的”指纹”和状态。车（键-值对）用车牌（哈希值）决定停车区。
┌─────────────────────────────────────────────────────────────────────────────┐
│ SwissTable 整体结构（停车场比喻） │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Group 0 │ │ Group 1 │ │ Group 2 │ │ Group 3 │ │ Group 4 │ ... │
│ │ 停车区0 │ │ 停车区1 │ │ 停车区2 │ │ 停车区3 │ │ 停车区4 │ │
│ └────┬────┘ └────┬────┘ └────┬────┘ └────┬────┘ └────┬────┘ │
│ │ │ │ │ │ │
│ ▼ ▼ ▼ ▼ ▼ │
│ ┌──────────────────────────────────────────────────────────────────┐ │
│ │ 智能门卫屏（控制字节 Control Bytes） │ │
│ │ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ │
│ │ │H2/S │H2/S │H2/S │H2/S │H2/S │H2/S │H2/S │H2/S │ (8个字节) │ │
│ │ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ │ │
│ │ 槽0 槽1 槽2 槽3 槽4 槽5 槽6 槽7 │ │
│ └──────────────────────────────────────────────────────────────────┘ │
│ │ │ │ │ │ │
│ ▼ ▼ ▼ ▼ ▼ │
│ ┌──────────────────────────────────────────────────────────────────┐ │
│ │ 键-值数据槽（Key-Value Slots） │ │
│ │ ┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐ │ │
│ │ │ Key/Val │ Key/Val │ Key/Val │ Key/Val │ Key/Val │ Key/Val │ │ │
│ │ └─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘ │ │
│ │ 0 1 2 3 4 5 │ │
│ └──────────────────────────────────────────────────────────────────┘ │
│ │
│ H2/S = H2指纹 + 状态位 (S: 状态 Status) │
└─────────────────────────────────────────────────────────────────────────────┘
传统哈希表 vs SwissTable 对比：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 传统开放地址哈希表 │
├─────────────────────────────────────────────────────────────────────────────┤
│ [槽0] → [槽1] → [槽2] → [槽3] → [槽4] → [槽5] → [槽6] → [槽7] → ... │
│ ↓ │
│ 线性探测：遇到碰撞就逐个检查下一个槽位，容易形成"簇聚" │
│ 例如：槽0,1,2,3 都满，新元素要探测 4 次才能找到槽4 │
└─────────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────────┐
│ SwissTable 分组设计 │
├─────────────────────────────────────────────────────────────────────────────┤
│ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │
│ │Group 0 │ │Group 1 │ │Group 2 │ │Group 3 │ ... │
│ │SIMD检查│ │SIMD检查│ │SIMD检查│ │SIMD检查│ │
│ └────────┘ └────────┘ └────────┘ └────────┘ │
│ 满了→跳过 │
│ 并行匹配：一次检查 8 个槽位，智能跳跃到下一个组 │
│ 优势：SIMD 加速，减少缓存未命中，避免簇聚 │
└─────────────────────────────────────────────────────────────────────────────┘
计算方式： 先用哈希函数（如 SipHash）计算键的 64 位完整哈希值。 H2（指纹）：最低 7 位，公式：H2 = full_hash & 0x7F（取低 7 位，二进制掩码）。 H1（高位）：剩余 57 位，公式：H1 = full_hash » 7（右移 7 位）。
例子：假设键 “example_key” 的哈希是 0xaa433baaa9c7f5dd。 H2：0x5d（二进制 1011101，十进制 93），计算：0xaa433baaa9c7f5dd & 0x7F = 0x5D。 H1：0x154863bd54f7faba，计算：0xaa433baaa9c7f5dd » 7 = 0x154863bd54f7faba。
┌─────────────────────────────────────────────────────────────────────────────┐
│ 64 位哈希值拆分示意图 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 完整哈希值 (64 bits): │
│ 0xaa433baaa9c7f5dd │
│ │
│ 二进制表示： │
│ ┌─────────────────────────────────┬──────────────────┐ │
│ │ H1 (57 bits) │ H2 (7 bits) │ │
│ │ 高位部分 │ 低位部分 │ │
│ └─────────────────────────────────┴──────────────────┘ │
│ │
│ 计算过程： │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 完整哈希: 10101010 01000011 00111011 10101010 10011100 01111111 │ │
│ │ 01011101 11011101 │ │
│ │ │ │
│ │ >> 7: 00010101 01001000 01100011 10111101 01010100 11110111 │ │
│ │ 11111010 11111010 (= H1) │ │
│ │ │ │
│ │ & 0x7F: 01011101 (= H2 = 0x5D) │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ 公式： │
│ H2 = full_hash & 0x7F (取最低 7 位) │
│ H1 = full_hash >> 7 (右移 7 位) │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
H1 和 H2 的职责分工：
┌─────────────────────────────────────────────────────────────────────────────┐
│ │
│ 键 (key) ──► SipHash ──► 64位哈希值 │
│ │ │
│ ├──────► H1 (57位) ──► 决定起始组 │
│ │ └─► 停车区选择 │
│ │ │
│ └──────► H2 (7位) ──► 组内快速匹配 │
│ └─► 门卫屏指纹对比 │
│ │
│ 例子：H1 = 0x154863bd54f7faba，num_groups = 8 │
│ 起始组 = H1 & (8-1) = H1 & 0x7 = 0xa & 0x7 = 2 │
│ 所以从 Group 2 开始查找 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
为什么这样拆分？
┌─────────────────────────────────────────────────────────────────────────────┐
│ 设计优势对比 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ❌ 不使用 H2（传统方法）： │
│ 每次槽位匹配都要比较完整的键 → CPU 开销大 │
│ 例如：查找 "example_key"，每个槽都要字符串比较 │
│ │
│ ✅ 使用 H2（SwissTable 方法）： │
│ 先用 7 位 H2 快速过滤 → 只在 H2 匹配时才比较完整键 │
│ 例如：H2=0x5D，只需检查槽位中 H2 也为 0x5D 的位置 │
│ 拒绝率：254/255 ≈ 99.6% 的碰撞可以快速过滤 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
所有组存储在一个连续大数组中，分两部分： 控制区：连续的控制字节（每个组 8 字节）。 数据区：连续的键-值槽。
┌─────────────────────────────────────────────────────────────────────────────┐
│ SwissTable 内存布局（连续数组） │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 内存地址从低到高： │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 控制区 (Control Bytes) │ │
│ │ ┌───────────────────────────────────────────────────────────────┐ │ │
│ │ │ Group 0 │ Group 1 │ Group 2 │ ... │ │ │
│ │ │ [0][1][2][3] │ [0][1][2][3] │ [0][1][2][3] │ │ │ │
│ │ │ [4][5][6][7] │ [4][5][6][7] │ [4][5][6][7] │ │ │ │
│ │ └───────────────────────────────────────────────────────────────┘ │ │
│ │ 每组 8 字节 每组 8 字节 每组 8 字节 │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 数据区 (Key-Value Slots) │ │
│ │ ┌───────────────────────────────────────────────────────────────┐ │ │
│ │ │ Slot 0 │ Slot 1 │ Slot 2 │ ... │ │ │
│ │ │ ┌─────┬─────┐ │ ┌─────┬─────┐ │ ┌─────┬─────┐ │ │ │ │
│ │ │ │ Key │ Val │ │ │ Key │ Val │ │ │ Key │ Val │ │ │ │ │
│ │ │ └─────┴─────┘ │ └─────┴─────┘ │ └─────┴─────┘ │ │ │ │
│ │ └───────────────────────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ 索引映射关系： │
│ 控制字节索引 i ←→ 数据槽索引 i │
│ │
│ 例子：Group 0, Slot 3 │
│ 控制区：control_bytes[0*8 + 3] → 该槽的控制字节 │
│ 数据区：slots[0*8 + 3] → 该槽的键值对 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
缓存友好性示意：
┌─────────────────────────────────────────────────────────────────────────────┐
│ CPU 缓存行 (Cache Line) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 典型缓存行大小：64 字节 │
│ SwissTable 的控制区每组 8 字节 → 一次加载 8 个组的元数据 │
│ │
│ ┌────────────────────────────────────────────────────────────────────┐ │
│ │ CPU Cache Line (64 bytes) │ │
│ │ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ │
│ │ │Group 0 │ │Group 1 │ │Group 2 │ │Group 3 │ │Group 4 │ │Group 5 │ │ │
│ │ │ 8B │ │ 8B │ │ 8B │ │ 8B │ │ 8B │ │ 8B │ │ │
│ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ │ │
│ └────────────────────────────────────────────────────────────────────┘ │
│ │
│ 优势：检查组 0-5 时，只需要 1 次内存加载 → 缓存命中率高 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
优势：访问快（用索引直接跳），缓存友好（数据局部性好）。扩容时复制到新数组，但保持连续。
插入过程（停车）：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 插入操作流程图 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 输入：键 "apple"，值 10 │
│ │
│ ┌──────────────┐ │
│ │ 1. 计算哈希值 │ SipHash("apple") = 0xaa433baaa9c7f5dd │
│ └──────┬───────┘ │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ 2. 拆分 H1/H2 │ H1 = 0x154863bd54f7faba, H2 = 0x5D │
│ └──────┬───────┘ │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ 3. 定位起始组 │ start_group = H1 % 8 = 2 → Group 2 │
│ └──────┬───────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ 4. 检查 Group 2 的控制字节 │ │
│ │ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ │
│ │ │0x3A │0x7C │0x80 │0x5D │0x1B │FULL │FULL │FULL │ │ │
│ │ │满 │满 │空 │满 │满 │满 │满 │满 │ │ │
│ │ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ │ │
│ │ │ │
│ │ SIMD并行比较：一次检查所有 8 个槽位，找到空位（0x80） │ │
│ └───────────────────────────┬──────────────────────────────┘ │
│ │ 找到空位（Slot 2） │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ 5. 写入数据 │ │
│ │ 控制字节[2] = 0x5D (设置 H2，bit 7=0 表示占用) │ │
│ │ slots[2].key = "apple" │ │
│ │ slots[2].value = 10 │ │
│ └──────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ 6. 完成 ✓ │ │
│ └──────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
查找过程（找车）：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 查找操作流程图 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 输入：查找键 "apple" │
│ │
│ ┌──────────────┐ │
│ │ 1. 计算哈希值 │ 同上，H1 → Group 2, H2 = 0x5D │
│ └──────┬───────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ 2. 检查 Group 2，匹配 H2=0x5D │ │
│ │ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ │
│ │ │0x3A │0x7C │0x5D │0x5D │0x1B │FULL │FULL │FULL │ │ │
│ │ │ ✗ │ ✗ │ ✓ │ ✓ │ ✗ │ │ │ │ │ │
│ │ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ │ │
│ │ Slot 0 Slot 1 Slot 2 Slot 3 Slot 4 │ │
│ └───────────────────────────┬──────────────────────────────┘ │
│ │ 找到 2 个匹配（Slot 2 和 3） │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ 3. 逐一验证完整键 │ │
│ │ Slot 2: slots[2].key == "apple"? ✓ 匹配！ │ │
│ │ 返回 slots[2].value = 10 │ │
│ └──────────────────────────────────────────────────────────────┘ │
│ │
│ 如果 Slot 2 不匹配，继续检查 Slot 3... │
│ 如果整个组都不匹配，按探测序列继续检查下一个组 │
│ 遇到空槽（0x80）表示不存在，停止查找 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
插入和查找的路径一致性：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 路径一致性保证 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 插入路径：Group 2 → Group 4 → Group 7 → ... │
│ 查找路径：Group 2 → Group 4 → Group 7 → ... (相同！) │
│ │
│ 为什么重要？ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ ✓ 确保查找一定能找到插入的元素 │ │
│ │ ✓ 避免重复插入相同的键 │ │
│ │ ✓ 探测序列由三角数决定，确定且可复现 │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
序列例子：0, 1, 3, 6, 10…（公式：i(i+1)/2，其中 i 是探测步数，从 0 递增，与 H1 无关）。 计算实现：用累加避免乘除：offset = 0, delta = 1；每次 offset += delta, delta += 1。这对 CPU 友好，只用加法。
┌─────────────────────────────────────────────────────────────────────────────┐
│ 三角数序列 (Triangular Number) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 序列生成： │
│ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │
│ │ i │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ... │
│ ├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤ │
│ │T(i) │ 0 │ 1 │ 3 │ 6 │ 10 │ 15 │ 21 │ 28 │ │
│ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ │
│ │
│ 公式：T(i) = i(i+1)/2 │
│ 差分：1, 2, 3, 4, 5, 6, 7, ... (每次增加的值递增) │
│ │
│ 计算示例： │
│ i=0: 0×1/2 = 0 │
│ i=1: 1×2/2 = 1 │
│ i=2: 2×3/2 = 3 │
│ i=3: 3×4/2 = 6 │
│ i=4: 4×5/2 = 10 │
│ │
│ 无乘除实现（CPU 友好）： │
│ offset = 0, delta = 1 │
│ loop: │
│ use offset │
│ offset += delta # 累加 │
│ delta += 1 # 步长递增 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
探测序列对比：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 线性探测 vs 二次探测（三角数） │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 线性探测 (Linear Probing): │
│ ┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐ │
│ │ Step 0│ Step 1│ Step 2│ Step 3│ Step 4│ Step 5│ Step 6│ Step 7│ │
│ │ +0 │ +1 │ +2 │ +3 │ +4 │ +5 │ +6 │ +7 │ │
│ └───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘ │
│ Group 0→Group 1→Group 2→Group 3→Group 4→Group 5→Group 6→Group 7 │
│ │ │
│ └─► 容易形成"簇聚"（clustering）：连续满槽会阻塞后续访问 │
│ │
│ 二次探测 (Quadratic Probing - 三角数): │
│ ┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐ │
│ │ Step 0│ Step 1│ Step 2│ Step 3│ Step 4│ Step 5│ Step 6│ Step 7│ │
│ │ +0 │ +1 │ +3 │ +6 │ +10 │ +15 │ +21 │ +28 │ │
│ └───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘ │
│ Group 0→Group 1→Group 3→Group 6→Group 10→Group 15→Group 21→... │
│ │ │
│ └─► 跳跃越来越大，避免簇聚，分布更均匀 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
探测序列与 H1 的结合：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 实际访问的组索引计算 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 公式：target_group = (H1 + triangular_number(i)) % num_groups │
│ │
│ 例子：H1 = 10, num_groups = 16 │
│ │
│ ┌─────┬─────────────┬──────────┬─────────────────────────────────────┐ │
│ │ i │ triangular(i) │ H1 + T(i) │ target_group % 16 │ │
│ ├─────┼─────────────┼──────────┼─────────────────────────────────────┤ │
│ │ 0 │ 0 │ 10 │ 10 → Group 10 │ │
│ │ 1 │ 1 │ 11 │ 11 → Group 11 │ │
│ │ 2 │ 3 │ 13 │ 13 → Group 13 │ │
│ │ 3 │ 6 │ 16 │ 0 → Group 0 (循环回到开头) │ │
│ │ 4 │ 10 │ 20 │ 4 → Group 4 │ │
│ │ 5 │ 15 │ 25 │ 9 → Group 9 │ │
│ │ 6 │ 21 │ 31 │ 15 → Group 15 │ │
│ └─────┴─────────────┴──────────┴─────────────────────────────────────┘ │
│ │
│ 访问序列：Group 10 → 11 → 13 → 0 → 4 → 9 → 15 → ... │
│ │
│ 可视化（假设 16 个组）： │
│ ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐│
│ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │10 │11 │12 │13 │14 │15 ││
│ │ │ │ │ │ │ │ │ │ │ │ ⭐ │ ⭐ │ │ ⭐ │ │ ││
│ │ ⭐ │ │ │ │ ⭐ │ │ │ │ │ ⭐ │ │ │ │ │ ⭐ │ ││
│ └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘│
│ 步骤3 步骤4 步骤5 步骤0 步骤1 步骤2 步骤6 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
原因：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 为什么选择三角数探测？ │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ✓ 避免簇聚：不像线性探测（+1, +2...）容易堵塞一条路，二次跳跃越来越大， │
│ 分布更均匀 │
│ │
│ ✓ 均匀覆盖：在表大小为 2 的幂时，能摸遍所有槽，不遗漏 │
│ │
│ ✓ 高负载高效：表填 90% 满时，平均探测 1-2 次 │
│ │
│ ✓ CPU 友好：只需加法，无需乘除运算 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
如果起始组满：停车时跳序列（组3 → 组4 → 组6…），找车时也从组3 开始跳相同序列。
探测序列与 H1 的结合：实际访问的组索引 = (H1 + triangular_number(i)) % num_groups，其中 i 是探测步数（从 0 开始）。例如：H1 = 10，num_groups = 16，则访问序列为组 10 → 组 11 → 组 13 → 组 16 → …（超过 16 时循环回到开头）。
H2 的存储：H2 存入控制字节（每个槽一个字节）：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 控制字节位结构 (Control Byte) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 每个槽的控制字节（8 bits = 1 byte）： │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Bit 7 │ Bit 6 │ Bit 5 │ Bit 4 │ Bit 3 │ Bit 2 │ Bit 1 │ Bit 0 │ │
│ │ ────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼────────│ │
│ │ 状态位 │ │ H2 指纹值（7 bits） │ │ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ 状态位（Bit 7）： │
│ 0 = 槽位被占用（occupied），低 7 位的 H2 有效 │
│ 1 = 槽位空闲或已删除（empty/deleted） │
│ │
│ 示例值： │
│ ┌─────────┬────────────┬──────────────────────────────────┬──────────────┐ │
│ │ 值 │ 二进制 │ 含义 │ 十六进制 │ │
│ ├─────────┼────────────┼──────────────────────────────────┼──────────────┤ │
│ │ 128 │ 10000000 │ 空槽（bit 7=1） │ 0x80 │ │
│ │ 0 │ 00000000 │ 已删除（墓碑标记） │ 0x00 │ │
│ │ 93 │ 01011101 │ 已占用，H2=0x5D (bit 7=0) │ 0x5D │ │
│ │ 45 │ 00101101 │ 已占用，H2=0x2D (bit 7=0) │ 0x2D │ │
│ └─────────┴────────────┴──────────────────────────────────┴──────────────┘ │
│ │
│ 检查状态： │
│ if (control_byte & 0x80) → 空或删除（bit 7=1） │
│ if (!(control_byte & 0x80)) → 已占用（bit 7=0） │
│ │
│ 提取 H2： │
│ H2 = control_byte & 0x7F （屏蔽最高位） │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
一个组的完整控制字节示例：
┌─────────────────────────────────────────────────────────────────────────────┐
│ 一个组的 8 个控制字节（64 bits） │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Slot: 0 1 2 3 4 5 6 7 │
│ ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐ │
│ │0x3A │0x7C │0x80 │0x5D │0x1B │FULL │FULL │FULL │ │
│ └──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘ │
│ 满 满 空 满 满 满 满 满 │
│ │
│ 二进制表示： │
│ ┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ │00111010 │01111100 │10000000 │01011101 │00011011 │xxxxxxxx │xxxxxxxx │xxxxxxxx │
│ └──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
│ H2=0x3A H2=0x3C 空槽 H2=0x5D H2=0x1B (已占用) (已占用) (已占用) │
│ bit7=0 bit7=0 bit7=1 bit7=0 bit7=0 │
│ │
│ 作为 64 位整数（小端序，低地址在前）： │
│ 0xXXXXXXXXXXXXXXXX1B5D807C3A │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
常见控制字节值：
Go 中的 SIMD 实现：Go 语言无内置 SIMD 支持，但标准库（runtime）用架构特定汇编（.s 文件）集成 CPU 指令（如 amd64 的 SSE2）。
┌─────────────────────────────────────────────────────────────────────────────┐
│ SIMD 并行匹配 H2 过程 │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 目标：查找 H2 = 0x5D 的槽位 │
│ │
│ 步骤 1：构建测试字（广播 H2） │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ SIMD 寄存器 (128 bits) │ │
│ │ ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐│
│ │ │5D │5D │5D │5D │5D │5D │5D │5D │5D │5D │5D │5D │5D │5D │5D │5D ││
│ │ └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘│
│ │ 每个 16 位字都包含重复的 0x5D │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ 步骤 2：加载控制字（64 bits，取低 8 字节） │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 控制字节（从内存加载） │ │
│ │ ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ │
│ │ │3A │7C │80 │5D │1B │XX │XX │XX │ │ │
│ │ └────┴────┴────┴────┴────┴────┴────┴────┘ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ 步骤 3：并行比较（SSE2 pcmpeqb 指令） │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ 测试字 控制字节 比较结果（匹配=FF，不匹配=00） │ │
│ │ ┌────┐ ┌────┐ ┌────┐ │ │
│ │ │ 5D │ cmp │ 3A │ =→ │ 00 │ ✗ 不匹配 │ │
│ │ ├────┤ ├────┤ ├────┤ │ │
│ │ │ 5D │ cmp │ 7C │ =→ │ 00 │ ✗ 不匹配 │ │
│ │ ├────┤ ├────┤ ├────┤ │ │
│ │ │ 5D │ cmp │ 80 │ =→ │ 00 │ ✗ 不匹配（空槽） │ │
│ │ ├────┤ ├────┤ ├────┤ │ │
│ │ │ 5D │ cmp │ 5D │ =→ │ FF │ ✓ 匹配！ │ │
│ │ ├────┤ ├────┤ ├────┤ │ │
│ │ │ 5D │ cmp │ 1B │ =→ │ 00 │ ✗ 不匹配 │ │
│ │ ├────┤ ├────┤ ├────┤ │ │
│ │ │ 5D │ cmp │ XX │ =→ │ 00 │ ✗ 不匹配 │ │
│ │ ├────┤ ├────┤ ├────┤ │ │
│ │ │ 5D │ cmp │ XX │ =→ │ 00 │ ✗ 不匹配 │ │
│ │ ├────┤ ├────┤ ├────┤ │ │
│ │ │ 5D │ cmp │ XX │ =→ │ 00 │ ✗ 不匹配 │ │
│ │ └────┘ └────┘ └────┘ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ 步骤 4：压缩掩码（pmovmskb） │
│ 结果 = 0b00001000 = 0x08 │
│ 第 3 位为 1 → Slot 3 匹配！ │
│ │
│ 性能： │
│ 无 SIMD：需要 8 次比较指令 │
│ 有 SIMD：1 次 SIMD 指令 + 1 次掩码提取 = 1-2 CPU 周期 │
│ 加速比：约 4-8 倍 │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
过程： 构建 64 位测试字：每个字节重复 H2（SIMD 用 _mm_set1_epi8 广播；fallback 用位移/乘法）。 加载控制字（64 位）。 并行比较：SIMD 用 pcmpeqb 字节级比较，生成掩码（匹配槽位=0xFF）；fallback 用位技巧（如 XOR + 溢出掩码）。 压缩掩码（pmovmskb）成 8 位整数，表示匹配/空位。
检查满/空：类似，用空标记（如 0x80）重复测试字，掩码找出可写入位（最高位=1 的字节）。 fallback：无 SIMD 时，用纯位运算模拟，确保跨平台。 优势：SIMD 让一组检查只需 1-2 周期，提升 60% 性能。Go 的相关实现（如 map_swiss.go 或 runtime 中的汇编代码）中可见此优化。
更快：SIMD 加速组内匹配，探测少，微基准快 60%，实际应用 CPU 省 1.5%。 内存高效：高负载因子（90% 满），少空槽。 Go 特定适应： 分成多个小 SwissTable，避免大表全复制（只翻倍溢出部分）。 支持迭代时修改（旧表固定顺序，新表查值）。
潜在缺点：实现复杂，低负载稍慢，额外元数据用 1/8 内存。