本文目錄如下掰曾，閱讀本文后水孩，將一網(wǎng)打盡下面Golang Map相關(guān)面試題

面試題

1. map的底層實現(xiàn)原理
2. 為什么遍歷map是無序的邪铲？
3. 如何實現(xiàn)有序遍歷map疲憋？
4. 為什么Go map是非線程安全的望拖？
5. 線程安全的map如何實現(xiàn)?
6. Go sync.map 和原生 map 誰的性能好渺尘，為什么？
7. 為什么 Go map 的負載因子是 6.5说敏？
8. map擴容策略是什么?

實現(xiàn)原理

Go中的map是一個指針鸥跟，占用8個字節(jié)，指向hmap結(jié)構(gòu)體; 源碼src/runtime/map.go中可以看到map的底層結(jié)構(gòu)

每個map的底層結(jié)構(gòu)是hmap盔沫，hmap包含若干個結(jié)構(gòu)為bmap的bucket數(shù)組医咨。每個bucket底層都采用鏈表結(jié)構(gòu)。接下來架诞，我們來詳細看下map的結(jié)構(gòu)

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

// A header for a Go map.
type hmap struct {
    count     int 
    // 代表哈希表中的元素個數(shù)拟淮，調(diào)用len(map)時，返回的就是該字段值谴忧。
    flags     uint8 
    // 狀態(tài)標志很泊，下文常量中會解釋四種狀態(tài)位含義。
    B         uint8  
    // buckets（桶）的對數(shù)log_2
    // 如果B=5沾谓，則buckets數(shù)組的長度 = 2^5=32委造，意味著有32個桶
    noverflow uint16 
    // 溢出桶的大概數(shù)量
    hash0     uint32 
    // 哈希種子

    buckets    unsafe.Pointer 
    // 指向buckets數(shù)組的指針，數(shù)組大小為2^B均驶，如果元素個數(shù)為0昏兆，它為nil。
    oldbuckets unsafe.Pointer 
    // 如果發(fā)生擴容妇穴，oldbuckets是指向老的buckets數(shù)組的指針爬虱，老的buckets數(shù)組大小是新的buckets的1/2;非擴容狀態(tài)下隶债，它為nil。
    nevacuate  uintptr        
    // 表示擴容進度饮潦，小于此地址的buckets代表已搬遷完成燃异。

    extra *mapextra 
    // 這個字段是為了優(yōu)化GC掃描而設計的。當key和value均不包含指針继蜡，并且都可以inline時使用回俐。extra是指向mapextra類型的指針。
 }

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

bmap 就是我們常說的“桶”稀并，一個桶里面會最多裝 8 個 key仅颇，這些 key 之所以會落入同一個桶，是因為它們經(jīng)過哈希計算后碘举，哈希結(jié)果是“一類”的忘瓦，關(guān)于key的定位我們在map的查詢和插入中詳細說明。在桶內(nèi)引颈，又會根據(jù) key 計算出來的 hash 值的高 8 位來決定 key 到底落入桶內(nèi)的哪個位置（一個桶內(nèi)最多有8個位置)耕皮。

// A bucket for a Go map.
type bmap struct {
    tophash [bucketCnt]uint8        
    // len為8的數(shù)組
    // 用來快速定位key是否在這個bmap中
    // 桶的槽位數(shù)組，一個桶最多8個槽位蝙场，如果key所在的槽位在tophash中凌停，則代表該key在這個桶中
}
//底層定義的常量 
const (
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits
    // 一個桶最多8個位置
）

但這只是表面(src/runtime/hashmap.go)的結(jié)構(gòu)，編譯期間會給它加料售滤，動態(tài)地創(chuàng)建一個新的結(jié)構(gòu)：

type bmap struct {
  topbits  [8]uint8
  keys     [8]keytype
  values   [8]valuetype
  pad      uintptr
  overflow uintptr
  // 溢出桶
}

bucket內(nèi)存數(shù)據(jù)結(jié)構(gòu)可視化如下：

注意到 key 和 value 是各自放在一起的罚拟，并不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding字段完箩，節(jié)省內(nèi)存空間赐俗。

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

當 map 的 key 和 value 都不是指針，并且 size 都小于 128 字節(jié)的情況下弊知，會把 bmap 標記為不含指針阻逮，這樣可以避免 gc 時掃描整個 hmap。但是秩彤，我們看 bmap 其實有一個 overflow 的字段夺鲜，是指針類型的，破壞了 bmap 不含指針的設想呐舔，這時會把 overflow 移動到 extra 字段來币励。

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

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

主要特性

引用類型

map是個指針，底層指向hmap，所以是個引用類型

golang 有三個常用的高級類型slice仅胞、map每辟、channel, 它們都是引用類型，當引用類型作為函數(shù)參數(shù)時干旧，可能會修改原內(nèi)容數(shù)據(jù)渠欺。

golang 中沒有引用傳遞，只有值和指針傳遞椎眯。所以 map 作為函數(shù)實參傳遞時本質(zhì)上也是值傳遞挠将，只不過因為 map 底層數(shù)據(jù)結(jié)構(gòu)是通過指針指向?qū)嶋H的元素存儲空間，在被調(diào)函數(shù)中修改 map编整，對調(diào)用者同樣可見舔稀，所以 map 作為函數(shù)實參傳遞時表現(xiàn)出了引用傳遞的效果。

因此掌测，傳遞 map 時内贮，如果想修改map的內(nèi)容而不是map本身，函數(shù)形參無需使用指針

func TestSliceFn(t *testing.T) {
    m := map[string]int{}
    t.Log(m, len(m))
    // map[a:1]
    mapAppend(m, "b", 2)
    t.Log(m, len(m))
    // map[a:1 b:2] 2
}

func mapAppend(m map[string]int, key string, val int) {
    m[key] = val
}

共享存儲空間

map 底層數(shù)據(jù)結(jié)構(gòu)是通過指針指向?qū)嶋H的元素存儲空間 汞斧，這種情況下夜郁，對其中一個map的更改，會影響到其他map

func TestMapShareMemory(t *testing.T) {
    m1 := map[string]int{}
    m2 := m1
    m1["a"] = 1
    t.Log(m1, len(m1))
    // map[a:1] 1
    t.Log(m2, len(m2))
    // map[a:1]
}

遍歷順序隨機

map 在沒有被修改的情況下粘勒，使用 range 多次遍歷 map 時輸出的 key 和 value 的順序可能不同竞端。這是 Go 語言的設計者們有意為之，在每次 range 時的順序被隨機化仲义，旨在提示開發(fā)者們婶熬，Go 底層實現(xiàn)并不保證 map 遍歷順序穩(wěn)定剑勾，請大家不要依賴 range 遍歷結(jié)果順序埃撵。

map 本身是無序的，且遍歷時順序還會被隨機化虽另，如果想順序遍歷 map暂刘，需要對 map key 先排序，再按照 key 的順序遍歷 map捂刺。

func TestMapRange(t *testing.T) {
    m := map[int]string{1: "a", 2: "b", 3: "c"}
    t.Log("first range:")
    // 默認無序遍歷
    for i, v := range m {
        t.Logf("m[%v]=%v ", i, v)
    }
    t.Log("\nsecond range:")
    for i, v := range m {
        t.Logf("m[%v]=%v ", i, v)
    }

    // 實現(xiàn)有序遍歷
    var sl []int
    // 把 key 單獨取出放到切片
    for k := range m {
        sl = append(sl, k)
    }
    // 排序切片
    sort.Ints(sl)
    // 以切片中的 key 順序遍歷 map 就是有序的了
    for _, k := range sl {
        t.Log(k, m[k])
    }
}

非線程安全

map默認是并發(fā)不安全的谣拣，原因如下：

Go 官方在經(jīng)過了長時間的討論后，認為 Go map 更應適配典型使用場景（不需要從多個 goroutine 中進行安全訪問）族展，而不是為了小部分情況（并發(fā)訪問）森缠，導致大部分程序付出加鎖代價（性能），決定了不支持仪缸。

場景: 2個協(xié)程同時讀和寫贵涵，以下程序會出現(xiàn)致命錯誤：fatal error: concurrent map writes

func main() {
    
    m := make(map[int]int)
    go func() {
                    //開一個協(xié)程寫map
        for i := 0; i < 10000; i++ {
    
            m[i] = i
        }
    }()

    go func() {
                    //開一個協(xié)程讀map
        for i := 0; i < 10000; i++ {
    
            fmt.Println(m[i])
        }
    }()

    //time.Sleep(time.Second * 20)
    for {
    
        ;
    }
}

如果想實現(xiàn)map線程安全，有兩種方式：

方式一：使用讀寫鎖 map + sync.RWMutex

func BenchmarkMapConcurrencySafeByMutex(b *testing.B) {
    var lock sync.Mutex //互斥鎖
    m := make(map[int]int, 0)
    var wg sync.WaitGroup
    for i := 0; i < b.N; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            lock.Lock()
            defer lock.Unlock()
            m[i] = i
        }(i)
    }
    wg.Wait()
    b.Log(len(m), b.N)
}

方式二：使用golang提供的 sync.Map

sync.map是用讀寫分離實現(xiàn)的，其思想是空間換時間宾茂。和map+RWLock的實現(xiàn)方式相比瓷马，它做了一些優(yōu)化：可以無鎖訪問read map，而且會優(yōu)先操作read map跨晴，倘若只操作read map就可以滿足要求(增刪改查遍歷)欧聘，那就不用去操作write map(它的讀寫都要加鎖)，所以在某些特定場景中它發(fā)生鎖競爭的頻率會遠遠小于map+RWLock的實現(xiàn)方式端盆。

func BenchmarkMapConcurrencySafeBySyncMap(b *testing.B) {   var m sync.Map  var wg sync.WaitGroup   for i := 0; i < b.N; i++ {      wg.Add(1)       go func(i int) {            defer wg.Done()         m.Store(i, i)       }(i)    }   wg.Wait()   b.Log(b.N)}

哈希沖突

golang中map是一個kv對集合怀骤。底層使用hash table，用鏈表來解決沖突 爱谁，出現(xiàn)沖突時晒喷，不是每一個key都申請一個結(jié)構(gòu)通過鏈表串起來，而是以bmap為最小粒度掛載访敌，一個bmap可以放8個kv凉敲。在哈希函數(shù)的選擇上，會在程序啟動時寺旺，檢測 cpu 是否支持 aes爷抓，如果支持，則使用 aes hash阻塑，否則使用 memhash蓝撇。

常用操作

創(chuàng)建

map有3鐘初始化方式，一般通過make方式創(chuàng)建

func TestMapInit(t *testing.T) {    // 初始化方式1：直接聲明  // var m1 map[string]int    // m1["a"] = 1  // t.Log(m1, unsafe.Sizeof(m1)) // panic: assignment to entry in nil map    // 向 map 寫入要非常小心陈莽，因為向未初始化的 map（值為 nil）寫入會引發(fā) panic渤昌，所以向 map 寫入時需先進行判空操作    // 初始化方式2：使用字面量 m2 := map[string]int{}  m2["a"] = 2 t.Log(m2, unsafe.Sizeof(m2))    // map[a:2] 8   // 初始化方式3：使用make創(chuàng)建  m3 := make(map[string]int)  m3["a"] = 3 t.Log(m3, unsafe.Sizeof(m3))    // map[a:3] 8}

map的創(chuàng)建通過生成匯編碼可以知道，make創(chuàng)建map時調(diào)用的底層函數(shù)是runtime.makemap走搁。如果你的map初始容量小于等于8會發(fā)現(xiàn)走的是runtime.fastrand是因為容量小于8時不需要生成多個桶独柑，一個桶的容量就可以滿足

創(chuàng)建流程

makemap函數(shù)會通過 fastrand 創(chuàng)建一個隨機的哈希種子，然后根據(jù)傳入的 hint 計算出需要的最小需要的桶的數(shù)量私植，最后再使用 makeBucketArray創(chuàng)建用于保存桶的數(shù)組忌栅，這個方法其實就是根據(jù)傳入的 B 計算出的需要創(chuàng)建的桶數(shù)量在內(nèi)存中分配一片連續(xù)的空間用于存儲數(shù)據(jù)，在創(chuàng)建桶的過程中還會額外創(chuàng)建一些用于保存溢出數(shù)據(jù)的桶曲稼，數(shù)量是 2^(B-4) 個索绪。初始化完成返回hmap指針。

計算B的初始值

找到一個 B贫悄，使得 map 的裝載因子在正常范圍內(nèi)

B := uint8(0)for overLoadFactor(hint, B) {  B++}h.B = B// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.func overLoadFactor(count int, B uint8) bool {   return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}

查找

Go 語言中讀取 map 有兩種語法：帶 comma 和 不帶 comma瑞驱。當要查詢的 key 不在 map 里，帶 comma 的用法會返回一個 bool 型變量提示 key 是否在 map 中窄坦；而不帶 comma 的語句則會返回一個 value 類型的零值唤反。如果 value 是 int 型就會返回 0晰筛，如果 value 是 string 類型，就會返回空字符串拴袭。

// 不帶 comma 用法value := m["name"]fmt.Printf("value:%s", value)// 帶 comma 用法value, ok := m["name"]if ok {    fmt.Printf("value:%s", value)}

map的查找通過生成匯編碼可以知道读第，根據(jù) key 的不同類型，編譯器會將查找函數(shù)用更具體的函數(shù)替換拥刻，以優(yōu)化效率：

查找流程

寫保護監(jiān)測

函數(shù)首先會檢查 map 的標志位 flags怜瞒。如果 flags 的寫標志位此時被置 1 了，說明有其他協(xié)程在執(zhí)行“寫”操作般哼，進而導致程序 panic吴汪。這也說明了 map 對協(xié)程是不安全的。

if h.flags&hashWriting != 0 {   throw("concurrent map read and map write")}

計算hash值

hash := t.hasher(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0))

key經(jīng)過哈希函數(shù)計算后蒸眠，得到的哈希值如下（主流64位機下共 64 個 bit 位）：

 10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

找到hash對應的bucket

m: 桶的個數(shù)

從buckets 通過 hash & m 得到對應的bucket漾橙，如果bucket正在擴容，并且沒有擴容完成楞卡，則從oldbuckets得到對應的bucket

m := bucketMask(h.B)b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))// m個桶對應B個位if c := h.oldbuckets; c != nil {  if !h.sameSizeGrow() {     // 擴容前m是之前的一半   m >>= 1  }  oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))  if !evacuated(oldb) {    b = oldb  }}

計算hash所在桶編號：

用上一步哈希值最后的 5 個 bit 位霜运，也就是 01010，值為 10蒋腮，也就是 10 號桶（范圍是0~31號桶）

遍歷bucket

計算hash所在的槽位:

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

用上一步哈希值哈希值的高8個bit 位淘捡，也就是10010111，轉(zhuǎn)化為十進制池摧，也就是151焦除，在 10 號 bucket 中尋找** tophash 值（HOB hash）為 151* 的 槽位**，即為key所在位置作彤，找到了 2 號槽位膘魄，這樣整個查找過程就結(jié)束了。

img

如果在 bucket 中沒找到竭讳，并且 overflow 不為空创葡，還要繼續(xù)去 overflow bucket 中尋找，直到找到或是所有的 key 槽位都找遍了代咸，包括所有的 overflow bucket蹈丸。

返回key對應的指針

通過上面找到了對應的槽位成黄，這里我們再詳細分析下key/value值是如何獲取的：

// key 定位公式k :=add(unsafe.Pointer(b),dataOffset+i*uintptr(t.keysize))// value 定位公式v:= add(unsafe.Pointer(b),dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))//對于 bmap 起始地址的偏移：dataOffset = unsafe.Offsetof(struct{  b bmap  v int64}{}.v)

bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset呐芥。第 i 個 key 的地址就要在此基礎上跨過 i 個 key 的大小奋岁；而我們又知道思瘟，value 的地址是在所有 key 之后，因此第 i 個 value 的地址還需要加上所有 key 的偏移闻伶。

賦值

通過匯編語言可以看到滨攻，向 map 中插入或者修改 key，最終調(diào)用的是 mapassign 函數(shù)。

實際上插入或修改 key 的語法是一樣的光绕，只不過前者操作的 key 在 map 中不存在女嘲，而后者操作的 key 存在 map 中。

mapassign 有一個系列的函數(shù)诞帐，根據(jù) key 類型的不同欣尼，編譯器會將其優(yōu)化為相應的“快速函數(shù)”。

我們只用研究最一般的賦值函數(shù) mapassign停蕉。

賦值流程

map的賦值會附帶著map的擴容和遷移愕鼓，map的擴容只是將底層數(shù)組擴大了一倍，并沒有進行數(shù)據(jù)的轉(zhuǎn)移慧起，數(shù)據(jù)的轉(zhuǎn)移是在擴容后逐步進行的菇晃，在遷移的過程中每進行一次賦值（access或者delete）會至少做一次遷移工作。

校驗和初始化

1.判斷map是否為nil

2. 判斷是否并發(fā)讀寫 map蚓挤，若是則拋出異常
3. 判斷 buckets 是否為 nil磺送，若是則調(diào)用 newobject 根據(jù)當前 bucket 大小進行分配

遷移

每一次進行賦值/刪除操作時，只要oldbuckets != nil 則認為正在擴容灿意，會做一次遷移工作册着，下面會詳細說下遷移過程

查找&更新

根據(jù)上面查找過程，查找key所在位置脾歧，如果找到則更新甲捏，沒找到則找空位插入即可

擴容

經(jīng)過前面迭代尋找動作，若沒有找到可插入的位置鞭执，意味著需要擴容進行插入司顿，下面會詳細說下擴容過程

刪除

通過匯編語言可以看到，向 map 中刪除 key兄纺，最終調(diào)用的是 mapdelete 函數(shù)

func mapdelete(t \*maptype, h _hmap, key unsafe.Pointer)

刪除的邏輯相對比較簡單大溜，大多函數(shù)在賦值操作中已經(jīng)用到過，核心還是找到 key 的具體位置估脆。尋找過程都是類似的钦奋，在 bucket 中挨個 cell 尋找。找到對應位置后疙赠，對 key 或者 value 進行“清零”操作付材，將 count 值減 1，將對應位置的 tophash 值置成 Empty

e := add(unsafe.Pointer(b), dataOffset+bucketCnt*2*goarch.PtrSize+i*uintptr(t.elemsize))if t.elem.ptrdata != 0 {    memclrHasPointers(e, t.elem.size)} else {   memclrNoHeapPointers(e, t.elem.size)}b.tophash[i] = emptyOne

擴容

擴容時機

再來說觸發(fā) map 擴容的時機：在向 map 插入新 key 的時候圃阳，會進行條件檢測厌衔，符合下面這 2 個條件，就會觸發(fā)擴容：

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    }

1捍岳、裝載因子超過閾值

源碼里定義的閾值是 6.5 (loadFactorNum/loadFactorDen)富寿，是經(jīng)過測試后取出的一個比較合理的因子

我們知道睬隶，每個 bucket 有 8 個空位，在沒有溢出页徐，且所有的桶都裝滿了的情況下苏潜，裝載因子算出來的結(jié)果是 8。因此當裝載因子超過 6.5 時变勇，表明很多 bucket 都快要裝滿了窖贤，查找效率和插入效率都變低了。在這個時候進行擴容是有必要的贰锁。

對于條件 1赃梧，元素太多，而 bucket 數(shù)量太少豌熄，很簡單：將 B 加 1授嘀，bucket 最大數(shù)量(2^B)直接變成原來 bucket 數(shù)量的 2 倍。于是锣险，就有新老 bucket 了蹄皱。注意，這時候元素都在老 bucket 里芯肤，還沒遷移到新的 bucket 來巷折。新 bucket 只是最大數(shù)量變?yōu)樵瓉碜畲髷?shù)量的 2 倍(2^B * 2) 。

2崖咨、overflow 的 bucket 數(shù)量過多

在裝載因子比較小的情況下锻拘，這時候 map 的查找和插入效率也很低，而第 1 點識別不出來這種情況击蹲。表面現(xiàn)象就是計算裝載因子的分子比較小署拟，即 map 里元素總數(shù)少，但是 bucket 數(shù)量多（真實分配的 bucket 數(shù)量多歌豺，包括大量的 overflow bucket）

不難想像造成這種情況的原因：不停地插入推穷、刪除元素。先插入很多元素类咧，導致創(chuàng)建了很多 bucket馒铃，但是裝載因子達不到第 1 點的臨界值，未觸發(fā)擴容來緩解這種情況痕惋。之后区宇，刪除元素降低元素總數(shù)量，再插入很多元素血巍，導致創(chuàng)建很多的 overflow bucket萧锉，但就是不會觸發(fā)第 1 點的規(guī)定珊随，你能拿我怎么辦述寡？overflow bucket 數(shù)量太多柿隙，導致 key 會很分散，查找插入效率低得嚇人鲫凶，因此出臺第 2 點規(guī)定禀崖。這就像是一座空城，房子很多螟炫，但是住戶很少波附，都分散了，找起人來很困難

對于條件 2昼钻，其實元素沒那么多掸屡，但是 overflow bucket 數(shù)特別多，說明很多 bucket 都沒裝滿然评。解決辦法就是開辟一個新 bucket 空間仅财，將老 bucket 中的元素移動到新 bucket，使得同一個 bucket 中的 key 排列地更緊密碗淌。這樣盏求，原來酷麦，在 overflow bucket 中的 key 可以移動到 bucket 中來蝌矛。結(jié)果是節(jié)省空間，提高 bucket 利用率锅棕，map 的查找和插入效率自然就會提升纳像。

擴容函數(shù)

func hashGrow(t *maptype, h *hmap) {    bigger := uint8(1)  if !overLoadFactor(h.count+1, h.B) {        bigger = 0      h.flags |= sameSizeGrow }   oldbuckets := h.buckets newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) flags := h.flags &^ (iterator | oldIterator)    if h.flags&iterator != 0 {      flags |= oldIterator    }   // commit the grow (atomic wrt gc)  h.B += bigger   h.flags = flags h.oldbuckets = oldbuckets   h.buckets = newbuckets  h.nevacuate = 0 h.noverflow = 0 if h.extra != nil && h.extra.overflow != nil {      // Promote current overflow buckets to the old generation.      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 }   // the actual copying of the hash table data is done incrementally  // by growWork() and evacuate().}

由于 map 擴容需要將原有的 key/value 重新搬遷到新的內(nèi)存地址荆烈，如果有大量的 key/value 需要搬遷，會非常影響性能竟趾。因此 Go map 的擴容采取了一種稱為“漸進式”的方式耙考，原有的 key 并不會一次性搬遷完畢，每次最多只會搬遷 2 個 bucket潭兽。

上面說的 hashGrow() 函數(shù)實際上并沒有真正地“搬遷”倦始，它只是分配好了新的 buckets，并將老的 buckets 掛到了 oldbuckets 字段上山卦。真正搬遷 buckets 的動作在 growWork() 函數(shù)中鞋邑，而調(diào)用 growWork() 函數(shù)的動作是在 mapassign 和 mapdelete 函數(shù)中。也就是插入或修改账蓉、刪除 key 的時候枚碗，都會嘗試進行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢铸本，具體來說就是檢查 oldbuckets 是否為 nil肮雨。

遷移

遷移時機

如果未遷移完畢，賦值/刪除的時候箱玷，擴容完畢后（預分配內(nèi)存）怨规，不會馬上就進行遷移陌宿。而是采取增量擴容的方式，當有訪問到具體 bukcet 時波丰，才會逐漸的進行遷移（將 oldbucket 遷移到 bucket）

if h.growing() {        growWork(t, h, bucket)}

遷移函數(shù)

func growWork(t *maptype, h *hmap, bucket uintptr) {    // 首先把需要操作的bucket 搬遷    evacuate(t, h, bucket&h.oldbucketmask())     // 再順帶搬遷一個bucket   if h.growing() {        evacuate(t, h, h.nevacuate) }}

nevacuate 標識的是當前的進度壳坪，如果都搬遷完，應該和2^B的長度是一樣的

在evacuate 方法實現(xiàn)是把這個位置對應的bucket掰烟，以及其沖突鏈上的數(shù)據(jù)都轉(zhuǎn)移到新的buckets上爽蝴。

1. 先要判斷當前bucket是不是已經(jīng)轉(zhuǎn)移。 (oldbucket 標識需要搬遷的bucket 對應的位置)

b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))// 判斷if !evacuated(b) {  // 做轉(zhuǎn)移操作}

轉(zhuǎn)移的判斷直接通過tophash 就可以纫骑，判斷tophash中第一個hash值即可

func evacuated(b *bmap) bool {  h := b.tophash[0]  // 這個區(qū)間的flag 均是已被轉(zhuǎn)移  return h > emptyOne && h < minTopHash // 1 ~ 5}

2. 如果沒有被轉(zhuǎn)移蝎亚，那就要遷移數(shù)據(jù)了。數(shù)據(jù)遷移時先馆，可能是遷移到大小相同的buckets上颖对，也可能遷移到2倍大的buckets上。這里xy 都是標記目標遷移位置的標記：x 標識的是遷移到相同的位置磨隘，y 標識的是遷移到2倍大的位置上缤底。我們先看下目標位置的確定：

var xy [2]evacDstx := &xy[0]x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))x.k = add(unsafe.Pointer(x.b), dataOffset)x.v = add(x.k, bucketCnt*uintptr(t.keysize))if !h.sameSizeGrow() {  // 如果是2倍的大小，就得算一次 y 的值  y := &xy[1]  y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))  y.k = add(unsafe.Pointer(y.b), dataOffset)  y.v = add(y.k, bucketCnt*uintptr(t.keysize))}

3. 確定bucket位置后番捂，需要按照kv 一條一條做遷移个唧。

4. 如果當前搬遷的bucket 和 總體搬遷的bucket的位置是一樣的，我們需要更新總體進度的標記 nevacuate

// newbit 是oldbuckets 的長度设预，也是nevacuate 的重點func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {  // 首先更新標記  h.nevacuate++  // 最多查看2^10 個bucket  stop := h.nevacuate + 1024  if stop > newbit {    stop = newbit  }  // 如果沒有搬遷就停止了徙歼，等下次搬遷  for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {    h.nevacuate++  }  // 如果都已經(jīng)搬遷完了，oldbukets 完全搬遷成功鳖枕，清空oldbuckets  if h.nevacuate == newbit {    h.oldbuckets = nil    if h.extra != nil {      h.extra.oldoverflow = nil    }    h.flags &^= sameSizeGrow  }

遍歷

遍歷的過程魄梯，就是按順序遍歷 bucket，同時按順序遍歷 bucket 中的 key宾符。

map遍歷是無序的酿秸，如果想實現(xiàn)有序遍歷，可以先對key進行排序

為什么遍歷 map 是無序的魏烫？

如果發(fā)生過遷移辣苏，key 的位置發(fā)生了重大的變化，有些 key 飛上高枝哄褒，有些 key 則原地不動稀蟋。這樣，遍歷 map 的結(jié)果就不可能按原來的順序了呐赡。

如果就一個寫死的 map，不會向 map 進行插入刪除的操作，按理說每次遍歷這樣的 map 都會返回一個固定順序的 key/value 序列吧萌狂。但是 Go 杜絕了這種做法档玻，因為這樣會給新手程序員帶來誤解，以為這是一定會發(fā)生的事情粥脚，在某些情況下窃肠，可能會釀成大錯包个。

Go 做得更絕刷允，當我們在遍歷 map 時，并不是固定地從 0 號 bucket 開始遍歷碧囊，每次都是從一個**隨機值序號的 bucket 開始遍歷树灶，并且是從這個 bucket 的一個隨機序號的 cell **開始遍歷。這樣糯而，即使你是一個寫死的 map天通，僅僅只是遍歷它，也不太可能會返回一個固定序列的 key/value 對了熄驼。

//runtime.mapiterinit 遍歷時選用初始桶的函數(shù)func mapiterinit(t *maptype, h *hmap, it *hiter) {  ...  it.t = t  it.h = h  it.B = h.B  it.buckets = h.buckets  if t.bucket.kind&kindNoPointers != 0 {    h.createOverflow()    it.overflow = h.extra.overflow    it.oldoverflow = h.extra.oldoverflow  }  r := uintptr(fastrand())  if h.B > 31-bucketCntBits {    r += uintptr(fastrand()) << 31  }  it.startBucket = r & bucketMask(h.B)  it.offset = uint8(r >> h.B & (bucketCnt - 1))  it.bucket = it.startBucket    ...  mapiternext(it)}

總結(jié)

1. map是引用類型
2. map遍歷是無序的
3. map是非線程安全的
4. map的哈希沖突解決方式是鏈表法
5. map的擴容不是一定會新增空間像寒，也有可能是只是做了內(nèi)存整理
6. map的遷移是逐步進行的，在每次賦值時瓜贾，會做至少一次遷移工作
7. map中刪除key诺祸，有可能導致出現(xiàn)很多空的kv，這會導致遷移操作祭芦，如果可以避免筷笨，盡量避免

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！