万字剖析Golang的map实现原理

0、弁言

相信大家对Map这个数据布局都不生疏，像C++的map、Java的HashMap。各个语言的底层实现各有不同，在本篇博客中，我将分享个人对Go的map实现的理解，以及深入源码进行分析，相信耐心看完肯定会收获不少。
1、宏观布局

相信大家对于map的基本使用都不生疏，Golang中的map是不允许并发写操纵的，这里的写指代的是宏观意义上的“写”，包罗了更新、插入、删除操纵。当发生了并发写时，程序会抛出fatal，这是一个非常严重的错误，会直接停止程序的进行，因此对于同一个map，它不应该被共享到多个协程中。
我们可以通过以下代码来验证：

1. func main() {
2.         hm := map[int]int{1: 1, 2: 2, 3: 3}
3.         for i := 4; i <= 9999; i++ {
4.                 go func(num int) {
5.                         hm[i] = i
6.                 }(i)
7.         }
8. }

复制代码

math.MulUintptr实现如下：

1. type hmap struct {
2.         count     int // # live cells == size of map.  Must be first (used by len() builtin)
3.         flags     uint8
4.         B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
5.         noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
6.         hash0     uint32 // hash seed
8.         buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
9.         oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
10.         nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
12.         extra *mapextra // optional fields
13. }

复制代码

在这里，bucketCnt为8。若count= 4 {                nbuckets += bucketShift(b - 4)        //计算分配的总内存大小                sz := t.Bucket.Size_ * nbuckets        //将内存大小向上对齐到合适的大小，是内存分配的一个优化。                up := roundupsize(sz, t.Bucket.PtrBytes == 0)                if up != sz {            //调解桶数量，使得内存被充实使用                        nbuckets = up / t.Bucket.Size_                }        }        if dirtyalloc == nil {        //分配nbuckets个桶                buckets = newarray(t.Bucket, int(nbuckets))        } else {                //复用旧的内存                buckets = dirtyalloc                size := t.Bucket.Size_ * nbuckets                if t.Bucket.PtrBytes != 0 {                        memclrHasPointers(buckets, size)                } else {                        memclrNoHeapPointers(buckets, size)                }        }        if base != nbuckets {                //如果base和nbuckets的数量不同，阐明预分配了溢出桶，需要设置溢出桶链表        //指向第一个可用的预分配溢出桶，计算出溢出桶的起始位置                nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))        //最后一个预分配的溢出桶的位置                last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))        //将最后一个溢出桶的指针设置为buckets，形成一个环形链表，用于背面的分配判断                last.setoverflow(t, (*bmap)(buckets))        }        return buckets, nextOverflow}[/code]makeBucketArray方法会根据初始的对数B来判断是否需要分配溢出桶。若B>=4，则需要预分配的溢出桶数量为2^(B-4)。确定好桶的总数后，会根据dirtyalloc是否为nil来判断是否需要新开发空间。最后会返回指向桶数组的指针以及指向首个溢出桶位置的指针。
当最后返回到上层的makemap方法中，最终创造出的map布局如图：

2.2、map的读流程

2.2.1、读流程步骤总览

大致流程如下：
1、检查表是否为nil，或者表是否没有元素，如果则直接返回零值。
2、若处在并发写状态，则会导致程序崩溃（fatal）。
3、计算key对应的hash值，而且定位到对应的桶上。
4、若数据在旧桶，且数据没有迁徙到新桶中，就在旧桶查找，否则在新桶中查找。
5、外层遍历桶数组的每个桶，内层遍历桶的每个kv对，找到了就返回value，否则返回零值
2.2.2、源码跟进mapaccess1

1. type mapextra struct {
2.         overflow    *[]*bmap
3.         oldoverflow *[]*bmap
5.         nextOverflow *bmap
6. }

复制代码

（1）若哈希表为空，或不存在键值对，则会返回零值。在此之前，会检查key是否正当，非法会触发panic。

1. type bmap struct {
2.         tophash [bucketCnt]uint8
3. }

复制代码

（2）若存在并发写map，会立即报错，使得程序停止运行。flags的第3个bit位标识map是否处于并发写状态。

1. type bmap struct {
2.         tophash [bucketCnt]uint8
3.         keys [bucketCnt]T
4.     values [bucketCnt]T
5.     overflow unsafe.Pointer
6. }

复制代码

（3）计算key的hash值，而且对桶数量取模，定位到具体的桶。取模运算为x & (mod-1)，只有mod为2的幂时可以加速。

1. //makemap为make(map[k]v,hint)实现Go映射创建
2. func makemap(t *maptype, hint int, h *hmap) *hmap {
3.         mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
4.         if overflow || mem > maxAlloc {
5.                 hint = 0
6.         }
8.         // initialize Hmap
9.         if h == nil {
10.                 h = new(hmap)
11.         }
12.         h.hash0 = uint32(rand())
14.         // Find the size parameter B which will hold the requested # of elements.
15.         // For hint < 0 overLoadFactor returns false since hint < bucketCnt.
16.         B := uint8(0)
17.         for overLoadFactor(hint, B) {
18.                 B++
19.         }
20.         h.B = B
21.        
22.     //若B==0，那么buckets将会采取懒创建的策略，会在未来要写map的方法mapassign中创建。
23.         if h.B != 0 {
24.                 var nextOverflow *bmap
25.                 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
26.                 if nextOverflow != nil {
27.                         h.extra = new(mapextra)
28.                         h.extra.nextOverflow = nextOverflow
29.                 }
30.         }
32.         return h
33. }

复制代码

（4）检查是否存在旧桶，存在旧桶且数据未搬迁完成则去旧桶中找key，否则在新桶找。

1. mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
2.         if overflow || mem > maxAlloc {
3.                 hint = 0
4.         }

复制代码

在取旧桶的时间，会根据evacuated判断数据是否已经迁徙到新的桶：判断方法是取桶首个元素的tophash值，若值为2,3,4中的一个，代表数据已经迁徙完成。

1. func MulUintptr(a, b uintptr) (uintptr, bool) {
2.         if a|b < 1<<(4*goarch.PtrSize) || a == 0 {
3.                 return a * b, false
4.         }
5.         overflow := b > MaxUintptr/a
6.         return a * b, overflow
7. }

复制代码

（5）取key的hash值的高8位值top，若值> (goarch.PtrSize*8 - 8))        if top < minTopHash {                top += minTopHash        }        return top}[/code]（6）外层b遍历每一个桶，内层遍历b中的每一个kv对，对比每一个kv对的tophash值是否和要查询的key的top值是否相同进行查找。

1. // initialize Hmap
2.         if h == nil {
3.                 h = new(hmap)
4.         }

复制代码

若两个hash值不同，而且桶中的当前键值对的tophash为0，表示后续没有元素，直接退出循环返回零值。否则检查下一个kv。

1. h.hash0 = uint32(rand())

复制代码

若找到了，就根据内存偏移找到对应的value而且返回。注意：会调用key.Equal方法具体检查要读的key和当前key是否一样，避免由于哈希冲突导致读取了错误的value。

1. B := uint8(0)
2.         for overLoadFactor(hint, B) {
3.                 B++
4.         }
5.         h.B = B

复制代码

否则最终返回0值。

1. func overLoadFactor(count int, B uint8) bool {
2.         return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
3. }

复制代码

2.3、map的写流程

2.3.1、写流程步骤总览

大致流程如下：

• 1、若表为nil，则panic，若处在并发写，则fatal
  
• 2、获取key的hash值，用于校验是否已经存在，需要覆盖
  
• 3、设置处于写状态
  
• 4、懒创建buckets，若B==0，则buckets会在第一次写的时间创建
  
• 5、根据hash定位到具体的bucket中，若表处在扩容阶段则调用growWork辅助扩容；创建三个拟插入位置指针，分别存储要插入的tophash、key、value的位置。（作用是若遇见空位置，就存储，然后要继续看是否存在相同的key要覆盖。）
  
• 6、遍历该桶的每一个kv，会遇到两种情况：
  
  
  
  • 若当前槽位的tophash和要插入的键值对的tophash不相同，那么检查是否是空槽，是则更新拟存储指针；若当前槽位是空槽，会继续检查对背面是否存在kv的标识，若背面全是空槽了，就可以直接退出了不必继续遍历。
    
  • 若相同，那就直接进行覆盖操纵，更新完成直接到第10步进行收尾。
    
  
  
• 7、如果我们没有找到要插入的位置，或者要插入的位置是当前桶的最后一个槽位，检查以下条件决定是否进行扩容：
  
  
  
  • Count+1 > loadfactor * 2^h.B，即总键值对 > 负载因子*总桶数
    
  • h.noverflow > threshold：如果 溢出桶过多，阐明冲突严重，也要扩容。
    
  发生扩容后，刚刚的记录就无效了，重新到第5步。
  
  
• 8、若不扩容，且没有插入的位置（没有空槽，也没有覆盖），就新创建一个新桶，连接到当前桶的背面作为溢出桶，插入到新桶的第一个位置上。这个新桶可以是新分配的，也可以是一开始创建表就预分配的（优先）。
  
• 9、对拟插入的位置进行现实的插入
  
• 10、收尾，再次检查是否处在并发写状态，是则fatal，否则重置写状态标识，然后退出。
  

2.3.2、源码跟进mapassign

1. if h.B != 0 {
2.                 var nextOverflow *bmap
3.                 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
4.                 if nextOverflow != nil {
5.                         h.extra = new(mapextra)
6.                         h.extra.nextOverflow = nextOverflow
7.                 }
8.         }

复制代码

（1）错误处置惩罚：map为空则panic，并发写则出发fatal。

1. func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
2.     //初始桶数量
3.         base := bucketShift(b)
4.     //最终桶数量，初始和base相同
5.         nbuckets := base
6.         //溢出桶预分配
7.         if b >= 4 {
8.                 nbuckets += bucketShift(b - 4)
9.         //计算分配的总内存大小
10.                 sz := t.Bucket.Size_ * nbuckets
11.         //将内存大小向上对齐到合适的大小，是内存分配的一个优化。
12.                 up := roundupsize(sz, t.Bucket.PtrBytes == 0)
13.                 if up != sz {
14.             //调整桶数量，使得内存被充分利用
15.                         nbuckets = up / t.Bucket.Size_
16.                 }
17.         }
19.         if dirtyalloc == nil {
20.         //分配nbuckets个桶
21.                 buckets = newarray(t.Bucket, int(nbuckets))
22.         } else {
23.                 //复用旧的内存
24.                 buckets = dirtyalloc
25.                 size := t.Bucket.Size_ * nbuckets
26.                 if t.Bucket.PtrBytes != 0 {
27.                         memclrHasPointers(buckets, size)
28.                 } else {
29.                         memclrNoHeapPointers(buckets, size)
30.                 }
31.         }
33.         if base != nbuckets {
34.                 //如果base和nbuckets的数量不同，说明预分配了溢出桶，需要设置溢出桶链表
35.         //指向第一个可用的预分配溢出桶，计算出溢出桶的起始位置
36.                 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))
37.         //最后一个预分配的溢出桶的位置
38.                 last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))
39.         //将最后一个溢出桶的指针设置为buckets，形成一个环形链表，用于后面的分配判断
40.                 last.setoverflow(t, (*bmap)(buckets))
41.         }
42.         return buckets, nextOverflow
43. }

复制代码

（2）标识map处在写的状态，而且懒创建桶。

1. func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
2.         //...
3.         if h == nil || h.count == 0 {
4.                 if err := mapKeyError(t, key); err != nil {
5.                         panic(err) // see issue 23734
6.                 }
7.                 return unsafe.Pointer(&zeroVal[0])
8.         }
9.         if h.flags&hashWriting != 0 {
10.                 fatal("concurrent map read and map write")
11.         }
12.         hash := t.Hasher(key, uintptr(h.hash0))
13.         m := bucketMask(h.B)
14.         b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))
15.         if c := h.oldbuckets; c != nil {
16.                 if !h.sameSizeGrow() {
17.                         // There used to be half as many buckets; mask down one more power of two.
18.                         m >>= 1
19.                 }
20.                 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))
21.                 if !evacuated(oldb) {
22.                         b = oldb
23.                 }
24.         }
25.         if c := h.oldbuckets; c != nil { //c!=nil，说明旧桶未完成迁移（rehash）
26.                 if !h.sameSizeGrow() { //是否是等量扩容
27.                         //如果不是等量扩容，调整 hash 掩码（mask）
28.                         m >>= 1
29.                 }
30.                 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))//计算旧桶地址
31.                 if !evacuated(oldb) { //检查旧桶是否已搬迁
32.                         b = oldb //未搬迁则数据有效
33.                 }
34.         }
35. bucketloop:
36.         for ; b != nil; b = b.overflow(t) {
37.                 for i := uintptr(0); i < bucketCnt; i++ {
38.                         if b.tophash[i] != top {
39.                                 if b.tophash[i] == emptyRest {
40.                                         break bucketloop
41.                                 }
42.                                 continue
43.                         }
44.                         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
45.                         if t.IndirectKey() {
46.                                 k = *((*unsafe.Pointer)(k))
47.                         }
48.                         if t.Key.Equal(key, k) {
49.                                 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
50.                                 if t.IndirectElem() {
51.                                         e = *((*unsafe.Pointer)(e))
52.                                 }
53.                                 return e
54.                         }
55.                 }
56.         }
57.         return unsafe.Pointer(&zeroVal[0])
58. }

复制代码

（3）获取当前key对应的桶的桶索引

1. if h == nil || h.count == 0 {
2.                 if err := mapKeyError(t, key); err != nil {
3.                         panic(err) // see issue 23734
4.                 }
5.                 return unsafe.Pointer(&zeroVal[0])
6.         }

复制代码

（4）若发现当前map处在扩容状态，则资助其渐进扩容。具体在下文中提及。

1. hashWriting  = 4 // a goroutine is writing to the map 4->100
2. if h.flags&hashWriting != 0 {
3.                 fatal("concurrent map read and map write")
4.         }

复制代码

（5）进行地址偏移，定位到具体的桶b

1. hash := t.Hasher(key, uintptr(h.hash0))
2.         m := bucketMask(h.B)
3.         b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))

复制代码

（6）计算tophash

1. if c := h.oldbuckets; c != nil { //c!=nil，说明旧桶未完成迁移（rehash）
2.                 if !h.sameSizeGrow() { //是否是等量扩容
3.                         //如果不是等量扩容，调整 hash 掩码（mask）
4.                         m >>= 1
5.                 }
6.                 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))//计算旧桶地址
7.                 if !evacuated(oldb) { //检查旧桶是否已搬迁
8.                         b = oldb //未搬迁则数据有效
9.                 }
10.         }

复制代码

（7）提前声明三个指针，用于指向存放kv对槽位

1. const emptyOne = 1
2. const evacuatedX = 2
3. const evacuatedY = 3
4. const evacuatedEmpty = 4
5. const minTopHash = 5
6. func evacuated(b *bmap) bool {
7.         h := b.tophash[0]
8.         return h > emptyOne && h < minTopHash
9. }

复制代码

（8）开启循环，和读流程雷同，外层遍历桶，内层遍历桶的每个位置。

1. top := tophash(hash)

复制代码

（9）若key的tophash和当前槽位的tophash不相同，则进行以下的检查：

• 若该槽位是空的，那么就将kv拟插入在这个位置（先记录），由于可能存在相同的key在背面的桶中。
  
• 若槽位当前位置tophash标识为emptyRest（0），则标识从当前槽位开始往后的槽位都是空的，就不消继续遍历了，直接退出bucketloop。（阐明可以插入在此位置了）
  

1. func tophash(hash uintptr) uint8 {
2.         top := uint8(hash >> (goarch.PtrSize*8 - 8))
3.         if top < minTopHash {
4.                 top += minTopHash
5.         }
6.         return top
7. }

复制代码

（10）否则阐明找到了相同的key，需要进行覆盖操纵。更新完成后跳到done，执行收尾流程。注意：会调用key.Equal方法具体检查要写的key和当前key是否一样，避免由于哈希冲突导致原来不同的kv对被错误的覆盖。

1. for ; b != nil; b = b.overflow(t) {
2.                 for i := uintptr(0); i < bucketCnt; i++ {
3.                         //...
4.                 }
5.         }

复制代码

（11）倘若没有相同的key，也没有剩余的空间了，则会考虑执行扩容模式，完成后再回到agian的位置重新桶定位以及遍历流程。

1. if b.tophash[i] != top {
2.                                 if b.tophash[i] == emptyRest {
3.                                         break bucketloop
4.                                 }
5.                                 continue
6.                         }

复制代码

触发扩容的条件：

• h.count+1 > loadFactor * 2^h.B：如果当前 map 达到负载因子上限，需要扩容。
  
• h.noverflow > threshold：如果 溢出桶过多，阐明冲突严重，也要扩容。
  
• h.growing()：检查是否 已经在扩容，如果已经在扩容，就不会触发新的扩容。
  

（12）若不执行扩容操纵，也没有找到插入的位置，则新创建一个溢出桶，将kv拟插入在溢出桶的第一个位置。

1. k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
2.                         if t.IndirectKey() {
3.                                 k = *((*unsafe.Pointer)(k))
4.                         }
5.                         if t.Key.Equal(key, k) {
6.                                 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
7.                                 if t.IndirectElem() {
8.                                         e = *((*unsafe.Pointer)(e))
9.                                 }
10.                                 return e
11.                         }

复制代码

创建新桶操纵如下：

1. return unsafe.Pointer(&zeroVal[0])

复制代码

这里存在一个非常容易混淆的点：请注意，在最开始的makeBucketArray方法中，我们提及到了只有最后一个溢出桶它才设置了overflow指针，对于前面的溢出桶，overflow指针是nil，以是可以根据这个特性来判断当前的溢出桶是不是最后一个溢出桶。
用图来表示，每个桶经过了多次溢出桶扩展后的表状态，如下：

（13）在拟插入位置现实插入kv

1. func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
2.         if h == nil {
3.                 panic(plainError("assignment to entry in nil map"))
4.         }
5.         //...
6.         if h.flags&hashWriting != 0 {
7.                 fatal("concurrent map writes")
8.         }
9.         hash := t.Hasher(key, uintptr(h.hash0))
11.         // Set hashWriting after calling t.hasher, since t.hasher may panic,
12.         // in which case we have not actually done a write.
13.         h.flags ^= hashWriting
15.         if h.buckets == nil {
16.                 h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1)
17.         }
19. again:
20.         bucket := hash & bucketMask(h.B)
21.         if h.growing() {
22.                 growWork(t, h, bucket)
23.         }
24.         b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
25.         top := tophash(hash)
27.         var inserti *uint8
28.         var insertk unsafe.Pointer
29.         var elem unsafe.Pointer
30. bucketloop:
31.         for {
32.                 for i := uintptr(0); i < bucketCnt; i++ {
33.                         if b.tophash[i] != top {
34.                                 if isEmpty(b.tophash[i]) && inserti == nil {
35.                                         inserti = &b.tophash[i]
36.                                         insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
37.                                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
38.                                 }
39.                                 if b.tophash[i] == emptyRest {
40.                                         break bucketloop
41.                                 }
42.                                 continue
43.                         }
44.                         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
45.                         if t.IndirectKey() {
46.                                 k = *((*unsafe.Pointer)(k))
47.                         }
48.                         if !t.Key.Equal(key, k) {
49.                                 continue
50.                         }
51.                         // already have a mapping for key. Update it.
52.                         if t.NeedKeyUpdate() {
53.                                 typedmemmove(t.Key, k, key)
54.                         }
55.                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
56.                         goto done
57.                 }
58.                 ovf := b.overflow(t)
59.                 if ovf == nil {
60.                         break
61.                 }
62.                 b = ovf
63.         }
65.         // Did not find mapping for key. Allocate new cell & add entry.
67.         // If we hit the max load factor or we have too many overflow buckets,
68.         // and we're not already in the middle of growing, start growing.
69.         if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
70.                 hashGrow(t, h)
71.                 goto again // Growing the table invalidates everything, so try again
72.         }
74.         if inserti == nil {
75.                 // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
76.                 newb := h.newoverflow(t, b)
77.                 inserti = &newb.tophash[0]
78.                 insertk = add(unsafe.Pointer(newb), dataOffset)
79.                 elem = add(insertk, bucketCnt*uintptr(t.KeySize))
80.         }
82.         // store new key/elem at insert position
83.         if t.IndirectKey() {
84.                 kmem := newobject(t.Key)
85.                 *(*unsafe.Pointer)(insertk) = kmem
86.                 insertk = kmem
87.         }
88.         if t.IndirectElem() {
89.                 vmem := newobject(t.Elem)
90.                 *(*unsafe.Pointer)(elem) = vmem
91.         }
92.         typedmemmove(t.Key, insertk, key)
93.         *inserti = top
94.         h.count++
96. done:
97.         if h.flags&hashWriting == 0 {
98.                 fatal("concurrent map writes")
99.         }
100.         h.flags &^= hashWriting
101.         if t.IndirectElem() {
102.                 elem = *((*unsafe.Pointer)(elem))
103.         }
104.         return elem
105. }

复制代码

（14）收尾流程，再次校验是否处在并发写，有则抛出fatal，否则将标记重置，然后退出。

1. if h == nil {
2.                 panic(plainError("assignment to entry in nil map"))
3.         }
4.         //...
5.         if h.flags&hashWriting != 0 {
6.                 fatal("concurrent map writes")
7.         }
8.         hash := t.Hasher(key, uintptr(h.hash0))

复制代码

2.4、map的删流程

2.4.1、删流程步骤总览

删流程步骤大致如下：

• 1、若表为nil或者不存在元素，则直接返回；若处在并发写则fatal
  
• 2、获取key的哈希因子，根据哈希值找到对应的桶
  
• 3、若表处在扩容阶段，则使用growWork辅助扩容
  
• 4、开始遍历查找要删除的元素，若没找到则直接退出查找流程，找到了则将值清为0值
  
• 5、若表的布局如：「值1——空——空——空——删除值——后全空——后全空」的布局，则需要向前回溯，将值1后的所有slot都置为emptyRest状态。
  
• 6、若删除后，表的count为0，则更新hash因子，避免哈希碰撞攻击。
  
• 7、再次校验是否处在并发写，处在将fatal，否则重置写标识
  

2.4.2、源码跟进mapdelete

1. func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {        //...        bucket := hash & bucketMask(h.B)        if h.growing() {
2.                 growWork(t, h, bucket)
3.         }        if h == nil || h.count == 0 {
4.                 if err := mapKeyError(t, key); err != nil {
5.                         panic(err) // see issue 23734
6.                 }
7.                 return unsafe.Pointer(&zeroVal[0])
8.         }        hashWriting  = 4 // a goroutine is writing to the map 4->100
9. if h.flags&hashWriting != 0 {
10.                 fatal("concurrent map read and map write")
11.         }        hash := t.Hasher(key, uintptr(h.hash0))
12.         m := bucketMask(h.B)
13.         b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))        bOrig := b        if c := h.oldbuckets; c != nil { //c!=nil，说明旧桶未完成迁移（rehash）
14.                 if !h.sameSizeGrow() { //是否是等量扩容
15.                         //如果不是等量扩容，调整 hash 掩码（mask）
16.                         m >>= 1
17.                 }
18.                 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))//计算旧桶地址
19.                 if !evacuated(oldb) { //检查旧桶是否已搬迁
20.                         b = oldb //未搬迁则数据有效
21.                 }
22.         }search:        for ; b != nil; b = b.overflow(t) {                for i := uintptr(0); i < bucketCnt; i++ {                        var inserti *uint8 //tophash拟插入位置
23. var insertk unsafe.Pointer //key拟插入位置
24. var elem unsafe.Pointer //value拟插入位置                        for {
25.                 for i := uintptr(0); i < bucketCnt; i++ {
26.                 //...
27.                 }
28.                 b = ovf
29.         }                        // 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 {                                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {                                        goto notLast                                }                        } else {                                if b.tophash[i+1] != emptyRest {                                        goto notLast                                }                        }                        k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
30.                         if t.IndirectKey() {
31.                                 k = *((*unsafe.Pointer)(k))
32.                         }
33.                         if !t.Key.Equal(key, k) {
34.                                 continue
35.                         }
36.                         // already have a mapping for key. Update it.
37.                         if t.NeedKeyUpdate() {
38.                                 typedmemmove(t.Key, k, key)
39.                         }
40.                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
41.                         goto done                // 如果达到负载因子上限，或者溢出桶过多，则扩容
42. if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
43.                 hashGrow(t, h)
44.                 goto again // Growing the table invalidates everything, so try again
45.         }        }        if inserti == nil {
46.                 // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
47.                 newb := h.newoverflow(t, b)
48.                 inserti = &newb.tophash[0]
49.                 insertk = add(unsafe.Pointer(newb), dataOffset)
50.                 elem = add(insertk, bucketCnt*uintptr(t.KeySize))
51.         }}

复制代码

（1）错误处置惩罚：当表为nil或者不存在元素，则直接返回；若处在并发写状态则fatal

1. bucket := hash & bucketMask(h.B)

复制代码

（2）获取key的hash，而且标识表为写状态

1. if h.growing() {
2.                 growWork(t, h, bucket)
3.         }

复制代码

（3）若表正在扩容，则调用growWork辅助扩容。通过hash值映射到对应的桶b。

1. if h == nil || h.count == 0 {
2.                 if err := mapKeyError(t, key); err != nil {
3.                         panic(err) // see issue 23734
4.                 }
5.                 return unsafe.Pointer(&zeroVal[0])
6.         }        hashWriting  = 4 // a goroutine is writing to the map 4->100
7. if h.flags&hashWriting != 0 {
8.                 fatal("concurrent map read and map write")
9.         }        hash := t.Hasher(key, uintptr(h.hash0))
10.         m := bucketMask(h.B)
11.         b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))        bOrig := b        if c := h.oldbuckets; c != nil { //c!=nil，说明旧桶未完成迁移（rehash）
12.                 if !h.sameSizeGrow() { //是否是等量扩容
13.                         //如果不是等量扩容，调整 hash 掩码（mask）
14.                         m >>= 1
15.                 }
16.                 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))//计算旧桶地址
17.                 if !evacuated(oldb) { //检查旧桶是否已搬迁
18.                         b = oldb //未搬迁则数据有效
19.                 }
20.         }

复制代码

（4）进入桶的遍历，外层遍历桶，内层遍历每个kv对

1. // initialize Hmap
2.         if h == nil {
3.                 h = new(hmap)
4.         }

复制代码

（5）若当前槽位的tophash和需要查找的不相同，则检查背面是否尚有元素；有元素就继续进行查找，没有就直接退出，表示想删除的元素不存在。

1. var inserti *uint8 //tophash拟插入位置
2. var insertk unsafe.Pointer //key拟插入位置
3. var elem unsafe.Pointer //value拟插入位置

复制代码

（6）否则，阐明找到了对应的key，进行删除操纵，具体包罗了：

• 查找key并找到存储位置
  
• 清除 key 和 value（包罗直接清零或 nil 指针）。
  
• 更新 tophash，标记该槽位为空（EmptyOne）。
  

注意：会调用key.Equal方法具体检查要删除的key和当前key是否一样，避免由于哈希冲突导致原来不同的kv对被错误的删除。

1. for {
2.                 for i := uintptr(0); i < bucketCnt; i++ {
3.                 //...
4.                 }
5.                 b = ovf
6.         }

复制代码

（7）检查当前删除的桶的元素是否是桶的最后一个元素：

• 如果，若该桶的背面还存在溢出桶，而且溢出桶非空则跳过清理环节，进入收尾阶段
  
• 若不是，检查背面是否尚有元素，有元素也跳过清理环节。（通过检查下一个slot的标识是否为emptyRest）
  

1. if b.tophash[i] != top {
2.                                 if isEmpty(b.tophash[i]) && inserti == nil {
3.                                         inserti = &b.tophash[i]
4.                                         insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
5.                                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
6.                                 }
7.                                 if b.tophash[i] == emptyRest {
8.                                         break bucketloop
9.                                 }
10.                                 continue
11.                         }

复制代码

否则，阐明背面没有更多的元素了，需要向前回溯，将最后一个元素的槽位背面的所有槽位都设置为emptyRest状态，优化将来的流程。
回溯流程：

• 先将当前桶从当前的删除元素一个个往前走，遇到是emptyOne的就修改为emptyRest
  
• 当到达第一个元素而且也为空时，回溯到上一个桶的末尾，重复流程
  
• 遇到非空元素，完成所有回溯而且退出。
  

1. k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
2.                         if t.IndirectKey() {
3.                                 k = *((*unsafe.Pointer)(k))
4.                         }
5.                         if !t.Key.Equal(key, k) {
6.                                 continue
7.                         }
8.                         // already have a mapping for key. Update it.
9.                         if t.NeedKeyUpdate() {
10.                                 typedmemmove(t.Key, k, key)
11.                         }
12.                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
13.                         goto done

复制代码

（8）收尾流程，将map的元素计数器count-1，若count为0，则更新哈希因子。

1. // 如果达到负载因子上限，或者溢出桶过多，则扩容
2. if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
3.                 hashGrow(t, h)
4.                 goto again // Growing the table invalidates everything, so try again
5.         }

复制代码

为什么要更新哈希因子？
让攻击者无法使用相同的哈希因子 h.hash0 构造出一组导致严重哈希碰撞的 key，从而保护 map 免受拒绝服务（DoS）攻击。

（9）最后的校验是否处在并发写状态，是则fatal，然后再更新状态标识

1. if inserti == nil {
2.                 // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
3.                 newb := h.newoverflow(t, b)
4.                 inserti = &newb.tophash[0]
5.                 insertk = add(unsafe.Pointer(newb), dataOffset)
6.                 elem = add(insertk, bucketCnt*uintptr(t.KeySize))
7.         }

复制代码

3、扩容机制

3.1、扩容类型

Gomap的扩容方式分为两种：

• 等量扩容（Same-Size-Grow）：如果map的溢出桶过多，导致查找性能下降，阐明KV分布不匀称，此时就会触发等量扩容，哈希表的桶数不会改变，但会重新分配K-V对的位置，目的是减少溢出桶的数量，增长KV的密度，让数据能平均分布。
  
• 增量扩容（Double-Size-Grow）：如果负载因子超标「count/2^B > loadFactor」，即KV对的数目凌驾了肯定上限，就会触发增量扩容，使得Buckets数量翻倍，让所有的KV对重新分配在新的桶数组中，目的是减少K-V对的密度，降低每个桶的KV数量，优化查询时间。
  

为什么说等量扩容是增长密度呢？
我们想，既然count是公道的，但是当前map导致了溢出桶过多，那么只可能是经过了多次删除操纵，导致出现了很多空位，比方「A——空——空——空——B」，如许子每次查找就很耗时了，于是等量扩容需要重新分配KV对的位置变为「A——B」，让数据更加紧凑。

3.2、扩容触发

在之前的写流程中，提及到以下代码会触发map的扩容：

1. func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
2.         var ovf *bmap
3.     //若表存在预分配溢出桶，则直接使用预分配的溢出桶。
4.         if h.extra != nil && h.extra.nextOverflow != nil {
5.                 if ovf.overflow(t) == nil {
6.             // 不是最后一个预分配的溢出桶，直接移动 `nextOverflow` 指针
7.                         h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.BucketSize)))
8.                 } else {
9.              // 这是最后一个预分配的溢出桶，重置 overflow 指针
10.                         ovf.setoverflow(t, nil)
11.                         h.extra.nextOverflow = nil
12.                 }
13.         } else {
14.         //创建一个新的溢出桶
15.                 ovf = (*bmap)(newobject(t.Bucket))
16.         }
17.     //更新 h.noverflow 计数，跟踪 map 目前有多少个溢出桶。
18.         h.incrnoverflow()
19.         if t.Bucket.PtrBytes == 0 { //如果map只存储基本数据类型
20.                 h.createOverflow() //创建overflow记录表
21.                 *h.extra.overflow = append(*h.extra.overflow, ovf) //记录新的溢出桶
22.         }
23.         b.setoverflow(t, ovf) //把ovf连接到b这个桶的overflow指针
24.         return ovf
25. }

复制代码

只有当map不处在扩容中，而且满足以下两个条件之一，触发扩容：
<ul>负载因子超标：当KV对的数目凌驾桶的数目，而且「KV对数目/桶数 > 负载因子」时，发生扩容

1.         // store new key/elem at insert position
2.         if t.IndirectKey() {
3.                 kmem := newobject(t.Key)
4.                 *(*unsafe.Pointer)(insertk) = kmem
5.                 insertk = kmem
6.         }
7.         if t.IndirectElem() {
8.                 vmem := newobject(t.Elem)
9.                 *(*unsafe.Pointer)(elem) = vmem
10.         }
11.         typedmemmove(t.Key, insertk, key)
12.         *inserti = top
13.         h.count++

复制代码

溢出桶过多：当溢出桶数量>桶数组的数量（B最大取15），则发生扩容

1. done:
2.         if h.flags&hashWriting == 0 {
3.                 fatal("concurrent map writes")
4.         }
5.         h.flags &^= hashWriting
6.         if t.IndirectElem() {
7.                 elem = *((*unsafe.Pointer)(elem))
8.         }
9.         return elem

复制代码

（8）通过读流程的mapaccessK方法来读取这个K-V对，通过迭代器hiter的key、value指针进行接收，用于对用户的遍历操纵进行响应。

1. func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
2.         //...
3.         if h == nil || h.count == 0 {
4.                 if err := mapKeyError(t, key); err != nil {
5.                         panic(err) // see issue 23734
6.                 }
7.                 return
8.         }
9.         if h.flags&hashWriting != 0 {
10.                 fatal("concurrent map writes")
11.         }
13.         hash := t.Hasher(key, uintptr(h.hash0))
15.         // Set hashWriting after calling t.hasher, since t.hasher may panic,
16.         // in which case we have not actually done a write (delete).
17.         h.flags ^= hashWriting
19.         bucket := hash & bucketMask(h.B)
20.         if h.growing() {
21.                 growWork(t, h, bucket)
22.         }
23.         b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
24.         bOrig := b
25.         top := tophash(hash)
26. search:
27.         for ; b != nil; b = b.overflow(t) {
28.                 for i := uintptr(0); i < bucketCnt; i++ {
29.                         if b.tophash[i] != top {
30.                                 if b.tophash[i] == emptyRest {
31.                                         break search
32.                                 }
33.                                 continue
34.                         }
35.                         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
36.                         k2 := k
37.                         if t.IndirectKey() {
38.                                 k2 = *((*unsafe.Pointer)(k2))
39.                         }
40.                         if !t.Key.Equal(key, k2) {
41.                                 continue
42.                         }
43.                         // Only clear key if there are pointers in it.
44.                         if t.IndirectKey() {
45.                                 *(*unsafe.Pointer)(k) = nil
46.                         } else if t.Key.PtrBytes != 0 {
47.                                 memclrHasPointers(k, t.Key.Size_)
48.                         }
49.                         e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
50.                         if t.IndirectElem() {
51.                                 *(*unsafe.Pointer)(e) = nil
52.                         } else if t.Elem.PtrBytes != 0 {
53.                                 memclrHasPointers(e, t.Elem.Size_)
54.                         } else {
55.                                 memclrNoHeapPointers(e, t.Elem.Size_)
56.                         }
57.                         b.tophash[i] = emptyOne
58.                         // If the bucket now ends in a bunch of emptyOne states,
59.                         // change those to emptyRest states.
60.                         // It would be nice to make this a separate function, but
61.                         // for loops are not currently inlineable.
62.                         if i == bucketCnt-1 {
63.                                 if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
64.                                         goto notLast
65.                                 }
66.                         } else {
67.                                 if b.tophash[i+1] != emptyRest {
68.                                         goto notLast
69.                                 }
70.                         }
71.                         for {
72.                                 b.tophash[i] = emptyRest
73.                                 if i == 0 {
74.                                         if b == bOrig {
75.                                                 break // beginning of initial bucket, we're done.
76.                                         }
77.                                         // Find previous bucket, continue at its last entry.
78.                                         c := b
79.                                         for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
80.                                         }
81.                                         i = bucketCnt - 1
82.                                 } else {
83.                                         i--
84.                                 }
85.                                 if b.tophash[i] != emptyOne {
86.                                         break
87.                                 }
88.                         }
89.                 notLast:
90.                         h.count--
91.                         // Reset the hash seed to make it more difficult for attackers to
92.                         // repeatedly trigger hash collisions. See issue 25237.
93.                         if h.count == 0 {
94.                                 h.hash0 = uint32(rand())
95.                         }
96.                         break search
97.                 }
98.         }
100.         if h.flags&hashWriting == 0 {
101.                 fatal("concurrent map writes")
102.         }
103.         h.flags &^= hashWriting
104. }

复制代码

5、结语

感谢观看阅读，如果有什么疑问可以在批评区一起讨论。本篇博客参考了小徐先生的文章，也是读者跟随其思路学习的笔记记录，推荐大家去看原文，一起深入源码学习，链接在下方：
Golang map 实现原理

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。