在Golang中，map的底層實(shí)現(xiàn)是一個(gè)散列表。實(shí)現(xiàn)map的過程實(shí)際上就是實(shí)現(xiàn)散列表的過程。在這個(gè)散列表中，主要涉及到兩個(gè)結(jié)構(gòu)體：一個(gè)是hmap（Go map的頭部），另一個(gè)是bmap（Go map的桶，通常稱為bucket）。這兩個(gè)結(jié)構(gòu)體的定義如下：

hmap結(jié)構(gòu)

hmap結(jié)構(gòu)體包含多個(gè)字段，但為了理解map的架構(gòu)，最重要的字段是標(biāo)紅的buckets數(shù)組。Golang的map中用于存儲的結(jié)構(gòu)是bucket數(shù)組。
hmap結(jié)構(gòu)圖:

+------------------+
| hmap             |
|------------------|
| count            |
| flags            |
| hash0            |
| buckets          |--------------------+
| oldbuckets       |                    |
| nevacuate        |                    |
| extra            |                    |
+------------------+                    |
                                        v
                                +--------------------+
                                |    buckets數(shù)組     |
                                +--------------------+

bucket結(jié)構(gòu)

相比于hmap，bucket的結(jié)構(gòu)更簡單。標(biāo)紅的字段依然是核心：我們使用的map中的key和value就存儲在這里。高位哈希值數(shù)組記錄的是當(dāng)前bucket中key相關(guān)的索引，稍后會詳細(xì)敘述。還有一個(gè)字段是一個(gè)指向擴(kuò)容后bucket的指針，使得bucket形成一個(gè)鏈表結(jié)構(gòu)。

bucket結(jié)構(gòu)圖:
+--------------------+
|       bucket       |
|--------------------|
| tophash [8]uint8   |
| keys    [8]keyType |
| values  [8]valType |
| overflow *bucket   |----+
+--------------------+    |
                          v
                +--------------------+
                |    overflow bucket |
                +--------------------+

hmap和bucket的關(guān)系

hmap包含一個(gè)指向bucket數(shù)組的指針，bucket數(shù)組存儲實(shí)際的數(shù)據(jù)。當(dāng)bucket需要擴(kuò)容時(shí)，通過指針鏈表的形式指向下一個(gè)bucket。整體的結(jié)構(gòu)如下圖所示：
hmap中的buckets指向bucket數(shù)組，bucket之間通過overflow指針形成鏈表。

hmap和bucket的關(guān)系:
+------------------+        +--------------------+
|     hmap         |        |    buckets數(shù)組     |
|------------------|        +--------------------+
|   buckets  ------|------> | bucket 0           |
|   ...            |        | tophash [8]uint8   |
+------------------+        | keys    [8]keyType |
                            | values  [8]valType |
                            | overflow *bucket   |----+
                            +--------------------+    |
                                                      v
                                                +--------------------+
                                                | overflow bucket 0  |
                                                +--------------------+

哈希表的特點(diǎn)

哈希表的特點(diǎn)是通過哈希函數(shù)對傳入的key進(jìn)行哈希運(yùn)算，得到唯一的值，通常是一個(gè)數(shù)值。Golang的map中也有這么一個(gè)哈希函數(shù)，它計(jì)算出唯一的值，并對其進(jìn)行高位和低位的分割。

低位用于尋找當(dāng)前key屬于hmap中的哪個(gè)bucket，而高位用于尋找bucket中的哪個(gè)key。bucket中的高位哈希值數(shù)組存儲了高位值，用于聲明當(dāng)前bucket中有哪些key，便于搜索查找。
哈希函數(shù)的高位和低位
哈希函數(shù)將key分為高位和低位，低位用于定位bucket，高位用于在bucket中定位具體的key。

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

map中的key/value存儲

需要特別指出的是，map中的key和value值存儲在同一個(gè)數(shù)組中，順序是key0、key1、key2...value0、value1、value2...的形式。這種存儲方式的好處是，在key和value長度不同時(shí)，可以消除padding帶來的空間浪費(fèi)。

Go語言map的結(jié)構(gòu)圖

結(jié)合以上描述，可以得到Go語言map的完整結(jié)構(gòu)圖：
map的key和value存儲
map中的key和value存儲在同一個(gè)數(shù)組中，順序如下圖所示：

key/value存儲順序圖:
+--------+--------+--------+--------+--------+--------+
| key0   | key1   | key2   | val0   | val1   | val2   |
+--------+--------+--------+--------+--------+--------+

map的擴(kuò)容

當(dāng)哈希表增長時(shí)，Go語言會將bucket數(shù)組的數(shù)量擴(kuò)充一倍，產(chǎn)生一個(gè)新的bucket數(shù)組，并將舊數(shù)組的數(shù)據(jù)遷移至新數(shù)組。

加載因子
擴(kuò)容的條件是哈希表的加載因子（load factor）。加載因子是一個(gè)閾值，一般表示為：散列包含的元素?cái)?shù)除以位置總數(shù)。它在“沖突機(jī)會”和“空間利用”之間做了平衡。加載因子越小，空間空置率高，利用率低；加載因子越大，空間利用率高，但沖突機(jī)會也高。

Golang的map的加載因子公式是：map長度 / 2^B，其中B表示已擴(kuò)容的次數(shù)。閾值是6.5。當(dāng)map長度超過加載因子閾值時(shí)，Go語言會產(chǎn)生一個(gè)新的bucket數(shù)組，并將舊bucket數(shù)組移至oldbucket字段中。注意，這并不是立即遷移舊數(shù)組中的所有元素，而是在訪問具體bucket時(shí)才會遷移對應(yīng)的數(shù)據(jù)。

擴(kuò)容時(shí)的map結(jié)構(gòu)如下圖所示：

藍(lán)色部分代表存有數(shù)據(jù)的bucket，橘黃色部分代表空的bucket。訪問舊bucket數(shù)據(jù)時(shí)，舊數(shù)據(jù)才會遷移至新bucket，如下圖：
當(dāng)map需要擴(kuò)容時(shí)，舊的bucket數(shù)據(jù)遷移到新的bucket數(shù)組中，但不是立即完成，而是逐步遷移。

復(fù)制代碼
擴(kuò)容前:
+------------------+
|     hmap         |
|------------------|
|   buckets        |-----> +--------------------+
|   oldbuckets     |      | bucket 0           |
|   ...            |      +--------------------+
+------------------+

擴(kuò)容后:
+------------------+                      +--------------------+
|     hmap         |                      |    新buckets數(shù)組   |
|------------------|                      +--------------------+
|   buckets        |-----> +--------------------+  新bucket 0  |
|   oldbuckets     |-----> | 舊buckets數(shù)組     |---->          |
|   ...            |      +--------------------+               |
+------------------+                                           v
                                                         +--------------------+
                                                         | 舊bucket 0        |
                                                         +--------------------+

數(shù)據(jù)訪問遷移
在訪問數(shù)據(jù)時(shí)，舊數(shù)據(jù)才會被遷移到新的bucket。

訪問時(shí)的數(shù)據(jù)遷移:

+------------------+                      +--------------------+
|     hmap         |                      |    新buckets數(shù)組   |
|------------------|                      +--------------------+
|   buckets        |-----> +--------------------+  新bucket 0  |
|   oldbuckets     |-----> | 舊buckets數(shù)組     |---->          |
|   ...            |      +--------------------+               |
+------------------+                                           v
                                                         +--------------------+
                                                         | 舊bucket 0        |
                                                         +--------------------+
                                                         數(shù)據(jù)訪問時(shí)遷移數(shù)據(jù)

map中數(shù)據(jù)的刪除

理解map的整體結(jié)構(gòu)后，查找、更新、刪除的步驟就顯而易見了。找到了map中的數(shù)據(jù)后，對key和value分別做如下操作：

在刪除數(shù)據(jù)時(shí)，需要將key和value分別處理：

數(shù)據(jù)刪除步驟:
1. 如果key是指針類型，將其置為空，等待GC。
2. 如果key是值類型，清除相關(guān)內(nèi)存。
3. 對value進(jìn)行同樣的處理。
4. 將高位哈希值數(shù)組對應(yīng)的索引置為空。

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