深入理解Go语言的Map

type

status

date

slug

summary

1. 引言

Map 是 GO 语言中的比较高效的数据结构，Map 的查询复杂度是 O(1)。我们在软件开发的过程善用 Map 会很大的提升我们程序。接下来我们首先看下 Map 的基本用法，然后在深入的探讨 Map 的底层原理。

2. Go语言的map的基本用法

2.1. 创建和初始化 map

2.2. 访问和修改 map 中的值

2.3. 检查键是否存在

2.4. 删除 map 中的键

2.5. 遍历 map

2.6. 总结

map 是一种键值对数据结构，键必须是可比较的类型，值可以是任意类型。

可以使用 make 函数创建 map，或者直接初始化。

通过键来访问某个值，如果键不存在则返回该值类型的零值。

使用 delete 函数可以删除 map 中的键。

使用 for range 可以遍历 map 中的所有键值对。

3. Map的基本结构和原理

3.1. Go语言中map的主要数据结构

hmap 是 map 的核心结构，负责存储所有关于 map 的元信息。它的定义如下（来自 runtime/map.go）：

mapextra 是 hmap 结构中的一个附加结构，它存储了溢出桶和旧桶的溢出信息。

bmap 桶，实际存储键值对的地方,每个桶能存储 8 对键值对。

但是在 go1.20 版本之后优化了桶如下

为什么要这样变化?

减少内存浪费：在旧版本中，键和值直接存储在桶中，而桶的大小是固定的。这就意味着，当键和值的大小差异较大时，会产生内存浪费。例如 map[int64]int8，int64 是 8 字节，而 int8 只有 1 字节，在这种情况下，会因为内存对齐和填充的原因浪费很多内存。

提高内存访问效率：在新结构中，键和值存储在连续的内存区域中，这样可以提高内存访问的局部性（locality），从而提高缓存命中率，进而提升性能。

简化桶结构：桶的结构变得更简单，只有 tophash 和溢出指针。这使得桶的大小固定，减少了管理复杂性

通过以上的数据结构我们了解 Go 中 map 的主要数据结构，接下来我们根据这个些数据结构在深入的了解以下几点：

map 创建流程

map 获取值

map 是怎么解决 hash 冲突的

map 的动态扩容

3.2. map 创建流程

在 Go 中，map 的初始化通过 makemap 函数完成。makemap 函数会分配 hmap 结构并进行初始化。

makemap 函数的执行流程：

参数检查：makemap 接受三个参数：键的类型、值的类型和预估的元素数量。如果预估的元素数量大于零，Go 会根据这个值来分配初始的桶大小。

分配 hmap 结构：分配并初始化 hmap 结构体。

初始化桶数组：根据预估的元素数量，计算所需的 B 值（桶数量的幂），并分配桶数组。桶数组的大小是 $2^B$。

随机化哈希种子：每个 map 都会分配一个随机的哈希种子 hash0，用于防止哈希碰撞攻击。

具体代码 golang1.21.6: 305

3.3. map 获取值

计算键的哈希值：首先，通过哈希函数计算要获取值的键的哈希值。

确定桶的位置：使用哈希值确定键值对在 map 中的位置。通过哈希值计算出键应该存储在哪个桶中。

访问桶中的数据：找到对应的桶后，通过桶的 tophash 数组快速筛选出可能存在的键值对，然后在键值存储区域中查找具体的键和值。

处理哈希冲突和溢出桶：如果主桶中的槽位已满，可能存在哈希冲突或溢出桶的情况。在哈希冲突时，需要处理碰撞，并可能需要继续查找溢出桶中的键值对。

返回值：最终从桶中找到对应的值，并返回给用户。

具体的代码 golang1.21.6: 396

3.4. map 是怎么解决 hash 冲突的

常见的解决 hash 冲突的方式有三种：

开放寻址法（Open Addressing）

链地址法（Chaining）

公共溢出区域法（Public Overflow Area）

3.4.1. 开放寻址法（Open Addressing）

计算键的哈希值：首先，通过哈希函数计算要存储或获取值的键的哈希值。

确定初始存储位置：使用哈希值确定键值对在哈希表中的初始存储位置。如果该位置为空，则直接将键值对存储在这里；如果不为空，则继续探查其他位置。

线性探查（Linear Probing）：如果初始存储位置已被占用，线性探查是一种常见的方法，按照固定的步长（通常为1）依次探查下一个位置，直到找到空闲位置或遍历整个表。

二次探查（Quadratic Probing）：另一种探查方法是二次探查，即按照固定的平方步长进行探查。如果初始位置已被占用，尝试在初始位置加上1²、2²、3²等步长处继续探查。

双重散列（Double Hashing）：双重散列是另一种开放寻址法的变体，通过使用第二个哈希函数来计算探查的步长。如果初始位置已被占用，可以使用第二个哈希函数计算出新的步长。

插入或查找键值对：在探查过程中，如果找到空闲位置，则插入键值对；如果找到匹配的键，则返回对应的值；如果探查到达哈希表的末尾仍未找到空闲位置，则哈希表已满。

3.4.2. 链地址法（Chaining）

计算键的哈希值：首先，通过哈希函数计算要存储或获取值的键的哈希值。

确定初始存储位置：使用哈希值确定键值对在哈希表中的初始存储位置。

解决冲突：当发生哈希冲突时（即多个关键字映射到同一个槽），链地址法不会尝试在同一个槽中存储多个元素，而是会在该槽处形成一个链表或其他形式的数据结构，用于存储冲突的元素。

插入元素：当要插入一个元素时，根据哈希函数找到对应的槽，如果该槽已经有元素存在，则将新元素插入到该位置形成链表的新节点，如果该槽为空，则直接插入元素。

3.4.3. 公共溢出区域法（Public Overflow Area）

计算键的哈希值：首先，通过哈希函数计算要存储或获取值的键的哈希值。

确定初始存储位置：使用哈希值确定键值对在哈希表中的初始存储位置。

解决冲突：当发生哈希冲突时（多个关键字映射到同一个槽），并且该槽已经被占用，这时就将新的关键字存储到公共溢出区域。

插入元素：插入元素时，首先通过哈希函数找到对应的槽，若该槽未被占用，则直接插入；若该槽已被占用，则将元素插入到公共溢出区域。

当我们了解了常用的哈希冲突的解决方式之后，我们就来详细的展开说明 Go 的 map 是怎么解决哈希冲突的：

Go 解决哈希冲突的方式是主要是通过链地址法来解决然后加上公共溢出区域法来实现的，具体实现看下图：

计算键的哈希值：首先，通过哈希函数计算要存储或获取值的键的哈希值。

确定初始存储位置：使用哈希值确定键值对在哈希表中的初始存储位置。

解决冲突：当发生哈希冲突时（即多个关键字映射到同一个槽）,首先会使用链地址法解决冲突，如果超过了8个冲突，就会放置新的 key 到溢出区域

插入元素：插入元素时，首先通过哈希函数找到对应的槽，若该槽和链表未足够，则直接插入；若位置不足，则将元素插入到公共溢出区域。

3.5 map 的动态扩容

3.5.1. 负载因子（Load Factor）

在 Go 的 map 实现中，负载因子是一个关键概念。负载因子定义为当前存储的键值对数量与桶的总数之比。当负载因子超过某个阈值时，即 map 的装载因子超过一定比例，就会触发动态扩容操作。

3.5.2. 触发条件

Go 语言中 map 的动态扩容操作会在以下情况触发：

当插入键值对后，map 的负载因子超过阈值（通常为 6.5）时，会触发动态扩容。

3.5.3. 动态扩容过程

Go 的 map 在动态扩容时，会进行以下操作：

分配新的桶数组：首先，会分配一个新的更大的桶数组，通常是当前桶数组大小的两倍。

重新哈希：将所有键值对重新哈希到新的桶数组中。这个过程涉及计算新的哈希值，确定新的桶位置，并将键值对移动到新的桶中。

数据迁移：在数据迁移的过程中，Go 会逐步将键值对从旧桶数组移到新桶数组中，确保数据的完整性和正确性。这是一个渐进性的过程，不会一次性移动所有的键值对。

更新指针：将 map 中的指针指向新的桶数组，同时释放旧的桶数组的资源。

3.6. 总结

以上就是 Go map 的所有相关底层原理，主要包含了以下内容:

Go map 的基本组成

Go map 操作的基本原理

Go map 是怎么解决 hash 冲突的

Go map 动态扩容的原理

4. Map 是并发安全的吗

首先, 我们在这里直接给出答案。原生的 Go map 是并发不安全的。我们可以使用以下程序来验证：

运行上面的代码会直接报错 fatal error: concurrent map writes 这错误主要就是因为并发的写 map 导致，那怎么解决这个问题呢，有如下两个方式：

4.1. sync.Map

4.2. 构造 struct map

以上就是并发下使用 map 姿势，这里还是比较建议使用官方封装的 sync.Map。

这篇文章的分享就到这里，希望能这篇文章对大家有一些帮助，更好的理解 Go 底层原理能让我们能写出更优秀的代码，加油，干饭人🍚