map与slice
# 1.数组与切片
# 1.1.差异
slice的底层数据是数组，它描述一个数组片段，两者都可以通过下标访问单个元素。数组是定长的，长度定义后无法修改。Go中的数组并不常见，因为其长度是类型的一部分，限制了它的表达能力。切片则非常灵活，它的类型与长度无关，可以动态扩容。数组是一片连续内存，切片对数组进行封装重新定义结构体，包含：长度、容量、底层数组三部分。// runtime/slice.go type slice struct { array unsafe.Pointer // 元素指针 len int // 长度 cap int // 容量 }1
2
3
4
5
6
# 1.2.示例
package main import "fmt" func main() { slice := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} s1 := slice[2:5] s2 := s1[2:6:7] s2 = append(s2, 100) s2 = append(s2, 200) s1[2] = 20 fmt.Println(s1) fmt.Println(s2) fmt.Println(slice) }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18结果
[2 3 20] [4 5 6 7 100 200] [0 1 2 3 20 5 6 7 100 9]
s1从slice索引2到索引5—左闭右开，长度为3，容量默认到数组结尾，总容量为8。s2从s1的索引2到索引6，容量到索引7—左闭右开，即容量为5。
接着，向
s2尾部追加一个元素100，由于s2的容量刚刚好，会直接追加到s2尾部。这会修改原始数组对应位置的元素，数组和s1均可见。
再次向
s2追加元素200，此时s2由于容量问题会扩容，于是s2会将自身数组扩容并将原来的元素复制到新的位置。扩容时，为了应对后续可能的容量不足问题，s2会将容量扩为2倍，多预留一些buffer。
最后修改
s1索引为2位置的元素，这次只会影响原始数组相应位置的元素，不会作用到s2。
此外，打印
s1的时候，只会打印出s1长度以内的元素，虽然底层数组不止三个元素。
# 1.3.切片扩容
slice追加元素才会引起扩容，追加元素调用的是append函数，append函数参数可变，追加后返回新的slice。Go编译器不允许调用append函数后不使用返回值，元素追加时会向底层数组追加元素，容量超出时slice会迁移到新的内存，新底层数组长度会增加。slice底层数组扩容时遵循一定规律，按照1.18版本区分：- 1.18版本前，
slice容量小于1024时，新slice容量变为2倍；原slice容量超出1024，新slice容量变成原本的1.25倍 - 1.18版本后，
slice容量小于256时，新slice容量变为2倍；原slice容量超出256时，新slice容量newcap = oldcap+(oldcap+3*256)/4
- 1.18版本前，
package main import "fmt" func main() { s := make([]int, 0) oldCap := cap(s) for i := 0; i < 2048; i++ { s = append(s, i) newCap := cap(s) if newCap != oldCap { fmt.Printf("[%d -> %4d] cap = %-4d | after append %-4d cap = %-4d\n", 0, i-1, oldCap, i, newCap) oldCap = newCap } } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20--- 1.18版本前运行结果 [0 -> -1] cap = 0 | after append 0 cap = 1 [0 -> 0] cap = 1 | after append 1 cap = 2 [0 -> 1] cap = 2 | after append 2 cap = 4 [0 -> 3] cap = 4 | after append 4 cap = 8 [0 -> 7] cap = 8 | after append 8 cap = 16 [0 -> 15] cap = 16 | after append 16 cap = 32 [0 -> 31] cap = 32 | after append 32 cap = 64 [0 -> 63] cap = 64 | after append 64 cap = 128 [0 -> 127] cap = 128 | after append 128 cap = 256 [0 -> 255] cap = 256 | after append 256 cap = 512 [0 -> 511] cap = 512 | after append 512 cap = 1024 [0 -> 1023] cap = 1024 | after append 1024 cap = 1280 [0 -> 1279] cap = 1280 | after append 1280 cap = 1696 [0 -> 1695] cap = 1696 | after append 1696 cap = 2304 --- 1.18版本后运行结果 [0 -> -1] cap = 0 | after append 0 cap = 1 [0 -> 0] cap = 1 | after append 1 cap = 2 [0 -> 1] cap = 2 | after append 2 cap = 4 [0 -> 3] cap = 4 | after append 4 cap = 8 [0 -> 7] cap = 8 | after append 8 cap = 16 [0 -> 15] cap = 16 | after append 16 cap = 32 [0 -> 31] cap = 32 | after append 32 cap = 64 [0 -> 63] cap = 64 | after append 64 cap = 128 [0 -> 127] cap = 128 | after append 128 cap = 256 [0 -> 255] cap = 256 | after append 256 cap = 512 [0 -> 511] cap = 512 | after append 512 cap = 848 [0 -> 847] cap = 848 | after append 848 cap = 1280 [0 -> 1279] cap = 1280 | after append 1280 cap = 1792 [0 -> 1791] cap = 1792 | after append 1792 cap = 25601
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针对旧版本，容量扩容结果与策略是一致的，但是新版本
512后的容量扩容总是有偏差，这并不是说容量变化没有按照扩容策略。// go 1.18 src/runtime/slice.go:178 func growslice(et *_type, old slice, cap int) slice { // …… newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { const threshold = 256 if old.cap < threshold { newcap = doublecap } else { for 0 < newcap && newcap < cap { // Transition from growing 2x for small slices // to growing 1.25x for large slices. This formula // gives a smooth-ish transition between the two. newcap += (newcap + 3*threshold) / 4 } if newcap <= 0 { newcap = cap } } } // …… capmem = roundupsize(uintptr(newcap) * ptrSize) newcap = int(capmem / ptrSize) }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上述的新版本扩容程序中，前半部分与扩容规律是一致的，但后半部分总是对
newcap作了内存对齐，正是由于内存分配策略，新slice的容量总是大等于前半部分生成的newcap。
# 1.4.引申
package main import "fmt" func main() { s := []int{1,2} s = append(s,4,5,6) fmt.Printf("len=%d, cap=%d",len(s),cap(s)) }1
2
3
4
5
6
7
8
9按照切片扩容分析，
s的初始长度和容量都是2，追加元素4时，长度为3，容量为4；追加元素5时，长度和容量均为4；追加元素6时，长度变为5，容量变为8。但这是错误的，再看切片扩容程序：// go 1.9.5 src/runtime/slice.go:82 func growslice(et *_type, old slice, cap int) slice { // …… newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { // …… } // …… capmem = roundupsize(uintptr(newcap) * ptrSize) newcap = int(capmem / ptrSize) }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15这个函数的参数依次是
元素类型、老的slice、新slice最小容量，上述示例中，s的初始长度和容量都是2，append三个元素后，长度变成5，最小容量为5，即调用growslice函数时，传入的第三个参数应该是5。另一方面，doublecap是原slice容量的2倍，等于4。满足第一个if条件，所以newcap变成5。继续调用roundupsize函数，传入40—preSize代表指针长度，64位机是8。// src/runtime/msize.go:13 func roundupsize(size uintptr) uintptr { if size < _MaxSmallSize { if size <= smallSizeMax-8 { return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]]) } else { //…… } } //…… } const _MaxSmallSize = 32768 const smallSizeMax = 1024 const smallSizeDiv = 81
2
3
4
5
6
7
8
9
10
11
12
13
14
15继续看
内存对齐，会返回class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]]表达式的结果，这是Go源码中内存分配的两个slice，class_to_size通过spanClass获取span划分的object大小，size_to_class8表示通过size获取它的spanClass。var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32} var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}1
2
3传入的
size等于40，所以(size+smallSizeDiv-1)/smallSizeDiv = 5，获取size_to_class8数组中索引为5的元素5，获取class_to_size中索引为5的元素为48。最终newcap = int(capmem / ptrSize)的计算结果为6。
# 1.5.补充
nil slice或者empty slice都是可以通过调用append函数来获取底层数组的扩容，最终都是调用mallocgc来向Go的内存管理器申请内存，申请内存后赋值给原来的nil slice或empty slice，原来的空切片就会变成真正的切片。需要注意的是，Go语言的函数参数传递，只有值传递没有引用传递，slice关于底层数组位置元素的变化会反映到函数外，但追加等操作不会反映到函数外。
# 2.哈希表
# 2.1.map原理
哈希表用于维护一组
<key,value>集合，主要有两种数据结构：哈希查找表和搜索树。哈希查找表用一个哈希函数将key分配到不同的桶，开销主要在哈希函数的计算以及数组的常数访问时间，由于一般存在碰撞问题，一般会采用链表法和开放地址法规避；搜索树一般采用自平衡树，常见的有AVL树、红黑树。Go语言中map采用哈希查找表实现方式，采用链表法解决哈希冲突。type hmap struct { // 元素个数,调用len(map)直接返回此值 count int flags uint8 // buckets的对数log_2 B uint8 // overflow的bucket近似数 noverflow uint16 // 计算key的哈希的时候会传入哈希函数 hash0 uint32 // 指向buckets数组,大小为2^B // 如果元素个数为0，就为 nil buckets unsafe.Pointer // 等量扩容的时候,buckets长度和oldbuckets相等 // 双倍扩容的时候,buckets长度会是oldbuckets的两倍 oldbuckets unsafe.Pointer // 指示扩容进度,小于此地址的buckets迁移完成 nevacuate uintptr extra *mapextra // optional fields }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20hmap是实现map的结构体，其内部定义的buckets是一个指针，指向另一个的结构体实现bmap。type bmap struct { tophash [bucketCnt]uint8 }1
2
3这只是表面的
hashmap结构，编译期间会给它加料，动态创建一个新的结构。type bmap struct { topbits [8]uint8 keys [8]keytype values [8]valuetype pad uintptr overflow uintptr }1
2
3
4
5
6
7bmap就是常说的桶，桶里面最多装8个key，这些key位置碰撞就是由于hash结果一致。桶内部会再经过一轮计算，根据key计算出来的hash值的高8位决定key落入桶内的位置。
当
map的key和value都不是指针，size小于128字节的情况下，bmap被标记为不含指针，避免gc时扫描整个哈希结构。但bmap的overflow字段属于指针类型，破坏了bmap不含指针的设想，这时会把overflow移动到extra字段。type mapextra struct { // overflow[0] contains overflow buckets for hmap.buckets. // overflow[1] contains overflow buckets for hmap.oldbuckets. overflow [2]*[]*bmap // nextOverflow包含空闲的overflow bucket,这是预分配的bucket nextOverflow *bmap }1
2
3
4
5
6
7
8bmap是存放k-v的地方，它的内部组成可以参考下图。
上图就是
bucket的内存模型，HOB Hash指的是top hash，注意到key和value各自放在一起，并不是key/value/key/value...形式，这样做可能节省内存空间，省略掉padding字段—key和value不同长度类型，如map[int64]int8。每个bucket设计成最多只能放8个key-value对，继续新增的key-value对会放入新构建的bucket，通过overflow指针连接。
# 2.2.初始化
make初始化map结构时，底层会调用makemap函数，主要做的工作就是初始化hmap结构体的各种字段，包括计算B的大小、设置哈希种子hash0等。func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap { // 省略各种条件检查... // 找到一个B,使得map的装载因子在正常范围内 B := uint8(0) for ; overLoadFactor(hint, B); B++ { } // 初始化hash table // 如果B等于0,那么buckets就会在赋值的时候再分配 // 如果长度比较大,分配内存会花费长一点 buckets := bucket var extra *mapextra if B != 0 { var nextOverflow *bmap buckets, nextOverflow = makeBucketArray(t, B) if nextOverflow != nil { extra = new(mapextra) extra.nextOverflow = nextOverflow } } // 初始化hamp if h == nil { h = (*hmap)(newobject(t.hmap)) } h.count = 0 h.B = B h.extra = extra h.flags = 0 h.hash0 = fastrand() h.buckets = buckets h.oldbuckets = nil h.nevacuate = 0 h.noverflow = 0 return h }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这个函数最终会返回指针类型的
hmap，因此作为实参被函数调用时，相应的修改会反应到外部的map上。
# 2.3.哈希函数
map的关键点在于哈希函数的选择，创建时会检测cpu是否支持aes，支持会使用aes hash，否则使用memhash，这是在函数alginit()完成，该函数位于src/runtime/alg.go。hash函数分为加密型和非加密型，map实现用的是后者，hash函数的选择会综合性能和碰撞概率两方面因素。type _type struct { size uintptr ptrdata uintptr // size of memory prefix holding all pointers hash uint32 tflag tflag align uint8 fieldalign uint8 kind uint8 alg *typeAlg gcdata *byte str nameOff ptrToThis typeOff }1
2
3
4
5
6
7
8
9
10
11
12
13类型结构体中，
alg字段就和哈希相关，其指向另一个结构体指针。// src/runtime/alg.go type typeAlg struct { // (ptr to object, seed) -> hash hash func(unsafe.Pointer, uintptr) uintptr // (ptr to object A, ptr to object B) -> ==? equal func(unsafe.Pointer, unsafe.Pointer) bool }1
2
3
4
5
6
7typeAlg包含两个函数，hash函数计算类型的哈希值，equal函数计算两个类型是否哈希相等。对于string类型，它的hash和equal函数实现如下。func strhash(a unsafe.Pointer, h uintptr) uintptr { x := (*stringStruct)(a) return memhash(x.str, h, uintptr(x.len)) } func strequal(p, q unsafe.Pointer) bool { return *(*string)(p) == *(*string)(q) }1
2
3
4
5
6
7
8根据
key的类型，_type结构体的alg字段会被设置对应类型的hash和equal。
# 2.4.key查找
key经过哈希计算后会得到哈希值，哈希值的最后B个bit位决定key落在哪个桶。哈希值的高8位用于决定key在bucket中的位置，第一次加入时，桶内还没有key，新加入的key会找到第一个位置放入。buckets编号就是桶编号，当两个不同的key发生哈希冲突，会用链表法从前向后找第一个空位。
上图中，以
B=5为例，此时bucket总数是32，key计算结果的低5位对应6号桶，高8位对应十进制151，对应6号bucket的151HOB HASH，找到2号槽位，这样整个查找过程就结束。当bucket没找到时，需要继续向overflow bucket查找，直到找遍所有的key槽位，key的查找会调用mapaccess1函数。func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { // …… // 如果h什么都没有,返回零值 if h == nil || h.count == 0 { return unsafe.Pointer(&zeroVal[0]) } // 写和读冲突 if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } // 不同类型key使用的hash算法在编译期确定 alg := t.key.alg // 计算哈希值,并且加入hash0引入随机性 hash := alg.hash(key, uintptr(h.hash0)) // 比如B=5,那m就是31,二进制是全 1 // 求bucket num时,将hash与m相与 // 达到bucket num由hash的低8位决定的效果 m := uintptr(1)<<h.B - 1 // b就是bucket 的地址 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // oldbuckets不为 nil,说明发生了扩容 if c := h.oldbuckets; c != nil { // 如果不是同size扩容 // 对应条件1的解决方案 if !h.sameSizeGrow() { // 新bucket数量是老的 2 倍 m >>= 1 } // 求出key在老的map中的bucket位置 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) // 如果oldb没有搬迁到新的bucket,那就在老的bucket中寻找 if !evacuated(oldb) { b = oldb } } // 计算出高8位的hash,相当于右移56位,只取高8位 top := uint8(hash >> (sys.PtrSize*8 - 8)) // 增加一个minTopHash if top < minTopHash { top += minTopHash } for { // 遍历bucket的8个位置 for i := uintptr(0); i < bucketCnt; i++ { // tophash不匹配,继续 if b.tophash[i] != top { continue } // tophash匹配,定位到key的位置 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) // key是指针 if t.indirectkey { // 解引用 k = *((*unsafe.Pointer)(k)) } // 如果key相等 if alg.equal(key, k) { // 定位到value的位置 v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) // value解引用 if t.indirectvalue { v = *((*unsafe.Pointer)(v)) } return v } } // bucket找完,继续到 overflow bucket里找 b = b.overflow(t) // overflow bucket也找完了,说明没有目标key // 返回零值 if b == nil { return unsafe.Pointer(&zeroVal[0]) } } }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函数返回
h[key]的指针，h中没有这个key时，就会返回一个key相应类型的零值，不会返回nil。查找过程中，key和value都涉及到定位。// key定位公式 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) // value定位公式 v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))1
2
3
4
5b是bmap地址，经编译器扩充包含key、value和overflow字段，dataOffset是key相对于bmap起始地址的偏移。dataOffset = unsafe.Offsetof(struct { b bmap v int64 }{}.v)1
2
3
4因此
bucket里key的起始地址就是unsafe.Pointer(b)+dataOffset，i个key的地址在此基础上跨过i*keySize。value的地址在所有key之后，因此i个value的地址需要再加上所有key的偏移。此外，遍历bucket会调用b.overflow(t)拿到下一个bucket，直至所有bucket处理完毕。
tophash计算时涉及到minTopHash偏移，当cell的tophash值小于minTopHash，标志这个cell的迁移状态。因为这个状态是放在tophash数组里，区分于正常哈希值会向key对应哈希值增加一个增量，用于区分正常的tophash值和表示状态的哈希值。// 空的 cell，也是初始时 bucket 的状态 empty = 0 // 空的 cell，表示 cell 已经被迁移到新的 bucket evacuatedEmpty = 1 // key,value 已经搬迁完毕，但是 key 都在新 bucket 前半部分， // 后面扩容部分会再讲到。 evacuatedX = 2 // 同上，key 在后半部分 evacuatedY = 3 // tophash 的最小正常值 minTopHash = 41
2
3
4
5
6
7
8
9
10
11
# 2.5.哈希取值
map取值有两种语法：带comma和不带comma，这其实是编译器调用不同的函数实现，将两种语法对应到两种底层函数实现。// src/runtime/hashmap.go func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)1
2
3函数声明也可以看出，mapaccess2函数返回值多了bool型变量，两者的代码完全一样。此外，根据key的不同类型，编译器会将查找、插入和删除的函数用更具体的函数计算，达到优化效率目的。key 类型 查找 uint32 mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer uint32 mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) uint64 mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer uint64 mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) string mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer string mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) 这些函数的参数类型直接是具体的
uint32、uint64、string，由于函数内部提前知晓key的类型，所以内存布局是很清楚的，可以提高操作效率。
# 2.6.遍历过程
map的遍历涉及到bucket和overflow backet的cell读取，每个bucket包含8个cell，取出key-value。但map扩容可能涉及到更复杂的操作，由于扩容过程不是一个原子操作，每次最多只搬运2个bucket，触发扩容的很长时间里，map都将处于中间态——部分bucket搬迁到新家，部分还待在旧的bucket数组。这也导致扩容期间，key的查找涉及到遍历新老bucket的过程。func main() { ageMp := make(map[string]int) ageMp["qcrao"] = 18 for name, age := range ageMp { fmt.Println(name, age) } }1
2
3
4
5
6
7
8编译以上程序
go tool compile -S main.go可以得到对应运行的汇编命令。// ...... 0x0124 00292 (test16.go:9) CALL runtime.mapiterinit(SB) // ...... 0x01fb 00507 (test16.go:9) CALL runtime.mapiternext(SB) 0x0200 00512 (test16.go:9) MOVQ ""..autotmp_4+160(SP), AX 0x0208 00520 (test16.go:9) TESTQ AX, AX 0x020b 00523 (test16.go:9) JNE 302 // ......1
2
3
4
5
6
7
8
9
10从汇编结果可以看到
map迭代的底层调用关系，会先调用mapiterinit函数初始化迭代器，然后循环调用mapiternext函数进行map迭代。type hiter struct { // key指针 key unsafe.Pointer // value指针 value unsafe.Pointer // map 类型,包含如key size大小等 t *maptype // map header h *hmap // 初始化时指向的bucket buckets unsafe.Pointer // 当前遍历到的bmap bptr *bmap overflow [2]*[]*bmap // 起始遍历的bucket 编号 startBucket uintptr // 遍历开始时cell的编号(每个bucket中有8个cell) offset uint8 // 是否从头遍历 wrapped bool // B的大小 B uint8 // 指示当前cell序号 i uint8 // 指向当前的bucket bucket uintptr // 因为扩容,需要检查的bucket checkBucket uintptr }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
29mapiterinit就是对hiter结构体里的字段进行初始化赋值操作。迭代遍历过程中，map中的元素获取是无序的，这是因为底层遍历策略的实现。// 生成随机数r r := uintptr(fastrand()) if h.B > 31-bucketCntBits { r += uintptr(fastrand()) << 31 } // 从哪个bucket开始遍历 it.startBucket = r & (uintptr(1)<<h.B - 1) // 从bucket的哪个cell开始遍历 it.offset = uint8(r >> h.B & (bucketCnt - 1))1
2
3
4
5
6
7
8
9
10当
B=2时，uintptr(1)<<h.B - 1结果是3，低8位是0000 0011，与r的结果就得到0~3的bucket序号；bucketCnt - 1结果是7，低8位为0000 0111，将r右移2位后与7可以得到0~7号的cell。因此，mapiternext函数就会从it.startBucket的it.offset号的cell开始遍历，取出其中的key-value，直到回到起点bucket，完成遍历过程。
假设有一个
map，起始状态B=1，有两个bucket，后来触发扩容B=2。扩容期间，1号bucket中的内容搬迁到新的bucket，裂变成1号和3号；0号bucket暂未迁移，老的bucket挂在*oldbuckets指针上面，新的bucket挂在*buckets指针上面。此时遍历map，初始化后startBucket = 3 offset = 2。
标红的表示起始位置，
bucket遍历顺序为3 -> 0 -> 1 -> 2，由于3号bucket对应老的1号bucket，因此先检查老1号的bucket是否已经被搬迁过，会调用evacuated函数判断。func evacuated(b *bmap) bool { h := b.tophash[0] return h > empty && h < minTopHash }1
2
3
4当
b.tophash[0]的值在标志值范围—（0,4）区间，说明已经搬迁过empty = 0 evacuatedEmpty = 1 evacuatedX = 2 evacuatedY = 3 minTopHash = 41
2
3
4
5由于
1号bucket已经搬迁过，所以它的tophash[0]值在合法区间，只用遍历新的3号bucket，依次处理cell，这时候会找到第一个非空的key——e，此时mapiternext函数返回，作为第一个遍历元素。由于返回的key不为空，会继续调用mapiternext函数函数向后遍历，从新3号overflow bucket找到元素f和元素g，遍历结果集进一步扩充。
新
3号bucket遍历结束后，回到新0号bucket，新0号bucket对应旧0号bucket，由于旧0号bucket未迁移，由于旧0号bucket会裂变为新0号bucket和新2号bucket，此时遍历新0号bucket时只会取出裂变后分给新0号bucket的key。因此，lowbits == 00将进入结果集。
继续遍历新
1号bucket，由于旧1号bucket已经搬迁，只用遍历新1号bucket中现有元素，结果集会进一步扩充。
继续遍历新
2号bucket，由于它的元素来自旧0号bucket裂变分配，因此只需遍历分配到新2号bucket中的key，也就是lowbits == 10的元素，结果集进一步扩充。
最后，遍历到
3号bucket时，发现所有bucket都已经遍历完毕，整个迭代过程执行完毕。当key是math.NAN()这种时，处理方式类似，也是看它分裂后落入哪个bucket，只需要看top hash的最低位。
# 2.7.赋值过程
map插入或修改key会调用mapassign函数，mapassign有多个函数实现，编译器会根据key类型将其优化为相应的快速函数。key 类型 插入 uint32 mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer uint64 mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer string mapassign_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer map的赋值过程核心就是一个双层循环，外层遍历bucket及对应的overflow bucket，内层遍历bucket的各个cell。函数会首先检查map的标志位flags，标志位为1代表其他协程正在执行写操作，导致程序panic。扩容场景下，key定位到bucket后需要等待bucket迁移完毕才能进行插入或更新操作。key定位过程中会准备两个指针，一个inserti指向key的hash值在tophash数组所处位置，insertk指向cell位置，value位置可根据key偏移8个key长度查找。inserti和insertk分别指向第一个找到的空闲cell，基于此之后在map没有找到key的存在，代表插入新key，插入位置就是inserti和insertk指向的cell。如果bucket的8个key满了，也就是跳出循环后inserti和insertk都是空，需要在bucket后挂overflow bucket。正式安置key前，还需要检查map是否需要扩容，主动触发一次扩容操作。如果触发扩容，由于key的分布发生变化，key位置查找的过程需要再走一次。key赋值后，会清零函数开始时设置的hashWriting写标志。func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer1查看
mapassign函数定义可以发现，函数并没有传入value值，其实mapassign会返回一个指针指向value的位置，赋值就是根据指针实现的。
# 2.8.删除过程
写操作底层的执行函数是
mapdelete，删除前会检查h.flags标志判断并发操作，然后计算key的哈希找到落入的bucket，检查此map正在扩容则进行一次搬迁操作。真正删除时，通过计算key的哈希找到对应bucket，然后利用两层循环挨个cell找到key的位置，对key或者value进行清零操作。// 对 key 清零 if t.indirectkey { *(*unsafe.Pointer)(k) = nil } else { typedmemclr(t.key, k) } // 对 value 清零 if t.indirectvalue { *(*unsafe.Pointer)(v) = nil } else { typedmemclr(t.elem, v) }1
2
3
4
5
6
7
8
9
10
11
12
13清零后，会将
count减1，然后对应位置的tophash会设置为Empty。
# 2.9.map扩容
map的每个bucket只能存放8个key，随着map中添加的key越来越多，key发生碰撞的效率会变大，bucket总会被塞满，bucket溢出后就会追加overflow bucket，此时会退化为链表，影响操作效率。因此，需要有一个指标衡量当前描述情况，这就是装载因子，Go源码里这样定义装载因子。loadFactor := count / (2^B)1count是map的元素个数，2^B表示bucket数量。map扩容时，会进行条件检测，基于检测条件进行扩容：- 装载因子超出阈值，源码里定义的阈值是
6.5 overflow bucket数量过多，当B小于15时，如果overflow bucket数量超出2^B；如果B大等于15，overflow bucket数量超出2^15
- 装载因子超出阈值，源码里定义的阈值是
// src/runtime/hashmap.go/mapassign // 触发扩容时机 if !h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) } // 装载因子超过 6.5 func overLoadFactor(count int64, B uint8) bool { return count >= bucketCnt && float32(count) >= loadFactor*float32((uint64(1)<<B)) } // overflow buckets太多 func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { if B < 16 { return noverflow >= uint16(1)<<B } return noverflow >= 1<<15 }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19每个
bucket有8个空位，没有溢出且所有桶装满时，装载因子算出的结果是8。因此当装载因子超出6.5时，表明很多的bucket快要装满了，此时查找效率和扩容效率都会变得很低，扩容是有必要的。但装载因子比较小的情况下，可能会出现map元素总数少，bucket分配数量多的问题，造成key的分散，map效率变低。
对于装载因子超出情况，由于
map元素太多，bucket数量无法满足存取需求，此时需要将bucket数量扩容为2倍，此时新旧bucket同时存在，但元素还存在老的bucket。
对于
bucket数量太多情况，由于key较为分散，会开辟一个新的bucket空间，将老bucket中的元素移动到新的bucket，将key排列更紧凑，减少overflow bucket数量，提高map空间利用率和效率。这种场景会存在一种极端情况，如果key的哈希都一样，就会出现大规模的哈希碰撞，增加overflow bucket数量，导致哈希表退化为链表，此时元素移动方式就无法处理了。map扩容会将原有的key/value重新搬迁到新的内存地址，大量搬迁会非常影响性能。因此，map的扩容采取一种渐进式扩容策略，原有的key不会一次性搬迁，每次只会至多搬迁2个bucket。
扩容调用的
hashGrow()函数其实不会真正搬迁元素，它只会分配好新的buckets，并将老的buckets挂载到oldbuckets字段，真正搬迁bucket的动作在growWork()函数，调用growWork()函数的动作在mapassign和mapdelete函数，也就是插入、修改、删除key的时候都会先检查oldbuckets是否搬迁完毕，尝试搬迁bucket。func hashGrow(t *maptype, h *hmap) { // B+1相当于是原来2倍的空间 bigger := uint8(1) // 对应条件 2 if !overLoadFactor(int64(h.count), h.B) { // 进行等量的内存扩容,所以B不变 bigger = 0 h.flags |= sameSizeGrow } // 将老buckets挂到buckets上 oldbuckets := h.buckets // 申请新的buckets空间 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger) flags := h.flags &^ (iterator | oldIterator) if h.flags&iterator != 0 { flags |= oldIterator } // 提交grow的动作 h.B += bigger h.flags = flags h.oldbuckets = oldbuckets h.buckets = newbuckets // 搬迁进度为 0 h.nevacuate = 0 // overflow buckets数为0 h.noverflow = 0 // …… }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
31hashGrow会申请新的buckets内存空间，设置标志位，包括flags标志位，该标志位标识map当前情况，包括以下四种：// 可能有迭代器使用 buckets iterator = 1 // 可能有迭代器使用 oldbuckets oldIterator = 2 // 有协程正在向 map 中写入 key hashWriting = 4 // 等量扩容（对应条件 2） sameSizeGrow = 81
2
3
4
5
6
7
8flags标志位计算时，会清除iterator和oldIterator对应位，然后发现iterator为1，就会将标志位转接到oldIterator，代表扩容前的bucket挂载到oldBuckets名下，标识要开始搬迁了，迭代器正在对oldBuckets搬迁。func growWork(t *maptype, h *hmap, bucket uintptr) { // 确认搬迁老的bucket对应正在使用的bucket evacuate(t, h, bucket&h.oldbucketmask()) // 再搬迁一个bucket,以加快搬迁进程 if h.growing() { evacuate(t, h, h.nevacuate) } } func (h *hmap) growing() bool { return h.oldbuckets != nil }1
2
3
4
5
6
7
8
9
10
11
12
13bucket&h.oldbucketmask()用于确认搬迁的bucket是正在使用的，oldbucketmask()函数返回扩容前的map的bucketmask。bucketmask用于对key计算出来的哈希值相与，得到key应该落在哪个bucket。growing函数用于判断oldbuckets是否搬迁完毕，基于此再搬迁1个bucket，这也是上面提到的，每次至多搬迁2个bucket，实现渐进式搬迁。func evacuate(t *maptype, h *hmap, oldbucket uintptr) { // 定位老的bucket地址 b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) // 结果是2^B,如B = 5,结果为32 newbit := h.noldbuckets() // key的哈希函数 alg := t.key.alg // 如果b没有被搬迁过 if !evacuated(b) { var ( // 表示bucket移动的目标地址 x, y *bmap // 指向x,y中的key/val xi, yi int // 指向x，y 中的key xk, yk unsafe.Pointer // 指向x，y中的value xv, yv unsafe.Pointer ) // 默认是等size扩容,前后bucket序号不变 // 使用x来进行搬迁 x = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) xi = 0 xk = add(unsafe.Pointer(x), dataOffset) xv = add(xk, bucketCnt*uintptr(t.keysize)) // 如果不是等size扩容,前后bucket序号有变 // 使用y来进行搬迁 if !h.sameSizeGrow() { // y代表的bucket序号增加2^B y = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) yi = 0 yk = add(unsafe.Pointer(y), dataOffset) yv = add(yk, bucketCnt*uintptr(t.keysize)) } // 遍历所有的bucket,包括overflowbuckets,b是老的bucket地址 for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) v := add(k, bucketCnt*uintptr(t.keysize)) // 遍历bucket中的所有cell for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) { // 当前cell的top hash值 top := b.tophash[i] // 如果cell为空,即没有key if top == empty { // 那就标志它被"搬迁"过 b.tophash[i] = evacuatedEmpty // 继续下个cell continue } // 正常不会出现这种情况 // 未被搬迁的 cell 只可能是empty或是正常的top hash(大于 minTopHash) if top < minTopHash { throw("bad map state") } k2 := k // 如果key是指针,则解引用 if t.indirectkey { k2 = *((*unsafe.Pointer)(k2)) } // 默认使用X,等量扩容 useX := true // 如果不是等量扩容 if !h.sameSizeGrow() { // 计算hash值,和key第一次写入时一样 hash := alg.hash(k2, uintptr(h.hash0)) // 如果有协程正在遍历map if h.flags&iterator != 0 { // 如果出现相同的key值,算出来的hash值不同 if !t.reflexivekey && !alg.equal(k2, k2) { // 只有在float变量的NaN()情况下会出现 if top&1 != 0 { // 第B位置1 hash |= newbit } else { // 第B位置0 hash &^= newbit } // 取高8位作为top hash值 top = uint8(hash >> (sys.PtrSize*8 - 8)) if top < minTopHash { top += minTopHash } } } // 取决于新哈希值的oldB+1位是0还是1 useX = hash&newbit == 0 } // 如果key搬到X部分 if useX { // 标志老的cell的top hash值,表示搬移到X部分 b.tophash[i] = evacuatedX // 如果xi等于8,说明要溢出 if xi == bucketCnt { // 新建一个bucket newx := h.newoverflow(t, x) x = newx // xi从0开始计数 xi = 0 // xk表示key要移动到的位置 xk = add(unsafe.Pointer(x), dataOffset) // xv 表示value要移动到的位置 xv = add(xk, bucketCnt*uintptr(t.keysize)) } // 设置top hash值 x.tophash[xi] = top // key是指针 if t.indirectkey { // 将原key复制到新位置 *(*unsafe.Pointer)(xk) = k2 // copy pointer } else { // 将原key复制到新位置 typedmemmove(t.key, xk, k) // copy value } // value是指针,操作同key if t.indirectvalue { *(*unsafe.Pointer)(xv) = *(*unsafe.Pointer)(v) } else { typedmemmove(t.elem, xv, v) } // 定位到下一个cell xi++ xk = add(xk, uintptr(t.keysize)) xv = add(xv, uintptr(t.valuesize)) } else { // key 搬到 Y 部分，操作同 X 部分 // …… // 省略了这部分，操作和 X 部分相同 } } } // 如果没有协程在使用老的buckets,就把老buckets清除掉 if h.flags&oldIterator == 0 { b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) // 只清除bucket的key,value部分,保留top hash部分,指示搬迁状态 if t.bucket.kind&kindNoPointers == 0 { memclrHasPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset) } else { memclrNoHeapPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset) } } } // 更新搬迁进度 // 如果此次搬迁的bucket等于当前进度 if oldbucket == h.nevacuate { // 进度加1 h.nevacuate = oldbucket + 1 // 尝试往后看1024个bucket stop := h.nevacuate + 1024 if stop > newbit { stop = newbit } // 寻找没有搬迁的bucket for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { h.nevacuate++ } // 现在h.nevacuate之前的bucket都被搬迁完毕 // 所有的buckets搬迁完毕 if h.nevacuate == newbit { // 清除老的buckets h.oldbuckets = nil // 清除老的 overflow bucket if h.extra != nil { h.extra.overflow[1] = nil } // 清除正在扩容的标志位 h.flags &^= sameSizeGrow } } }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
180evacuate会将老的bucket搬迁到新的bucket，对等量扩容场景只需保持bucket不变按序搬迁，但对于倍数扩容场景则需要重新计算key归属的位置，这就是rehash。
因此，某个
key搬迁后的bucket序号可能不变，也可能相比之前偏移2^B，这取决于计算出的hash新增的位是0还是1，相应的老的bucket总是会列变成2个新的bucket。
evacuate函数每次只完成一个bucket的搬迁工作，需要遍历此bucket的所有cell并copy到新的地方。bucket还会链接overflow bucket，因此map中很多地方都是两层循环，外层遍历bucket和overflow bucket，内层遍历bucket所有cell。程序中出现的X Y部分其实就是倍数扩容后裂变的2个新bucket，前一个称为X桶，后一个称为Y桶。有一种特殊情况，当math.NaN()作为key时，它代表not a number的float64类型，每次计算的哈希结果都不一样，会导致该key对应值永远Get不到，只有遍历整个map才会出现，这种key的搬迁会基于top hash的最低位决定。if top&1 != 0 { // top hash最低位为1 // 新算出来的hash值的B位置1 hash |= newbit } else { // 新算出来的hash值的B位置0 hash &^= newbit } // hash值的B位为0,则搬迁到x part // 当B = 5时,newbit = 32,二进制低6位为10 0000 useX = hash&newbit == 01
2
3
4
5
6
7
8
9
10
11
12确定要搬迁的目标
bucket后，只需将key/value复制到目标bucket第一个非空位置。之后需要设置key在原始buckets的tophash为evacuatedX或evacuatedY，key在新buckets的tophash正常取高8位，代表key已经搬迁到新位置。
# 2.10.key无序
map扩容会发生key的搬迁，旧buckets的key可能会移动到新的buckets。由于map遍历会循环获取bucket和overflow bucket，挨个处理每个bucket cell，因此key搬迁后本身就会无序。原本不向map中插入或删除元素，按理说每次遍历map会返回固定顺序的key/value序列，但Go对迭代的实现作了处理，每次从随机值序号的bucket开始遍历，从随机序号的cell开始遍历，避免给新手带来误解。
# 2.11.map的key
Go语言中只要是可比较的类型都可以作为key，除了slice、map和functions类型都可以作为key，包括布尔值、数字、字符串、指针、通道、接口类型、结构体。这些类型的共同特征是支持比较操作，对于结构体来说，只有hash后的值相等以及字面值相等才会作为相同的key。func main() { m := make(map[float64]int) m[1.4] = 1 m[2.4] = 2 m[math.NaN()] = 3 m[math.NaN()] = 3 for k, v := range m { fmt.Printf("[%v, %d]\n", k, v) } fmt.Println("---------------") fmt.Printf("k: %v, v: %d\n", math.NaN(), m[math.NaN()]) fmt.Printf("k: %v, v: %d\n", 2.400000000001, m[2.400000000001]) fmt.Printf("k: %v, v: %d\n", 2.4000000000000000000000001, m[2.4000000000000000000000001]) fmt.Println(math.NaN() == math.NaN()) } --- 程序输出 [1.4, 1] [2.4, 2] [NaN, 3] [NaN, 3] --------------- k: NaN, v: 0 k: 2.400000000001, v: 0 k: 2.4, v: 2 false1
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示例中
key类型是float型的map，像其中插入四个key后进行查询发现NAN不存在，2.400000000001不存在，但2.4000000000000000000000001却存在。通过汇编可以发现，当float64作为key的时候，先将其转成uint64类型再作为key插入，具体是通过Float64frombits函数完成。// Float64frombits returns the floating point number corresponding // the IEEE 754 binary representation b. func Float64frombits(b uint64) float64 { return *(*float64)(unsafe.Pointer(&b)) }1
2
3也就是将浮点数表示成
IEEE 754规定的格式，如赋值语句。0x00bd 00189 (test18.go:9) LEAQ "".statictmp_0(SB), DX 0x00c4 00196 (test18.go:9) MOVQ DX, 16(SP) 0x00c9 00201 (test18.go:9) PCDATA $0, $2 0x00c9 00201 (test18.go:9) CALL runtime.mapassign(SB)1
2
3
4"".statictmp_0(SB)变量形式如下："".statictmp_0 SRODATA size=8 0x0000 33 33 33 33 33 33 03 40 "".statictmp_1 SRODATA size=8 0x0000 ff 3b 33 33 33 33 03 40 "".statictmp_2 SRODATA size=8 0x0000 33 33 33 33 33 33 03 401
2
3
4
5
6func main() { m := make(map[float64]int) m[2.4] = 2 fmt.Println(math.Float64bits(2.4)) fmt.Println(math.Float64bits(2.400000000001)) fmt.Println(math.Float64bits(2.4000000000000000000000001)) } --- 程序输出 4612586738352862003 4612586738352864255 46125867383528620031
2
3
4
5
6
7
8
9
10
11
12
13将程序输出结果转换为
16进制：0x4003333333333333 0x4003333333333BFF 0x40033333333333331
2
3和
"".statictmp_0输出相比，2.4和2.4000000000000000000000001经过math.Float64bits()函数转换后的结果是一样的，相应的作为key也会被当成一个。uvnan = 0x7FF8000000000001 // NaN returns an IEEE 754 ``not-a-number'' value. func NaN() float64 { return Float64frombits(uvnan) }1
2
3
4NAN()直接调用Float64frombits，传入写死的const变量0x7FF8000000000001，得到NAN型值，由于float64的哈希函数有多种准入形式，NAN的特性就是NAN!=NAN，所以计算哈希时总会加一个随机数，所以会被当做不同的key。func f64hash(p unsafe.Pointer, h uintptr) uintptr { f := *(*float64)(p) switch { case f == 0: return c1 * (c0 ^ h) // +0, -0 case f != f: return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN default: return memhash(p, h, 8) } }1
2
3
4
5
6
7
8
9
10
11总的来说，对于
float64类型的key，由于精度问题，会导致一些诡异问题，因此一般不会当作key。当key是引用类型时，判断两个key是否相等，需要hash后的值相等且key的字面量相等才会判断为一致。func TestT(t *testing.T) { type S struct { ID int } s1 := S{ID: 1} s2 := S{ID: 1 var h = map[*S]int {} h[&s1] = 1 t.Log(h[&s1]) t.Log(h[&s2]) t.Log(s1 == s2) }1
2
3
4
5
6
7
8
9
10
11
12
13
# 2.12.其他操作
map不是一个线程安全的数据结构，同时读写一个map是未定义的行为，检测后会抛出panic，一般会使用锁解决并发冲突问题，或使用sync.Map作为线程安全map使用。另外，map的key和value不能作取址操作，因此map可能扩容，扩容后key和value的地址会变化，长期持有会失效。