哈希表是工程里最常用、也最容易被"用错"的数据结构。当数据规模从万级膨胀到亿级，链式哈希的指针追逐会拖垮缓存命中率，而朴素开放寻址又在高装载率下探测退化。Google 的 Swiss Table（absl::flat_hash_map）用一套"元数据与数据分离 + SIMD 分组探测 + 7-bit 指纹"的设计，在 87.5% 装载率下仍保持接近哈希计算本身的吞吐。本文从工程实现角度，逐层拆解它的内部机制，并给出一个可运行的 Python 教学版实现。
一、为什么链式哈希在大数组上变慢
经典哈希表有两种路线：链地址法（separate chaining）把冲突元素挂成链表；开放寻址（open addressing）把元素直接塞进同一个数组，靠探测解决冲突。链式哈希在小数据量下实现简单，但在现代 CPU 架构上有两个致命问题：
- 指针追逐（pointer chasing）：每个桶是一个独立堆分配的对象，查找要沿着指针跳来跳去，几乎每次跳跃都是一次 L1/L2 cache miss。
- 内存碎片化：海量小节点带来分配器压力与缓存行浪费，一个 64 字节的缓存行可能只装下 1~2 个有效节点。
开放寻址把 key/value 紧凑地放在一块连续数组里，对缓存友好得多。但它的老毛病是：一旦装载率升高，探测序列变长，最坏情况退化为 O(n)。Swiss Table 的核心贡献，就是让开放寻址在高装载率下依然保持"短而规整"的探测。
二、核心抽象：slot 与 ctrl 元数据分离
Swiss Table 把一张表拆成两个并行数组：
| 数组 | 类型 | 作用 |
|---|---|---|
| slots | key/value 连续数组 | 真正存放数据，按槽位对齐 |
| ctrl | 每槽 1 字节元数据 | 标记空/墓碑/占用，并缓存 7-bit 指纹 |
ctrl 字节只有三种有意义的状态（其余 0..127 表示占用并携带指纹）：
0xFF= EMPTY（空槽，探测遇它即终止）0x80= DELETED（墓碑，表示该位置曾被占用、现已删除）0x00 ~ 0x7F= FULL（占用，字节本身即 7-bit 指纹 H2）
把"是否占用"与"指纹"压缩进 1 个字节，是后续能用一条 SIMD 指令同时扫描 16 个槽的前提。
三、哈希拆分：H1 定位分组，H2 做指纹校验
Swiss Table 把一个高质量哈希值切成两段：
- H1：高位 bit，用于决定"起始分组（group）"的索引。
- H2：低 7 bit（
hash & 0x7F），作为该 key 的短指纹，直接写进 ctrl 字节。
为什么只存 7-bit 指纹而不是完整哈希？因为 7-bit 正好塞进 1 个 ctrl 字节，且足够用它做一次廉价初筛：SIMD 先比指纹，只有指纹命中才进一步做完整 key 比较。误判（不同 key 的 7-bit 指纹相同）会被真正的 key 比较兜底，不影响正确性，只偶尔多比一次。
四、分组探测：一条 SIMD 指令扫 16 个槽
表按"分组（group）"组织，每组 16 个槽，ctrl 数组按分组对齐。查找时：
- 用 H1 定位起始分组；
- 用一条
_mm_cmpeq_epi8（SSE2，一次比较 16 字节）把本组 16 个 ctrl 字节与 H2 做相等比较，得到 16 个槽里哪些"指纹匹配"； - 对指纹匹配的候选槽再做完整 key 比较，命中即返回；
- 若本组无空槽且未命中，则跳到下一个分组继续（探测步长采用类二次/双哈希策略，绕过已删除的墓碑）。
把 16 个槽打包成一组用 SIMD 一次性比对，是 Swiss Table 性能的关键：绝大多数查找在第一个分组内就结束，且 16 次比较只消耗 1 条向量指令的延迟。
五、插入、查找、删除的精确流程
查找
沿 H1 确定的探测序列逐组扫描：对本组 16 个 ctrl 做 SIMD 指纹匹配；命中指纹的槽逐一比较 key；遇到 EMPTY 立即终止（说明 key 不存在）；遇到 DELETED 继续（墓碑不应中断探测）。
插入
先在探测序列上找是否已存在相同 key（命中则覆盖）；否则找序列上第一个 EMPTY 或 DELETED 槽写入，把 H2 写进 ctrl、key/value 写进 slot。注意：墓碑槽（DELETED）可以被复用，从而在不破坏探测链的前提下回收空间。
删除
找到目标后，把 ctrl 置为 DELETED（墓碑），而不是 EMPTY。这是关键设计：若置为 EMPTY，会切断排在它后面的 key 的探测链，导致这些 key 再也查不到。墓碑保留了"这里曾经有东西"的信号，让后续探测能越过它继续前进。
六、装载率与扩容：为什么能撑到 87.5%
传统开放寻址常在 50%~70% 装载率就要扩容，否则探测长度爆炸。Swiss Table 把"扩容阈值"设得很高（实际在约 7/8 = 87.5% 的 occupied 比例时扩容），原因有三：
- 分组内 16 槽同时比对，单组不满时探测几乎不跨组；
- 7-bit 指纹大幅降低"误以为命中而进入慢速 key 比较"的概率；
- 墓碑机制让删除不破坏探测链，装载率可以堆得更高而不退化。
扩容时容量翻倍并 rehash 所有 FULL 槽（墓碑不参与 rehash，自然消失），平均摊还成本依然很低。
七、与工业实现的对比
| 实现 | 探测方式 | 缓存友好 | 典型装载率 | 亮点 |
|---|---|---|---|---|
| std::unordered_map | 单向链表 | 差（指针追逐） | 约 50% 后劣化 | 标准库、零依赖 |
| absl::flat_hash_map | Swiss Table + SIMD | 优 | 约 87.5% | 元数据/数据分离、分组探测 |
| folly::F14 | 混合（chunked） | 优 | 高 | 小表 inline、大表分块 |
| Rust hashbrown | Swiss Table 变体 | 优 | 约 85% | 无 unsafe 风险、Group 抽象跨架构 |
八、用 Python 复刻一个教学版 Swiss Table
下面是一份忠实于上述思想的 Python 实现（为可读性用线性扫描代替 SIMD，用墓碑代替 backshift 删除；生产实现请直接用 absl / hashbrown）。
EMPTY = 255 # ctrl = 0xFF 表示空槽
DELETED = 128 # ctrl = 0x80 表示墓碑（已删除）
GROUP = 16 # 一个分组 16 个槽
def hash_key(key):
# 仅用于演示：取内置 hash 的 64-bit 非负值
return hash(key) & 0xFFFFFFFFFFFFFFFF
class MiniSwiss:
def __init__(self, cap=32):
self.cap = cap # 容量，2 的幂且 >= GROUP
self.ctrl = [EMPTY] * cap # 元数据字节数组
self.slots = [None] * cap # 真正的 key/value 槽
self.count = 0 # 存活（FULL）元素数
self.occupied = 0 # FULL + 墓碑，用于触发扩容
self.resizes = 0
def _h1(self, h):
# H1 决定起始分组：取哈希高 bit，再对分组数取模
groups = self.cap // GROUP
return (h >> 7) % groups
def _h2(self, h):
# H2 是 7-bit 指纹，存入 ctrl 字节
return h & 0x7F
def _find(self, key, h):
h2 = self._h2(h)
g = self._h1(h)
groups = self.cap // GROUP
for step in range(groups):
gi = (g + step) % groups
base = gi * GROUP
for i in range(GROUP):
idx = base + i
c = self.ctrl[idx]
if c == EMPTY:
return (idx, False, "empty") # 遇到空槽，探测终止
if c == h2 and self.slots[idx][0] == key:
return (idx, True, "found")
# 本分组无空槽也无命中，跳到下一分组继续
return (None, False, "full")
def get(self, key, h=None):
if h is None:
h = hash_key(key)
idx, ok, _ = self._find(key, h)
if ok:
return self.slots[idx][1]
raise KeyError(key)
def put(self, key, value, h=None):
if h is None:
h = hash_key(key)
idx, ok, _ = self._find(key, h)
if ok:
self.slots[idx] = (key, value) # 已存在则覆盖
return
h2 = self._h2(h)
g = self._h1(h)
groups = self.cap // GROUP
target = None
for step in range(groups): # 沿探测序列找首个 EMPTY/DELETED
gi = (g + step) % groups
base = gi * GROUP
for i in range(GROUP):
idx = base + i
c = self.ctrl[idx]
if c == EMPTY or c == DELETED:
target = idx
break
if target is not None:
break
if target is None:
self._grow()
return self.put(key, value, h)
if self.ctrl[target] == EMPTY:
self.count += 1
self.occupied += 1
else: # 复用了墓碑槽
self.count += 1
self.slots[target] = (key, value)
self.ctrl[target] = h2
if self.occupied > self.cap * 7 // 8: # 超过 87.5% 装载率则扩容
self._grow()
def delete(self, key, h=None):
if h is None:
h = hash_key(key)
idx, ok, _ = self._find(key, h)
if not ok:
raise KeyError(key)
self.ctrl[idx] = DELETED # 置墓碑，不置 EMPTY
self.slots[idx] = None
self.count -= 1 # occupied 不变
def _grow(self):
old_slots, old_ctrl, old_cap = self.slots, self.ctrl, self.cap
self.cap *= 2
self.ctrl = [EMPTY] * self.cap
self.slots = [None] * self.cap
self.count = 0
self.occupied = 0
self.resizes += 1
for idx in range(old_cap):
c = old_ctrl[idx]
if c != EMPTY and c != DELETED and old_slots[idx] is not None:
k, v = old_slots[idx]
self.put(k, v, hash_key(k))探测长度统计
下面这个函数复现了"平均/最大探测分组数"的统计思路（真实实现由 SIMD 一次扫 16 槽，这里用线性循环等价表达），用来直观感受高装载率下探测为何仍能收敛。
def probe_stats(table, keys):
# 统计平均/最大探测分组数（仅演示，真实实现由 SIMD 一次扫 16 槽）
maxd = 0
total = 0
for k in keys:
h = hash_key(k)
g = table._h1(h)
groups = table.cap // GROUP
d = 0
for step in range(groups):
gi = (g + step) % groups
base = gi * GROUP
hit = False
for i in range(GROUP):
idx = base + i
c = table.ctrl[idx]
if c == EMPTY:
hit = True
break
if c == (h & 0x7F) and table.slots[idx] and table.slots[idx][0] == k:
hit = True
break
if hit:
d = step + 1
break
maxd = max(maxd, d)
total += d
return total / len(keys), maxd九、性能实测与工程建议
在装载率逐步升高的压测中，Swiss Table 的探测长度呈现典型特征：
| 装载率 | 平均探测分组数 | 最大探测分组数 | 说明 |
|---|---|---|---|
| 50% | 约 1.0 | 约 1~2 | 几乎总在第一组命中 |
| 75% | 约 1.1 | 约 2~3 | SIMD 分组仍高效 |
| 87.5% | 约 1.3 | 约 3~5 | 扩容阈值附近，仍可控 |
| 95%（不推荐） | 快速上升 | 可能 > 10 | 应在此之前扩容 |
工程上的取舍建议：
- 当 key 较小、查找密集、对延迟敏感（如索引、缓存、计数器）时，优先选 Swiss Table 系实现（absl::flat_hash_map / Rust HashMap 默认即 hashbrown）。
- 若 key 极大或需要稳定迭代顺序，链式或
std::map（红黑树）仍有其位置。 - 删除频繁的场景，关注墓碑累积；生产实现多用 backshift 删除把墓碑往前压实，避免长时间运行后 occupied 虚高触发不必要扩容。
十、结语
Swiss Table 的优雅在于"用一点元数据换大量性能"：1 字节的 ctrl 让 SIMD 得以一次扫 16 槽，7-bit 指纹把昂贵的 key 比较挡在门外，墓碑与高装载率扩容策略让连续内存的开放寻址重新变得高效。理解它，不只是为了用一个库，更是为了在面对"高吞吐 + 大内存 + 低延迟"的存储与索引场景时，知道缓存与向量化是如何被一点点榨出来的。
发表评论 取消回复