golang系列之-swiss map

发表于 更新于 本文字数： 8.3k 阅读时长 ≈ 30 分钟

map/哈希表，是golang常用的数据结构之一，也充当set数据结构的存在，相对slice要复杂很多。从1.24开始，swiss table替代noswiss成为默认实现，swiss与noswiss区别在于，swiss使用开放地址法，noswiss使用拉链法

当前go版本：1.24

swiss map的开关放在文件src/internal/buildcfg/exp.go的函数ParseGOEXPERIMENT中

数据结构

todo：文章图片待补充

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// table-groups是二维数组，算上slot的话是三维
// 
// map_header -> table1 -> group1(8个slot)
//                      -> group2
//                      ...
//                      -> group127
// 
//            -> table2
//            -> ...
//            -> tableN
//
// 当hint<=8时，map_header直接指向一个group，全量扫描操作
// 当hint>8 and hint<=1024*7/8时，一个table，2~128个group
// 当hint>1024*7/8时，多个table，多个group
// 
// hash高B位 - 用于定位table
// h1-hash高57位 - 用于定位group
// h2-hash低7位 - 用于匹配hash，类似tophash

核心数据结构包括Map、table、groupsReference、groupReference，具体如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// src/internal/runtime/maps/map.go
type Map struct {
    used uint64            // 已用slot，当数据量<=8时用来替换table的used使用
    seed uintptr           // 哈希函数种子
    dirPtr unsafe.Pointer  // table数组指针/group指针
    dirLen int             // table数组大小
    globalDepth uint8      // log2(dirLen)（相当于旧版的B）
    globalShift uint8      // 64-globalDepth，高B位用做table的索引
    writing uint8          // 是否正在写入，乐观锁
    clearSeq uint64        // 执行过多少次clear，扩容时，获取数据判断用
}

// src/internal/runtime/maps/table.go
type table struct {
    used uint16            // 已用slot，最多能写入1024*7/8=896个slot
    capacity uint16        // slot容量 <=1024（由hint算出，2的乘方向上取整）
    growthLeft uint16      // 可用slot，与used相反，初始值最大为896
    localDepth uint8       // >globalDepth？分裂/遍历时使用
    index int              // 上层directory数组中的index（-1-过期，作用类似localDepth）
    groups groupsReference // group数组，8个slot为一组，最多1024/8=128组
}

// src/internal/runtime/maps/group.go
type groupsReference struct {
    data unsafe.Pointer    // group数组，8个slot为一组，具体结构看下方
    lengthMask uint64      // 长度固定为2^N，因此mask=2^N-1
}

type groupReference struct {
    // 结构如下
    //
    // type group struct {
    //     ctrls ctrlGroup                    // 8个8bit的ctrl，共三种状态
    //     slots [abi.SwissMapGroupSlots]slot // 8个slot(key/value对)
    // }
    // 
    // 三种状态如下：
    //      empty: 1 0 0 0 0 0 0 0
    //    deleted: 1 1 1 1 1 1 1 0
    //       full: 0 h h h h h h h  // h represents the H2 hash bits
    //
    // type slot struct {
    //     key  typ.Key  // 键
    //     elem typ.Elem // 值
    // }
    data unsafe.Pointer // ctrls数组+slots数组
    // 内存布局如下（C语言开发者真的很喜欢这种内存布局啊）
    // | ctrls         | slots         |
    // |ctrl7|...|ctrl0|slot0|...|slot7|
}

初始化

字面量

字面量初始化调用的是maplit，具体看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// src/cmd/compile/internal/walk/complit.go
func maplit(n *ir.CompLitExpr, m ir.Node, init *ir.Nodes) {
    args := []ir.Node{ir.TypeNode(n.Type()), ir.NewInt(base.Pos, n.Len+int64(len(n.List)))}
    a := typecheck.Expr(ir.NewCallExpr(base.Pos, ir.OMAKE, nil, args)).(*ir.MakeExpr)
    a.RType = n.RType
    a.SetEsc(n.Esc())
    appendWalkStmt(init, ir.NewAssignStmt(base.Pos, m, a))

    entries := n.List

    for _, r := range entries {
        r := r.(*ir.KeyExpr)
        if !isStaticCompositeLiteral(r.Key) || !isStaticCompositeLiteral(r.Value) {
            base.Fatalf("maplit: entry is not a literal: %v", r)
        }
    }

    if len(entries) > 25 {
        // ...
        // loop adding structure elements to map
        // for i = 0; i < len(vstatk); i++ {
        //    map[vstatk[i]] = vstate[i]
        // }
        // ...
        return
    }

    // ...
}

其中，如果小于等于25个元素，直接赋值

1
2
3
4
hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

如果，大于25个元素，分key/value两组，使用for循环进行赋值

1
2
3
for i = 0; i < len(vstatk); i++ {
    map[vstatk[i]] = vstate[i]
}

关键字

当使用make关键字初始化map时，调用的是makemap，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
// src/internal/runtime/maps/map.go
func makemap(t *abi.SwissMapType, hint int, m *maps.Map) *maps.Map {
    if hint < 0 {
        hint = 0
    }

    return maps.NewMap(t, uintptr(hint), m, maxAlloc)
}

func NewMap(mt *abi.SwissMapType, hint uintptr, m *Map, maxAlloc uintptr) *Map {
    if m == nil {
        m = new(Map)
    }

    // 哈希种子
    m.seed = uintptr(rand())

    // hint<=8
    if hint <= abi.SwissMapGroupSlots {
        return m
    }

    // capacity = hint*8/7 => 每个group最多容纳7个slot，不能直接按hint计算group数量
    targetCapacity := (hint * abi.SwissMapGroupSlots) / maxAvgGroupLoad
    if targetCapacity < hint { // overflow
        return m // return an empty map.
    }

    // dirSize = (capacity+1024-1)/1024 => table数量 => 一个table=128个group=1024个slot
    dirSize := (uint64(targetCapacity) + maxTableCapacity - 1) / maxTableCapacity
    // 2的乘方向上取整，如dirSize=40? => dirSize=64
    dirSize, overflow := alignUpPow2(dirSize)
    // overflow?
    if overflow || dirSize > uint64(math.MaxUintptr) {
        return m // return an empty map.
    }

    // Reject hints that are obviously too large.
    // ngroup = dirSize*1024
    groups, overflow := math.MulUintptr(uintptr(dirSize), maxTableCapacity)
    if overflow {
        return m // return an empty map.
    } else {
        // ngroup*GroupSize overflow?
        mem, overflow := math.MulUintptr(groups, mt.GroupSize)
        if overflow || mem > maxAlloc {
            return m // return an empty map.
        }
    }

    // globalDepth = 二进制数dirSize末尾有多少个0 => 2^globalDepth=dirSize
    m.globalDepth = uint8(sys.TrailingZeros64(dirSize))
    // globalShift = 64-globalDepth
    m.globalShift = depthToShift(m.globalDepth)

    directory := make([]*table, dirSize)

    // 创建table
    for i := range directory {
        // (type, a/b, i, d)
        // capacity = a/b <= 1024
        directory[i] = newTable(mt, uint64(targetCapacity)/dirSize, i, m.globalDepth)
    }

    m.dirPtr = unsafe.Pointer(&directory[0])
    m.dirLen = len(directory) // 为什么不能直接用dirSize？

    return m
}

// src/internal/runtime/maps/table.go
// 创建table
func newTable(typ *abi.SwissMapType, capacity uint64, index int, localDepth uint8) *table {
    // capacity最小值为8
    if capacity < abi.SwissMapGroupSlots {
        capacity = abi.SwissMapGroupSlots
    }

    t := &table{
        index:      index,      // 上层directory数组中的index
        localDepth: localDepth, // <= globalDepth
    }

    // >1024 => 异常
    if capacity > maxTableCapacity {
        panic("initial table capacity too large")
    }

    // 2的乘方向上取整
    capacity, overflow := alignUpPow2(capacity)
    if overflow {
        panic("rounded-up capacity overflows uint64")
    }

    // 创建groups
    t.reset(typ, uint16(capacity))

    return t
}

// 主要职责 => 创建groups
func (t *table) reset(typ *abi.SwissMapType, capacity uint16) {
    // 8个slot为一组，最多1024/8=128组
    groupCount := uint64(capacity) / abi.SwissMapGroupSlots
    // 创建groups
    t.groups = newGroups(typ, groupCount)
    t.capacity = capacity
    // 根据capacity重置growthLeft字段
    t.resetGrowthLeft()

    // 相当于for i, g := range t.groups 
    for i := uint64(0); i <= t.groups.lengthMask; i++ {
        g := t.groups.group(typ, i)
        // 每组有8个slot，每个slot对应的ctrl都设置为empty => 0b10000000
        g.ctrls().setEmpty()
    }
}

// 重置table的growthLeft字段
func (t *table) resetGrowthLeft() {
    var growthLeft uint16
    if t.capacity == 0 {
        // 1. capacity不能为0
        // No real reason to support zero capacity table, since an
        // empty Map simply won't have a table.
        panic("table must have positive capacity")
    } else if t.capacity <= abi.SwissMapGroupSlots {
        // 2. capacity <= 8
        // If the map fits in a single group then we're able to fill all of
        // the slots except 1 (an empty slot is needed to terminate find
        // operations).
        growthLeft = t.capacity - 1
    } else {
        // 3. capacity > 8
        // capacity*7 < capacity？
        if t.capacity*maxAvgGroupLoad < t.capacity {
            panic("overflow")
        }
        // growthLeft = capacity*7/8
        growthLeft = (t.capacity * maxAvgGroupLoad) / abi.SwissMapGroupSlots
    }
    t.growthLeft = growthLeft
}

// src/internal/runtime/maps/group.go
// length => 2^N
func newGroups(typ *abi.SwissMapType, length uint64) groupsReference {
    return groupsReference{
        data:       newarray(typ.Group, int(length)), // 申请一片内存
        lengthMask: length - 1, // 2^N-1
    }
}

// group=8*ctrl+8*slot
func (g *groupsReference) group(typ *abi.SwissMapType, i uint64) groupReference {
    offset := uintptr(i) * typ.GroupSize

    return groupReference{
        data: unsafe.Pointer(uintptr(g.data) + offset),
    }
}

相对旧版，新版的逻辑看起来会复杂一些，大概的逻辑如下

  1. 如果hint的数量不超过8，生成map header返回
  2. 如果hint的数量超过8
    • 新版map只能容纳7/8的数据量，因此需要根据公式hint*8/7重新计算容量
    • 根据容量计算table数量、group数量，基本都是2的乘方向上取整
    • 生成table数组、group数组
    • map header、table、group等参数初始化

globalDepth、globalShift一部份数据示例如下

dirSize(10) dirSize(2) globalDepth globalShift
1 0001 0 64
2 0010 1 63
4 0100 2 62
8 1000 3 61

其他：

  1. table数量、group数量固定为2的乘方
  2. table最大容量=1024个slot=128个group
  3. group最大容量=8个slot

读写操作

swiss table使用二次探测法法用于定位group，而终止扫描依赖group的ctrls字段，只要该字段中有一个处于empty状态，立即终止扫描，具体通过probeSeq实现

使用的二次探测法公式为：p(i) := (i^2 + i)/2 + hash (mod mask+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// quadratic probing - 二次探测法
type probeSeq struct {
    mask   uint64 // groups数组的索引的最大值=2^N-1
    offset uint64 // groups数组索引（取hash的低N位）
    index  uint64 // 扫描计数器
}

func makeProbeSeq(hash uintptr, mask uint64) probeSeq {
    return probeSeq{
        mask:   mask,
        offset: uint64(hash) & mask,
        index:  0,
    }
}

func (s probeSeq) next() probeSeq {
    s.index++
    // 从offset的位置开始循环groups数组扫描
    // 保证不超过groups数组的最大索引
    // p(i) := (i^2 + i)/2 + hash (mod mask+1)
    s.offset = (s.offset + s.index) & s.mask
    return s
}

probeSeq的使用示例如下，其中offset是group的定位索引，看起来还是比较均匀的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
seq := makeProbeSeq(12345678, 7)
for i := 0; i < 10; i++ {
    fmt.Printf("%+v\n", seq)
    seq = seq.next()
}

// 输出：
// {mask:7 offset:6 index:0}
// {mask:7 offset:7 index:1}
// {mask:7 offset:1 index:2}
// {mask:7 offset:4 index:3}
// {mask:7 offset:0 index:4}
// {mask:7 offset:5 index:5}
// {mask:7 offset:3 index:6}
// {mask:7 offset:2 index:7}
// {mask:7 offset:2 index:8}
// {mask:7 offset:3 index:9}

索引访问

使用索引获取map的数值有两种

  1. 仅接受一个参数
  2. 接受两个参数
1
2
3
4
// 仅接受一个参数
v := h[key]
// 接受两个参数
v, ok := h[key]

当仅接受一个参数时，底层使用runtime_mapaccess1，当接受两个参数时，底层使用runtime_mapaccess2，其与runtime_mapaccess1只有返回值的不同

这里的runtime_mapaccess1逻辑与Get方法相似，因此只介绍maps包的接口方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
// src/internal/runtime/maps/runtime_swiss.go
func runtime_mapaccess1(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
    // ... 
}

func runtime_mapaccess2(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // ...
}

// src/internal/runtime/maps/map.go
func (m *Map) Get(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, bool) {
    return m.getWithoutKey(typ, key)
}

// 返回key、value指针
func (m *Map) getWithKey(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
    // 无数据
    if m.Used() == 0 {
        return nil, nil, false
    }

    // 其他goroutine在写入，异常
    if m.writing != 0 {
        fatal("concurrent map read and map write")
    }

    // 计算key的哈希值
    hash := typ.Hasher(key, m.seed)

    // 只有一个table一个group，数据量<8
    if m.dirLen == 0 {
        return m.getWithKeySmall(typ, hash, key)
    }

    // 计算table的索引，取hash高B位
    idx := m.directoryIndex(hash)
    // 找到table再找group最后找slot
    return m.directoryAt(idx).getWithKey(typ, hash, key)
}

// 返回value指针
func (m *Map) getWithoutKey(typ *abi.SwissMapType, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // 无数据
    if m.Used() == 0 {
        return nil, false
    }

    // 其他goroutine在写入，异常
    if m.writing != 0 {
        fatal("concurrent map read and map write")
    }

    // 计算key的哈希值
    hash := typ.Hasher(key, m.seed)

    // 只有一个table一个group，数据量<8
    if m.dirLen == 0 {
        _, elem, ok := m.getWithKeySmall(typ, hash, key)
        return elem, ok
    }

    // 计算table的索引，取hash高B位
    idx := m.directoryIndex(hash)
    // 找到table再找group最后找slot
    return m.directoryAt(idx).getWithoutKey(typ, hash, key)
}

// 数据量小于等于8时调用
func (m *Map) getWithKeySmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
    // 只有一个table一个group
    // table.groups不是第一个字段也能cast？
    g := groupReference{
        data: m.dirPtr,
    }

    // 获取哈希值低7位
    h2 := uint8(h2(hash))
    // data的前64位为ctrls
    ctrls := *g.ctrls()

    // 8个slot
    // |ctrl7|...|ctrl0|slot0|...|slot7|
    for i := uintptr(0); i < abi.SwissMapGroupSlots; i++ {
        // ctrls从后往前扫描，但i从0开始
        c := uint8(ctrls)
        ctrls >>= 8
        if c != h2 {
            continue
        }

        // slot从前往后扫描
        // key
        slotKey := g.key(typ, i)
        if typ.IndirectKey() {
            slotKey = *((*unsafe.Pointer)(slotKey))
        }

        // value
        if typ.Key.Equal(key, slotKey) {
            slotElem := g.elem(typ, i)
            if typ.IndirectElem() {
                slotElem = *((*unsafe.Pointer)(slotElem))
            }
            return slotKey, slotElem, true
        }
    }

    return nil, nil, false
}

// 以下是table相关

func (t *table) getWithKey(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer, bool) {
    // probeSeq
    seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
    // 二次探测查找
    for ; ; seq = seq.next() {
        // 找到指定group
        g := t.groups.group(typ, seq.offset)

        // 一次性比对8个ctrl，将成功匹配的ctrl挑出来
        match := g.ctrls().matchH2(h2(hash))

        // match不为0，至少找到一个（假阳性）
        // |ctrl7|...|ctrl0|slot0|...|slot7|
        for match != 0 {
            // 第一个非0的ctrl的索引，根据match的末尾有多少个0算出
            // 看样子同一个i会被用很多次
            i := match.first()

            // key
            slotKey := g.key(typ, i)
            if typ.IndirectKey() {
                slotKey = *((*unsafe.Pointer)(slotKey))
            }
            // value
            if typ.Key.Equal(key, slotKey) {
                slotElem := g.elem(typ, i)
                if typ.IndirectElem() {
                    slotElem = *((*unsafe.Pointer)(slotElem))
                }
                return slotKey, slotElem, true
            }
            // match末尾第一个1将会被置为0
            match = match.removeFirst()
        }

        // 没找到

        // matchEmpty将非empty的ctrl全部置为0，如果8个ctrl都有数据，如full或者deleted状态，那么match=0
        match = g.ctrls().matchEmpty()
        if match != 0 {
            // Finding an empty slot means we've reached the end of
            // the probe sequence.
            return nil, nil, false
        }
    }
}

// 与getWithKey相同，只有返回值不同
func (t *table) getWithoutKey(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // ... 
}

遍历访问

1
2
3
4
var v1 = map[int]int{1: 1, 2: 2, 3: 3}
for key, value := range v1 {
    // ...
}

当使用for range遍历整个map时，依赖Iter数据结构实现该操作，大概过程如下

  1. 创建Iter，纪录map的快照信息、生成随机数作为table、slot的索引偏移
  2. 调用Next方法，获取并存储第一个key/value地址
  3. 上层函数继续调用Next方法，获取并存储下一个key/value地址，或者主动退出循环

注意：如果发生了扩容，iter.tab的index显示是已过时，需要从旧的table获取key，从新的table获取新的key/value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
type Iter struct {
    key  unsafe.Pointer     // key指针 为nil结束遍历
    elem unsafe.Pointer     // value指针
    typ  *abi.SwissMapType  // 类型
    m    *Map               // map指针
    entryOffset uint64      // slot计数器的偏移量（随机）
    dirOffset   uint64      // table索引初始偏移（随机） -> head
    clearSeq uint64         // 执行过多少次clear
    globalDepth uint8       // log2(dirLen)（相当于以前的B）
    dirIdx int              // table索引 -> curr
    tab *table              // table指针，不同dirIdx可以指向同一个tab
    group groupReference    // group指针
    entryIdx uint64         // 整个table的slot计数器 [0,1023]
}

func mapIterStart(t *abi.SwissMapType, m *maps.Map, it *maps.Iter) {
    it.Init(t, m)
    it.Next()
}

func (it *Iter) Init(typ *abi.SwissMapType, m *Map) {
    it.typ = typ

    // 空map
    if m == nil || m.used == 0 {
        return
    }

    // small map
    dirIdx := 0
    var groupSmall groupReference
    // 只有一个table一个group，数据量<8
    if m.dirLen <= 0 {
        // Use dirIdx == -1 as sentinel for small maps.
        dirIdx = -1
        // 直接拿map的dirPtr字段转换
        groupSmall.data = m.dirPtr
    }

    it.m = m
    it.entryOffset = rand()        // slot索引初始偏移
    it.dirOffset = rand()          // table索引初始偏移
    it.globalDepth = m.globalDepth // 2^B个table
    it.dirIdx = dirIdx             // 0-默认 -1-small map
    it.group = groupSmall          // nil-默认 否则 small map
    it.clearSeq = m.clearSeq
}

func mapIterNext(it *maps.Iter) {
    it.Next()
}

func (it *Iter) Next() {
    // 空map，直接终止
    if it.m == nil {
        it.key = nil
        it.elem = nil
        return
    }

    // 其他goroutine在写入，异常
    if it.m.writing != 0 {
        fatal("concurrent map iteration and map write")
        return
    }

    // 1. small map ，单个group
    if it.dirIdx < 0 {
        // 遍历所有slot，从entryOffset开始
        for ; it.entryIdx < abi.SwissMapGroupSlots; it.entryIdx++ {
            k := uintptr(it.entryIdx+it.entryOffset) % abi.SwissMapGroupSlots

            // 删除的或空的slot？跳过（small map删除直接设置为empty）
            if (it.group.ctrls().get(k) & ctrlEmpty) == ctrlEmpty {
                continue
            }

            // key
            key := it.group.key(it.typ, k)
            if it.typ.IndirectKey() {
                key = *((*unsafe.Pointer)(key))
            }

            //
            grown := it.m.dirLen > 0
            var elem unsafe.Pointer
            // 还在扩容中
            if grown {
                var ok bool
                // 从扩容后的map获取
                newKey, newElem, ok := it.m.getWithKey(it.typ, key)
                // 找不到
                if !ok {
                    // key是NaN
                    // NaN无法被update/delete，只能clear，如果很幸运，没有clear过，那么可以从旧的table里拿到数据
                    // 详细可以看grownKeyElem注释
                    if it.clearSeq == it.m.clearSeq && !it.typ.Key.Equal(key, key) {
                        elem = it.group.elem(it.typ, k)
                        if it.typ.IndirectElem() {
                            elem = *((*unsafe.Pointer)(elem))
                        }
                    } else {
                        // 被删除了
                        continue
                    }
                } else {
                    // 按新的key/value为准
                    key = newKey
                    elem = newElem
                }
            } else {
                // 没有扩容
                elem = it.group.elem(it.typ, k)
                if it.typ.IndirectElem() {
                    elem = *((*unsafe.Pointer)(elem))
                }
            }
            // 更新iter，方便下次调用
            it.entryIdx++  // [0,1023]
            it.key = key   // 上层读取数据用
            it.elem = elem // 上层读取数据用
            return
        }

        // 已经扫描完所有slot
        it.key = nil
        it.elem = nil
        return
    }

    // 2. 常规map

    // 如果map在iter的过程中分裂了
    if it.globalDepth != it.m.globalDepth {
        // Consider:
        //
        // Before:
        // - 0: *t1
        // - 1: *t2  <- dirIdx
        //
        // After:
        // - 0: *t1a (split)
        // - 1: *t1b (split)
        // - 2: *t2  <- dirIdx
        // - 3: *t2
        //
        // dirIdx*(2^分裂次数)即可指向正确的table
        // 具体公式如下
        // dirIdx := (it.dirIdx + it.dirOffset) % it.m.dirLen
        // 需要保证结果为正
        orders := it.m.globalDepth - it.globalDepth // 分裂次数
        it.dirIdx <<= orders    // 2^orders
        it.dirOffset <<= orders
        // it.m.dirLen // 调整directory时已经调整了dirLen，这里不需要再处理
        it.globalDepth = it.m.globalDepth
    }

    // 扫描所有table [0,dirLen]，当然nextDirIdx会根据分裂等情况调整table的索引
    for ; it.dirIdx < it.m.dirLen; it.nextDirIdx() {
        // table第一次扫描时
        if it.tab == nil {
            // local dirIdx
            dirIdx := int((uint64(it.dirIdx) + it.dirOffset) & uint64(it.m.dirLen-1))
            // 找到目标table
            newTab := it.m.directoryAt(uintptr(dirIdx))
            // 解决随机dirIdx可能引发的问题
            // 扩容/分裂后，两个dirIdx可能指向同一个table
            if newTab.index != dirIdx {
                diff := dirIdx - newTab.index
                // 调整dirOffset，使其能指向table的index
                it.dirOffset -= uint64(diff)
                // 以table的index为准
                dirIdx = newTab.index
            }
            it.tab = newTab
        }

        
        entryMask := uint64(it.tab.capacity) - 1
        // 全局计数器超过table的容量时，扫描下一个table
        if it.entryIdx > entryMask {
            continue
        }

        // 2.1 Fast path：只判断当前idx指向的ctrl，这要比匹配一组ctrls快

        // slot全局计数器
        entryIdx := (it.entryIdx + it.entryOffset) & entryMask
        // slot局部计数器-按8取模
        slotIdx := uintptr(entryIdx & (abi.SwissMapGroupSlots - 1))

        // slotIdx重新回到0 or 第一次遍历当前table
        if slotIdx == 0 || it.group.data == nil {
            // groupIdx=entryIdx丢弃低3位 => [0,127]
            groupIdx := entryIdx >> abi.SwissMapGroupSlotsBits
            it.group = it.tab.groups.group(it.typ, groupIdx)
        }

        // 到这里，table、group、slot的索引都已经确认了，只判断单个slot即可

        // 当前slot是刚好是有值的，ctrl=full
        if (it.group.ctrls().get(slotIdx) & ctrlEmpty) == 0 {
            key := it.group.key(it.typ, slotIdx)
            if it.typ.IndirectKey() {
                key = *((*unsafe.Pointer)(key))
            }

            grown := it.tab.index == -1
            var elem unsafe.Pointer
            // 扩容中
            if grown {
                // 从新table拿数据，如果拿不到，确认是NaN还是已删除
                newKey, newElem, ok := it.grownKeyElem(key, slotIdx)
                if !ok {
                    // 没找到，走slow path
                    goto next
                } else {
                    key = newKey
                    elem = newElem
                }
            } else {
                // 非扩容
                elem = it.group.elem(it.typ, slotIdx)
                if it.typ.IndirectElem() {
                    elem = *((*unsafe.Pointer)(elem))
                }
            }

            // 纪录key/value
            it.entryIdx++
            it.key = key
            it.elem = elem
            return
        }

    next:
        // 计数器+1
        it.entryIdx++

        // 2.2 Slow path：批量匹配一组ctrl
        // 如果map比较稀疏效率会比较高
        // 如果是中等负载运行效果亦佳，如每个group有3-4个empty的slot
        // 遍历过程可能会发生删除等操作，需要double-check

        var groupMatch bitset
        for it.entryIdx <= entryMask {
            // slot全局计数器
            entryIdx := (it.entryIdx + it.entryOffset) & entryMask
            // slot局部计数器-按8取模
            slotIdx := uintptr(entryIdx & (abi.SwissMapGroupSlots - 1))

            // slotIdx重新回到0 or 第一次遍历当前table
            if slotIdx == 0 || it.group.data == nil {
                // groupIdx=entryIdx丢弃低3位 => [0,127]
                groupIdx := entryIdx >> abi.SwissMapGroupSlotsBits
                it.group = it.tab.groups.group(it.typ, groupIdx)
            }

            // 刚开始 或者 上一轮没找到
            if groupMatch == 0 {
                // 寻找ctrl=full状态的slot
                groupMatch = it.group.ctrls().matchFull()

                if slotIdx != 0 {
                    // 把当前group的idx<slotIdx的ctrl全部置为0，即丢弃掉
                    // 扫描过？or 随机？
                    groupMatch = groupMatch.removeBelow(slotIdx)
                }

                // 没有找到
                if groupMatch == 0 {
                    // 扫描下一个group
                    it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
                    continue
                }

                // 找到一组数据了

                // 取第一个full slot
                i := groupMatch.first()
                // 调整计数器，使其指向当前slot => slotIdx=i
                it.entryIdx += uint64(i - slotIdx)
                // 扫描了table全部数据了，扫描下一个table
                // idx roll over了，这个数据之前已经返回过了
                if it.entryIdx > entryMask {
                    continue
                }
                // 这句源代码应该是写重复了
                entryIdx += uint64(i - slotIdx)
                slotIdx = i
            }

            // key
            key := it.group.key(it.typ, slotIdx)
            if it.typ.IndirectKey() {
                key = *((*unsafe.Pointer)(key))
            }

            grown := it.tab.index == -1
            var elem unsafe.Pointer
            // 扩容/分裂后
            if grown {
                // 从新table拿数据，如果拿不到，确认是NaN还是已删除
                newKey, newElem, ok := it.grownKeyElem(key, slotIdx)
                if !ok {
                    // 没找到
                    // groupMatch末尾第一个1将会被置为0
                    groupMatch = groupMatch.removeFirst()
                    // 当前组的slot扫描完了
                    if groupMatch == 0 {
                        // 指向下一个group开始位置
                        it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
                        continue
                    }

                    // 下一个非空的slot的idx
                    i := groupMatch.first()
                    it.entryIdx += uint64(i - slotIdx)
                    continue
                } else {
                    key = newKey
                    elem = newElem
                }
            } else {
                // 非扩容
                elem = it.group.elem(it.typ, slotIdx)
                if it.typ.IndirectElem() {
                    elem = *((*unsafe.Pointer)(elem))
                }
            }

            // groupMatch末尾第一个1将会被置为0
            groupMatch = groupMatch.removeFirst()
            // 当前组的slot扫描完了
            if groupMatch == 0 {
                // 指向下一个group开始位置
                it.entryIdx += abi.SwissMapGroupSlots - uint64(slotIdx)
            } else {
                // 下一个非空的slot的idx
                i := groupMatch.first()
                it.entryIdx += uint64(i - slotIdx)
            }

            it.key = key
            it.elem = elem
            return
        }

        // Continue to next table.
    }

    // 扫描完所有table，结束
    it.key = nil
    it.elem = nil
    return
}

// 获取下一个dirIdx，原文已经详细介绍了原理，不再赘述
func (it *Iter) nextDirIdx() {
    // Consider this directory:
    //
    // - 0: *t1
    // - 1: *t1
    // - 2: *t2a
    // - 3: *t2b
    //
    // 如果随机的dirIdx指向1，调整为0，上层代码已处理
    // 如果dirIdx指向0，下一个dirIdx指向2，跳过1
    // 如果此时t1分裂了，而我们的tab指向是旧的t1而不是t1a、t1b，依然要指跳过1
    entries := 1 << (it.m.globalDepth - it.tab.localDepth)
    it.dirIdx += entries
    it.tab = nil
    it.group = groupReference{}
    it.entryIdx = 0
}

// 从新table拿数据，如果拿不到，确认是NaN还是已删除
func (it *Iter) grownKeyElem(key unsafe.Pointer, slotIdx uintptr) (unsafe.Pointer, unsafe.Pointer, bool) {
    newKey, newElem, ok := it.m.getWithKey(it.typ, key)
    if !ok {
        // Key has likely been deleted, and
        // should be skipped.
        //
        // One exception is keys that don't
        // compare equal to themselves (e.g.,
        // NaN). These keys cannot be looked
        // up, so getWithKey will fail even if
        // the key exists.
        //
        // However, we are in luck because such
        // keys cannot be updated and they
        // cannot be deleted except with clear.
        // Thus if no clear has occurred, the
        // key/elem must still exist exactly as
        // in the old groups, so we can return
        // them from there.
        //
        // TODO(prattmic): Consider checking
        // clearSeq early. If a clear occurred,
        // Next could always return
        // immediately, as iteration doesn't
        // need to return anything added after
        // clear.
        if it.clearSeq == it.m.clearSeq && !it.typ.Key.Equal(key, key) {
            elem := it.group.elem(it.typ, slotIdx)
            if it.typ.IndirectElem() {
                elem = *((*unsafe.Pointer)(elem))
            }
            return key, elem, true
        }

        // This entry doesn't exist anymore.
        return nil, nil, false
    }

    return newKey, newElem, true
}

写入

1
2
3
var v1 = make(map[string]string)

v1["hello"] = "world"

系统调用runtime_mapassign实现map的赋值操作，其代码逻辑与Put方法相似，大概逻辑如下

  1. 如果是小map，扫描group，找到空位置返回地址
  2. 如果是常规大小的map，根据哈希值找到table，用二次探测法找到合适的group，最后找到空位置返回地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
func runtime_mapassign(typ *abi.SwissMapType, m *Map, key unsafe.Pointer) unsafe.Pointer {
    // ...
}

func (m *Map) Put(typ *abi.SwissMapType, key, elem unsafe.Pointer) {
    slotElem := m.PutSlot(typ, key)
    typedmemmove(typ.Elem, slotElem, elem)
}

// PutSlot returns a pointer to the element slot where an inserted element
// should be written.
//
// PutSlot never returns nil.
func (m *Map) PutSlot(typ *abi.SwissMapType, key unsafe.Pointer) unsafe.Pointer {
    // 其他goroutine在写入，异常
    if m.writing != 0 {
        fatal("concurrent map writes")
    }

    // 计算key的哈希值
    hash := typ.Hasher(key, m.seed)

    // Set writing after calling Hasher, since Hasher may panic, in which
    // case we have not actually done a write.
    m.writing ^= 1 // toggle, see comment on writing

    // 空的，原因有很多，这里初始化一个table一个group
    if m.dirPtr == nil {
        m.growToSmall(typ)
    }

    // small map
    if m.dirLen == 0 {
        // used<8
        if m.used < abi.SwissMapGroupSlots {
            // value指针
            elem := m.putSlotSmall(typ, hash, key)

            // 其他goroutine在写入，异常
            if m.writing == 0 {
                fatal("concurrent map writes")
            }
            // 取消writing标志
            m.writing ^= 1

            return elem
        }

        // used>=8？扩容
        // 单个group到完整的table-groups结构
        m.growToTable(typ)
    }

    // dirLen>0 or used>=8
    for {
        // 计算table的索引，取hash高B位
        idx := m.directoryIndex(hash)
        elem, ok := m.directoryAt(idx).PutSlot(typ, m, hash, key)
        if !ok {
            continue
        }

        // 其他goroutine在写入，异常
        if m.writing == 0 {
            fatal("concurrent map writes")
        }
        // 取消writing标志
        m.writing ^= 1

        return elem
    }
}

// small map初始化group
func (m *Map) growToSmall(typ *abi.SwissMapType) {
    // 创建一个group
    grp := newGroups(typ, 1)
    m.dirPtr = grp.data

    g := groupReference{
        data: m.dirPtr,
    }
    // 每个slot对应的ctrl都设置为empty => 0b10000000
    g.ctrls().setEmpty()
}

// 单个group到完整的table-groups结构
func (m *Map) growToTable(typ *abi.SwissMapType) {
    // 一个table，两个group
    // capacity=16 index=0 localDepth=0
    tab := newTable(typ, 2*abi.SwissMapGroupSlots, 0, 0)

    // 原先的group指针
    g := groupReference{
        data: m.dirPtr,
    }

    // 
    for i := uintptr(0); i < abi.SwissMapGroupSlots; i++ {
        // 空的不处理
        if (g.ctrls().get(i) & ctrlEmpty) == ctrlEmpty {
            // Empty
            continue
        }

        // key地址
        key := g.key(typ, i)
        if typ.IndirectKey() {
            key = *((*unsafe.Pointer)(key))
        }

        // value地址
        elem := g.elem(typ, i)
        if typ.IndirectElem() {
            elem = *((*unsafe.Pointer)(elem))
        }

        // key的hash
        hash := typ.Hasher(key, m.seed)

        tab.uncheckedPutSlot(typ, hash, key, elem)
    }

    // 一个table
    directory := make([]*table, 1)

    directory[0] = tab

    m.dirPtr = unsafe.Pointer(&directory[0])
    m.dirLen = len(directory)

    m.globalDepth = 0 // 2^0=1
    m.globalShift = depthToShift(m.globalDepth) // 64-0
}

// 只有一个table一个group时，或者说只有一个group时
func (m *Map) putSlotSmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) unsafe.Pointer {
    // 直接拿map的dirPtr字段转换
    g := groupReference{
        data: m.dirPtr,
    }

    // 一次性比对8个ctrl，将成功匹配的ctrl挑出来
    match := g.ctrls().matchH2(h2(hash))

    // 已存在（假阳性）
    for match != 0 {
        // 第一个非空的slot
        i := match.first()

        slotKey := g.key(typ, i)
        if typ.IndirectKey() {
            slotKey = *((*unsafe.Pointer)(slotKey))
        }
        if typ.Key.Equal(key, slotKey) {
            if typ.NeedKeyUpdate() {
                typedmemmove(typ.Key, slotKey, key)
            }

            slotElem := g.elem(typ, i)
            if typ.IndirectElem() {
                slotElem = *((*unsafe.Pointer)(slotElem))
            }
            // 返回value的地址
            return slotElem
        }
        // match末尾第一个1将会被置为0
        match = match.removeFirst()
    }

    // 没找到

    // matchEmptyOrDeleted将full状态的ctrl全部置为0，找到empty和deleted的slot
    // small map不能删除slot
    match = g.ctrls().matchEmptyOrDeleted()
    // 8个slot都被使用了
    if match == 0 {
        fatal("small map with no empty slot (concurrent map writes?)")
        return nil
    }

    // 经过上一步，empty跟delete标记的slot都被找出来了
    i := match.first()

    slotKey := g.key(typ, i)
    if typ.IndirectKey() {
        kmem := newobject(typ.Key)
        *(*unsafe.Pointer)(slotKey) = kmem
        slotKey = kmem
    }
    typedmemmove(typ.Key, slotKey, key)

    slotElem := g.elem(typ, i)
    if typ.IndirectElem() {
        emem := newobject(typ.Elem)
        *(*unsafe.Pointer)(slotElem) = emem
        slotElem = emem
    }

    // ctrl状态更新
    g.ctrls().set(i, ctrl(h2(hash)))
    // 计数器更新，small map用的是map结构体的used
    m.used++

    return slotElem
}

// src/internal/runtime/maps/table.go
func (t *table) PutSlot(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // probeSeq
    seq := makeProbeSeq(h1(hash), t.groups.lengthMask)

    // 纪录第一个已删除slot的group指针和slot索引
    var firstDeletedGroup groupReference
    var firstDeletedSlot uintptr

    // 二次探测查找
    for ; ; seq = seq.next() {
        // 找到指定group
        g := t.groups.group(typ, seq.offset)
        // 一次性比对8个ctrl，将成功匹配的ctrl挑出来
        match := g.ctrls().matchH2(h2(hash))

        // match不为0，至少找到一个（假阳性）
        for match != 0 {
            // 第一个非0的ctrl的索引，根据match的末尾有多少个0算出
            // 看样子同一个i会被用很多次
            i := match.first()

            // key
            slotKey := g.key(typ, i)
            if typ.IndirectKey() {
                slotKey = *((*unsafe.Pointer)(slotKey))
            }
            // value
            if typ.Key.Equal(key, slotKey) {
                // 更新key？
                if typ.NeedKeyUpdate() {
                    typedmemmove(typ.Key, slotKey, key)
                }
                // value
                slotElem := g.elem(typ, i)
                if typ.IndirectElem() {
                    slotElem = *((*unsafe.Pointer)(slotElem))
                }
                // debug时开启，忽略
                t.checkInvariants(typ, m)
                return slotElem, true
            }
            // match末尾第一个1将会被置为0
            match = match.removeFirst()
        }

        // 没找到

        // matchEmptyOrDeleted将full状态的ctrl全部置为0，找到empty和deleted的slot
        match = g.ctrls().matchEmptyOrDeleted()
        // 8个slot都被使用了，看是否在其他group
        if match == 0 {
            continue // nothing but filled slots. Keep probing.
        }

        // 有空的或被删除的slot
        i := match.first()
        // 该slot已删除，继续找其他group
        // todo 其他index都是已删除吗？为什么不继续找当前group
        if g.ctrls().get(i) == ctrlDeleted {
            // 纪录group指针和slot的index
            if firstDeletedGroup.data == nil {
                firstDeletedGroup = g
                firstDeletedSlot = i
            }
            continue
        }

        // empty代表探测的末尾，不用再找了

        // If we found a deleted slot along the way, we can
        // replace it without consuming growthLeft.
        if firstDeletedGroup.data != nil {
            g = firstDeletedGroup
            i = firstDeletedSlot
            t.growthLeft++ // will be decremented below to become a no-op.
        }

        // If there is room left to grow, just insert the new entry.
        if t.growthLeft > 0 {
            // key
            slotKey := g.key(typ, i)
            if typ.IndirectKey() {
                kmem := newobject(typ.Key)
                *(*unsafe.Pointer)(slotKey) = kmem
                slotKey = kmem
            }
            typedmemmove(typ.Key, slotKey, key)

            // value
            slotElem := g.elem(typ, i)
            if typ.IndirectElem() {
                emem := newobject(typ.Elem)
                *(*unsafe.Pointer)(slotElem) = emem
                slotElem = emem
            }

            // map/table/group状态更新
            g.ctrls().set(i, ctrl(h2(hash)))
            t.growthLeft--
            t.used++
            m.used++

            // debug时开启，忽略
            t.checkInvariants(typ, m)
            return slotElem, true
        }

        // table扩容，如果超过限制的1024个slot，分裂并更新map
        t.rehash(typ, m)
        return nil, false
    }
}

// 扩容时用，复制旧的table的slot数据到新的table
// 1. growthLeft-- used++
// 2. 不能有已删除的slot
// 3. indirect的key和value可以直接复制，由调用者保证key/value数据不变
func (t *table) uncheckedPutSlot(typ *abi.SwissMapType, hash uintptr, key, elem unsafe.Pointer) {
    // 异常
    if t.growthLeft == 0 {
        panic("invariant failed: growthLeft is unexpectedly 0")
    }

    // probeSeq
    seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
    // 二次探测查找
    for ; ; seq = seq.next() {
        // 找到指定group
        g := t.groups.group(typ, seq.offset)

        // matchEmptyOrDeleted将full状态的ctrl全部置为0，找到empty和deleted的slot
        match := g.ctrls().matchEmptyOrDeleted()
        // match不为0，至少找到一个
        if match != 0 {
            // 第一个非0的ctrl的索引，根据match的末尾有多少个0算出
            i := match.first()

            // 复制key
            slotKey := g.key(typ, i)
            if typ.IndirectKey() {
                *(*unsafe.Pointer)(slotKey) = key
            } else {
                typedmemmove(typ.Key, slotKey, key)
            }

            // 复制value
            slotElem := g.elem(typ, i)
            if typ.IndirectElem() {
                *(*unsafe.Pointer)(slotElem) = elem
            } else {
                typedmemmove(typ.Elem, slotElem, elem)
            }

            // 状态更新
            t.growthLeft--
            t.used++
            g.ctrls().set(i, ctrl(h2(hash)))
            return
        }
    }
}

扩容

map使用growthLeft作为可用的slot大小，该值一般为capacity*7/8，最大值为896。每次写入都会消耗growthLeft，当growthLeft减少到0时，触发扩容，扩容函数为rehash

大概逻辑如下

  1. 如果扩容后到容量没有超过单个table的容量限制
    • 创建双倍容量的新table，将旧table的数据拷贝到新的table
    • dirPtr按指定索引替换掉table指针
  2. 如果扩容后容量超过单个table的容量限制
    • 创建两个容量为1024的table_a和table_b
    • 按哈希值高B+1位疏散slot数据到新的table
    • 疏散完毕后，双倍扩容dirPtr数组
    • 重新调整dirPtr数组指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
// table扩容，如果超过限制的1024个slot，分裂并更新map
func (t *table) rehash(typ *abi.SwissMapType, m *Map) {
    // 双倍容量
    newCapacity := 2 * t.capacity
    // 没有超过单个table的容量限制 -> 扩容
    if newCapacity <= maxTableCapacity {
        t.grow(typ, m, newCapacity)
        return
    }

    // 超过单个table容量限制 -> 分裂
    t.split(typ, m)
}

func (t *table) grow(typ *abi.SwissMapType, m *Map, newCapacity uint16) {
    // 创建table
    newTable := newTable(typ, uint64(newCapacity), t.index, t.localDepth)

    // 走到这里还能等于0？
    if t.capacity > 0 {
        // 遍历所有group
        for i := uint64(0); i <= t.groups.lengthMask; i++ {
            g := t.groups.group(typ, i)
            // 遍历所有slot
            for j := uintptr(0); j < abi.SwissMapGroupSlots; j++ {
                if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
                    // Empty or deleted
                    continue
                }

                // key
                key := g.key(typ, j)
                if typ.IndirectKey() {
                    key = *((*unsafe.Pointer)(key))
                }

                // value
                elem := g.elem(typ, j)
                if typ.IndirectElem() {
                    elem = *((*unsafe.Pointer)(elem))
                }

                // hash
                hash := typ.Hasher(key, m.seed)

                // 复制key和value到newTable
                newTable.uncheckedPutSlot(typ, hash, key, elem)
            }
        }
    }

    // debug时开启，忽略
    newTable.checkInvariants(typ, m)
    // dirPtr指定index关联newTable
    m.replaceTable(newTable)
    // 旧的table标记为过期
    t.index = -1
}

// table分裂
//
//    directory (globalDepth=2)
//    +----+
//    | 00 | --\
//    +----+    +--> table (localDepth=1)
//    | 01 | --/
//    +----+
//    | 10 | ------> table (localDepth=2)
//    +----+
//    | 11 | ------> table (localDepth=2)
//    +----+
func (t *table) split(typ *abi.SwissMapType, m *Map) {
    localDepth := t.localDepth
    localDepth++

    // capacity=1024 index=-1 localDepth=localDepth+1
    // 两个table设置为已过期
    left := newTable(typ, maxTableCapacity, -1, localDepth)
    right := newTable(typ, maxTableCapacity, -1, localDepth)

    // 1<<(64-localDepth) 高(B+1)位所谓索引
    // origin_depth=1 index => [0,1]
    // current_depth=2 index => [0,1,2,3]
    mask := localDepthMask(localDepth)

    // 遍历所有group
    for i := uint64(0); i <= t.groups.lengthMask; i++ {
        g := t.groups.group(typ, i)
        // 遍历所有slot
        for j := uintptr(0); j < abi.SwissMapGroupSlots; j++ {
            if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
                // Empty or deleted
                continue
            }

            // key
            key := g.key(typ, j)
            if typ.IndirectKey() {
                key = *((*unsafe.Pointer)(key))
            }

            // value
            elem := g.elem(typ, j)
            if typ.IndirectElem() {
                elem = *((*unsafe.Pointer)(elem))
            }

            // hash
            hash := typ.Hasher(key, m.seed)
            var newTable *table
            // 按hash新的bit进行分组
            if hash&mask == 0 {
                newTable = left
            } else {
                newTable = right
            }
            // 复制key和value到newTable
            newTable.uncheckedPutSlot(typ, hash, key, elem)
        }
    }

    // 
    m.installTableSplit(t, left, right)
    // 旧的table标记为过期
    t.index = -1
}

// 根据table的index，更新dirPtr数组的指针
func (m *Map) replaceTable(nt *table) {
    // The number of entries that reference the same table doubles for each
    // time the globalDepth grows without the table splitting.
    entries := 1 << (m.globalDepth - nt.localDepth)
    // 有分裂？更新多个dirPtr数组的table指针，没有分裂就会只有一个index
    for i := 0; i < entries; i++ {
        //m.directory[nt.index+i] = nt
        m.directorySet(uintptr(nt.index+i), nt)
    }
}

func (m *Map) installTableSplit(old, left, right *table) {
    // table分裂了，dirPtr数组需要扩容
    // 第一个分裂的table
    if old.localDepth == m.globalDepth {
        // 双倍扩容
        newDir := make([]*table, m.dirLen*2)
        for i := range m.dirLen {
            t := m.directoryAt(uintptr(i))
            // 指向同一个table
            newDir[2*i] = t
            newDir[2*i+1] = t
            // t may already exist in multiple indicies. We should
            // only update t.index once. Since the index must
            // increase, seeing the original index means this must
            // be the first time we've encountered this table.
            if t.index == i {
                t.index = 2 * i
            }
        }
        m.globalDepth++
        m.globalShift--
        m.dirPtr = unsafe.Pointer(&newDir[0])
        m.dirLen = len(newDir)
    }

    // N.B. left and right may still consume multiple indicies if the
    // directory has grown multiple times since old was last split.
    left.index = old.index
    // dirPtr指定index关联newTable
    m.replaceTable(left)

    // 其他table可能分裂多次，导致localDepth远小于globalDepth，无法直接+1
    entries := 1 << (m.globalDepth - left.localDepth)
    right.index = left.index + entries
    // dirPtr指定index关联newTable
    m.replaceTable(right)
}

删除

1
delete(v1, "hello")

当使用关键字delete删除指定key时，调用mapdelete，大概逻辑如下

  1. 如果map的slot数量小于等于8，small map，直接扫描dirPtr指向的group，删除key/value并将对应的ctrl改为empty
  2. 如果map的slot数量大于8，根据hash使用二次探测查找法定位table、group，找到目标slot
    • 如果该group是满数据的，将ctrl改为deleted
    • 如果该group是有空位的，将ctrl改为empty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// src/runtime/map_swiss.go
func mapdelete(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) {
    m.Delete(t, key)
}

// src/internal/runtime/maps/map.go
func (m *Map) Delete(typ *abi.SwissMapType, key unsafe.Pointer) {
    // 空map
    if m == nil || m.Used() == 0 {
        if err := mapKeyError(typ, key); err != nil {
            panic(err) // see issue 23734
        }
        return
    }

    // 其他goroutine在写入，异常
    if m.writing != 0 {
        fatal("concurrent map writes")
    }

    // 计算key的哈希值
    hash := typ.Hasher(key, m.seed)

    // Set writing after calling Hasher, since Hasher may panic, in which
    // case we have not actually done a write.
    m.writing ^= 1 // toggle, see comment on writing

    // small map
    if m.dirLen == 0 {
        m.deleteSmall(typ, hash, key)
    } else {
        // 计算table的索引，取hash高B位
        idx := m.directoryIndex(hash)
        m.directoryAt(idx).Delete(typ, m, hash, key)
    }

    // 删光了？重置hash种子
    if m.used == 0 {
        // Reset the hash seed to make it more difficult for attackers
        // to repeatedly trigger hash collisions. See
        // https://go.dev/issue/25237.
        m.seed = uintptr(rand())
    }

    // 其他goroutine在写入，异常
    if m.writing == 0 {
        fatal("concurrent map writes")
    }
    // 取消writing标志
    m.writing ^= 1
}

// 只有一个table一个group时，或者说只有一个group时
func (m *Map) deleteSmall(typ *abi.SwissMapType, hash uintptr, key unsafe.Pointer) {
    // 直接拿map的dirPtr字段转换
    g := groupReference{
        data: m.dirPtr,
    }

    // 一次性比对8个ctrl，将成功匹配的ctrl挑出来
    match := g.ctrls().matchH2(h2(hash))

    // 找到了（假阳性）
    for match != 0 {
        // 按顺序比对ctrl
        i := match.first()
        slotKey := g.key(typ, i)
        origSlotKey := slotKey
        if typ.IndirectKey() {
            slotKey = *((*unsafe.Pointer)(slotKey))
        }
        // key比对成功
        if typ.Key.Equal(key, slotKey) {
            // 计数器更新，small map用的是map结构体的used
            m.used--

            // key是一个指针，直接置为nil
            if typ.IndirectKey() {
                // Clearing the pointer is sufficient.
                *(*unsafe.Pointer)(origSlotKey) = nil
            } else if typ.Key.Pointers() {
                // key存储的是一个指针
                // Only bother clearing if there are pointers.
                typedmemclr(typ.Key, slotKey)
            }

            slotElem := g.elem(typ, i)
            if typ.IndirectElem() {
                // Clearing the pointer is sufficient.
                *(*unsafe.Pointer)(slotElem) = nil
            } else {
                // Unlike keys, always clear the elem (even if
                // it contains no pointers), as compound
                // assignment operations depend on cleared
                // deleted values. See
                // https://go.dev/issue/25936.
                typedmemclr(typ.Elem, slotElem)
            }

            // 设置为empty而不是deleted
            // We only have 1 group, so it is OK to immediately
            // reuse deleted slots.
            g.ctrls().set(i, ctrlEmpty)
            return
        }
        // match末尾第一个1将会被置为0
        match = match.removeFirst()
    }
}

// src/internal/runtime/maps/table.go
func (t *table) Delete(typ *abi.SwissMapType, m *Map, hash uintptr, key unsafe.Pointer) {
    // probeSeq
    seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
    // 二次探测查找
    for ; ; seq = seq.next() {
        // 找到指定group
        g := t.groups.group(typ, seq.offset)
        // 一次性比对8个ctrl，将成功匹配的ctrl挑出来
        match := g.ctrls().matchH2(h2(hash))

        // 找到了（假阳性）
        for match != 0 {
            // 第一个非0的ctrl的索引，根据match的末尾有多少个0算出
            i := match.first()

            // key
            slotKey := g.key(typ, i)
            origSlotKey := slotKey
            if typ.IndirectKey() {
                slotKey = *((*unsafe.Pointer)(slotKey))
            }

            // key比对成功
            if typ.Key.Equal(key, slotKey) {
                // 计数器更新
                t.used--
                m.used--

                // key是一个指针，直接置为nil
                if typ.IndirectKey() {
                    // Clearing the pointer is sufficient.
                    *(*unsafe.Pointer)(origSlotKey) = nil
                } else if typ.Key.Pointers() {
                    // key存储的是一个指针
                    // Only bothing clear the key if there
                    // are pointers in it.
                    typedmemclr(typ.Key, slotKey)
                }

                // value
                slotElem := g.elem(typ, i)
                if typ.IndirectElem() {
                    // Clearing the pointer is sufficient.
                    *(*unsafe.Pointer)(slotElem) = nil
                } else {
                    // Unlike keys, always clear the elem (even if
                    // it contains no pointers), as compound
                    // assignment operations depend on cleared
                    // deleted values. See
                    // https://go.dev/issue/25936.
                    typedmemclr(typ.Elem, slotElem)
                }

                // matchEmpty将非empty的ctrl全部置为0，如果8个ctrl都有数据，如full或者deleted状态，那么match=0
                // Only a full group can appear in the middle
                // of a probe sequence (a group with at least
                // one empty slot terminates probing). Once a
                // group becomes full, it stays full until
                // rehashing/resizing. So if the group isn't
                // full now, we can simply remove the element.
                // Otherwise, we create a tombstone to mark the
                // slot as deleted.
                if g.ctrls().matchEmpty() != 0 {
                    g.ctrls().set(i, ctrlEmpty)
                    t.growthLeft++
                } else {
                    // tombstone
                    g.ctrls().set(i, ctrlDeleted)
                }

                // debug时开启，忽略
                t.checkInvariants(typ, m)
                return
            }
            // match末尾第一个1将会被置为0
            match = match.removeFirst()
        }

        // 没找到

        // matchEmpty将非empty的ctrl全部置为0，如果8个ctrl都有数据，如full或者deleted状态，那么match=0
        match = g.ctrls().matchEmpty()
        if match != 0 {
            // Finding an empty slot means we've reached the end of
            // the probe sequence.
            return
        }
    }
}

清空

1
2
var v1 = map[int]int{1: 1, 2: 2, 3: 3}
clear(v1)

使用clear清理map的所有元素时，系统调用mapclear进行处理，大概逻辑如下

  1. 如果是small map，直接清理掉group数据
  2. 如果是常规map，遍历table、group清理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// src/runtime/map_swiss.go
func mapclear(t *abi.SwissMapType, m *maps.Map) {
    m.Clear(t)
}

// src/internal/runtime/maps/map.go
func (m *Map) Clear(typ *abi.SwissMapType) {
    // 空map
    if m == nil || m.Used() == 0 {
        return
    }

    // 其他goroutine在写入，异常
    if m.writing != 0 {
        fatal("concurrent map writes")
    }
    m.writing ^= 1 // toggle, see comment on writing

    // small map
    if m.dirLen == 0 {
        m.clearSmall(typ)
    } else {
        var lastTab *table
        // 遍历所有table
        for i := range m.dirLen {
            t := m.directoryAt(uintptr(i))
            // 分裂时，会指向同一个table
            if t == lastTab {
                continue
            }
            // 清理groups、重置table状态
            t.Clear(typ)
            lastTab = t
        }
        // 重置map状态
        m.used = 0
        m.clearSeq++
        // TODO: shrink directory?
    }

    // 重置hash种子
    // Reset the hash seed to make it more difficult for attackers to
    // repeatedly trigger hash collisions. See https://go.dev/issue/25237.
    m.seed = uintptr(rand())

    // 其他goroutine在写入，异常
    if m.writing == 0 {
        fatal("concurrent map writes")
    }
    // 取消writing标志
    m.writing ^= 1
}

func (m *Map) clearSmall(typ *abi.SwissMapType) {
    // 直接拿map的dirPtr字段转换
    g := groupReference{
        data: m.dirPtr,
    }

    typedmemclr(typ.Group, g.data) // slot数据
    g.ctrls().setEmpty() // ctrl状态

    m.used = 0
    m.clearSeq++
}

// src/internal/runtime/maps/table.go
func (t *table) Clear(typ *abi.SwissMapType) {
    // 遍历所有group
    for i := uint64(0); i <= t.groups.lengthMask; i++ {
        g := t.groups.group(typ, i)
        typedmemclr(typ.Group, g.data) // slot数据
        g.ctrls().setEmpty() // ctrl状态
    }

    t.used = 0
    // 根据capacity重置growthLeft字段
    t.resetGrowthLeft()
}

克隆

1
2
3
4
5
6
7
// 以下非克隆，只是复制了header
var v1 = map[int]int{1: 1, 2: 2, 3: 3}
var v2 = v1

// go 1.21
var v1 = map[int]int{1: 1, 2: 2, 3: 3}
var v2 = maps.Clone(v1)

当使用maps.Clone复制数据时，系统使用mapclone2实现该操作，大概逻辑如下大概逻辑如下

  1. 创建一个Iter
  2. 不断调用Next获取数据，写入新的map
1
2
3
4
5
6
7
8
9
10
11
12
// src/runtime/map_swiss.go
func mapclone2(t *abi.SwissMapType, src *maps.Map) *maps.Map {
    dst := makemap(t, int(src.Used()), nil)

    var iter maps.Iter
    iter.Init(t, src)
    for iter.Next(); iter.Key() != nil; iter.Next() {
        dst.Put(t, iter.Key(), iter.Elem())
    }

    return dst
}