不会飞的章鱼

熟能生巧，勤能补拙；念念不忘，必有回响。

Go语言精进——了解map原理并高效使用

发表于 分类于
本文字数： 6.1k 阅读时长 ≈ 6 分钟

什么是Map

map 是 Go 语言提供的一种抽象数据类型，它表示一组无序的键值对。

map的声明： 

1
map[key_type]value_type

key 与 value 的类型可以相同，也可以不同： 

1
2
map[string]string  // key与value元素的类型相同
map[int]string     // key与value元素的类型不同

如果两个 map 类型的 key 元素类型相同，value 元素类型也相同，那么我们可以说它们是同一个 map 类型，否则就是不同的 map 类型。

map 类型对 value 的类型没有限制，但是对 key 的类型却有严格要求，因为 map 类型要保证 key 的唯一性。Go 语言中要求，key 的类型必须支持“==”和“!=”两种比较操作符。

在Go语言中，函数类型、map类型本身，以及切片只支持与nil的比较，而不支持同类型两个变量的比较： 

1
2
3
4
5
6
7
8
9
10
11
func main() {
	s1 := make([]int, 1)
	s2 := make([]int, 2)
	f1 := func() {}
	f2 := func() {}
	m1 := make(map[int]string)
	m2 := make(map[int]string)
	println(s1 == s2) // invalid operation: s1 == s2 (slice can only be compared to nil)
	println(f1 == f2) // invalid operation: f1 == f2 (func can only be compared to nil)
	println(m1 == m2) // invalid operation: m1 == m2 (map can only be compared to nil)
}

结论：函数类型、map 类型自身，以及切片类型是不能作为 map的 key 类型的。

map基本操作

声明

1
2
3
4
5
// 声明一个map
var m map[string]int // 一个 map[string]int 类型的变量

// 赋值会报错
m["keys"] = 1  // panic: assignment to entry in nil map

使用复合字面值初始化 map 类型变量

1
m := map[int]string{}

使用 make 为 map 类型变量进行显式初始化

1
2
m1 := make(map[int]string)  // 未指定初始容量
m2 := make(map[int]string,8) // 指定初始容量为8

插入新键值对

1
2
3
4
5
6
m := make(map[int]string)
m[1] = "v1"
m[2] = "v2"
m[3] = "v3"

m[1] = "v1-back"  // 会覆盖掉1所对应的值

获取键值对数量

1
2
3
4
5
6
7
8
9
func main() {
	m := map[string]int{
		"key1": 1,
		"key2": 2,
	}
	fmt.Println(len(m))  // 2
	m["key3"] = 3
	fmt.Println(len(m)) // 3
}

注意：我们不能对 map 类型变量调用 cap，来获取当前容量。

查找和数据读取

1
2
3
4
5
v, ok := m["key1"]
if !ok {
	fmt.Println("not exist")
}
fmt.Println(v) // 1

在 Go 语言中，请使用“comma ok”惯用法对 map 进行键查找和键值读取操作。

删除数据

1
2
3
fmt.Println(m) // map[key1:1 key2:2 key3:3]
delete(m, "key1")
fmt.Println(m) // map[key2:2 key3:3]

注意：delete 函数是从 map 中删除键的唯一方法。即便传给 delete 的键在map 中并不存在，delete 函数的执行也不会失败，更不会抛出运行时的异常。

遍历 map 中的键值数据

像对待切片那样通过 for range 语句对 map 数据进行遍历： 

1
2
3
4
5
6
7
8
9
10
11
	fmt.Printf("{ ")
	for k, v := range m {
		fmt.Printf("%v: %v\n", k, v)
	}
	fmt.Printf("}\n")
/*
{ key1: 1
key2: 2
key3: 3
}
*/

map的内部实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// makemap implements Go map creation for make(map[k]v, hint).
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h != nil, the map can be created directly in h.
// If h.buckets != nil, bucket pointed to can be used as the first bucket.
func makemap(t *maptype, hint int, h *hmap) *hmap{...}

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer{}

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool){}

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer){}

map 类型在 Go 运行时层实现的示意图

初始状态

与语法层面 map 类型变量（m）一一对应的是 runtime.hmap 的实例。
hmap 类型是 map 类型的头部结构（header），也就是map 类型的描述符，它存储了后续 map 类型操作所需的所有信息，包括：

真正用来存储键值对数据的是桶，也就是 bucket，每个 bucket 中存储的是 Hash 值低
bit 位数值相同的元素，默认的元素个数为 BUCKETSIZE(值为 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 指针上，这样两个 buckets 形成了一个链表结构，直到下一次 map 扩容之前，这个结构都会一直存在。

从图中我们可以看到，每个 bucket 由三部分组成，从上到下分别是 tophash 区域、
key存储区域和 value 存储区域。

tophash 区域

当我们向 map 插入一条数据，或者是从 map 按 key 查询数据的时候，运行时都会使用哈希函数对 key 做哈希运算，并获得一个哈希值（hashcode）。这个 hashcode 非常关键，运行时会把 hashcode“一分为二”来看待，其中低位区的值用于选定 bucket，高位区的值用于在某个 bucket 中确定 key 的位置。

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

key 存储区域

tophash 区域下面是一块连续的内存区域，存储的是这个 bucket 承载的所有 key 数据。运行时在分配 bucket 的时候需要知道 key 的 Size。——Go 运行时就是利用 maptype 参数中的信息确定 key 的类型和大小的。 

1
2
3
4
5
6
7
8
9
10
11
12
type maptype struct {
	typ    _type
	key    *_type
	elem   *_type
	bucket *_type // internal type representing a hash bucket
	// function for hashing keys (ptr to key, seed) -> hash
	hasher     func(unsafe.Pointer, uintptr) uintptr
	keysize    uint8  // size of key slot
	elemsize   uint8  // size of elem slot
	bucketsize uint16 // size of bucket
	flags      uint32
}

value 存储区域

key 存储区域下方的另外一块连续的内存区域，这个区域存储的是 key 对应的 value。
和 key 一样，这个区域的创建也是得到了 maptype 中信息的帮助。Go 运行时采用了把 key 和 value 分开存储的方式，而不是采用一个 kv 接着一个 kv 的 kv 紧邻方式
存储，这带来的其实是算法上的复杂性，但却减少了因内存对齐带来的内存浪费。

我们以 map[int8]int64 为例，看看下面的存储空间利用率对比图：

当前 Go 运行时使用的方案内存利用效率很高，而 kv 紧邻存储的方案在map[int8]int64 这样的例子中内存浪费十分严重，它的内存利用率是 72/128=56.25%，有近一半的空间都浪费掉了。

注意：如果 key 或 value 的数据长度大于一定数值，那么运行时不会在 bucket 中直接存储数据，而是会存储 key 或 value 数据的指针。
目前 Go 运行时定义的最大 key 和 value 的长度是这样的： 

1
2
3
4
5
// $GOROOT/src/runtime/map.go
const (
    maxKeySize  = 128
	maxElemSize = 128
)

map扩容

map 会对底层使用的内存进行自动管理。
因此，在使用过程中，当插入元素个数超出一定数值后，map 一定会存在自动扩容的问题，也就是怎么扩充 bucket 的数量，并重新在 bucket 间均衡分配数据的问题。

那么 map 在什么情况下会进行扩容呢？
Go 运行时的 map 实现中引入了一个LoadFactor（负载因子），当count > LoadFactor * 2^B或 overflow bucket 过多时，运行时会自动对 map 进行扩容。

目前 Go 最新 1.17 版本以上 LoadFactor 设置为6.5（loadFactorNumloadFactorDen）。

1
2
3
4
5
6
7
8
// $GOROOT/src/runtime/map.go
const (
    loadFactorNum = 13
	loadFactorDen = 2
)

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer{}

  • 如果是因为 overflowbucket 过多导致的“扩容”，实际上运行时会新建一个和现有规模一样的 bucket 数组，然后在 assign 和 delete 时做排空和迁移。

  • 如果是因为当前数据数量超出 LoadFactor 指定水位而进行的扩容，那么运行时会立一个两倍于现有规模的 bucket 数组，但真正的排空和迁移工作也是在 assign 和 delete 时逐步进行的。原 bucket 数组会挂在 hmap 的 oldbuckets 指针下面，直到原 buckets 数组中所有数据都迁移到新数组后，原 buckets 数组才会被释放。

map与并发

从上面的实现原理来看，充当 map 描述符角色的 hmap实例自身是有状态的（hmap.flags），而且对状态的读写是没有并发保护的。所以，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
package main

import (
	"fmt"
	"time"
)

func doIteration(m map[int]int) {
	for k, v := range m {
		_ = fmt.Sprintf("[%d, %d] ", k, v)
	}
}
func doWrite(m map[int]int) {
	for k, v := range m {
		m[k] = v + 1
	}
}

func main() {
	m := map[int]int{
		1: 11,
		2: 12,
		3: 13,
	}

	go func() {
		for i := 0; i < 1000; i++ {
			doIteration(m)
		}
	}()

	go func() {
		for i := 0; i < 1000; i++ {
			doWrite(m)
		}
	}()

	time.Sleep(5 * time.Second)
}

// fatal error: concurrent map iteration and map write

如果我们仅仅是进行并发读，map 是没有问题的。

Go 1.9 版本中引入了支持并发写安全的 sync.Map 类型，可以用来在并发读写的场景下替换掉 map。

注意：考虑到 map 可以自动扩容，map 中数据元素的 value 位置可能在这一过程中发生变化，所以Go 不允许获取 map 中 value 的地址，这个约束是在编译期间就生效的。 

1
2
p := &m[key]//can not take the address of m[key]
fmt.Println(p)
------ 本文结束------
如果本篇文章对你有帮助，可以给作者加个鸡腿~(*^__^*)，感谢鼓励与支持！