HikariTish

1
// 方式一：声明未初始化（nil map）
2
var m1 map[int]string
3
// m1 == nil  →  true
4

5
// 方式二：动态分配初始化
6
m2 := make(map[int]string)
7
m3 := map[int]string{}
8

9
// 方式三：预分配容量（推荐）
10
m4 := make(map[int]string, 100)

1
// make 的第二个参数是"预期元素数"，不是桶数量
2
m := make(map[int]string, 100)

1
所需桶数 = ceil(100 / 6.5) ≈ 16 → 2^4 → 预分配 16 个桶 (B=4)

1
// 单值读取：key 不存在时返回零值
2
val := m[key]   // key 不存在 → val 为零值，无法区分"存的是零值"还是"不存在"
3

4
// ✓ Comma-ok 惯用法：精准判断存在性
5
if val, ok := m[key]; ok {
6
    // key 存在
7
} else {
8
    // key 不存在
9
}

1
delete(m, key)

1
for k, v := range m {
2
    // 处理逻辑
3
}

1
n := len(m)  // 返回元素总数，O(1)

1
clear(m)  // 清空所有键值对，len(m) → 0

1
┌──────────────────────────────────────────────────────────────┐
2
│                     bmap 内存布局                              │
3
├──────────────────────────────────────────────────────────────┤
4
│  tophash[0..7]  │  key[0]..key[7]  │  value[0]..value[7]  │  overflow │
5
│     8×1B        │   8×sizeof(key)  │  8×sizeof(value)     │  指针     │
6
└──────────────────────────────────────────────────────────────┘

1
buckets 数组
2
┌───────┬───────┬───────┬───────┐
3
│ bmap0 │ bmap1 │ bmap2 │ bmap3 │  ← 2^B 个桶
4
└───┬───┴───────┴───────┴───────┘
5
    │
6
    ├── 装满 → overflow → ┌───────┐
7
    │                      │bmap(溢)│
8
    │                      └───┬───┘
9
    │                          │
10
    │                          └── overflow → ┌───────┐
11
    │                                          │bmap(溢)│
12
    │                                          └───────┘

1
64 位哈希值：| ←── 高 8 位 ──→ | ←──────── 低 B 位 ────────→ | ... |
2
                  tophash               bucketIndex

1
m[key]
2
    │
3
    ├── 1. 计算 hash(key)，取低 B 位 → 定位桶 bmap[i]
4
    │
5
    ├── 2. 取高 8 位 → tophash
6
    │
7
    ├── 3. 遍历 bmap[i] 的 8 个槽位：
8
    │       ├── tophash 匹配？→ 进一步比较完整 key
9
    │       │     ├── key 相等 → 返回 value
10
    │       │     └── key 不等 → 继续下一个槽位
11
    │       └── tophash 不匹配？→ 继续下一个槽位
12
    │
13
    ├── 4. 8 个槽位均未找到？→ 沿 overflow 指针进入溢出桶，重复步骤 3
14
    │
15
    └── 5. 所有溢出桶均遍历完 → 返回零值

1
m[key] = value
2
    │
3
    ├── 1. 计算 hash(key) → bucketIndex + tophash
4
    │
5
    ├── 2. 遍历桶及其溢出链：
6
    │       ├── 找到相同 key → 原地更新 value → 返回
7
    │       └── 发现空槽位 → 记录位置
8
    │
9
    ├── 3. 若 key 不存在：
10
    │       ├── 写入空槽位（tophash + key + value）
11
    │       ├── count++
12
    │       └── 检查是否需要扩容
13
    │
14
    └── 4. 若桶链已满（无空槽位）：
15
            └── 挂载新的溢出桶 → 写入

1
delete(m, key)
2
    │
3
    ├── 1. 定位桶 + tophash
4
    ├── 2. 找到 key
5
    │       ├── 清除 key, value（写零值）
6
    │       └── tophash 设为 emptyRest 或 emptyOne
7
    └── 3. key 不存在 → 空操作返回

1
负载因子 = count / 2^B  >  6.5

1
扩容前 (B=2, 4个桶)           扩容后 (B=3, 8个桶)
2
┌───┬───┬───┬───┐            ┌───┬───┬───┬───┬───┬───┬───┬───┐
3
│ 0 │ 1 │ 2 │ 3 │            │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
4
└───┴───┴───┴───┘            └───┴───┴───┴───┴───┴───┴───┴───┘
5
      桶 1 的数据                     ←─ 桶 1 ─→  ←─ 桶 5 ─→
6
      (haB=0 部分)                    (haB=0)      (haB=1)

1
// src/runtime/map.go（简化）
2
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
3
    if B > 15 { B = 15 }
4
    return noverflow >= uint16(1)<<(B&15)
5
}

1
触发扩容
2
    │
3
    ├── 1. 分配新桶数组 → buckets
4
    │      旧桶数组 → oldbuckets
5
    │      nevacuate = 0
6
    │
7
    ├── 2. 每次 map 读写操作时"顺手"搬迁 1~2 个旧桶
8
    │      nevacuate++
9
    │
10
    ├── 3. 读写路由（搬迁期间）：
11
    │       ┌─ 增/改 (insert/update)：直接写入新桶
12
    │       ├─ 删 (delete)：double-check 双桶
13
    │       └─ 查 (lookup)：先找旧桶，再找新桶
14
    │
15
    └── 4. 全部搬迁完成 → oldbuckets = nil → GC 回收旧内存

1
// src/runtime/map.go（简化）
2

3
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
4
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
5

6
    // 遍历旧桶及其溢出链上所有元素
7
    for ; b != nil; b = b.overflow(t) {
8
        for i := 0; i < bucketCnt; i++ {
9
            // 取出 key, value
10
            // 重新计算 hash → 确定在新桶数组中的位置
11
            // 写入新桶
12
        }
13
    }
14
}

1
一次性搬迁 vs 渐进式搬迁
2

3
一次性：STW 期间搬迁 100 万个元素 → 数百毫秒卡顿
4
渐进式：每次操作搬 1~2 个桶 → 搬迁开销均摊到 O(n) 次操作中 → 无感

1
// 两个 goroutine 同时操作同一个 map
2
go func() { m["a"] = 1 }()  // 写
3
go func() { _ = m["b"] }     // 读
4
// → fatal error: concurrent map read and map write
5
// → 进程直接崩溃，无法 recover

1
// ✓ 方案一：sync.RWMutex 保护（最通用）
2
type SafeMap struct {
3
    mu sync.RWMutex
4
    m  map[string]int
5
}
6

7
// ✓ 方案二：sync.Map（特定场景，见第 8 节）
8

9
// ✓ 方案三：单 goroutine 操作 + channel 通信

1
// ❌ 编译错误：cannot take the address of m["key"]
2
_ = &m["key"]

1
type T struct { Data int }
2
m := make(map[string]*T)
3
m["key"] = &T{Data: 42}
4
ptr := m["key"]  // ptr 本身是拷贝，但指向的 T 不会随 map 搬迁而变

1
// 插入 100 万个元素 → 桶数组扩容到很大
2
// delete 全部元素 → count=0，但桶数组依然占用大量内存
3
// clear(m)       → count=0，同上

1
// ✓ 重建 map 释放底层内存
2
oldMap := largeCache
3
newMap := make(map[string]ValueType, len(oldMap))
4
for k, v := range oldMap {
5
    newMap[k] = v
6
}
7
largeCache = nil       // 旧的大桶数组 → GC 回收
8
largeCache = newMap    // 新 map 紧凑，无空闲槽位

1
// ✓ 合法
2
m1 := map[struct{ X, Y int }]string{}
3
m2 := map[[3]int]string{}
4

5
// ✗ 不合法（编译错误）
6
m3 := map[[]int]string{}
7
m4 := map[map[string]int]string{}

1
m := make(map[string]*MyStruct)
2
m["a"] = &MyStruct{}

1
┌──────────────────────────────────────────────────────────────────┐
2
│                          Map 总览                                 │
3
├──────────────────────────────────────────────────────────────────┤
4
│                                                                  │
5
│   hmap                                                           │
6
│   ┌──────────────────────────────────────────────────────┐       │
7
│   │ count, B=2, hash0, flags                             │       │
8
│   │ buckets ───┐           oldbuckets ─── nil (正常)     │       │
9
│   │ nevacuate  │                     (扩容时指向旧桶)     │       │
10
│   └────────────┼─────────────────────────────────────────┘       │
11
│                │                                                  │
12
│         buckets (2^B = 4 个桶)                                    │
13
│         ┌──────┬──────┬──────┬──────┐                             │
14
│         │bmap 0│bmap 1│bmap 2│bmap 3│                             │
15
│         └──┬───┴──────┴──┬───┴──────┘                             │
16
│            │             │                                        │
17
│    每个 bmap:              overflow 链                            │
18
│    ┌─────────────────────────┐                                    │
19
│    │ tophash[8] (8×1B)      │  装满后→┌──────────┐               │
20
│    │ keys[8]   (紧凑排列)    │         │overflow  │               │
21
│    │ values[8] (紧凑排列)    │         │  bmap    │→...           │
22
│    │ overflow  →─────────────┼────────→└──────────┘               │
23
│    └─────────────────────────┘                                    │
24
│                                                                  │
25
│    扩容: 负载因子>6.5 → 翻倍(B+1)  │  溢出桶过多 → 等量重排       │
26
│    搬迁: 渐进式 — 每次读写顺手搬 1~2 个旧桶                        │
27
│                                                                  │
28
└──────────────────────────────────────────────────────────────────┘