go基础08-map的内部实现

和切片相比，map类型的内部实现要复杂得多。Go运行时使用一张哈希表来实现抽象的map类型。运行时实现了map操作的所有功能，包括查找、插入、删除、遍历等。在编译阶段，Go编译器会将语法层面的map操作重写成运行时对应的函数调用。

下面是大致的对应关系：

// $GOROOT/src/cmd/compile/internal/gc/walk.go
// $GOROOT/src/runtime/map.go
m := make(map[keyType]valType, capacityhint) → m := runtime.makemap(maptype, capacityhint, m)
v := m["key"] → v := runtime.mapaccess1(maptype, m, "key")
v, ok := m["key"] → v, ok := runtime.mapaccess2(maptype, m, "key")
m["key"] = "value" → v := runtime.mapassign(maptype, m, "key") // v是用于后续存储value 的空间的地址
delete(m, "key") → runtime.mapdelete(maptype, m, "key")
1
2
3
4
5
6
7

下图是map类型在运行时层实现的示意图。

1. 初始状态

从图上中我们可以看到，与语法层面map类型变量一一对应的是runtime.hmap类型的实例。hmap是map类型的header，可以理解为map类型的描述符，它存储了后续map类型操作所需的所有信息。

● count：当前map中的元素个数；对map类型变量运用len内置函数时，len函数返回的就是count这个值。

● flags：当前map所处的状态标志，目前定义了4个状态值——iterator、oldIterator、hashWriting和sameSizeGrow。

● B：B的值是bucket数量的以2为底的对数，即2^B = bucket数量。

● noverflow：overflow bucket的大约数量。

● hash0：哈希函数的种子值。

● buckets：指向bucket数组的指针。

● oldbuckets：在map扩容阶段指向前一个bucket数组的指针。

● nevacuate：在map扩容阶段充当扩容进度计数器。所有下标号小于nevacuate的bucket都已经完成了数据排空和迁移操作。

● extra：可选字段。如果有overflow bucket存在，且key、value都因不包含指针而被内联（inline）的情况下，该字段将存储所有指向overflow bucket的指针，保证overflow bucket是始终可用的（不被垃圾回收掉）。

真正用来存储键值对数据的是bucket（桶），每个bucket中存储的是Hash值低bit位数值相同的元素，默认的元素个数为BUCKETSIZ（值为8，在$GOROOT/src/cmd/compile/internal/gc/reflect.go中定义，与runtime/map.go中常量bucketCnt保持一致）。

当某个bucket（比如buckets[0]）的8个空槽（slot）都已填满且map尚未达到扩容条件时，运行时会建立overflow bucket，并将该overflow bucket挂在上面bucket（如buckets[0]）末尾的overflow指针上，这样两个bucket形成了一个链表结构，该结构的存在将持续到下一次map扩容。

每个bucket由三部分组成：tophash区域、key存储区域和value存储区域。

1）tophash区域

当向map插入一条数据或从map按key查询数据的时候，运行时会使用哈希函数对key做哈希运算并获得一个哈希值hashcode。这个hashcode非常关键，运行时将hashcode“一分为二”地看待，其中低位区的值用于选定bucket，高位区的值用于在某个bucket中确定key的位置。这个过程可参考下图。

因此，每个bucket的tophash区域是用于快速定位key位置的，这样避免了逐个key进行比较这种代价较大的操作，尤其是当key是size较大的字符串类型时，这是一种以空间换时间的思路。

2）key存储区域

tophash区域下面是一块连续的内存区域，存储的是该bucket承载的所有key数据。

运行时在分配bucket时需要知道key的大小。那么运行时是如何知道key的大小的呢？当我们声明一个map类型变量时，比如var m map[string]int，Go运行时就会为该变量对应的特定map类型生成一个runtime.maptype实例（如存在，则复用）：

// $GOROOT/src/runtime/type.go
type maptype struct {
typ _type
key *_type
elem *_type
bucket *_type // 表示hash bucket的内部类型
keysize uint8 // key的大小
elemsize uint8 // elem的大小
bucketsize uint16 // bucket的大小
flags uint32
}
1
2
3
4
5
6
7
8
9
10
11

该实例包含了我们所需的map类型的所有元信息。前面提到过编译器会将语法层面的map操作重写成运行时对应的函数调用，这些运行时函数有一个共同的特点：

第一个参数都是maptype指针类型的参数。Go运行时就是利用maptype参数中的信息确定key的类型和大小的，map所用的hash函数也存放在maptype.key.alg.hash(key, hmap.hash0)中。

同时maptype的存在也让Go中所有map类型共享一套运行时map操作函数，而无须像C++那样为每种map类型创建一套map操作函数，从而减少了对最终二进制文件空间的占用。

运行该程序：

$go run map_concurrent_read_and_write.go
fatal error: concurrent map iteration and map write
1
2

我们会得到上述panic信息。如果仅仅是并发读，则map是没有问题的。

Go 1.9版本中引入了支持并发写安全的sync.Map类型，可以用来在并发读写的场景下替换掉map。另外考虑到map可以自动扩容，map中数据元素的value位置可能在这一过程中发生变化，因此Go不允许获取map中value的地址，这个约束是在编译期间就生效的。示例
代码如下：

p := m[key] // 无法获取m[key]的地址
fmt.Println(p)
1
2

尽量使用cap参数创建map

从上面的自动扩容原理我们了解到，如果初始创建map时没有创建足够多可以应付map使用场景的bucket，那么随着插入map元素数量的增多，map会频繁扩容，而这一过程将降低map的访问性能。

因此，如果可能的话，我们最好对map使用规模做出粗略的估算，并使
用cap参数对map实例进行初始化。下面是使用cap参数与不使用map参数的map写性能基准测
试及测试结果：

const mapSize = 10000
func BenchmarkMapInitWithoutCap(b *testing.B) {
	for n := 0; n < b.N; n++ {
		m := make(map[int]int)
	for i := 0; i < mapSize; i++ {
		m[i] = i
	}
	}
}
func BenchmarkMapInitWithCap(b *testing.B) {
	for n := 0; n < b.N; n++ {
		m := make(map[int]int, mapSize)
	for i := 0; i < mapSize; i++ {
		m[i] = i
	}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以看出，使用cap参数的map实例的平均写性能是不使用cap参数的2倍。

goos: darwin
goarch: amd64
BenchmarkMapInitWithoutCap-8 2000 645946 ns/op 687188 B/op 276 allocs/op
BenchmarkMapInitWithCap-8 5000 317212 ns/op 322243 B/op 11 allocs/op
PASS
ok command-line-arguments 2.987s

1
2
3
4
5
6
7

和切片一样，map是Go语言提供的重要数据类型，也是Gopher日常编码中最常使用的类型之一。通过本条的学习我们掌握了map的基本操作和运行时实现原理，并且我们在日常使

用map的场合要把握住下面几个要点：

● 不要依赖map的元素遍历顺序；

● map不是线程安全的，不支持并发写；

● 不要尝试获取map中元素（value）的地址；

● 尽量使用cap参数创建map，以提升map平均访问性能，减少频繁扩容带来的不必要损耗