引言

map 是一种内置的数据结构，也常被称为字典或哈希表。它使用键值对（key-value pairs）的方式存储数据，其中每个键都是唯一的，且每个键都映射到一个值。使用 map 可以快速地查找、添加和删除数据项。

本文总结了 map 的基础使用方式，探讨 map 的实现原理，并在最后总结 map 高效使用的原则和一些常见的问题。

map 的使用

在 Go 语言中，map 是一种内置的数据结构，也常被称为字典或哈希表。它使用键值对（key-value pairs）的方式存储数据，其中每个键都是唯一的，且每个键都映射到一个值。使用 map 可以快速地查找、添加和删除数据项。

创建和初始化

创建一个 map 可以使用 make 函数或者直接使用 map 字面量：

// 使用 make 函数创建 map
m1 := make(map[string]int)

// 使用字面量初始化 map
m2 := map[string]int{"foo": 1, "bar": 2}

添加和修改元素

向 map 中添加或修改元素的方式非常简单，只需要指定键和对应的值即可：

m := make(map[string]int)
m["a"] = 1  // 添加一个新的键值对
m["b"] = 2
m["a"] = 3  // 更新键 "a" 对应的值

访问元素

访问 map 中的元素也很直接，通过键来访问：

value := m["a"]  // 获取键 "a" 对应的值

如果访问的键不存在于 map 中，将返回该类型的零值。为了区分零值和不存在的情况，可以使用两个值来接收结果：

value, ok := m["c"]  // 如果 "c" 在 map 中，ok 为 true；否则为 false

删除元素

删除 map 中的元素可以使用内置的 delete 函数：

delete(m, "b")  // 删除键为 "b" 的元素

遍历 map

遍历 map 可以使用 for 循环和 range 关键字：

for key, value := range m {
    fmt.Println(key, value)
}

在对同一 map 做多次遍历时，遍历的顺序并不相同，Go 运行时在初始化 map 迭代器时对起始位置做了随机处理，因此不能依赖遍历 map 得到的元素顺序。

map 实现原理

Go运行时使用一张哈希表来实现抽象的map类型。运行时实现了map操作的所有功能，包括查找、插入、删除、遍历等。在编译阶段，Go编译器会将语法层面的 map 操作重写成运行时对应的函数调用。

初始状态

与语法层面 map 对应的是 runtime.hmap 类型的实例。可以将 hmap 理解为 map 类型的描述符，存储了后续所有操作所需的相关信息。

其中：

• count：当前map中的元素个数
• flags：当前map所处的状态标志，目前定义了4个状态值 ——iterator、oldIterator、hashWriting和 sameSizeGrow。
• B：B的值是bucket数量的以2为底的对数，即2^B = bucket 数量。
• noverflow：overflow bucket的大约数量。
• hash0：哈希函数的种子值。
• buckets：指向bucket数组的指针。
• oldbuckets：在map扩容阶段指向前一个bucket数组的指针。
• nevacuate：在map扩容阶段充当扩容进度计数器。所有下标小于nevacuate的bucket都已经完成了数据排空和迁移操作。
• extra：可选字段。如果有overflow bucket存在，且key、 value都因不包含指针而被内联（inline）的情况下，该字段将存储所有指向overflow bucket的指针，保证overflow bucket是始终可用的（不被垃圾回收掉）。

真正用于存储键值对数据的是 bucket（桶），每个 bucket 中存储的是 Hash 值低 bit 位数值相同的元素。

默认的元素个数为 BUCKETSIZE 值为8，当某个 bucket 的8个空槽（slot）都已填满且 map 尚未达到扩容条件时，运行时会建立 overflow bucket，并将该 overflow bucket 挂在上面 bucket 末尾的 overflow 指针上，这样两个 bucket 形成了一个链表结构，该结构的存在将持续到下一次 map 扩容。

每个 bucket 由三部分组成：tophash、key 和 value

tophash 区域

当向 map 插入或查询时，运行时会使用哈希函数对 key 做哈希运算获取 hashcode，运行时使用 hashcode 的低位区选定 bucket，使用高位区确定 key 的位置。

key 存储区域

tophash 区域下方是一块连续的内存区域，存储所有的 key 数据。运行时在分配 bucket 时会使用 map 类型的元信息确定 key 的类型和大小。

value 存储区域

key 存储区域下方是另一块连续的内存区域，该区域存储的是 key 对应的 value。Go 运行时采用了将 key 和 value 分开存储而不是采用 kv 紧邻方式存储，算法上更加复杂，但减少了因内存对齐带来的内存浪费。

map 扩容

当插入元素个数超出一定数值后，map 会自动扩容（扩充bucket的数量），并重新在bucket间均衡分配数据。

Go 运行时的 map 实现中引入了一个 LoadFactor（负载因子），当 LoadFactor < count / (2^B) 或 overflow bucket 过多时，运行时会对 map 进行扩容。

目前 LoadFactor 设置为 6.5（即每个桶最多存储 6 个键值对）。这个值是通过实验和优化得出的，旨在在内存使用和查找效率之间达到一个平衡。

如果是因为 overflow bucket 过多导致扩容，运行时会新建一个规模相同的 bucket 数组；如果是超过 LoadFactor，则会建立一个两倍于现有规模的 bucket 数组。真正的排空和迁移是在进行 assign 和 delete操作时逐步进行，直至原 bucket 数组中所有数据都迁移到新数组，原 bucket 数组才会被释放。

基于自动扩容原理，如果初始创建 map 时没有创建足够多可以应对 map 使用场景的 bucket，那么随着插入 map 元素数量的增多，map 会频繁扩容，而这一过程将降低 map 的访问性能。因此，最好对map使用规模做出粗略的估算，并使用 cap 参数对 map 实例进行初始化。

map 常见问题

Go map 如何处理哈希碰撞

Go 语言中的 map 类型处理哈希碰撞的机制是使用链地址法。这是一种常见的解决哈希碰撞的方法，其中每个桶（bucket）不仅存储一个键值对，而是可以链接多个键值对。这些键值对在发生哈希碰撞时会被存储在同一个桶里的一个链表中。

当尝试将一个键值对添加到 map 中时，Go 语言的哈希函数首先计算键的哈希值，然后使用这个哈希值来找到对应的桶。如果这个桶中已经有一个或多个键值对存在（即哈希值相同），新的键值对将被加入到这个桶的链表中。查找或删除键值对时，Go 将计算键的哈希值，访问对应的桶，然后在链表中遍历以找到匹配的键。

为了优化性能，Go 的 map 实现也可能在内部进行动态调整，比如在桶过载时进行扩容，这样可以分散并减少碰撞，从而优化访问速度。

Go map 删除一个 key 是否会立即释放

从 map 中删除键值对会从逻辑上移除该键值对，但不会缩小 map 的底层存储空间。

如何减少哈希碰撞

• 使用高质量的哈希函数
• 增加哈希表的大小
• 使用动态调整大小的哈希表

如何设计一个哈希函数

• 整数哈希：如果键是整数，可以使用模运算（取模一个大质数）、位运算技巧（如位移和异或）来设计哈希函数。
• 字符串哈希：对于字符串，常用的方法包括多项式累积（如对每个字符的ASCII值进行乘积和累加，通常与一个质数相结合），或使用更复杂的方法如 Fowler-Noll-Vo（FNV）或 MurmurHash。
• 复杂数据结构：对于对象或复合数据结构，可以组合其内部各字段的哈希值，例如使用每个字段的哈希值的线性组合，并确保组合方式能够减少重叠和碰撞。