Go語言是怎么設計Map的

由于本文篇幅較長，故將目錄整理如下

• 維基百科的定義

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

說明：在計算機科學中，包含鍵值對（key-value）集合的抽象數據結構（關聯(lián)數組、符號表或字典），其每個可能的鍵在該集合中最多出現一次，這樣的數據結構就是一種Map。

對Map的操作主要是增刪改查：

• 在集合中增加鍵值對

• 在集合中移除鍵值對

• 修改某個存在的鍵值對

• 根據特定的鍵尋找對應的值

  
  

Map的實現主要有兩種方式：哈希表（hash table）和搜索樹（search tree）。例如Java中的hashMap是基于哈希表實現，而C++中的Map是基于一種平衡搜索二叉樹——紅黑樹而實現的。以下是不同實現方式的時間復雜度對比。

可以看到，對于元素查找而言，二叉搜索樹的平均和最壞效率都是O(log n)，哈希表實現的平均效率是O(1)，但最壞情況下能達到O(n)，不過如果哈希表設計優(yōu)秀，最壞情況基本不會出現（所以，讀者不想知道Go是如何設計的Map嗎）。另外二叉搜索樹返回的key是有序的，而哈希表則是亂序。

哈希表

由于Go中map的基于哈希表（也被稱為散列表）實現，本文不探討搜索樹的map實現。以下是Go官方博客對map的說明。

One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.

學習哈希表首先要理解兩個概念：哈希函數和哈希沖突。

哈希函數（常被稱為散列函數）是可以用于將任意大小的數據映射到固定大小值的函數，常見的包括MD5、SHA系列等。

一個設計優(yōu)秀的哈希函數應該包含以下特性：

• 均勻性：一個好的哈希函數應該在其輸出范圍內盡可能均勻地映射，也就是說，應以大致相同的概率生成輸出范圍內的每個哈希值。

• 效率高：哈希效率要高，即使很長的輸入參數也能快速計算出哈希值。

• 可確定性：哈希過程必須是確定性的，這意味著對于給定的輸入值，它必須始終生成相同的哈希值。

• 雪崩效應：微小的輸入值變化也會讓輸出值發(fā)生巨大的變化。

• 不可逆：從哈希函數的輸出值不可反向推導出原始的數據。

重復一遍，哈希函數是將任意大小的數據映射到固定大小值的函數。那么，我們可以預見到，即使哈希函數設計得足夠優(yōu)秀，幾乎每個輸入值都能映射為不同的哈希值。但是，當輸入數據足夠大，大到能超過固定大小值的組合能表達的最大數量數，沖突將不可避免?。▍⒁姵閷显恚?/p>

抽屜原理：桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發(fā)現至少會有一個抽屜里面放不少于兩個蘋果。抽屜原理有時也被稱為鴿巢原理。

• 如何解決哈希沖突

比較常用的Has沖突解決方案有鏈地址法和開放尋址法。

在講鏈地址法之前，先說明兩個概念。

1. 哈希桶。哈希桶（也稱為槽，類似于抽屜原理中的一個抽屜）可以先簡單理解為一個哈希值，所有的哈希值組成了哈?？臻g。

2. 裝載因子。裝載因子是表示哈希表中元素的填滿程度。它的計算公式：裝載因子=填入哈希表中的元素個數/哈希表的長度。裝載因子越大，填入的元素越多，空間利用率就越高，但發(fā)生哈希沖突的幾率就變大。反之，裝載因子越小，填入的元素越少，沖突發(fā)生的幾率減小，但空間浪費也會變得更多，而且還會提高擴容操作的次數。裝載因子也是決定哈希表是否進行擴容的關鍵指標，在java的HashMap的中，其默認裝載因子為0.75；Python的dict默認裝載因子為2/3。

鏈地址法的思想就是將映射在一個桶里的所有元素用鏈表串起來。

下面以一個簡單的哈希函數 H(key) = key MOD 7（除數取余法）對一組元素 [50, 700, 76, 85, 92, 73, 101] 進行映射，通過圖示來理解鏈地址法處理Hash沖突的處理邏輯。

鏈地址法解決沖突的方式與圖的鄰接表存儲方式在樣式上很相似，發(fā)生沖突，就用單鏈表組織起來。

對于鏈地址法而言，槽位數m與鍵的數目n是沒有直接關系的。但是對于開放尋址法而言，所有的元素都是存儲在Hash表當中的，所以無論任何時候都要保證哈希表的槽位數m大于或等于鍵的數據n（必要時，需要對哈希表進行動態(tài)擴容）。

開放尋址法有多種方式：線性探測法、平方探測法、隨機探測法和雙重哈希法。這里以線性探測法來幫助讀者理解開放尋址法思想。

• 線性探測法

設 Hash(key) 表示關鍵字 key 的哈希值， 表示哈希表的槽位數（哈希表的大?。?。

線性探測法則可以表示為：

如果 Hash(x) % M 已經有數據，則嘗試 (Hash(x) + 1) % M ;

如果 (Hash(x) + 1) % M 也有數據了，則嘗試 (Hash(x) + 2) % M ;

如果 (Hash(x) + 2) % M 也有數據了，則嘗試 (Hash(x) + 3) % M ;

……

我們同樣以哈希函數 H(key) = key MOD 7 （除數取余法）對 [50, 700, 76, 85, 92, 73, 101] 進行映射，通過圖示來理解線性探測法處理 Hash 碰撞。

其中，empty代表槽位為空，occupied代表槽位已被占（后續(xù)映射到該槽，則需要線性向下繼續(xù)探測），而lazy delete則代表將槽位里面的數據清除，并不釋放存儲空間。

對于開放尋址法而言，它只有數組一種數據結構就可完成存儲，繼承了數組的優(yōu)點，對CPU緩存友好，易于序列化操作。但是它對內存的利用率不如鏈地址法，且發(fā)生沖突時代價更高。當數據量明確、裝載因子小，適合采用開放尋址法。

鏈表節(jié)點可以在需要時再創(chuàng)建，不必像開放尋址法那樣事先申請好足夠內存，因此鏈地址法對于內存的利用率會比開方尋址法高。鏈地址法對裝載因子的容忍度會更高，并且適合存儲大對象、大數據量的哈希表。而且相較于開放尋址法，它更加靈活，支持更多的優(yōu)化策略，比如可采用紅黑樹代替鏈表。但是鏈地址法需要額外的空間來存儲指針。

值得一提的是，在Python中dict在發(fā)生哈希沖突時采用的開放尋址法，而java的HashMap采用的是鏈地址法。

Go Map 實現

同python與java一樣，Go語言中的map是也基于哈希表實現的，它解決哈希沖突的方式是鏈地址法，即通過使用數組+鏈表的數據結構來表達map。

注意：本文后續(xù)出現的map統(tǒng)一代指Go中實現的map類型。

map中的數據被存放于一個數組中的，數組的元素是桶（bucket），每個桶至多包含8個鍵值對數據。哈希值低位（low-order bits）用于選擇桶，哈希值高位（high-order bits）用于在一個獨立的桶中區(qū)別出鍵。哈希值高低位示意圖如下

本文基于go 1.15.2 darwin/amd64分析，源碼位于src/runtime/map.go.

• map的結構體為hmap

 1// A header for a Go map.
 2type hmap struct {
 3    count     int // 代表哈希表中的元素個數，調用len(map)時，返回的就是該字段值。
 4    flags     uint8 // 狀態(tài)標志，下文常量中會解釋四種狀態(tài)位含義。
 5    B         uint8  // buckets（桶）的對數log_2（哈希表元素數量最大可達到裝載因子*2^B）
 6    noverflow uint16 // 溢出桶的大概數量。
 7    hash0     uint32 // 哈希種子。
 8
 9    buckets    unsafe.Pointer // 指向buckets數組的指針，數組大小為2^B，如果元素個數為0，它為nil。
10    oldbuckets unsafe.Pointer // 如果發(fā)生擴容，oldbuckets是指向老的buckets數組的指針，老的buckets數組大小是新的buckets的1/2。非擴容狀態(tài)下，它為nil。
11    nevacuate  uintptr        // 表示擴容進度，小于此地址的buckets代表已搬遷完成。
12
13    extra *mapextra // 這個字段是為了優(yōu)化GC掃描而設計的。當key和value均不包含指針，并且都可以inline時使用。extra是指向mapextra類型的指針。

• mapextra的結構體

 1// mapextra holds fields that are not present on all maps.
 2type mapextra struct {
 3    // 如果 key 和 value 都不包含指針，并且可以被 inline(<=128 字節(jié))
 4    // 就使用 hmap的extra字段 來存儲 overflow buckets，這樣可以避免 GC 掃描整個 map
 5    // 然而 bmap.overflow 也是個指針。這時候我們只能把這些 overflow 的指針
 6    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
 7    // overflow 包含的是 hmap.buckets 的 overflow 的 buckets
 8    // oldoverflow 包含擴容時的 hmap.oldbuckets 的 overflow 的 bucket
 9    overflow    *[]*bmap
10    oldoverflow *[]*bmap
11
12    // 指向空閑的 overflow bucket 的指針
13    nextOverflow *bmap
14}

• bmap結構體

1// A bucket for a Go map.
2type bmap struct {
3    // tophash包含此桶中每個鍵的哈希值最高字節(jié)（高8位）信息（也就是前面所述的high-order bits）。
4    // 如果tophash[0] < minTopHash，tophash[0]則代表桶的搬遷（evacuation）狀態(tài)。
5    tophash [bucketCnt]uint8
6}

bmap也就是bucket（桶）的內存模型圖解如下（相關代碼邏輯可查看src/cmd/compile/internal/gc/reflect.go中的bmap()函數）。

在以上圖解示例中，該桶的第7位cell和第8位cell還未有對應鍵值對。需要注意的是，key和value是各自存儲起來的，并非想象中的key/value/key/value…的形式。這樣做雖然會讓代碼組織稍顯復雜，但是它的好處是能讓我們消除例如map[int64]int所需要的填充（padding）。此外，在8個鍵值對數據后面有一個overflow指針，因為桶中最多只能裝8個鍵值對，如果有多余的鍵值對落到了當前桶，那么就需要再構建一個桶（稱為溢出桶），通過overflow指針鏈接起來。

• 重要常量標志

 1const (
 2    // 一個桶中最多能裝載的鍵值對（key-value）的個數為8
 3    bucketCntBits = 3
 4    bucketCnt     = 1 << bucketCntBits
 5
 6  // 觸發(fā)擴容的裝載因子為13/2=6.5
 7    loadFactorNum = 13
 8    loadFactorDen = 2
 9
10    // 鍵和值超過128個字節(jié)，就會被轉換為指針
11    maxKeySize  = 128
12    maxElemSize = 128
13
14    // 數據偏移量應該是bmap結構體的大小，它需要正確地對齊。
15  // 對于amd64p32而言，這意味著：即使指針是32位的，也是64位對齊。
16    dataOffset = unsafe.Offsetof(struct {
17        b bmap
18        v int64
19    }{}.v)
20
21
22  // 每個桶（如果有溢出，則包含它的overflow的鏈桶）在搬遷完成狀態(tài)（evacuated* states）下，要么會包含它所有的鍵值對，要么一個都不包含（但不包括調用evacuate()方法階段，該方法調用只會在對map發(fā)起write時發(fā)生，在該階段其他goroutine是無法查看該map的）。簡單的說，桶里的數據要么一起搬走，要么一個都還未搬。
23  // tophash除了放置正常的高8位hash值，還會存儲一些特殊狀態(tài)值（標志該cell的搬遷狀態(tài)）。正常的tophash值，最小應該是5，以下列出的就是一些特殊狀態(tài)值。
24    emptyRest      = 0 // 表示cell為空，并且比它高索引位的cell或者overflows中的cell都是空的。（初始化bucket時，就是該狀態(tài)）
25    emptyOne       = 1 // 空的cell，cell已經被搬遷到新的bucket
26    evacuatedX     = 2 // 鍵值對已經搬遷完畢，key在新buckets數組的前半部分
27    evacuatedY     = 3 // 鍵值對已經搬遷完畢，key在新buckets數組的后半部分
28    evacuatedEmpty = 4 // cell為空，整個bucket已經搬遷完畢
29    minTopHash     = 5 // tophash的最小正常值
30
31    // flags
32    iterator     = 1 // 可能有迭代器在使用buckets
33    oldIterator  = 2 // 可能有迭代器在使用oldbuckets
34    hashWriting  = 4 // 有協(xié)程正在向map寫人key
35    sameSizeGrow = 8 // 等量擴容
36
37    // 用于迭代器檢查的bucket ID
38    noCheck = 1<<(8*sys.PtrSize) - 1
39)

綜上，我們以B等于4為例，展示一個完整的map結構圖。

map初始化有以下兩種方式

1make(map[k]v)
2// 指定初始化map大小為hint
3make(map[k]v, hint)

對于不指定初始化大小，和初始化值hint<=8（bucketCnt）時，go會調用makemap_small函數（源碼位置src/runtime/map.go），并直接從堆上進行分配。

1func makemap_small() *hmap {
2    h := new(hmap)
3    h.hash0 = fastrand()
4    return h
5}

當hint>8時，則調用makemap函數

 1// 如果編譯器認為map和第一個bucket可以直接創(chuàng)建在棧上，h和bucket可能都是非空
 2// 如果h != nil，那么map可以直接在h中創(chuàng)建
 3// 如果h.buckets != nil，那么h指向的bucket可以作為map的第一個bucket使用
 4func makemap(t *maptype, hint int, h *hmap) *hmap {
 5  // math.MulUintptr返回hint與t.bucket.size的乘積，并判斷該乘積是否溢出。
 6    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
 7// maxAlloc的值，根據平臺系統(tǒng)的差異而不同，具體計算方式參照src/runtime/malloc.go
 8    if overflow || mem > maxAlloc {
 9        hint = 0
10    }
11
12// initialize Hmap
13    if h == nil {
14        h = new(hmap)
15    }
16  // 通過fastrand得到哈希種子
17    h.hash0 = fastrand()
18
19    // 根據輸入的元素個數hint，找到能裝下這些元素的B值
20    B := uint8(0)
21    for overLoadFactor(hint, B) {
22        B++
23    }
24    h.B = B
25
26    // 分配初始哈希表
27  // 如果B為0，那么buckets字段后續(xù)會在mapassign方法中l(wèi)azily分配
28    if h.B != 0 {
29        var nextOverflow *bmap
30    // makeBucketArray創(chuàng)建一個map的底層保存buckets的數組，它最少會分配h.B^2的大小。
31        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
32        if nextOverflow != nil {
33    h.extra = new(mapextra)
34            h.extra.nextOverflow = nextOverflow
35        }
36    }
37
38    return h
39}

分配buckets數組的makeBucketArray函數

 1// makeBucket為map創(chuàng)建用于保存buckets的數組。
 2func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
 3    base := bucketShift(b)
 4    nbuckets := base
 5  // 對于小的b值（小于4），即桶的數量小于16時，使用溢出桶的可能性很小。對于此情況，就避免計算開銷。
 6    if b >= 4 {
 7    // 當桶的數量大于等于16個時，正常情況下就會額外創(chuàng)建2^(b-4)個溢出桶
 8        nbuckets += bucketShift(b - 4)
 9        sz := t.bucket.size * nbuckets
10        up := roundupsize(sz)
11        if up != sz {
12            nbuckets = up / t.bucket.size
13        }
14    }
15
16 // 這里，dirtyalloc分兩種情況。如果它為nil，則會分配一個新的底層數組。如果它不為nil，則它指向的是曾經分配過的底層數組，該底層數組是由之前同樣的t和b參數通過makeBucketArray分配的，如果數組不為空，需要把該數組之前的數據清空并復用。
17    if dirtyalloc == nil {
18        buckets = newarray(t.bucket, int(nbuckets))
19    } else {
20        buckets = dirtyalloc
21        size := t.bucket.size * nbuckets
22        if t.bucket.ptrdata != 0 {
23            memclrHasPointers(buckets, size)
24        } else {
25            memclrNoHeapPointers(buckets, size)
26        }
27}
28
29  // 即b大于等于4的情況下，會預分配一些溢出桶。
30  // 為了把跟蹤這些溢出桶的開銷降至最低，使用了以下約定：
31  // 如果預分配的溢出桶的overflow指針為nil，那么可以通過指針碰撞（bumping the pointer）獲得更多可用桶。
32  // （關于指針碰撞：假設內存是絕對規(guī)整的，所有用過的內存都放在一邊，空閑的內存放在另一邊，中間放著一個指針作為分界點的指示器，那所分配內存就僅僅是把那個指針向空閑空間那邊挪動一段與對象大小相等的距離，這種分配方式稱為“指針碰撞”）
33  // 對于最后一個溢出桶，需要一個安全的非nil指針指向它。
34    if base != nbuckets {
35        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
36        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
37        last.setoverflow(t, (*bmap)(buckets))
38    }
39    return buckets, nextOverflow
40}

根據上述代碼，我們能確定在正常情況下，正常桶和溢出桶在內存中的存儲空間是連續(xù)的，只是被hmap 中的不同字段引用而已。

在初始化go程序運行環(huán)境時（src/runtime/proc.go中的schedinit），就需要通過alginit方法完成對哈希的初始化。

 1func schedinit() {
 2    lockInit(&sched.lock, lockRankSched)
 3
 4    ...
 5
 6    tracebackinit()
 7    moduledataverify()
 8    stackinit()
 9    mallocinit()
10    fastrandinit() // must run before mcommoninit
11    mcommoninit(_g_.m, -1)
12    cpuinit()       // must run before alginit
13    // 這里調用alginit()
14    alginit()       // maps must not be used before this call
15    modulesinit()   // provides activeModules
16    typelinksinit() // uses maps, activeModules
17    itabsinit()     // uses activeModules
18
19    ...
20
21    goargs()
22    goenvs()
23    parsedebugvars()
24    gcinit()
25
26  ...
27}

對于哈希算法的選擇，程序會根據當前架構判斷是否支持AES，如果支持就使用AES hash，其實現代碼位于src/runtime/asm_{386,amd64,arm64}.s中；若不支持，其hash算法則根據xxhash算法（https://code.google.com/p/xxhash/）和cityhash算法（https://code.google.com/p/cityhash/）啟發(fā)而來，代碼分別對應于32位（src/runtime/hash42.go）和64位機器（src/runtime/hash42.go）中，對這部分內容感興趣的讀者可以深入研究。

 1func alginit() {
 2    // Install AES hash algorithms if the instructions needed are present.
 3    if (GOARCH == "386" || GOARCH == "amd64") &&
 4        cpu.X86.HasAES && // AESENC
 5        cpu.X86.HasSSSE3 && // PSHUFB
 6        cpu.X86.HasSSE41 { // PINSR{D,Q}
 7        initAlgAES()
 8        return
 9    }
10    if GOARCH == "arm64" && cpu.ARM64.HasAES {
11        initAlgAES()
12        return
13    }
14    getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
15    hashkey[0] |= 1 // make sure these numbers are odd
16    hashkey[1] |= 1
17    hashkey[2] |= 1
18    hashkey[3] |= 1
19}

上文在創(chuàng)建map的時候，我們可以知道m(xù)ap的哈希種子是通過h.hash0 = fastrand()得到的。它是在以下maptype中的hasher中被使用到，在下文內容中會看到hash值的生成。

 1type maptype struct {
 2    typ    _type
 3    key    *_type
 4    elem   *_type
 5    bucket *_type
 6  // hasher的第一個參數就是指向key的指針，h.hash0 = fastrand()得到的hash0，就是hasher方法的第二個參數。
 7  // hasher方法返回的就是hash值。
 8    hasher     func(unsafe.Pointer, uintptr) uintptr
 9    keysize    uint8  // size of key slot
10    elemsize   uint8  // size of elem slot
11    bucketsize uint16 // size of bucket
12    flags      uint32
13}
14

假定key經過哈希計算后得到64bit位的哈希值。如果B=5，buckets數組的長度，即桶的數量是32（2的5次方）。

例如，現要置一key于map中，該key經過哈希后，得到的哈希值如下：

前面我們知道，哈希值低位（low-order bits）用于選擇桶，哈希值高位（high-order bits）用于在一個獨立的桶中區(qū)別出鍵。當B等于5時，那么我們選擇的哈希值低位也是5位，即01010，它的十進制值為10，代表10號桶。再用哈希值的高8位，找到此key在桶中的位置。最開始桶中還沒有key，那么新加入的key和value就會被放入第一個key空位和value空位。

注意：對于高低位的選擇，該操作的實質是取余，但是取余開銷很大，在實際代碼實現中采用的是位操作。以下是tophash的實現代碼。

1func tophash(hash uintptr) uint8 {
2    top := uint8(hash >> (sys.PtrSize*8 - 8))
3    if top < minTopHash {
4        top += minTopHash
5    }
6    return top
7}

當兩個不同的key落在了同一個桶中，這時就發(fā)生了哈希沖突。go的解決方式是鏈地址法（這里為了讓讀者更好理解，只描述非擴容且該key是第一次添加的情況）：在桶中按照順序尋到第一個空位并記錄下來，后續(xù)在該桶和它的溢出桶中均未發(fā)現存在的該key，將key置于第一個空位；否則，去該桶的溢出桶中尋找空位，如果沒有溢出桶，則添加溢出桶，并將其置溢出桶的第一個空位（因為是第一次添加，所以不描述已存在該key的情況）。

上圖中的B值為5，所以桶的數量為32。通過哈希函數計算出待插入key的哈希值，低5位哈希00110，對應于6號桶；高8位10010111，十進制為151，由于桶中前6個cell已經有正常哈希值填充了(遍歷)，所以將151對應的高位哈希值放置于第7位cell（第8個cell為empty Rest，表明它還未使用），對應將key和value分別置于相應的第七個空位。

如果是查找key，那么我們會根據高位哈希值去桶中的每個cell中找，若在桶中沒找到，并且overflow不為nil，那么繼續(xù)去溢出桶中尋找，直至找到，如果所有的cell都找過了，還未找到，則返回key類型的默認值（例如key是int類型，則返回0）。

對于map的元素查找，其源碼實現如下

 1func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
 2  // 如果開啟了競態(tài)檢測 -race
 3    if raceenabled && h != nil {
 4        callerpc := getcallerpc()
 5        pc := funcPC(mapaccess1)
 6        racereadpc(unsafe.Pointer(h), callerpc, pc)
 7        raceReadObjectPC(t.key, key, callerpc, pc)
 8    }
 9  // 如果開啟了memory sanitizer -msan
10    if msanenabled && h != nil {
11        msanread(key, t.key.size)
12    }
13  // 如果map為空或者元素個數為0，返回零值
14    if h == nil || h.count == 0 {
15        if t.hashMightPanic() {
16            t.hasher(key, 0) // see issue 23734
17        }
18        return unsafe.Pointer(&zeroVal[0])
19    }
20  // 注意，這里是按位與操作
21  // 當h.flags對應的值為hashWriting（代表有其他goroutine正在往map中寫key）時，那么位計算的結果不為0，因此拋出以下錯誤。
22  // 這也表明，go的map是非并發(fā)安全的
23    if h.flags&hashWriting != 0 {
24        throw("concurrent map read and map write")
25    }
26  // 不同類型的key，會使用不同的hash算法，可詳見src/runtime/alg.go中typehash函數中的邏輯
27    hash := t.hasher(key, uintptr(h.hash0))
28    m := bucketMask(h.B)
29  // 按位與操作，找到對應的bucket
30    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
31  // 如果oldbuckets不為空，那么證明map發(fā)生了擴容
32  // 如果有擴容發(fā)生，老的buckets中的數據可能還未搬遷至新的buckets里
33  // 所以需要先在老的buckets中找
34    if c := h.oldbuckets; c != nil {
35        if !h.sameSizeGrow() {
36            m >>= 1
37        }
38        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
39    // 如果在oldbuckets中tophash[0]的值，為evacuatedX、evacuatedY，evacuatedEmpty其中之一
40    // 則evacuated()返回為true，代表搬遷完成。
41    // 因此，只有當搬遷未完成時，才會從此oldbucket中遍歷
42        if !evacuated(oldb) {
43            b = oldb
44        }
45    }
46  // 取出當前key值的tophash值
47    top := tophash(hash)
48  // 以下是查找的核心邏輯
49  // 雙重循環(huán)遍歷：外層循環(huán)是從桶到溢出桶遍歷；內層是桶中的cell遍歷
50  // 跳出循環(huán)的條件有三種：第一種是已經找到key值；第二種是當前桶再無溢出桶；
51  // 第三種是當前桶中有cell位的tophash值是emptyRest，這個值在前面解釋過，它代表此時的桶后面的cell還未利用，所以無需再繼續(xù)遍歷。
52bucketloop:
53    for ; b != nil; b = b.overflow(t) {
54        for i := uintptr(0); i < bucketCnt; i++ {
55      // 判斷tophash值是否相等
56            if b.tophash[i] != top {
57                if b.tophash[i] == emptyRest {
58                    break bucketloop
59                }
60                continue
61      }
62      // 因為在bucket中key是用連續(xù)的存儲空間存儲的，因此可以通過bucket地址+數據偏移量（bmap結構體的大小）+ keysize的大小，得到k的地址
63      // 同理，value的地址也是相似的計算方法，只是再要加上8個keysize的內存地址
64            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
65            if t.indirectkey() {
66                k = *((*unsafe.Pointer)(k))
67            }
68      // 判斷key是否相等
69            if t.key.equal(key, k) {
70                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
71                if t.indirectelem() {
72                    e = *((*unsafe.Pointer)(e))
73                }
74                return e
75            }
76        }
77    }
78  // 所有的bucket都未找到，則返回零值
79    return unsafe.Pointer(&zeroVal[0])
80}

以下是mapaccess1的查找過程圖解

map的元素查找，對應go代碼有兩種形式

1    // 形式一
2    v := m[k]
3    // 形式二
4    v, ok := m[k]

形式一的代碼實現，就是上述的mapaccess1方法。此外，在源碼中還有個mapaccess2方法，它的函數簽名如下。

1func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {}

與mapaccess1相比，mapaccess2多了一個bool類型的返回值，它代表的是是否在map中找到了對應的key。因為和mapaccess1基本一致，所以詳細代碼就不再貼出。

同時，源碼中還有mapaccessK方法，它的函數簽名如下。

1func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {}

與mapaccess1相比，mapaccessK同時返回了key和value，其代碼邏輯也一致。

對于寫入key的邏輯，其源碼實現如下

  1func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  2  // 如果h是空指針，賦值會引起panic
  3  // 例如以下語句
  4  // var m map[string]int
  5    // m["k"] = 1
  6    if h == nil {
  7        panic(plainError("assignment to entry in nil map"))
  8    }
  9  // 如果開啟了競態(tài)檢測 -race
 10    if raceenabled {
 11        callerpc := getcallerpc()
 12        pc := funcPC(mapassign)
 13        racewritepc(unsafe.Pointer(h), callerpc, pc)
 14        raceReadObjectPC(t.key, key, callerpc, pc)
 15    }
 16  // 如果開啟了memory sanitizer -msan
 17    if msanenabled {
 18        msanread(key, t.key.size)
 19    }
 20  // 有其他goroutine正在往map中寫key，會拋出以下錯誤
 21    if h.flags&hashWriting != 0 {
 22        throw("concurrent map writes")
 23    }
 24  // 通過key和哈希種子，算出對應哈希值
 25    hash := t.hasher(key, uintptr(h.hash0))
 26
 27  // 將flags的值與hashWriting做按位或運算
 28  // 因為在當前goroutine可能還未完成key的寫入，再次調用t.hasher會發(fā)生panic。
 29    h.flags ^= hashWriting
 30
 31    if h.buckets == nil {
 32        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
 33}
 34
 35again:
 36  // bucketMask返回值是2的B次方減1
 37  // 因此，通過hash值與bucketMask返回值做按位與操作，返回的在buckets數組中的第幾號桶
 38    bucket := hash & bucketMask(h.B)
 39  // 如果map正在搬遷（即h.oldbuckets != nil）中,則先進行搬遷工作。
 40    if h.growing() {
 41        growWork(t, h, bucket)
 42    }
 43  // 計算出上面求出的第幾號bucket的內存位置
 44  // post = start + bucketNumber * bucketsize
 45    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
 46    top := tophash(hash)
 47
 48    var inserti *uint8
 49    var insertk unsafe.Pointer
 50    var elem unsafe.Pointer
 51bucketloop:
 52    for {
 53    // 遍歷桶中的8個cell
 54        for i := uintptr(0); i < bucketCnt; i++ {
 55      // 這里分兩種情況，第一種情況是cell位的tophash值和當前tophash值不相等
 56      // 在 b.tophash[i] != top 的情況下
 57      // 理論上有可能會是一個空槽位
 58      // 一般情況下 map 的槽位分布是這樣的，e 表示 empty:
 59      // [h0][h2][h3][h4][h5][e][e][e]
 60      // 但在執(zhí)行過 delete 操作時，可能會變成這樣:
 61      // [h0][h2][e][e][h6][e][e][e]
 62      // 所以如果再插入的話，會盡量往前面的位置插
 63      // [h0][h2][e][e][h6][e][e][e]
 64      //          ^
 65      //          ^
 66      //       這個位置
 67      // 所以在循環(huán)的時候還要順便把前面的空位置先記下來
 68      // 因為有可能在后面會找到相等的key，也可能找不到相等的key
 69            if b.tophash[i] != top {
 70        // 如果cell位為空，那么就可以在對應位置進行插入
 71                if isEmpty(b.tophash[i]) && inserti == nil {
 72                    inserti = &b.tophash[i]
 73                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
 74                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
 75                }
 76                if b.tophash[i] == emptyRest {
 77                    break bucketloop
 78                }
 79                continue
 80            }
 81      // 第二種情況是cell位的tophash值和當前的tophash值相等
 82            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
 83            if t.indirectkey() {
 84                k = *((*unsafe.Pointer)(k))
 85            }
 86      // 注意，即使當前cell位的tophash值相等，不一定它對應的key也是相等的，所以還要做一個key值判斷
 87            if !t.key.equal(key, k) {
 88                continue
 89            }
 90            // 如果已經有該key了，就更新它
 91            if t.needkeyupdate() {
 92                typedmemmove(t.key, k, key)
 93            }
 94      // 這里獲取到了要插入key對應的value的內存地址
 95      // pos = start + dataOffset + 8*keysize + i*elemsize
 96            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
 97      // 如果順利到這，就直接跳到done的結束邏輯中去
 98            goto done
 99        }
100    // 如果桶中的8個cell遍歷完，還未找到對應的空cell或覆蓋cell，那么就進入它的溢出桶中去遍歷
101        ovf := b.overflow(t)
102    // 如果連溢出桶中都沒有找到合適的cell，跳出循環(huán)。
103        if ovf == nil {
104            break
105        }
106        b = ovf
107    }
108
109    // 在已有的桶和溢出桶中都未找到合適的cell供key寫入，那么有可能會觸發(fā)以下兩種情況
110  // 情況一：
111  // 判斷當前map的裝載因子是否達到設定的6.5閾值，或者當前map的溢出桶數量是否過多。如果存在這兩種情況之一，則進行擴容操作。
112  // hashGrow()實際并未完成擴容，對哈希表數據的搬遷（復制）操作是通過growWork()來完成的。
113  // 重新跳入again邏輯，在進行完growWork()操作后，再次遍歷新的桶。
114    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
115        hashGrow(t, h)
116        goto again // Growing the table invalidates everything, so try again
117    }
118
119  // 情況二：
120// 在不滿足情況一的條件下，會為當前桶再新建溢出桶，并將tophash，key插入到新建溢出桶的對應內存的0號位置
121    if inserti == nil {
122        // all current buckets are full, allocate a new one.
123        newb := h.newoverflow(t, b)
124        inserti = &newb.tophash[0]
125        insertk = add(unsafe.Pointer(newb), dataOffset)
126        elem = add(insertk, bucketCnt*uintptr(t.keysize))
127    }
128
129  // 在插入位置存入新的key和value
130    if t.indirectkey() {
131        kmem := newobject(t.key)
132        *(*unsafe.Pointer)(insertk) = kmem
133        insertk = kmem
134    }
135    if t.indirectelem() {
136        vmem := newobject(t.elem)
137        *(*unsafe.Pointer)(elem) = vmem
138    }
139    typedmemmove(t.key, insertk, key)
140    *inserti = top
141  // map中的key數量+1
142    h.count++
143
144done:
145    if h.flags&hashWriting == 0 {
146        throw("concurrent map writes")
147    }
148    h.flags &^= hashWriting
149    if t.indirectelem() {
150        elem = *((*unsafe.Pointer)(elem))
151    }
152    return elem
153}

通過對mapassign的代碼分析之后，發(fā)現該函數并沒有將插入key對應的value寫入對應的內存，而是返回了value應該插入的內存地址。為了弄清楚value寫入內存的操作是發(fā)生在什么時候，分析如下map.go代碼。

1package main
2
3func main() {
4    m := make(map[int]int)
5    for i := 0; i < 100; i++ {
6        m[i] = 666
7    }
8}

m[i] = 666對應的匯編代碼

 1$ go tool compile -S map.go
 2...
 3        0x0098 00152 (map.go:6) LEAQ    type.map[int]int(SB), CX
 4        0x009f 00159 (map.go:6) MOVQ    CX, (SP)
 5        0x00a3 00163 (map.go:6) LEAQ    ""..autotmp_2+184(SP), DX
 6        0x00ab 00171 (map.go:6) MOVQ    DX, 8(SP)
 7        0x00b0 00176 (map.go:6) MOVQ    AX, 16(SP)
 8        0x00b5 00181 (map.go:6) CALL    runtime.mapassign_fast64(SB) // 調用函數runtime.mapassign_fast64，該函數實質就是mapassign（上文示例源代碼是該mapassign系列的通用邏輯）
 9        0x00ba 00186 (map.go:6) MOVQ    24(SP), AX 24(SP), AX // 返回值，即 value 應該存放的內存地址
10        0x00bf 00191 (map.go:6) MOVQ    $666, (AX) // 把 666 放入該地址中
11...        

賦值的最后一步實際上是編譯器額外生成的匯編指令來完成的，可見靠 runtime 有些工作是沒有做完的。所以，在go中，編譯器和 runtime 配合，才能完成一些復雜的工作。同時說明，在平時學習go的源代碼實現時，必要時還需要看一些匯編代碼。

理解了賦值key的邏輯，刪除key的邏輯就比較簡單了。本文就不再討論該部分內容了，讀者感興趣可以自行查看src/runtime/map.go的mapdelete方法邏輯。

結論：迭代 map 的結果是無序的

1    m := make(map[int]int)
2    for i := 0; i < 10; i++ {
3        m[i] = i
4    }
5    for k, v := range m {
6        fmt.Println(k, v)
7    }

運行以上代碼，我們會發(fā)現每次輸出順序都是不同的。

map遍歷的過程，是按序遍歷bucket，同時按需遍歷bucket中和其overflow bucket中的cell。但是map在擴容后，會發(fā)生key的搬遷，這造成原來落在一個bucket中的key，搬遷后，有可能會落到其他bucket中了，從這個角度看，遍歷map的結果就不可能是按照原來的順序了（詳見下文的map擴容內容）。

但其實，go為了保證遍歷map的結果是無序的，做了以下事情：map在遍歷時，并不是從固定的0號bucket開始遍歷的，每次遍歷，都會從一個隨機值序號的bucket，再從其中隨機的cell開始遍歷。然后再按照桶序遍歷下去，直到回到起始桶結束。

上圖的例子，是遍歷一個處于未擴容狀態(tài)的map。如果map正處于擴容狀態(tài)時，需要先判斷當前遍歷bucket是否已經完成搬遷，如果數據還在老的bucket，那么就去老bucket中拿數據。

注意：在下文中會講解到增量擴容和等量擴容。當發(fā)生了增量擴容時，一個老的bucket數據可能會分裂到兩個不同的bucket中去，那么此時，如果需要從老的bucket中遍歷數據，例如1號，則不能將老1號bucket中的數據全部取出，僅僅只能取出老 1 號 bucket 中那些在裂變之后，分配到新 1 號 bucket 中的那些 key（這個內容，請讀者看完下文map擴容的講解之后再回頭理解）。

鑒于篇幅原因，本文不再對map遍歷的詳細源碼進行注釋貼出。讀者可自行查看源碼src/runtime/map.go的mapiterinit()和mapiternext()方法邏輯。

這里注釋一下mapiterinit()中隨機保證的關鍵代碼

1// 生成隨機數
2r := uintptr(fastrand())
3if h.B > 31-bucketCntBits {
4   r += uintptr(fastrand()) << 31
5}
6// 決定了從哪個隨機的bucket開始
7it.startBucket = r & bucketMask(h.B)
8// 決定了每個bucket中隨機的cell的位置
9it.offset = uint8(r >> h.B & (bucketCnt - 1))

在文中講解裝載因子時，我們提到裝載因子是決定哈希表是否進行擴容的關鍵指標。在go的map擴容中，除了裝載因子會決定是否需要擴容，溢出桶的數量也是擴容的另一關鍵指標。

為了保證訪問效率，當map將要添加、修改或刪除key時，都會檢查是否需要擴容，擴容實際上是以空間換時間的手段。在之前源碼mapassign中，其實已經注釋map擴容條件，主要是兩點:

1. 判斷已經達到裝載因子的臨界點，即元素個數 >= 桶（bucket）總數 * 6.5，這時候說明大部分的桶可能都快滿了（即平均每個桶存儲的鍵值對達到6.5個），如果插入新元素，有大概率需要掛在溢出桶（overflow bucket）上。

1func overLoadFactor(count int, B uint8) bool {
2    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
3}

2. 判斷溢出桶是否太多，當桶總數 < 2 ^ 15 時，如果溢出桶總數 >= 桶總數，則認為溢出桶過多。當桶總數 >= 2 ^ 15 時，直接與 2 ^ 15 比較，當溢出桶總數 >= 2 ^ 15 時，即認為溢出桶太多了。

1func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
2    if B > 15 {
3        B = 15
4    }
5    return noverflow >= uint16(1)<<(B&15)
6}

對于第2點，其實算是對第 1 點的補充。因為在裝載因子比較小的情況下，有可能 map 的查找和插入效率也很低，而第 1 點識別不出來這種情況。表面現象就是計算裝載因子的分子比較小，即 map 里元素總數少，但是桶數量多（真實分配的桶數量多，包括大量的溢出桶）。

在某些場景下，比如不斷的增刪，這樣會造成overflow的bucket數量增多，但負載因子又不高，未達不到第 1 點的臨界值，就不能觸發(fā)擴容來緩解這種情況。這樣會造成桶的使用率不高，值存儲得比較稀疏，查找插入效率會變得非常低，因此有了第 2 點判斷指標。這就像是一座空城，房子很多，但是住戶很少，都分散了，找起人來很困難。

如上圖所示，由于對map的不斷增刪，以0號bucket為例，該桶鏈中就造成了大量的稀疏桶。

兩種情況官方采用了不同的解決方案

• 針對 1，將 B + 1，新建一個buckets數組，新的buckets大小是原來的2倍，然后舊buckets數據搬遷到新的buckets。該方法我們稱之為增量擴容。

• 針對 2，并不擴大容量，buckets數量維持不變，重新做一遍類似增量擴容的搬遷動作，把松散的鍵值對重新排列一次，以使bucket的使用率更高，進而保證更快的存取。該方法我們稱之為等量擴容。

對于 2 的解決方案，其實存在一個極端的情況：如果插入 map 的 key 哈希都一樣，那么它們就會落到同一個 bucket 里，超過 8 個就會產生 overflow bucket，結果也會造成 overflow bucket 數過多。移動元素其實解決不了問題，因為這時整個哈希表已經退化成了一個鏈表，操作效率變成了 O(n)。但 Go 的每一個 map 都會在初始化階段的 makemap時定一個隨機的哈希種子，所以要構造這種沖突是沒那么容易的。

在源碼中，和擴容相關的主要是hashGrow()函數與growWork()函數。hashGrow() 函數實際上并沒有真正地“搬遷”，它只是分配好了新的 buckets，并將老的 buckets 掛到了 oldbuckets 字段上。真正搬遷 buckets 的動作在 growWork() 函數中，而調用 growWork() 函數的動作是在mapassign() 和 mapdelete() 函數中。也就是插入（包括修改）、刪除 key 的時候，都會嘗試進行搬遷 buckets 的工作。它們會先檢查 oldbuckets 是否搬遷完畢（檢查 oldbuckets 是否為 nil），再決定是否進行搬遷工作。

hashGrow()函數

 1func hashGrow(t *maptype, h *hmap) {
 2  // 如果達到條件 1，那么將B值加1，相當于是原來的2倍
 3  // 否則對應條件 2，進行等量擴容，所以 B 不變
 4    bigger := uint8(1)
 5    if !overLoadFactor(h.count+1, h.B) {
 6        bigger = 0
 7        h.flags |= sameSizeGrow
 8    }
 9  // 記錄老的buckets
10    oldbuckets := h.buckets
11  // 申請新的buckets空間
12    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
13  // 注意&^ 運算符，這塊代碼的邏輯是轉移標志位
14    flags := h.flags &^ (iterator | oldIterator)
15    if h.flags&iterator != 0 {
16        flags |= oldIterator
17    }
18    // 提交grow (atomic wrt gc)
19    h.B += bigger
20    h.flags = flags
21    h.oldbuckets = oldbuckets
22    h.buckets = newbuckets
23  // 搬遷進度為0
24    h.nevacuate = 0
25  // overflow buckets 數為0
26    h.noverflow = 0
27
28  // 如果發(fā)現hmap是通過extra字段 來存儲 overflow buckets時
29    if h.extra != nil && h.extra.overflow != nil {
30        if h.extra.oldoverflow != nil {
31            throw("oldoverflow is not nil")
32        }
33        h.extra.oldoverflow = h.extra.overflow
34        h.extra.overflow = nil
35    }
36    if nextOverflow != nil {
37        if h.extra == nil {
38            h.extra = new(mapextra)
39        }
40        h.extra.nextOverflow = nextOverflow
41    }
42}

growWork()函數

 1func growWork(t *maptype, h *hmap, bucket uintptr) {
 2  // 為了確認搬遷的 bucket 是我們正在使用的 bucket
 3  // 即如果當前key映射到老的bucket1，那么就搬遷該bucket1。
 4    evacuate(t, h, bucket&h.oldbucketmask())
 5
 6    // 如果還未完成擴容工作，則再搬遷一個bucket。
 7    if h.growing() {
 8        evacuate(t, h, h.nevacuate)
 9    }
10}

從growWork()函數可以知道，搬遷的核心邏輯是evacuate()函數。這里讀者可以思考一個問題：為什么每次至多搬遷2個bucket？這其實是一種性能考量，如果map存儲了數以億計的key-value，一次性搬遷將會造成比較大的延時，因此才采用逐步搬遷策略。

在講解該邏輯之前，需要讀者先理解以下兩個知識點。

• 知識點1：bucket序號的變化

前面講到，增量擴容（條件1）和等量擴容（條件2）都需要進行bucket的搬遷工作。對于等量擴容而言，由于buckets的數量不變，因此可以按照序號來搬遷。例如老的的0號bucket，仍然搬至新的0號bucket中。

但是，對于增量擴容而言，就會有所不同。例如原來的B=5，那么增量擴容時，B就會變成6。那么決定key值落入哪個bucket的低位哈希值就會發(fā)生變化（從取5位變?yōu)槿?位），取新的低位hash值得過程稱為rehash。

因此，在增量擴容中，某個 key 在搬遷前后 bucket 序號可能和原來相等，也可能是相比原來加上 2^B（原來的 B 值），取決于低 hash 值第倒數第B+1位是 0 還是 1。

如上圖所示，當原始的B = 3時，舊buckets數組長度為8，在編號為2的bucket中，其2號cell和5號cell，它們的低3位哈希值相同（不相同的話，也就不會落在同一個桶中了），但是它們的低4位分別是0010、1010。當發(fā)生了增量擴容，2號就會被搬遷到新buckets數組的2號bucket中去，5號被搬遷到新buckets數組的10號bucket中去，它們的桶號差距是2的3次方。

• 知識點2：確定搬遷區(qū)間

在源碼中，有bucket x 和bucket y的概念，其實就是增量擴容到原來的 2 倍，桶的數量是原來的 2 倍，前一半桶被稱為bucket x，后一半桶被稱為bucket y。一個 bucket 中的 key 可能會分裂到兩個桶中去，分別位于bucket x的桶，或bucket y中的桶。所以在搬遷一個 cell 之前，需要知道這個 cell 中的 key 是落到哪個區(qū)間（而對于同一個桶而言，搬遷到bucket x和bucket y桶序號的差別是老的buckets大小，即2^old_B）。

思考：為什么確定key落在哪個區(qū)間很重要？

確定了要搬遷到的目標 bucket 后，搬遷操作就比較好進行了。將源 key/value 值 copy 到目的地相應的位置。設置 key 在原始 buckets 的 tophash 為 evacuatedX 或是 evacuatedY，表示已經搬遷到了新 map 的bucket x或是bucket y，新 map 的 tophash 則正常取 key 哈希值的高 8 位。

下面正式解讀搬遷核心代碼evacuate()函數。

evacuate()函數

  1func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
  2  // 首先定位老的bucket的地址
  3    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  4  // newbit代表擴容之前老的bucket個數
  5    newbit := h.noldbuckets()
  6  // 判斷該bucket是否已經被搬遷
  7    if !evacuated(b) {
  8    // 官方TODO，后續(xù)版本也許會實現
  9        // TODO: reuse overflow buckets instead of using new ones, if there
 10        // is no iterator using the old buckets.  (If !oldIterator.)
 11
 12    // xy 包含了高低區(qū)間的搬遷目的地內存信息
 13    // x.b 是對應的搬遷目的桶
 14    // x.k 是指向對應目的桶中存儲當前key的內存地址
 15    // x.e 是指向對應目的桶中存儲當前value的內存地址
 16        var xy [2]evacDst
 17        x := &xy[0]
 18        x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
 19        x.k = add(unsafe.Pointer(x.b), dataOffset)
 20        x.e = add(x.k, bucketCnt*uintptr(t.keysize))
 21
 22    // 只有當增量擴容時才計算bucket y的相關信息（和后續(xù)計算useY相呼應）
 23        if !h.sameSizeGrow() {
 24            y := &xy[1]
 25            y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
 26            y.k = add(unsafe.Pointer(y.b), dataOffset)
 27            y.e = add(y.k, bucketCnt*uintptr(t.keysize))
 28        }
 29
 30    // evacuate 函數每次只完成一個 bucket 的搬遷工作，因此要遍歷完此 bucket 的所有的 cell，將有值的 cell copy 到新的地方。
 31    // bucket 還會鏈接 overflow bucket，它們同樣需要搬遷。
 32    // 因此同樣會有 2 層循環(huán)，外層遍歷 bucket 和 overflow bucket，內層遍歷 bucket 的所有 cell。
 33
 34    // 遍歷當前桶bucket和其之后的溢出桶overflow bucket
 35    // 注意：初始的b是待搬遷的老bucket
 36        for ; b != nil; b = b.overflow(t) {
 37            k := add(unsafe.Pointer(b), dataOffset)
 38            e := add(k, bucketCnt*uintptr(t.keysize))
 39      // 遍歷桶中的cell，i，k，e分別用于對應tophash，key和value
 40            for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
 41                top := b.tophash[i]
 42        // 如果當前cell的tophash值是emptyOne或者emptyRest，則代表此cell沒有key。并將其標記為evacuatedEmpty，表示它“已經被搬遷”。
 43                if isEmpty(top) {
 44                    b.tophash[i] = evacuatedEmpty
 45                    continue
 46                }
 47        // 正常不會出現這種情況
 48        // 未被搬遷的 cell 只可能是emptyOne、emptyRest或是正常的 top hash（大于等于 minTopHash）
 49                if top < minTopHash {
 50                    throw("bad map state")
 51                }
 52                k2 := k
 53        // 如果 key 是指針，則解引用
 54                if t.indirectkey() {
 55                    k2 = *((*unsafe.Pointer)(k2))
 56                }
 57                var useY uint8
 58        // 如果是增量擴容
 59                if !h.sameSizeGrow() {
 60          // 計算哈希值，判斷當前key和vale是要被搬遷到bucket x還是bucket y
 61                    hash := t.hasher(k2, uintptr(h.hash0))
 62                    if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
 63            // 有一個特殊情況：有一種 key，每次對它計算 hash，得到的結果都不一樣。
 64            // 這個 key 就是 math.NaN() 的結果，它的含義是 not a number，類型是 float64。
 65            // 當它作為 map 的 key時，會遇到一個問題：再次計算它的哈希值和它當初插入 map 時的計算出來的哈希值不一樣！
 66            // 這個 key 是永遠不會被 Get 操作獲取的！當使用 m[math.NaN()] 語句的時候，是查不出來結果的。
 67            // 這個 key 只有在遍歷整個 map 的時候，才能被找到。
 68            // 并且，可以向一個 map 插入多個數量的 math.NaN() 作為 key，它們并不會被互相覆蓋。
 69            // 當搬遷碰到 math.NaN() 的 key 時，只通過 tophash 的最低位決定分配到 X part 還是 Y part（如果擴容后是原來 buckets 數量的 2 倍）。如果 tophash 的最低位是 0 ，分配到 X part；如果是 1 ，則分配到 Y part。
 70                        useY = top & 1
 71                        top = tophash(hash)
 72          // 對于正常key，進入以下else邏輯  
 73                    } else {
 74                        if hash&newbit != 0 {
 75                            useY = 1
 76                        }
 77                    }
 78                }
 79
 80                if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
 81                    throw("bad evacuatedN")
 82                }
 83
 84        // evacuatedX + 1 == evacuatedY
 85                b.tophash[i] = evacuatedX + useY
 86        // useY要么為0，要么為1。這里就是選取在bucket x的起始內存位置，或者選擇在bucket y的起始內存位置（只有增量同步才會有這個選擇可能）。
 87                dst := &xy[useY]
 88
 89        // 如果目的地的桶已經裝滿了（8個cell），那么需要新建一個溢出桶，繼續(xù)搬遷到溢出桶上去。
 90                if dst.i == bucketCnt {
 91                    dst.b = h.newoverflow(t, dst.b)
 92                    dst.i = 0
 93                    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
 94                    dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
 95                }
 96                dst.b.tophash[dst.i&(bucketCnt-1)] = top
 97        // 如果待搬遷的key是指針，則復制指針過去
 98                if t.indirectkey() {
 99                    *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
100        // 如果待搬遷的key是值，則復制值過去  
101                } else {
102                    typedmemmove(t.key, dst.k, k) // copy elem
103                }
104        // value和key同理
105                if t.indirectelem() {
106                    *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
107                } else {
108                    typedmemmove(t.elem, dst.e, e)
109                }
110        // 將當前搬遷目的桶的記錄key/value的索引值（也可以理解為cell的索引值）加一
111                dst.i++
112        // 由于桶的內存布局中在最后還有overflow的指針，多以這里不用擔心更新有可能會超出key和value數組的指針地址。
113                dst.k = add(dst.k, uintptr(t.keysize))
114                dst.e = add(dst.e, uintptr(t.elemsize))
115            }
116        }
117    // 如果沒有協(xié)程在使用老的桶，就對老的桶進行清理，用于幫助gc
118        if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
119            b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
120      // 只清除bucket 的 key,value 部分，保留 top hash 部分，指示搬遷狀態(tài)
121            ptr := add(b, dataOffset)
122            n := uintptr(t.bucketsize) - dataOffset
123            memclrHasPointers(ptr, n)
124        }
125    }
126
127  // 用于更新搬遷進度
128    if oldbucket == h.nevacuate {
129        advanceEvacuationMark(h, t, newbit)
130    }
131}
132
133func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
134  // 搬遷桶的進度加一
135    h.nevacuate++
136  // 實驗表明，1024至少會比newbit高出一個數量級（newbit代表擴容之前老的bucket個數）。所以，用當前進度加上1024用于確保O(1)行為。
137    stop := h.nevacuate + 1024
138    if stop > newbit {
139        stop = newbit
140    }
141  // 計算已經搬遷完的桶數
142    for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
143        h.nevacuate++
144    }
145  // 如果h.nevacuate == newbit，則代表所有的桶都已經搬遷完畢
146    if h.nevacuate == newbit {
147    // 搬遷完畢，所以指向老的buckets的指針置為nil
148        h.oldbuckets = nil
149    // 在講解hmap的結構中，有過說明。如果key和value均不包含指針，則都可以inline。
150    // 那么保存它們的buckets數組其實是掛在hmap.extra中的。所以，這種情況下，其實我們是搬遷的extra的buckets數組。
151    // 因此，在這種情況下，需要在搬遷完畢后，將hmap.extra.oldoverflow指針置為nil。
152        if h.extra != nil {
153            h.extra.oldoverflow = nil
154        }
155    // 最后，清除正在擴容的標志位，擴容完畢。
156        h.flags &^= sameSizeGrow
157    }
158}

代碼比較長，但是文中注釋已經比較清晰了，如果對map的擴容還不清楚，可以參見以下圖解。

針對上圖的map，其B為3，所以原始buckets數組為8。當map元素數變多，加載因子超過6.5，所以引起了增量擴容。

以3號bucket為例，可以看到，由于B值加1，所以在新選取桶時，需要取低4位哈希值，這樣就會造成cell會被搬遷到新buckets數組中不同的桶（3號或11號桶）中去。注意，在一個桶中，搬遷cell的工作是有序的：它們是依序填進對應新桶的cell中去的。

當然，實際情況中3號桶很可能還有溢出桶，在這里為了簡化繪圖，假設3號桶沒有溢出桶，如果有溢出桶，則相應地添加到新的3號桶和11號桶中即可，如果對應的3號和11號桶均裝滿，則給新的桶添加溢出桶來裝載。

對于上圖的map，其B也為3。假設整個map中的overflow過多，觸發(fā)了等量擴容。注意，等量擴容時，新的buckets數組大小和舊buckets數組是一樣的。

以6號桶為例，它有一個bucket和3個overflow buckets，但是我們能夠發(fā)現桶里的數據非常稀疏，等量擴容的目的就是為了把松散的鍵值對重新排列一次，以使bucket的使用率更高，進而保證更快的存取。搬遷完畢后，新的6號桶中只有一個基礎bucket，暫時并不需要溢出桶。這樣，和原6號桶相比，數據變得緊密，使后續(xù)的數據存取變快。

最后回答一下上文中留下的問題：為什么確定key落在哪個區(qū)間很重要？因為對于增量擴容而言，原本一個bucket中的key會被分裂到兩個bucket中去，它們分別處于bucket x和bucket y中，但是它們之間存在關系 bucket x + 2^B = bucket y （其中，B是老bucket對應的B值）。假設key所在的老bucket序號為n，那么如果key落在新的bucket x，則它應該置入 bucket x起始位置 + n*bucket 的內存中去；如果key落在新的bucket y，則它應該置入 bucket y起始位置 + n*bucket的內存中去。因此，確定key落在哪個區(qū)間，這樣就很方便進行內存地址計算，快速找到key應該插入的內存地址。

map 總結和使用建議

Go語言的map，底層是哈希表實現的，通過鏈地址法解決哈希沖突，它依賴的核心數據結構是數組加鏈表。

map中定義了2的B次方個桶，每個桶中能夠容納8個key。根據key的不同哈希值，將其散落到不同的桶中。哈希值的低位（哈希值的后B個bit位）決定桶序號，高位（哈希值的前8個bit位）標識同一個桶中的不同 key。

當向桶中添加了很多 key，造成元素過多，超過了裝載因子所設定的程度，或者多次增刪操作，造成溢出桶過多，均會觸發(fā)擴容。

擴容分為增量擴容和等量擴容。增量擴容，會增加桶的個數（增加一倍），把原來一個桶中的 keys 被重新分配到兩個桶中。等量擴容，不會更改桶的個數，只是會將桶中的數據變得緊湊。不管是增量擴容還是等量擴容，都需要創(chuàng)建新的桶數組，并不是原地操作的。

擴容過程是漸進性的，主要是防止一次擴容需要搬遷的 key 數量過多，引發(fā)性能問題。觸發(fā)擴容的時機是增加了新元素， 桶搬遷的時機則發(fā)生在賦值、刪除期間，每次最多搬遷兩個 桶。查找、賦值、刪除的一個很核心的內容是如何定位到 key 所在的位置，需要重點理解。一旦理解，關于 map 的源碼就可以看懂了。

從map設計可以知道，它并不是一個并發(fā)安全的數據結構。同時對map進行讀寫時，程序很容易出錯。因此，要想在并發(fā)情況下使用map，請加上鎖（sync.Mutex或者sync.RwMutex）。其實，Go標準庫中已經為我們實現了并發(fā)安全的map——sync.Map，我之前寫過文章對它的實現進行講解，詳情可以查看本公眾號《深入理解sync.Map》一文。

遍歷map的結果是無序的，在使用中，應該注意到該點。

通過map的結構體可以知道，它其實是通過指針指向底層buckets數組。所以和slice一樣，盡管go函數都是值傳遞，但是，當map作為參數被函數調用時，在函數內部對map的操作同樣會影響到外部的map。

另外，有個特殊的key值math.NaN，它每次生成的哈希值是不一樣的，這會造成m[math.NaN]是拿不到值的，而且多次對它賦值，會讓map中存在多個math.NaN的key。不過這個基本用不到，知道有這個特殊情況就可以了。