0%

《Golang》Map原理

Hash 冲突解决

要实现 map 这样的数据结构,需要根据 key 的不同把 value 放到不同的地方以供存取,且不允许两个不同的 key 命中同一个地方,这样的话就覆盖了

自然就会想到对 key 进行某个 hash 算法来定位位置,但是 hash 算法是不能保证不同的 key ,hash 出来的结果是不一样的,所以需要外加一种方案来解决这个问题

常见的是下面两种方案

开放寻址法

开放寻址法 是一种在哈希表中解决哈希碰撞的方法,这种方法的核心思想是在一维数组对元素进行探测和比较以判断待查找的目标键是否存在于当前的哈希表中,如果我们使用开放寻址法来实现哈希表,那么在初始化哈希表时就会创建一个新的数组,如果当我们向当前『哈希表』写入新的数据时发生了冲突,就会将键值对写入到下一个不为空的位置:

上图展示了键 Key3 与已经存入『哈希表』中的两个键 Key1 和 Key2 发生冲突时,Key3 会被自动写入到 Key2 后面的空闲内存上,在这时我们再去读取 Key3 对应的值时就会先对键进行哈希并所索引到 Key1 上,对比了目标键与 Key1 发现不匹配就会读取后面的元素,直到内存为空或者找到目标元素。

当我们查找某个键对应的数据时,就会对哈希命中的内存进行线性探测,找到目标键值对或者空内存就意味着这一次查询操作的结束。

开放寻址法中对性能影响最大的就是装载因子,它是数组中元素的数量与数组大小的比值,随着装载因子的增加,线性探测的平均用时就会逐渐增加,这会同时影响哈希表的查找和插入性能,当装载率超过 70% 之后,哈希表的性能就会急剧下降,而一旦装载率达到 100%,整个哈希表就会完全失效,所以在实现哈希表时一定要时刻关注装载因子的变化。

拉链法

与开放地址法相比,拉链法是哈希表中最常见的实现方法,大多数的编程语言都是用拉链法实现哈希表,它的实现相对比较简单,平均查找的长度也比较短,而且各个用于存储节点的内存都是动态申请的,可以节省比较多的存储空间。

拉链法的实现其实就是使用数组加上链表组合起来实现哈希表,数组中的每一个元素其实都是一个链表,我们可以将它看成一个可以扩展的二维数组:

当我们需要将一个键值对加入一个哈希表时,键值对中的键都会先经过一个哈希函数,哈希函数返回的哈希会帮助我们『选择』一个桶,然后遍历当前桶中持有的链表,找到键相同的键值对执行更新操作或者遍历到链表的末尾追加一个新的键值对。

如果要通过某个键在哈希表中获取对应的值,就会经历如下的过程:

Key11 就是展示了一个键在哈希表中不存在的例子,当哈希表发现它命中 2 号桶时,它会依次遍历桶中的链表,如果遍历到链表的末尾也没有找到期望的键,那么该键对应的值就是空。

在一个性能比较好的哈希表中,每一个桶中都应该有 0 或者 1 个元素,有时会有 2~3 个元素,很少会发生遇到超过这个数量的情况,每一次读写哈希表的时间基本上都花在了定位桶和遍历链表这两个过程,有 1000 个桶的哈希表如果保存了 10000 个键值对,它的性能是保存 1000 个键值对的 1/10,但是仍然比一个链表的性能好 1000 倍。

Golang 中 Map 源码解析

Golang 使用的是拉链法方案解决冲突问题

下图是 Map 的存储结构

如果多个 key 通过 hash 计算后命中了同一个 bucket ,那么这些 key 、 value 会放到这个 bucket 中,但是 bucket 容量有限,当 bucket 容量不够了,就会放到 overflow 中

Golang 中所有的 Map 都分配在堆中

当 make 第二个参数也就是 hint <= 8 时,编译器会将 make 翻译成 runtime.makemap_small ,大于 8 时会翻译成 runtime.makemap

下面是 map 的底层数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed

buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)

extra *mapextra // optional fields
}

Map 的创建

1
2
3
4
5
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand()
return h
}

makemap_small 仅仅是申请了 Map header 的空间然后初始化了 hash 种子。元素数量小于或等于 8 的情况下是不需要 overflow 区域的,即使 8 个 key 都落在了同一个 bucket 上,这个 bucket 也能装得下他们,因为一个 bucket 最多能存放 8 个键值对

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
func makemap(t *maptype, hint int, h *hmap) *hmap {
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 = fastrand() // 随机产生一个hash种子

// Find the size parameter B which will hold the requested # of elements.
// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
B := uint8(0)
for overLoadFactor(hint, B) { // 根据hint,也就是map预设的长度,确定B的大小,也就是桶的个数
B++
}
h.B = B

// allocate initial hash table
// if B == 0, the buckets field is allocated lazily later (in mapassign)
// If hint is large zeroing this memory could take a while.
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) // 分配buckets以及overflow区域
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow // 指定下一个可用的overflow bucket
}
}

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
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
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if h == nil { // nil map设置值会panic
panic(plainError("assignment to entry in nil map"))
}
if raceenabled {
callerpc := getcallerpc()
pc := funcPC(mapassign)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled {
msanread(key, t.key.size)
}
if h.flags&hashWriting != 0 { // 如果hashWriting标识位已经是1的话,表示其他线程正在写,就发生并发写,然后panic 
throw("concurrent map writes")
}
hash := t.hasher(key, uintptr(h.hash0)) // 对key进行hash

// Set hashWriting after calling t.hasher, since t.hasher may panic,
// in which case we have not actually done a write.
h.flags ^= hashWriting // 设置hashWriting标识位为1,其他位不变(异或运算就是相同取0,不同取1)

if h.buckets == nil { // 如果buckets还没有初始化(hint<=8时在make的时候不会初始化)
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) 初始化一个bucket
}

again:
bucket := hash & bucketMask(h.B) // 得到key落在哪个bucket索引上
if h.growing() { // 如果正在扩容,那么进行迁移工作
growWork(t, h, bucket)
}
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) // 得到那个bucket所在的地址
top := tophash(hash) // 取hash的高8位

var inserti *uint8 // 记录b.tophash中下一个插入的地址
var insertk unsafe.Pointer // 记录key的插入地址
var elem unsafe.Pointer // 记录value的插入地址
bucketloop:
for {
for i := uintptr(0); i < bucketCnt; i++ { // 遍历8次,就是遍历bucket中所有key
if b.tophash[i] != top { // 如果bucket中保存的第i个位置的tophash跟hash高8位不一样
if isEmpty(b.tophash[i]) && inserti == nil { // 如果i位置是空的,那么找到了这个位置插入
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
}
if b.tophash[i] == emptyRest { // 如果i这个位置是空的,而且i后面都是空的
break bucketloop // bucket中没有找到且还有空余位置,则跳出bucketloop处的for循环
}
continue // 继续寻找此bucket的下一个位置
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) // 得到i位置的key的地址
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if !t.key.equal(key, k) { // 如果找到的key跟想插入或更新的key不相等,则接着找下一个
continue
}
// already have a mapping for key. Update it. 如果找到了这个key
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) // 找到i位置对应元素的地址
goto done // 找到key了,跳到done位置执行
}
ovf := b.overflow(t) // 执行到这里,说明bucket中没有找到这个key,而且bucket已经塞满了。这里得到这个bucket下的overflow bucket的地址
if ovf == nil {
break // 如果没有overflow bucket,则跳出循环
}
b = ovf // 有的话,将需要遍历的bucket替换成overflow bucket,接着就会遍历它
}

// Did not find mapping for key. Allocate new cell & add entry.

// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing. 执行到这里应该是开始插入key、value了
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { // 如果没有正在扩容且(overflow bucket太多或者负载因子太大),则需要扩容
hashGrow(t, h) // 扩容
goto again // Growing the table invalidates everything, so try again // 再次寻找空位置插入
}

if inserti == nil { // 如果前面没有找到位置插入,则要插入到overflow中
// all current buckets are full, allocate a new one.
newb := h.newoverflow(t, b) // 新建一个overflow bucket
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}

// store new key/elem at insert position
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectelem() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.key, insertk, key) // 插入key
*inserti = top
h.count++

done:
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
if t.indirectelem() {
elem = *((*unsafe.Pointer)(elem))
}
return elem // 返回value的地址,实际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
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapdelete)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
if msanenabled && h != nil {
msanread(key, t.key.size)
}
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return
}
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}

hash := t.hasher(key, uintptr(h.hash0))

// Set hashWriting after calling t.hasher, since t.hasher may panic,
// in which case we have not actually done a write (delete).
h.flags ^= hashWriting

bucket := hash & bucketMask(h.B) // 得到命中的bucket
if h.growing() { // 如果正在扩容,那么进行迁移工作
growWork(t, h, bucket)
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
top := tophash(hash)
search:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ { // 遍历bucket中的8个数据
if b.tophash[i] != top { // i位置不是要找的key
if b.tophash[i] == emptyRest { // 如果i位置是空的,而且后面也是空的,就跳出搜索,说明map中不存在这个key,什么都不做了
break search
}
continue // 接着找下一个key
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) // 执行到这里说明找到key了,就是i位置。这里找到key在的地址
k2 := k
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
if !t.key.equal(key, k2) { // double check
continue
}
// Only clear key if there are pointers in it.
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.ptrdata != 0 { // 如果key是指针类型
memclrHasPointers(k, t.key.size) // 删除key,不删除的话,会影响这个key的gc回收。非指针类型无需删除,下次写直接覆盖了
}
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) // 找到元素所处的地址
if t.indirectelem() {
*(*unsafe.Pointer)(e) = nil
} else if t.elem.ptrdata != 0 {
memclrHasPointers(e, t.elem.size)
} else {
memclrNoHeapPointers(e, t.elem.size)
}
b.tophash[i] = emptyOne // i位置置为空
// If the bucket now ends in a bunch of emptyOne states,
// change those to emptyRest states.
// It would be nice to make this a separate function, but
// for loops are not currently inlineable.
if i == bucketCnt-1 { // 如果是bucket最后一个位置
if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { // 如果存在overflow bucket且overflow bucket中存在key
goto notLast
}
} else {
if b.tophash[i+1] != emptyRest { // 如果后面的key有的不是空
goto notLast
}
}
for { // 从i开始将前面的key都标记为emptyRest,直到碰到一个非空的key
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 = bucketCnt - 1
} else {
i--
}
if b.tophash[i] != emptyOne {
break
}
}
notLast:
h.count--
break search
}
}

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

获取值

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
func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
if raceenabled && h != nil {
callerpc := getcallerpc()
racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess1_fast64))
}
if h == nil || h.count == 0 {
return unsafe.Pointer(&zeroVal[0])
}
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
var b *bmap
if h.B == 0 { // Map只有一个bucket
// One-bucket table. No need to hash.
b = (*bmap)(h.buckets)
} else {
hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
m := bucketMask(h.B)
b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil { // oldbuckets存在的话表示正在扩容
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
}
for ; b != nil; b = b.overflow(t) {
for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) { // 遍历bucket,没找到就接着遍历overflow bucket
if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) {
return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.elemsize)) // 找到了,返回元素
}
}
}
return unsafe.Pointer(&zeroVal[0])
}

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
func hashGrow(t *maptype, h *hmap) {
// If we've hit the load factor, get bigger.
// Otherwise, there are too many overflow buckets,
// so keep the same number of buckets and "grow" laterally.
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow // map大小没改变
}
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) // 分配更大的buckets以及overflow区域

flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// commit the grow (atomic wrt gc)
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets // 旧的buckets指针会保存起来
h.buckets = newbuckets // bucket指针指向新的buckets
h.nevacuate = 0
h.noverflow = 0

if h.extra != nil && h.extra.overflow != nil {
// Promote current overflow buckets to the old generation.
if h.extra.oldoverflow != nil {
throw("oldoverflow is not nil")
}
h.extra.oldoverflow = h.extra.overflow // 老的overflow区域也保存起来
h.extra.overflow = nil
}
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}

// the actual copying of the hash table data is done incrementally
// by growWork() and evacuate().
}

可以看到上面并没有发生搬迁的动作,老的数据只是备份了,新的 buckets 都是空的。

实际上,真正的搬迁工作发生在新增 key 和删除 key 的时候,新增 key 和删除 key 的时候会判断是否有备份数据,有的话将备份数据迁移到新的 buckets 里面,然后删除备份

由 growWork 和 evacuate 函数完成

这就是 COW(copy on write)机制

Map 扩容其实就是安排更多的 bucket ,但是并不能简单的直接在 bucket 区域后面新增 bucket ,因为 key 经过 hash 后要与 bucket 个数运算得到第几个 bucket ,如果简单的增加 bucket 个数,而数据不重新安置的话,根据 key 将找不到对应的 value 。

Map 元素无法取址问题

如果我们尝试对 Map 的元素取址,会遇到 cannot take the address of m[“a”] 错误。

因为 Map 在扩容后 m[“a”] 的地址是会发生改变的。

总结

  1. overflow 区域的最后一个 bucket 具有 overflow ,指向第一个 bucket
  2. key 经过 hash 得到一个 hash 值,与 hmap.B 运算得到第几个 bucket ,然后遍历这个 bucket 下面的 8 个坑位,坑位满了的话遍历 overflow bucket 的坑位,同时会检查负载因子,如果太大,说明某些 bucket 连同它的 overflow 的坑位不多了,就会进行扩容,新增更多的 bucket
  3. map 的元素无法取地址,因为一旦发生扩容,他们的地址就变了(因为扩容时是新开辟内存),这种扩容现象也很随机
  4. map 的 key 通过 hash 定位到某个 bucket ,这个动作结果是随机的,所以不管插入顺序是怎样的,存储位置没有任何规律,那么 map 遍历肯定是跟插入顺序无关的,所以 map 是无序的
  5. map 不是并发安全的。可以看到 map 的结构体中并没有 Mutex 锁
  6. Map 实际是 struct 值类型,但很像指针类型,Map 本身就被编译器视为地址,指向 struct 结构第一个元素,即已有元素个数
  7. Map 整个结构体都在堆中



微信关注我,及时接收最新技术文章