Go 底层原理 · 第 8 篇
Go 底层原理丨map（Swiss Table 版本）
本文系统解析 Go map（Swiss Table 版本）的底层实现，涵盖控制字并行匹配、开放寻址探测、可扩展哈希、细粒度并发控制，并对比 sync.Map 的 HashTrieMap 实现。
特此声明，本篇是笔者与 Google Gemini 3Pro 共创所作，非常庆幸在当今 AI 时代下获取知识已是如此便利，且也为学习者从第一性原理理解所学知识大大降低了门槛。不过本篇的篇章安排和叙述逻辑，均由笔者把控和审阅，欢迎放心阅读。
1. 整体设计思想
Go map（Swiss Table 版本）是基于 Google Abseil 的 "Swiss Table" 设计的现代化哈希表实现，采用以下核心设计：
- 控制字并行匹配：使用 8 字节控制字一次性检查 8 个槽位
- 开放寻址 + 二次探测：无需链表，所有数据存储在连续数组中
- 可扩展哈希：使用目录机制实现增量扩容，单表大小受限
- SIMD 加速：AMD64 架构使用 SIMD 指令并行比较控制字
设计灵感来源：Abseil Swiss Tables
2. 核心数据结构
本篇以 Go1.25 版本的源码为基准，完整源码参考：
- Runtime 封装：map_swiss.go
- 核心实现：internal/runtime/maps/
2.1 Map（顶层结构）
type Map struct {
// 元素总数（必须在第一位，供 len() 使用）
used uint64
// 哈希种子（每个 map 独立随机）
seed uintptr
// 目录指针：指向 table 数组或单个 group
// 小 map 优化：≤8 个元素时，dirPtr 直接指向单个 group
// 大 map：dirPtr 指向 *[dirLen]*table
dirPtr unsafe.Pointer
dirLen int // 目录长度 = 1 << globalDepth
// 可扩展哈希的全局深度（使用哈希高位的 bit 数）
globalDepth uint8
globalShift uint8 // 64 - globalDepth（用于快速计算索引）
// 并发写检测标志
writing uint8
// 墓碑存在标记
tombstonePossible bool
// 清空序列号（用于检测迭代中的 clear）
clearSeq uint64
}
关键字段说明：
dirPtr+dirLen：实现可扩展哈希的目录结构globalDepth：当前使用哈希高位的 bit 数- 小 map 优化：≤8 个元素时无需分配 table
2.2 Table（哈希表）
type table struct {
used uint16 // 已使用槽位数
capacity uint16 // 总槽位数（= groups数 × 8）
growthLeft uint16 // 剩余可填充槽位
localDepth uint8 // 表的局部深度
index int // 在目录中的索引
groups groupsReference // group 数组
}
单表最大容量：1024 个槽位（限制单次扩容开销）
2.3 Group（组结构）
每个 group 包含：
- 1 个控制字（8 字节）：每字节对应一个槽位的状态
- 8 个槽位：每个槽位存储一个 key-value 对
type groupReference struct {
data unsafe.Pointer // 指向实际的 group 内存
}
// 内存布局
type group struct {
ctrls ctrlGroup // 8 字节控制字
slots [8]struct {
key K
elem V
}
}
控制字编码：
empty: 1000 0000 (0x80)
deleted: 1111 1110 (0xFE) - 墓碑标记
full: 0xxx xxxx (0x00-0x7F) - 低 7 位存储 H2 哈希值
2.4 总结图
3. 核心算法
3.1 哈希值分割
64 位哈希值分为两部分：
┌─────────────────────────────────────────────┬───────────┐
│ H1 (高 57 位) │ H2 (低7位) │
└─────────────────────────────────────────────┴───────────┘
用于定位 group 存储在控制字中
H1：用于定位 group（二次探测）
H2：存储在控制字中，用于快速过滤
3.2 并行匹配算法
传统方式（non-Swiss）：
for i := 0; i < 8; i++ {
if tophash[i] == target {
// 逐个串行比较
}
}
Swiss 方式：
// 一次操作检查所有 8 个槽位！
matches := ctrlGroup.matchH2(target)
// matches 是 bitset，每位表示一个槽位是否匹配
实现原理：
func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset {
// 1. XOR：将匹配的字节变为 0x00
v := uint64(g) ^ (0x0101010101010101 * uint64(h))
// 2. 减法技巧：0x00 - 0x01 会借位变成 0xFF
// 其他值减 0x01 不会设置最高位
result := (v - 0x0101010101010101) &^ v
// 3. 提取每字节的最高位
return bitset(result & 0x8080808080808080)
}
AMD64 优化：使用 SIMD 指令（SSE2 PCMPEQB）进一步加速
3.3 二次探测序列
type probeSeq struct {
mask uint64 // 组数 - 1
offset uint64 // 当前偏移
index uint64 // 探测索引
}
func (s probeSeq) next() probeSeq {
s.index++
// 三角数序列：offset[i+1] = offset[i] + i + 1
s.offset = (s.offset + s.index) & s.mask
return s
}
探测公式：p(i) = (i² + i)/2 + hash (mod 组数)
优势：
- 当组数为 2 的幂时，保证遍历所有组
- 跳跃式分布，减少聚集（clustering）
- 缓存友好性优于线性探测
3.4 查找流程
底层调用了 runtime/maps/runtime_swiss.go 中的 mapaccess1() 或者 mapaccess2 函数：
- v := m[k] 调用
runtime_mapaccess1() - v,k := m[k] 调用
runtime_mapaccess2()
我们重点来看 runtime_mapaccess1()：
func runtime_mapaccess1(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
// 空map检查
if m == nil || m.Used() == 0 {
if err := mapKeyError(typ, key); err != nil {
panic(err)
}
return unsafe.Pointer(&zeroVal[0])
}
// 并发写检测
if m.writing != 0 {
fatal("concurrent map read and map write")
}
// ============================================
// 步骤 1：计算哈希值
// hash 将被分为 H1（高57位）和 H2（低7位）
// ============================================
hash := typ.Hasher(key, m.seed)
// ============================================
// 步骤 2：小 map 快速路径（≤8个元素）
// ============================================
if m.dirLen <= 0 {
// 小map：数据直接存储在单个group中，无需探测
_, elem, ok := m.getWithKeySmall(typ, hash, key)
if !ok {
return unsafe.Pointer(&zeroVal[0])
}
return elem
}
// ============================================
// 步骤 3：大 map 路径 - 选择 table
// 使用哈希值的高位索引目录，选择对应的 table
// ============================================
idx := m.directoryIndex(hash) // idx = hash >> globalShift
t := m.directoryAt(idx) // 获取 table 指针
// ============================================
// 步骤 4：二次探测循环
// 初始化探测序列：使用 H1（高57位）定位初始 group
// ============================================
seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
for ; ; seq = seq.next() { // 无限循环，直到找到或遇到空槽
// ----------------------------------------
// 步骤 4.1：获取当前探测的 group
// ----------------------------------------
g := t.groups.group(typ, seq.offset)
// ----------------------------------------
// 步骤 4.2：并行匹配控制字（核心优化！）
// 使用 H2（低7位）与控制字进行并行匹配
// 一次操作检查 8 个槽位的控制字
// ----------------------------------------
match := g.ctrls().matchH2(h2(hash)) // match 是 bitset，每位代表一个槽位是否匹配
// ----------------------------------------
// 步骤 4.3：遍历所有匹配的槽位
// ----------------------------------------
for match != 0 {
// 获取第一个匹配槽位的索引
i := match.first()
// 获取槽位中的 key 指针
slotKey := g.key(typ, i)
slotKeyOrig := slotKey // 保存原始指针（计算 elem 偏移用）
// 如果是间接key（key太大，存的是指针）
if typ.IndirectKey() {
slotKey = *((*unsafe.Pointer)(slotKey)) // 解引用
}
// ----------------------------------------
// 步骤 4.4：完整 key 比较
// ----------------------------------------
if typ.Key.Equal(key, slotKey) {
// 找到了！计算 elem 的地址
// elem 紧跟在 key 后面，偏移量为 typ.ElemOff
slotElem := unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
// 如果是间接elem（elem太大，存的是指针）
if typ.IndirectElem() {
slotElem = *((*unsafe.Pointer)(slotElem)) // 解引用
}
return slotElem // 返回元素指针
}
// key不匹配（控制字碰撞），移除当前匹配位，检查下一个
match = match.removeFirst()
}
// ----------------------------------------
// 步骤 4.5：检查空槽（探测终止条件）
// ----------------------------------------
match = g.ctrls().matchEmpty()
if match != 0 {
// 找到空槽 → 探测序列结束 → key不存在 → 返回对应类型的零值
return unsafe.Pointer(&zeroVal[0])
}
// 当前group没有匹配且无空槽，继续探测下一个group
// seq.next() 会应用二次探测公式：offset += index+1
}
}
查找步骤：
- 计算哈希并分割为 H1/H2
- 使用 H1 定位初始 group
- 并行匹配 H2（一次检查 8 个槽位）
- 对匹配的槽位进行完整 key 比较
- 未找到则二次探测下一个 group
正在绘制图表…
3.5 插入流程
插入底层调用了 runtime/maps/runtime_swiss.go 中的 runtime_mapassign() 函数：
func runtime_mapassign(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
// 并发写检测
if m.writing != 0 {
fatal("concurrent map writes")
}
// ============================================
// 步骤 1：计算哈希并设置写标志
// ============================================
hash := typ.Hasher(key, m.seed)
// 在调用Hasher之后设置writing标志（Hasher可能panic）
m.writing ^= 1 // toggle写标志
// ============================================
// 步骤 2：确保map已初始化
// ============================================
if m.dirPtr == nil {
m.growToSmall(typ) // 初始化为小map
}
// ============================================
// 步骤 3：小 map 快速路径（≤8个元素）
// ============================================
if m.dirLen == 0 {
if m.used < abi.SwissMapGroupSlots {
// 小map还有空间，直接插入
elem := m.putSlotSmall(typ, hash, key)
if m.writing == 0 {
fatal("concurrent map writes")
}
m.writing ^= 1 // 清除写标志
return elem
}
// 小map满了，扩展为大map
m.growToTable(typ)
}
// ============================================
// 步骤 4：大 map 路径 - 外层循环（处理rehash）
// ============================================
var slotElem unsafe.Pointer
outer:
for {
// ----------------------------------------
// 步骤 4.1：选择 table
// ----------------------------------------
idx := m.directoryIndex(hash)
t := m.directoryAt(idx)
// ----------------------------------------
// 步骤 4.2：初始化探测序列
// ----------------------------------------
seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
// 记录第一个删除槽位（墓碑复用优化）
var firstDeletedGroup groupReference
var firstDeletedSlot uintptr
// ----------------------------------------
// 步骤 4.3：二次探测内层循环
// ----------------------------------------
for ; ; seq = seq.next() {
g := t.groups.group(typ, seq.offset)
// 并行匹配控制字
match := g.ctrls().matchH2(h2(hash))
// ====================================
// 场景 1：查找已存在的 key（更新操作）
// ====================================
for match != 0 {
i := match.first()
slotKey := g.key(typ, i)
slotKeyOrig := slotKey
if typ.IndirectKey() {
slotKey = *((*unsafe.Pointer)(slotKey))
}
// 找到相同的key → 更新操作
if typ.Key.Equal(key, slotKey) {
// 某些类型需要更新key（如float NaN）
if typ.NeedKeyUpdate() {
typedmemmove(typ.Key, slotKey, key)
}
// 计算elem地址并返回
slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
if typ.IndirectElem() {
slotElem = *((*unsafe.Pointer)(slotElem))
}
t.checkInvariants(typ, m)
break outer // 完成更新，退出所有循环
}
match = match.removeFirst()
}
// ====================================
// 场景 2：遇到空槽 → 插入新 key
// ====================================
match = g.ctrls().matchEmpty()
if match != 0 {
// 找到空槽，探测序列结束
var i uintptr
// 优先复用删除槽位（避免消耗growthLeft）
if firstDeletedGroup.data != nil {
g = firstDeletedGroup
i = firstDeletedSlot
t.growthLeft++ // 补偿后面的--操作
} else {
// 使用空槽
i = match.first()
}
// --------------------------------
// 检查是否有增长空间
// --------------------------------
if t.growthLeft > 0 {
// 有空间，直接插入新entry
// 准备key存储
slotKey := g.key(typ, i)
slotKeyOrig := slotKey
if typ.IndirectKey() {
// 大key：分配堆内存，存指针
kmem := newobject(typ.Key)
*(*unsafe.Pointer)(slotKey) = kmem
slotKey = kmem
}
typedmemmove(typ.Key, slotKey, key)
// 准备elem存储
slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
if typ.IndirectElem() {
// 大elem：分配堆内存，存指针
emem := newobject(typ.Elem)
*(*unsafe.Pointer)(slotElem) = emem
slotElem = emem
}
// 设置控制字为H2
g.ctrls().set(i, ctrl(h2(hash)))
// 更新计数器
t.growthLeft--
t.used++
m.used++
t.checkInvariants(typ, m)
break outer // 完成插入，退出所有循环
}
// --------------------------------
// 没有增长空间，触发rehash
// --------------------------------
t.rehash(typ, m)
continue outer // 重新开始（table结构已变化）
}
// ====================================
// 场景 3：记录第一个删除槽位（延迟选择）
// ====================================
// 当前group没有空槽，继续探测，但记录删除槽位
if firstDeletedGroup.data == nil {
match = g.ctrls().matchEmptyOrDeleted()
if match != 0 {
// 找到删除槽位，记录下来
// （可能后续找到existing key，也可能用于插入）
firstDeletedGroup = g
firstDeletedSlot = match.first()
}
}
// 继续探测下一个group
}
}
// ============================================
// 步骤 5：清除写标志并返回
// ============================================
if m.writing == 0 {
fatal("concurrent map writes")
}
m.writing ^= 1 // 清除写标志
return slotElem // 返回elem指针供调用者写入值
}
关键策略：
- 优先重用墓碑槽位（避免浪费空间）
- 探测到空槽表示 key 不存在
- 自动触发表分裂（如果负载过高）
正在绘制图表…
3.6 删除操作（墓碑机制）
删除操作底层调用了 runtime/map_swiss.go 中的 mapdelete() 函数：
func mapdelete(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) {
// ...
m.Delete(t, key)
}
func (m *Map) Delete(typ *abi.SwissMapType, key unsafe.Pointer) {
// ...
if m.dirLen == 0 {
// 小 map 删除
m.deleteSmall(typ, hash, key)
} else {
// 大 map 删除
idx := m.directoryIndex(hash)
if m.directoryAt(idx).Delete(typ, m, hash, key) {
m.tombstonePossible = true // 如果返回 true，则表明可能设置了墓碑
}
}
// ...
}
根据 map 的大小具体分为 m.deleteSmall(typ, hash, key) 和 m.directoryAt(idx).Delete(typ, m, hash, key) 两种删除逻辑。我们重点来看一下 m.directoryAt(idx).Delete(typ, m, hash, key)：
// Delete 删除 key，返回是否放置了墓碑
// 返回 true：放置了墓碑（group已满，需要保持探测链完整）
// 返回 false：未找到key 或 直接清空（group有空槽）
func (t *table) Delete(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer) bool {
// 1：初始化二次探测序列
seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
// 2：探测循环 - 查找 key
for ; ; seq = seq.next() {
// 获取当前 group
g := t.groups.group(typ, seq.offset)
// 并行匹配控制字
match := g.ctrls().matchH2(h2(hash))
// 遍历所有匹配的槽位
for match != 0 {
i := match.first()
// 获取槽位中的 key
slotKey := g.key(typ, i)
origSlotKey := slotKey // 保存原始指针
if typ.IndirectKey() {
slotKey = *((*unsafe.Pointer)(slotKey))
}
// 3：找到匹配的 key，执行删除
if typ.Key.Equal(key, slotKey) {
t.used--
m.used--
// 清除 key 的内存
if typ.IndirectKey() {
*(*unsafe.Pointer)(origSlotKey) = nil
} else if typ.Key.Pointers() {
typedmemclr(typ.Key, slotKey)
}
// 清除 elem 的内存
slotElem := g.elem(typ, i)
if typ.IndirectElem() {
*(*unsafe.Pointer)(slotElem) = nil
} else {
typedmemclr(typ.Elem, slotElem)
}
// 4：决定控制字策略（关键设计！）
/*
* 核心逻辑：
* - 探测链遇到空槽会终止
* - 只有"满group"才会出现在探测链中间
* - group一旦满了，在rehash前会一直保持满
*
* 因此：
* - group有空槽 → 删除不会破坏探测链 → 直接清空
* - group无空槽 → 删除可能破坏探测链 → 放置墓碑
*/
var tombstone bool
if g.ctrls().matchEmpty() != 0 {
// --------------------------------
// 场景 A：group 有空槽 → 直接清空
// --------------------------------
g.ctrls().set(i, ctrlEmpty)
t.growthLeft++ // 恢复增长空间
tombstone = false
} else {
// --------------------------------
// 场景 B：group 已满 → 放置墓碑
// --------------------------------
g.ctrls().set(i, ctrlDeleted)
tombstone = true
// 注意：不增加 growthLeft
// 墓碑仍占用空间，但可被后续插入复用
}
t.checkInvariants(typ, m)
return tombstone // 返回是否放置了墓碑
}
// key不匹配，检查下一个匹配位
match = match.removeFirst()
}
// 4：检查空槽（探测终止条件）
match = g.ctrls().matchEmpty()
if match != 0 {
// 遇到空槽 → 探测链结束 → key不存在
return false
}
// 继续探测下一个 group
}
}
正在绘制图表…
墓碑的核心作用是：保持探测链的完整性，防止后续元素"失联"。
不用墓碑会发生什么？
假设有3个连续的满group（hash碰撞导致）：
初始状态（插入顺序：A → B → C）：
┌─────────────────────────┐
│ Group 5: [A][X][X][X][X][X][X][X] │ ← A的首选位置，但已满
└─────────────────────────┘
↓ 继续探测
┌─────────────────────────┐
│ Group 6: [B][X][X][X][X][X][X][X] │ ← B的首选也是Group 5，被挤到这里
└─────────────────────────┘
↓ 继续探测
┌─────────────────────────┐
│ Group 7: [C][X][X][X][X][X][X][X] │ ← C也是，被挤到这里
└─────────────────────────┘
↓
┌─────────────────────────┐
│ Group 8: [ ][...未使用...] │ ← 空槽，探测终止
└─────────────────────────┘
现在删除 B（如果直接设置为 Empty）：
┌─────────────────────────┐
│ Group 5: [A][X][X][X][X][X][X][X] │
└─────────────────────────┘
↓
┌─────────────────────────┐
│ Group 6: [Empty][X][X][X][X][X][X][X] │ ← 变成空槽！
└─────────────────────────┘
↓ ⚠️ 探测在这里终止！
┌─────────────────────────┐
│ Group 7: [C][X][X][X][X][X][X][X] │ ← C"失联"了！
└─────────────────────────┘
查找 C 时：
1. 计算 hash → 首选 Group 5
2. Group 5 没有 → 继续探测到 Group 6
3. Group 6 发现 Empty → 终止探测
4. 返回"不存在" ❌ （但 C 实际在 Group 7！）
解决方案：使用墓碑
删除 B（使用墓碑）：
┌─────────────────────────┐
│ Group 5: [A][X][X][X][X][X][X][X] │
└─────────────────────────┘
↓
┌─────────────────────────┐
│ Group 6: [Deleted][X][X][X][X][X][X][X] │ ← 墓碑，探测继续！
└─────────────────────────┘
↓ ✓ 探测继续
┌─────────────────────────┐
│ Group 7: [C][X][X][X][X][X][X][X] │ ← 能找到 C！
└─────────────────────────┘
↓
┌─────────────────────────┐
│ Group 8: [ ][...未使用...] │ ← Empty 才终止
└─────────────────────────┘
查找 C 时：
1. 计算 hash → 首选 Group 5
2. Group 5 没有 → 继续
3. Group 6 发现 Deleted → 跳过，继续探测！
4. Group 7 找到 C ✓
三种控制字代表不同的探测行为：
| ctrlEmpty | ctrlDeleted | H2 (0-127) |
|---|---|---|
| 空槽 | 墓碑 | 有效 entry |
| 停止探测，key 不存在 | 跳过继续找 | 检查 key，可能找到 |
实际代码中的体现：
// 探测循环中
match = g.ctrls().matchEmpty()
if match != 0 {
// 遇到 Empty → 终止
return false // key不存在
}
// 遇到 Deleted → 循环继续
// 遇到 H2 → 检查key
// 这就是为什么墓碑必须 != ctrlEmpty
为什么有些情况不需要墓碑？
如果删除后 group 有空槽：
删除前：
Group 6: [B][X][X][ ][ ][ ][ ][ ] ← 有空槽
删除 B：
Group 6: [ ][X][X][ ][ ][ ][ ][ ] ← 直接清空
为什么安全？
因为探测链本来就在这个 group 终止！
（有空槽意味着后续没有碰撞元素）
总结来说，墓碑 = 探测链的"虚拟占位符"，如果没有墓碑，删除操作会破坏开放寻址哈希表的探测链，导致某些元素永远找不到！
| 作用 | 说明 |
|---|---|
| 🔗 保持链接 | 防止探测链被"截断"，后续元素失联 |
| ♻️ 可复用 | 插入时优先使用墓碑位置（不消耗 growthLeft） |
| 🧹 延迟清理 | rehash 时一次性清除所有墓碑 |
| ⚖️ 权衡 | 占用空间 vs 探测链完整性 |
4. 可扩展哈希与增量扩容
4.1 可扩展哈希原理
传统单表扩容的问题：
Table (100万元素) → Table (200万元素)
↑ 延迟峰值！
Swiss map 的解决方案：
将大 map 拆分成多个小 table
每个 table 独立扩容
目录结构：
Hash = 0x1A2B3C4D
globalDepth = 2 (使用高 2 位)
┌────────────────────┐
│ Directory (size=4) │
├────────────────────┤
│ [00] → Table0 │ ← localDepth=1
│ [01] → Table0 │ ← 同一个 table
│ [10] → Table1 │ ← localDepth=2
│ [11] → Table2 │ ← localDepth=2
└────────────────────┘
hash >> (64-2) = 00 → 索引 Table0
4.2 表分裂过程
const maxTableCapacity = 1024
func (t *table) rehash(typ *abi.SwissMapType, m *Map) {
newCapacity := 2 * t.capacity
if newCapacity <= maxTableCapacity {
t.grow(typ, m, newCapacity) // 表内扩容
return
}
t.split(typ, m) // 分裂
}
触发条件：
- 负载因子 > 7/8（容量 × 0.875）
- 单表容量 ≤ 1024：表内扩容（容量翻倍）
- 单表容量 > 1024：分裂成两个表
分裂示例：
初始状态 (globalDepth=1):
Directory: [0] → Table0 (localDepth=1, 容量=1024)
[1] → Table1 (localDepth=1, 容量=1024)
Table1 满了，需要分裂：
1. Table1 分裂为 Table1a 和 Table1b
2. globalDepth 增加到 2
3. 目录扩展：
Directory: [00] → Table0 (localDepth=1)
[01] → Table0 (同一个)
[10] → Table1a (localDepth=2)
[11] → Table1b (localDepth=2)
分裂规则：
旧 table 的元素根据哈希的新 bit 分流：
hash & newbit == 0 → Table1a (低位)
hash & newbit != 0 → Table1b (高位)
4.3 负载因子
const maxAvgGroupLoad = 7 // 7/8 = 87.5%
- Non-Swiss：6.5（约 81%）
- Swiss：7/8（87.5%）
更高的原因：开放寻址 + 墓碑重用提高空间利用率
5. 与 Non-Swiss 对比
| 维度 | Non-Swiss | Swiss |
|---|---|---|
| 核心结构 | 桶 + 链式溢出 | 组 + 开放寻址 |
| 每桶/组大小 | 8 个键值对 | 8 个槽位 |
| 查找方式 | 顺序比较 tophash | 并行匹配 H2 ⭐ |
| 冲突处理 | 溢出桶链表 | 二次探测 |
| 扩容方式 | 渐进式迁移（全局锁） | 表分裂（细粒度） ⭐ |
| 负载因子 | 6.5 (81%) | 7/8 (87.5%) |
| 删除标记 | 直接删除 | 墓碑机制 |
| SIMD 支持 | 无 | AMD64 优化 ⭐ |
| 内存布局 | 分离 keys/values | 交错 key-value |
Swiss 的优势：
- ✅ 并行匹配：一次检查 8 个槽位
- ✅ SIMD 加速：硬件级优化
- ✅ 细粒度扩容：单表限制控制延迟
- ✅ 更高负载因子：空间利用率提升
Swiss 的劣势：
- ❌ 墓碑管理：需要定期清理
- ❌ 实现复杂：位运算 + SIMD 内联
- ❌ 目录开销：大 map 需要额外目录
6. 从源头理解 Swiss Table 版本
swiss table 版本的 map 实现对笔者来说还是比较新奇的，我一开始一直无法彻底这种这种实现思路。因为它的核心思想确实与我们教科书上常见的拉链法（Chaining）或线性探测法（Linear Probing）有很大不同。好在现在有 LLM，所以笔者跟 Gemini 进行了一番探讨，才对 swiss table 的底层原理有了更深的理解。
6.1 传统 HashMap 的问题
要从根本上理解 swiss table 版本的 HashMap，我们必须回归到第一性原理：HashMap 的目标是在 O(1) 的时间复杂度内完成插入、查找和删除。而这个 1 在现代 CPU 面前，其含金量是完全不同的。
[!IMPORTANT]
现代 CPU 的第一性原理：缓存为王 (Cache is King)
我们常说的 O(1) 理论上假设内存访问是等价的。但在现实中：
- CPU 访问 L1 缓存：~1-2 纳秒
- CPU 访问 L2 缓存：~5-10 纳秒
- CPU 访问 L3 缓存：~30-50 纳秒
- CPU 访问主内存 (RAM)：~100-200 纳秒
一个 Cache Miss 并从主内存读取数据的代价，可能是访问 L1 缓存的 100 倍以上。
传统的 HashMap 是一个"数组 + 链表"的结构。hash(key) 算出一个数组下标（桶 B[i]）。如果冲突了，就把这个 (key, value) 挂在 B[i] 后面的链表上。这存在 2 个问题：
- 缓存极不友好： 链表的节点在内存中是离散分布的。当你遍历一个长链表来查找 key 时，每访问一个节点，都极有可能导致一次 Cache Miss（这被称为指针追逐 pointer chasing）。
- 元数据开销： 每个节点都需要一个额外的指针来指向下一个节点，这在 64 位系统上就是 8 个字节。如果你的 (key, value) 本身很小（比如
map[int]int），这个指针的开销就非常巨大。
所以：传统拉链法的主要瓶颈不在于 CPU 计算，而在于内存访问延迟。
6.2 Swiss Table 的创新
Swiss Table 的核心思想是用密集的计算换取稀疏的内存访问。它属于开放寻址法（Open Addressing）的一种，但又做出了革命性的优化。它同时解决了两个层面的核心问题：
- 微观问题 (Group 内)： 如何在 8 个槽位 (slot) 中一次性找到目标？（解决 CPU 运算和 L1 缓存效率）
- 宏观问题 (Map 级)： 如何在 map 变得巨大时，实现低延迟的扩容？（解决内存访问和延迟抖动）
在我看来，Swiss Table 有 3 点最重要的核心创新：
6.2.1 核心创新一：控制字 (ctrls) 与并行匹配
这是 Swiss Map 对缓存为王的极致应用。
-
第一性原理： CPU 访问 8 个完整的
key来比较，即使它们都在 L1 缓存中，也是昂贵的（因为key可能很大）。最快的方式是，先用元数据过滤掉 99% 的无效比较。 -
理论：
- 数据结构：
group结构包含一个 8 字节的ctrls控制字 和 8 个slots(key/elem 对)。 - 哈希分割： 64 位哈希被分为 H1（高 57 位，用于定位）和 H2（低 7 位，用于匹配）。
- 控制字编码： 这 8 字节的
ctrls中，每个字节代表一个槽位 (slot) 的状态。0x80(1000 0000) =empty（空）0xFE(1111 1110) =deleted（墓碑）0x00-0x7F(0xxx xxxx) =full（已占用）
- 关键设计： 当槽位为
full时，它的 7 个x位存储的正是 H2 的 7 位哈希值。
- 数据结构：
-
**实践（并行匹配的魔力）：**当我们要查找一个 key（其 H2 值为 target_h2）时，我们不再需要 for 循环 8 次。Go (Abseil) 使用了一种位运算的魔法：
ctrlGroup.matchH2(target_h2)。v := uint64(g) ^ (0x0101010101010101 * uint64(h)) result := (v - 0x0101010101010101) &^ v matches := bitset(result & 0x8080808080808080)这一系列操作（在 AMD64 上甚至可以用 SIMD 指令
PCMPEQB加速）的唯一目的是：用 1-2 个 CPU 指令，同时将 8 个槽位的 H2 值与
target_h2进行比较，并返回一个bitset。这个
bitset(例如0b00100100) 会瞬间告诉我们："第 2 号和第 5 号槽位的 H2 匹配了，请只检查它们俩的完整key"。这使得查找 8 个槽位的开销，从 O(8) 次比较 降低到了 O(1) 次并行比较。
6.2.2 核心创新二：开放寻址与二次探测
这是 Swiss Map 解决哈希冲突的方式，也是它优于传统拉链法的第二个关键点。
- 第一性原理： 拉链法的
overflow链表节点在内存中是离散的，遍历链表会导致大量的指针追逐 (pointer chasing)，引发灾难性的 Cache Miss。 - **理论（开放寻址）：**Swiss Map 规定，所有数据都必须存储在连续的 group 数组中。如果
hash(key)算出的主 group 满了，它不会挂一个链表。 - 实践（二次探测）：
- 如果主
group满了（或者 H2 没匹配上，且没有空槽），我们怎么办？ - 我们通过一个二次探测 (Quadratic Probing) 公式：
p(i) = (i² + i)/2 + hash (mod 组数)，计算下一个要探测的group的索引。 - 这个公式的重点在于它可预测、无指针、计算快，并且能保证（在 2 的幂容量下）遍历所有
group。 - 根本收益： 我们用 CPU 计算（下一个索引） 代替了 内存访问（指针跳转）。由于
group数组是连续内存，下一个group极有可能也已在 CPU 缓存中，访问极快。
- 如果主
- **带来的问题（墓碑机制）：**这也解释了为什么需要
deleted (0xFE)状态。如文档所说，如果你删除了探测链中间的一个元素并将其标记为empty (0x80)，那么查找它后面的元素时，探测链会在这里错误地终止。因此，删除时必须留下墓碑 (tombstone)，告诉查找操作："这里曾经有过人，请继续往后找"。
6.2.3 核心创新三：可扩展哈希与表分裂
这是 Swiss Map 解决宏观扩容问题的精妙之举。
- 第一性原理： 传统 map 扩容时，需要分配一个 2 倍大的新数组，并把所有元素 rehash 过去。如果 map 有 1 亿个元素，这个延迟是不可接受的。
- **理论（可扩展哈希）：**Go 的 Swiss Map 并没有一个无限大的 group 数组。它引入了目录 (Directory) 结构。
- 顶层
Map结构有一个dirPtr和dirLen。 dirPtr指向一个[dirLen]*table指针数组。- 每个
table才是真正存储group的地方，但每个table的容量是受限的（例如 1024 个槽位）。
- 顶层
- 实践（增量扩容与表分裂）：
- 查找：
hash(key)的高位（由globalDepth决定）用于在directory中选择使用哪个table。hash(key)的低位（H1）用于在该table内进行“二次探测”。 - 扩容（关键）： 当一个
table负载过高（例如 > 7/8） 且已达到 1024 槽位的上限时，我们不再扩容整个 map。 - 我们只分裂这一个
table。如Table1(localDepth=1) 分裂为Table1a和Table1b(localDepth=2)。 - 然后，我们去更新
directory中的指针。如果directory不够大（globalDepth < new_localDepth），我们就只扩容directory（这很快，因为它只存指针）。 - 根本收益： 扩容的开销被均摊了。延迟是可控的，因为我们一次最多只迁移 1024 个元素，而不是 1 亿个。
- 查找：
6.2.4 总结
总的来说，Go Swiss Table 是三种先进技术的完美结合：
- 微观 (Group 内)： 并行匹配（基于 SIMD/位运算），实现 O(1) 的 8 槽位匹配。
- 中观 (Table 内)： 二次探测（开放寻址），实现无指针、缓存友好的冲突解决。
- 宏观 (Map 级)： 可扩展哈希（目录+表分裂），实现低延迟、增量式的扩容。
这套组合拳，从 L1 缓存、CPU 指令集，一直优化到全局内存布局和延迟控制，是现代高性能 Hash Map 的典范之作。
6.3 Swiss Table 的演进猜想
理解了是什么（What）之后，追问为什么（Why）和如何演进（How）是掌握一个复杂系统最根本的方法。本小节我们尝试像一个系统设计师一样，从零开始推演 Go Swiss Table 的实现过程。
6.3.1 第 0 步：明确目标与核心矛盾
- 初始状态： 拉链法。
- 要解决的核心矛盾（第一性原理）：
- 性能瓶颈： 传统 map 的性能瓶颈不在 CPU 计算，而在内存访问。
- 缓存失效 (Cache Miss)： 拉链法的溢出桶链表在内存中是离散的，遍历它会导致大量的指针追逐，每一次跳转都可能是一次昂贵的 Cache Miss（访问主内存）。
- 延迟抖动： 传统 map 扩容时，需要一次性迁移所有数据，导致服务（STW）的延迟毛刺。
- 新 map 的目标：
- 缓存友好： 必须用连续内存布局，消除指针追逐。
- 低延迟： 必须实现增量式扩容，平滑延迟。
- 高吞吐： 查找、插入、删除操作要尽可能快。
6.3.2 第 1 步：从拉链到开放寻址
为了实现目标 1（缓存友好）：
- 设计师的决策： 抛弃拉链法，全面转向开放寻址法 (Open Addressing)。
- 为什么？ 开放寻址法将所有 (key, value) 存储在一个连续的数组中。
- 带来的新问题：
- 冲突解决： 如何处理哈希冲突？（拉链法用链表，现在没链表了）
- 查找效率： 如何在连续数组中快速找到目标？
- 删除： 拉链法删除一个节点很简单，开放寻址法删除了一个元素，会不会中断探测链？
6.3.3 第 2 步：解决冲突与查找效率
为了解决第 1 步的新问题（冲突与查找）：
- 决策 1 - 冲突解决： 采用二次探测 (Quadratic Probing)。
- 为什么不用线性探测？ 线性探测（
hash + i）会导致严重的聚集。 - 为什么用二次探测？
p(i) = (i² + i)/2 + hash公式能跳跃式分布，减少聚集，且计算开销小。
- 为什么不用线性探测？ 线性探测（
- 决策 2 - 查找效率（Swiss Table 的核心！）：
- 开放寻址的痛点： 探测
i位置时，必须比较key == target_key。如果key是个很长的字符串，这个比较本身就非常昂贵。 - 思路： 我们能不能先不过早地比较完整的 Key？
- 解决方案： 引入元数据！将哈希值一分为二：H1（用于探测）和 H2（用于过滤）。
- 演进： 我们设计一个控制字 (Control Word) 数组，它与
slots数组平行。这个ctrls数组只存放 H2（低 7 位）。 - 查找流程优化：
- （昂贵）
for i... { if array[i].key == my_key } - （优化后）
for i... { if ctrls[i] == H2 { if array[i].key == my_key } }
- （昂贵）
- 收益： 99% 的比较，都从昂贵的 Key 比较变成了廉价的 1 字节 H2 比较。
- 开放寻址的痛点： 探测
6.3.4 第 3 步：将查找效率推向极致
为了解决第 2 步的遗留问题：
- 新痛点： 查找 H2（
ctrls[i] == H2）虽然廉价，但我们仍然在for循环！如果一个group有 8 个槽位，最坏情况还是要循环 8 次。 - 设计师的决策： 一次性比较 8 个槽位！
- 为什么？
- 现代 CPU 拥有 SIMD（单指令多数据流）指令集（如 x86 上的 SSE2，ARM 上的 NEON）。
- CPU 的 L1 缓存一次加载 64 字节（一个 Cache Line）。我们一个
group里的 8 字节ctrls必定在同一个 Cache Line 里。
- 解决方案：
- 将 8 个
ctrl字节视为一个uint64。 - 使用 SIMD 指令（如
PCMPEQB）或等效的位运算，并行地将这个uint64中的 8 个字节与我们目标的 H2 进行比较。 - 收益： 查找
group内 8 个槽位的复杂度，从 O(8)（串行） 降低到 O(1)（并行）。
- 将 8 个
6.3.5 第 4 步：解决删除的遗留问题
为了解决第 1 步留下的删除问题：
- 痛点： 在一个探测链
A -> B -> C中，如果删除了 B 并标记为empty。 - 后果： 查找 C 时，探测到 A，下一个是
empty，查找会提前终止，导致 C 永远找不到。 - 解决方案： 引入墓碑 (Tombstone) 状态。
- 演进：
ctrls字节现在必须有 3 种状态：empty(0x80)：空的，探测终止。deleted(0xFE)：墓碑，插入时可复用，查找时请继续。full(0x00-0x7F)：有数据（H2）。
6.3.6 第 5 步：解决扩容的延迟目标
为了实现目标 2（低延迟）：
- 痛点： 我们的开放寻址表（
group数组）如果满了（例如负载 > 87.5%），传统的做法是分配一个 2 倍大的新表，然后 rehash 所有元素。 - 后果： 导致巨大的延迟毛刺，违背了目标 2。
- 解决方案： 可扩展哈希 (Extensible Hashing)。
- 演进：
- 我们不使用一个无限大的表。我们将数据拆分到多个、固定大小（如 1024 槽位）的
table中。 - 我们引入一个目录 (Directory) 结构，它是一个指针数组，指向这些
table。 - 使用哈希的高位 (
globalDepth) 来决定去哪个directory槽位，找到对应的table。 - 使用哈希的低位 (H1) 在
table内部进行二次探测。
- 我们不使用一个无限大的表。我们将数据拆分到多个、固定大小（如 1024 槽位）的
- 收益：
- 当一个
table满了，我们只需要分裂这一个table！ - 扩容的开销被均摊了。一次迁移的元素上限是 1024，而不是 N（N 可能是 1 亿）。这完美解决了延迟抖动问题。
- 当一个
6.3.7 第 6 步：锦上添花的优化
- 痛点： 如果用户只
make(map[int]int)并存了 3 个元素，我们也需要分配directory和table吗？太浪费了。 - 解决方案： 小 Map 优化。
- 演进：
- 当
dirLen == 0时，dirPtr不指向directory，而是直接指向单个group（8 个槽位）。 - 收益： 对于绝大多数（< 8 个元素）的 map，内存开销极小，且无需任何
table间接寻址。
- 当
6.3.8 总结：从 0 到 1 的演进路径
这个 0 到 1 的实现路径，清晰地展现了从第一性原理出发的思考：
缓存失效（问题） → 1. 开放寻址（方案） → 2. 元数据（H2）过滤（解决比较效率） → 3. 并行匹配（极致优化比较） → 4. 墓碑（解决删除遗留问题） → 5. 可扩展哈希（解决扩容延迟） → 6. 小 Map 优化（解决小内存开销）
7. 并发：sync.Map 的 HashTrieMap 实现
7.1 为什么需要新实现？
传统 sync.Map 的问题：
- 全局锁：写操作竞争激烈
- 双 map 开销：read + dirty 内存翻倍
- 提升机制：周期性全量拷贝
HashTrieMap 的解决方案：
- Hash-Trie 结构：树形结构，天然支持分区
- 细粒度锁：每个节点独立锁，并发度高
- 无需提升：没有 read/dirty 切换
7.2 HashTrieMap 数据结构
type HashTrieMap[K comparable, V any] struct {
root atomic.Pointer[indirect[K, V]]
keyHash hashFunc
valEqual equalFunc
seed uintptr
}
// 中间节点（indirect node）
type indirect[K, V] struct {
mu Mutex // 节点锁
dead atomic.Bool // 节点是否已死
children [64]atomic.Pointer[node] // 64 个子节点
}
// 叶子节点（entry node）
type entry[K, V] struct {
overflow *entry[K, V] // 哈希冲突链表
key K
value V
}
Trie 结构（每层使用 6 位哈希）：
root
/ \
[0-63] [64-127]
/ \ |
[0-15] [16-31] [...]
| |
entries entries
7.3 查找流程
func (ht *HashTrieMap[K, V]) Load(key K) (V, bool) {
hash := Hash(key)
i := ht.root.Load()
// 从根向下遍历，每次取 6 位哈希
for shift := 58; shift >= 0; shift -= 6 {
idx := (hash >> shift) & 0x3F // 取 6 位
n := i.children[idx].Load()
if n == nil {
return zero, false
}
if n.isEntry {
return n.entry().lookup(key)
}
i = n.indirect()
}
}
无锁读取：读操作不需要加锁！
7.4 插入流程
func (ht *HashTrieMap[K, V]) LoadOrStore(key K, value V) (V, bool) {
hash := Hash(key)
retry:
// 无锁查找插入点
i, slot := ht.findInsertPoint(hash)
// 加锁（只锁一个节点）
i.mu.Lock()
defer i.mu.Unlock()
// 双重检查
n := slot.Load()
if n != nil && n changed {
goto retry // 节点变化，重试
}
// 插入新 entry
newEntry := &entry{key: key, value: value}
slot.Store(newEntry)
return value, false
}
细粒度锁：
root (lock1)
/ \
indirect1 indirect2
(lock2) (lock3)
↓ ↓
goroutine1 goroutine2
可以同时修改不同子树！
7.5 与传统 sync.Map 对比
| 维度 | Read-Write sync.Map | HashTrieMap |
|---|---|---|
| 数据结构 | 双 map（read + dirty） | Hash-Trie 树 |
| 并发策略 | 全局锁 + 读写分离 | 细粒度锁（per-node） |
| 读性能 | 命中 read：O(1) 无锁 未命中：加锁 | 始终无锁，O(log₆₄ n) |
| 写性能 | 快速路径：原子操作 慢速路径：全局锁 | 锁粒度细，O(log₆₄ n) |
| 内存开销 | 两份 map | Trie 节点开销 |
| 提升机制 | 需要周期性提升 | 无需提升 |
| 类型安全 | map[any]any | 泛型 HashTrieMap[K,V] |
HashTrieMap 的优势：
- ✅ 细粒度并发：锁竞争大幅降低
- ✅ 无需提升：没有全量拷贝开销
- ✅ 泛型支持：类型安全
- ✅ 读无锁：始终无需加锁
适用场景：
- 高并发写入
- 键空间大（Trie 的空间优势）
- 需要泛型支持
8. 总结
8.1 Swiss Map 核心创新
-
并行匹配算法：
传统：逐个比较 8 次 Swiss：并行比较 1 次（8 倍提升） -
可扩展哈希：
传统：单表扩容，延迟峰值 Swiss：多表分裂，延迟可控 -
SIMD 加速：
AMD64：使用 SSE2 指令 性能提升：2-3 倍
8.2 设计权衡
优势：
- ✅ 查找性能：并行匹配 + SIMD
- ✅ 空间效率：87.5% 负载因子
- ✅ 增量扩容：表分裂控制延迟
劣势：
- ❌ 墓碑管理：需要定期清理
- ❌ 实现复杂：位运算 + SIMD 内联
- ❌ 目录开销：大 map 需要额外结构
8.3 选择建议
┌─────────────────────────────────────┐
│ 需要并发？ │
│ ├─ 否 → 使用 map (Swiss 或 non-Swiss)|
│ └─ 是 ↓ │
├─────────────────────────────────────┤
│ 写多还是读多？ │
│ ├─ 读多 → sync.Map (Read-Write) │
│ └─ 写多 → sync.Map (HashTrieMap) │
└─────────────────────────────────────┘
最佳实践：
- 默认使用 Swiss map（已启用实验特性）
- 高并发场景使用 sync.Map
- 简单场景用
RWMutex + map
参考资料：
来自开放网络的回应
引用、喜欢、转发和站外回复会通过 Webmention 回到这里。
接收与展示代码已经就绪，注册正式域名后即可开始收集回应。
评论
评论由 GitHub Discussions 保存和管理。