“我正在参加「掘金·启航计划」”

Map

Map 是一种用于存储键值对的数据结构，通常被称为映射或字典。最大的特点是只需要 O(1) 级别的时间复杂度就能查询出对应键存储的数据。它为什么这么快速呢？

Map 的基石

因为其具有极快的访问速度，所以它的底层通常会使用到数组来实现。而在 Go 语言中的 Map 是使用拉链法实现的哈希表。那么什么是哈希表呢？简单来说，哈希表由哈希函数、数组和链表组成。为了实现快速访问，使用数组表示哈希桶；为了解决哈希冲突，使用链表将冲突的键串联起来。通常将这个数组称为桶数组，将数组的每一个槽位称为桶。

不过，在 Go 语言中，Map 的实现略有所不同，它底层桶数组的每一个槽位，也是由几个数组构成的。所以不是用链表将具体的一个键值对串连起来，而是将一个个桶串连起来。不理解没关系，往下面看：

如上图所示，常见的 Map，当出现哈希冲突后，是将每一个键值对用链表或者其它数据结构将其串连起来。但是在 Go 中的 Map，是将一个桶串连起来。若你对哈希表有一个初步的认识后，我们来看看 Go 是如何表示 Map 的。

Map 的底层结构主要用 hmap结构体表示哈希表，其中最重要的字段是指向存储数据的桶数组的指针（buckets），而桶数组由 bmap 结构体构成的一个数组。bmap 结构体主要包含三个固定大小的数组和一个溢出桶指针。

当你了解了 Map 的基本构造，来看看如何操作 Map。

如何操作 Map

先初始化一个 Hmap

可以使用字面量和 make 两种方式初始化 Map。但是使用字面量也会被转换成使用 make 的方式。首先会根据元素数量创建哈希表，并进行相应的赋值操作。当元素数量小于等于 25，会逐个赋值给 hmap；否则，会将键和值分别放入两个切片中，然后进行遍历赋值。

元素数量小于等于 25 时

	m := map[string]int{

		"1": 1,

		"2": 2,

		"3": 3,

		"4": 4,

	}

// 上面使用字面量创建 map 时，元素数量 <= 25 了
//	会挨个添加键值

	m := make(map[string]int, 4)
	m["1"] = 1
	m["2"] = 2
	m["3"] = 3
	m["4"] = 4

元素数量大于 25 时

	m := map[string]int{

		"1": 1,

		"2": 2,

		"3": 3,

		"4": 4,

    	...
    	"26": 26,
	}

// 上面使用字面量创建 map 时，元素数量 > 25 了
//	会通过循环添加键值

	m := make(map[string]int, 4)
	vstatk := []string{"1", "2", "4", ..., "26"}
	vstatv := []int{1, 2, 3, ..., 26}

	for i := 0; i < len(vstatk); i++ {
		m[vstatk[i]] = vstatv[i]
	}

所以其实都是使用 make 函数来创建 map，当使用 make 关键字时，会转化为调用与 Map 相关的初始化方法，主要是构建 hmap 结构体。这个过程会生成一个哈希种子用于计算键的哈希值；根据元素数量推算出桶的数量并赋值给 B 字段，桶数组容量等于 2 的 B 次方；然后根据 B 的数值分配桶数组的空间，若 B < 4，则无需创建溢出桶；否则，会额外创建一些溢出桶，这些溢出桶的地址与正常桶连续，只是有额外的指针指向它们。

比如这里有两个 Map，一个有溢出桶，另一个没有：

在这个过程中，我在 hmap 结构体中，引入了 hash0 和 B 字段，因为一会获取操作会用到它们。再来看看 Map 的结构：

将桶的数量设置为二的幂次方，能够使用位运算优化取模运算，快速的求解出 key 的桶号。如果你不知道为什么要将桶的数量设置为 2^B 次方，可以看这一篇文章，开篇就解释了这个问题。常见类型的 HashCode 都是如何计算的啊。

这样简要介绍了初始化过程，先来看看查找操作，因为在添加和删除之前也需要进行元素的查找。所以查找元素是 Map 的关键操作。

获取元素是关键

计算桶号

想要获取对应 key 的值，首先需要得到桶号。根据哈希函数和哈希种子计算键的哈希值，然后通过取模操作得到桶数组的索引。这个过程还可以使用位运算的方式，将哈希值与(2^B - 1) 进行按位与操作，快速获取索引。

在 Go 中，获取桶号设计得非常巧妙：获取到 key 的哈希值后，直接取哈希值的低 B 位，其对应的十进制就是桶号。来看图：

上图想要查询 ciusyan 这个 key 对应的桶号，先根据哈希函数和哈希种子计算出它的哈希值，上面是使用二进制表示的。因为 B = 3，那么直接取哈希值的低 3 位 101，其对应的十进制是 5，那么 ciusyan 这个 key 对应的桶号就是 5。

真的很巧妙吧！但你可能有些疑惑，也没看到上面使用到取模运算，更别提到优化了，得到的桶号真的正确吗？首先来验证一下是否正确，将 ciusyan 的哈希值转换成十进制后是 23637，桶数组的长度为2^3 = 8，将其哈希值取模于数组长度：23637 % 8 = 5，可以看到计算出来的桶号也是 5。验证了正确性后，我们再来探讨为什么这么巧妙。

其实上面计算桶号的方法，本质上还是：哈希值 % 桶数组长度。又因为桶数组长度一定是 2^B，那么我们就可以将计算桶号的方法优化为：哈希值 & (2^B – 1)。带入我们这里的场景：

2^B - 1 的二进制表示只有低 B 位是 1，其余的全是 0，那么再与哈希值进行按位与操作，结果当然就等于哈希值的低 B 位了。相信你现在应该明白了，为什么能这么巧妙了吧~ 而且这样的设计，在对 Map 进行扩容的时候，会更巧妙。我们先来继续看看如何查找元素。

当桶数组长度为 2^B 时，为什么有这样的关系？桶号 = 哈希值 & (2^B – 1)

详细请见：常见类型的 HashCode 都是如何计算的啊

从桶中获取元素

通过上面的巧妙操作，我们已经获取到了键对应的桶号了，那么该如何获取具体的值呢？为了快速遍历桶数组中存放的元素，首先会提取哈希值的高八位（tophash），然后遍历桶中的 TopHashs 数组，找到相同的高八位后，还需要比较该索引位置的键是否与查找的键相等。 如果相等，则返回对应索引位置的值；如果不相等，则继续遍历高八位数组。当正常桶中的高八位都遍历完后，查看此桶是否有挂载溢出桶，如果有，则重复上述操作，直到遍历完与该桶相关的高八位数组。如果没有找到对应的键，则返回对应类型的零值。当然，在扩容状态下，可能需要在旧桶中查找数据。

用一幅图片表达上述文字的描述：

当了解了获取元素的操作后，添加删除的操作就比较简单了。首先也是需要根据键去查找对应值的位置，然后再继续相应的覆盖、添加、删除的操作。但由于 Map 的扩容方案。还是有很多注意的地方，那么我们先来看看它的扩容策略。

从插入元素的角度来说扩容

刚学会了如何获取元素，再来看插入元素的操作。首先会判断 Map 是否需要扩容。如果不需要扩容，会查找对应的键。如果之前存在该键，则直接覆盖对应的值并返回；如果不存在对应的键，则将该键放入对应索引位置的桶中。如果正常桶已满，则放入链接的溢出桶中，如果没有可用的溢出桶，则新建一个溢出桶并挂载到该桶的后面。此时，新生成的溢出桶的内存就不会与正常桶放在一起了。这是在不需要扩容时的添加操作，那如果满足扩容条件呢？

有两种时机会触发扩容操作。第一种扩容时机是当 装载因子 大于 6.5 时，说明元素数量太多，而桶的数量太少，查找一个键可能会花费很长时间。因此，扩容的思路是增加桶的数量，将 B 加 1，那么新桶的数量就是 2^(B+1)，也就是将桶的数量翻倍。然后，将两倍大小的桶数组以及一些溢出桶准备好，将 Buckets 桶数组的指针指向新数组，将 oldBuckets 指针指向旧数组，并且将 Map 调整为扩容状态，扩容完成。

装载因子 = 元素数量 / 桶的数量

现在又在 hmap 中扩充了 oldBuckets 和 flags 字段，来看看现在的结构：

再来看看翻倍扩容后的 map：

类似上图这样，申请了两倍容量的桶，然后修改引用和状态，扩容就完成了。因为 Go 的 Map采用的是渐进式扩容的方案。处于扩容状态时，对于写入数据的操作，才会将对应旧桶中的数据驱逐到新桶中，而且每一次只迁移有限数量的桶。当旧桶中的数据都被驱逐完成时，才会释放 oldBuckets 指向的旧桶空间。

我们可以发现，这样做需要维护额外的状态和额外的空间。这样做有什么好处呢？因为这样做能够减少一次性扩容消耗的时间，本质上是将扩容的操作均摊到其他的操作上了，提升了整体的性能，所以其实也是利用了空间换时间的思想。

在这种翻倍扩容的情况下，根据我们查找桶号的方法，当将 B 扩充一位后，会尽可能的将所有键值对分散的放到 2 个桶中。因为扩充的那一位，要么是 0，要么是 1。

再来看另一种扩容的方式。第二种扩容时机是当使用了过多的溢出桶时，说明删除操作过多，导致很多元素都分散到溢出桶中，可能会有内存泄露的风险。这时，采用的扩容思路是等量扩容，申请一个和原桶数组大小相同的新 buckets 数组，然后将 oldBuckets 指针指向旧数组，将 Buckets 指针指向新数组。所以与其说这样是在扩容，还不如说这是在整理元素。

但不论是哪种扩容方案，Map 都采用渐进式扩容，即当写操作访问旧桶时，将对应桶中和挂载在上面的溢出桶的元素驱逐到新的桶数组中。等量扩容时，目标桶索引不变，翻倍扩容时，会尽量均匀地将元素分布到两个桶中。在扩容期间，读操作会优先访问旧的桶数组。

最后画一幅图总结扩容的过程：

删除

以上介绍了扩容时的操作。最后还是来提一下 Map 是如何删除元素的吧。当调用 delete 关键字删除 Map 中的元素时，会调用 Map 相关的删除方法。首先会检查当前 Map 是否处于扩容状态，如果是，则根据键进行分流操作。然后在新桶中找到对应的键，并将其删除。如果找不到对应的键，则不执行删除操作。

总结

通过对 Map 基本原理的了解，可以简单总结：

Go 中的 Map 是使用拉链法实现的哈希表。
Map 对应 hmap 结构体，每个桶对应 bmap 结构体。每个 bmap 结构体包含三个大小固定为 8 的数组，以及用于挂载溢出桶的指针。
核心操作是查找，首先生成键的哈希值。
- 如果 Map 处于扩容状态，使用旧桶计算索引，在旧桶中查找；找不到时，利用新桶数组计算索引，在新桶中查找。
- 如果不处于扩容状态，直接利用桶数组计算索引，在桶数组中查找元素。
在添加元素之前，需要判断是否需要扩容。当装载因子大于 6.5 时，需要执行翻倍扩容；当溢出桶数量过多时，只需等量扩容整理。
需要扩容时，采用渐进式驱逐的方式。然后将元素放入适当的位置。
删除元素与查找元素非常相似，只是当找到对应键时，将相关信息删除而不是返回。