golang系列之-map

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

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

当前go版本：1.23

数据结构

todo：文章图片待补充

1
2
3
4
5
6
7
8
9
10
11
12
13
// 
// hmap -> oldbuckets
//      -> buckets         -> bmap0(8个key/value对) 
//                         -> bmap1 -> overflow0(bmapX) -> overflow1(bmapZ)
//                         -> ...  
//                         -> bmapM -> overflow0(bmapY)
//                         -> bmapN
//
//      -> extra.overflow  -> bmapX(pre-alloc)
//                         -> bmapY(pre-alloc)
//                         -> ...
//                         -> bmapZ(new-alloc)
//

map的数据结构如下所示

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
// src/runtime/map.go
type hmap struct {
    count     int              // 元素数量-key/value对
    flags     uint8            // 1-iter正在使用buckets字段 2-iter正在使用oldbuckets字段 4-正在写入 8-同等大小扩容
    B         uint8            // buckets数量=(loadFactor * 2^B)
    noverflow uint16           // 统计溢出buckets的数量，当B大于15时不是精确值
    hash0     uint32           // 哈希种子，计算hash用
    buckets    unsafe.Pointer  // buckets数组
    oldbuckets unsafe.Pointer  // 旧buckets数组，扩容时用
    nevacuate  uintptr         // 下一个未疏散的bucket索引
    clearSeq   uint64          // 执行过多少次clear
    extra *mapextra            // 可选字段，不是每个map都需要，同时也需要为gc考虑
}

// key/value都不是指针才会使用下面几个字段
type mapextra struct {
    overflow    *[]*bmap       // 溢出buckets，buckets链接使用
    oldoverflow *[]*bmap       // 溢出buckets，oldbuckets链接使用，扩容时
    nextOverflow *bmap         // 下一个可用/未使用overflow的索引
}

// bucket结构，可存储8个key/value对及其他数据，编译时自动补充其余结构，真实结构如下
//    A "bucket" is a "struct" {
//          tophash [abi.MapBucketCount]uint8  // hash的高8位
//          keys [abi.MapBucketCount]keyType   // 所有key
//          elems [abi.MapBucketCount]elemType // 所有value
//          overflow *bucket // 下一个溢出桶指针
//        }
// 详细可见MapBucketType函数（src/cmd/compile/internal/reflectdata/reflect.go）
type bmap struct {
    // abi.MapBucketCount=8
    // 0-默认状态 1-已删除 2-疏散到x 3-疏散到y 4-不需要疏散 5-guard xyz(>5)-正常tophash值
    // 状态转移如下：
    // 0/xyz -> 2/3/4 => 如果所有bucket都疏散完毕，会一次性清空释放
    // 0/xyz -> 1 删除 => 如果idx+1的状态是0，则向前寻找状态为1数据并改为0
    tophash [abi.MapBucketCount]uint8
}

上面数据结构中中比较关键的是

  • hmap - header部份，var变量存储的也是这部份
  • buckets - 指向一片连续内存区域，bucket数组
  • bmap - bucket的具体实现，可以存储8个key/value对，尾部overflow是溢出bucket的指针

初始化

map的初始化方式有两种

  1. 使用字面量创建map
  2. 使用关键字make创建
1
2
3
4
5
6
7
8
// 字面量
var v1 = map[int]int{1: 1, 2: 2, 3: 3}
fmt.Println(v1)

// make关键字
var v2 = make(map[int]int)
v2[4] = 4
fmt.Println(v2)

字面量

字面量初始化调用的是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
// src/runtime/map.go
func makemap(t *maptype, hint int, h *hmap) *hmap {
    // 1. mem（连续内存区域大小） = 元素类型占用大小(type_size)*数量(hint)
    // 2. overflow（是否溢出） = !(type_size|hint < 4GB or type_size=0 or hint > uint_max/type_size)
    mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
    if overflow || mem > maxAlloc {
        hint = 0
    }

    // initialize Hmap
    if h == nil {
        h = new(hmap)
    }
    h.hash0 = uint32(rand())

    // 计算B的大小
    // hint <= 8 ？=> B = 0
    B := uint8(0)
    // 数据量大于8且已经超过80%的饱和度
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B
    
    // B!=0则申请内存创建buckets和overflow
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

// 数量超过8且超到80%的饱和度（13/16 => 81.25%）
func overLoadFactor(count int, B uint8) bool {
    // 数量 > 8 and 数量 > (13*2^B/2)
    return count > abi.MapBucketCount && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// buckets、overflow等字段初始化
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b) // 2^b
    nbuckets := base

    // 大于等于2^4=16个元素时，多准备b-4个bucket用于overflow
    // 比如b=4时，共有16个元素，极端情况下都放在同一个bucket，那么需要一个额外的overflow
    if b >= 4 {
        nbuckets += bucketShift(b - 4)
        sz := t.Bucket.Size_ * nbuckets
        up := roundupsize(sz, !t.Bucket.Pointers()) // 按tcmalloc规则向上取整
        if up != sz {
            nbuckets = up / t.Bucket.Size_
        }
    }

    // 新map
    if dirtyalloc == nil {
        buckets = newarray(t.Bucket, int(nbuckets))
    } else {
        // 清理dirtyalloc，一般用于mapclear
        buckets = dirtyalloc
        size := t.Bucket.Size_ * nbuckets
        if t.Bucket.Pointers() {
            memclrHasPointers(buckets, size)
        } else {
            memclrNoHeapPointers(buckets, size)
        }
    }

    // 有overflow，计算nextOverflow指针
    if base != nbuckets {
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))
        last.setoverflow(t, (*bmap)(buckets)) // 防止nil pointer，将其弄成环形
    }
    return buckets, nextOverflow
}

大概的逻辑如下

  1. 新生成hmap
  2. 初始状态修改
    • hash种子初始化
    • 计算B，如果hint<=8则B为0
  3. 如果B!=0，初始化buckets数组

注意

  1. hint超过BUCKETSIZE则放置在heap，否则放在stack
  2. key与value最大为128个字节，超过这个值则会转成指针

B的计算示例如下

1
2
3
4
5
6
7
for i := range 50 {
    b := uint8(0)
    for overLoadFactor(i, b) {
        b++
    }
    fmt.Printf("hint=%d; b=%d\n", i, b)
}

输出结果如下

hint B bucket count capacity
[0,8] 0 1 8
[9,13] 1 2 16
[14,26] 2 4 32
[27,52] 3 8 64
… … … …

loadFactorNum=13是一个关键数据，右边界=13*2^(B-1)

读写操作

索引访问

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

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

当仅接受一个参数时，底层使用mapaccess1

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
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 未初始化/为空
    if h == nil || h.count == 0 {
        if err := mapKeyError(t, key); err != nil {
            panic(err) // see issue 23734
        }
        return unsafe.Pointer(&zeroVal[0])
    }
    // 有goroutine在写入，不允许
    if h.flags&hashWriting != 0 {
        fatal("concurrent map read and map write")
    }
    // 计算哈希值
    hash := t.Hasher(key, uintptr(h.hash0))
    // 2^b-1
    m := bucketMask(h.B)
    // 计算并移动指针指向目标bucket
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))
    // oldbuckets不为nil，扩容中
    if c := h.oldbuckets; c != nil {
        // 不是同等大小扩容，mask丢弃一位
        if !h.sameSizeGrow() {
            m >>= 1
        }
        // 同上，计算并移动指针指向目标bucket，这里是oldbuckets
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))
        // 是否已疏散，否，数据还在原位
        if !evacuated(oldb) {
            b = oldb
        }
    }
    // 获取hash高8位，优化查找
    top := tophash(hash)
    // 进入循环
bucketloop:
    // 扫描正常桶以及溢出桶
    for ; b != nil; b = b.overflow(t) {
        // 每个桶可存储8个数据，一个个比对tophash
        for i := uintptr(0); i < abi.MapBucketCount; i++ {
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {
                    // index后面的索引位置都为空，退出循环
                    break bucketloop
                }
                // 不是目标数据，继续比对下一个
                continue
            }
            // 计算key索引 = 8+i*key_size
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
            // bucket的key是指针
            if t.IndirectKey() {
                k = *((*unsafe.Pointer)(k))
            }
            // 两个key相等
            if t.Key.Equal(key, k) {
                // 计算value索引 = 8+8*key_size+i*value_size
                e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
                // bucket的value是指针
                if t.IndirectElem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return e
            }
        }
    }
    // 没找到，返回0值
    return unsafe.Pointer(&zeroVal[0])
}

当接受两个参数时，底层使用mapaccess2，其与mapaccess1只有返回值的不同

1
2
3
4
5
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // ...
    // mapaccess2与mapaccess1基本一致，只是返回值不同
    return unsafe.Pointer(&zeroVal[0]), false
}

这里补充两个用到的函数注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 是否已疏散
func evacuated(b *bmap) bool {
    h := b.tophash[0]
    // 如果第一个tophash的值在(1,5)之间，说明这个bucket已经疏散了
    return h > emptyOne && h < minTopHash
}

func tophash(hash uintptr) uint8 {
    // 获取hash的高8位
    top := uint8(hash >> (goarch.PtrSize*8 - 8))
    // 异常处理，加上偏移值minTopHash=5，否则容易与预设值冲突导致误判
    if top < minTopHash {
        top += minTopHash
    }
    return top
}

遍历访问

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

当使用for range遍历整个map时，依赖hiter、mapiterinit、mapiternext实现该操作，大概过程如下

  1. 调用mapiterinit创建hiter
  2. 纪录指定map的状态信息
    • 复制指定map的状态属性
    • 用随机数计算出一个bucket的索引和offset，用来无序化输出
    • 返回第一个key/value对
  3. 调用mapiternext，获取并存储第一个key/value地址
  4. 上层函数继续调用mapiternext，获取并存储下一个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
// src/runtime/map.go
// 纪录指定map状态
type hiter struct {
    key         unsafe.Pointer // key，为nil时表示结束
    elem        unsafe.Pointer // value
    t           *maptype       // 类型
    h           *hmap          // header
    buckets     unsafe.Pointer // bucket指针
    bptr        *bmap          // 当前bucket指针
    overflow    *[]*bmap       // 指向overflow
    oldoverflow *[]*bmap       // 指向oldoverflow
    startBucket uintptr        // 初始bucket索引 -> head
    offset      uint8          // 初始偏移-用于tophash索引匹配
    wrapped     bool           // rand_idx -> max_idx(7) -> min_idx(0) -> rand_idx
    B           uint8          // h.B
    i           uint8          // tophash索引
    bucket      uintptr        // 当前bucket索引 -> curr
    checkBucket uintptr        // 扩容中且未疏散指定bucket
}

// 创建hiter
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    it.t = t
    // 未初始化/为空
    if h == nil || h.count == 0 {
        return
    }

    // iter大小异常？
    if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
        throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
    }
    // 指向map
    it.h = h

    // 复制map当前属性
    it.B = h.B
    it.buckets = h.buckets
    if !t.Bucket.Pointers() {
        h.createOverflow()
        it.overflow = h.extra.overflow
        it.oldoverflow = h.extra.oldoverflow
    }

    // 计算一个随机的bucket索引以及offset作为扫描的开始地址
    r := uintptr(rand())
    // 取低B位->bucket索引
    it.startBucket = r & bucketMask(h.B)
    // 丢掉低B位后再取低3位作为offset
    it.offset = uint8(r >> h.B & (abi.MapBucketCount - 1))

    // curr指向head
    it.bucket = it.startBucket

    // 多个iter
    if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
        atomic.Or8(&h.flags, iterator|oldIterator)
    }

    mapiternext(it)
}

func mapiternext(it *hiter) {
    // 指向map
    h := it.h
    // 有goroutine在写入，不允许
    if h.flags&hashWriting != 0 {
        fatal("concurrent map iteration and map write")
    }
    t := it.t
    // curr索引
    bucket := it.bucket
    // nil-初始值（第一次访问的时候）
    b := it.bptr
    // 0-初始值（第一次访问的时候）
    i := it.i
    // 0-初始值（第一次访问的时候）
    checkBucket := it.checkBucket

next:
    // 开始/结束时
    if b == nil {
        // 回到了最初的位置，终止
        if bucket == it.startBucket && it.wrapped {
            it.key = nil // 表示终止
            it.elem = nil
            return
        }
        // 如果是扩容时创建的iter
        if h.growing() && it.B == h.B {
            // 先看oldbuckets
            oldbucket := bucket & it.h.oldbucketmask()
            b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
            // 还没疏散
            if !evacuated(b) {
                checkBucket = bucket
            } else {
                // 已疏散
                b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
                checkBucket = noCheck
            }
        } else {
            // 没有发生扩容或者扩容前创建的iter
            b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
            checkBucket = noCheck
        }
        // 指针继续指向下一个bucket
        bucket++
        if bucket == bucketShift(it.B) {
            bucket = 0
            it.wrapped = true
        }
        // tophash索引回到0
        i = 0
    }
    // bucket以及overflow逐个元素扫描
    for ; i < abi.MapBucketCount; i++ {
        // 因为有offset的原因，offi => offset -> 7 -> 0 -> offset
        offi := (i + it.offset) & (abi.MapBucketCount - 1)
        // 该位置全新或已删除或已疏散
        if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
            continue
        }
        // 计算key索引 = 8+i*key_size
        k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.KeySize))
        if t.IndirectKey() {
            k = *((*unsafe.Pointer)(k))
        }
        // 计算value索引 = 8+8*key_size+i*value_size
        e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize))
        // 双倍扩容且未疏散
        if checkBucket != noCheck && !h.sameSizeGrow() {
            if t.ReflexiveKey() || t.Key.Equal(k, k) {
                hash := t.Hasher(k, uintptr(h.hash0))
                // iter以新index为准，如果疏散的目的index与新index不同，跳过
                if hash&bucketMask(it.B) != checkBucket {
                    continue
                }
            } else {
                // NaN判断，同上，checkBucket最高位与tophash最低位比较，不相等则跳过，一切以新index为准
                if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
                    continue
                }
            }
        }
        // 前面已经排除了空值
        // 未疏散 or key!=key（NaN）
        if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
            !(t.ReflexiveKey() || t.Key.Equal(k, k)) {
            // NaN无法被更新/删除，无需再判断是否为nil
            it.key = k
            if t.IndirectElem() {
                e = *((*unsafe.Pointer)(e))
            }
            it.elem = e
        } else {
            // 已疏散 用mapaccessK获取key/value
            rk, re := mapaccessK(t, h, k)
            if rk == nil {
                continue // key has been deleted
            }
            it.key = rk
            it.elem = re
        }
        // 保存iter状态
        it.bucket = bucket
        if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
            it.bptr = b
        }
        it.i = i + 1
        it.checkBucket = checkBucket
        return
    }
    // 扫描overflow
    b = b.overflow(t)
    i = 0
    goto next
}

// 扩容时，根据key从新的bucket数组获取key/value地址
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
    // 未初始化/为空
    if h == nil || h.count == 0 {
        return nil, nil
    }
    // 计算哈希值
    hash := t.Hasher(key, uintptr(h.hash0))
    // 2^b-1
    m := bucketMask(h.B)
    // 计算并移动指针指向目标bucket
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))
    // oldbuckets不为nil，扩容中
    if c := h.oldbuckets; c != nil {
        // 不是同等大小扩容，mask丢弃一位
        if !h.sameSizeGrow() {
            m >>= 1
        }
        // 同上，计算并移动指针指向目标bucket，这里是oldbuckets
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))
        // 是否已疏散，否，数据还在原位
        if !evacuated(oldb) {
            b = oldb
        }
    }
    // 获取hash高8位，优化查找
    top := tophash(hash)
bucketloop:
    // 扫描正常桶以及溢出桶
    for ; b != nil; b = b.overflow(t) {
        // 每个桶可存储8个数据，一个个比对tophash
        for i := uintptr(0); i < abi.MapBucketCount; i++ {
            if b.tophash[i] != top {
                // 当前位置以及后面位置都没有数据了，退出循环
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                // 不是目标数据，继续比对下一个
                continue
            }
            // 计算key索引 = 8+i*key_size
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
            if t.IndirectKey() {
                k = *((*unsafe.Pointer)(k))
            }
            // 两个key相等
            if t.Key.Equal(key, k) {
                // 计算value索引 = 8+8*key_size+i*value_size
                e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
                if t.IndirectElem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return k, e
            }
        }
    }
    return nil, nil
}

写入

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

v1["hello"] = "world"

系统调用mapassign实现map的赋值操作，大概逻辑如下

  1. 确保map已经初始化
  2. 计算key的hash值
  3. 判断是否需要扩容？是，则先扩容
  4. 算出目标bucket的位置
  5. 判断是否在扩容中？是，则疏散旧bucket
  6. 扫描整个目标bucket，包括overflow，找到可写入的位置
  7. 返回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
// 根据key查找value并获得指向value的指针
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 为nil，未初始化
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    // 有goroutine在写入，不允许
    if h.flags&hashWriting != 0 {
        fatal("concurrent map writes")
    }
    // 计算哈希值
    hash := t.Hasher(key, uintptr(h.hash0))

    // 设置flag，防止同时写入
    h.flags ^= hashWriting

    // 初始化时B=0，延迟
    if h.buckets == nil {
        h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1)
    }

again:
    // 获取低B位hash值，用于计算桶索引
    bucket := hash & bucketMask(h.B)
    // oldbuckets不为nil，即为扩容中
    if h.growing() {
        // 疏散指定bucket
        growWork(t, h, bucket)
    }
    // 计算并移动指针指向目标bucket
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
    // 获取hash高8位，优化查找
    top := tophash(hash)

    var inserti *uint8 // tophash索引
    var insertk unsafe.Pointer // key索引
    var elem unsafe.Pointer // value索引
bucketloop:
    // 扫描正常桶以及溢出桶
    for {
        // 每个桶可存储8个数据，一个个比对hash
        for i := uintptr(0); i < abi.MapBucketCount; i++ {
            // 1. 没找到key
            if b.tophash[i] != top {
                // 该位置全新或已删除 and index还没找到 -> 找到一个空的位置
                if isEmpty(b.tophash[i]) && inserti == nil {
                    inserti = &b.tophash[i]
                    // 计算key索引 = 8+i*key_size
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
                    // 计算value索引 = 8+8*key_size+i*value_size
                    elem = add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
                }
                // 按上面的顺序来说，后面基本都是0，因此执行上面代码后，到这里就可以break了
                if b.tophash[i] == emptyRest {
                    // index后面的索引位置都为空，退出循环
                    break bucketloop
                }
                // 当前位置不为空，寻找下一个可写入位置
                continue
            }
            // 2. 找到一个key，至少tophash是相等的
            // 计算key索引 = 8+i*key_size
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
            // bucket的key是指针
            if t.IndirectKey() {
                k = *((*unsafe.Pointer)(k))
            }
            // tophash相等但key值不相等，继续寻找下一个
            if !t.Key.Equal(key, k) {
                continue
            }
            // 指针？数据需要更新？
            if t.NeedKeyUpdate() {
                typedmemmove(t.Key, k, key)
            }
            // 计算value索引 = 8+8*key_size+i*value_size
            elem = add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
            goto done
        }
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

    // 非扩容状态，但已经达到80%的饱和度或者数据非常稀疏
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        // 扩容
        hashGrow(t, h)
        // 扩容后，重新找位置
        goto again
    }

    // 全满了，没有位置了
    if inserti == nil {
        // 从预申请获取或直接创建新的bucket，作为overflow bucket
        newb := h.newoverflow(t, b)
        // overflow第一个位置
        inserti = &newb.tophash[0]
        // 同上
        insertk = add(unsafe.Pointer(newb), dataOffset)
        // 同上
        elem = add(insertk, abi.MapBucketCount*uintptr(t.KeySize))
    }

    // 写入数据
    if t.IndirectKey() {
        kmem := newobject(t.Key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.IndirectElem() {
        vmem := newobject(t.Elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    // 把key拷贝到哈希表的key里
    typedmemmove(t.Key, insertk, key)
    // tophash更新
    *inserti = top
    // 总数量更新
    h.count++

done:
    // flag被修改了，异常
    if h.flags&hashWriting == 0 {
        fatal("concurrent map writes")
    }
    // 移除修改标记
    h.flags &^= hashWriting
    if t.IndirectElem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    // 返回value位置的指针，上层代码会更新value
    return elem
}

// 疏散旧bucket
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // todo ？ 保证当前是一次全新的扩容？
    evacuate(t, h, bucket&h.oldbucketmask())

    // 扩容中
    if h.growing() {
        // 疏散
        evacuate(t, h, h.nevacuate)
    }
}

// 疏散用，纪录bucket信息
type evacDst struct {
    b *bmap          // bucket指针
    i int            // tophash地址
    k unsafe.Pointer // key地址
    e unsafe.Pointer // value地址
}

// 疏散旧bucket
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    // 计算并移动指针指向目标bucket，这里是oldbuckets
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
    // 2^(b-1) -> oldbucket+1
    newbit := h.noldbuckets()
    // 如果tophash[0]的值不在在(1,5)之间
    if !evacuated(b) {
        // 将新的buckets分为x和y两部份
        var xy [2]evacDst
        // 低地址部份
        x := &xy[0]
        x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize)))
        x.k = add(unsafe.Pointer(x.b), dataOffset)
        x.e = add(x.k, abi.MapBucketCount*uintptr(t.KeySize))

        // 如果是双倍扩容
        if !h.sameSizeGrow() {
            // 高地址部份
            y := &xy[1]
            y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize)))
            y.k = add(unsafe.Pointer(y.b), dataOffset)
            y.e = add(y.k, abi.MapBucketCount*uintptr(t.KeySize))
        }

        // 扫描正常桶以及溢出桶，这里是oldbuckets
        for ; b != nil; b = b.overflow(t) {
            // key基地址
            k := add(unsafe.Pointer(b), dataOffset)
            // value基地址
            e := add(k, abi.MapBucketCount*uintptr(t.KeySize))
            // 每个桶可存储8个数据，搬空所有
            for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) {
                top := b.tophash[i]
                // 该位置全新或已删除
                if isEmpty(top) {
                    // 设置为4-不需要疏散
                    b.tophash[i] = evacuatedEmpty
                    continue
                }
                // 不为0，但小于5，异常
                if top < minTopHash {
                    throw("bad map state")
                }
                // 不为0，还未疏散
                k2 := k
                if t.IndirectKey() {
                    k2 = *((*unsafe.Pointer)(k2))
                }
                var useY uint8
                if !h.sameSizeGrow() {
                    // 计算hash值
                    hash := t.Hasher(k2, uintptr(h.hash0))

                    // 有goroutine在遍历新的buckets
                    if h.flags&iterator != 0 && !t.ReflexiveKey() && !t.Key.Equal(k2, k2) {
                        // 浮点数，NaN != NaN，无法判断，拿top的最低位判断应该放在哪里
                        useY = top & 1
                        top = tophash(hash)
                    } else {
                        // 根据hash&B判断是否要放在高地址部份
                        if hash&newbit != 0 {
                            useY = 1
                        }
                    }
                }

                // 异常数值？
                if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
                    throw("bad evacuatedN")
                }

                // 设置为2或3
                b.tophash[i] = evacuatedX + useY
                // 疏散的目标地址
                dst := &xy[useY]

                // 溢出了
                if dst.i == abi.MapBucketCount {
                    // 链接overflow并使用第一个地址
                    dst.b = h.newoverflow(t, dst.b)
                    dst.i = 0
                    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
                    dst.e = add(dst.k, abi.MapBucketCount*uintptr(t.KeySize))
                }
                dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top
                if t.IndirectKey() {
                    *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
                } else {
                    typedmemmove(t.Key, dst.k, k) // copy elem
                }
                if t.IndirectElem() {
                    *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
                } else {
                    typedmemmove(t.Elem, dst.e, e)
                }
                dst.i++
                dst.k = add(dst.k, uintptr(t.KeySize))
                dst.e = add(dst.e, uintptr(t.ValueSize))
            }
        }
        // 旧的bucket已经清空且无iter在使用
        if h.flags&oldIterator == 0 && t.Bucket.Pointers() {
            b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))
            ptr := add(b, dataOffset)
            n := uintptr(t.BucketSize) - dataOffset
            // 把key/value数据全部清空，方便gc做？
            memclrHasPointers(ptr, n)
        }
    }

    // 惰性清理函数，不会每次都触发，只有oldbucket索引刚好跟nevacuate值相等才行
    // [0 1 2 3]共四个bucket
    // 当疏散了idx=2的bucket，此时nevacuate=0，不触发
    // 当疏散了idx=0的bucket时，与nevacuate相等，触发，将nevacuate指向1
    // 当nevacuate=4时，说明疏散了所有bucket，清理掉buckets数组，更新状态
    if oldbucket == h.nevacuate {
        advanceEvacuationMark(h, t, newbit)
    }
}

// 是否疏散完毕，是=>清理oldbucket
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
    // 指向下一个bucket，不管有没有清理
    h.nevacuate++

    // guard，实际保证能nevacuate<newbit即可
    stop := h.nevacuate + 1024
    if stop > newbit {
        stop = newbit
    }
    // nevacuate指向下一个未清理的bucket索引
    for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
        h.nevacuate++
    }
    // 全部疏散完毕
    if h.nevacuate == newbit {
        // 删除oldbuckets
        h.oldbuckets = nil
        // 删除oldoverflow
        if h.extra != nil {
            h.extra.oldoverflow = nil
        }
        // 取消sameSizeGrow标记？
        h.flags &^= sameSizeGrow
    }
}

// 申请一个新的overflow bucket
func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
    var ovf *bmap
    // 有预申请的overflow直接使用
    if h.extra != nil && h.extra.nextOverflow != nil {
        ovf = h.extra.nextOverflow
        // next为nil，说明申请的overflow还有很多
        if ovf.overflow(t) == nil {
            // 写上next指针，不然下一次没法用
            h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.BucketSize)))
        } else {
            // 用完了，bucket的overflow指针清空
            ovf.setoverflow(t, nil)
            h.extra.nextOverflow = nil
        }
    } else {
        // 没有预申请或者用完了预申请的
        ovf = (*bmap)(newobject(t.Bucket))
    }
    // noverflow counter调整
    // <16时noverflow是个精确值
    // >=16时noverflow指数级衰减
    h.incrnoverflow()
    // 不包含指针
    if !t.Bucket.Pointers() {
        // 确保extra跟overflow已初始化
        h.createOverflow()
        // 追加到末尾，超过容量还是会触发slice扩容
        *h.extra.overflow = append(*h.extra.overflow, ovf)
    }
    // bucket的overflow指针指向ovf
    b.setoverflow(t, ovf)
    return ovf
}

扩容

当map的元素数量超过8且达到80%的饱和度时，会触发扩容，扩容函数为hashGrow。

注意：hashGrow只负责扩容，不负责疏散oldbucket，只有每次调用mapassign时才会去疏散旧的bucket

大概逻辑如下

  1. 判断是双倍扩容还是同等大小扩容
  2. 将buckets数组搬到oldbuckets
  3. 更新hmap状态
  4. 有overflow？搬到oldoverflow并更新extra状态
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
// 只管扩容，下一次写的时候才疏散对应的bucket
func hashGrow(t *maptype, h *hmap) {
    // 判断是双倍扩容还是同等大小扩容
    bigger := uint8(1)
    // 未达到80%的饱和度，同等大小扩容
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    // 迁移旧的buckets
    oldbuckets := h.buckets
    // 创建新的buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

    // 清除iterator/oldIterator标记
    flags := h.flags &^ (iterator | oldIterator)
    // 加上oldIterator标记？
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }

    // 更新状态
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0

    // 处理overflow
    if h.extra != nil && h.extra.overflow != nil {
        // 异常状态
        if h.extra.oldoverflow != nil {
            throw("oldoverflow is not nil")
        }
        h.extra.oldoverflow = h.extra.overflow
        h.extra.overflow = nil
    }
    if nextOverflow != nil {
        if h.extra == nil {
            h.extra = new(mapextra)
        }
        h.extra.nextOverflow = nextOverflow
    }
}

删除

1
delete(v1, "hello")

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

  1. 计算hash值，找到目标bucket
  2. 是否在扩容中？是，则疏散旧bucket
  3. 对比tophash和key，找到value的地址，清空tophash、key、value
  4. idx+1位置的tophash都是0-默认值？从idx开始往前扫描，将所有tophash=emptyOne改成0
  5. 更新map状态
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
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    // 未初始化/为空
    if h == nil || h.count == 0 {
        if err := mapKeyError(t, key); err != nil {
            panic(err) // see issue 23734
        }
        return
    }
    // 有goroutine在写入，不允许
    if h.flags&hashWriting != 0 {
        fatal("concurrent map writes")
    }
    // 计算哈希值
    hash := t.Hasher(key, uintptr(h.hash0))

    // 设置flag，防止同时写入
    h.flags ^= hashWriting

    // 获取低B位hash值，用于计算桶索引
    bucket := hash & bucketMask(h.B)
    // oldbuckets不为nil，即为扩容中
    if h.growing() {
        // 疏散指定bucket
        growWork(t, h, bucket)
    }
    // 计算并移动指针指向目标bucket
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
    bOrig := b
    // 获取hash高8位，优化查找
    top := tophash(hash)
search:
    // 扫描正常桶以及溢出桶
    for ; b != nil; b = b.overflow(t) {
        // 每个桶可存储8个数据，一个个比对hash
        for i := uintptr(0); i < abi.MapBucketCount; i++ {
            // 1. 没找到key
            if b.tophash[i] != top {
                // 后面基本都是0，到这里就可以break了
                if b.tophash[i] == emptyRest {
                    break search
                }
                continue
            }
            // 2. 找到一个key，至少tophash是相等的
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
            k2 := k
            if t.IndirectKey() {
                k2 = *((*unsafe.Pointer)(k2))
            }
            // tophash相等但key值不相等，继续寻找下一个
            if !t.Key.Equal(key, k2) {
                continue
            }
            // Only clear key if there are pointers in it.
            if t.IndirectKey() {
                *(*unsafe.Pointer)(k) = nil
            } else if t.Key.Pointers() {
                memclrHasPointers(k, t.Key.Size_)
            }
            e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
            if t.IndirectElem() {
                *(*unsafe.Pointer)(e) = nil
            } else if t.Elem.Pointers() {
                memclrHasPointers(e, t.Elem.Size_)
            } else {
                memclrNoHeapPointers(e, t.Elem.Size_)
            }
            // 删除了一个数据
            b.tophash[i] = emptyOne
            // index=7，指向了bucket最后一个数据
            if i == abi.MapBucketCount-1 {
                // 还不是最终的数据，不处理
                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
                    goto notLast
                }
            } else {
                // index<7 且 后续的元素也不为空，不处理
                if b.tophash[i+1] != emptyRest {
                    goto notLast
                }
            }
            // 将当前以及前面tophash=emptyOne的tophash设置为0-默认值
            for {
                b.tophash[i] = emptyRest
                if i == 0 {
                    if b == bOrig {
                        break // beginning of initial bucket, we're done.
                    }
                    // Find previous bucket, continue at its last entry.
                    c := b
                    for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
                    }
                    i = abi.MapBucketCount - 1
                } else {
                    i--
                }
                if b.tophash[i] != emptyOne {
                    break
                }
            }
        notLast:
            h.count--
            // Reset the hash seed to make it more difficult for attackers to
            // repeatedly trigger hash collisions. See issue 25237.
            if h.count == 0 {
                h.hash0 = uint32(rand())
            }
            break search
        }
    }

    // 异常状态
    if h.flags&hashWriting == 0 {
        fatal("concurrent map writes")
    }
    // 清除标记
    h.flags &^= hashWriting
}

清空

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

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

  1. 循环将每一个bucket的tophash都设置为0，包括oldbuckets
  2. 重置map的所有状态、seed等
  3. 调用makeBucketArray，清理所有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
func mapclear(t *maptype, h *hmap) {
    // 未初始化/为空
    if h == nil || h.count == 0 {
        return
    }
    // 有goroutine在写入，不允许
    if h.flags&hashWriting != 0 {
        fatal("concurrent map writes")
    }

    // 设置flag，防止同时写入
    h.flags ^= hashWriting

    // Mark buckets empty, so existing iterators can be terminated, see issue #59411.
    markBucketsEmpty := func(bucket unsafe.Pointer, mask uintptr) {
        for i := uintptr(0); i <= mask; i++ {
            b := (*bmap)(add(bucket, i*uintptr(t.BucketSize)))
            for ; b != nil; b = b.overflow(t) {
                for i := uintptr(0); i < abi.MapBucketCount; i++ {
                    b.tophash[i] = emptyRest
                }
            }
        }
    }
    // 2^b-1
    markBucketsEmpty(h.buckets, bucketMask(h.B))
    if oldBuckets := h.oldbuckets; oldBuckets != nil {
        markBucketsEmpty(oldBuckets, h.oldbucketmask())
    }

    // 剩下的没什么好说的
    h.flags &^= sameSizeGrow
    h.oldbuckets = nil
    h.nevacuate = 0
    h.noverflow = 0
    h.count = 0

    // Reset the hash seed to make it more difficult for attackers to
    // repeatedly trigger hash collisions. See issue 25237.
    h.hash0 = uint32(rand())

    // Keep the mapextra allocation but clear any extra information.
    if h.extra != nil {
        *h.extra = mapextra{}
    }

    // makeBucketArray clears the memory pointed to by h.buckets
    // and recovers any overflow buckets by generating them
    // as if h.buckets was newly alloced.
    _, nextOverflow := makeBucketArray(t, h.B, h.buckets)
    if nextOverflow != nil {
        // If overflow buckets are created then h.extra
        // will have been allocated during initial bucket creation.
        h.extra.nextOverflow = nextOverflow
    }

    if h.flags&hashWriting == 0 {
        fatal("concurrent map writes")
    }
    h.flags &^= hashWriting
}

克隆

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)

go 1.21增加了maps.Clone用于克隆整个map数据，系统调用mapclone2实现该操作，大概逻辑如下

  1. 创建目标哈希表dst，复制源哈希表src的状态等相关数据
  2. 复制src的数据到dst
    • 如果B=0且key/value非指针，直接赋值一个bucket即可，复制完毕直接退出
    • 如果dst.B=src.B，1:1复制bucket数组
    • 如果dst.B<=src.B，直接看代码吧
  3. src是否在扩容中？是，则复制src的oldbucket数据
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
func mapclone2(t *maptype, src *hmap) *hmap {
    // 数据量
    hint := src.count
    // 已经达到80%的饱和度
    if overLoadFactor(hint, src.B) {
        // 13*2^B/2 (why？)
        hint = int(loadFactorNum * (bucketShift(src.B) / loadFactorDen))
    }
    dst := makemap(t, hint, nil)
    // 共用hash seed
    dst.hash0 = src.hash0
    dst.nevacuate = 0
    // flags不需要拷贝

    // 数量为0，不处理
    if src.count == 0 {
        return dst
    }

    // 有goroutine在写入，不允许
    if src.flags&hashWriting != 0 {
        fatal("concurrent map clone and map write")
    }

    // b=0 and key跟value非指针
    if src.B == 0 && !(t.IndirectKey() && t.NeedKeyUpdate()) && !t.IndirectElem() {
        // Quick copy for small maps.
        dst.buckets = newobject(t.Bucket)
        dst.count = src.count
        typedmemmove(t.Bucket, dst.buckets, src.buckets)
        return dst
    }

    // b=0 key或value为指针类型
    if dst.B == 0 {
        dst.buckets = newobject(t.Bucket)
    }

    // dst.B <= src.B
    dstArraySize := int(bucketShift(dst.B))
    srcArraySize := int(bucketShift(src.B))
    for i := 0; i < dstArraySize; i++ {
        // dst bucket指针
        dstBmap := (*bmap)(add(dst.buckets, uintptr(i*int(t.BucketSize))))
        pos := 0
        for j := 0; j < srcArraySize; j += dstArraySize {
            // src bucket指针
            // 如果dst.B = src.B，1:1复制，否则多余部份wrapped写到dst前面几个bucket
            srcBmap := (*bmap)(add(src.buckets, uintptr((i+j)*int(t.BucketSize))))
            for srcBmap != nil {
                dstBmap, pos = moveToBmap(t, dst, dstBmap, pos, srcBmap)
                // 包括overflow
                srcBmap = srcBmap.overflow(t)
            }
        }
    }

    // 非扩容
    if src.oldbuckets == nil {
        return dst
    }

    // 下面全是跟oldbuckets相关的
    oldB := src.B
    srcOldbuckets := src.oldbuckets
    if !src.sameSizeGrow() {
        oldB--
    }
    oldSrcArraySize := int(bucketShift(oldB))

    for i := 0; i < oldSrcArraySize; i++ {
        srcBmap := (*bmap)(add(srcOldbuckets, uintptr(i*int(t.BucketSize))))
        // 已疏散
        if evacuated(srcBmap) {
            continue
        }

        // oldB比dst的B还要更大，按dst的B取hash的低位作为bucket索引
        // dst.B <= src.B and dst.B <= (src.B-1)
        if oldB >= dst.B { // main bucket bits in dst is less than oldB bits in src
            // src.oldbuckets => dst.buckets
            // 索引按dst.B取低位
            dstBmap := (*bmap)(add(dst.buckets, (uintptr(i)&bucketMask(dst.B))*uintptr(t.BucketSize)))
            for dstBmap.overflow(t) != nil {
                dstBmap = dstBmap.overflow(t)
            }
            pos := 0
            for srcBmap != nil {
                dstBmap, pos = moveToBmap(t, dst, dstBmap, pos, srcBmap)
                srcBmap = srcBmap.overflow(t)
            }
            continue
        }

        // oldB < dst.B (说明dst.B == src.B ?)
        for srcBmap != nil {
            // oldbuckets分成x/y两个部份疏散
            for i := uintptr(0); i < abi.MapBucketCount; i++ {
                // 该位置全新或已删除
                if isEmpty(srcBmap.tophash[i]) {
                    continue
                }

                // // 有goroutine在写入，不允许
                if src.flags&hashWriting != 0 {
                    fatal("concurrent map clone and map write")
                }

                srcK := add(unsafe.Pointer(srcBmap), dataOffset+i*uintptr(t.KeySize))
                if t.IndirectKey() {
                    srcK = *((*unsafe.Pointer)(srcK))
                }

                srcEle := add(unsafe.Pointer(srcBmap), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
                if t.IndirectElem() {
                    srcEle = *((*unsafe.Pointer)(srcEle))
                }
                // 找到key在dst的位置，然后复制数据
                dstEle := mapassign(t, dst, srcK)
                typedmemmove(t.Elem, dstEle, srcEle)
            }
            srcBmap = srcBmap.overflow(t)
        }
    }
    return dst
}

func moveToBmap(t *maptype, h *hmap, dst *bmap, pos int, src *bmap) (*bmap, int) {
    // src的bucket数据复制到dst的bucket，overflow在上一层做处理
    for i := 0; i < abi.MapBucketCount; i++ {
        // src-该位置全新或已删除
        if isEmpty(src.tophash[i]) {
            continue
        }

        // 索引 0-7
        for ; pos < abi.MapBucketCount; pos++ {
            // dst-找到一个可写入的位置
            if isEmpty(dst.tophash[pos]) {
                break
            }
        }

        // dst写满了，加一个overflow bucket
        if pos == abi.MapBucketCount {
            dst = h.newoverflow(t, dst)
            pos = 0
        }

        srcK := add(unsafe.Pointer(src), dataOffset+uintptr(i)*uintptr(t.KeySize))
        srcEle := add(unsafe.Pointer(src), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(i)*uintptr(t.ValueSize))
        dstK := add(unsafe.Pointer(dst), dataOffset+uintptr(pos)*uintptr(t.KeySize))
        dstEle := add(unsafe.Pointer(dst), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(pos)*uintptr(t.ValueSize))

        // 复制tophash
        dst.tophash[pos] = src.tophash[i]
        // 复制key
        if t.IndirectKey() {
            srcK = *(*unsafe.Pointer)(srcK)
            if t.NeedKeyUpdate() {
                kStore := newobject(t.Key)
                typedmemmove(t.Key, kStore, srcK)
                srcK = kStore
            }
            // Note: if NeedKeyUpdate is false, then the memory
            // used to store the key is immutable, so we can share
            // it between the original map and its clone.
            *(*unsafe.Pointer)(dstK) = srcK
        } else {
            typedmemmove(t.Key, dstK, srcK)
        }
        // 复制value
        if t.IndirectElem() {
            srcEle = *(*unsafe.Pointer)(srcEle)
            eStore := newobject(t.Elem)
            typedmemmove(t.Elem, eStore, srcEle)
            *(*unsafe.Pointer)(dstEle) = eStore
        } else {
            typedmemmove(t.Elem, dstEle, srcEle)
        }
        // counter更新
        pos++
        h.count++
    }
    return dst, pos
}

参考文档

3.3 哈希表
Go Maps Explained: How Key-Value Pairs Are Actually Stored
GopherCon 2016: Keith Randall - Inside the Map Implementation
Inside the Map Implementation - Gophercon
Arrays, Slices and Maps in Go
Maps and memory leaks