目标

需要弄懂下面的问题:

  • map的基本数据结构定义
  • map的增、删、改、查的实现
  • 扩容机制
  • range map为什么是无序的
  • map为什么不安全,以及sync.Map为什么安全

工具

go tool compile -S main.go

通过上面命令可以输出汇编指令,方便获取实际调用的方法。

数据结构

map对应的数据结构为 hmap

 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
const (
	bucketCntBits = 3
	bucketCnt     = 1 << bucketCntBits
)

type hmap struct {
	count     int               // 指map的count数量
	flags     uint8             // 迭代map或者对map进行写操作的时候,会记录该标志位,用于一些并发场景的检测校验
	B         uint8             // 存放当前map存放的bucket数组长度的对数,即len(buckets) == 2^B
	noverflow uint16            // 溢出的bucket数量
	hash0     uint32            // hash函数种子

	buckets    unsafe.Pointer   // buckets桶的头指针,增删改查都需要相对头指针偏移计算获取目标数据地址
	oldbuckets unsafe.Pointer   // 只有扩容的时候不是nil,指向旧的buckets
	nevacuate  uintptr          // 下一个扩容的桶编号

	extra *mapextra             // optional fields
}

type mapextra struct {
	overflow    *[]*bmap        // 已经使用的溢出桶
	oldoverflow *[]*bmap        // 旧桶使用的溢出桶
	nextOverflow *bmap          // 下一个空闲溢出桶
}

// runtime下的源码
type bmap struct {
	tophash [bucketCnt]uint8
}

// 编译期间,反射的类型
type bmap struct {
  topbits  [8]uint8
  keys     [8]keytype
  values   [8]valuetype
  pad      uintptr
  overflow uintptr
}

bBSU78.png

由上面的数据结构可以知道:

  • B作为2的幂次,意义是方便通过bucket := hash & bucketMask(h.B)定位到key和哪个bucket关联
  • 如果分配桶的数目大于2^4次方,会分配2^(B-4)次方个溢出桶

增刪改查

创建

1
2
3
4
5
6
7
package main

func main() {
	m1 := make(map[int]int)
	m2 := make(map[int]int, 10)
	_, _ = m1, m2
}

上面m1初始化调用的 runtime.makemap_small,编译期能确定map长度小于bucketCnt,没有初始化bucket。m2初始化调用 runtime.makemap,通过传入的size,获取对应的对数B进行初始化。

查询

查询某个key的流程如下:

  • 将k1通过Hash函数生成64位二进制数d1
  • 将d1和hmap的B-1值进行与操作获取具体bucket号
  • 遍历前面获取到的bucket,将d1的首8位和bucket里的tophash值进行比较查找,查找到了即拿当前索引去计算值的索引返回值。没有查找到就看啊可能overflow是否为空,不为空则查找关联的下一个bucket

map的查询访问涉及下面两个函数, mapaccess2多了一个key是否存在的返回值:

  • func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
  • func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

增加和修改

不考虑扩容的情况下,map的增加与map的查询访问基本逻辑是一致的。首先遵循map访问的方式通过后B位定位bmap,通过前8位快速比较tophash。当map中不存在这个key,会记录bmap中的第一个空闲的tophash,并插入该key。当map中存在这个key,会更新该key的value,涉及到的函数主要是 mapassign

删除

map的删除与map的查询访问基本逻辑也是一致的。遍历bmap与overflow寻找目标key,如果找到则清空tophash并删除key/value释放内存,涉及的函数时 mapdelete

扩容机制

map扩容的目的时解决Hash冲突,防止复杂度增加,尽量保持算法O(1)的时间复杂度。Golang的map扩容时渐进式扩容,写入操作中发生,触发扩容的时机有以下两个:

  • 情况一, overLoadFactor函数计算count/2^B(长度/桶)是否大于6.5,大于就进行2倍扩容,即hmap.B++
  • 情况二,map存在局部bmap包含过多overflow的情况(B <= 15 && noverflow >= 2^B || B > 15 && noverflow >= 2^15),此时map会认为局部的bmap可以进行tophash密集排列,进行等量扩容,创建一样多的新通,将旧桶迁移到新桶,进行密集排列

不知道6.5这个阈值怎么定下来的,每个桶装8个,定个6.5 😅。

range map为什么是无序的

遍历map对应的函数分别是 runtime.mapiterinitruntime.mapiternext

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// decide where to start
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
    r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))

// iterator state
it.bucket = it.startBucket

如上面代码所示,在遍历开始的时候,随机取的开始bucket,所以每次遍历的顺序都不一样,但是理论上是开始bucket不一样,但是整体bucket是按照写入顺序的。

map为什么不安全,以及sync.Map为什么安全

官方设计就是不支持多个协程进行map的并发读写操作,相关源码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// flags
iterator     = 1 // there may be an iterator using buckets
oldIterator  = 2 // there may be an iterator using oldbuckets
hashWriting  = 4 // a goroutine is writing to the map
sameSizeGrow = 8 // the current map growth is to a new map of the same size

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
}

// ... mapassign / mapdelete / mapiternext / mapclear 也一样,这里省略

至于sync.Map为什么安全,见 golang-sync-map

Reference