在Golang中，map的底层实现是一个散列表。实现map的过程实际上就是实现散列表的过程。在这个散列表中，主要涉及到两个结构体：一个是hmap（Go map的头部），另一个是bmap（Go map的桶，通常称为bucket）。这两个结构体的定义如下：

hmap结构

hmap结构体包含多个字段，但为了理解map的架构，最重要的字段是标红的buckets数组。Golang的map中用于存储的结构是bucket数组。
hmap结构图:

+------------------+
| hmap             |
|------------------|
| count            |
| flags            |
| hash0            |
| buckets          |--------------------+
| oldbuckets       |                    |
| nevacuate        |                    |
| extra            |                    |
+------------------+                    |
                                        v
                                +--------------------+
                                |    buckets数组     |
                                +--------------------+

bucket结构

相比于hmap，bucket的结构更简单。标红的字段依然是核心：我们使用的map中的key和value就存储在这里。高位哈希值数组记录的是当前bucket中key相关的索引，稍后会详细叙述。还有一个字段是一个指向扩容后bucket的指针，使得bucket形成一个链表结构。

bucket结构图:
+--------------------+
|       bucket       |
|--------------------|
| tophash [8]uint8   |
| keys    [8]keyType |
| values  [8]valType |
| overflow *bucket   |----+
+--------------------+    |
                          v
                +--------------------+
                |    overflow bucket |
                +--------------------+

hmap和bucket的关系

hmap包含一个指向bucket数组的指针，bucket数组存储实际的数据。当bucket需要扩容时，通过指针链表的形式指向下一个bucket。整体的结构如下图所示：
hmap中的buckets指向bucket数组，bucket之间通过overflow指针形成链表。

hmap和bucket的关系:
+------------------+        +--------------------+
|     hmap         |        |    buckets数组     |
|------------------|        +--------------------+
|   buckets  ------|------> | bucket 0           |
|   ...            |        | tophash [8]uint8   |
+------------------+        | keys    [8]keyType |
                            | values  [8]valType |
                            | overflow *bucket   |----+
                            +--------------------+    |
                                                      v
                                                +--------------------+
                                                | overflow bucket 0  |
                                                +--------------------+

哈希表的特点

哈希表的特点是通过哈希函数对传入的key进行哈希运算，得到唯一的值，通常是一个数值。Golang的map中也有这么一个哈希函数，它计算出唯一的值，并对其进行高位和低位的分割。

低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key。bucket中的高位哈希值数组存储了高位值，用于声明当前bucket中有哪些key，便于搜索查找。
哈希函数的高位和低位
哈希函数将key分为高位和低位，低位用于定位bucket，高位用于在bucket中定位具体的key。

哈希值分解图:
+----------------------------------------+
|                hash value              |
+----------------------------------------+
|  high bits  |           low bits       |
+----------------------------------------+
|  用于定位bucket中的key  |  用于定位bucket  |
+----------------------------------------+

map中的key/value存储

需要特别指出的是，map中的key和value值存储在同一个数组中，顺序是key0、key1、key2...value0、value1、value2...的形式。这种存储方式的好处是，在key和value长度不同时，可以消除padding带来的空间浪费。

Go语言map的结构图

结合以上描述，可以得到Go语言map的完整结构图：
map的key和value存储
map中的key和value存储在同一个数组中，顺序如下图所示：

key/value存储顺序图:
+--------+--------+--------+--------+--------+--------+
| key0   | key1   | key2   | val0   | val1   | val2   |
+--------+--------+--------+--------+--------+--------+

map的扩容

当哈希表增长时，Go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将旧数组的数据迁移至新数组。

加载因子
扩容的条件是哈希表的加载因子（load factor）。加载因子是一个阈值，一般表示为：散列包含的元素数除以位置总数。它在“冲突机会”和“空间利用”之间做了平衡。加载因子越小，空间空置率高，利用率低；加载因子越大，空间利用率高，但冲突机会也高。

Golang的map的加载因子公式是：map长度 / 2^B，其中B表示已扩容的次数。阈值是6.5。当map长度超过加载因子阈值时，Go语言会产生一个新的bucket数组，并将旧bucket数组移至oldbucket字段中。注意，这并不是立即迁移旧数组中的所有元素，而是在访问具体bucket时才会迁移对应的数据。

扩容时的map结构如下图所示：

蓝色部分代表存有数据的bucket，橘黄色部分代表空的bucket。访问旧bucket数据时，旧数据才会迁移至新bucket，如下图：
当map需要扩容时，旧的bucket数据迁移到新的bucket数组中，但不是立即完成，而是逐步迁移。

复制代码
扩容前:
+------------------+
|     hmap         |
|------------------|
|   buckets        |-----> +--------------------+
|   oldbuckets     |      | bucket 0           |
|   ...            |      +--------------------+
+------------------+

扩容后:
+------------------+                      +--------------------+
|     hmap         |                      |    新buckets数组   |
|------------------|                      +--------------------+
|   buckets        |-----> +--------------------+  新bucket 0  |
|   oldbuckets     |-----> | 旧buckets数组     |---->          |
|   ...            |      +--------------------+               |
+------------------+                                           v
                                                         +--------------------+
                                                         | 旧bucket 0        |
                                                         +--------------------+

数据访问迁移
在访问数据时，旧数据才会被迁移到新的bucket。

访问时的数据迁移:

+------------------+                      +--------------------+
|     hmap         |                      |    新buckets数组   |
|------------------|                      +--------------------+
|   buckets        |-----> +--------------------+  新bucket 0  |
|   oldbuckets     |-----> | 旧buckets数组     |---->          |
|   ...            |      +--------------------+               |
+------------------+                                           v
                                                         +--------------------+
                                                         | 旧bucket 0        |
                                                         +--------------------+
                                                         数据访问时迁移数据

map中数据的删除

理解map的整体结构后，查找、更新、删除的步骤就显而易见了。找到了map中的数据后，对key和value分别做如下操作：

在删除数据时，需要将key和value分别处理：

数据删除步骤:
1. 如果key是指针类型，将其置为空，等待GC。
2. 如果key是值类型，清除相关内存。
3. 对value进行同样的处理。
4. 将高位哈希值数组对应的索引置为空。

+------------------+
|    bucket        |
|------------------|
| keys    [8]keyType|----> [ key0, key1, ... ]
| values  [8]valType|----> [ val0, val1, ... ]
| tophash [8]uint8 |----> [ 0, 1, ... ]
| overflow *bucket |----> 其他bucket
+------------------+