Golang源码分析 - map哈希表

Map结构体

Go中 map 底层实现数据结构是 哈希表 而非 C++中的 红黑树，这样设计的目的是为了加快查找过程，而如果使用红黑树的话由于在插入和删除的过程中需要对树结构进行旋转而导致性能降低，而且查找的过程中需要遍历树，这相对于哈希表实现的map来说是很慢的，不过基于哈希表实现的map也有一个缺点就是占用内存高。

哈希表实现的map重点是 哈希函数 的选择，哈希函数映射的结果一定要尽可能均匀，结果不均匀的哈希函数会带来更多的 哈希冲突 以和更差的读写性能。

哈希冲突一般解决方法为以下几种：

  • 开放寻址法
  • 拉链法，即数组+链表/红黑树/跳表

由于个人能力有限，在分析Go源码的过程中难免会出现一些错误，还望各位指出～😘

Golang中的map源码位于 src/runtime/map.go，其几个重要的数据结构：

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
// 哈希表 hash map
type hmap struct {
    // 哈希表中key-value数量
	count     int 
	flags     uint8
    B         uint8  // B = log_2(buckets)
    // 溢出桶里bmap的数量
	noverflow uint16
    // 随机哈希种子
	hash0     uint32 

    // 可以看作 buckets []*bmap
    buckets    unsafe.Pointer // 共 2^B 个桶 
    // 在map扩容时，oldbuckets保存之前半数的buckets
	oldbuckets unsafe.Pointer 
	nevacuate  uintptr

	// 这个字段是为了优化GC扫描而设计的。当key和value均不包含指针，并且都可以inline时使用。extra是指向mapextra类型的指针。
    extra *mapextra
}

bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits = 8

// 每个哈希桶bmap结构最多存放8组键值对槽位，注意 src/runtime/map.go bmap结构体只有 tophash 字段
type bmap struct {
    tophash [bucketCnt]uint8 // 保存高八位 hash，快速比较
    keys [bucketCnt] keytype // 保存键
    elems [bucketCnt] valuetype // 保存键值
  
    // 存放了对应使用的溢出桶hmap.extra.overflow里的bmap的地址
    // 将正常桶hmap.buckets里的bmap关联上溢出桶hmap.extra.overflow的bmap
    // 也就是 *bmap
    overflow unsafe.Pointer
}

// 溢出桶信息
type mapextra struct {
    // 如果 key 和 value 都不包含指针，并且可以被 inline(<=128 字节)
    // 就使用 hmap的extra字段 来存储 overflow buckets，这样可以避免 GC 扫描整个 map
    // 然而 bmap.overflow 也是个指针。这时候我们只能把这些 overflow 的指针
    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
    // overflow 包含的是 hmap.buckets 的 overflow 的 buckets
    // oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
    // 参考：https://liangtian.me/post/go-map
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // 指向预分配的溢出桶里下一个可以使用的bmap
    // nextOverflow=nil，表示预分配的溢出桶已经满了
	nextOverflow *bmap
}

字面量

在使用字面量初始化map时，如果键值的个数小于25个，Go则将使用如下方式进行初始化：

1
2
3
4
var mp = map[string]int{}
mp["1"] = 10
mp["2"] = 20
...

相反，如果键值个数超过25个，则Go会先创建 两个数组，分别将键和值存储到数组中，然后在通过如下方式创建map：

1
2
3
4
5
6
7
var mp = map[string]int{}
keys := []string {"1", "2"}
values := []int {10, 20}

for i:=0 ;i< len(keys); i++ {
  mp[keys[i]] = values[i]
}

makemap_small

1
2
3
4
5
6
7
8
// makemap_small implements Go map creation for make(map[k]v) and
// make(map[k]v, hint) when hint is known to be at most bucketCnt
// at compile time and the map needs to be allocated on the heap.
func makemap_small() *hmap {
	h := new(hmap)
	h.hash0 = fastrand()
	return h
}

如果编译器能够确定map的大小不大于8，则会通过 makemap_small() 来创建hmap对象，反之通过 makemap()

makemap

通过make创建哈希表在由编译器调用 makemap 完成，比如下面创建一个初始容量为1024的哈希表。

1
var mp = make(map[int]string, 1024)
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
// hint 表示初始容量
func makemap(t *maptype, hint int, h *hmap) *hmap {
    // 内存容量 = 桶个数 * 每个桶大小
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	if h == nil {
		h = new(hmap)
	}
    // 快速生成随机哈希种子
	h.hash0 = fastrand()
  
    // 负载因子
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B
  
	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        // 是否需要溢出桶
		if nextOverflow != nil {
            h.extra = new(mapextra)
            // 关联下一个可以使用的溢出桶
            // 也就是之后可以通过 hmap.extra.nextOverflow 快速查找下一个可以使用的溢出桶
            h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

计算当前哈希表的负载因子是否超过 6.5（仅在初始创建map时指定了一个初始容量 hint 有效）。

如果超过了理想的负载因子6.5，需要增加桶数量，也就是上面的 B++。

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

使用dlv跟踪 make(map[int]int, 1024) 流程：

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
(dlv) b runtime.makemap
Breakpoint 1 set at 0x40d4ea for runtime.makemap() /usr/local/go/src/runtime/map.go:303
(dlv) c
> runtime.makemap() /usr/local/go/src/runtime/map.go:303 (hits goroutine(1):1 total:1) (PC: 0x40d4ea)
Warning: debugging optimized function
   298: // makemap implements Go map creation for make(map[k]v, hint).
   299: // If the compiler has determined that the map or the first bucket
   300: // can be created on the stack, h and/or bucket may be non-nil.
   301: // If h != nil, the map can be created directly in h.
   302: // If h.buckets != nil, bucket pointed to can be used as the first bucket.
=> 303: func makemap(t *maptype, hint int, h *hmap) *hmap {
   304:         mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
   305:         if overflow || mem > maxAlloc {
   306:                 hint = 0
   307:         }
   308:
(dlv) p t.bucket.size
144
(dlv) p hint
1024
(dlv) p h
*runtime.hmap nil
 ...
> runtime.makemap() /usr/local/go/src/runtime/map.go:328 (PC: 0x40d588)
Warning: debugging optimized function
   323:         // allocate initial hash table
   324:         // if B == 0, the buckets field is allocated lazily later (in mapassign)
   325:         // If hint is large zeroing this memory could take a while.
   326:         if h.B != 0 {
   327:                 var nextOverflow *bmap
=> 328:                 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
   329:                 if nextOverflow != nil {
   330:                         h.extra = new(mapextra)
   331:                         h.extra.nextOverflow = nextOverflow
   332:                 }
   333:         }
(dlv) p h
*runtime.hmap {
        count: 0,
        flags: 0,
        B: 8,
        noverflow: 0,
        hash0: 696655033,
        buckets: unsafe.Pointer(0x0),
        oldbuckets: unsafe.Pointer(0x0),
        nevacuate: 0,
        extra: *runtime.mapextra nil,}
(dlv)

可以看到，我们创建map时指定一个一个初始的容量 1024=1<<10 ，但是实际上 hmap.B=8 。

makeBucketArray

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
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
  // base = uintptr(1) << (b & (goarch.PtrSize*8 - 1))
  // 在 64 位平台下就是： base = 1 << (b & 63)
  // 最大桶数量为 2^64 ，因此 b 最大也就63，不能为 64
  base := bucketShift(b)
  nbuckets := base

  // 数据量多余 2^4 时使用额外的溢出桶
  if b >= 4 {
    // 额外增加 2^(b-4) 个溢出桶！
		nbuckets += bucketShift(b - 4)
    // 所有桶（正常桶+溢出桶）的内存大小
		sz := t.bucket.size * nbuckets
    // 内存对齐
		up := roundupsize(sz)
		if up != sz {
      // 这才是实际的桶数量
			nbuckets = up / t.bucket.size
		}
	}

	if dirtyalloc == nil {
    // 创建一定数量的桶
		buckets = newarray(t.bucket, int(nbuckets))
	} else {
		buckets = dirtyalloc
		size := t.bucket.size * nbuckets
		if t.bucket.ptrdata != 0 {
			memclrHasPointers(buckets, size)
		} else {
			memclrNoHeapPointers(buckets, size)
		}
	}
	// 是否需要溢出桶
	if base != nbuckets {
    // 预分配溢出桶，正常桶和溢出桶在内存上是连续的
    // size = base * sizeof(bmap)
    // nextOverflow 指向第一个预分配的溢出桶
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		// 最后一个预分配的溢出桶
    last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		// 设置last下一个溢出桶为第一个正常桶（类似环形桶，用于判断一个溢出桶是否最后一个）
    last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}

针对上面的代码，可能一开始看时迷迷糊糊，不过当研究透彻后其实简简单单。

  • 当桶的数量少于 2^4 时，因此数据较少、使用溢出桶的可能性较低，因此不打算分配额外溢出桶
  • 当桶的数量多于 2^4 时，会额外创建 2^(B-4) 个溢出桶

除此之外，还需要注意以下三个不变量：

  • base 表示正常桶的数量
  • bucketShift(b - 4) 表示预分配的溢出桶数量
  • nbuckets 表示所有桶（正常桶和溢出桶）的数量

举个例子🌰，假设用户创建一个map：mp := make(map[int]int, 1024)，则

  • B=8
  • base=256
  • nbuckets=272，经过内存对齐后实际为 284！！！

即：桶的数量已经超过16个，makeBucketArray() 会 预分配 一部分溢出桶，且正常桶（有256个）和预分配的溢出桶（28个）在内存上是连续的，最终有284个桶。

如果在之后插入数据过程中，之前预分配的溢出桶不够了，那么就会调用 newoverflow() 重新创建一个溢出桶并关联到当前的hmap中，该函数之后会介绍。

下面这幅图应该够直观了吧：

image-20220407235727445

针对 var mp = make(map[int]int, 1024) ，我使用delve调试工具打印出最后创建的hmap结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(dlv) p h
*runtime.hmap {
        count: 0,
        flags: 0,
        B: 8,
        noverflow: 0,
        hash0: 2819793772,
        buckets: unsafe.Pointer(0xc000100000),
        oldbuckets: unsafe.Pointer(0x0),
        nevacuate: 0,
        extra: *runtime.mapextra {
                overflow: *[]*runtime.bmap nil,
                oldoverflow: *[]*runtime.bmap nil,
                nextOverflow: *(*runtime.bmap)(0xc000109000),},}
(dlv) p h.extra
*runtime.mapextra {
        overflow: *[]*runtime.bmap nil,
        oldoverflow: *[]*runtime.bmap nil,
        nextOverflow: *runtime.bmap {
                tophash: [8]uint8 [0,0,0,0,0,0,0,0],},}

newarray

该函数用于创建一定数量的哈希桶/bmap

1
2
3
4
5
6
7
8
9
10
func newarray(typ *_type, n int) unsafe.Pointer {
	if n == 1 {
		return mallocgc(typ.size, typ, true)
	}
	mem, overflow := math.MulUintptr(typ.size, uintptr(n))
	if overflow || mem > maxAlloc || n < 0 {
		panic(plainError("runtime: allocation size out of range"))
	}
	return mallocgc(mem, typ, true)
}

访问

C++ std::map 提供的 [] 重载操作符很方便获取key对应的value，但是如果key不存在，则会抛出异常，因此一般通过 find() 判断是否存在。而Go中的map即使key不存在，也不会抛出异常，而是直接返回一个value类型的 零值，要判断一个key-value是否存在一般是使用 value,ok := mp[key]; ok 。这不禁让我想起了之前写C++17中的if初始化表达式，比如下面这个例子

1
2
3
4
5
6
7
int main() {
  std::map<int, int> mp;
  if (auto x = mp.find(10); x != mp.end()) {
    std::cout << x->first << ":" << x->second << std::endl;
  }
  return 0;
}

而Go的判断key-value是否存在则是：

1
2
3
4
5
6
func main() {
	mp := make(map[int]int, 1024)
	if v, ok := mp[10]; ok {
		fmt.Println(v)
	}
}

回归正题，一般来说有以下几种方法访问map，分别调用不同的函数

  • value = h[key] 对应 mapaccess1
  • valueh, ok = [key] 对应 mapaccess2
  • for k,v :=range h {} 对应 mapaccessK

mapaccess1

image-20220408194953970

mapaccess1如果访问 不存在对应的key-value 或者 nil map，则返回 零值zeroValue ，而不是 nil。关键源码如下 mapaccess1。

下面的注释我自认为非常详细了，关于扩容那一段代码稍微有点难度，不过在阅读完之后的关于扩容那一小节后，在回过头来看该函数应该是没有问题的了😄。

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
const maxZero = 1024
var zeroVal [maxZero]byte

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	...
  
    // 访问的hmap为nil或者空map
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
        // 返回零值
		return unsafe.Pointer(&zeroVal[0])
	}
    // 标准map不允许并发读写
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
    // 通过希函数hasher对key进行哈希映射，得到一个哈希值
	hash := t.hasher(key, uintptr(h.hash0))
	// 简单理解为 m=(1<<h.B)-1，获取桶数量
    m := bucketMask(h.B)

    // 通过hash后B位获取key映射到第几个桶
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

  // 下面这段代码有点东西。。。
  if c := h.oldbuckets; c != nil {
	    // 如果当前正在扩容，且是翻倍扩容，为了获得翻倍之前的旧桶数量
        // 需要 m/2 获取旧桶数量
		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)))
        // 如果该旧桶没有迁移完成，说明数据还保留着，没有被GC
		if !evacuated(oldb) {
            // 则访问该旧桶
			b = oldb
		}
	}
  
  // 计算key哈希值的高8位
  top := tophash(hash)
bucketloop:
  // 遍历所有的bmap桶（包括正常桶和溢出桶）
  for ; b != nil; b = b.overflow(t) {
        // 遍历bmap桶中所有的tophash，一共8个tophash/key/value
		for i := uintptr(0); i < bucketCnt; i++ {
            // tophash不一致
			if b.tophash[i] != top {
                // 当 tophash[0]=emptyRest 表示整个bucket都是空的
				if b.tophash[i] == emptyRest {
                    // 直接跳出循环遍历
					break bucketloop
				}
				continue
			}
            // 获取keys的首地址，每个tophash对应一个key value
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
                // 将 key 转换为 unsafe.Pointer 类型
				k = *((*unsafe.Pointer)(k)) 
			}
            // 判断存储在桶bmap.keys中的key 是否和访问的key相同
            // 如果不相同，则跳过，继续判断下一个 tophash
            // 如果相同，则从桶bmap.elems 中获取对应的value
			if t.key.equal(key, k) {
                // 指针偏移获取对应的value
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
                    // 将value转换为 unsafe.Pointer 类型
					e = *((*unsafe.Pointer)(e))
				}
                // 返回vlaue指针
				return e
			}
		}
	}
    // 不存在key，返回零值
	return unsafe.Pointer(&zeroVal[0])
}

tophash() 计算不同平台下对应指针类型哈希值的高8位，在32位平台下 goarch.PtrSize=4 、64位平台下为8。

注意，tophash<5 表示的是状态，而 tophash>=5 则存储的是哈希值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
emptyRest      = 0 // 表示桶bucket是空
emptyOne       = 1 // 表示该bmap下的某个tophash是否为空，也就是可以插入
evacuatedX     = 2 // key/elem is valid.  Entry has been evacuated to first half of larger table.
evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
evacuatedEmpty = 4 // cell is empty, bucket is evacuated.
minTopHash     = 5 // minimum tophash for a normal filled cell.

func tophash(hash uintptr) uint8 {
	// 32位： hash >> 24
  // 64位： hash >> 56
  top := uint8(hash >> (goarch.PtrSize*8 - 8))
  // top < 5 ?
	if top < minTopHash {
		top += minTopHash
	}
	return top
}

获取/设置当前 bmap 下一个溢出桶的首地址 *bmap，通过指针偏移获取和修改，为什么？

这是因为 Go 在编译期间动态确定bmap中的keys和elems，也就是键值类型，且最后一个字段保存着下一个溢出桶bmap的地址，即 overflow unsafe.Pointer（这也是为什么源码中bmap结构体只有tophash字段）。因此如果想要获取运行期间下一个bmap指针，只能通过指针偏移获取（梦回C语言🤔）。

1
2
3
4
5
6
7
8
9
// 获取当前bmap的下一个的bmap溢出桶
func (b *bmap) overflow(t *maptype) *bmap {
	return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize))
}

// 设置当前bmap的下一个bmap溢出桶指针
func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
	*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize)) = ovf
}

总之就是Go的map采用数组（映射key到对应的桶）+链表（解决哈希冲突）的方案，但是在存储key-value时则分别存储，并且使用了tophash高8位哈希值，用于在遍历的过程中快速比较对应的key否存在。

mapaccess2

该函数大部分逻辑处理和mapaccess1一样，不过返回的是一个value指针和bool，bool用于指示该key是否存在。

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
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
	...
	hash := t.hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	...
	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
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if t.key.equal(key, k) {
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
                // key存在，返回true
				return e, true
			}
		}
	}
    // key不存在，返回false
	return unsafe.Pointer(&zeroVal[0]), false
}

mapaccessK

当通过语法 for k, v := range h {} 遍历map时，Go会在编译期间调用 mapaccessK 。遍历逻辑还是和mapaccess1一样，该函数返回两个指针，分别表示键和值的地址

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
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
	...
	hash := t.hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	...
	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
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if t.key.equal(key, k) {
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
                // 返回一个键值对指针
				return k, e
			}
		}
	}
	return nil, nil
}

写入

总所周知，Go不能将key-value写入到一个nil的map中，否则报错 panic: assignment to entry in nil map，但是却可以读取一个nil的map。

lp

mapassign

Go通过 h[key] = value 对map添加键值，这是在编译期间将其转换为 mapassign 调用。

该函数返回value在bmap桶中的指针，真正的赋值操作是在编译期间插入，下面的代码只是在bmap桶中对应的value槽位分配了一个空间以便后续编译器能够将value插入到该位置（注意key已经插入到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
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
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  ...
  // 计算key的哈希值
	hash := t.hasher(key, uintptr(h.hash0))

  // 添加 hashWriting 标志位，防止并发写情况下其他goroutine读取map
	h.flags ^= hashWriting

	if h.buckets == nil {
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}

again:
  // key映射到哪一个桶
	bucket := hash & bucketMask(h.B)
  // 如果正在扩容，则在每一次写入时迁移一部分旧桶数据到新桶中
	if h.growing() {
		growWork(t, h, bucket)
    // 当旧桶中的数据迁移到新桶后，
    // 就可以继续通过 h.buckets 访问新桶中的数据
	}
  // 获取key在buckets中对应的bmap桶
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
  // 计算key哈希值高8位
	top := tophash(hash)

  // 存放要修改的tophash、key、value引用
	var inserti *uint8
	var insertk unsafe.Pointer
	var elem unsafe.Pointer
  
  // 遍历正常桶和所有溢出桶中的对应bmap
bucketloop:
	for {
    // 遍历bmap的所有tophash/keys/values
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
        // 该位置为空，可插入
				if isEmpty(b.tophash[i]) && inserti == nil {
          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 {
					break bucketloop
				}
				continue
			}
      // 获取该位置的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) {
				continue
			}
			...
      // 获取该位置的value指针
			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
	}

  // 是否需要扩容
	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
	}
	
  // inserti = nil 说明bmap桶已经满了, 找不到插入槽位
	if inserti == nil {
    // 创建一个新的溢出桶bmap并关联到hmap.extra.overflow溢出桶中
		newb := h.newoverflow(t, b)
    // 使用新的溢出桶存放 tophash-key-value
		inserti = &newb.tophash[0] 
		insertk = add(unsafe.Pointer(newb), dataOffset) 
		elem = add(insertk, bucketCnt*uintptr(t.keysize)) 
	}

	if t.indirectkey() {
    // 为key分配新的内存
		kmem := newobject(t.key)
    *(*unsafe.Pointer)(insertk) = kmem
		insertk = kmem
	}
	if t.indirectelem() {
    // 为value分配新的内存
		vmem := newobject(t.elem)
		*(*unsafe.Pointer)(elem) = vmem
	}
  // 将key保存到对应的位置
	typedmemmove(t.key, insertk, key)
  // 存储tophash
	*inserti = top
  
	// 数量+1
  h.count++

done:
	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
  // 取消并发写标志
	h.flags &^= hashWriting
  // 解引用，返回 unsafe.Pointer 指针类型
	if t.indirectelem() {
		elem = *((*unsafe.Pointer)(elem))
	}
	return elem
}

newoverflow

这个函数在前面的 makeBucketArray 中已经提到过了，这里对其进行详细介绍。

newoverflow 函数的主要流程：

  • 如果 存在预分配的溢出桶，则获取一个溢出桶 ovf：

    • 如果 ovf.overflow(t) 为 nil，说明存在下一个溢出桶，这是因为一开始创建预分配的溢出桶时没有对bmap的overflow字段初始化（除了最后一个）
    • 如果 ovf.overflow 不为nil（指向第一个正常桶），说明ovf已经是最后一个溢出桶了（还记得之前的 last.setoverflow(t, (*bmap)(buckets))吗？）

  • 如果 正常桶/溢出桶满 了则通过newobject创建一个新的 bmap，并将其关联到当前正在访问的bmap的overflow，实际上也就是将新创建的bmap溢出桶和之前的bmap通过overflow指针链接起来，形成bmap链表。

由于 hmap.extra.nextOverflow 保存的是下一个可以使用的bmap溢出桶，如果该bmap是溢出桶最后一个，说明溢出桶已经满了，那么下次需要重新创建一个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
func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
	var ovf *bmap
  
	// 是否存在预分配的溢出桶
  if h.extra != nil && h.extra.nextOverflow != nil {
    // 下一个可以使用的bmap
		ovf = h.extra.nextOverflow
		if ovf.overflow(t) == nil {
      // h.extra.nextOverflow =ovf.overflow
      // 指向下一个溢出桶
      h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
		} else {
      // 如果ovf是最后一个溢出桶，重置当前bmap的overflow为空
      ovf.setoverflow(t, nil)
      // 将h.extra.nextOverflow设置为nil，表示当前[预分配的溢出桶]已经用完了
      // 那么之后再进入newoverflow就只能重新创建一个 bmap了
      // 也就是进入下面的else语句 创建一个bmap
			h.extra.nextOverflow = nil
		}
	} else {
    // 创建一个bmap
		ovf = (*bmap)(newobject(t.bucket))
	}
  // 增加溢出桶计数
	h.incrnoverflow()
  // 只有在map的key和value都不包含指针的情况下，才会使用overflow和oldoverflow
	if t.bucket.ptrdata == 0 {
		h.createOverflow()
		*h.extra.overflow = append(*h.extra.overflow, ovf)
	}
  // 关联/设置当前bmap下一个溢出桶ovf
  // 也就是当正常桶/溢出桶bmap满的时候，就使用另外一个溢出桶bmap存放数据
	b.setoverflow(t, ovf)
	return ovf
}
1
2
3
4
5
6
7
8
func (h *hmap) createOverflow() {
	if h.extra == nil {
		h.extra = new(mapextra)
	}
	if h.extra.overflow == nil {
		h.extra.overflow = new([]*bmap)
	}
}

这种情况针对一开始 makemap 初始时没有创建预分配的溢出桶，而之后在插入数据过程中，却需要溢出桶保存额外的数据。

Go_HMap.drawio 2

扩容

当哈希表超过了负载因子6.5 时或者存在太多的溢出桶则需要扩容。

1
2
3
4
5
6
7
 // 判断是否处于扩容的状态
// 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
}

overLoadFactor

Go中map哈希表中负载因子为 6.5，即理想的负载因子为 loadfactor = loadFactorNum/loadFactorDen = 6.5。当负载因子超过6.5时说明此时哈希表中的桶将要填满，为了保证查询和插入效率需要扩容。

负载因子的计算方式如下： loadfactor = count / (1<<B)

1
2
loadFactorNum = 13
loadFactorDen = 2
1
2
3
4
// 计算当前哈希表的负载因子是否超过 6.5
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

tooManyOverflowBuckets

该函数主要是判断当前哈希表中是否存在过多的溢出桶。这种情况通常发生在不断地插入、删除元素，导致创建了很多溢出桶，但由于存在删除操作，另一方面也会使得 哈希表的负载因子始终小于6.5。即当正常桶满时，会额外创建溢出桶保存数据，并挂接到桶的链表末尾，因此如果存在大量的溢出桶，那么在查询时遍历溢出桶（实质是遍历链表）也会消耗过多的时间。

故针对这种情况，当溢出桶数量超过阈值时需要对哈希表进行扩容。

1
2
3
4
5
6
7
8
9
10
11
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	// If the threshold is too low, we do extraneous work.
	// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
	// "too many" means (approximately) as many overflow buckets as regular buckets.
	// See incrnoverflow for more details.
	if B > 15 {
		B = 15
	}
	// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
	return noverflow >= uint16(1)<<(B&15)
}

hashGrow

当存在多个溢出桶时（tooManyOverflowBuckets()），或者负载因子超过 6.5 （overLoadFactor()）时会自动触发扩容机制。但是无论是哪种情况下都会调用 makeBucketArray 创建 数量翻倍 的新桶，并在之后的过程中将旧桶迁移到新桶中。但如果桶的数量非常多，那么一次性迁移所有的桶将非常耗时。为了避免这种情况Go采用 渐进式迁移 ，在每次进行写操作时将 一部分旧桶 迁移到新的桶中。

比如上面的 mapassign() 写入key-value中扩容逻辑

1
2
3
4
5
6
7
 // key映射到哪一个桶
bucket := hash & bucketMask(h.B)
 // 如果需要扩容，则在每一次写入时迁移一部分桶数据到新桶中
if h.growing() {
   // 传入的bucket表示key位于第几个桶
	growWork(t, h, bucket)
}

除了采用 渐进式迁移桶，Go中还针对溢出桶过多的情况采取 sameSizeGrow机制，即 等量扩容，换句话说就是扩容时通过 makeBucketArray() 创建和旧桶数量相同的新桶。

因此map的扩容针对是否存在过多的溢出桶有两种策略：

  • 翻倍扩容，新桶数量是旧桶数量两倍（1<<(B+1)）
  • 等量扩容，新桶数量和旧桶数量一样 （1<<B）
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
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
	}
  
  // 旧桶中的数据
	oldbuckets := h.buckets

  // 如果是溢出桶过多的情况采取等量扩容，新桶数量不变 1<<B
  // 否则翻倍
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	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
  // 新桶
	h.buckets = newbuckets
	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
    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().
}

growWork

上面说到Go在迁移桶不是一次性将旧桶中的数据复制到新桶，而是一个 渐进式迁移 的过程。在迁移之前将旧桶保存在 hmap.oldbuckets 中，而新桶保存在 hmap.buckets 中。

1
2
3
4
5
6
7
8
9
// bucket 表示需要迁移第几个桶
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 将旧桶迁移到新桶
	evacuate(t, h, bucket&h.oldbucketmask())

	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

hmap.noldbuckets() 根据不同扩容策略返回旧桶数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 获取当前哈希表中有多少旧桶（不包括溢出桶）
func (h *hmap) noldbuckets() uintptr {
	oldB := h.B
  // 是否是翻倍扩容
	if !h.sameSizeGrow() {
		oldB--
	}
  // 返回旧桶数量
	return bucketShift(oldB)
}

// oldbucketmask provides a mask that can be applied to calculate n % noldbuckets().
func (h *hmap) oldbucketmask() uintptr {
	return h.noldbuckets() - 1
}

evacuate

evacuate单词意思为 “撤离，转移，分流”，对于map的迁移过程也是将旧桶的数据迁移到新桶中。

下面6个常量表示bmap桶中槽位的状态，上界为 minTopHash=5

1
2
3
4
5
6
7
8
9
10
11
12
const emptyRest      = 0 // 表示整个桶bmap为空
const emptyOne       = 1 // 表示桶bmap槽位为空
const evacuatedX     = 2 // 表示桶bmap槽位迁移完成，且迁移到了前半部分X
const evacuatedY     = 3 // 表示桶bmap槽位迁移完成，且迁移到了后半部分Y
const evacuatedEmpty = 4 // 表示桶bmap槽位迁移完成，但槽位是空的，即没有key-value需要迁移的
const minTopHash     = 5

// 表示桶所有的槽位是否迁移完成，无论迁移前的槽位是否为空
func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > emptyOne && h < minTopHash
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 将旧桶数据分流到哪里
type evacDst struct {
  // 目标桶
	b *bmap          
  // key/value位于目标桶bmap哪一个槽位
	i int            
  // 新桶中key在内存中的地址
	k unsafe.Pointer 
  // 新桶中value在内存中的地址
	e unsafe.Pointer 
}

// 偏移大小，可简单理解为获取bmap中keys起始地址，即跳过8字节的tophash
const dataOffset = unsafe.Offsetof(struct {
		b bmap
		v int64 // 8字节tophash
}{}.v)

该函数较为复杂，不过大部分注释我都写出来了。

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
// bucket 表示需要迁移第几个旧桶
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
  // 本次将要迁移的旧桶bmap
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  // 旧桶数量
	newbit := h.noldbuckets()
  // 旧桶是否已经迁移完成
	if !evacuated(b) {
		// xy contains the x and y (low and high) evacuation destinations.
		var xy [2]evacDst
		x := &xy[0]
    
    // 等量时新桶位置
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
    // 存放在新桶中的key内存地址
		x.k = add(unsafe.Pointer(x.b), dataOffset)
    // 存放在新桶中的value内存地址
		x.e = add(x.k, bucketCnt*uintptr(t.keysize))
	
    // 翻倍扩容
		if !h.sameSizeGrow() {
			// Only calculate y pointers if we're growing bigger.
			// Otherwise GC can see bad pointers.
			y := &xy[1]
      // 数量翻倍后的新桶位置
			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			// 存放在新桶中的key内存地址
      y.k = add(unsafe.Pointer(y.b), dataOffset)
      // 存放在新桶中的value内存地址
			y.e = add(y.k, bucketCnt*uintptr(t.keysize))
		}

    // 遍历所有旧桶（正常桶和溢出桶），将每一个桶的key-value迁移到新桶
		for ; b != nil; b = b.overflow(t) {
      // 获取旧桶bmap中keys内存起始地址
			k := add(unsafe.Pointer(b), dataOffset)
      // 获取旧桶bmap中values内存起始地址
			e := add(k, bucketCnt*uintptr(t.keysize))
      // 遍历8个槽位，获取对应槽位上的 tophash-key-value
			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) {
          // 标记该槽位迁移后为空，即没有key-value需要迁移
					b.tophash[i] = evacuatedEmpty
					continue
				}
				if top < minTopHash {
					throw("bad map state")
				}
       	// 获取key
				k2 := k
				if t.indirectkey() {
					k2 = *((*unsafe.Pointer)(k2))
				}
				var useY uint8
        // 翻倍扩容
				if !h.sameSizeGrow() {
					// Compute hash to make our evacuation decision (whether we need
					// to send this key/elem to bucket x or bucket y).
          // 计算key哈希值，也就是key位于哪一个桶
					hash := t.hasher(k2, uintptr(h.hash0))
					if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
            // If key != key (NaNs), then the hash could be (and probably
						// will be) entirely different from the old hash. Moreover,
						// it isn't reproducible. Reproducibility is required in the
						// presence of iterators, as our evacuation decision must
						// match whatever decision the iterator made.
						// Fortunately, we have the freedom to send these keys either
						// way. Also, tophash is meaningless for these kinds of keys.
						// We let the low bit of tophash drive the evacuation decision.
						// We recompute a new random tophash for the next level so
						// these keys will get evenly distributed across all buckets
						// after multiple grows.
            // 当遇到math.NaN()的key时由tophash最低位决定迁移到X或者Y桶
            // 因为使用math.Nan()作为key每次求hash都是不一样的。
						useY = top & 1
            // 重新计算tophash
						top = tophash(hash)
					} else {
            // 是否可以将数据存放在翻倍后的Y桶位置
						if hash&newbit != 0 {
							useY = 1
						}
					}
				}

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

        // 标记当前旧桶对应槽位迁移到哪个目标桶，是X还是Y
				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
        // 迁移到目标桶
				dst := &xy[useY]                 // evacuation destination

        // 迁移目标桶槽位满了
				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))
				}
       	// 记录tophash
				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
				// 迁移key，复制内存中的值
        if t.indirectkey() {
					*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
				} else {
					typedmemmove(t.key, dst.k, k) // copy elem
				}
        // 迁移value，复制内存中的值
				if t.indirectelem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
				} else {
					typedmemmove(t.elem, dst.e, e)
				}
        // 继续迁移当前桶的下一个 key-value槽位
				dst.i++
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.e = add(dst.e, uintptr(t.elemsize))
			}
		}
    
    // 迁移完成，清空旧桶bmap中的keys和values
		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
      // keys起始内存地址
			ptr := add(b, dataOffset)
      // 所有的keys和values字节
			n := uintptr(t.bucketsize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}

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

advanceEvacuationMark

该函数记录当前旧桶bmap迁移完成的进度，如果所有的旧桶都迁移完成，则重置 hmap.oldbuckets 和 hmap.extra.oldoverflow 指针为 nil。

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
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
  // 记录已经迁移完成的进度
	h.nevacuate++
	// Experiments suggest that 1024 is overkill by at least an order of magnitude.
	// Put it in there as a safeguard anyway, to ensure O(1) behavior.
	stop := h.nevacuate + 1024
	if stop > newbit {
		stop = newbit
	}
  // bucketEvacuated 判断桶是否迁移完成
	for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
		h.nevacuate++
	}
  // 当所有的旧桶都迁移完成，则将oldbuckets和oldoverflow指针重置为nil
	if h.nevacuate == newbit { // newbit == # of oldbuckets
		// Growing is all done. Free old main bucket array.
		h.oldbuckets = nil
		// Can discard old overflow buckets as well.
		// If they are still referenced by an iterator,
		// then the iterator holds a pointers to the slice.
		if h.extra != nil {
			h.extra.oldoverflow = nil
		}
		h.flags &^= sameSizeGrow
	}
}

下面这幅图大致说明了两种策略的桶迁移过程。注意该图中只展示一个旧桶的迁移，实际上迁移过程是会通过overflow指针遍历旧桶和所有的溢出桶，也就是迁移发生时会将多个旧桶迁移到新桶中。

Go_HMap_evacuate.drawio

遍历

Go语言支持以下三种方法遍历一个哈希表：

  • for k := range mp {}
  • for k,v :=range mp {}
  • for range mp {}

遍历map通常需要一个迭代器iterator保存中间状态。而且遍历是 无序的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type hiter struct {
	key         unsafe.Pointer
	elem        unsafe.Pointer
	t           *maptype
	h           *hmap
	buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
	bptr        *bmap          // current bucket
	overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
	oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
	startBucket uintptr        // bucket iteration started at
	offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
	wrapped     bool           // already wrapped around from end of bucket array to beginning
	B           uint8
	i           uint8
	bucket      uintptr
	checkBucket uintptr
}

mapiterinit

Go编译器会在编译期间调用 mapiterinit() 初始化map迭代器。可参考： https://github.com/golang/go/blob/3e7ffb862f550c38ce0611b970a4dce10a01226e/src/cmd/compile/internal/walk/range.go#L160

对于该函数我们可以了解到：

  • 随机从当前哈希表的选择一个起始桶开始迭代
  • 从该起始桶随机选择一个槽位开始迭代
  • 调用 mapiternext() 开始真正的迭代
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
func mapiterinit(t *maptype, h *hmap, it *hiter) {
	it.t = t
	if h == nil || h.count == 0 {
		return
	}

	it.h = h

	// grab snapshot of bucket state
	it.B = h.B
	it.buckets = h.buckets
	if t.bucket.ptrdata == 0 {
		h.createOverflow()
		it.overflow = h.extra.overflow
		it.oldoverflow = h.extra.oldoverflow
	}

	// 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))
	// 指向桶指针
	it.bucket = it.startBucket

	// Remember we have an iterator.
	// Can run concurrently with another mapiterinit().
	if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
		atomic.Or8(&h.flags, iterator|oldIterator)
	}
  
  // 真正的迭代过程
	mapiternext(it)
}

mapiternext

该函数还是比较好理解的（前提是前面的大致掌握了），总之使用for range遍历map是 无序的，而且在特定情况下也会通过 mapaccessK() 访问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
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
func mapiternext(it *hiter) {
	h := it.h
	t := it.t
	bucket := it.bucket
	b := it.bptr
	i := it.i
	checkBucket := it.checkBucket

// 循环遍历，最终会回到起始桶位置 it.startBucket
next:
	if b == nil {
    // 回到开头
		if bucket == it.startBucket && it.wrapped {
			// end of iteration
			it.key = nil
			it.elem = nil
      // 结束遍历
			return
		}
    // 是否为等量扩容
		if h.growing() && it.B == h.B {
      // 第几个旧桶
			oldbucket := bucket & it.h.oldbucketmask()
			b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
      // 桶b没有迁移完成，则使用该旧桶
			if !evacuated(b) {
				checkBucket = bucket
			} else {
        // 桶b已经迁移完成，则从新桶中获取
				b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
				checkBucket = noCheck
			}
		} else {
      // 当前未扩容/翻倍扩容
			b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
			checkBucket = noCheck
		}
    // 到了最后一个桶，下次从0号桶开始，即循环遍历
		bucket++
		if bucket == bucketShift(it.B) {
			bucket = 0
			it.wrapped = true
		}
		i = 0
	}
  // 遍历8个槽位
	for ; i < bucketCnt; i++ {
		offi := (i + it.offset) & (bucketCnt - 1)
		if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
			continue
		}
    // 键
		k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
		if t.indirectkey() {
			k = *((*unsafe.Pointer)(k))
		}
    // 值
		e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
    if checkBucket != noCheck && !h.sameSizeGrow() {
			if t.reflexivekey() || t.key.equal(k, k) {
				hash := t.hasher(k, uintptr(h.hash0))
				if hash&bucketMask(it.B) != checkBucket {
					continue
				}
			} else {
				if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
					continue
				}
			}
		}
    // 当前桶b没有发生迁移，因此可以从该槽位中获取kv
		if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
			!(t.reflexivekey() || t.key.equal(k, k)) {
			it.key = k
			if t.indirectelem() {
				e = *((*unsafe.Pointer)(e))
			}
			it.elem = e
		} else {
        // 否则通过 mapaccessK 获取key-value
			rk, re := mapaccessK(t, h, k)
			if rk == nil {
				continue // key has been deleted
			}
			it.key = rk
			it.elem = re
		}
		it.bucket = bucket
		if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
			it.bptr = b
		}
		it.i = i + 1
		it.checkBucket = checkBucket
		return
	}
  // 继续遍历b的下一个溢出桶
	b = b.overflow(t)
	i = 0
	goto next
}

删除

Go中可使用delete内建函数删除一个map对应的key-value， mapdelete() 并不会对map缩容，因此随着插入元素越来越多，map占用的内存也会随之增加。

mapdelete

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
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	...
  
  // 获取key哈希
	hash := t.hasher(key, uintptr(h.hash0))
	h.flags ^= hashWriting
  ...
  // key映射在哪一个桶
	bucket := hash & bucketMask(h.B)
  // 如果在删除key的时候正在进行扩容
  // 则需要等到growWork完成，也就是迁移oldbucket中的数据到新桶中
	if h.growing() {
		growWork(t, h, bucket)
	}
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
	bOrig := b
  // 高8位tophash
	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))
			}
			// key不一致
      if !t.key.equal(key, k2) {
				continue
			}
			// Only clear key if there are pointers in it.
			if t.indirectkey() {
        // 标记为nil，表示该内存不在使用，用于GC回收内存
				*(*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() {
        // 标记为nil，用于GC回收内存
				*(*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
			...
      // kv数量减1
      h.count--
      ...
    }
	}
	...
}

清空

mapclear

清空map相对来说比较简单，源码位于：https://github.com/golang/go/blob/5a90270d7f5b384de31399133c7336d007fbd93d/src/runtime/map.go#L991

Go没有提供函数给用户来清空一个map，但是我们可以通过for range清空map

1
2
3
4
5
6
7
8
9
func main() {
	mp := make(map[int]int, 128)
	for i := 0; i < 1000; i++ {
		mp[i] = i * 1000
	}
	for k := range mp {
		delete(mp, k)
	}
}

或者也可以通过 make() 重新创建一个map

1
2
3
4
5
6
7
func main() {
	mp := make(map[int]int, 128)
	for i := 0; i < 1000; i++ {
		mp[i] = i * 1000
	}
	mp = make(map[int]int, 1024)
}

下面我针对第一种情况输出其汇编代码：

  • -S 生成汇编代码
  • -N 禁止编译优化
  • -l 禁止内联
1
go tool compile -S -N -l main.go

image-20220408210654972

1
go tool compile -S main.go

image-20220408210818782

由于Go编译器默认会对用户编写的代码进行优化，以取得更好的性能，但是在调试Go代码时为了更加清楚了解背后的代码逻辑，一般需要关闭编译器优化和函数内联。

总结

  • Go语言使用 数组+拉链法 实现哈希表并解决哈希碰撞的问题。

  • Go语言标准map不支持并发读写删除，如有需要可使用 sync.Map

  • Go语言每个哈希桶bmap提供8个槽位保存tophash-key-value，其中tophash保存的是64位key哈希值的 高8位，用于快速查找槽位，而低hmap.B位则表示该 key映射到哪一个桶。除此之外key-value槽位保存的是对应值存储在内存中的指针地址。

  • 当哈希表负载因子超过 6.5 或者 溢出桶数量超过阈值 时会触发 扩容。

  • map迁移采用 渐进式迁移 旧桶，在写入操作时将一部分的桶迁移到新桶中，而非一次性全部迁移。一旦全部旧桶迁移完成后将其清空。

  • map根据当前哈希表是否存在过多的溢出桶采取不同扩容策略：翻倍扩容和等量扩容。

  • 使用for-range遍历map是 无序的。

  • Go语言哈希表不支持缩容。

总的来说，Go的map源码阅读起来还不是那么困难，但对我来说研究了很久，最后也算是弄懂了些皮毛，毕竟map牵扯到的内容不是很多，大部分代码都在 map.go 中，不像GMP那样涉及到多个源文件。总之就当作学习了一个新的数据结构😊

参考