Dig101:Go之读懂map的底层设计

文章目录

  1. 1. 0x01 map的内部结构
  2. 2. 0x02 map的hash方式
  3. 3. 0x03 map的扩容方式
  4. 4. 0x04 map的初始化
  5. 5. 0x05 map的读取
  6. 6. 0x06 map的赋值
  7. 7. 0x07 map的删除
  8. 8. 0x08 map的遍历

Dig101: dig more, simplified more and know more

在golang中,map是一个不可或缺的存在。

它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。

这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。

我们不会过多在源码分析上展开,只结合代码示例对其背后设计实现上做些总结,希望可以简单明了一些。

希望看完后,会让你对 map 的理解有一些帮助。网上也有很多不错的源码分析,会附到文末,感兴趣的同学自行查看下。

(本文分析基于 Mac 平台上go1.14beta1版本。长文预警 … )

我们先简单过下map实现hash表所用的数据结构,这样方便后边讨论。

0x01 map的内部结构

map数据结构

在这里我们先弄清楚map实现的整体结构

map本质是hash表(hmap),指向一堆桶(buckets)用来承接数据,每个桶(bmap)能存8组k/v。

当有数据读写时,会用key的hash找到对应的桶。

为加速hash定位桶,bmap里记录了tophash数组(hash的高8位)

hash表就会有哈希冲突的问题(不同key的hash值一样,即hash后都指向同一个桶),为此map使用桶后链一个溢出桶(overflow)链表来解决当桶8个单元都满了,但还有数据需要存入此桶的问题。

剩下noverflow,oldbuckets,nevacuate,oldoverflow 会用于扩容,暂时先不展开

具体对应的数据结构详细注释如下:

(虽然多,先大致过一遍,后边遇到会在提到)

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
// runtime/map.go
// A header for a Go map.
type hmap struct {
//用于len(map)
count int
//标志位
// iterator = 1 // 可能有遍历用buckets
// oldIterator = 2 // 可能有遍历用oldbuckets,用于扩容期间
// hashWriting = 4 // 标记写,用于并发读写检测
// sameSizeGrow = 8 // 用于等大小buckets扩容,减少overflow桶
flags uint8

// 代表可以最多容纳loadFactor * 2^B个元素(loadFactor=6.5)
B uint8
// overflow桶的计数,当其接近1<<15 - 1时为近似值
noverflow uint16
// 随机的hash种子,每个map不一样,减少哈希碰撞的几率
hash0 uint32

// 当前桶,长度为(0-2^B)
buckets unsafe.Pointer
// 如果存在扩容会有扩容前的桶
oldbuckets unsafe.Pointer
// 迁移数,标识小于其的buckets已迁移完毕
nevacuate uintptr

// 额外记录overflow桶信息,不一定每个map都有
extra *mapextra
}

// 额外记录overflow桶信息
type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap

// 指向下一个可用overflow桶
nextOverflow *bmap
}

const(
// 每个桶8个k/v单元
BUCKETSIZE = 8
// k或v类型大小大于128转为指针存储
MAXKEYSIZE = 128
MAXELEMSIZE = 128
)

// 桶结构 (字段会根据key和elem类型动态生成,见下边bmap)
type bmap struct {
// 记录桶内8个单元的高8位hash值,或标记空桶状态,用于快速定位key
// emptyRest = 0 // 此单元为空,且更高索引的单元也为空
// emptyOne = 1 // 此单元为空
// evacuatedX = 2 // 用于表示扩容迁移到新桶前半段区间
// evacuatedY = 3 // 用于表示扩容迁移到新桶后半段区间
// evacuatedEmpty = 4 // 用于表示此单元已迁移
// minTopHash = 5 // 最小的空桶标记值,小于其则是空桶标志
tophash [bucketCnt]uint8
}

// cmd/compile/internal/gc/reflect.go
// func bmap(t *types.Type) *types.Type {
// 每个桶内k/v单元数是8
type bmap struct{
topbits [8]uint8 //tophash
keys [8]keytype
elems [8]elemtype
// overflow 桶
// otyp 类型为指针*Type,
// 若keytype及elemtype不含指针,则为uintptr
// 使bmap整体不含指针,避免gc去scan此类map
overflow otyp
}

这里有几个字段需要解释一下:

  • hmap.B

这个为啥用2的对数来表示桶的数目呢?

这里是为了hash定位桶及扩容方便

比方说,hash%n可以定位桶, 但%操作没有位运算快。

而利用 n=2^B,则hash%n=hash&(n-1)

则可优化定位方式为: hash&(1<<B-1)(1<<B-1)即源码中BucketMask

再比方扩容,hmap.B=hmap.B+1 即为扩容到二倍

  • bmap.keys, bmap.elems

在桶里存储k/v的方式不是一个k/v一组, 而是k放一块,v放一块。

这样的相对k/v相邻的好处是,方便内存对齐。比如map[int64]int8, v是int8,放一块就避免需要额外内存对齐。

另外对于大的k/v也做了优化。

正常情况key和elem直接使用用户声明的类型,但当其size大于128(MAXKEYSIZE/MAXELEMSIZE)时,

则会转为指针去存储。(也就是indirectkey、indirectelem

  • hmap.extra

这个额外记录溢出桶意义在哪?

具体是为解决让gc不需要扫描此类bucket

只要bmap内不含指针就不需gc扫描。

mapkeyelem类型都不包含指针时,但其中的overflow是指针。

此时bmap的生成函数会将overflow的类型转化为uintptr

uintptr虽然是地址,但不会被gc认为是指针,指向的数据有被回收的风险。

此时为保证其中的overflow指针指向的数据存活,就用mapextra结构指向了这些buckets,这样bmap有被引用就不会被回收了。

关于uintptr可能被回收的例子,可以看下 go101 - Type-Unsafe Pointers 中 Some Facts in Go We Should Know

0x02 map的hash方式

了解map的基本结构后,我们通过下边代码分析下map的hash

1
2
3
4
5
6
var m = map[interface{}]int{}
var i interface{} = []int{}
//panic: runtime error: hash of unhashable type []int
println(m[i])
//panic: runtime error: hash of unhashable type []int
delete(m, i)

为什么不可以用[]int作为key呢?

查找源码中hash的调用链注释如下:

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
// runtime/map.go
// mapassign,mapaccess1中 获取key的hash
hash := t.hasher(key, uintptr(h.hash0))

// cmd/compile/internal/gc/reflect.go
func dtypesym(t *types.Type) *obj.LSym {
switch t.Etype {
// ../../../../runtime/type.go:/mapType
case TMAP:
...
// 依据key构建hash函数
hasher := genhash(t.Key())
...
}
}

// cmd/compile/internal/gc/alg.go
func genhash(t *types.Type) *obj.LSym {
switch algtype(t) {
...
//具体针对interface调用interhash
case AINTER:
return sysClosure("interhash")
...
}
}

// runtime/alg.go
func interhash(p unsafe.Pointer, h uintptr) uintptr {
//获取interface p的实际类型t,此处为slice
a := (*iface)(p)
tab := a.tab
t := tab._type
// slice类型不可比较,没有equal函数
if t.equal == nil {
panic(errorString("hash of unhashable type " + t.string()))
}
...
}

如上,我们会发现map的hash函数并不唯一。

它会对不同key类型选取不同的hash方式,以此加快hash效率

这个例子slice不可比较,所以不能作为key。

也对,不可比较的类型作为key的话,找到桶但没法比较key是否相等,那map用这个key读写都会是个问题。

还有哪些不可比较?

cmd/compile/internal/gc/alg.goalgtype1 函数中可以找到返回ANOEQ(不可比较类型)的类型,如下:

  • func,map,slice
  • 内部元素有这三种类型的array和struct类型

0x03 map的扩容方式

map不可以对其值取地址;

如果值类型为slicestruct,不能直接操作其内部元素

我们用代码验证如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
m0 := map[int]int{}
// ❎ cannot take the address of m0[0]
_ = &m0[0]

m := make(map[int][2]int)
// ✅
m[0] = [2]int{1, 0}
// ❎ cannot assign to m[0][0]
m[0][0] = 1
// ❎ cannot take the address of m[0]
_ = &m[0]

type T struct{ v int }
ms := make(map[int]T)
// ✅
ms[0] = T{v: 1}
// ❎ cannot assign to struct field ms[0].v in map
ms[0].v = 1
// ❎ cannot take the address of ms[0]
_ = &ms[0]
}

为什么呢?

这是因为map内部有渐进式扩容,所以map的值地址不固定,取地址没有意义。

也因此,对于值类型为slicestruct, 只有把他们各自当做整体去赋值操作才是安全的。 go有个issue讨论过这个问题:issues-3117

针对扩容的方式,有两类,分别是:

  • sameSizeGrow

过多的overflow使用,使用等大小的buckets重新整理,回收多余的overflow桶,提高map读写效率,减少溢出桶占用

这里借助hmap.noverflow来判断溢出桶是否过多

hmap.B<=15 时,判断是溢出桶是否多于桶数1<<hmap.B

否则只判断溢出桶是否多于 1<<15

这也就是为啥hmap.noverflow,当其接近1<<15 - 1时为近似值, 只要可以评估是否溢出桶过多不合理就行了

  • biggerSizeGrow

count/size > 6.5 (装载因子 :overLoadFactor), 避免读写效率降低。

扩容一倍,并渐进的在赋值和删除(mapassign和mapdelete)期间,

对每个桶重新分流到x(原来桶区间)和y(扩容后的增加的新桶区间)

这里overLoadFactor (count/size)是评估桶的平均装载数据能力,即map平均每个桶装载多少个k/v。

这个值太大,则桶不够用,会有太多溢出桶;太小,则分配了太多桶,浪费了空间。

6.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
// mapassign 中创建新bucket时检测是否需要扩容
if !h.growing() && //非扩容中
(overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
// 提交扩容,生成新桶,记录旧桶相关。但不开始
// 具体开始是后续赋值和删除期间渐进进行
hashGrow(t, h)
}

//mapassign 或 mapdelete中 渐进扩容
bucket := hash & bucketMask(h.B)
if h.growing() {
growWork(t, h, bucket)
}

// 具体迁移工作执行,每次最多两个桶
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 迁移对应旧桶
// 若无迭代器遍历旧桶,可释放对应的overflow桶或k/v
// 全部迁移完则释放整个旧桶
evacuate(t, h, bucket&h.oldbucketmask())

// 如果还有旧桶待迁移,再迁移一个
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}

具体扩容evacuate(迁移)时,判断是否要将旧桶迁移到新桶后半区间(y)有段代码比较有趣, 注释如下:

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
newbit := h.noldbuckets()
var useY uint8
if !h.sameSizeGrow() {
// 获取hash
hash := t.hasher(k2, uintptr(h.hash0))
if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
// 这里 key != key 是指key为NaNs,
// 此时 useY = top & 1 意味着有50%的几率到新桶区间
useY = top & 1
top = tophash(hash)
} else {
if hash&newbit != 0 {
// 举例来看 若扩容前h.B=3时, newbit=1<<3
// hash&newbit != 0 则hash形如 xxx1xxx
// 新hmap的BucketMask= 1<<4 - 1 (1111: 15)
// 则 hash&新BucketMask > 原BucketMask 1<<3-1 (111: 7)
// 所以去新桶区间
useY = 1
}
}
}

// 补充一个 key != key 的代码示例
n1, n2 := math.NaN(), math.NaN()
m := map[float64]int{}
m[n1], m[n2] = 1, 2
println(n1 == n2, m[n1], m[n2])
// output: false 0 0
// 所以NaN做key没有意义。。。

弄清楚map的结构、hash和扩容,剩下的就是初始化、读写、删除和遍历了,我们就不详细展开了,简单过下。

0x04 map的初始化

map不初始化时为nil,是不可以操作的。可以通过make方式初始化

1
2
3
4
// 不指定大小
s := make(map[int]int)
// 指定大小
b := make(map[int]int,10)

对于这两种map内部调用方式是不一样的

  • small map

当不指定大小或者指定大小不大于8时,调用

func makemap_small() *hmap {

只需要直接在堆上初始化hmap和hash种子(hash0)就行。

  • bigger map

当大小大于8, 调用

func makemap(t *maptype, hint int, h *hmap) *hmap {

hint溢出则置0

初始化hmap和hash种子

根据overLoadFactor:6.5的要求, 循环增加h.B, 获取 hint/(1<<h.B) 最接近 6.5的h.B

预分配hashtable的bucket数组

h.B 大于4的话,多分配至少1<<(h.B-4)(需要内存对齐)个bucket,用于可能的overflow桶使用,

并将 h.nextOverflow设置为第一个可用的overflow桶。

最后一个overflow桶指向h.buckets(方便后续判断已无overflow桶)

0x05 map的读取

对于map的读取有着三个函数,主要区别是返回参数不同

1
2
3
mapaccess1: m[k]
mapaccess2: a,b = m[i]
mapaccessk: 在map遍历时若grow已发生,key可能有更新,需用此函数重新获取k/v

计算key的hash,定位当前buckets里桶位置

如果当前处于扩容中,也尝试去旧桶取对应的桶,需考虑扩容前bucket大小是否为现在一半,且其所指向的桶未迁移

然后就是按照bucket->overflow链表的顺序去遍历,直至找到tophash匹配且key相等的记录(entry)

期间,如果key或者elem是转过指针(size大于128),需转回对应值。

map为空或无值返回elem类型的零值

0x06 map的赋值

计算key的hash,拿到对应的桶

如果此时处于扩容期间,则执行扩容growWork

对桶bucket->overflow链表遍历

  • 若有空桶(对应tophash[i]为空),则准备在此空桶存储k/v

  • 若非空,且和tophash相等,且key相等,则更新对应elem

  • 若无可用桶,则分配一个新的overflow桶来存储k/v, 会判断是否需要扩容

最后若使用了空桶或新overflow桶,则要将对应tophash更新回去, 如果需要的话,也更新count

0x07 map的删除

获取待删除key对应的桶,方式和mapassign的查找方式基本一样,找到则清除k/v。

这里还有个额外操作:

如果当前tophash状态是:当前cell为空(emptyOne),

若其后桶或其后的overflow桶状态为:当前cell为空前索引高于此cell的也为空(emptyRest),则将当前状态也更新为emptyRest

倒着依次往前如此处理,实现 emptyOne -> emptyRest的转化

这样有什么好处呢?

答案是为了方便读写删除(mapaccess,mapassign,mapdelete)时做桶遍历(bucketLoop)能减少不必要的空bucket遍历

截取代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
// 减少空cell的遍历
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
...
}

0x08 map的遍历

先调用mapiterinit 初始化用于遍历的 hiter结构体, 这里会用随机定位出一个起始遍历的桶hiter.startBucket, 这也就是为啥map遍历无序。

随机获取起始桶的代码如下:

1
2
3
4
5
6
r := uintptr(fastrand())
// 随机数不够用得再加一个32位
if h.B > 31-bucketCntBits {
r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)

在调用mapiternext去实现遍历, 遍历中如果处于扩容期间,如果当前桶已经迁移了,那么就指向新桶,没有迁移就指向旧桶


至此,map的内部实现我们就过完了。

里边有很多优化点,设计比较巧妙,简单总结一下:

  • 以2的对数存储桶数,便于优化hash模运算定位桶,也利于扩容计算
  • 每个map都随机hash种子,减少哈希碰撞的几率
  • map以key的类型确定hash函数,对不同类型针对性优化hash计算方式
  • 桶内部k/v并列存储,减少不必要的内存对齐浪费;对于大的k/v也会转为指针,便于内存对齐和控制桶的整体大小
  • 桶内增加tophash数组加快单元定位,也方便单元回收(空桶)标记
  • 当桶8个单元都满了,还存在哈希冲突的k/v,则在桶里增加overflow桶链表存储
  • 桶内若只有overflow桶链表是指针,则overflow类型转为uintptr,并使用mapextra引用该桶,避免桶的gc扫描又保证其overflow桶存活
  • 写操作增加新桶时如果需要扩容,只记录提交,具体执行会分散到写操作和删除操作中渐进进行,将迁移成本打散
  • 哈希表的装载因子不满足要求是,扩容一倍,保证桶的装载能力
  • 哈希表overflow桶过多,则内存重新整理,减少不必要的overflow桶,提升读写效率
  • 对指定不同大小的map初始化,区别对待,不必要的桶预分配就避免;桶较多的情况下,也增加overflow桶的预分配
  • 每次遍历起始位置随机,严格保证map无序语义
  • 使用flags位标记检测map的并发读写,发现时panic,一定程度上预防数据不一致发生

趁热打铁,建议你再阅读一遍源码,加深一下理解。

附上几篇不错的源码分析文章,代码对应的go版本和本文不一致,但变化不大,可以对照着看。

本文代码见 NewbMiao/Dig101-Go

如有疑问,请文末留言交流或邮件:newbvirgil@gmail.com 本文链接 : http://blog.newbmiao.com/2020/02/04/dig101-golang-map.html