什么是 Map

Map 是一种无序的键值对集合，类似于其他编程语言中的字典或哈希表。它允许通过键快速访问对应的值。Map 的键必须是唯一的，而值可以重复。Map 的键可以是任何类型，但通常使用字符串或整数作为键。Map 的值可以是任何类型，包括其他 Map、切片或结构体。

最主要的数据结构有两种：哈希表和搜索树（红黑树、AVL树等）。Go 语言的 Map 是基于哈希表实现的，使用链地址法解决冲突。哈希表的平均时间复杂度为 O(1)，最坏情况下为 O(n)，而搜索树的平均和最坏时间复杂度均为 O(log n)。

Map 的基本用法

Map 的基本用法包括创建、添加、删除和查询元素。下面是一些常见的操作示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var m map[string]int // 声明一个 map
m = make(map[string]int) // 创建一个 map

m["a"] = 1 // 添加元素
m["b"] = 2 // 添加元素
m["c"] = 3 // 添加元素

fmt.Println(m) // 输出 map[a:1 b:2 c:3]

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

for k, v := range m { // 遍历 map
    fmt.Println(k, v)
}

Map 的基本用法并不难，需要注意的是遍历 Map 时，遍历的顺序是随机的，因为 Map 是无序的，基本上每次遍历的结果都不一样。其原因跟其底层实现有关，后续会详细分析。如果需要保持顺序，可以使用切片来存储键，然后按照切片的顺序遍历 Map。

Map 的底层实现

首先来粗略看一下 Map 的结构体：

1
2
3
4
5
6
7
8
9
10
11
12
// src/runtime/map.go
type hmap struct {
    count     int // map 中的元素个数，调用 len() 函数时会返回这个值
    flags     uint8
    B         uint8 // buckets 数组长度的对数，buckets 的大小为 2^B
    noverflow uint16 // 溢出桶的数量
    hash0     uint32
    buckets   unsafe.Pointer // 指向哈希桶的指针，大小为 2^B。若元素个数为 0，则 buckets 为 nil
    oldbuckets unsafe.Pointer // 指向旧哈希桶的指针，扩容时使用
    nevacuate uintptr // 扩容的进度，小于此地址的桶已经完成迁移
    extra     *mapextra // 额外信息
}

其中 buckets 是一个指向哈希桶的指针：

1
2
3
type bmap struct {
	tophash [bucketCnt]uint8
}

但是在运行时，buckets 的具体结构会被编译器优化，因为哈希表中可能存储不同类型的键值对，所以键值对占据的内存空间大小只能在编译时进行推导。查了一些资料，其最后的结构体大致如下：

1
2
3
4
5
6
7
type bmap struct {
    topbits     [8]uint8 // 8 个字节的哈希值
    keys        [8]keytype
    values      [8]valuetype
    pad         uintptr
    overflow    *bmap
}

topbits 是根据 key 计算出来的哈希值的高 8 位。
keys 和 values 分别是存储键和值的数组。
overflow 是一个指向下一个桶的指针，用于处理哈希冲突。

也就是说一个 Map 中的所有桶，都是存在 hmap.buckets 这个指针指向的内存空间中。hmap.buckets 是一个类似数组的连续内存空间，每个单元存储一个 bmap 类型的链表头指针。

真正存放 key 和 value 的是 bmap 结构体中的 keys 和 values 数组。每个桶（bmap）中最多可以存放 8 个键值对，当超过 8 个时，就会发生哈希冲突，新的键值对会被存放到 overflow 指针指向的下一个桶中。

这里还有一个点值得注意，就是为了内存紧凑，bmap 结构体中的 keys 和 values 数组的大小是 8，并且是先存放 8 个 key，再存放 8 个 value。

创建 Map

语法层面的创建 Map 非常简单，但是在实际底层实现中，创建 Map 的过程是比较复杂的。并且只能通过汇编分析来得知，创建 Map 的需要初始化 hmap 结构体的各种字段，比如计算 B 的值、设置哈希种子 hash0、分配内存空间等。

需要特别注意的一点是创建函数 func makemap(t *maptype, hint int, h *hmap) *hmap 返回的数据类型是 *hmap，也就是说创建 Map 的过程是返回一个指向 hmap 结构体的指针。

这里要和 slice 的区别在于，创建切片时返回的是一个切片结构体，而不是指向切片结构体的指针。

那么这两个数据在作为函数参数时就会有不同的表现。对于 Map，传递的是指向 hmap 结构体的指针，因此在函数内部可以直接修改原始的 Map。而对于切片，传递的是切片结构体的值，函数内部修改切片的长度等结构体参数不会影响原始切片。

访问 Map

了解了基本的数据结构后，就可以分析 Map 的访问过程了。访问 Map 的过程主要分为以下几个步骤：

  1. 计算哈希值：根据键的类型和内容计算哈希值，使用 hash0 作为种子。
  2. 计算桶索引：根据哈希值的后 B 位计算桶索引。假设 B 的值为 3，那么桶索引的计算方式为 hash & (1 << B - 1)。
  3. 访问桶：根据桶索引访问 hmap.buckets 数组中的桶。然后在桶内根据哈希值的高 8 位找到对应的 Key 和 Value。
  4. 匹配完整 key：由于是根据哈希值的高 8 位快速定位的，所以需要匹配完整的 key，确保找到的是正确的键值对。
  5. 溢出桶查找：如果在当前桶内没有找到，则查找溢出桶，使用 overflow 指针按照之前的方式查找，直到找到对应的键值对或者溢出桶为空为止。
  6. 返回值：如果找到对应的键值对，则返回对应的值；如果没有找到，则返回 nil。

这里有一个比较重要的点，就是前面结构体例维护了一个 topbits 数组(tophash)，存储的是哈希值的高 8 位。相当于是一种缓存机制，先匹配前 8 位然后再对比完整的 key。

插入/修改

插入和修改的过程，首先也需要和访问一样，查找 key 在 Map 中的位置。如果没有找到，则在当前桶内插入新的键值对；如果找到了，则更新对应的值。可总结为以下几个步骤：

  1. 计算哈希值：根据键的类型和内容计算哈希值，使用 hash0 作为种子。
  2. 计算桶索引：根据哈希值的后 B 位计算桶索引。
  3. 访问桶：根据桶索引访问 hmap.buckets 数组中的桶。然后在桶内根据哈希值的高 8 位找到对应的 Key 和 Value。
  4. 哈希冲突：如果找到了哈希值一样但是 key 不一样的键值对，则需要处理哈希冲突。如果有空位置则插入新的键值对，如果没有则需要通过溢出桶来添加。
  5. 更新数据：如果找到了对应的 key，则更新对应的值。
  6. 如果没有找到对应的 key，那就找到合适的位置插入新的键值对。当然如果桶已经满了，那就表示发生了哈希冲突，需要扩容（创建溢出桶）。

当然如果是插入的话，要更新 Map 结构体的字段 count，表示 Map 中的元素个数增加了。

这里也可以看出了 Map 是线程不安全的，因为在插入和修改的过程中，如果有多个 goroutine 同时访问同一个 Map，可能导致数据不一致。
当然为了保证 Map 结构体中还有一个 flags 字段，用于标记 Map 的状态，是在读还是写操作，当出现并发读写操作时，依据这个字段会抛出 panic 错误。
为了保证线程安全，需要使用 sync.Mutex、sync.RWMutex 来进行加锁或者使用 sync.Map 来代替。

删除

删除的过程首先要完整地经过访问 Map 的过程，找到对应的 key 和 value。如果找到了对应的键值对，则将 tophash 位置设置为 emptyOne 或者 emptyRest，表示该位置已经被删除。同步置空对应位置的 key 和 value，并更新 Map 结构体的 count 字段。

emptyOne 和 emptyRest 是 Map 中的特殊值，表示该位置为空。emptyOne 表示该位置只有一个元素被删除，而 emptyRest 表示该位置及其后续位置（包括溢出桶）都为空。这样在查找的时候如果遇到 emptyRest，就可以直接跳过后续所有元素的查找。

这里要注意的是，删除操作并不会立即释放内存，而是将对应位置标记为空。这样可以避免频繁的内存分配和释放，提高性能。

扩容和迁移

Map 的扩容是一个比较复杂的过程，主要是为了提高性能和减少哈希冲突。扩容分为两种，一种是双倍扩容，另一种是等量扩容。

双倍扩容

双倍扩容依赖于负载因子，Map 的负载因子是指 Map 中元素个数与桶的数量的比值。负载因子过高会导致哈希冲突增多，影响性能。Go 语言中默认的负载因子为 6.5，即当 Map 中元素个数超过 buckets 数组长度的 6.5 倍时，就会触发扩容。元素个数就是结构体中的 count 字段，而桶的数量则是 2^B，其中 B 是 hmap 结构体中的字段。

因为一个桶能容纳的元素最多为 8 个，所以当负载因子超过 6.5 时，就相当于正常桶的填充率已经超过 65% 了，此时所有正常桶的数量就会乘以 2，也就是 B 的值加 1。扩容后，新的 buckets 数组的长度为原来的两倍。

而新桶的哈希值计算方式也会发生变化，因为 B 的值变了，所以新的桶索引计算方式为 hash & (1 << B - 1)。这就意味着，原来的哈希值需要重新计算，以适应新的桶索引。所以原来桶内的元素会根据新的计算方式重新分配到新的桶中。

等量扩容

双倍扩容是为了减少哈希冲突，提高性能，并且双倍扩容的负载因子计算和扩容数量都是基于正常桶的数量来计算的。而等量扩容则主要是为了针对溢出桶数量过多的情况，去提高查询效率。

想象先往一个 Map 中插入了多个元素，再删除多个元素，这时可能会出现负载因子没达到临界值，不会触发双倍扩容，但是溢出桶的数量过多且元素分配在同一个正常桶后的不同溢出桶的不同位置。这样查找的性能就是非常低的，因为需要遍历多个溢出桶。

此时如果将溢出桶的元素根据开放地址法重新分配到前面桶的空槽位上，就可以有效提高查询性能。也就是说等量扩容发生在溢出桶过多的情况，而溢出桶过多可以分为两种：

  1. 正常桶的数量小于 2^15，即 B 小于 15 时，如果溢出桶的数量（noverflow）大于等于正常桶的数量，则认为溢出桶过多。
  2. 正常桶的数量大于等于 2^15，即 B 大于等于 15 时，如果溢出桶的数量（noverflow）大于等于 2^15，则认为溢出桶过多。

扩容的时机

双倍扩容和等量扩容都是在操作 Map 时触发的（插入、修改或删除）。具体来说，当访问 Map 时，如果发现负载因子超过了临界值，就会触发双倍扩容；如果发现溢出桶过多，则会触发等量扩容。

但是需要注意的是，扩容是一个耗时的操作，会导致 Map 的访问性能下降。因此在实际实现中，并不是每次扩容完毕后（预）都是全量迁移的，而是采用写时复制的方式。也就是说，当访问到具体某个 bucket 时，才会逐渐将 oldbucket 和该正常桶后一个正常桶中的所有元素迁移到新的 buckets 中。这样可以避免在扩容时一次性迁移所有元素，提高性能。

总结常见问题

    1. Map 的底层数据结构是怎么样的？
    1. Map 的遍历为什么是无序的？
    1. 如何实现 Map 的有序遍历？
    1. Map 是线程安全吗？
    1. Map 的 key 为什么要是可比较的类型？（哈希冲突，tophash 比较之后还需要比较真实 key）
    1. Map 的扩容策略是什么？（双倍扩容和等量扩容）
    1. Map 如何解决哈希冲突？（链地址法和开放地址法）