Go · map 底层与并发

💡 一句话理解

map 就是"一个头加一片桶": hmap 只存 count/B/指针这些元数据, 真正的键值躺在 2^B 个桶里, 每桶 8 槽, 桶满了挂溢出桶。查找 = 哈希一次 + 低 B 位定桶 + tophash 指纹快筛 + 精确比对 key。扩容不搬家—— 分配新桶后搬迁摊到后续每次写操作, 所以单次写看起来还是 O(1)。代价是 map 完全不受并发保护: 一个在读一个在写, runtime 直接 fatal error, 整个进程退出, 连 recover 的机会都没有。

🧠 必知必会 必考 & 必会

map 的真身

变量本体是 *runtime.hmap: 元数据 + 指向桶数组的指针。把 map 赋给另一个变量只拷指针, 两个名字共享同一张表, 一处改两处可见。

a := map[string]int{"x": 1}
b := a                            // 关键: 只拷 *hmap 指针
b["x"] = 99
fmt.Println(a["x"])               // → 99, 共享同一张表

查找四步

哈希一次 → 低 B 位定桶 → tophash 快筛 8 槽 → memcmp key 确认, 命中取对应 value 槽; 桶内找不到再沿溢出链找。

v := m[key]
// ① 哈希 key  ② 低 B 位定桶 (2^B 个桶)
// ③ tophash 快筛 8 槽  ④ memcmp key 确认
// 关键: 桶内未命中 → 沿溢出桶链继续找

tophash

哈希值的高 8 位存在桶头, 一次缓存行访问筛掉不匹配的槽 —— map 快的核心。指纹相等不代表命中, 最终必须比 key 本体。

m := map[string]int{"a": 1}
fmt.Println(m["a"])          // → 1
// tophash = 哈希高 8 位存桶头, 一次筛掉不匹配槽
// 关键: 指纹相等 ≠ 命中, 最终必须比 key 本体

key 可比较性

slice/map/func 不能做 key(编译错); 接口做 key 时若动态类型不可比较, 运行时 panic: hash of unhashable type。

var _ map[[]int]int     // 编译错: invalid map key type
m := map[any]int{}       // 接口做 key: 编译过
m[[]int{1}] = 1          // 运行时 panic: hash of unhashable type []int

负载因子 6.5

count / 2^B > 6.5 触发双倍扩容(B+1): 平均每桶 6.5 个元素, 留 1.5 槽余量吸收哈希不均。

m := make(map[int]int)          // B=0: 1 个桶 8 槽
for i := 0; i < 7; i++ { m[i] = i }
// 关键: count/2^B > 6.5 即第 7 个触发翻倍扩容
// 留 1.5 槽余量吸收哈希不均

等量扩容

溢出桶数量接近 2^B 时触发: B 不变, 数据重新排布进新桶。目的是压缩溢出链(插入删除churn 打散数据), 不是扩容量。

// B 不变, 数据重排进新桶 — 不是扩容量
for i := 0; i < 1e6; i++ {
    m[key(i)] = i; delete(m, key(i)) // churn 打散数据
}
// 关键: 溢出桶 ≈ 2^B 时等量重排, 压缩溢出链

渐进式搬迁

扩容只分配新桶, 数据搬迁摊到后续每次写(一次搬 1~2 桶), nevacuate 记进度; 期间 old/new 并存, 访问先查新桶再回退旧桶。

// 扩容只分配新桶, 搬迁摊到后续每次写 (1~2 桶/次)
// nevacuate 记游标; 期间 old/new 并存: 内存双份峰值
// 关键: 访问先查 new, 未搬迁的回退 old 桶
// 全搬完 oldbuckets 置 nil, 均摊后单写近似 O(1)

遍历无序

起点桶和槽位随机化, 是刻意设计(防止业务依赖遍历序)。要有序输出: 先取 keys 排序再遍历。

m := map[string]int{"a": 1, "b": 2}
for k, v := range m { fmt.Println(k, v) } // 顺序每次可能不同
// 关键: 要有序 → 先取 keys 排序再遍历

逗号 ok

v, ok := m[k] 是判存在的唯一可靠方式 —— 零值完全可能是合法业务值, 单返回值版本区分不了"没有"和"是零"。

m := map[string]int{"cnt": 0}
v := m["cnt"]              // → 0, 但分不清"没有"和"是零"
v, ok := m["cnt"]            // v=0, ok=true
_, miss := m["none"]           // 关键: miss=false 才是"没有"

delete 不缩容

只清 tophash 和槽位, 桶数组不回缩。海量键删完内存不降, 想释放只能重建一张新 map 再整体替换。

for k := range big { delete(big, k) }
fmt.Println(len(big))         // → 0, 但桶数组内存不降
nm := make(map[K]V, need)    // 关键: 重建新表整体替换

nil map 语义

读返回零值不报错, 写直接 panic: assignment to entry in nil map。声明与初始化要成对出现。

var m map[string]int
fmt.Println(m["k"])           // → 0, 读不报错
m["k"] = 1                 // panic: assignment to entry in nil map

不可寻址

&m[k] 编译错: 扩容搬迁会让元素地址失效, 语言层面直接禁止。要修改就存指针或读-改-写回。

_ = &m["k"]              // 编译错: cannot take the address
v := m["k"]; v.field++; m["k"] = v // 对: 读-改-写回
mp := map[string]*T{}      // 关键: 或存指针

并发三选一

读多写少键集稳定 → sync.Map; 通用 → mutex+map; 写热点 → 分片锁。另外 make(map, hint) 预分配能整段省掉扩容搬迁链。

var sm sync.Map              // 读多写少: 读走只读层, 无锁
var mu sync.RWMutex; m := map[string]int{} // 通用
m := make(map[K]V, n)         // 关键: hint 预分配省扩容链

🏭 生产实战 real world

type entry struct {
    val      []byte
    expireAt int64 // unix nano: 惰性过期, 读时才判, 不起清扫 goroutine
}

type LocalCache struct {
    mu   sync.RWMutex          // 写锁全量, 读锁共享 — 读远多于写才划算
    data map[string]entry
    ttl  time.Duration
}

func (c *LocalCache) Get(key string) ([]byte, bool) {
    c.mu.RLock()
    e, ok := c.data[key]
    c.mu.RUnlock()
    if !ok || time.Now().UnixNano() > e.expireAt {
        return nil, false // miss 时上层 singleflight 回源防击穿(见 sync 页)
    }
    return e.val, true
}

var configMap sync.Map // key: 开关名 → 配置对象

// 发布端: 低频写(每天几次)
func UpdateConfig(name string, cfg Config) {
    configMap.Store(name, cfg) // 原子替换, 读端立即可见
}

// 消费端: 每请求读, QPS 5w — Load 走只读层, 无锁
func GetConfig(name string) Config {
    if v, ok := configMap.Load(name); ok {
        return v.(Config)
    }
    return DefaultConfig // 未加载兜底, 别让空配置悄悄上线
}
// 为什么不用 RWMutex: 读也要抢原子计数, 热点在多核间弹跳;
// sync.Map 读路径纯只读 map, 写走 dirty 晋升 — 各得其所

const shardBits = 4 // 2^4 = 16 片: 把锁冲突率降到 ~1/16

type ShardedCounter struct {
    shards [1 << shardBits]struct {
        mu sync.Mutex
        n  int64
    }
}

func (c *ShardedCounter) Inc(key uint64) {
    s := &c.shards[key&(1<<shardBits-1)] // 低位选片, 各锁各的
    s.mu.Lock()
    s.n++
    s.mu.Unlock()
}
// 压测(8 核全写): 单锁 map ~120w ops/s, p99 随核数恶化;
// 16 分片 ~890w ops/s 接近线性 — 分片数取核数附近的 2 的幂

rows, err := db.QueryContext(ctx, `SELECT sku, price FROM t_price`)
if err != nil {
    return fmt.Errorf("query prices: %w", err)
}
defer rows.Close()

n := 500_000 // 来自 COUNT(*) 或容量规划, 宁准勿大
prices := make(map[string]Price, n) // hint 一步到位: 桶一次分够

for rows.Next() {
    var p Price
    if err := rows.Scan(&p.SKU, &p.Cents); err != nil {
        return fmt.Errorf("scan: %w", err)
    }
    prices[p.SKU] = p
}
// 改后 210ms 且无尖刺; hint 超实际 10 倍以上 = 白占内存的空桶

groups := make(map[string][]Order, len(orders)/4) // 粗估分组长
for _, o := range orders {
    groups[o.City] = append(groups[o.City], o) // nil 切片可 append, 无需判空
}

// 需要稳定输出顺序: 取出 keys 排序, 绝不依赖遍历序
keys := make([]string, 0, len(groups))
for k := range groups {
    keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
    flush(groups[k]) // 下游按序消费, 测试可复现
}

seen := make(map[string]struct{}, len(logs))
dup := 0
for _, line := range logs {
    if _, ok := seen[line]; ok { // 逗号 ok: 与"空串也是合法行"区分
        dup++
        continue
    }
    seen[line] = struct{}{}
    write(line)
}
// bool 做 value: 亿级键多 ~100MB; struct{} 是零宽类型,
// 桶里只占 tophash + key 槽, value 区域完全不占

// var m map[string]map[string]float64; m["a"]["x"] = 1 直接 panic:
// 外层是 nil, 赋值目标不存在 — 且内层同样要 make

func ensure(m map[string]map[string]float64, top string) map[string]float64 {
    sub, ok := m[top]
    if !ok {
        sub = make(map[string]float64, 8) // 每层都要独立 make
        m[top] = sub                 // 外层键先落位
    }
    return sub
}

// 用法: 入口 m = make(...) 一次, 之后
//   ensure(m, "shop")["qps"] += 1 — 初始化收口, 处处安全

type Cache struct {
    cap int
    ll  *list.List               // container/list: 头 = 最新
    m   map[string]*list.Element // key → 节点, O(1) 定位
}

func (c *Cache) Get(k string) (any, bool) {
    if el, ok := c.m[k]; ok {
        c.ll.MoveToFront(el) // 访问即续期
        return el.Value.(pair).v, true
    }
    return nil, false
}
// 生产别手搓: hashicorp/golang-lru / ristretto 自带淘汰回调与
// 内存预算; 自研版只用于理解机制, 或千级以内小缓存

type Router struct {
    rules atomic.Pointer[map[string]Backend] // 整表一个指针
}

func (r *Router) Swap(newRules map[string]Backend) {
    // 深拷贝构建新表: 不在旧表上原地改, 读端才看不到半新半旧
    snapshot := make(map[string]Backend, len(newRules))
    for k, v := range newRules {
        snapshot[k] = v
    }
    r.rules.Store(&snapshot) // 单指针原子写 = 发布瞬间
}

func (r *Router) Pick(path string) Backend {
    m := *r.rules.Load() // 拿到的是不可变快照, 并发读安全
    return m[path]
}
// 前提: 快照发布后任何人不再修改它 — 违反即数据竞争

func tally(files []string) map[string]int {
    n := runtime.NumCPU()
    parts := make([]map[string]int, n)
    var wg sync.WaitGroup
    for i := 0; i < n; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            local := make(map[string]int, 1<<12) // 私有 map: 零锁竞争
            for _, f := range files[i*len(files)/n : (i+1)*len(files)/n] {
                countFile(local, f)
            }
            parts[i] = local
        }(i)
    }
    wg.Wait()
    total := make(map[string]int, len(parts[0])*n) // 合并只做一轮
    for _, p := range parts {
        for k, v := range p {
            total[k] += v
        }
    }
    return total
}

⚠️ 编码注意与常见坑 pitfalls

go func() {
    for { _ = m["k"] }           // 错: 一个在读
}()
m["k"] = 1                       // + 一个在写 → fatal error
// 对: 加锁/sync.Map/分片, CI 与预发常跑 -race

for k := range m {
    first = k; break           // 错: 遍历取第一条, 起点"随机"
}
keys := make([]string, 0, len(m))
for k := range m { keys = append(keys, k) }
sort.Strings(keys)                 // 对: 排序后再消费

for k := range big { delete(big, k) }  // 错: RSS 不降
nm := make(map[K]V, n)                // 对: 重建新表
for k, v := range src { nm[k] = v }
big = nm                                // 整体替换释放驻留

_ = &m[k]                       // 错: cannot take the address
v := m[k]; v.field++; m[k] = v  // 对: 读-改-写回
mp := map[K]*T{}; mp[k].field++ // 对: 或存指针

var m map[string]map[string]int
m["a"]["x"] = 1                  // 错: panic: assignment to entry in nil map
m = map[string]map[string]int{}   // 对: 每层 make
m["a"] = map[string]int{}; m["a"]["x"] = 1

var _ map[[]int]int          // 错: 编译不过 invalid map key type
m := map[string]int{}          // 对: key 用 string/整数
type K struct{ A string; B int }  // 对: 复合 key 定义结构体
_ = map[K]int{}

v := m["qty"]               // 错: 不存在拿 0 参与计算
v, ok := m["qty"]             // 对: 存在性判断
if !ok { return errors.New("missing qty") }

for k := range m {
    delete(m, k)               // 删当前 key: 规范保证安全
    m[newKey(k)] = 1           // 错: 新键出现与否不确定
}
// 对: 两阶段, 先收集要动的 keys 再改

m[k].field += 1               // 错: cannot assign to struct field
m2 := map[K]*T{}              // 对: 存指针
m2[k].field++                    // 通过指针改到本体

var sm sync.Map
for i := 0; i < 1e6; i++ {     // 错: 写走 dirty+晋升, 比锁慢
    sm.Store(i, i)
}
mu.Lock(); im[k] = v; mu.Unlock() // 对: 写多用 mutex+map

m := make(map[string]int, 10_000_000) // 错: 白占空桶
m := make(map[string]int, 50_000)     // 对: 贴近真实规模
// 拿不准就不传, 让 runtime 自己涨

var m map[string]int
b, _ := json.Marshal(m)          // 错: → null, 前端 .map() 崩
m = map[string]int{}             // 对: 声明即 make
b, _ = json.Marshal(m)           // → {}

seen := map[string]bool{}      // 错: bool 也占 value 槽
seen := map[string]struct{}{}  // 对: 零宽 value
if _, ok := seen[k]; ok {}       // 判存在同款

m := map[any]int{}           // 错: 哈希走动态派发+装箱
m := map[string]int{}          // 对: 具体类型 key

nm := make(map[K]V, len(old))   // old+new 并存
for k, v := range old { nm[k] = v } // 错: 大表换瞬间有 OOM 风险
old = nil                        // 对: 尽早弃旧表
// 对: 分批拆小表或低峰执行, 预留 ~2 倍峰值

for k := range m {
    k := k                   // 对: 1.22 前显式复制
    go func() { use(k) }()   // 错: 不复制则全拿最后一个 key
}

// 错: 本地压不触发就当没有 — 窄窗口撞上才崩
// 对: CI 必跑 go test -race ./...
//     预发常驻 -race: 内存 5~10 倍只付在测试环境

m := make(map[string]int)      // 错: 撞扩容的写要多干活
m := make(map[string]int, n)    // 对: hint 削掉扩容点
// 实时路径避开大 map 写

for k, v := range big { small[k] = v }  // 错: 写放大触发扩容
dst := make(map[K]V, len(a)+len(b))    // 对: 预留容量
for k, v := range small { dst[k] = v }    // 遍历小的写大的

var m map[string]int
v := m["k"]               // → 0, 不报错: 初始化遗漏安静烂线上
m["k"] = 1                // 只有写才 panic
// 对: 声明必初始化; 可疑读点判 m == nil