一、引言

如果你刚开始接触 Go 语言，可能会对如何在 Go 中使用映射（map）感到有些困惑。即使经验丰富，理解映射的实际工作方式也颇具难度。

例如：

或者在映射上使用for-range循环时的顺序问题等。

在我们继续之前，先提醒一下——这里的信息基于 Go 1.23。如果情况发生了变化，并且这个内容不是最新的，请私信我。

二、Go 语言中的映射：快速入门

1.基本概念

Go 中的映射是一种内置类型，用作键值存储。与数组中递增的索引作为键不同，映射的键可以是任何可比较的类型，这提供了更多灵活性。

2.创建方式

• 使用make()?创建空映射，并后续赋值。

• 通过映射字面量在创建时直接设置键值对。

3.删除操作

若想删除某个键值对，可使用delete?函数：delete(m, "a")?。

4.零值与特殊情况

映射的零值是nil?，类似于空映射。搜索不存在的键时，会返回值类型的“零值”。但不能向nil?映射添加新键值对。

对于nil?映射的遍历，不会出错，只是不做任何操作。

5.其他特性

• ?for-range??循环返回键无特定顺序。
• 映射不是线程安全的。
• 可通过ok??检查键是否在映射中：_, ok := m[key]??。

6.关于映射键

• 可比较类型：能使用==??比较同一类型的两个值的类型被认为是可比较的。但某些类型，如切片、函数或包含切片或映射的结构体等不可作为映射键。
• 接口：接口可以是可比较的，也可以是不可比较的。使用空接口作为键需谨慎，可能导致运行时错误。

而运行时错误“hash of unhashable type []int”揭示了 Go 在幕后处理映射的线索。

三、映射（Map）剖析

1.映射的基本结构

在 Go 代码中，单个映射是抽象概念，隐藏了数据组织的复杂细节，它由称为“桶（buckets）”的单元组成。

一个映射包含指向桶数组的指针，这使得映射赋值或传递时，相关变量和函数参数共享同一指针。

2.映射的传递与修改

需注意，映射底层虽指向hmap?的指针，但不是引用类型。改变整个映射，不会反映在原始映射上。

在 Go 中，一切都是按值传递的。实际发生的情况有点不同：当你将映射m1?传递给changeMap?函数时，Go 会复制 *hmap?结构。所以，main()?中的m1?和changeMap()?函数中的m2?在技术上是指向同一个hmap?的不同指针。

3.桶的特性

每个桶最多容纳 8 个键值对。

上面的映射有 2 个桶，并且len(map)?是 6。

4.简单赋值场景

让我们看下面图像中的简单赋值场景，当有一个空映射并向其分配一个键值对"hello": 1?。

它首先将“hello”哈希为一个数字，然后对桶的数量取模。由于这里只有一个桶，任何数字对 1 取模都是 0，所以直接放入桶 0 中。添加另一个键值对时，同样过程发生，若桶 0 已满或键不同，则移至下一个槽。

5.哈希与循环中的键顺序

当你向映射中添加一个键值对时，Go 不会只是随机或顺序地将其放入其中。相反，它会根据键的哈希值将该键值对放入这些桶中的一个，哈希值是由hash(key, seed)?确定的。看一下hash(key, seed)?，当在具有相同键的两个映射上使用for-range?循环时，键可能以不同顺序出现。

虽然 Go 中用于映射的哈希函数对于具有相同键类型的所有映射一致，但每个映射实例使用的“种子（seed）”不同。创建新映射时，Go 会为其生成随机种子。在上述例子中，a?和b?的键都是string?类型，都使用相同哈希函数，但各自有唯一种子。

6.桶的增长

当桶开始变满或几乎满（取决于算法定义）时，映射会触发增长，可能使主桶数量加倍。

引入“溢出桶（overflow buckets）”概念，在高冲突情况下发挥作用。想象有 4 个桶，其中一个因高冲突已满 8 个键值对，其他 3 个为空。

真的需要因添加一个不巧落入已满桶的条目而将映射增长到 8 个桶吗？答案是，不需要！

Go 通过创建与第一个桶链接的“溢出桶”来更有效地处理这种情况。新的键值对存储在这个溢出桶中，而不是强制进行全面增长。

当满足两个条件之一时，Go 中的映射会增长：要么有太多溢出桶，要么映射过载，这意味着负载因子太高。

由于这两个条件，也有两种增长方式：

• 一种是将桶的大小加倍（当过载时）。
• 一种是保持相同大小但重新分配条目（当有太多溢出桶时）。

如果有太多溢出桶，重新分配条目比仅仅添加更多内存更好。

目前，Go 的负载因子设置为 6.5，意味着映射设计为每个桶平均保持 6.5 个条目，约 80%容量。超过此阈值，映射被认为过载，将通过分配新桶数组（大小为当前两倍）来增长，然后重新哈希元素到新桶中。

即使桶几乎满了也增长映射，原因在于性能。通常认为在映射中访问和赋值是 O(1)，但并非总是如此。

桶中被占用的槽越多，速度越慢。添加新键值对时，不仅检查桶是否有空间，还需比较键与现有键，决定添加新条目还是更新现有条目。有溢出桶时更糟，需检查每个溢出桶的槽，影响访问和删除操作。

但 Go 团队进行了优化，哈希“Hello”得到的哈希值不会被丢弃，会将“Hello”的顶部哈希值作为uint8?缓存，与新键的顶部哈希值快速比较，使初始检查很快。

比较顶部哈希值后，若匹配，键可能相同，然后 Go 进行较慢过程检查键是否实际相同。

7.make(map, hint)?的提示

?make(map, hint)?中的hint?参数表示期望映射容纳的初始元素数量。此提示有助于添加元素时最小化映射增长次数。每次增长操作涉及分配新桶数组并复制现有元素，效率不高。以较大初始容量开始可避免昂贵的增长操作。

举例说明添加更多元素时桶的大小增长情况：

负载因子影响映射增长，不同提示范围对应不同的桶数量和容量。

在提示为 14 时，会有 4 个桶，这是负载因子在起作用，还记得负载因子阈值 6.5 吗？它直接影响映射何时增长。

在提示为 13 时，有 2 个桶，负载因子为 13/2 = 6.5，达到阈值但未超。增加到 14 时，负载因子超过 6.5，触发增长。

对于提示为 26 同理，有 4 个桶时，负载因子是 26/4 = 6.5，再次达到阈值。超过 26 时，映射需增长以容纳更多元素。

基本上，从第二个范围开始，提示范围与前一个相比加倍，桶的数量和容量也如此。

四、增长时的迁移

1.映射增长带来的问题

映射的增长回答了两个常见问题：

• “为什么你不能获取映射元素的地址？”
• “为什么在不同时间for-range??的顺序不保证？”

2.映射增长的过程

当映射增长时，会分配大小为旧数组两倍的新桶数组，旧桶中条目位置失效，需移至新桶。

?

若映射有大量键值对（如 1000 个），一次性移动所有键成本高昂，可能阻塞 goroutine 。为避免此情况，Go 采用“渐进式增长”，分散操作，使程序平稳运行。

此过程复杂，需维护映射完整性，同时管理新旧桶。

3.渐进式增长的触发条件

只有两种情况会触发渐进式增长：

• 向映射分配键值对。
• 从映射中删除键。

任何一种操作都会触发迁移过程，且至少有一个桶会移至新桶数组。

当进行m["Hello"] = 2?操作且映射正在增长时，会先迁移含“Hello”键的旧桶。?

旧桶元素移至新桶的规则：

例如从 4 桶增至 8 桶，旧“桶 1”元素移至新“桶 1”或新“桶 5”。

如果hash % 4 == 1?，这意味着hash % 8 == 1?或hash % 8 == 5?。因为对于一个旧桶，其中H % 4 == 1?，H?的最后两位是01?。当我们考虑新桶数组的最后三位时：

• 如果第三位（从右数）是 0，最后三位是 001，这意味着H % 8 == 1?。
• 如果第三位（从右数）是 1，最后三位是 010，这意味着H % 8 == 5?。

若旧桶有溢出桶，也会将其中元素移至新桶，全部移动后，通过“顶部哈希（tophash）”字段将旧桶标记为“已迁移”。

五、更多

掌握Golang精髓，释放编程潜能！关注我的《Golang实用技巧》专栏，它将为你揭秘生产环境最佳实践，带你探索高并发编程的实用教程。从分享实用的Golang小技巧到深入剖析实际应用场景，让你成为真正的Golang大师。无论你是初学者还是经验丰富的开发者，这里都有你所需要的灵感和知识。让我们一同探索Golang的无限可能！