从源码学习 Go 的基础数据结构 —— Map

博主： EwdAger
发布时间：2021 年 06 月 09 日
837次浏览
暂无评论
16927字数
分类： Golang 学习笔记

# 0x01

本篇源码分析基于 **Go 1.14.12** 注意信息时效
</div>

哈希表是几乎每个语言里都拥有的数据结构，Go 里面也不例外。但是不同的语言其哈希表的实现还是略微有些不同的，接下来我们来分析 Go 中哈希表 Map 的实现。

# Go 中 Map 的实现

## Map 的创建

跟前面几篇文章一样，我们先通过创建 Map 找到函数的位置，进而找到他的数据结构

![image.png](https://gvoidy.cn/usr/uploads/2021/06/3373685133.png)

```go
func makemap(t *maptype, hint int, h *hmap) *hmap {
	...
	return h
}
```

然后我们就能从这个函数的返回值里找到 Map 的数据结构 `hmap`

## Map 的数据结构

```go
// A header for a Go map.
type hmap struct {

count     int // # live cells == size of map.  Must be first (used by len() builtin)
		      // 存活的元素个数，可以用 len() 来统计
	flags     uint8
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
			 // 用于控制 buckets 最大值系数，即 2^B 个 buckets
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
			 // overflow buckets 的数量
	hash0     uint32 // hash seed
			 // hash 种子，用来防止哈希碰撞
	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
				  // 一个最大长度为 2^B 的数组，其中元素为 bmap 结构
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when 		    growing  
				  // 和 buckets 一样的结构，用于扩容时存储旧数据
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
				  // 发生扩容后的搬迁数，小于buckets长度时表示已经搬完
	extra *mapextra // optional fields
			// 而外的 overflow 信息，不一定每个 map 都有
}

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap

// nextOverflow holds a pointer to a free overflow bucket.
	// 指向下一个 overflow bucket
	nextOverflow *bmap
}

// A bucket for a Go map.
type bmap struct {

tophash [bucketCnt]uint8

}
```

梳理 `hmap` 的时候发现里面还有一个 `mapextra`和`bmap`结构，`mapextra`还比较好理解，`bmap`我们先不管。通过 `hmap`的结构我们大致可以看出`hmap`是一个如下图这样的结构。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2138082877.png)

那么再回看 `bmap` 为啥结构体内只有个 `tophash`字段， 经过[查阅](https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/)得到了以下这个解释：

> 桶的结构体 [`runtime.bmap`](https://draveness.me/golang/tree/runtime.bmap) 在 Go 语言源代码中的定义只包含一个简单的 `tophash` 字段，`tophash` 存储了键的哈希的高 8 位，通过比较不同键的哈希的高 8 位可以减少访问键值对次数以提高性能：
>
> 在运行期间，[`runtime.bmap`](https://draveness.me/golang/tree/runtime.bmap) 结构体其实不止包含 `tophash` 字段，因为哈希表中可能存储不同类型的键值对，而且 Go 语言也不支持泛型，所以键值对占据的内存空间大小只能在编译时进行推导。[`runtime.bmap`](https://draveness.me/golang/tree/runtime.bmap) 中的其他字段在运行时也都是通过计算内存地址的方式访问的，所以它的定义中就不包含这些字段，不过我们能根据编译期间的 [`cmd/compile/internal/gc.bmap`](https://draveness.me/golang/tree/cmd/compile/internal/gc.bmap) 函数重建它的结构：

得到了以下这个结构：

```go
type bmap struct {
    topbits  [8]uint8  // tophash 值
    keys     [8]keytype 
    values   [8]valuetype 
    overflow uintptr  // 指向 overflow 发生时的 bmap bucket
}
```

然后我们就能得出结论，一个 Map 是由`hmap`构成的，而一个`hmap`内有由最大2^B个`bmap`组成的`buckets`，真正的 `Key-Value`结构是在 `bmap` 内实现的，并且 Map 提供了一堆处理 overflow 的字段。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/4166731956.png)

## Map 的 Hash 实现

从上面我们总结的 Map 数据结构图，那么一个 `key - value` 的结构是怎么插入到 Map 中的呢？

1. 使用 hash 函数计算 key 的 hash value
2. 取 hash value 二进制位的后 5 位 (low bits)
3. 计算 `low bits & bucketMask` ，`bucketMask` 为 `1 << B - 1`，得到的答案为所取 `buckets` 中的具体 `bmap` 位置
4. 完整遍历 `bmap` 中的 `tophash` 数组，看数组中有没有与 hash value 的 `tophash` 相等的值，如果有且已经存在的 `key` 等于要存入的 `key` 就覆盖对应 `key`的`value`，如果没有就继续遍历 `overflow`指向的`bmap`中的`tophash`。等全部遍历完毕都没有发现相等的 `tophash`，就存入之前遍历就已经记录的空位中了。同理，如果遍历一遍未发现相等的 `tophash`值也没有空位，则新建一个`bmap`将`overflow`的指针指向新建的`bmap`，再将其填充到新 `bmap` 中。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/345240761.png)

由此可见，Go 中 Map 的防止哈希冲突的方式是使用了 **拉链法** 解决的。这里补充一下 **拉链法** 的定义：

> 拉链法是哈希表最常见的实现方法，大多数的编程语言都用拉链法实现哈希表，它的实现比较开放地址法稍微复杂一些，但是平均查找的长度也比较短，各个用于存储节点的内存都是动态申请的，可以节省比较多的存储空间。
>
> 实现拉链法一般会使用数组加上链表，不过一些编程语言会在拉链法的哈希中引入红黑树以优化性能，拉链法会使用链表数组作为哈希底层的数据结构，我们可以将它看成可以扩展的二维数组：
>
> ![separate-chaing-and-set](https://gvoidy.cn/usr/uploads/2021/06/2366016604.png)

具体代码位置，以 `mapassign_fast64()` 为例。

```go
func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {

// 一堆判断，暂时不看
    ...

// 计算 key 的 hash value
    hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))

// 扩容相关的，暂时不看
    ...

again:
    // 通过 low bits 和 bucketMask 找到 buckets 里具体的 bmap
    bucket := hash & bucketMask(h.B)
    // 扩容相关的，暂时不看
    ...
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))

var insertb *bmap
    var inserti uintptr
    var insertk unsafe.Pointer

bucketloop:

for {
        // 遍历当前 bmap 的 tophash
        for i := uintptr(0); i < bucketCnt; i++ {

// 记录第一个空的 tophash 位置
            if isEmpty(b.tophash[i]) {
                if insertb == nil {
                    insertb = b
                    inserti = i
                }
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }

k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8)))
            // 当前 tophash 对应的 key 与 传入的 key 不相等，跳过
            if k != key {
                continue
            }
            insertb = b
            inserti = i
            goto done
        }
        // 如果当前 bmap 里没找到取 overflow 里找
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

// Did not find mapping for key. Allocate new cell & add entry.

// 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
    }

if insertb == nil {
        // all current buckets are full, allocate a new one.
        insertb = h.newoverflow(t, b)
        inserti = 0 // not necessary, but avoids needlessly spilling inserti
    }
    insertb.tophash[inserti&(bucketCnt-1)] = tophash(hash) // mask inserti to avoid bounds checks

insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8)
    // store new key at insert position
    *(*uint64)(insertk) = key

h.count++

done:
    elem := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*8+inserti*uintptr(t.elemsize))
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting
    return elem
}
```

## Map 的基本操作(访问、更新和删除)

看完了 Map hash 的具体过程，其实同时也知道了 Map 是怎么进行 **插入更新** 的（就是上面`mapassign_xxxx()`的代码），接下来顺手也把 Map 访问和删除代码分析一下吧。

### Map 的访问 `mapaccess`

这里以 `mapaccess1_fast64()`为例，其中 `mapaccess2` 和 `fast64`的意义请直接看最后的 **其他细节**，并且这里不考虑扩容的情况，扩容情况处理代码已隐藏。

```##go
func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
    ...
    // 计算 key 的 hash value
    hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))
    // 取 bucketMask
    m := bucketMask(h.B)

// 通过 low bits 和 bucketMask 找到 buckets 里具体的 bmap
    b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

...

// 开始遍历当前 bmap 下的 tophash 和 overflow 指向的 bmap
    for ; b != nil; b = b.overflow(t) {
        // 遍历当前 bmap 的 keys
        for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
            // 如果 bmap 里的 key 与当前 key 相等且 tophash 不为空（扩容可能搬迁 key）
            if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) {
                // 返回找到的 value
                return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.elemsize))
            }
        }
    }
    // 没找到返回 nil
    return unsafe.Pointer(&zeroVal[0])
}
```

### Map 的删除`mapdelete`

看了会发现定位逻辑几乎跟 `mapassign`几乎一模一样，这里就不贴了。唯一要注意的是，Map 删除元素不是真删除，而是做了一个标记。

```go
func mapdelete_fast64(t *maptype, h *hmap, key uint64) {
    ...
    for ; b != nil; b = b.overflow(t) {
	for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) {
            // 先判断 key 是否相等
            if key != *(*uint64)(k) || isEmpty(b.tophash[i]) {
                continue
	    }
  
            ...
            // 当前位置的 tophash 标记为 0
            b.tophash[i] = emptyOne // emptyOne == 0
}
```

## Map 扩容

按照我们上面的分析的思路，是不发现了一个很严重的问题，即当 key 在 `bmap` 里没有位置时会在 `overflow` 后面链一个新 `bmap`，同时当 `hmap` 的 bucket 不够时，会在 `overflow` 里链一个新的 `hmap`。当这个 Map overflow 越来越多时，Map 的性能会越来越差，因为每次都要遍历所以 `overflow` 甚至会接近 `O(N)`。Go 的设计者们当然不允许这种情况出现，所以在 Map 的 overflow 到一定程度的时候，会发生自动扩容，而扩容也分解决 `bmap overflow`链表过长的 **等大扩容(same size grow)** 和解决 `hmap overflow`链表过长的 **增大扩容(bigger size grow)**。

回到刚刚我们看的 Map 更新操作的地方，有一个何时发生扩容的判断（在上面的代码已经隐藏了），即：

* 触发 `load factor` 的最大值，负载因子已达到当前界限
* 溢出桶 `overflow buckets` 过多

```go
// 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
}
```

### 等大扩容(same size grow)

等大扩容只发生在一种特殊情况，即原有 `bmap` 里的已经有很多元素被删除了，留下了许多空槽。等大扩容的目的就是把这些“碎片”拍平整合起来。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2829083928.png)

### 增大扩容(bigger size grow)

增大扩容就是直接把 `hmap` 里的 buckets 数量翻一倍，即将当前 `B` 加一。因为 `B`的值改变了，我们前面用于判断 key 插入哪个槽位的 `hashMask` 也会相应的改变，所以该 Map 下的所有元素都需要重新计算 bucket 的槽位。当完成了增大扩容，其 `overflow` 上的元素也因为搬迁而被分配到 bucket 里了。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/715867073.png)

### 伴随扩容而来的搬迁操作

既然发生扩容操作所有的元素会被移到新的位置或者 bucket 里，那么搬迁是在什么时候发生的呢？回到刚刚我们看到的扩容代码，在判断是否需要发生扩容后，调用了一个 `hashGrow(t, h)` 方法，进行扩容。我们来看看这部分代码。

```go
func hashGrow(t *maptype, h *hmap) {
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }

// 将老的 buckets 挂在 oldbuckets 上
    oldbuckets := h.buckets
    // 创建一个新的 buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

// 一堆初始化操作
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0

h.extra.oldoverflow = h.extra.overflow
    h.extra.overflow = nil
    h.extra.nextOverflow = nextOverflow
}
```

可以看到，这里的扩容只预申请了一片空间（没有申请完整的内存），并没有对数据进行拷贝和转移。然后我们回想一下刚刚分析的代码，在更新操作`mapassign()`有一个`growWork()`函数的调用：

```go
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    if h.growing() {
        growWork(t, h, bucket)
    }
    ...
}
```

这里就可以很明显的看出是在进行真正的扩容搬运工作了，我们再来看下这个函数的调用，发现只有在更新`mapassign` 和删除 `mapdelete` 时才会进行搬迁。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/206040316.png)

我们回过头再来看看这个 `growWork()`函数，可以看出，每次进行搬运会搬运两个 bucket。

```##go
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
	// 具体的搬运逻辑，比较复杂这里不展开讲了
	evacuate(t, h, bucket&h.oldbucketmask())

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

最后我们总结一下 **扩容和搬运** ：

- 当 Map 的 `overflow` 过多时，Map 会进行等大扩容或者增量扩容，两种扩容方法降低 Map 访问元素的时间复杂度
- 判断需要扩容操作后，先预申请一部分空间，但不马上进行扩容，并且把需要进行扩容的标志位打开、把扩容前的 `buckets` 放到 `oldbuckets`里，`overflow` 也挂在 `oldoverflow`后面。
- 当该 Map 进行更新 `mapassign`和删除 `mapdelete`操作时才会进行搬运，并且是把当前 key 匹配到的 oldbucket 搬运到新的 bucket 里，再顺手查一下 oldbuckets 有没有搬运完全，没有完全就再搬运后面一个 oldbucket
- `mapaccess` 优先在 oldbuckets 中找，如果命中，则说明这个 bucket 没有被搬运

### Map 的缩容

我们能很顺其自然的想到，Map 的空间不够用了 Go 会自动帮我们进行扩容，但是后面这个 Map 的元素又被删的差不多了，Go 会不会帮我们自动缩容？我们来测试一下：

```go
package main

import (
    "fmt"
)

func main() {
    dict := make(map[int]int, 10)
    a := dict[0]
    fmt.Println(a)

for i := 0; i < 10000; i++ {
        dict[i] = 1
    }
    a = dict[0]
    fmt.Println(a)

for i := 0; i < 10000; i++ {
        delete(dict, i)
    }
    a = dict[0]
    fmt.Println(a)
}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/1301722026.png)

然后在`mapaccess1_fast64()`上打断点，看每一次 `h.B`的值，即可大致看出当前 Map buckets 的容量。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/1467223012.png)

三次查询 `h.B`的值分别是 `1 -> 11 -> 11`，说明即便我们 `delete()` 了 Map 也不会进行缩容。在可以**预期的 Map 容量大幅扩大**以后我们可以进行手动缩容(感觉有点蠢)：

```go
newDict := make(map[int]int, 10000 - 999)
for k, v := range dict {
    newDict[k] = v
}
dict = nil
```

# Map 的遍历

Go 的Map 的遍历比较有趣，为啥每次 Map 的遍历输出顺序都是随机的呢？接下来我们分析一下遍历，先看下函数调用顺序。

```go
package main

import "fmt"

func main() {
    dict := make(map[int]int, 10)

for k, v := range dict {
        fmt.Println(k, v)
    }

}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2434750245.png)

可以看出先调用了 `mapiterinit()` 然后调用 `mapiternext()`遍历。

```go
func mapiterinit(t *maptype, h *hmap, it *hiter) {

// 一堆判断
    ...

it.t = t
    it.h = h

// grab snapshot of bucket state
    it.B = h.B
    it.buckets = h.buckets

// 判断
    ...

// 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))

// iterator state
    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)
}
```

可以看出 `mapiterinit()`先初始化了一个`hiter`对象，并且随机出(`fastrand()`)了一个 `offset`和 `bucket`，即从一个随机的 `bucket` 里的随机`offset`位置开始遍历，具体逻辑如下图：

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2355798884.png)

当 Map 发生扩容时，需要先从 `oldbuckets` 和 `buckets`里找这些元素，逻辑有点复杂（其实是我太菜了看不太懂细节）就不展开提了。

# 其他细节

## Q: 为啥不直接把`key`、`values`、`overflow`直接放入`bmap`结构体

A：至于为啥 `bmap` 没有直接把`key`、`values`、`overflow`直接放入 `bmap` 结构体里。感觉应该是 Go (1.14)在目前版本没有泛型，所以官方可能不太想写一大堆各种类型的 `bmap` 结构，所以把这些东西指针通过 `unsafe`来访问。

至于没有泛型，在 Map 里是个很大的问题，因为`key`和`value`的类型繁多，所以官方几乎每一种函数都写个几个对应版本的相似函数：

![从曹大PPT里盗的图，再次感谢曹大](https://gvoidy.cn/usr/uploads/2021/06/2705170385.png)

## Q: 为什么 Map 能 `v1 := m[1]`和 `v2, ok := m[2]`？

```go
package main

import "fmt"

func main() {
    m := make(map[int]int, 10)
    m[0] = 0
    m[1] = 1

v1 := m[0]
    v2, ok := m[1]

fmt.Println(v1)
    fmt.Println(v2, ok)
}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/3203640813.png)

具体看第 10、11 行的 CALL，分别调用了 `mapaccess1_fast64()`和`mapaccess2_fast64()`，然后他们的返回值分别是：

```go
func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
    ...
    // 其中一种返回情况，这里只是表示返回了一个值
    return unsafe.Pointer(&zeroVal[0])
}

func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) {
    ...
    // 其中一种返回情况，这里只是表示返回了两个值
    return unsafe.Pointer(&zeroVal[0]), false
}
```

所以得出结论，这就是一个 Go 的语法糖，这两种写法编译器帮我们定位到了不同的函数上，顺带一提 `mapaccess1_fast64()`和`mapaccess2_fast64()` 的 `fast64`代表元素的类型，这也就是上面我们提到的因为目前版本的 Go 里没有泛型，所以写了一大坨功能类似的函数的原因。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2606308845.png)

## Map `value` 为啥不能取地址

```go
package main

func main() {
    dict := make(map[int][]int, 10)
    dict[1] = []int{1, 2, 3}

_ = &[]int{1, 2, 3}

// compile error: cannot take address of map element
    _ = &dict[1]
}
```

其实经过上面的分析，我们其实已经可以得出结论了，Map 中 `value` 的地址是不稳定的，因为 Map 随时会发生扩容，而扩容会迁移数据，如果 Go 允许这种语法，那么当前的指针不就变成 **悬垂指针** 了？而 Go 里显然是不允许悬垂指针的，所以 Go 在编译的时候直接拒绝这种语法了。

## 并发安全的 Map `sync.Map`

Go 语言中的 Map 是非并发安全的，如果在并发中同时读写会在 runtime 的时候触发 `fatal error: concurrent map read and map write`

```go
package main

import (
    "fmt"
    "time"
)

func main() {
    dict := make(map[int]int, 100)

go func() {
        for i := 0; i < 100; i++ {
            dict[i] = i
        }
    }()

go func() {
        for i := 0; i < 100; i++ {
            v := dict[i]
            fmt.Println(v)
        }
    }()
    time.Sleep(time.Hour)
}

```

我们使用 `sync` 包中的 Map 即可解决并发安全的问题(注：这个 Map 也就是个使用了读写锁 + dirty map维护了一下的 Map，适合 **读多写少** 的场景)，具有以下[方法](https://golang.org/pkg/sync/#Map)：

> ![image.png](https://gvoidy.cn/usr/uploads/2021/06/3991135154.png)

我们测试一下：

```go
package main

import (
    "fmt"
    "sync"
    "time"
)

func main() {
    dict := sync.Map{}

go func() {
        for i := 0; i < 100; i++ {
	    // 写
            dict.Store(i, i)
        }
    }()

go func() {

for i := 0; i < 100; i++ {
           // 读
           fmt.Println(dict.Load(i))
       }
    }()

go func() {
        time.Sleep(time.Second)
        // 遍历
        dict.Range(func(k, v interface{}) bool {
            fmt.Println(k, v)
            return true
        })
    }()
    time.Sleep(time.Hour)
}

```

# Reference

[Dig101:Go之读懂map的底层设计](http://blog.newbmiao.com/2020/02/04/dig101-golang-map.html)

[Go map原理剖析](https://segmentfault.com/a/1190000020616487)

[Go 语言设计与实现 - 哈希表](https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/)

[深入理解 Go map：赋值和扩容迁移](https://segmentfault.com/a/1190000018632347)

[Go 语言圣经 - MAP](https://book.itsfun.top/gopl-zh/ch4/ch4-03.html)

[由浅入深聊聊Golang的sync.Map](https://juejin.cn/post/6844903895227957262)

最后修改：2021 年 08 月 05 日 09 : 55 AM

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

名称 *

🎲

邮箱

地址

从源码学习 Go 的基础数据结构 —— Map

EwdAger • 2021 年 06 月 09 日

# 0x01

本篇源码分析基于 **Go 1.14.12** 注意信息时效
</div>

# Go 中 Map 的实现

## Map 的创建

跟前面几篇文章一样，我们先通过创建 Map 找到函数的位置，进而找到他的数据结构

![image.png](https://gvoidy.cn/usr/uploads/2021/06/3373685133.png)

```go
func makemap(t *maptype, hint int, h *hmap) *hmap {
	...
	return h
}
```

然后我们就能从这个函数的返回值里找到 Map 的数据结构 `hmap`

## Map 的数据结构

```go
// A header for a Go map.
type hmap struct {

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap

// nextOverflow holds a pointer to a free overflow bucket.
	// 指向下一个 overflow bucket
	nextOverflow *bmap
}

// A bucket for a Go map.
type bmap struct {

tophash [bucketCnt]uint8

}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2138082877.png)

得到了以下这个结构：

```go
type bmap struct {
    topbits  [8]uint8  // tophash 值
    keys     [8]keytype 
    values   [8]valuetype 
    overflow uintptr  // 指向 overflow 发生时的 bmap bucket
}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/4166731956.png)

## Map 的 Hash 实现

从上面我们总结的 Map 数据结构图，那么一个 `key - value` 的结构是怎么插入到 Map 中的呢？

![image.png](https://gvoidy.cn/usr/uploads/2021/06/345240761.png)

由此可见，Go 中 Map 的防止哈希冲突的方式是使用了 **拉链法** 解决的。这里补充一下 **拉链法** 的定义：

具体代码位置，以 `mapassign_fast64()` 为例。

```go
func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {

// 一堆判断，暂时不看
    ...

// 计算 key 的 hash value
    hash := t.hasher(noescape(unsafe.Pointer(&key)), uintptr(h.hash0))

// 扩容相关的，暂时不看
    ...

var insertb *bmap
    var inserti uintptr
    var insertk unsafe.Pointer

bucketloop:

for {
        // 遍历当前 bmap 的 tophash
        for i := uintptr(0); i < bucketCnt; i++ {

// Did not find mapping for key. Allocate new cell & add entry.

insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8)
    // store new key at insert position
    *(*uint64)(insertk) = key

h.count++

## Map 的基本操作(访问、更新和删除)

### Map 的访问 `mapaccess`

这里以 `mapaccess1_fast64()`为例，其中 `mapaccess2` 和 `fast64`的意义请直接看最后的 **其他细节**，并且这里不考虑扩容的情况，扩容情况处理代码已隐藏。

// 通过 low bits 和 bucketMask 找到 buckets 里具体的 bmap
    b = (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

...

### Map 的删除`mapdelete`

看了会发现定位逻辑几乎跟 `mapassign`几乎一模一样，这里就不贴了。唯一要注意的是，Map 删除元素不是真删除，而是做了一个标记。

## Map 扩容

回到刚刚我们看的 Map 更新操作的地方，有一个何时发生扩容的判断（在上面的代码已经隐藏了），即：

* 触发 `load factor` 的最大值，负载因子已达到当前界限
* 溢出桶 `overflow buckets` 过多

```go
// 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
}
```

### 等大扩容(same size grow)

等大扩容只发生在一种特殊情况，即原有 `bmap` 里的已经有很多元素被删除了，留下了许多空槽。等大扩容的目的就是把这些“碎片”拍平整合起来。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2829083928.png)

### 增大扩容(bigger size grow)

![image.png](https://gvoidy.cn/usr/uploads/2021/06/715867073.png)

### 伴随扩容而来的搬迁操作

```go
func hashGrow(t *maptype, h *hmap) {
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }

// 将老的 buckets 挂在 oldbuckets 上
    oldbuckets := h.buckets
    // 创建一个新的 buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

// 一堆初始化操作
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0

h.extra.oldoverflow = h.extra.overflow
    h.extra.overflow = nil
    h.extra.nextOverflow = nextOverflow
}
```

```go
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    if h.growing() {
        growWork(t, h, bucket)
    }
    ...
}
```

这里就可以很明显的看出是在进行真正的扩容搬运工作了，我们再来看下这个函数的调用，发现只有在更新`mapassign` 和删除 `mapdelete` 时才会进行搬迁。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/206040316.png)

我们回过头再来看看这个 `growWork()`函数，可以看出，每次进行搬运会搬运两个 bucket。

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

最后我们总结一下 **扩容和搬运** ：

### Map 的缩容

```go
package main

import (
    "fmt"
)

func main() {
    dict := make(map[int]int, 10)
    a := dict[0]
    fmt.Println(a)

for i := 0; i < 10000; i++ {
        dict[i] = 1
    }
    a = dict[0]
    fmt.Println(a)

for i := 0; i < 10000; i++ {
        delete(dict, i)
    }
    a = dict[0]
    fmt.Println(a)
}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/1301722026.png)

然后在`mapaccess1_fast64()`上打断点，看每一次 `h.B`的值，即可大致看出当前 Map buckets 的容量。

![image.png](https://gvoidy.cn/usr/uploads/2021/06/1467223012.png)

```go
newDict := make(map[int]int, 10000 - 999)
for k, v := range dict {
    newDict[k] = v
}
dict = nil
```

# Map 的遍历

Go 的Map 的遍历比较有趣，为啥每次 Map 的遍历输出顺序都是随机的呢？接下来我们分析一下遍历，先看下函数调用顺序。

```go
package main

import "fmt"

func main() {
    dict := make(map[int]int, 10)

for k, v := range dict {
        fmt.Println(k, v)
    }

}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2434750245.png)

可以看出先调用了 `mapiterinit()` 然后调用 `mapiternext()`遍历。

```go
func mapiterinit(t *maptype, h *hmap, it *hiter) {

// 一堆判断
    ...

it.t = t
    it.h = h

// grab snapshot of bucket state
    it.B = h.B
    it.buckets = h.buckets

// 判断
    ...

// iterator state
    it.bucket = it.startBucket

mapiternext(it)
}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2355798884.png)

当 Map 发生扩容时，需要先从 `oldbuckets` 和 `buckets`里找这些元素，逻辑有点复杂（其实是我太菜了看不太懂细节）就不展开提了。

# 其他细节

## Q: 为啥不直接把`key`、`values`、`overflow`直接放入`bmap`结构体

至于没有泛型，在 Map 里是个很大的问题，因为`key`和`value`的类型繁多，所以官方几乎每一种函数都写个几个对应版本的相似函数：

![从曹大PPT里盗的图，再次感谢曹大](https://gvoidy.cn/usr/uploads/2021/06/2705170385.png)

## Q: 为什么 Map 能 `v1 := m[1]`和 `v2, ok := m[2]`？

```go
package main

import "fmt"

func main() {
    m := make(map[int]int, 10)
    m[0] = 0
    m[1] = 1

v1 := m[0]
    v2, ok := m[1]

fmt.Println(v1)
    fmt.Println(v2, ok)
}
```

![image.png](https://gvoidy.cn/usr/uploads/2021/06/3203640813.png)

具体看第 10、11 行的 CALL，分别调用了 `mapaccess1_fast64()`和`mapaccess2_fast64()`，然后他们的返回值分别是：

```go
func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
    ...
    // 其中一种返回情况，这里只是表示返回了一个值
    return unsafe.Pointer(&zeroVal[0])
}

![image.png](https://gvoidy.cn/usr/uploads/2021/06/2606308845.png)

## Map `value` 为啥不能取地址

```go
package main

func main() {
    dict := make(map[int][]int, 10)
    dict[1] = []int{1, 2, 3}

_ = &[]int{1, 2, 3}

// compile error: cannot take address of map element
    _ = &dict[1]
}
```

## 并发安全的 Map `sync.Map`

Go 语言中的 Map 是非并发安全的，如果在并发中同时读写会在 runtime 的时候触发 `fatal error: concurrent map read and map write`

```go
package main

import (
    "fmt"
    "time"
)

func main() {
    dict := make(map[int]int, 100)

go func() {
        for i := 0; i < 100; i++ {
            dict[i] = i
        }
    }()

go func() {
        for i := 0; i < 100; i++ {
            v := dict[i]
            fmt.Println(v)
        }
    }()
    time.Sleep(time.Hour)
}

```

> ![image.png](https://gvoidy.cn/usr/uploads/2021/06/3991135154.png)

我们测试一下：

```go
package main

import (
    "fmt"
    "sync"
    "time"
)

func main() {
    dict := sync.Map{}

go func() {
        for i := 0; i < 100; i++ {
	    // 写
            dict.Store(i, i)
        }
    }()

go func() {

for i := 0; i < 100; i++ {
           // 读
           fmt.Println(dict.Load(i))
       }
    }()

```

# Reference

[Dig101:Go之读懂map的底层设计](http://blog.newbmiao.com/2020/02/04/dig101-golang-map.html)

[Go map原理剖析](https://segmentfault.com/a/1190000020616487)

[Go 语言设计与实现 - 哈希表](https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/)

[深入理解 Go map：赋值和扩容迁移](https://segmentfault.com/a/1190000018632347)

[Go 语言圣经 - MAP](https://book.itsfun.top/gopl-zh/ch4/ch4-03.html)

[由浅入深聊聊Golang的sync.Map](https://juejin.cn/post/6844903895227957262)

发表评论 取消回复

从源码学习 Go 的基础数据结构 —— Map

发表评论取消回复