golang 基础-深入理解 map

哈希表是通过键直接访问值的数据结构，这种结构在查询、添加、删除元素中的时间复杂度是 O(1)，而在 golang 中，map 就是实现哈希表的一种类型；同时 map 也是日常开发中使用频率较高的一种类型，下面我们着重分析下。

基本能力

map 的基本使用是比较明确的，总结下来，是如下几个动作。

Map 操作	具体方法
初始化	m := make(map[string]string)
插入	m["name"] = "zhangsan"
检索	value, ok := m["name"]
删除	delete(m, "name")
遍历	for key, value := range m
长度	len(m)

具体的可以参考下官方文档，这里不多赘述，下面我们详细分析下底层实现。

底层实现

首先回到问题本身，如果想存储一个 key/value 对并且可根据 key 检索 value ，可以有以下三种解决方案:

1. 存储到列表中(也就是 slice 中)，然后检索整个列表，时间复杂度是 O(N)。
2. 存储到平衡二叉树中，这里需要检索平衡二叉树的高度，时间复杂度为 O(logN)。
3. 存储到哈希表中，时间复杂度可以到 O(1)。

考虑到性能因素的影响，所以 map 底层实现是哈希表。

内存模型

Map 底层是一个指向 hmap 结构体的指针，以下是 hmap 的结构体(注: 以下只列出几个关键的属性)。

// A header for a Go map.
type hmap struct {
  .....
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
  ....
}

• B: 2^B 表示 bucket 的数量，比如 b = 3，那么在 hmap 中存储了 8 个桶。
• hash0: 作为 hash 种子使用。
• buckets: 存储具体 key/value 的 bucket 数组，里面每个 bucket 本质也是指向结构体的一个指针，其指向的结构体是 bmap，但是这个 bucket 的定义更多是占位符的作用，其实 bmap 真正的内存布局应该是以下第二种方式，这个真正的结构体是在编译期生成的，然后在运行期挂载上这个属性。

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8
}
// bmap 真正的内存布局
type bmap struct {
    tophash     [bucketCnt]uint8
    keys        [bucketCnt]keyType
    values      [bucketCnt]valueType
    pad         uintptr
    overflowPtr uintptr
}

所以 bmap 的内存布局应该如下图所示：

• 在 bmap 中 keys 和 values 是单独存储的，比如 key1/key2，然后再是 value1/valu2
  • 其实更常规的方式应该是 key/elem/key/elem/...，hmap 这里使用先 key，再 value 的存储方式是为了节省内存。

同是为了验证上文的内存模型，可以使用 dlv 工具分析下，比如以下代码

func main() {
	m := make(map[int]int, 4)
	m[1] = 3
	m[2] = 4
	value, ok := m[2]
	fmt.Println(value, ok)
}

具体 debug 分析结果如下: 通过以下 key 和 value 的内存布局，可以看出和上面的内存布局图是吻合的。

➜  maptest dlv debug . 
Type 'help' for list of commands.
(dlv) break b runtime.mapaccess2_fast64
....
(dlv) print b 
*runtime.bmap {
        tophash: [8]uint8 [239,74,0,0,0,0,0,0],}
(dlv) examinemem -count 16 -size 8 -x b 
0xc00009de38:   0x0000000000004aef   0x0000000000000001   0x0000000000000002   0x0000000000000000   0x0000000000000000   0x0000000000000000   0x0000000000000000   0x0000000000000000   
0xc00009de78:   0x0000000000000000   0x0000000000000003   0x0000000000000004   0x0000000000000000   0x0000000000000000   0x0000000000000000   0x0000000000000000   0x0000000000000000  

Hack Map 底层

说明:

• 本文不会详细分析 map 的源代码，而是通过 hack map 的方式理解 map 的底层实现。
• 以下使用 golang 版本是最新版本 1.9。

首先，如果可以把 map 结构转化为 hmap 结构，这样就更容易理解其内部实现了。幸运的是，可以借助 unsafe.Pointer 和 empty interface 进行转化，首先把 map 结构转化为 unsafe.Pointer，然后再转化为 emptyInterface 结构体，emptyInterface 结构体的 value 属性就是 hmap。

type emptyInterface struct {
	_type unsafe.Pointer
	value unsafe.Pointer
}

func mapTypeAndValue(m interface{}) (*maptype, *hmap) {
	ei := (*emptyInterface)(unsafe.Pointer(&m))
	return (*maptype)(ei._type), (*hmap)(ei.value)
}

key 在 bucket 中分布

我们从 golang 的 map 源代码中复制 maptype, hmap 结构体和函数，然后编写以下 showSpread 函数就能获取每个 key 值在 bucket 中的分布。

func showSpread(m interface{}) {
	// dataOffset is where the cell data begins in a bmap
	dataOffset := unsafe.Offsetof(struct {
		b bmap
		v int64
	}{}.v)

	t, h := mapTypeAndValue(m)

	fmt.Printf("Overflow buckets: %d", h.noverflow)

	numBuckets := 1 << h.B

	for r := 0; r < numBuckets*bucketCnt; r++ {
		bucketIndex := r / bucketCnt
		cellIndex := r % bucketCnt

		if cellIndex == 0 {
			fmt.Printf("\nBucket %3d:", bucketIndex)
		}

		// lookup cell
		b := (*bmap)(add(h.buckets, uintptr(bucketIndex)*uintptr(t.bucketsize)))
		if b.tophash[cellIndex] == 0 {
			// cell is empty
			continue
		}

		k := add(unsafe.Pointer(b), dataOffset+uintptr(cellIndex)*uintptr(t.keysize))

		ei := emptyInterface{
			_type: unsafe.Pointer(t.key),
			value: k,
		}
		key := *(*interface{})(unsafe.Pointer(&ei))
		fmt.Printf(" %3d", key.(int))
	}
	fmt.Printf("\n\n")
}

以上代码的流程图如下

• 首先把 map 转化为 hmap 结构；然后获取 bucket 的数量 numBuckets。
• 依次遍历 bucket 中的每个 key 值
  • 根据每个 key 值获取其对应的 bmap 结构，如果 bmap 中的对应的 key 值是空，说明没存储值，直接跳过。
  • 否则就存储值了，再根据 bmap dataOffset 的偏移量获取 key 值
  • 最后通过 emptyInterface 把 key 转化到 int 值

可以通过 docker run --rm -it -v $(pwd):/app golang:1.19 go run /app/main.go 执行以下代码

func main() {
	m := make(map[int]int)

	for i := 0; i < 10; i++ {
		m[i] = i * 3
	}

	showSpread(m)
}

最后打印结果一下，可以看到 map 中的 key 是分布到两个 bucket 中。

➜  mapTest docker run --rm -it -v $(pwd):/app golang:1.19 go run /app/main.go 
Overflow buckets: 0
Bucket   0:   0   1   6   7   9
Bucket   1:   2   3   4   5   8

代码详见: github

查找值

同样我们需要 hack map 的底层，把 map 转化为 hmap 结构，然后看下 map 是如何根据一个 key 查到 value 的。

func main() {
	abc := make(map[int]int, 100)
	for i := 0; i < 100; i++ {
		abc[i] = i * i
	}

	t, h := mapTypeAndValue(abc)

	// 查找 value 的过程
	key := 40
	hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))

	m := bucketMask(h.B)
	var b *bmap
	b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	for ; b != nil; b = b.overflow(t) {
		for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
			if *(*uint64)(k) == uint64(key) && !isEmpty(b.tophash[i]) {
				value := add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.elemsize))
				fmt.Println(value, *(*uint64)(value))
			}
		}
	}
}

以上代码的流程图如下

• 首先把 map 转化为 hmap 结构
• 根据存储 hash 值找到对应的 bucket
  • 遍历 bucket 找到对应的 key
  • 根据偏移量找到对应的 value
  • 否则返回空值

最后通过 docker run --rm -it -v $(pwd):/app golang:1.19 go run /app/retrieve.go 执行以上代码，打印结果为

0xc000122058 1600	

说明已经可以成功检索到相应的 value 值了。

代码详见: github

既然清楚了 map 的底层实现，下面我们看下 map 的一些常见错误。

常见错误

函数之间传递 map

以下代码中，map 作为函数参数传递，通过 map 内存模型我们已经知道「Map 底层是一个指向 hmap 结构体的指针」，然后执行以下代码。

package main

import "fmt"

func main() {
	myMap := map[string]string{
		"key": "value",
	}

	fmt.Println(myMap) // 打印 'map[key:value]'

	DoWork(myMap)

	fmt.Println(myMap) // 打印 'map[dog:cat key:value]'
}

func DoWork(m map[string]string) {
	m["dog"] = "cat"
}

以上函数对 map 的修改是会反映到 main 函数中，因此最后结果打印为 map[dog:cat key:value]。

并发读写

比如我们有以下例子: 两个 goroutine，其中一个 goroutine 正在读 map，而另一个 goroutine 写 map，尝试执行以下程序。

package main

import (
	"fmt"
	"time"
)

func read(m map[string]string, key string) string {
	if value, ok := m[key]; ok {
		return value
	}
	return ""
}

func write(m map[string]string, key, value string) {
	m[key] = value
}

func main() {
	m := map[string]string{}

	go func() {
		write(m, "name", "zhangsan")
	}()

	go func() {
		value := read(m, "name")
		fmt.Println(value)
	}()
	time.Sleep(time.Second)
}

通过 go run --race main.go 执行后，会发现有一些报错的，因为以上程序是会导致数据竞争的，解决此问题的办法是加锁。

通过给 read、write 函数加锁即可。

var (
   mutex sync.RWMutex
)
func read(m map[string]string, key string) string {
	mutex.RLock()
	defer mutex.RUnlock()
	if value, ok := m[key]; ok {
		return value
	}
	return ""
}

func write(m map[string]string, key, value string) {
	mutex.Lock()
	defer mutex.Unlock()
	m[key] = value
}

注意⚠️: map 可以并发读，但是不能并发写或者并发读写。

总结

本文首先分析了 golang map 的底层逻辑， 说明 map 本质是一个指向 hmap 结构体的指针，然后通过 hack 的一些方式验证了 map 的 buckets 以及根据 key 查到 value 的逻辑，最后根据 map 的底层实现，引出了一些其中常见的错误，比如: 函数之间传递 map 和并发读写。

最后，希望本篇文章真的能给你带来收获，你的点赞和评论将是我持续创作的巨大动力。

参考

groups.google.com/g/golang-nu…

hackernoon.com/some-insigh…

levelup.gitconnected.com/memory-allo…