Golang Map 深度解析

基于 Go 1.26.4 源码，源码路径：/home/lin/src/github.com/go-go1.26.4
核心源文件：internal/runtime/maps/map.go、internal/runtime/maps/group.go、internal/runtime/maps/table.go、runtime/map.go

---

1 map 功能完整介绍

1.1 语法定义

Go 内置哈希表 map 使用 map[KeyType]ValueType 语法定义：

// 声明（零值 nil，不可直接赋值）
var m map[string]int

// make 初始化（指定初始容量可选）
m = make(map[string]int)
m = make(map[string]int, 100)  // hint=100

// 字面量初始化
m := map[string]int{
    "alice": 90,
    "bob":   85,
}

// 空字面量（非 nil！）
m := map[string]int{}

1.2 键值类型约束

key 类型必须满足 comparable 约束——即支持 == 和 != 比较：

可用 key 类型	不可用 key 类型	原因
int, int8…int64	[]T（切片）	切片不可比较
uint, uint8…uint64	map[K]V（map）	map 不可比较
float32, float64	func（函数）	函数不可比较
string
bool
complex64, complex128
指针 *T		指针比较的是地址
数组 [N]T（元素可比较）
结构体 struct{...}（字段均可比较）
接口 interface{}		接口比较动态类型+值

value 类型无限制——可以是任意类型，包括切片、map、函数、通道等。

1.3 存储特性

特性	说明
无序	for range 遍历顺序随机，每次运行可能不同
引用类型	map 变量本质是指针，传参不拷贝数据
非并发安全	同时读写会触发 fatal: concurrent map read and map write
动态扩容	负载因子超过 7/8 时触发扩容
不可取址	&m["key"] 编译错误，因为扩容会使地址失效

1.4 适用场景

---

2 底层 runtime 实现原理

⚠️ Go 1.26.4 的 map 实现已从传统的 hmap/bmap 迁移到 Swiss Table 设计（基于 Abseil），
核心代码在 internal/runtime/maps/ 包中。

2.1 Map 结构体完整字段说明

源码位置：internal/runtime/maps/map.go:191

type Map struct {
    // ★ 已使用的插槽数量（即 map 中的元素个数）
    // 必须放在第一个字段（编译器已知，用于 len() 内置函数）
    used uint64

    // ★ 哈希种子，每个 map 独有的随机数
    // 防止哈希碰撞攻击
    seed uintptr

    // ★ 目录指针——指向 table 指针数组或单个 group
    //
    // 正常情况: dirPtr 指向数组  *[dirLen]*table
    //
    // 小 map 优化: 如果 map 始终只有 ≤8 个元素，
    //   dirPtr 直接指向单个 group（无需 table 开销）
    //   此时 dirLen = 0
    dirPtr unsafe.Pointer

    // 目录长度 = 1 << globalDepth
    dirLen int

    // ★ 目录查找使用的比特数
    // 哈希值的顶部 globalDepth 位用于选择 table
    globalDepth uint8

    // ★ 目录查找的位移量
    // 64-bit 系统: globalShift = 64 - globalDepth
    globalShift uint8

    // ★ 写标志位
    // 正常=0, 写操作时=1
    // 如果多个 goroutine 并发写, XOR 1 使双方都能检测到竞态
    writing uint8

    // 是否可能存在墓碑（deleted 标记）
    tombstonePossible bool

    // Clear 调用的序列号，用于检测迭代期间的 clear
    clearSeq uint64
}

内存布局图：

Map 结构体 (64-bit, 约 56 bytes)
┌────────────────────────────────────────────────────┐
│  used            uint64     │ 元素数量（len()直接读）│
├────────────────────────────────────────────────────┤
│  seed            uintptr    │ 哈希种子（随机值）     │
├────────────────────────────────────────────────────┤
│  dirPtr          unsafe.P  │ 目录/小map group指针   │
├────────────────────────────────────────────────────┤
│  dirLen          int        │ 目录长度               │
├────────────────────────────────────────────────────┤
│  globalDepth     uint8      │ 目录查找比特数         │
│  globalShift     uint8      │ 目录位移量             │
│  writing         uint8      │ 写标志                 │
│  tombstonePossible bool     │ 墓碑标志               │
├────────────────────────────────────────────────────┤
│  clearSeq        uint64     │ Clear 序列号           │
└────────────────────────────────────────────────────┘

2.2 table 结构体——单个 Swiss Table

源码位置：internal/runtime/maps/table.go:18

type table struct {
    // 已填充的插槽数量
    used uint16

    // 总插槽数（2的幂次）= (groups.lengthMask+1) * MapGroupSlots
    capacity uint16

    // ★ 剩余可插入数（不含墓碑消耗的名额）
    // 当 used + tombstones > loadFactor*capacity 时触发 rehash
    growthLeft uint16

    // 此 table 的目录深度（可能 < globalDepth）
    localDepth uint8

    // 此 table 在目录中的首个索引位置
    // -1 表示已过期（被替换后不再在目录中）
    index int

    // ★ groups 数组——实际存储键值对的地方
    groups groupsReference
}

table 结构体
┌─────────────────────────────────────────────┐
│  used       uint16  │ 已用插槽数             │
│  capacity   uint16  │ 总插槽数（2^N）        │
│  growthLeft uint16  │ 剩余可插入数           │
│  localDepth uint8   │ 本地目录深度           │
│  index      int     │ 目录索引（-1=过期）    │
│  groups     groupsRef│ groups 数组引用       │
└─────────────────────────────────────────────┘

2.3 group 结构体——8 个插槽 + 控制字

源码位置：internal/runtime/maps/group.go:131

// 一个 group 的内存布局：
//
// type group struct {
//     ctrls ctrlGroup          // 8 字节控制字
//     slots [MapGroupSlots]slot // 8 个 key/elem 插槽
// }
//
// type slot struct {
//     key  typ.Key
//     elem typ.Elem
// }

type groupReference struct {
    data unsafe.Pointer // 指向 group 的内存
}

ctrl（控制字节）编码：

每个 slot 有 1 字节控制信息：

  empty:    1 0 0 0 0 0 0 0  (0x80) ← 空，未使用
  deleted:  1 1 1 1 1 1 1 0  (0xFE) ← 已删除（墓碑）
  full:     0 h h h h h h h          ← 已使用，低7位 = H2(hash)

判断规则：
  bit7=1 && bit1=0 → empty
  bit7=1 && bit1=1 → deleted
  bit7=0           → full (H2在低7位)

group 内存布局（以 map[string]int 为例）
┌──────────────────────────────────────────────────────┐
│  ctrlGroup (8 bytes)                                  │
│  ├── ctrl[0]: 0x42 (full, H2=0x42)                   │
│  ├── ctrl[1]: 0x80 (empty)                            │
│  ├── ctrl[2]: 0xFE (deleted/墓碑)                     │
│  ├── ctrl[3]: 0x17 (full, H2=0x17)                   │
│  ├── ctrl[4]: 0x80 (empty)                            │
│  ├── ctrl[5]: 0x80 (empty)                            │
│  ├── ctrl[6]: 0x80 (empty)                            │
│  └── ctrl[7]: 0x80 (empty)                            │
├──────────────────────────────────────────────────────┤
│  slot[0]: key="alice", elem=90                        │
│  slot[1]: (empty)                                     │
│  slot[2]: (deleted)                                   │
│  slot[3]: key="bob", elem=85                          │
│  slot[4]: (empty)                                     │
│  slot[5]: (empty)                                     │
│  slot[6]: (empty)                                     │
│  slot[7]: (empty)                                     │
└──────────────────────────────────────────────────────┘

2.4 哈希函数、桶寻址、probe 探测序列

哈希分割：H1 与 H2

64-bit hash 值:  hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhlllllll
                 │←──────────── H1 (57 bits) ────────────────────→│← H2(7b)→│

H1: 高 57 位 → 用于确定 probe 起始位置（哪个 group）
H2: 低 7 位  → 存储在控制字节中，用于快速过滤匹配

func h1(h uintptr) uintptr { return h >> 7 }     // 取高57位
func h2(h uintptr) uintptr { return h & 0x7f }   // 取低7位

probeSeq 探测序列

源码位置：internal/runtime/maps/table.go:530

// 二次探测序列: p(i) = hash + (i² + i)/2 mod (mask+1)
// 即: hash, hash+1, hash+3, hash+6, hash+10, ...
// 当 groups 数量是 2 的幂次时，此序列能遍历每个 group 恰好一次
type probeSeq struct {
    mask   uint64  // groups 数量 - 1
    offset uint64  // 当前 group 偏移
    index  uint64  // 步进索引
}

func makeProbeSeq(hash uintptr, mask uint64) probeSeq {
    return probeSeq{
        mask:   mask,
        offset: uint64(hash) & mask,  // H1 & mask = 起始 group
        index:  0,
    }
}

func (s probeSeq) next() probeSeq {
    s.index++
    s.offset = (s.offset + s.index) & s.mask  // 二次探测步进
    return s
}

2.5 哈希冲突解决——Swiss Table 方式

Go 1.26 采用 Swiss Table 设计（而非传统的拉链法），使用开放寻址 + 控制字节并行匹配：

传统拉链法 vs Swiss Table 对比：

传统拉链法（旧版 Go hmap/bmap）:
  bucket[0] → [k1][v1] → [k2][v2] → overflow bucket → ...
  bucket[1] → [k3][v3] → ...
  bucket[2] → ...

Swiss Table（Go 1.26+）:
  group[0]: ctrl=[0x42|0x80|0xFE|0x17|0x80|0x80|0x80|0x80]
            slots=[k1,v1|    |tomb|k3,v3|    |    |    |    ]
  group[1]: ctrl=[0x2A|0x80|0x80|0x80|0x80|0x80|0x80|0x80]
            slots=[k2,v2|    |    |    |    |    |    |    ]
  group[2]: ...

★ 冲突解决：同一 group 内通过 ctrl 并行比较 H2
            不同 group 间通过 probeSeq 二次探测
★ 不再使用链表/溢出桶！

并行匹配的魔力——matchH2 一次检查 8 个 slot：

// matchH2: 用位运算同时比较 8 个控制字节的 H2
func ctrlGroupMatchH2(g ctrlGroup, h uintptr) bitset {
    v := uint64(g) ^ (bitsetLSB * uint64(h))  // XOR 8 份 h
    return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)  // 巧妙判断哪些字节匹配
}
// 这条指令在 AMD64 上会被编译为 SIMD 指令，一条指令检查 8 个字节！

2.6 扩容机制：grow 和 split

扩容触发条件

当 growthLeft == 0 时（即 used + tombstones 达到 loadFactor × capacity）：
  1. 先尝试 pruneTombstones（清除不需要的墓碑）
  2. 如果墓碑不够多（< 10% capacity），则执行 rehash

两种扩容方式

func (t *table) rehash(typ *abi.MapType, m *Map) {
    newCapacity := 2 * t.capacity
    if newCapacity <= maxTableCapacity {   // maxTableCapacity = 1024
        t.grow(typ, m, newCapacity)        // ← 增量扩容：2倍容量
        return
    }
    t.split(typ, m)                        // ← 分裂：拆成两个 table
}

grow（增量扩容）

func (t *table) grow(typ *abi.MapType, m *Map, newCapacity uint16) {
    newTable := newTable(typ, uint64(newCapacity), t.index, t.localDepth)
    // 把旧 table 的所有有效 entry 重新插入新 table
    // 新的 probeSeq 基于 2 倍的 groups 数量
    for 每个有效 slot {
        hash := typ.Hasher(key, m.seed)
        newTable.uncheckedPutSlot(typ, hash, key, elem)
    }
    m.replaceTable(newTable)  // 在目录中替换旧 table
    t.index = -1              // 标记旧 table 为过期
}

split（分裂扩容——可扩展哈希）

func (t *table) split(typ *abi.MapType, m *Map) {
    localDepth := t.localDepth + 1
    left  := newTable(typ, maxTableCapacity, -1, localDepth)
    right := newTable(typ, maxTableCapacity, -1, localDepth)

    mask := localDepthMask(localDepth)  // 新增的1个比特位

    for 每个有效 slot {
        hash := typ.Hasher(key, m.seed)
        if hash & mask == 0 {
            left.uncheckedPutSlot(...)   // 该比特=0 → left
        } else {
            right.uncheckedPutSlot(...)  // 该比特=1 → right
        }
    }
    m.installTableSplit(t, left, right)  // 更新目录
}

目录扩展示例：

split 前（globalDepth=1, 2个目录项）:
  directory
  +----+
  | 0  | → table_A (localDepth=1)
  +----+
  | 1  | → table_B (localDepth=1)  ← B 满了，要 split
  +----+

split 后（globalDepth=2, 4个目录项）:
  directory
  +----+
  | 00 | → table_A (localDepth=1)   ← A 没变，两个目录项指向它
  +----+
  | 01 | → table_A (localDepth=1)
  +----+
  | 10 | → table_B_left (localDepth=2)  ← B 拆成两个
  +----+
  | 11 | → table_B_right (localDepth=2)
  +----+

2.7 删除机制与墓碑（tombstone）

func (t *table) Delete(typ *abi.MapType, m *Map, hash uintptr, key unsafe.Pointer) bool {
    // 1. 通过 probeSeq 找到 key
    // 2. 清除 key 和 elem
    // 3. 设置控制字节：
    
    if g.ctrls().matchEmpty() != 0 {
        // ★ group 内有空 slot → 可以安全设为 empty
        //    因为探测不会跳过有空 slot 的 group
        g.ctrls().set(i, ctrlEmpty)
        t.growthLeft++   // 恢复一个 growthLeft
    } else {
        // ★ group 全满 → 必须设为 deleted（墓碑）
        //    如果设为 empty，正在探测的查找会提前终止！
        g.ctrls().set(i, ctrlDeleted)  // 0xFE
        // growthLeft 不增加（墓碑仍占名额）
    }
}

墓碑机制的核心逻辑：

插入 k1 → hash(k1)%4 = 0 → group[0] 满 → 探测到 group[1] 插入

查找 k1: group[0] → 不匹配 → group[1] → 找到 ✅

如果删除 k1 时 group[0] 变为 empty 而非 deleted：
  查找 k1': hash(k1')%4 = 0 → group[0] 有 empty → 探测终止 → 未找到 ❌
  但 k1' 实际在 group[1]！

所以：group 全满时删除必须用墓碑，不能设为 empty！

2.8 map 内存初始化：var 声明 vs make

var 声明——零值 nil

var m map[string]int
// m = nil（Map 指针为 nil）
// m == nil → true
// len(m) → 0
// m["key"] → 0（读取不 panic，返回零值）
// m["key"] = 1 → panic! assignment to entry in nil map
// delete(m, "key") → 不 panic（no-op）
// for range m → 不执行循环体

底层原因：runtime 中 nil map 的检测：

// runtime/map.go
var maps_errNilAssign error = plainError("assignment to entry in nil map")

// 赋值操作编译为 mapassign 调用
// 内部会检查 m == nil → panic(maps_errNilAssign)

make 初始化——分配 Map 结构体

m := make(map[string]int)      // 调用 makemap_small() → 不预分配 group
m := make(map[string]int, 100) // 调用 makemap() → 按需分配 groups

// makemap_small: 小 map 优化
func makemap_small() *maps.Map {
    return maps.NewEmptyMap()  // 只分配 Map 结构体，不分配 group
                               // 首次赋值时再分配
}

// makemap: 带 hint 的初始化
func makemap(t *abi.MapType, hint int, m *maps.Map) *maps.Map {
    if hint <= abi.MapGroupSlots {  // ≤8 个元素
        return m  // 小 map，不需要预分配
    }
    // 计算 targetCapacity = (hint * 8) / 7
    // 分配 groups 和 directory
    return maps.NewMap(t, uintptr(hint), m, maxAlloc)
}

2.9 遍历 map 随机顺序的底层原因

源码位置：internal/runtime/maps/table.go Iter.Init

func (it *Iter) Init(typ *abi.MapType, m *maps.Map) {
    // ...
    it.entryOffset = rand()  // ★ 随机 slot 起始偏移！
    it.dirOffset = rand()    // ★ 随机目录起始偏移！
    // ...
}

两层随机化：

1. entryOffset：在 group 内，从随机 slot 开始遍历
2. dirOffset：在目录中，从随机 table 开始遍历

为什么这样做？

Go 语言规范明确要求迭代顺序是未指定的（unspecified），Go 团队刻意随机化遍历顺序，防止程序员依赖特定的迭代顺序——因为哈希表的实现可能在不同版本中改变，依赖顺序的代码不可移植。

---

3 示例代码逐行解析

3.1 声明与初始化

// ── 声明（零值 nil map）──
var m1 map[string]int
// [编译器] m1 = nil（*Map 指针为 nil）
// [注意] 可以读取 m1["key"] → 返回 0
// [注意] 不能写入 m1["key"] = 1 → panic!

// ── make 初始化 ──
m2 := make(map[string]int)
// [编译器] 调用 makemap_small()
// [运行时] 分配 Map 结构体 {used:0, seed:random, dirPtr:nil, dirLen:0}
//          首次赋值时分配第一个 group

// ── make 带 hint ──
m3 := make(map[string]int, 100)
// [编译器] 调用 makemap(mapType, 100, nil)
// [运行时] 计算需要 (100*8)/7 ≈ 115 个 slot
//          分配 Map + directory + groups
//          目录有多个 table，每个 table 有 8-1024 个 slot

// ── 字面量 ──
m4 := map[string]int{"a": 1, "b": 2}
// [编译器] 生成初始化代码
//          先 makemap_small()，再逐个 mapassign

3.2 赋值（写入）

m["alice"] = 90
// [编译器] 生成调用 mapassign(mapType, m, &"alice")
// [运行时] 底层流程：
//   1. 检查 m.writing != 0 → 如果正在写，fatal("concurrent map write")
//   2. 设置 m.writing = 1
//   3. hash = Hasher("alice", m.seed)  // 计算哈希
//   4. H1 = hash >> 7, H2 = hash & 0x7f
//   5. directoryIndex = hash >> m.globalShift  // 选择 table
//   6. 在 table 中 PutSlot:
//      a. seq = makeProbeSeq(H1, groupsMask)
//      b. group[seq.offset].ctrl.matchH2(H2)  // 并行匹配
//      c. 如果匹配到且 key 相等 → 更新 elem → 返回
//      d. 如果有空/墓碑 slot → 插入新 entry
//      e. 如果 growthLeft == 0 → pruneTombstones → rehash → 重试
//   7. 设置 m.writing = 0

3.3 取值（读取）

v := m["alice"]
// [编译器] 生成调用 mapaccess1(mapType, m, &"alice")
// [运行时] 底层流程：
//   1. 如果 m == nil → 返回零值指针（&zeroVal）
//   2. hash = Hasher("alice", m.seed)
//   3. 选择 table，在 table.Get 中：
//      a. seq = makeProbeSeq(H1, groupsMask)
//      b. group[seq.offset].ctrl.matchH2(H2)
//      c. 匹配到且 key 相等 → 返回 elem 指针
//      d. 匹配到 empty slot → 返回 zeroVal 指针
//      e. 全满 → seq.next() 继续探测

v, ok := m["alice"]
// [编译器] 生成调用 mapaccess2(mapType, m, &"alice")
//          返回 (elem指针, bool)
//          ok=true 表示 key 存在，ok=false 表示不存在

3.4 删除 delete

delete(m, "alice")
// [编译器] 生成调用 mapdelete(mapType, m, &"alice")
// [运行时] 底层流程：
//   1. 检查并发写
//   2. hash = Hasher("alice", m.seed)
//   3. 在 table.Delete 中：
//      a. probeSeq 找到 key
//      b. 清除 key 和 elem（typedmemclr）
//      c. 如果 group 有空 slot → ctrl = empty, growthLeft++
//      d. 如果 group 全满 → ctrl = deleted（墓碑）
//   4. m.used--
//   注意: delete 不存在的 key 是 no-op，不会 panic

3.5 长度 len

n := len(m)
// [编译器] 直接读取 m.used 字段（第一个字段，偏移=0）
// [运行时] 无函数调用，直接从 Map 结构体读取
//          即使 m == nil 也能工作（nil map 的 len 返回 0）

3.6 遍历 for range

for k, v := range m {
    fmt.Println(k, v)
}
// [编译器] 生成:
//   var it maps.Iter
//   mapIterStart(mapType, m, &it)  // 初始化 + 第一次 Next
//   for it.Key() != nil {
//       k = *it.Key()
//       v = *it.Elem()
//       // ... 循环体 ...
//       mapIterNext(&it)
//   }

// [运行时] Iter.Init 设置随机 entryOffset 和 dirOffset
//          Next() 从随机位置开始遍历所有 group 的所有 slot
//          跳过 empty 和 deleted 的 slot

3.7 nil map 直接赋值 panic 触发

var m map[string]int
m["key"] = 1  // panic: assignment to entry in nil map

// [运行时] mapassign 内部:
//   if m == nil {
//       panic(plainError("assignment to entry in nil map"))
//   }
// 触发位置：runtime/map.go 的 maps_errNilAssign 变量

3.8 key 不存在返回零值细节

v := m["nonexistent"]  // 返回 0（int 的零值）

// [运行时] mapaccess1 返回 unsafe.Pointer(&zeroVal[0])
//          编译器对零值有特殊处理：
//          - 如果 value 类型大小 > 0，mapaccess1_fat 传入 zero 指针
//          - 找不到 key 时返回 zero 指针（指向预分配的零值）
//          - 而不是返回 nil（因为 elem 指针不能为 nil）

---

4 完整使用示例合集

4.1 基础增删改查

package main

import "fmt"

func main() {
    // 创建
    m := make(map[string]int)
    
    // 增
    m["alice"] = 90
    m["bob"] = 85
    m["charlie"] = 78
    fmt.Println("after add:", m)  // map[alice:90 bob:85 charlie:78]
    
    // 查（两种方式）
    v1 := m["alice"]                    // 不存在返回零值 0
    v2, ok := m["david"]                // ok=false 表示不存在
    fmt.Println(v1, v2, ok)             // 90 0 false
    
    // 改
    m["alice"] = 95
    fmt.Println("after update:", m["alice"])  // 95
    
    // 删
    delete(m, "bob")
    fmt.Println("after delete:", m)      // map[alice:95 charlie:78]
    
    // 长度
    fmt.Println("len:", len(m))          // 2
}

4.2 结构体/切片作为 value

type Student struct {
    Name  string
    Score int
}

func main() {
    // 结构体作为 value
    m1 := map[int]Student{
        1: {Name: "Alice", Score: 90},
        2: {Name: "Bob", Score: 85},
    }
    m1[1].Score = 95  // ✅ Go 1.20+ 支持直接修改
    fmt.Println(m1[1])
    
    // 切片作为 value
    m2 := map[string][]string{
        "fruits":  {"apple", "banana"},
        "veggies": {"carrot", "celery"},
    }
    m2["fruits"] = append(m2["fruits"], "cherry")  // ✅ append 返回新切片
    fmt.Println(m2["fruits"])
}

4.3 map 嵌套 map

func main() {
    // 二维 map
    m := map[string]map[string]int{}
    
    // 必须初始化内层 map！
    m["class1"] = map[string]int{"alice": 90, "bob": 85}
    m["class2"] = map[string]int{"charlie": 78}
    
    // 查找
    if class, ok := m["class1"]; ok {
        if score, ok := class["alice"]; ok {
            fmt.Println("alice score:", score)  // 90
        }
    }
    
    // 安全写入辅助函数
    ensureMap(m, "class3")["david"] = 88
    fmt.Println(m)
}

func ensureMap(m map[string]map[string]int, key string) map[string]int {
    if m[key] == nil {
        m[key] = make(map[string]int)
    }
    return m[key]
}

4.4 map 有序遍历

import "sort"

func main() {
    m := map[string]int{
        "charlie": 78,
        "alice":   90,
        "bob":     85,
    }
    
    // 方法1：收集 key 排序
    keys := make([]string, 0, len(m))
    for k := range m {
        keys = append(keys, k)
    }
    sort.Strings(keys)
    for _, k := range keys {
        fmt.Printf("%s: %d\n", k, m[k])
    }
    // alice: 90
    // bob: 85
    // charlie: 78
    
    // 方法2：按 value 排序
    type entry struct{ Key string; Value int }
    entries := make([]entry, 0, len(m))
    for k, v := range m {
        entries = append(entries, entry{k, v})
    }
    sort.Slice(entries, func(i, j int) bool {
        return entries[i].Value > entries[j].Value  // 降序
    })
    for _, e := range entries {
        fmt.Printf("%s: %d\n", e.Key, e.Value)
    }
}

---

5 并发安全专题详解

5.1 原生 map 非并发安全底层原因

// Map 结构体中有 writing 标志位
type Map struct {
    writing uint8  // 写操作时设为 1
    // ...
}

// 写操作开始时：
m.writing = 1  // 或 XOR 1（并发写时双方都能检测到）

// 读操作时检查：
if m.writing != 0 {
    fatal("concurrent map iteration and map write")
}

// 写操作结束时：
m.writing = 0  // 或 XOR 1

为什么不用锁而是 fatal？

1. 性能：每次读写都加锁太重，标准库 map 是高性能设计的
2. 设计哲学：map 的竞态是程序 bug，应该暴露而非静默忍受
3. 不可恢复：竞态可能导致数据结构损坏，继续执行结果未定义

5.2 sync.RWMutex 封装并发安全 map

package safemap

import "sync"

type SafeMap[K comparable, V any] struct {
    mu sync.RWMutex
    m  map[K]V
}

func New[K comparable, V any]() *SafeMap[K, V] {
    return &SafeMap[K, V]{
        m: make(map[K]V),
    }
}

// 读操作：RLock 允许多个读者并发
func (s *SafeMap[K, V]) Get(key K) (V, bool) {
    s.mu.RLock()
    defer s.mu.RUnlock()
    v, ok := s.m[key]
    return v, ok
}

// 写操作：Lock 独占
func (s *SafeMap[K, V]) Set(key K, value V) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.m[key] = value
}

// 删除：Lock 独占
func (s *SafeMap[K, V]) Delete(key K) {
    s.mu.Lock()
    defer s.mu.Unlock()
    delete(s.m, key)
}

// 遍历：RLock
func (s *SafeMap[K, V]) Range(fn func(K, V) bool) {
    s.mu.RLock()
    defer s.mu.RUnlock()
    for k, v := range s.m {
        if !fn(k, v) {
            break
        }
    }
}

// Len：RLock
func (s *SafeMap[K, V]) Len() int {
    s.mu.RLock()
    defer s.mu.RUnlock()
    return len(s.m)
}

读写锁性能特征：

操作          锁类型     并发性
Get           RLock     ✅ 多读者并发
Set           Lock      ❌ 独占
Delete        Lock      ❌ 独占
Range         RLock     ✅ 多读者并发

适用场景：读多写少（如配置缓存、白名单）
不适用场景：写频繁（Lock 竞争严重）

5.3 sync.Map 适用场景对比

Go 1.9+ 引入的 sync.Map 是无锁读的并发安全 map：

var m sync.Map

m.Store("key", "value")           // 写
v, ok := m.Load("key")            // 读
v, ok := m.LoadOrStore("k", "v")  // 读或写
m.Delete("key")                   // 删
m.Range(func(k, v any) bool {     // 遍历
    fmt.Println(k, v)
    return true
})

sync.Map 内部设计：

sync.Map 结构：
  read  atomic.Value → readOnly{amended: bool, m: map[any]*entry}
  dirty map[any]*entry

entry 状态：
  - *expunged → 已删除且不在 dirty 中
  - nil       → 已删除但在 dirty 中
  - 正常指针 → 有效值

读路径：
  1. 先查 read（原子读，无锁）→ 命中 → 直接返回 ⚡
  2. 未命中 + amended=true → 加锁查 dirty → 找到 → 返回
  3. 未命中 → 返回 false

写路径：
  1. 先查 read → key 存在 → CAS 更新 entry（无锁）⚡
  2. key 不存在或 expunged → 加锁 → 写 dirty → 可能提升 dirty 到 read

三种方案对比：

维度	map + RWMutex	sync.Map	原生 map
读性能	中等（RLock）	快（原子读）	最快（无锁）
写性能	中等（Lock）	慢（dirty 提升）	最快（但并发崩溃）
适用场景	读多写少	读远多于写，key 稳定	单 goroutine
类型安全	泛型可用	any 接口	泛型可用
遍历安全	RLock 保护	快照语义	不并发安全

---

6 经典问题与优化

6.1 遍历中删除/新增元素的风险

Go 的行为：

迭代语义（Go 规范）：
1. ✅ 迭代期间删除的元素——不会在后续迭代中出现
2. ✅ 迭代期间新增的元素——可能出现也可能不出现
3. ✅ 迭代期间修改的元素——返回最新值
4. ✅ 不会返回同一个 entry 两次

安全删除方式：

// ❌ 危险：在其他 goroutine 删除（并发问题）
// ✅ 安全：在同一个 goroutine 中用 for range 删除

// 方式1：for range 直接 delete（安全）
for k, v := range m {
    if v < 0 {
        delete(m, k)  // ✅ 安全，Go 保证不会重复或遗漏
    }
}

// 方式2：收集 key 后再删除（更安全，逻辑更清晰）
var toDelete []string
for k, v := range m {
    if v < 0 {
        toDelete = append(toDelete, k)
    }
}
for _, k := range toDelete {
    delete(m, k)
}

6.2 map key 类型限制原因

为什么切片、map、函数不能做 key？

根本原因：这些类型不可比较（not comparable），而 map 的查找依赖于 key 的 == 比较。

// 切片不可比较的原因：
a := []int{1, 2, 3}
b := []int{1, 2, 3}
// a == b  → 编译错误！切片不可比较
// 原因：切片是引用类型，如果 == 比较的是内容，那每次比较都要遍历
//        如果 == 比较的是指针，那语义不直观（相同内容但不同地址就不等）

// 解决方案：转换为可比较类型
m[string(a)] = value      // 切片转字符串
m[fmt.Sprintf("%v", a)]   // 格式化为字符串 key

6.3 内存无法主动释放、大 map 内存占用优化

问题：delete 只标记墓碑或清空 slot，不会释放 group 的内存。map 的内存只在以下情况释放：

1. map 变量本身被 GC 回收（没有引用了）
2. map 被整体 Clear

优化方案：

// 方案1：重建 map（适合大量删除后）
old := m
m = make(map[string]int, len(old))  // 新 map 只有实际元素大小
for k, v := range old {
    m[k] = v
}
// old 被 GC 回收

// 方案2：使用 clear（Go 1.21+）
clear(m)  // 清空所有元素，保留底层数组

// 方案3：分片 map（减少单 map 的内存压力）
type ShardedMap[K comparable, V any] struct {
    shards [64]struct {
        mu sync.RWMutex
        m  map[K]V
    }
}

func (s *ShardedMap[K, V]) shard(key K) int {
    h := fnv.New32a()
    h.Write([]byte(fmt.Sprintf("%v", key)))
    return int(h.Sum32() % 64)
}

func (s *ShardedMap[K, V]) Get(key K) (V, bool) {
    sh := &s.shards[s.shard(key)]
    sh.mu.RLock()
    defer sh.mu.RUnlock()
    v, ok := sh.m[key]
    return v, ok
}

func (s *ShardedMap[K, V]) Set(key K, value V) {
    sh := &s.shards[s.shard(key)]
    sh.mu.Lock()
    defer sh.mu.Unlock()
    sh.m[key] = value
}
// 每个 shard 独立 GC，单 shard 扩容不影响其他 shard

大 map 内存占用分析：

每个 entry 的内存开销：
  - key 存储：sizeof(key) 或 8 bytes（indirect key 指针）
  - elem 存储：sizeof(elem) 或 8 bytes（indirect elem 指针）
  - ctrl 字节：1 byte / slot（8 bytes / group）
  - group 对齐开销
  - table 元数据：~20 bytes / table
  - directory：8 bytes * (1 << globalDepth)

示例：map[int64]int64, 100万个元素
  - 纯数据：100万 * 16 = 16 MB
  - 实际占用：~20 MB（含 ctrl、group 对齐、table 元数据）
  - 负载因子 7/8，总 slot 数 = 100万 / (7/8) ≈ 114万

---

7 总结：Go Map 核心知识图谱

Go 1.26 Swiss Table vs 旧版 hmap/bmap 对比：

旧版 (Go ≤1.23)                    新版 (Go 1.24+)
hmap + bmap                        Map + table + group
拉链法（溢出桶链表）                 开放寻址（Swiss Table）
每个 bucket 8个 key/elem           每个 group 8个 slot
overflow bucket 处理冲突            probeSeq 二次探测
等量扩容 + 增量扩容                  grow 2倍 + split 分裂
渐进式搬迁（evacuate）              一次性 rehash（单 table 范围小）
 evacuated 标记位                   table.index = -1（过期标记）

---

源码索引

文件	关键内容
internal/runtime/maps/map.go	Map 结构体、NewMap、NewEmptyMap、directoryIndex、installTableSplit、replaceTable
internal/runtime/maps/table.go	table 结构体、Get、PutSlot、Delete、rehash、grow、split、Iter、probeSeq
internal/runtime/maps/group.go	ctrlGroup、matchH2、matchEmpty、matchFull、groupReference、bitset
runtime/map.go	makemap、makemap_small、mapassign、mapaccess1/2、mapdelete、mapIterStart/Next、mapclear