Go 数据结构 - map

golang map
golang
发布日期:   2021-12-28
更新日期:   2025-04-12
文章字数:   4.3k
阅读时长:   16 分
阅读次数:  

Go 数据结构 - map

参考
《Go 语言底层原理剖析》第 8 章
深度解密 Go 语言之 map - 码农桃花源
理解 Golang 哈希表 map 的原理
Go 语言设计与实现 注：本文部分内容从该博客中复制，博主写的太棒了，respect~

map 作为一种基础数据结构，经常会用到，比如统计元素个数、去重等，但是 Go 内置的 map 有个缺点即不支持并发操作。下面将对 map 的使用方式以及底层原理进行介绍，最后再介绍如何实现一个支持并发操作的 map。



1. 简介

很多语言里都支持 map 数据结构，如 Go 的 map、Java 的 HashMap、Python 的 dict，它们逻辑上都是键值对，所以可以把 map 看作一种 key→value 的映射。实现上一般有两种：

  • 哈希表：Go 的 map 以及 Python 的 dict 底层是哈希表。最差查找效率是 O(n)，平均查找效率是 O(1)，遍历哈希表得到的是乱序序列。
  • 搜索树：一般是 AVL 树和红黑树，如 Java1.8 之后 HashMap 的底层就是数组 + 链表 + 红黑树。自平衡搜索树法的最差搜索效率是 O(lgn)，遍历自平衡搜索树，返回的 key 序列，一般会按照从小到大的顺序。


2. 基本操作

map 支持增删改查这些基础操作，里面也有一些需要注意的点。

2.1 声明与初始化

需要注意的是 map 只有在初始化之后才能插入 k-v 对。

// 声明之后插入数据
var m map[string]int
m["x"] = 1 // panic: assignment to entry in nil map

// 初始化之后插入数据
m := make(map[int]string)
m["x"] = 1
fmt.Println(m) // map[x:1]

// 字面量初始化
m := map[string]int{
    "x": 1,
    "y": 2,
}
fmt.Println(m) // map[x:1 y:2]

不难理解，声明时并没有给 map 分配内存空间，只有在通过 make 初始化 map(或使用字面量初始化) 后给其分配内存空间才能插入数据，下面来验证一下。

// 声明的 map 没有实际的地址
var m map[string]int
fmt.Printf("%p, %v\n", m, m) // 0x0, map[]

// 初始化之后的 map 才有实际的地址
m = map[string]int
// m = make(map[int]string, 10) 初始化时可以设置长度，降低扩容的成本
fmt.Printf("%p, %v\n", m, m) // 0xc000100d20, map[]

2.2 增 - 插入键值对

给不存在的数据赋值即为插入操作，插入键值很简单，按照 map 的类型将 key 和 value 绑定起来。

m := make(map[string]int)
m["x"] = 1
m["y"]++ // 在 int 零值的基础上 + 1，在统计个数时很方便
fmt.Println(m) // map[x:1 y:1]

2.3 删 - 删除键值对

使用 delete(mapName, keyName) 即可根据键删除 map 中相应的键值对。

m := make(map[string]int)
m["x"] = 1
m["y"]++
delete(m, "x")
delete(m, "z") // 删除不存在的 kv 相当于不做任何操作
fmt.Println(m) // map[y:1]

2.4 改 - 修改值

给存在的数据赋值即为修改操作。

m := make(map[string]int)
m["x"]++
m["x"] = 10 // 修改 value
fmt.Println(m) // map[x:10]

2.5 查 - 查询值

根据 key 查询值，可以得到 value 以及 key 是否存在的 bool 值，若 key 不存在则返回零值

m := make(map[string]int)
m["x"]++
v := m["x"]
fmt.Println(v) // 1

v, ok := m["x"]
fmt.Println(v, ok) // 1 true

v, ok = m["y"] // y 不存在
fmt.Println(v, ok) // 0 false


3. 实现原理

注：源码在 src/runtime/map.go 中

3.1 map 结构体

3.1.1 hmap

hmap
  • count：元素个数
  • flags：代表当前 map 的状态（是否处于正在写入的状态等）
  • B：桶的数量: 2^B
  • noverflow：溢出桶的数量，当溢出的桶太多时，map 会进行 same-size map growth，其实质是避免溢出桶过大导致内存泄露
  • hash0：计算 key hash 时的种子
  • buckets：指向新桶
  • oldbuckets：指向旧桶，扩容时会用到，所有旧桶中的数据都已经转移到了新桶中时，则清空
  • nevacuate：指示扩容进度，小于此地址的 buckets 迁移完成
  • extra：存储 map 中的溢出桶

3.1.2 bmap

map 的核心是” 桶 “，这也是真正存储 key-value 的数据结构，buckets 和 oldbuckets 是一个指针，最终它指向的是桶的结构体 bmap。

bmap

bmap 里存放 tophash 字段，即长度为 8 的数组，存储着 key 的 hash 值的前 8 位。但这只是表面 src/runtime/map.go 的结构，编译期间会给它加料，动态地创建一个新的结构：

bmap-gc

bmap 桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是 “一类” 的。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有 8 个位置）。

hmap 结构

Go 语言选择将 key 与 value 分开存储而不是以 key/value/key/value 的形式存储，是为了在字节对齐时压缩空间。在根据 key 找 value 的过程中，首先计算 key 的 hash 值从而找到桶的 index(hash%array_size), 找到桶的位置后遍历 tophash 数组，如果在数组中找到了相同的 hash，那么可以接着通过指针的寻址操作找到对应的 key 与 value。

map 结构

3.1.3 mapextra

在 Go 语言中还有一个溢出桶的概念，在执行 hash[key]=value 赋值操作时，当指定桶中的数据超过 8 个时，并不会直接开辟一个新桶，而是将数据放置到溢出桶中，每个桶的最后都存储了 overflow，即溢出桶的指针。在正常情况下，数据是很少会跑到溢出桶里面去的。

mapextra hmap-buckets

当发生以下两种情况之一时，map 会进行重建：

  • map 超过了负载因子大小。
  • 溢出桶的数量过多。

在哈希表中有经典的负载因子的概念：负载因子 = 哈希表中的元素数量 / 桶的数量。负载因子的增大，意味着更多的元素会被分配到同一个桶中，此时效率会减慢。Go 语言中的负载因子为 6.5，当超过其大小后，map 会进行扩容，增大到旧表 2 倍的大小，旧桶的数据会存到 oldbuckets 字段中，并想办法分散转移到新桶中。当旧桶中的数据全部转移到新桶中后，旧桶就会被清空。

溢出桶的数量太多，这时 map 只会新建和原来相同大小的桶，目的是防止溢出桶的数量缓慢增长导致的内存泄露。


3.2 初始化

Go 初始化 map 主要通过两种方式 — 字面量 & 运行时

3.2.1 字面量初始化

m := map[string]int{
    "x": 1,
    "y": 2,
}
fmt.Println(m) // map[x:1 y:2]

如果 map 采取了字面量初始化的方式，那么它最终仍然需要转换为 make 操作。map 的长度被自动推断为字面量的长度，其核心逻辑位于 gc/sinit.go 中，该函数专门用于处理各种类型的字面量。

若 len(map) ≤ 25，则会将字面量初始化的结构体转为以下代码，将 key-value 一次加入 map。

m := make(map[string]int, 2)
m["x"] = 1
m["y"] = 2

若 len(map) > 25，编译器会构建两个数组专门存储 key 与 value，在运行时循环添加数据。

m := make(map[string]int, 26)
vstatk := []string{"a", "b", "c", ... , "z"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i <len(vstak); i++ {
    m[vstatk[i]] = vstatv[i]
}

3.2.2 运行时初始化

小容量 hash 优化：当创建的哈希被分配到栈上并且其容量小于 BUCKETSIZE = 8 时，Go 语言在编译阶段会使用如下方式快速初始化哈希，这也是编译器对小容量的哈希做的优化。

var h *hmap
var hv hmap
var bv bmap
h := &hv
b := &bv
h.buckets = b
h.hash0 = fashtrand0()

makemap

初始化 map 最后调用的都是 makemap 函数

  1. 计算哈希占用的内存是否溢出或者超出能分配的最大值；
  2. 调用 runtime.fastrand 获取一个随机的哈希种子；
  3. 根据传入的 hint 计算出需要的最小需要的桶的数量；
  4. 使用 runtime.makeBucketArray 创建用于保存桶的数组；
makemap

makemap 函数会计算出需要的桶的数量，即 ${log_2N}$ ，并调用 makeBucketArray 函数生成桶和溢出桶。如果初始化时生成了溢出桶，则会放置到 map 的 extra 字段里去。

makeBucketArray

runtime.makeBucketArray 会根据传入的 B 计算出的需要创建的桶数量并在内存中分配一片连续的空间用于存储数据：

makeBucketArray
  • 当桶的数量小于 2^4 时，由于数据较少、使用溢出桶的可能性较低，会省略创建的过程以减少额外开销；
  • 当桶的数量多于 2^4 时，会额外创建 2^(B-4) 个溢出桶；

3.3 查 - 查询值

根据 key 查询 value 时有两种方式，因为 Go 没有函数重载所以会调用两个函数名不同的函数，但是内部逻辑基本相同。

v     := hash[key] // => v     := *mapaccess1(maptype, hash, &key)
v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key)

mapaccess1

mapaccess1 会先算出 key 的 hash 值，再通过 bucketMask 和 add 拿到该键值对所在的桶序号和 hash 值高位的 8 位数字。之后会依次遍历正常桶和溢出桶中的数据，它会先比较 hash 值的高 8 位和桶中存储的 tophash，后比较传入的和桶中的值以加速数据的读写。

用于选择桶序号的是哈希的最低几位，而用于加速访问的是哈希的高 8 位，这种设计能够减少同一个桶中有大量相等 tophash 的概率影响性能。

mapaccess

如上图所示，每一个桶都是一整片的内存空间，当发现桶中的 tophash 与传入键的 tophash 匹配之后，我们会通过指针和偏移量获取哈希中存储的键 keys[0] 并与 key 比较，如果两者相同就会获取目标值的指针 values[0] 并返回。

mapaccess2

mapaccess2 在 mapaccess1 的基础上多返回了一个标识键值对是否存在的 bool 值，使用 v, ok := hash[k] 的形式访问哈希表中元素时，我们能够通过这个布尔值更准确地知道当 v == nil 时，v 到底是哈希中存储的元素还是表示该键对应的元素不存在，所以在访问哈希时，更推荐使用这种方式判断元素是否存在。


3.4 增 / 改 - 写入 / 修改键值对

3.4.1 操作流程

当形如 hash[k] 的表达式出现在赋值符号左侧时，该表达式也会在编译期间转换成 runtime.mapassign 函数的调用。

overflow
  1. 首先是函数会根据传入的键拿到对应的哈希和桶。
  2. 然后通过遍历比较桶中存储的 tophash 和键的哈希，如果找到了相同结果就会返回目标位置的地址。其中 inserti 表示目标元素的在桶中的索引，insertk 和 val 分别表示键值对的地址，获得目标地址之后会通过算术计算寻址获得键值对 k 和 val。
  3. 如果当前桶已经满了，哈希会调用 runtime.hmap.newoverflow 创建新桶或者使用 runtime.hmap 预先在 noverflow 中创建好的桶来保存数据，新创建的桶不仅会被追加到已有桶的末尾，还会增加哈希表的 noverflow 计数器。
  4. 如果当前键值对在哈希中不存在，哈希会为新键值对规划存储的内存地址，通过 runtime.typedmemmove 将键移动到对应的内存空间中并返回键对应值的地址 val。如果当前键值对在哈希中存在，那么就会直接返回目标区域的内存地址，哈希并不会在 runtime.mapassign 这个运行时函数中将值拷贝到桶中，该函数只会返回内存地址，真正的赋值操作是在编译期间插入的。

3.4.2 扩容

随着哈希表中元素的逐渐增加，哈希的性能会逐渐恶化，所以我们需要更多的桶和更大的内存保证哈希的读写性能。

以下两种情况发生时触发哈希的扩容：

  1. 装载因子已经超过 6.5；
  2. 哈希使用了太多溢出桶；

不过因为 Go 语言哈希的扩容不是一个原子的过程，所以 runtime.mapassign 还需要判断当前哈希是否已经处于扩容状态，避免二次扩容造成混乱。

根据触发的条件不同扩容的方式分成两种，如果这次扩容是溢出的桶太多导致的，那么这次扩容就是等量扩容 sameSizeGrow，sameSizeGrow 是一种特殊情况下发生的扩容，当我们持续向哈希中插入数据并将它们全部删除时，如果哈希表中的数据量没有超过阈值，就会不断积累溢出桶造成缓慢的内存泄漏 4。runtime: limit the number of map overflow buckets 引入了 sameSizeGrow 通过复用已有的哈希扩容机制解决该问题，一旦哈希中出现了过多的溢出桶，它会创建新桶保存数据，垃圾回收会清理老的溢出桶并释放内存。

扩容的入口是 runtime.hashGrow ，哈希在扩容的过程中会通过 runtime.makeBucketArray 创建一组新桶和预创建的溢出桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑更新，下图展示了触发扩容后的哈希：

hashgrow

我们在 runtime.hashGrow 中还看不出来等量扩容和翻倍扩容的太多区别，等量扩容创建的新桶数量只是和旧桶一样，该函数中只是创建了新的桶，并没有对数据进行拷贝和转移。哈希表的数据迁移的过程在是 runtime.evacuate 中完成的，它会对传入桶中的元素进行再分配。

runtime.evacuate 会将一个旧桶中的数据分流到两个新桶，所以它会创建两个用于保存分配上下文的 runtime.evacDst 结构体，这两个结构体分别指向了一个新桶。

evacuate

我们简单总结一下哈希表扩容的设计和原理，哈希在存储元素过多时会触发扩容操作，每次都会将桶的数量翻倍，扩容过程不是原子的，而是通过 runtime.growWork 增量触发的，在扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流。除了这种正常的扩容之外，为了解决大量写入、删除造成的内存泄漏问题，哈希引入了 sameSizeGrow 这一机制，在出现较多溢出桶时会整理哈希的内存减少空间的占用。


3.5 删 - 删除键值对

如果想要删除哈希中的元素，就需要使用 Go 语言中的 delete 关键字，这个关键字的唯一作用就是将某一个键对应的元素从哈希表中删除，无论是该键对应的值是否存在，这个内建的函数都不会返回任何的结果。

哈希表的删除逻辑与写入逻辑很相似，只是触发哈希的删除需要使用关键字，如果在删除期间遇到了哈希表的扩容，就会分流桶中的元素，分流结束之后会找到桶中的目标元素完成键值对的删除工作。



4 总结

Go 语言使用拉链法来解决哈希碰撞的问题实现了哈希表，它的访问、写入和删除等操作都在编译期间转换成了运行时的函数或者方法。哈希在每一个桶中存储键对应哈希的前 8 位，当对哈希进行操作时，这些 tophash 就成为可以帮助哈希快速遍历桶中元素的缓存。

哈希表的每个桶都只能存储 8 个键值对，一旦当前哈希的某个桶超出 8 个，新的键值对就会存储到哈希的溢出桶中。随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容，扩容会将桶的数量翻倍，元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大抖动。



文章作者: xuxiangfei
文章链接: http://xxf0512.github.io/posts/7e08620c.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 xuxiangfei !
golang map
  目录