Go Map：从 hash 到 Go 1.24+ Swiss Table

先看它解决什么问题

班级只有 3 名学生时，把姓名和成绩放进列表，再从头比较姓名也能找到 Tom。可是一旦有 10 万名学生，每次查询都从第一项开始找，最坏要比较 10 万次。我们需要一种结构，把“按姓名寻找”变成“根据姓名直接缩小到很小的候选范围”。

map 的正式名称是 key-value（键值对）数据结构：key（键）像姓名或编号，用来定位数据；value（值）是这个键对应的实际内容。下面的 scores 代表“全班成绩表”，student 代表“这次要查询的学生”。

package main

import "fmt"

func main() {
    scores := make(map[string]int)
    scores["Tom"] = 90

    student := "Tom"
    score := scores[student]
    fmt.Println(score)
}

map[string]int 表示 key 的类型是 string（字符串），value 的类型是 int（整数）。类型写在这里，是为了限制这张 map 允许存什么数据。

最小对照：0 分和没这个学生

scores := map[string]int{"Tom": 0}

tomScore, tomExists := scores["Tom"] // 0, true：学生存在，成绩就是 0
bobScore, bobExists := scores["Bob"] // 0, false：学生不存在

两次读取都得到数字 0，只改变 key 是否存在，ok 的结果就不同。这就是 comma-ok 真正解决的歧义。

nil map

nil 表示这个 map 变量目前没有指向已经初始化的底层存储。它看起来像一个空 map，因此可以读，但还没有可写入的空间；强行写入会触发 panic，也就是程序发现无法继续执行当前操作时抛出的运行时错误。

var m map[string]int
fmt.Println(m["a"]) // 0，可以读
m["a"] = 1            // panic: assignment to entry in nil map

key 为什么必须可比较

“可比较”是指两个值可以使用 == 判断是否相等。hash 只能帮你快速缩小范围，最终仍要判断“候选 key 和查询 key 是否真的相等”。所以 map key 必须可比较。slice（动态长度序列）、map 和 func（函数值）不能做 key；数组和结构体只有内部字段都可比较时才可以。

1. hash 函数是什么

可以先按小学生版本记：hash 函数就是一台“编号机”，把任意 key 算成一个固定长度整数。这个整数不是 value，只是为了定位数据。

key                 hash(key)
"Tom"        ->     0x8f31a6c2d4b97012
123          ->     0x7b
User{ID:7}   ->     某个固定长度整数

2. hash 函数不保证唯一

不同 key 可能产生相同的 hash 摘要或落入同一个搜索区域，这就是哈希冲突。所以任何可靠实现都不能“只比较 hash 就认为 key 相等”，最终必须比较完整 key。

3. 当前 Swiss Table 怎么拆 hash

H 是 hash 的缩写。Go 把一个 64 位 hash 数字拆成 H1 和 H2 两部分：H1 负责“大范围定位”，H2 是用于快速初筛的“小摘要”。

64 位 hash
┌──────────────────────────────────────────────────────────┬───────┐
│ H1：高 57 位                                              │ H2    │
│ 选择大区域 / 起始小组 / 冲突后继续寻找                    │ 低7位 │
└──────────────────────────────────────────────────────────┴───────┘

1. 五层结构与关键元数据

可以把它想成五层收纳结构：先从总盒子找到目录，再找到某张表、某个小组，最后落到一个具体位置。

2. control word 为什么是 Swiss Table 的关键

开放寻址（open addressing）是一种处理冲突的方法：目标位置已经被占用时，不挂一条链，而是继续在同一组连续存储空间里寻找其他位置。传统开放寻址往往一个 slot 一个 slot 比；Swiss Table 额外使用紧凑的 control word，其中 8 个 control byte（控制字节）分别对应 8 个 slot。查询时可以用位运算——直接对一串 0/1 进行计算——一次比较 8 个 H2，快速找出候选槽位，再只对候选槽做完整 key 比较。

下面图中的 empty 表示真正的空槽，deleted 表示这里原来有数据、后来被删除，但查询暂时还不能在这里停止。

3. 现在已经不用 bucket 了吗？

准确地说：Go 1.24+ 已经不再使用旧版的 bmap bucket + overflow bucket 结构。bmap bucket 是旧版一次存放 8 组数据的桶；overflow bucket（溢出桶）是原桶装满后额外连接的桶。但这不代表当前所有槽位都毫无分组地堆在一起：新版仍然会分组，只是分组单位改叫 Group，内部组织和冲突处理方式也变了。

这里说“更现代”，主要是指它更适合现代处理器：

• 相关数据放得更紧凑：更容易一起进入 CPU cache，减少根据 overflow 地址到处寻找。
• 一次筛 8 个槽：control word 可以同时筛选 8 个 H2，不必马上比较多个完整 key。
• 冲突后继续检查连续 Group：probe（探测）就是“按既定顺序寻找下一个可能位置”。让接下来要访问的数据尽量待在相近内存中，这种特性叫内存局部性，通常比追踪溢出桶地址更适合 CPU cache。

1. 查询 v := m["Tom"]

1. 根据 key 类型和 map 的随机 seed（哈希种子，可以理解成每张 map 自己的一份随机“调味料”）计算 hash。
2. 拆出 H1 / H2。
3. 如果有多个 table，使用 hash 高位从 Directory 选择 table。
4. H1 决定 table 内初始 group。
5. control word 用 H2 一次筛选 8 个 slot。
6. 对 H2 匹配的候选 slot 做完整 key 比较。
7. 没找到且尚未遇到 empty（真正空槽）：按二次探测序列检查下一个 group。
8. 找到返回 value；确认不存在则返回 value 零值，comma-ok 的 ok=false。

2. 哈希冲突怎么办

当前实现使用开放寻址和 quadratic probing（二次探测）。二次探测就是：发生冲突后，不固定每次只往后走一步，而是按逐渐变化的距离检查下一组。注意这里的探测单位是整个 group，不是一个 slot；每次先同时检查组内 8 个 control byte，再沿序列进入下一组。

3. delete 为什么有 tombstone

查询在看到真正 empty 时可以停止。如果删除一个元素后错误地直接标成 empty，就可能把 probe 链截断，让后面的元素“失联”。所以必要时删除会标记 deleted（tombstone，墓碑）。后续插入会优先复用 tombstone。

扩容就是在元素越来越多、原有空间快不够时增加存储容量；分裂则是把一张已经很大的 Table 拆成两张较小的 Table。

1. 当前负载因子

负载因子（load factor）表示“已经使用的 slot 占全部 slot 的比例”。Swiss Table 的最大平均 group 负载是 7/8：一个 group 有 8 个 slot，平均最多使用约 7 个，需要保留空位，让查询知道在哪里可以停止，同时避免冲突过多。

2. 每张 table 独立增长

grow 就是“增长容量”。当前 Map 可以有多张 Table，每张 Table 可以独立 grow：

• 容量较小时：Table 整体翻倍并 rehash（重新根据 hash 把旧元素放进新的位置）。
• 单张 Table 达到当前源码上限 1024 个 slot 后：执行 split（把一张 Table 分裂成两张）。
• Directory 使用 hash 高位选择 Table；必要时 Directory 自身翻倍。

3. 分裂前后：目录项怎样改指向

Directory 的长度由 global depth（全局深度）决定，它表示目录当前使用多少个 hash 高位来选 Table；每张 Table 记录自己的 local depth（局部深度），表示这张 Table 实际由多少个 hash 高位区分。当 local depth 小于 global depth 时，多个目录项会共享同一张 Table——这不是重复数据，只是多个地址指向同一个对象。

4. 什么时候 Directory 自身也要翻倍

如果待分裂 Table 的 local depth == global depth，现有目录位数已经不足以区分两个新 Table。此时先把 Directory 翻倍（每个旧指针复制成两个目录项），global depth 加 1，再按新增的 hash 高位把相关目录项分别改指向 left / right。这样扩容只重建一张局部 Table；其他 Table 仍复用原指针。

package main

import (
    "fmt"
    "sort"
)

func main() {
    // 1. nil map：可以读，不能写
    var nilMap map[string]int
    fmt.Println(nilMap["missing"]) // 0

    // 2. hint 不是长度
    scores := make(map[string]int, 8)
    fmt.Println(len(scores)) // 0

    scores["Tom"] = 0
    scores["Jack"] = 90
    scores["Lucy"] = 95

    // 3. comma ok：区分“零值”和“不存在”
    v1, ok1 := scores["Tom"]
    v2, ok2 := scores["Bob"]
    fmt.Println(v1, ok1) // 0 true
    fmt.Println(v2, ok2) // 0 false

    // 4. range 无序；需要稳定结果时排序 key
    keys := make([]string, 0, len(scores))
    for k := range scores {
        keys = append(keys, k)
    }
    sort.Strings(keys)
    for _, k := range keys {
        fmt.Printf("%s => %d\n", k, scores[k])
    }

    // 5. 删除不存在 key 也安全
    delete(scores, "not-exist")
}

Go map 本质是哈希表。

当前版本先说 Go 1.24+：
内置 map 默认使用 Swiss Table。
顶层 Map 可以通过 Directory 管理多张 Table，
每张 Table 由多个 Group 组成，每个 Group 有 8 个 key/value slot
和一个 8 字节 control word。

key 先计算 hash，再拆 H1 和 H2：
H1 是高 57 位，用于选 Table、找初始 Group、参与 group 级 quadratic probing；
H2 是低 7 位，保存在 control byte 中。
查询时先用 H2 一次筛 8 个 slot，
再对候选 slot 比较完整 key。

当前冲突处理主要是开放寻址 + group 级 quadratic probing，
探测偏移按 0、1、3、6……增长。
扩容按 Table 局部进行，小 Table 翻倍，
达到上限后 split 成两个；多个目录项可先共享同一 Table，
split 后只更新相关指针，必要时 Directory 自身翻倍。

另外：
nil map 可以读不能写；
range 顺序不保证；
key 必须可比较；
普通 map 不支持无同步的并发写。

本文只讲 Go 1.24+ 当前实现。探测算法已按源码校正为“group 级 quadratic probing”，而非 linear probing；旧版内部结构请查看经典 hmap/bmap 专题。

• Go 1.24 Release Notes
• Go Blog：Faster Go maps with Swiss Tables
• Go 源码：internal/runtime/maps/map.go
• Go 源码：table.go（split / grow / probeSeq）