什么是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.

說(shuō)明：在計(jì)算機(jī)科學(xué)中，包含鍵值對(duì)（key-value）集合的抽象數(shù)據(jù)結(jié)構(gòu)（關(guān)聯(lián)數(shù)組、符號(hào)表或字典），其每個(gè)可能的鍵在該集合中最多出現(xiàn)一次，這樣的數(shù)據(jù)結(jié)構(gòu)就是一種Map。

操作

對(duì)Map的操作主要是增刪改查：

• 在集合中增加鍵值對(duì)
• 在集合中移除鍵值對(duì)
• 修改某個(gè)存在的鍵值對(duì)
• 根據(jù)特定的鍵尋找對(duì)應(yīng)的值

實(shí)現(xiàn)

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

哈希表和搜索樹對(duì)比

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

哈希表

由于Go中map的基于哈希表（也被稱為散列表）實(shí)現(xiàn)，本文不探討搜索樹的map實(shí)現(xiàn)。以下是Go官方博客對(duì)map的說(shuō)明。

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.

學(xué)習(xí)哈希表首先要理解兩個(gè)概念：哈希函數(shù)和哈希沖突。

哈希函數(shù)

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

一個(gè)設(shè)計(jì)優(yōu)秀的哈希函數(shù)應(yīng)該包含以下特性：

• 均勻性：一個(gè)好的哈希函數(shù)應(yīng)該在其輸出范圍內(nèi)盡可能均勻地映射，也就是說(shuō)，應(yīng)以大致相同的概率生成輸出范圍內(nèi)的每個(gè)哈希值。
• 效率高：哈希效率要高，即使很長(zhǎng)的輸入?yún)?shù)也能快速計(jì)算出哈希值。
• 可確定性：哈希過(guò)程必須是確定性的，這意味著對(duì)于給定的輸入值，它必須始終生成相同的哈希值。
• 雪崩效應(yīng)：微小的輸入值變化也會(huì)讓輸出值發(fā)生巨大的變化。
• 不可逆：從哈希函數(shù)的輸出值不可反向推導(dǎo)出原始的數(shù)據(jù)。

哈希沖突

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

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

如何解決哈希沖突

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

在講鏈地址法之前，先說(shuō)明兩個(gè)概念。

1. 哈希桶。哈希桶（也稱為槽，類似于抽屜原理中的一個(gè)抽屜）可以先簡(jiǎn)單理解為一個(gè)哈希值，所有的哈希值組成了哈希空間。
2. 裝載因子。裝載因子是表示哈希表中元素的填滿程度。它的計(jì)算公式：裝載因子=填入哈希表中的元素個(gè)數(shù)/哈希表的長(zhǎng)度。裝載因子越大，填入的元素越多，空間利用率就越高，但發(fā)生哈希沖突的幾率就變大。反之，裝載因子越小，填入的元素越少，沖突發(fā)生的幾率減小，但空間浪費(fèi)也會(huì)變得更多，而且還會(huì)提高擴(kuò)容操作的次數(shù)。裝載因子也是決定哈希表是否進(jìn)行擴(kuò)容的關(guān)鍵指標(biāo)，在java的HashMap的中，其默認(rèn)裝載因子為0.75；Python的dict默認(rèn)裝載因子為2/3。

鏈地址法

鏈地址法的思想就是將映射在一個(gè)桶里的所有元素用鏈表串起來(lái)。

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

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

開放尋址法

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

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

• 線性探測(cè)法

設(shè) Hash(key) 表示關(guān)鍵字 key 的哈希值， 表示哈希表的槽位數(shù)（哈希表的大?。?。

線性探測(cè)法則可以表示為：

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

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

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

......

我們同樣以哈希函數(shù) H(key) = key MOD 7 （除數(shù)取余法）對(duì) **[50, 700, 76, 85, 92, 73, 101]** 進(jìn)行映射，通過(guò)圖示來(lái)理解線性探測(cè)法處理 Hash 碰撞。

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

兩種解決方案比較

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

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

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

為什么要用 map

從 Go 語(yǔ)言官方博客摘錄一段話：

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.

hash table 是計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)中一個(gè)最重要的設(shè)計(jì)。大部分 hash table 都實(shí)現(xiàn)了快速查找、添加、刪除的功能。Go 語(yǔ)言內(nèi)置的 map 實(shí)現(xiàn)了上述所有功能。

很難想象寫一個(gè)程序不使用 map，以至于在回答為什么要用 map 這個(gè)問(wèn)題上犯了難。

所以，到底為什么要用 map 呢？因?yàn)樗珡?qiáng)大了，各種增刪查改的操作效率非常高。

Go Map實(shí)現(xiàn)

同python與java一樣，Go語(yǔ)言中的map是也基于哈希表實(shí)現(xiàn)的，它解決哈希沖突的方式是鏈地址法，即通過(guò)使用數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)map。

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

map數(shù)據(jù)結(jié)構(gòu)

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

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

• map的結(jié)構(gòu)體為hmap

// A header for a Go map.
type hmap struct {
    count     int // 代表哈希表中的元素個(gè)數(shù)，調(diào)用len(map)時(shí)，返回的就是該字段值。
    flags     uint8 // 狀態(tài)標(biāo)志，下文常量中會(huì)解釋四種狀態(tài)位含義。
    B         uint8  // buckets（桶）的對(duì)數(shù)log_2（哈希表元素?cái)?shù)量最大可達(dá)到裝載因子*2^B）
    noverflow uint16 // 溢出桶的大概數(shù)量。
    hash0     uint32 // 哈希種子。

    buckets    unsafe.Pointer // 指向buckets數(shù)組的指針，數(shù)組大小為2^B，如果元素個(gè)數(shù)為0，它為nil。
    oldbuckets unsafe.Pointer // 如果發(fā)生擴(kuò)容，oldbuckets是指向老的buckets數(shù)組的指針，老的buckets數(shù)組大小是新的buckets的1/2。非擴(kuò)容狀態(tài)下，它為nil。
    nevacuate  uintptr        // 表示擴(kuò)容進(jìn)度，小于此地址的buckets代表已搬遷完成。

    extra *mapextra // 這個(gè)字段是為了優(yōu)化GC掃描而設(shè)計(jì)的。當(dāng)key和value均不包含指針，并且都可以inline時(shí)使用。extra是指向mapextra類型的指針。

• mapextra的結(jié)構(gòu)體

// mapextra holds fields that are not present on all maps.
type mapextra struct {
    // 如果 key 和 value 都不包含指針，并且可以被 inline(<=128 字節(jié))
    // 就使用 hmap的extra字段 來(lái)存儲(chǔ) overflow buckets，這樣可以避免 GC 掃描整個(gè) map
    // 然而 bmap.overflow 也是個(gè)指針。這時(shí)候我們只能把這些 overflow 的指針
    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
    // overflow 包含的是 hmap.buckets 的 overflow 的 buckets
    // oldoverflow 包含擴(kuò)容時(shí)的 hmap.oldbuckets 的 overflow 的 bucket
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // 指向空閑的 overflow bucket 的指針
    nextOverflow *bmap
}

• bmap結(jié)構(gòu)體

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

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

bmap struct

在以上圖解示例中，該桶的第7位cell和第8位cell還未有對(duì)應(yīng)鍵值對(duì)。需要注意的是，key和value是各自存儲(chǔ)起來(lái)的，并非想象中的key/value/key/value...的形式。這樣做雖然會(huì)讓代碼組織稍顯復(fù)雜，但是它的好處是能讓我們消除例如map[int64]int所需要的填充（padding）。此外，在8個(gè)鍵值對(duì)數(shù)據(jù)后面有一個(gè)overflow指針，因?yàn)橥爸凶疃嘀荒苎b8個(gè)鍵值對(duì)，如果有多余的鍵值對(duì)落到了當(dāng)前桶，那么就需要再構(gòu)建一個(gè)桶（稱為溢出桶），通過(guò)overflow指針鏈接起來(lái)。

• 重要常量標(biāo)志

const (
    // 一個(gè)桶中最多能裝載的鍵值對(duì)（key-value）的個(gè)數(shù)為8
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits

  // 觸發(fā)擴(kuò)容的裝載因子為13/2=6.5
    loadFactorNum = 13
    loadFactorDen = 2

    // 鍵和值超過(guò)128個(gè)字節(jié)，就會(huì)被轉(zhuǎn)換為指針
    maxKeySize  = 128
    maxElemSize = 128

    // 數(shù)據(jù)偏移量應(yīng)該是bmap結(jié)構(gòu)體的大小，它需要正確地對(duì)齊。
  // 對(duì)于amd64p32而言，這意味著：即使指針是32位的，也是64位對(duì)齊。
    dataOffset = unsafe.Offsetof(struct {
        b bmap
        v int64
    }{}.v)

  // 每個(gè)桶（如果有溢出，則包含它的overflow的鏈接桶）在搬遷完成狀態(tài)（evacuated* states）下，要么會(huì)包含它所有的鍵值對(duì)，要么一個(gè)都不包含（但不包括調(diào)用evacuate()方法階段，該方法調(diào)用只會(huì)在對(duì)map發(fā)起write時(shí)發(fā)生，在該階段其他goroutine是無(wú)法查看該map的）。簡(jiǎn)單的說(shuō)，桶里的數(shù)據(jù)要么一起搬走，要么一個(gè)都還未搬。
  // tophash除了放置正常的高8位hash值，還會(huì)存儲(chǔ)一些特殊狀態(tài)值（標(biāo)志該cell的搬遷狀態(tài)）。正常的tophash值，最小應(yīng)該是5，以下列出的就是一些特殊狀態(tài)值。
    emptyRest      = 0 // 表示cell為空，并且比它高索引位的cell或者overflows中的cell都是空的。（初始化bucket時(shí)，就是該狀態(tài)）
    emptyOne       = 1 // 空的cell，cell已經(jīng)被搬遷到新的bucket
    evacuatedX     = 2 // 鍵值對(duì)已經(jīng)搬遷完畢，key在新buckets數(shù)組的前半部分
    evacuatedY     = 3 // 鍵值對(duì)已經(jīng)搬遷完畢，key在新buckets數(shù)組的后半部分
    evacuatedEmpty = 4 // cell為空，整個(gè)bucket已經(jīng)搬遷完畢
    minTopHash     = 5 // tophash的最小正常值

    // flags
    iterator     = 1 // 可能有迭代器在使用buckets
    oldIterator  = 2 // 可能有迭代器在使用oldbuckets
    hashWriting  = 4 // 有協(xié)程正在向map寫人key
    sameSizeGrow = 8 // 等量擴(kuò)容

    // 用于迭代器檢查的bucket ID
    noCheck = 1<<(8*sys.PtrSize) - 1
)

綜上，我們以B等于5為例，展示一個(gè)完整的map結(jié)構(gòu)圖。

創(chuàng)建map

map初始化有以下幾種方式

ageMp := make(map[string]int)
// 指定 map 長(zhǎng)度
ageMp := make(map[string]int, 8)

// ageMp 為 nil，不能向其添加元素，會(huì)直接panic
var ageMp map[string]int

對(duì)于不指定初始化大小，和初始化值hint<=8（bucketCnt）時(shí)，go會(huì)調(diào)用makemap_small函數(shù)（源碼位置src/runtime/map.go），并直接從堆上進(jìn)行分配。

func makemap_small() *hmap {
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

當(dāng)hint>8時(shí)，則調(diào)用makemap函數(shù)

// 如果編譯器認(rèn)為map和第一個(gè)bucket可以直接創(chuàng)建在棧上，h和bucket可能都是非空
// 如果h != nil，那么map可以直接在h中創(chuàng)建
// 如果h.buckets != nil，那么h指向的bucket可以作為map的第一個(gè)bucket使用
func makemap(t *maptype, hint int, h *hmap) *hmap {
  // math.MulUintptr返回hint與t.bucket.size的乘積，并判斷該乘積是否溢出。
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
// maxAlloc的值，根據(jù)平臺(tái)系統(tǒng)的差異而不同，具體計(jì)算方式參照src/runtime/malloc.go
    if overflow || mem > maxAlloc {
        hint = 0
    }

// initialize Hmap
    if h == nil {
        h = new(hmap)
    }
  // 通過(guò)fastrand得到哈希種子
    h.hash0 = fastrand()

    // 根據(jù)輸入的元素個(gè)數(shù)hint，找到能裝下這些元素的B值
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    // 分配初始哈希表
  // 如果B為0，那么buckets字段后續(xù)會(huì)在mapassign方法中l(wèi)azily分配
    if h.B != 0 {
        var nextOverflow *bmap
    // makeBucketArray創(chuàng)建一個(gè)map的底層保存buckets的數(shù)組，它最少會(huì)分配h.B^2的大小。
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
    h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

分配buckets數(shù)組的makeBucketArray函數(shù)

// makeBucket為map創(chuàng)建用于保存buckets的數(shù)組。
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b)
    nbuckets := base
  // 對(duì)于小的b值（小于4），即桶的數(shù)量小于16時(shí)，使用溢出桶的可能性很小。對(duì)于此情況，就避免計(jì)算開銷。
    if b >= 4 {
    // 當(dāng)桶的數(shù)量大于等于16個(gè)時(shí)，正常情況下就會(huì)額外創(chuàng)建2^(b-4)個(gè)溢出桶
        nbuckets += bucketShift(b - 4)
        sz := t.bucket.size * nbuckets
        up := roundupsize(sz)
        if up != sz {
            nbuckets = up / t.bucket.size
        }
    }

 // 這里，dirtyalloc分兩種情況。如果它為nil，則會(huì)分配一個(gè)新的底層數(shù)組。如果它不為nil，則它指向的是曾經(jīng)分配過(guò)的底層數(shù)組，該底層數(shù)組是由之前同樣的t和b參數(shù)通過(guò)makeBucketArray分配的，如果數(shù)組不為空，需要把該數(shù)組之前的數(shù)據(jù)清空并復(fù)用。
    if dirtyalloc == nil {
        buckets = newarray(t.bucket, int(nbuckets))
    } else {
        buckets = dirtyalloc
        size := t.bucket.size * nbuckets
        if t.bucket.ptrdata != 0 {
            memclrHasPointers(buckets, size)
        } else {
            memclrNoHeapPointers(buckets, size)
        }
}

  // 即b大于等于4的情況下，會(huì)預(yù)分配一些溢出桶。
  // 為了把跟蹤這些溢出桶的開銷降至最低，使用了以下約定：
  // 如果預(yù)分配的溢出桶的overflow指針為nil，那么可以通過(guò)指針碰撞（bumping the pointer）獲得更多可用桶。
  // （關(guān)于指針碰撞：假設(shè)內(nèi)存是絕對(duì)規(guī)整的，所有用過(guò)的內(nèi)存都放在一邊，空閑的內(nèi)存放在另一邊，中間放著一個(gè)指針作為分界點(diǎn)的指示器，那所分配內(nèi)存就僅僅是把那個(gè)指針向空閑空間那邊挪動(dòng)一段與對(duì)象大小相等的距離，這種分配方式稱為“指針碰撞”）
  // 對(duì)于最后一個(gè)溢出桶，需要一個(gè)安全的非nil指針指向它。
    if base != nbuckets {
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
        last.setoverflow(t, (*bmap)(buckets))
    }
    return buckets, nextOverflow
}

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

哈希函數(shù)

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

func schedinit() {
    lockInit(&sched.lock, lockRankSched)

    ...

    tracebackinit()
    moduledataverify()
    stackinit()
    mallocinit()
    fastrandinit() // must run before mcommoninit
    mcommoninit(_g_.m, -1)
    cpuinit()       // must run before alginit
    // 這里調(diào)用alginit()
    alginit()       // maps must not be used before this call
    modulesinit()   // provides activeModules
    typelinksinit() // uses maps, activeModules
    itabsinit()     // uses activeModules

    ...

    goargs()
    goenvs()
    parsedebugvars()
    gcinit()

  ...
}

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

func alginit() {
    // Install AES hash algorithms if the instructions needed are present.
    if (GOARCH == "386" || GOARCH == "amd64") &&
        cpu.X86.HasAES && // AESENC
        cpu.X86.HasSSSE3 && // PSHUFB
        cpu.X86.HasSSE41 { // PINSR{D,Q}
        initAlgAES()
        return
    }
    if GOARCH == "arm64" && cpu.ARM64.HasAES {
        initAlgAES()
        return
    }
    getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
    hashkey[0] |= 1 // make sure these numbers are odd
    hashkey[1] |= 1
    hashkey[2] |= 1
    hashkey[3] |= 1
}

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

type maptype struct {
    typ    _type
    key    *_type
    elem   *_type
    bucket *_type
  // hasher的第一個(gè)參數(shù)就是指向key的指針，h.hash0 = fastrand()得到的hash0，就是hasher方法的第二個(gè)參數(shù)。
  // hasher方法返回的就是hash值。
    hasher     func(unsafe.Pointer, uintptr) uintptr
    keysize    uint8  // size of key slot
    elemsize   uint8  // size of elem slot
    bucketsize uint16 // size of bucket
    flags      uint32
}

map操作

假定key經(jīng)過(guò)哈希計(jì)算后得到64bit位的哈希值。如果B=5，buckets數(shù)組的長(zhǎng)度，即桶的數(shù)量是32（2的5次方）。

例如，現(xiàn)要置一key于map中，該key經(jīng)過(guò)哈希后，得到的哈希值如下：

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

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

注意：對(duì)于高低位的選擇，該操作的實(shí)質(zhì)是取余，但是取余開銷很大，在實(shí)際代碼實(shí)現(xiàn)中采用的是位操作。以下是tophash的實(shí)現(xiàn)代碼。

func tophash(hash uintptr) uint8 {
    top := uint8(hash >> (sys.PtrSize*8 - 8))
    if top < minTopHash {
        top += minTopHash
    }
    return top
}

當(dāng)兩個(gè)不同的key落在了同一個(gè)桶中，這時(shí)就發(fā)生了哈希沖突。go的解決方式是鏈地址法：在桶中按照順序?qū)さ降谝粋€(gè)空位，若有位置，則將其置于其中；否則，判斷是否存在溢出桶，若有溢出桶，則去該桶的溢出桶中尋找空位，如果沒有溢出桶，則添加溢出桶，并將其置溢出桶的第一個(gè)空位（非擴(kuò)容的情況）。

上圖中的B值為5，所以桶的數(shù)量為32。通過(guò)哈希函數(shù)計(jì)算出待插入key的哈希值，低5位哈希00110，對(duì)應(yīng)于6號(hào)桶；高8位10010111，十進(jìn)制為151，由于桶中前6個(gè)cell已經(jīng)有正常哈希值填充了(遍歷)，所以將151對(duì)應(yīng)的高位哈希值放置于第7位cell，對(duì)應(yīng)將key和value分別置于相應(yīng)的第七個(gè)空位。

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

查找key

對(duì)于map的元素查找，其源碼實(shí)現(xiàn)如下

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  // 如果開啟了競(jìng)態(tài)檢測(cè) -race
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := funcPC(mapaccess1)
        racereadpc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
  // 如果開啟了memory sanitizer -msan
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
  // 如果map為空或者元素個(gè)數(shù)為0，返回零值
    if h == nil || h.count == 0 {
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return unsafe.Pointer(&zeroVal[0])
    }
  // 注意，這里是按位與操作
  // 當(dāng)h.flags對(duì)應(yīng)的值為hashWriting（代表有其他goroutine正在往map中寫key）時(shí)，那么位計(jì)算的結(jié)果不為0，因此拋出以下錯(cuò)誤。
  // 這也表明，go的map是非并發(fā)安全的
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
  // 不同類型的key，會(huì)使用不同的hash算法，可詳見src/runtime/alg.go中typehash函數(shù)中的邏輯
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B)
  // 按位與操作，找到對(duì)應(yīng)的bucket
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
  // 如果oldbuckets不為空，那么證明map發(fā)生了擴(kuò)容
  // 如果有擴(kuò)容發(fā)生，老的buckets中的數(shù)據(jù)可能還未搬遷至新的buckets里
  // 所以需要先在老的buckets中找
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    // 如果在oldbuckets中tophash[0]的值，為evacuatedX、evacuatedY，evacuatedEmpty其中之一
    // 則evacuated()返回為true，代表搬遷完成。
    // 因此，只有當(dāng)搬遷未完成時(shí)，才會(huì)從此oldbucket中遍歷
        if !evacuated(oldb) {
            b = oldb
        }
    }
  // 取出當(dāng)前key值的tophash值
    top := tophash(hash)
  // 以下是查找的核心邏輯
  // 雙重循環(huán)遍歷：外層循環(huán)是從桶到溢出桶遍歷；內(nèi)層是桶中的cell遍歷
  // 跳出循環(huán)的條件有三種：第一種是已經(jīng)找到key值；第二種是當(dāng)前桶再無(wú)溢出桶；
  // 第三種是當(dāng)前桶中有cell位的tophash值是emptyRest，這個(gè)值在前面解釋過(guò)，它代表此時(shí)的桶后面的cell還未利用，所以無(wú)需再繼續(xù)遍歷。
bucketloop:
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
      // 判斷tophash值是否相等
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
      }
      // 因?yàn)樵赽ucket中key是用連續(xù)的存儲(chǔ)空間存儲(chǔ)的，因此可以通過(guò)bucket地址+數(shù)據(jù)偏移量（bmap結(jié)構(gòu)體的大?。? keysize的大小，得到k的地址
      // 同理，value的地址也是相似的計(jì)算方法，只是再要加上8個(gè)keysize的內(nèi)存地址
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
      // 判斷key是否相等
            if t.key.equal(key, k) {
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return e
            }
        }
    }
  // 所有的bucket都未找到，則返回零值
    return unsafe.Pointer(&zeroVal[0])
}

以下是mapaccess1的查找過(guò)程圖解

map的元素查找，對(duì)應(yīng)go代碼有兩種形式

    // 形式一
    v := m[k]
    // 形式二
    v, ok := m[k]

形式一的代碼實(shí)現(xiàn)，就是上述的mapaccess1方法。此外，在源碼中還有個(gè)mapaccess2方法，它的函數(shù)簽名如下。

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

與mapaccess1相比，mapaccess2多了一個(gè)bool類型的返回值，它代表的是是否在map中找到了對(duì)應(yīng)的key。因?yàn)楹蚼apaccess1基本一致，所以詳細(xì)代碼就不再貼出。

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

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

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

賦值key

對(duì)于寫入key的邏輯，其源碼實(shí)現(xiàn)如下

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  // 如果h是空指針，賦值會(huì)引起panic
  // 例如以下語(yǔ)句
  // var m map[string]int
    // m["k"] = 1
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
  // 如果開啟了競(jìng)態(tài)檢測(cè) -race
    if raceenabled {
        callerpc := getcallerpc()
        pc := funcPC(mapassign)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
  // 如果開啟了memory sanitizer -msan
    if msanenabled {
        msanread(key, t.key.size)
    }
  // 有其他goroutine正在往map中寫key，會(huì)拋出以下錯(cuò)誤
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
  // 通過(guò)key和哈希種子，算出對(duì)應(yīng)哈希值
    hash := t.hasher(key, uintptr(h.hash0))

  // 將flags的值與hashWriting做按位或運(yùn)算
  // 因?yàn)樵诋?dāng)前goroutine可能還未完成key的寫入，再次調(diào)用t.hasher會(huì)發(fā)生panic。
    h.flags ^= hashWriting

    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}

again:
  // bucketMask返回值是2的B次方減1
  // 因此，通過(guò)hash值與bucketMask返回值做按位與操作，返回的在buckets數(shù)組中的第幾號(hào)桶
    bucket := hash & bucketMask(h.B)
  // 如果map正在搬遷（即h.oldbuckets != nil）中,則先進(jìn)行搬遷工作。
    if h.growing() {
        growWork(t, h, bucket)
    }
  // 計(jì)算出上面求出的第幾號(hào)bucket的內(nèi)存位置
  // post = start + bucketNumber * bucketsize
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
    top := tophash(hash)

    var inserti *uint8
    var insertk unsafe.Pointer
    var elem unsafe.Pointer
bucketloop:
    for {
    // 遍歷桶中的8個(gè)cell
        for i := uintptr(0); i < bucketCnt; i++ {
      // 這里分兩種情況，第一種情況是cell位的tophash值和當(dāng)前tophash值不相等
      // 在 b.tophash[i] != top 的情況下
      // 理論上有可能會(huì)是一個(gè)空槽位
      // 一般情況下 map 的槽位分布是這樣的，e 表示 empty:
      // [h0][h1][h2][h3][h4][e][e][e]
      // 但在執(zhí)行過(guò) delete 操作時(shí)，可能會(huì)變成這樣:
      // [h0][h1][e][e][h5][e][e][e]
      // 所以如果再插入的話，會(huì)盡量往前面的位置插
      // [h0][h1][e][e][h5][e][e][e]
      //          ^
      //          ^
      //       這個(gè)位置
      // 所以在循環(huán)的時(shí)候還要順便把前面的空位置先記下來(lái)
      // 因?yàn)橛锌赡茉诤竺鏁?huì)找到相等的key，也可能找不到相等的key
            if b.tophash[i] != top {
        // 如果cell位為空，那么就可以在對(duì)應(yīng)位置進(jìn)行插入
                if isEmpty(b.tophash[i]) && inserti == nil {
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                }
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
      // 第二種情況是cell位的tophash值和當(dāng)前的tophash值相等
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
      // 注意，即使當(dāng)前cell位的tophash值相等，不一定它對(duì)應(yīng)的key也是相等的，所以還要做一個(gè)key值判斷
            if !t.key.equal(key, k) {
                continue
            }
            // 如果已經(jīng)有該key了，就更新它
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
      // 這里獲取到了要插入key對(duì)應(yīng)的value的內(nèi)存地址
      // pos = start + dataOffset + 8*keysize + i*elemsize
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
      // 如果順利到這，就直接跳到done的結(jié)束邏輯中去
            goto done
        }
    // 如果桶中的8個(gè)cell遍歷完，還未找到對(duì)應(yīng)的空cell或覆蓋cell，那么就進(jìn)入它的溢出桶中去遍歷
        ovf := b.overflow(t)
    // 如果連溢出桶中都沒有找到合適的cell，跳出循環(huán)。
        if ovf == nil {
            break
        }
        b = ovf
    }

    // 在已有的桶和溢出桶中都未找到合適的cell供key寫入，那么有可能會(huì)觸發(fā)以下兩種情況
  // 情況一：
  // 判斷當(dāng)前map的裝載因子是否達(dá)到設(shè)定的6.5閾值，或者當(dāng)前map的溢出桶數(shù)量是否過(guò)多。如果存在這兩種情況之一，則進(jìn)行擴(kuò)容操作。
  // hashGrow()實(shí)際并未完成擴(kuò)容，對(duì)哈希表數(shù)據(jù)的搬遷（復(fù)制）操作是通過(guò)growWork()來(lái)完成的。
  // 重新跳入again邏輯，在進(jìn)行完growWork()操作后，再次遍歷新的桶。
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }

  // 情況二：
// 在不滿足情況一的條件下，會(huì)為當(dāng)前桶再新建溢出桶，并將tophash，key插入到新建溢出桶的對(duì)應(yīng)內(nèi)存的0號(hào)位置
    if inserti == nil {
        // all current buckets are full, allocate a new one.
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }

  // 在插入位置存入新的key和value
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectelem() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    typedmemmove(t.key, insertk, key)
    *inserti = top
  // map中的key數(shù)量+1
    h.count++

done:
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting
    if t.indirectelem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    return elem
}

通過(guò)對(duì)mapassign的代碼分析之后，發(fā)現(xiàn)該函數(shù)并沒有將插入key對(duì)應(yīng)的value寫入對(duì)應(yīng)的內(nèi)存，而是返回了value應(yīng)該插入的內(nèi)存地址。為了弄清楚value寫入內(nèi)存的操作是發(fā)生在什么時(shí)候，分析如下map.go代碼。

package main

func main() {
    m := make(map[int]int)
    for i := 0; i < 100; i++ {
        m[i] = 666
    }
}

m[i] = 666對(duì)應(yīng)的匯編代碼

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

賦值的最后一步實(shí)際上是編譯器額外生成的匯編指令來(lái)完成的，可見靠 runtime 有些工作是沒有做完的。所以，在go中，編譯器和 runtime 配合，才能完成一些復(fù)雜的工作。

刪除key

理解了賦值key的邏輯，刪除key的邏輯就比較簡(jiǎn)單了.src/runtime/map.go的mapdelete方法。

根據(jù) key 類型的不同，刪除操作會(huì)被優(yōu)化成更具體的函數(shù)：

uint32 mapdelete_fast32(t *maptype, h *hmap, key uint32)
uint64 mapdelete_fast64(t *maptype, h *hmap, key uint64)
string mapdelete_faststr(t *maptype, h *hmap, ky string)

當(dāng)然，我們只關(guān)心 mapdelete 函數(shù)。它首先會(huì)檢查 h.flags 標(biāo)志，如果發(fā)現(xiàn)寫標(biāo)位是 1，直接 panic，因?yàn)檫@表明有其他協(xié)程同時(shí)在進(jìn)行寫操作。

計(jì)算 key 的哈希，找到落入的 bucket。檢查此 map 如果正在擴(kuò)容的過(guò)程中，直接觸發(fā)一次搬遷操作。

刪除操作同樣是兩層循環(huán)，核心還是找到 key 的具體位置。尋找過(guò)程都是類似的，在 bucket 中挨個(gè) cell 尋找。

找到對(duì)應(yīng)位置后，對(duì) key 或者 value 進(jìn)行“清零”操作：

// 對(duì) key 清零
if t.indirectkey {
    *(*unsafe.Pointer)(k) = nil
} else {
    typedmemclr(t.key, k)
}

// 對(duì) value 清零
if t.indirectvalue {
    *(*unsafe.Pointer)(v) = nil
} else {
    typedmemclr(t.elem, v)
}

最后，將 count 值減 1，將對(duì)應(yīng)位置的 tophash 值置成 Empty。

遍歷map

結(jié)論：迭代 map 的結(jié)果是無(wú)序的

m := make(map[int]int)
for i := 0; i < 10; i++ {
     m[i] = i
}

for k, v := range m {
     fmt.Println(k, v)
}

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

map遍歷的過(guò)程，是按序遍歷bucket，同時(shí)按需遍歷bucket中和其overflow bucket中的cell。但是map在擴(kuò)容后，會(huì)發(fā)生key的搬遷，這造成原來(lái)落在一個(gè)bucket中的key，搬遷后，有可能會(huì)落到其他bucket中了，從這個(gè)角度看，遍歷map的結(jié)果就不可能是按照原來(lái)的順序。

但其實(shí)，go為了保證遍歷map的結(jié)果是無(wú)序的，做了以下事情：map在遍歷時(shí)，并不是從固定的0號(hào)bucket開始遍歷的，每次遍歷，都會(huì)從一個(gè)隨機(jī)值序號(hào)的bucket，再?gòu)钠渲?strong>隨機(jī)的cell開始遍歷。然后再按照桶序遍歷下去，直到回到起始桶結(jié)束。

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

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

底層的函數(shù)調(diào)用關(guān)系：先是調(diào)用 mapiterinit 函數(shù)初始化迭代器，然后循環(huán)調(diào)用 mapiternext 函數(shù)進(jìn)行 map 迭代。

map iter loop

迭代器的結(jié)構(gòu)體定義：

type hiter struct {
 // key 指針
 key         unsafe.Pointer
 // value 指針
 value       unsafe.Pointer
 // map 類型，包含如 key size 大小等
 t           *maptype
 // map header
 h           *hmap
 // 初始化時(shí)指向的 bucket
 buckets     unsafe.Pointer
 // 當(dāng)前遍歷到的 bmap
 bptr        *bmap
 overflow    [2]*[]*bmap
 // 起始遍歷的 bucet 編號(hào)
 startBucket uintptr
 // 遍歷開始時(shí) cell 的編號(hào)（每個(gè) bucket 中有 8 個(gè) cell）
 offset      uint8
 // 是否從頭遍歷了
 wrapped     bool
 // B 的大小
 B           uint8
 // 指示當(dāng)前 cell 序號(hào)
 i           uint8
 // 指向當(dāng)前的 bucket
 bucket      uintptr
 // 因?yàn)閿U(kuò)容，需要檢查的 bucket
 checkBucket uintptr
}

mapiterinit 就是對(duì) hiter 結(jié)構(gòu)體里的字段進(jìn)行初始化賦值操作。

前面已經(jīng)提到過(guò)，即使是對(duì)一個(gè)寫死的 map 進(jìn)行遍歷，每次出來(lái)的結(jié)果也是無(wú)序的。下面我們就可以近距離地觀察他們的實(shí)現(xiàn)了。

// 生成隨機(jī)數(shù)
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
   r += uintptr(fastrand()) << 31
}
// 決定了從哪個(gè)隨機(jī)的bucket開始
it.startBucket = r & bucketMask(h.B)
// 決定了每個(gè)bucket中隨機(jī)的cell的位置
it.offset = uint8(r >> h.B & (bucketCnt - 1))

例如，B = 2，那 uintptr(1)<<h.B - 1 結(jié)果就是 3，低 8 位為 0000 0011，將 r 與之相與，就可以得到一個(gè) 0~3 的 bucket 序號(hào)；bucketCnt - 1 等于 7，低 8 位為 0000 0111，將 r 右移 2 位后，與 7 相與，就可以得到一個(gè) 0~7 號(hào)的 cell。

于是，在 mapiternext 函數(shù)中就會(huì)從 it.startBucket 的 it.offset 號(hào)的 cell 開始遍歷，取出其中的 key 和 value，直到又回到起點(diǎn) bucket，完成遍歷過(guò)程。

源碼部分比較好看懂，尤其是理解了前面注釋的幾段代碼后，再看這部分代碼就沒什么壓力了。所以，接下來(lái)，我將通過(guò)圖形化的方式講解整個(gè)遍歷過(guò)程，希望能夠清晰易懂。

假設(shè)我們有下圖所示的一個(gè) map，起始時(shí) B = 1，有兩個(gè) bucket，后來(lái)觸發(fā)了擴(kuò)容（這里不要深究擴(kuò)容條件，只是一個(gè)設(shè)定），B 變成 2。并且， 1 號(hào) bucket 中的內(nèi)容搬遷到了新的 bucket，1 號(hào)裂變成 1 號(hào)和 3 號(hào)；0 號(hào) bucket 暫未搬遷。老的 bucket 掛在在 *oldbuckets 指針上面，新的 bucket 則掛在 *buckets 指針上面。

map origin

這時(shí)，我們對(duì)此 map 進(jìn)行遍歷。假設(shè)經(jīng)過(guò)初始化后，startBucket = 3，offset = 2。于是，遍歷的起點(diǎn)將是 3 號(hào) bucket 的 2 號(hào) cell，下面這張圖就是開始遍歷時(shí)的狀態(tài)：

map init

標(biāo)紅的表示起始位置，bucket 遍歷順序?yàn)椋? -> 0 -> 1 -> 2。

因?yàn)?3 號(hào) bucket 對(duì)應(yīng)老的 1 號(hào) bucket，因此先檢查老 1 號(hào) bucket 是否已經(jīng)被搬遷過(guò)。判斷方法就是：

func evacuated(b *bmap) bool {
 h := b.tophash[0]
 return h > empty && h < minTopHash
}

如果 b.tophash[0] 的值在標(biāo)志值范圍內(nèi)，即在 (0,4) 區(qū)間里，說(shuō)明已經(jīng)被搬遷過(guò)了。

empty = 0
evacuatedEmpty = 1
evacuatedX = 2
evacuatedY = 3
minTopHash = 4

在本例中，老 1 號(hào) bucket 已經(jīng)被搬遷過(guò)了。所以它的 tophash[0] 值在 (0,4) 范圍內(nèi)，因此只用遍歷新的 3 號(hào) bucket。

依次遍歷 3 號(hào) bucket 的 cell，這時(shí)候會(huì)找到第一個(gè)非空的 key：元素 e。到這里，mapiternext 函數(shù)返回，這時(shí)我們的遍歷結(jié)果僅有一個(gè)元素：

iter res

由于返回的 key 不為空，所以會(huì)繼續(xù)調(diào)用 mapiternext 函數(shù)。

繼續(xù)從上次遍歷到的地方往后遍歷，從新 3 號(hào) overflow bucket 中找到了元素 f 和 元素 g。

遍歷結(jié)果集也因此壯大：

iter res

新 3 號(hào) bucket 遍歷完之后，回到了新 0 號(hào) bucket。0 號(hào) bucket 對(duì)應(yīng)老的 0 號(hào) bucket，經(jīng)檢查，老 0 號(hào) bucket 并未搬遷，因此對(duì)新 0 號(hào) bucket 的遍歷就改為遍歷老 0 號(hào) bucket。那是不是把老 0 號(hào) bucket 中的所有 key 都取出來(lái)呢？

并沒有這么簡(jiǎn)單，回憶一下，老 0 號(hào) bucket 在搬遷后將裂變成 2 個(gè) bucket：新 0 號(hào)、新 2 號(hào)。而我們此時(shí)正在遍歷的只是新 0 號(hào) bucket（注意，遍歷都是遍歷的 *bucket 指針，也就是所謂的新 buckets）。所以，我們只會(huì)取出老 0 號(hào) bucket 中那些在裂變之后，分配到新 0 號(hào) bucket 中的那些 key。

因此，lowbits == 00 的將進(jìn)入遍歷結(jié)果集：

iter res

和之前的流程一樣，繼續(xù)遍歷新 1 號(hào) bucket，發(fā)現(xiàn)老 1 號(hào) bucket 已經(jīng)搬遷，只用遍歷新 1 號(hào) bucket 中現(xiàn)有的元素就可以了。結(jié)果集變成：

iter res

繼續(xù)遍歷新 2 號(hào) bucket，它來(lái)自老 0 號(hào) bucket，因此需要在老 0 號(hào) bucket 中那些會(huì)裂變到新 2 號(hào) bucket 中的 key，也就是 lowbit == 10 的那些 key。

這樣，遍歷結(jié)果集變成：

iter resg

最后，繼續(xù)遍歷到新 3 號(hào) bucket 時(shí)，發(fā)現(xiàn)所有的 bucket 都已經(jīng)遍歷完畢，整個(gè)迭代過(guò)程執(zhí)行完畢。

順便說(shuō)一下，如果碰到 key 是 math.NaN() 這種的，處理方式類似。核心還是要看它被分裂后具體落入哪個(gè) bucket。只不過(guò)只用看它 top hash 的最低位。如果 top hash 的最低位是 0 ，分配到 X part；如果是 1 ，則分配到 Y part。據(jù)此決定是否取出 key，放到遍歷結(jié)果集里。

map 遍歷的核心在于理解 2 倍擴(kuò)容時(shí)，老 bucket 會(huì)分裂到 2 個(gè)新 bucket 中去。而遍歷操作，會(huì)按照新 bucket 的序號(hào)順序進(jìn)行，碰到老 bucket 未搬遷的情況時(shí)，要在老 bucket 中找到將來(lái)要搬遷到新 bucket 來(lái)的 key。

map擴(kuò)容

在文中講解裝載因子時(shí)，我們提到裝載因子是決定哈希表是否進(jìn)行擴(kuò)容的關(guān)鍵指標(biāo)。在go的map擴(kuò)容中，除了裝載因子會(huì)決定是否需要擴(kuò)容，溢出桶的數(shù)量也是擴(kuò)容的另一關(guān)鍵指標(biāo)。

為了保證訪問(wèn)效率，當(dāng)map將要添加、修改或刪除key時(shí)，都會(huì)檢查是否需要擴(kuò)容，擴(kuò)容實(shí)際上是以空間換時(shí)間的手段。在之前源碼mapassign中，其實(shí)已經(jīng)注釋map擴(kuò)容條件，主要是兩點(diǎn):

1. 判斷已經(jīng)達(dá)到裝載因子的臨界點(diǎn)，即元素個(gè)數(shù) >= 桶（bucket）總數(shù) * 6.5，這時(shí)候說(shuō)明大部分的桶可能都快滿了（即平均每個(gè)桶存儲(chǔ)的鍵值對(duì)達(dá)到6.5個(gè)），如果插入新元素，有大概率需要掛在溢出桶（overflow bucket）上。

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

2. 判斷溢出桶是否太多，當(dāng)桶總數(shù) < 2 ^ 15 時(shí)，如果溢出桶總數(shù) >= 桶總數(shù)，則認(rèn)為溢出桶過(guò)多。當(dāng)桶總數(shù) >= 2 ^ 15 時(shí)，直接與 2 ^ 15 比較，當(dāng)溢出桶總數(shù) >= 2 ^ 15 時(shí)，即認(rèn)為溢出桶太多了。

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

對(duì)于第2點(diǎn)，其實(shí)算是對(duì)第 1 點(diǎn)的補(bǔ)充。因?yàn)樵谘b載因子比較小的情況下，有可能 map 的查找和插入效率也很低，而第 1 點(diǎn)識(shí)別不出來(lái)這種情況。表面現(xiàn)象就是計(jì)算裝載因子的分子比較小，即 map 里元素總數(shù)少，但是桶數(shù)量多（真實(shí)分配的桶數(shù)量多，包括大量的溢出桶）。

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

image

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

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

• 針對(duì) 1，將 B + 1，新建一個(gè)buckets數(shù)組，新的buckets大小是原來(lái)的2倍，然后舊buckets數(shù)據(jù)搬遷到新的buckets。該方法我們稱之為增量擴(kuò)容。
• 針對(duì) 2，并不擴(kuò)大容量，buckets數(shù)量維持不變，重新做一遍類似增量擴(kuò)容的搬遷動(dòng)作，把松散的鍵值對(duì)重新排列一次，以使bucket的使用率更高，進(jìn)而保證更快的存取。該方法我們稱之為等量擴(kuò)容。

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

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

hashGrow()函數(shù)

func hashGrow(t *maptype, h *hmap) {
  // 如果達(dá)到條件 1，那么將B值加1，相當(dāng)于是原來(lái)的2倍
  // 否則對(duì)應(yīng)條件 2，進(jìn)行等量擴(kuò)容，所以 B 不變
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
  // 記錄老的buckets
    oldbuckets := h.buckets
  // 申請(qǐng)新的buckets空間
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
  // 注意&^ 運(yùn)算符，這塊代碼的邏輯是轉(zhuǎn)移標(biāo)志位
    flags := h.flags &^ (iterator | oldIterator)
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }
    // 提交grow (atomic wrt gc)
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
  // 搬遷進(jìn)度為0
    h.nevacuate = 0
  // overflow buckets 數(shù)為0
    h.noverflow = 0

  // 如果發(fā)現(xiàn)hmap是通過(guò)extra字段 來(lái)存儲(chǔ) overflow buckets時(shí)
    if h.extra != nil && h.extra.overflow != nil {
        if h.extra.oldoverflow != nil {
            throw("oldoverflow is not nil")
        }
        h.extra.oldoverflow = h.extra.overflow
        h.extra.overflow = nil
    }
    if nextOverflow != nil {
        if h.extra == nil {
            h.extra = new(mapextra)
        }
        h.extra.nextOverflow = nextOverflow
    }
}

主要是申請(qǐng)到了新的 buckets 空間，把相關(guān)的標(biāo)志位都進(jìn)行了處理：例如標(biāo)志 nevacuate 被置為 0， 表示當(dāng)前搬遷進(jìn)度為 0。

值得一說(shuō)的是對(duì) h.flags 的處理：

flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
    flags |= oldIterator
}

這里得先說(shuō)下運(yùn)算符：&^。這叫按位置 0運(yùn)算符。例如：

x = 01010011
y = 01010100
z = x &^ y = 00000011

如果 y bit 位為 1，那么結(jié)果 z 對(duì)應(yīng) bit 位就為 0，否則 z 對(duì)應(yīng) bit 位就和 x 對(duì)應(yīng) bit 位的值相同。

所以上面那段對(duì) flags 一頓操作的代碼的意思是：先把 h.flags 中 iterator 和 oldIterator 對(duì)應(yīng)位清 0，然后如果發(fā)現(xiàn) iterator 位為 1，那就把它轉(zhuǎn)接到 oldIterator 位，使得 oldIterator 標(biāo)志位變成 1。潛臺(tái)詞就是：buckets 現(xiàn)在掛到了 oldBuckets 名下了，對(duì)應(yīng)的標(biāo)志位也轉(zhuǎn)接過(guò)去吧。

幾個(gè)標(biāo)志位如下：

// 可能有迭代器使用 buckets
iterator     = 1
// 可能有迭代器使用 oldbuckets
oldIterator  = 2
// 有協(xié)程正在向 map 中寫入 key
hashWriting  = 4
// 等量擴(kuò)容（對(duì)應(yīng)條件 2）
sameSizeGrow = 8

growWork()函數(shù)

func growWork(t *maptype, h *hmap, bucket uintptr) {
  // 為了確認(rèn)搬遷的 bucket 是我們正在使用的 bucket
  // 即如果當(dāng)前key映射到老的bucket1，那么就搬遷該bucket1。
    evacuate(t, h, bucket&h.oldbucketmask())

    // 如果還未完成擴(kuò)容工作，則再搬遷一個(gè)bucket。
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

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

在講解該邏輯之前，需要讀者先理解以下兩個(gè)知識(shí)點(diǎn)。

• 知識(shí)點(diǎn)1：bucket序號(hào)的變化

前面講到，增量擴(kuò)容（條件1）和等量擴(kuò)容（條件2）都需要進(jìn)行bucket的搬遷工作。對(duì)于等量擴(kuò)容而言，由于buckets的數(shù)量不變，因此可以按照序號(hào)來(lái)搬遷。例如老的的0號(hào)bucket，仍然搬至新的0號(hào)bucket中。

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

因此，在增量擴(kuò)容中，某個(gè) key 在搬遷前后 bucket 序號(hào)可能和原來(lái)相等，也可能是相比原來(lái)加上 2^B（原來(lái)的 B 值），取決于低 hash 值第倒數(shù)第B+1位是 0 還是 1。

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

• 知識(shí)點(diǎn)2：確定搬遷區(qū)間

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

這里留一個(gè)問(wèn)題：為什么確定key落在哪個(gè)區(qū)間很重要？

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

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

evacuate()函數(shù)

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
  // 首先定位老的bucket的地址
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  // newbit代表擴(kuò)容之前老的bucket個(gè)數(shù)
    newbit := h.noldbuckets()
  // 判斷該bucket是否已經(jīng)被搬遷
    if !evacuated(b) {
    // 官方TODO，后續(xù)版本也許會(huì)實(shí)現(xiàn)
        // TODO: reuse overflow buckets instead of using new ones, if there
        // is no iterator using the old buckets.  (If !oldIterator.)

    // xy 包含了高低區(qū)間的搬遷目的地內(nèi)存信息
    // x.b 是對(duì)應(yīng)的搬遷目的桶
    // x.k 是指向?qū)?yīng)目的桶中存儲(chǔ)當(dāng)前key的內(nèi)存地址
    // x.e 是指向?qū)?yīng)目的桶中存儲(chǔ)當(dāng)前value的內(nèi)存地址
        var xy [2]evacDst
        x := &xy[0]
        x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
        x.k = add(unsafe.Pointer(x.b), dataOffset)
        x.e = add(x.k, bucketCnt*uintptr(t.keysize))

    // 只有當(dāng)增量擴(kuò)容時(shí)才計(jì)算bucket y的相關(guān)信息（和后續(xù)計(jì)算useY相呼應(yīng)）
        if !h.sameSizeGrow() {
            y := &xy[1]
            y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
            y.k = add(unsafe.Pointer(y.b), dataOffset)
            y.e = add(y.k, bucketCnt*uintptr(t.keysize))
        }

    // evacuate 函數(shù)每次只完成一個(gè) bucket 的搬遷工作，因此要遍歷完此 bucket 的所有的 cell，將有值的 cell copy 到新的地方。
    // bucket 還會(huì)鏈接 overflow bucket，它們同樣需要搬遷。
    // 因此同樣會(huì)有 2 層循環(huán)，外層遍歷 bucket 和 overflow bucket，內(nèi)層遍歷 bucket 的所有 cell。

    // 遍歷當(dāng)前桶bucket和其之后的溢出桶overflow bucket
    // 注意：初始的b是待搬遷的老bucket
        for ; b != nil; b = b.overflow(t) {
            k := add(unsafe.Pointer(b), dataOffset)
            e := add(k, bucketCnt*uintptr(t.keysize))
      // 遍歷桶中的cell，i，k，e分別用于對(duì)應(yīng)tophash，key和value
            for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
                top := b.tophash[i]
        // 如果當(dāng)前cell的tophash值是emptyOne或者emptyRest，則代表此cell沒有key。并將其標(biāo)記為evacuatedEmpty，表示它“已經(jīng)被搬遷”。
                if isEmpty(top) {
                    b.tophash[i] = evacuatedEmpty
                    continue
                }
        // 正常不會(huì)出現(xiàn)這種情況
        // 未被搬遷的 cell 只可能是emptyOne、emptyRest或是正常的 top hash（大于等于 minTopHash）
                if top < minTopHash {
                    throw("bad map state")
                }
                k2 := k
        // 如果 key 是指針，則解引用
                if t.indirectkey() {
                    k2 = *((*unsafe.Pointer)(k2))
                }
                var useY uint8
        // 如果是增量擴(kuò)容
                if !h.sameSizeGrow() {
          // 計(jì)算哈希值，判斷當(dāng)前key和vale是要被搬遷到bucket x還是bucket y
                    hash := t.hasher(k2, uintptr(h.hash0))
                    if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
            // 有一個(gè)特殊情況：有一種 key，每次對(duì)它計(jì)算 hash，得到的結(jié)果都不一樣。
            // 這個(gè) key 就是 math.NaN() 的結(jié)果，它的含義是 not a number，類型是 float64。
            // 當(dāng)它作為 map 的 key時(shí)，會(huì)遇到一個(gè)問(wèn)題：再次計(jì)算它的哈希值和它當(dāng)初插入 map 時(shí)的計(jì)算出來(lái)的哈希值不一樣！
            // 這個(gè) key 是永遠(yuǎn)不會(huì)被 Get 操作獲取的！當(dāng)使用 m[math.NaN()] 語(yǔ)句的時(shí)候，是查不出來(lái)結(jié)果的。
            // 這個(gè) key 只有在遍歷整個(gè) map 的時(shí)候，才能被找到。
            // 并且，可以向一個(gè) map 插入多個(gè)數(shù)量的 math.NaN() 作為 key，它們并不會(huì)被互相覆蓋。
            // 當(dāng)搬遷碰到 math.NaN() 的 key 時(shí)，只通過(guò) tophash 的最低位決定分配到 X part 還是 Y part（如果擴(kuò)容后是原來(lái) buckets 數(shù)量的 2 倍）。如果 tophash 的最低位是 0 ，分配到 X part；如果是 1 ，則分配到 Y part。
                        useY = top & 1
                        top = tophash(hash)
          // 對(duì)于正常key，進(jìn)入以下else邏輯  
                    } else {
                        if hash&newbit != 0 {
                            useY = 1
                        }
                    }
                }

                if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
                    throw("bad evacuatedN")
                }

        // evacuatedX + 1 == evacuatedY
                b.tophash[i] = evacuatedX + useY
        // useY要么為0，要么為1。這里就是選取在bucket x的起始內(nèi)存位置，或者選擇在bucket y的起始內(nèi)存位置（只有增量同步才會(huì)有這個(gè)選擇可能）。
                dst := &xy[useY]

        // 如果目的地的桶已經(jīng)裝滿了（8個(gè)cell），那么需要新建一個(gè)溢出桶，繼續(xù)搬遷到溢出桶上去。
                if dst.i == bucketCnt {
                    dst.b = h.newoverflow(t, dst.b)
                    dst.i = 0
                    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
                    dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
                }
                dst.b.tophash[dst.i&(bucketCnt-1)] = top
        // 如果待搬遷的key是指針，則復(fù)制指針過(guò)去
                if t.indirectkey() {
                    *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
        // 如果待搬遷的key是值，則復(fù)制值過(guò)去  
                } else {
                    typedmemmove(t.key, dst.k, k) // copy elem
                }
        // value和key同理
                if t.indirectelem() {
                    *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
                } else {
                    typedmemmove(t.elem, dst.e, e)
                }
        // 將當(dāng)前搬遷目的桶的記錄key/value的索引值（也可以理解為cell的索引值）加一
                dst.i++
        // 由于桶的內(nèi)存布局中在最后還有overflow的指針，多以這里不用擔(dān)心更新有可能會(huì)超出key和value數(shù)組的指針地址。
                dst.k = add(dst.k, uintptr(t.keysize))
                dst.e = add(dst.e, uintptr(t.elemsize))
            }
        }
    // 如果沒有協(xié)程在使用老的桶，就對(duì)老的桶進(jìn)行清理，用于幫助gc
        if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
            b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
      // 只清除bucket 的 key,value 部分，保留 top hash 部分，指示搬遷狀態(tài)
            ptr := add(b, dataOffset)
            n := uintptr(t.bucketsize) - dataOffset
            memclrHasPointers(ptr, n)
        }
    }

  // 用于更新搬遷進(jìn)度
    if oldbucket == h.nevacuate {
        advanceEvacuationMark(h, t, newbit)
    }
}

func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
  // 搬遷桶的進(jìn)度加一
    h.nevacuate++
  // 實(shí)驗(yàn)表明，1024至少會(huì)比newbit高出一個(gè)數(shù)量級(jí)（newbit代表擴(kuò)容之前老的bucket個(gè)數(shù)）。所以，用當(dāng)前進(jìn)度加上1024用于確保O(1)行為。
    stop := h.nevacuate + 1024
    if stop > newbit {
        stop = newbit
    }
  // 計(jì)算已經(jīng)搬遷完的桶數(shù)
    for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
        h.nevacuate++
    }
  // 如果h.nevacuate == newbit，則代表所有的桶都已經(jīng)搬遷完畢
    if h.nevacuate == newbit {
    // 搬遷完畢，所以指向老的buckets的指針置為nil
        h.oldbuckets = nil
    // 在講解hmap的結(jié)構(gòu)中，有過(guò)說(shuō)明。如果key和value均不包含指針，則都可以inline。
    // 那么保存它們的buckets數(shù)組其實(shí)是掛在hmap.extra中的。所以，這種情況下，其實(shí)我們是搬遷的extra的buckets數(shù)組。
    // 因此，在這種情況下，需要在搬遷完畢后，將hmap.extra.oldoverflow指針置為nil。
        if h.extra != nil {
            h.extra.oldoverflow = nil
        }
    // 最后，清除正在擴(kuò)容的標(biāo)志位，擴(kuò)容完畢。
        h.flags &^= sameSizeGrow
    }
}

代碼比較長(zhǎng)，但是文中注釋已經(jīng)比較清晰了，如果對(duì)map的擴(kuò)容還不清楚，可以參見以下圖解。

• 等量擴(kuò)容
  擴(kuò)容前，B = 2，共有 4 個(gè) buckets，lowbits 表示 hash 值的低位。假設(shè)我們不關(guān)注其他 buckets 情況，專注在 2 號(hào) bucket。并且假設(shè) overflow 太多，觸發(fā)了等量擴(kuò)容（對(duì)應(yīng)于前面的條件 2）。

擴(kuò)容前

擴(kuò)容完成后，overflow bucket 消失了，key 都集中到了一個(gè) bucket，更為緊湊了，提高了查找的效率。

same size 擴(kuò)容

• 增量擴(kuò)容

  
  
  增量擴(kuò)容

針對(duì)上圖的map，其B為3，所以原始buckets數(shù)組為8。當(dāng)map元素?cái)?shù)變多，加載因子超過(guò)6.5，所以引起了增量擴(kuò)容。

以3號(hào)bucket為例，可以看到，由于B值加1，所以在新選取桶時(shí)，需要取低4位哈希值，這樣就會(huì)造成cell會(huì)被搬遷到新buckets數(shù)組中不同的桶（3號(hào)或11號(hào)桶）中去。注意，在一個(gè)桶中，搬遷cell的工作是有序的：它們是依序填進(jìn)對(duì)應(yīng)新桶的cell中去的。

當(dāng)然，實(shí)際情況中3號(hào)桶很可能還有溢出桶，在這里為了簡(jiǎn)化繪圖，假設(shè)3號(hào)桶沒有溢出桶，如果有溢出桶，則相應(yīng)地添加到新的3號(hào)桶和11號(hào)桶中即可，如果對(duì)應(yīng)的3號(hào)和11號(hào)桶均裝滿，則給新的桶添加溢出桶來(lái)裝載。

增量擴(kuò)容

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

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

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

總結(jié)

Go語(yǔ)言的map，底層是哈希表實(shí)現(xiàn)的，通過(guò)鏈地址法解決哈希沖突，它依賴的核心數(shù)據(jù)結(jié)構(gòu)是數(shù)組加鏈表。

map中定義了2的B次方個(gè)桶，每個(gè)桶中能夠容納8個(gè)key。根據(jù)key的不同哈希值，將其散落到不同的桶中。哈希值的低位（哈希值的后B個(gè)bit位）決定桶序號(hào)，高位（哈希值的前8個(gè)bit位）標(biāo)識(shí)同一個(gè)桶中的不同 key。

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

擴(kuò)容分為增量擴(kuò)容和等量擴(kuò)容。增量擴(kuò)容，會(huì)增加桶的個(gè)數(shù)（增加一倍），把原來(lái)一個(gè)桶中的 keys 被重新分配到兩個(gè)桶中。等量擴(kuò)容，不會(huì)更改桶的個(gè)數(shù)，只是會(huì)將桶中的數(shù)據(jù)變得緊湊。不管是增量擴(kuò)容還是等量擴(kuò)容，都需要?jiǎng)?chuàng)建新的桶數(shù)組，并不是原地操作的。

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