• Go语言map底层分析

    哈希表的实现方式有多种，比如哈希表、红黑树等。Golang的map底层是用哈希表实现的，在介绍Golang map的实现之前首先介绍一下哈希表的两种实现方式：

    1、哈希表的两种实现方式

    1.1、开放寻址法

            开放寻址法，底层是一个数组，每个数组都存放一个键值对，空闲的地方就是没有放键值对的地方。首先看如何插入：key-val首先经过一个哈希函数将key值进行哈希得到一个大的数字，然后将其对数组的长度取模，这样它就落在了数组中的一个位置。如果得到的位置没有被占用，那么就直接存放在对应位置。如果已经被占用了，那么就向后寻找一个槽，直到找到空闲的槽。读取也是同样的步骤，先哈希再取模，然后去对应的槽位寻找，如果没有找到，就向后找。

    在这里插入图片描述

     

    1.2、拉链法

            拉链法前两个步骤一样，也是先哈希再取模，然后会落到数组的一个槽中（每个槽并不存放k-v数据，它们都是指针），然后使用链表将k-v连接起来。查询的时候，获取槽位后，遍历链表来查询。

    在这里插入图片描述

     

    2、Go语言map源码分析

    Go语言的map是用拉链法来实现的，但是与上面所说的也有所不同。

    实现map的文件为runtime包下的map.go

    注意: 使用的go sdk的版本为：go1.18

    2.1 map的结构

    map的底层为一个结构体，结构体如下：

    // Go map 的底层结构体表示
type hmap struct {
    count     int    // map中键值对的个数，使用len()可以获取 
	flags     uint8
	B         uint8  // 哈希桶的数量的log2，比如有8个桶，那么B=3
	noverflow uint16 // 溢出桶的数量
	hash0     uint32 // 哈希种子

	buckets    unsafe.Pointer // 指向哈希桶数组的指针，数量为 2^B 
	oldbuckets unsafe.Pointer // 扩容时指向旧桶的指针，当扩容时不为nil 
	nevacuate  uintptr        

	extra *mapextra  // 可选字段
}

const (
	bucketCntBits = 3
	bucketCnt     = 1 << bucketCntBits     // 桶数量 1 << 3 = 8
)

// Go map 的一个哈希桶，一个桶最多存放8个键值对
type bmap struct {
    // tophash存放了哈希值的最高字节
	tophash [bucketCnt]uint8
    
    // 在这里有几个其它的字段没有显示出来，因为k-v的数量类型是不确定的，编译的时候才会确定
    // keys: 是一个数组，大小为bucketCnt=8，存放Key
    // elems: 是一个数组，大小为bucketCnt=8，存放Value
    // 你可能会想到为什么不用空接口，空接口可以保存任意类型。但是空接口底层也是个结构体，中间隔了一层。因此在这里没有使用空接口。
    // 注意：之所以将所有key存放在一个数组，将value存放在一个数组，而不是键值对的形式，是为了消除例如map[int64]所需的填充整数8（内存对齐）
    
    // overflow: 是一个指针，指向溢出桶，当该桶不够用时，就会使用溢出桶
}


    • 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

    map结构的图表示为如下：

            map的底层为hmap结构体，其中包含了很多字段，buckets是一个数组，大小是2的B次方个。数组中的每一个是一个bmap结构体的哈希桶，bmap包含了4个字段，后面三个字段在编译时才能确定。tophash、keys、elems都是大小为8的数组，它们每个元素一一对应。tophash存放哈希值的最高字节，keys存放了键，elems存放数据。每个桶只能存放最多8个键值对，因此当某个桶不够用时，就会使用溢出桶，overflow指向下一个溢出桶。

            Go语言的map并没有将键值对一起存放，而是将键值分开存放。是因为如果存放在一起可能需要内存对齐，会导致空间的浪费，存放在一起会使内存更紧凑，也不会损失什么性能。

    在这里插入图片描述

     

    2.2 map的初始化

    我们在使用map的时候的初始化方式主要有两种：一种是使用字面量初始化，一种是使用make

    m1 := map[string]int{"a" : 1, "b" : 2}
m2 := make(map[string]int, 10)

    • 1
    • 2

    接下来我们看这两种初始化方式在底层到底是怎么做的：

    首先看一段代码，使用 go build -gcflags -S main.go 来生成汇编代码

    // main.go
package main

import "fmt"

func main() {
	m1 := map[string]int{"a": 1, "b": 2}
	m2 := make(map[int]string, 10)
	fmt.Println(m1, m2)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    生成的汇编文件的一段如下：

    在这里插入图片描述

            我们可以看到，这两种初始化方式分别调用了runtime.makemap_small() 和 runtime.makemap()，但不管是字面量初始化还是make初始化，如果初始化的键值对数量比较小就会使用makemap_small，否则就使用makemap()。经过测试，当初始化的数量大于8时，也就是字面量中的键值对数量大于8或make中的第二个参数大于8，就会使用makemap()来进行初始化。

    接下来我们找到这两个函数（其中省略了一些暂时不关注的内容）：

    // makemap_small 实现了Go map的构造
// make(map[k]v, hint) 当hint最多为bucketCnt=8时，就会使用该函数来构造map
func makemap_small() *hmap {
    // 就是new了一个hmp的结构体，随机生成hash0，然后返回它的指针
	h := new(hmap)
	h.hash0 = fastrand()
	return h
}


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

	// 构造hmap结构体
	if h == nil {
		h = new(hmap)
	}
	h.hash0 = fastrand()

	// 根据传入的数据的数量来算出需要的B的大小
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

    // 分配哈希桶的内存空间
    // 如果B为0，那么将会进行延迟分配
	if h.B != 0 {
		var nextOverflow *bmap
        /* 
        	创建哈希桶以及一些溢出桶，假设创建了8个桶，那么只能存放 8 * 8 = 64对键值，如果再存放的话，就会溢出，因此会多创建一些溢出桶
        	这些溢出桶会存放在extra字段中
        */
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}


type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// 保存了下一个可用的溢出桶的地址
	nextOverflow *bmap
}


    • 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

    makemap_small: 我们可以看到，它直接new了一个hmap，然后返回hmap的指针。与Go中的切片不同，切片是返回一个结构体，而map返回的是结构体的指针。

    makemap: new了一个hmap的结构体，然后根据传入的数据的数量来算出需要的B的数量。然后进行哈希桶的内存分配，它还会多创建一些溢出桶，extra结构体的nextoverflow字段保存了这些溢出桶，最后返回hmap的指针。

    图示如下：

            在创建map的时候，首先要确定B，假设B为3，那么桶的数量就为2^3=8，其次，也会创建出一些溢出桶。然后创建mapextra类型的结构体，其中的nextoverflow保存了下一个可用的溢出桶的地址。

    假设位于一号槽的桶已经用满了，那么就会使用extra字段来寻找一个新的可用的溢出桶，然后使用bmap中的overflow字段指向溢出桶来组成一个链表。

    在这里插入图片描述

    map字面量赋值的两种方式

    • 当元素少于25个时，转化为简单赋值：

    在这里插入图片描述

    • 元素多于25个时，转化为循环赋值：

    在这里插入图片描述

     

    2.3 map的访问

            每个桶中的tophash没有保存哈希值的全部，而是保存了高八位，是为了快速遍历。

    在访问map时有两种返回值：第一种，只获取值；第二种，获取值和是否查询到

    val := m["a"]
val, ok := m["a"]

    • 1
    • 2

    源码如下（其中省略了一目前些不太关注的代码）：

    // mapaccess1 返回一个指针，这个指针不会为nil，如果key不存在，则返回该值对应的0值
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    
	...
    
    // 如果h为nil 或者数量为0，如果为说明map没有初始化，可能会panic
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
         // 返回对应的0值
		return unsafe.Pointer(&zeroVal[0])
	}
    // 防止map并发读写
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
    // 对key和hash0计算哈希值
	hash := t.hasher(key, uintptr(h.hash0))
    
	...
    // 计算tophash
	top := tophash(hash)
bucketloop:
    // 遍历哈希桶以及溢出桶
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
            // 匹配tophash成功后，计算key的地址
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
            // 比较是否是要找的key
			if t.key.equal(key, k) {
                // 如果是，则计算val的地址
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
                // 返回val
				return e
			}
		}
	}
    // 返回对应的0值
	return unsafe.Pointer(&zeroVal[0])
}

// mapaccess2与mapaccess逻辑相同，只是多了个bool的返回值，如果没有找到就为false，否则为true
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {

    ...
    
}

    • 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

    假设要查找的键为"a"

    • 首先要计算桶号：

      将a与hash0一同进行哈希运算，输出一长串哈希值。然后根据B来取二进制哈希值的后B位，得到的值即为桶号，假设B为3，那么取后三位为010b也就是2，那么桶号就是2

    在这里插入图片描述

    • 然后计算tophash

      取哈希值的高八位作为tophash，16进制为0x5c

    在这里插入图片描述

    • 匹配

      算出tophash后，再tophash数组中进行一一匹配，如果没有找到，则查看overflow是否为nil，不为nil则匹配溢出桶中的tophash，直到匹配成功或者到最后也找不到。如果找到了，也不一定是我们想要的，因为如果哈希碰撞的比较厉害，一个桶中的tophash可能有相等的，因此需要再进行key值的比较，如果相同，就找到了相匹配的键值对。如果key值不相同，就继续从tophash中找。

    在这里插入图片描述

     

    2.4 map的插入

            map的插入首先要查找要插入的key是否已经存在，如果存在就更新新的value。如果不存在，就插入一条记录。

    源码如下：

    func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// 如果没有初始化就直接panic
    if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
	
    ...
    // 防止并发写入
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
    // 计算哈希值
	hash := t.hasher(key, uintptr(h.hash0))

    // buckets内存空间的滞后申请
	if h.buckets == nil {
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}

	...
    
bucketloop:
	for {
        // 首先要查询key是否已经存在
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				
                ...
                
				continue
			}
 			
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if !t.key.equal(key, k) {
				continue
			}
			// key已经存在，更新对应的值  
			if t.needkeyupdate() {
				typedmemmove(t.key, k, key)
			}
			elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
			goto done
		}
		ovf := b.overflow(t)
		if ovf == nil {
			break
		}
		b = ovf
	}

    ...
    
	// 没有找到该key，分配一个新的地方存放
    // 存放新的键值对
	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)
	*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
}

    • 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

     

    2.5 map的删除

            map的删除首先要查找key值是否存在，如果存在，就删除key-val，如果val中存在指针，就需要删除，因为需要解除对该指针的引用，以便垃圾回收器回收垃圾，否则就不用删除。

    func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	
    ...
    
	// 计算哈希值 
	hash := t.hasher(key, uintptr(h.hash0))
	
    ...
	
	top := tophash(hash)
search:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break search
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			k2 := k
			if t.indirectkey() {
				k2 = *((*unsafe.Pointer)(k2))
			}
			if !t.key.equal(key, k2) {
				continue
			}
            // 到此为止，说明已经找到了key-val
			// 删除key-val，如果val中没有指针，就只删除key，因此要取消对指针的引用，这样垃圾回收器才能回收到
			if t.indirectkey() {
				*(*unsafe.Pointer)(k) = nil
			} else if t.key.ptrdata != 0 {
				memclrHasPointers(k, t.key.size)
			}
			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
			
            ...
            
		notLast:
			h.count--
			// Reset the hash seed to make it more difficult for attackers to
			// repeatedly trigger hash collisions. See issue 25237.
			if h.count == 0 {
				h.hash0 = fastrand()
			}
			break search
		}
	}


}

    • 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

     

    2.6 map的清空

            map的清空方式有两种：1、make一个新的map；2、使用for range一个一个删除

    m1 = make(map[string]int)

for k := range m1 {
    delete(m1, k)
}

    • 1
    • 2
    • 3
    • 4
    • 5

    第一种会解除上一个map的引用，然后重新创建一个map，垃圾回收器会自动回收旧的map。

    第二种会被go的编译器进行优化，调用mapclear函数。

    在这里插入图片描述

    mapclear的源码如下：

    就是重置了其中的一些字段，然后新建了一个bucket数组

    func mapclear(t *maptype, h *hmap) {
	
    ...

	if h == nil || h.count == 0 {
		return
	}


	h.flags ^= hashWriting

	h.flags &^= sameSizeGrow
	h.oldbuckets = nil
	h.nevacuate = 0
	h.noverflow = 0
	h.count = 0

	h.hash0 = fastrand()

	// Keep the mapextra allocation but clear any extra information.
	if h.extra != nil {
		*h.extra = mapextra{}
	}

	// makeBucketArray clears the memory pointed to by h.buckets
	// and recovers any overflow buckets by generating them
	// as if h.buckets was newly alloced.
	_, nextOverflow := makeBucketArray(t, h.B, h.buckets)
	if nextOverflow != nil {
		// If overflow buckets are created then h.extra
		// will have been allocated during initial bucket creation.
		h.extra.nextOverflow = nextOverflow
	}

	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

    那么哪个的速度更快呢？我们可以进行一个基准测试：

    package test

import (
	"testing"
)

const C = 1000

func BenchmarkMapDelete1(b *testing.B) {
	m := make(map[int]int, C)
	for i := 0; i < b.N; i++ {
		for i := 0; i < C; i++ {
			m[i] = i
		}
		m = make(map[int]int, C)
	}
}

func BenchmarkMapDelete2(b *testing.B) {
	m := make(map[int]int, C)
	for i := 0; i < b.N; i++ {
		for i := 0; i < C; i++ {
			m[i] = i
		}
		for k := range m {
			delete(m, k)
		}
	}
}


    • 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

    C = 1000, 10000, 100000 时的测试数据如下

    goos: windows
goarch: amd64
pkg: code/source_code_analyse/test
cpu: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
# 1000
BenchmarkMapDelete1-8              40911             29330 ns/op
BenchmarkMapDelete2-8              55832             22061 ns/op
PASS
ok      code/source_code_analyse/test   3.146s
# 10000
BenchmarkMapDelete1-8               3655            302420 ns/op
BenchmarkMapDelete2-8               5011            247473 ns/op
PASS
ok      code/source_code_analyse/test   2.585s
# 100000
BenchmarkMapDelete1-8                302           3923456 ns/op
BenchmarkMapDelete2-8                378           3239029 ns/op
PASS
ok      code/source_code_analyse/test   3.320s

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    可以看到，使用for range的方式更快。

     

    2.7 总结

    • Go语言使用拉链法实现了map
    • 每一个桶中存储键值哈希的高八位，key和value的数组
    • 桶超过8个数据，就会存储到溢出桶中

     

    3 map的扩容

    map为什么需要扩容？

            首先就是当可用空间不足时就需要扩容。其次当哈希碰撞比较严重时，很多数据都会落在同一个桶中，那么就会导致越来越多的溢出桶被链接起来。这样的话，查找的时候最坏的情况就是要遍历整个链表，时间复杂度很高，效率很低。而且当删除了很多元素后，可能会导致虽然有很多溢出桶，但是桶中的元素很稀疏。

    map扩容的时机：

    • 达到最大的负载因子
    • 溢出桶的数量太多

    在mapassign中会判断是否要扩容：

    func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
 
    ...
    
    // 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.
    // 如果达到了最大的负载因子或者有太多的溢出桶
    // 或是是已经在扩容中
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again // Growing the table invalidates everything, so try again
	}
    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • map溢出桶太多时会导致严重的性能下降
    • runtime.mapassign()可能会触发扩容的情况：
      • 负载因子超过6.5（平均每个槽6.5个key）
      • 使用了太多的溢出桶（溢出桶超过了普通桶）

    map扩容的类型：

    • 等量扩容：数据不多但是溢出桶太多了（整理）
    • 翻倍扩容：数据太多了

    等量扩容，溢出桶太多了，导致查询效率低。扩容时，桶的数量不增加。

    翻倍扩容，每个桶的k-v太多了，需要增加普通桶的数量。

    3.1 map扩容的步骤

    步骤1：

    • 创建一组新桶
    • oldbuckets指向原有的桶数组
    • buckets指向新的桶的数组
    • map标记为扩容状态

    如下图：

    在这里插入图片描述

    代码如下：

    func hashGrow(t *maptype, h *hmap) {
	// 计算出要增加的新桶的数量，如果是溢出桶太多，就等量扩容
	bigger := uint8(1)
	if !overLoadFactor(h.count+1, h.B) {
		bigger = 0
		h.flags |= sameSizeGrow
	}
    // 记录旧的桶的数组
	oldbuckets := h.buckets
    // 创建新的桶
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
    
	// 更新其它字段
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets    // oldbuckets指向旧的桶
	h.buckets = newbuckets
	h.nevacuate = 0
	h.noverflow = 0

    // 更新extra字段，使其指向新的桶的溢出桶
	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
		h.extra.overflow = nil
	}
	if nextOverflow != nil {
		if h.extra == nil {
			h.extra = new(mapextra)
		}
		h.extra.nextOverflow = nextOverflow
	}

}

    • 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

    步骤2：迁移数据

    • 将所有的数据从旧桶驱逐到新桶
    • 采用渐进式驱逐
    • 每次操作一个旧桶时，将旧桶数据驱逐到新桶
    • 读取时不进行驱逐，只判断读取新桶还是旧桶

    假设原来的桶的数量为4，那么B为2。当进行扩容后，假设桶的数量为8，B为3。那么这里就体现出了使用B的智慧，扩容后B为3，那么取哈希值的二进制后三位就有两种情况：010b和110b，分别是2和6。所以原来二号桶中的数据就会分布到新桶数组的2号和6号桶中。

    在这里插入图片描述

    在这里插入图片描述

    源码为：

    func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
 
    ...
   
again:
    bucket := hash & bucketMask(h.B)  // 计算桶号 hash & (1 << h.B - 1), 假设B为3，那么就是 hash & (7) ==> hash & 111b，也就是取后三位
    if h.growing() {
        // 调用growWork进行扩容
        growWork(t, h, bucket)
    }
    
    ...
    
}

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 驱逐
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    // 计算要驱逐的旧桶的地址
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
    // 计算增长之前的桶数
	newbit := h.noldbuckets()
	if !evacuated(b) {
        
        // x y 包含了疏散的目的地(低和高).
		var xy [2]evacDst
        // x为低疏散目的地，比如在旧桶中为2，在新桶中也为2
        // x.b是桶的地址  x.k是keys数组的地址  x.e是elems的地址
		x := &xy[0]
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		x.e = add(x.k, bucketCnt*uintptr(t.keysize))
		
        // 如果不是等量扩容，旧桶的数据还会被疏散到其它桶，比如旧桶为2，新桶为110b，也就是6
		if !h.sameSizeGrow() {
			/* y为高疏散的目的地
			   newbit = h.noldbuckets()
			   func (h *hmap) noldbuckets() uintptr {
                oldB := h.B
                if !h.sameSizeGrow() {
                    oldB--
                }
                return bucketShift(oldB)
            }
            假设扩容前B=2， 扩容后B=3， 那么newbit = 1 << (3--) = 4
            oldbucket + newbit = 6
            */
			y := &xy[1]
			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			y.k = add(unsafe.Pointer(y.b), dataOffset)
			y.e = add(y.k, bucketCnt*uintptr(t.keysize))
		}
		// 开始疏散工作
		for ; b != nil; b = b.overflow(t) {
            // 要迁移的旧桶的keys数组的开始地址
			k := add(unsafe.Pointer(b), dataOffset)
            // 要迁移的旧桶的elems数组的开始地址
			e := add(k, bucketCnt*uintptr(t.keysize))
            // 循环将桶中的数据进行疏散迁移
			for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
				top := b.tophash[i]
				if isEmpty(top) {
					b.tophash[i] = evacuatedEmpty
					continue
				}
				if top < minTopHash {
					throw("bad map state")
				}
				k2 := k
				if t.indirectkey() {
					k2 = *((*unsafe.Pointer)(k2))
				}
				var useY uint8
				if !h.sameSizeGrow() {
                    // 计算hash来决定将k-v存放到x还是y中
					hash := t.hasher(k2, uintptr(h.hash0))
					
                    ...
                    
						if hash&newbit != 0 {
							useY = 1
						}
					
				}

				if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
					throw("bad evacuatedN")
				}

				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
                // 根据计算出的useY来决定将k-v放入哪个桶
				dst := &xy[useY]                 
				
				if dst.i == bucketCnt {
					dst.b = h.newoverflow(t, dst.b)
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
				}
                // 迁移数据
				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
				if t.indirectkey() {
					*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
				} else {
					typedmemmove(t.key, dst.k, k) // copy elem
				}
				if t.indirectelem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
				} else {
					typedmemmove(t.elem, dst.e, e)
				}
				dst.i++
				// These updates might push these pointers past the end of the
				// key or elem arrays.  That's ok, as we have the overflow pointer
				// at the end of the bucket to protect against pointing past the
				// end of the bucket.
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.e = add(dst.e, uintptr(t.elemsize))
			}
		}
		// Unlink the overflow buckets & clear key/elem to help GC.
		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
			// Preserve b.tophash because the evacuation
			// state is maintained there.
			ptr := add(b, dataOffset)
			n := uintptr(t.bucketsize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}

	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}

    • 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

    步骤3：

    • 所有旧桶驱逐完成后，回收oldbuckets

    3.2 总结

    • 负载因子太大或者溢出桶太多，会触发map扩容
    • ”扩容”可能并不是增加桶数，而是整理
    • map扩容采用渐进式，桶被操作时才会重新分配
  • 相关阅读:
    不同的子序列问题I
    C++入门 —— 命名空间
    串级PID为什么外环输出时内环的期望值
    C++入门笔记
    【Java设计模式 思想原则重构】设计思想、设计原则、重构总结
    线索二叉树的建立与遍历
    Ap01- 自适应 AutoSAR概述和简介
    【C++】set和map
    TypeScript type 和 interface区别
    2023年数维杯数学建模C题宫内节育器的生产求解全过程文档及程序
  • 原文地址：https://blog.csdn.net/Peerless__/article/details/125458742