GO 中map的底層是如何實現(xiàn)的

首先Go 語言采用的是哈希查找表忍弛，并且使用鏈表解決哈希沖突冠桃。

GO的內存模型

先看這一張map原理圖

map

再來看看源碼中map的定義

//src/runtime/map.go  line 115

// A header for a Go map.
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    //
    count     int  //len(map)時，返回的值
    flags     uint8   //表示是否有其他協(xié)程在操作map
    B         uint8    //上圖中[]bmap的''長度'' 2^B
    noverflow uint16  //// 溢出的bucket個數(shù)
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer    //buckets 數(shù)組指針
    oldbuckets unsafe.Pointer  // 擴容的時候用于賦值的buckets數(shù)組
    nevacuate  uintptr       // 搬遷進度

    extra *mapextra   // 用于擴容的指針

    type mapextra struct {
    overflow    *[]*bmap
    oldoverflow *[]*bmap
    nextOverflow *bmap
}

// A bucket for a Go map.
type bmap struct {
    tophash [bucketCnt]uint8        // len為8的數(shù)組
}
//底層定義的常量 
const (
    // Maximum number of key/value pairs a bucket can hold.
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits

}

但這只是表面(src/runtime/hashmap.go)的結構条辟，編譯期間會給它加料媒熊，動態(tài)地創(chuàng)建一個新的結構：

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

bmap 就是我們常說的“桶”，桶里面會最多裝 8 個 key谜酒，這些 key 之所以會落入同一個桶叹俏，是因為它們經過哈希計算后，哈希結果是“一類”的(低位的B位決定bucket)僻族。在桶內粘驰，又會根據 key 計算出來的 hash 值的高 8 位來決定 key 到底落入桶內的哪個位置（一個桶內最多有8個位置）。如上圖所示

bmap 是存放 k-v 的地方鹰贵，我們把視角拉近晴氨，仔細看 bmap 的內部組成康嘉。

上圖就是 bucket 的內存模型碉输， HOBHash 指的就是 top hash。注意到 key 和 value 是各自放在一起的亭珍，并不是 key/value/key/value/... 這樣的形式敷钾。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 字段，節(jié)省內存空間肄梨。

每個 bucket 設計成最多只能放 8 個 key-value 對阻荒，如果有第 9 個 key-value 落入當前的 bucket，那就需要再構建一個 bucket 众羡，通過 overflow 指針連接起來侨赡。

創(chuàng)建map

從語法上來說，創(chuàng)建一個map很簡單（記得key的類型必須為可比較類型）

maps := make(map[string]int)
    maps2 := map[string]int{
        "1":1,
        "2":2,
        "3":3,
    }
    var maps3 map[string]int

通過匯編語言可以看到，實際上底層調用的是 makemap 函數(shù)羊壹，主要做的工作就是初始化 hmap 結構體的各種字段蓖宦，例如計算 B 的大小，設置哈希種子 hash0 等等油猫。

func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap

注意稠茂，這個函數(shù)返回的結果：*hmap，它是一個指針情妖，而我們之前講過的 makeslice 函數(shù)返回的是 Slice 結構體:

func makeslice(et *_type, len, cap int) slice

hash函數(shù)

map 的一個關鍵點在于睬关，哈希函數(shù)的選擇。在程序啟動時，會檢測 cpu 是否支持 aes毅弧，如果支持诞外，則使用 aes hash，否則使用 memhash藐不。這是在函數(shù) alginit() 中完成，位于路徑：src/runtime/alg.go 下秦效。

hash 函數(shù)雏蛮，有加密型和非加密型。加密型的一般用于加密數(shù)據阱州、數(shù)字摘要等挑秉，典型代表就是 md5、sha1苔货、sha256犀概、aes256 這種；非加密型的一般就是查找夜惭。在 map 的應用場景中姻灶，用的是查找。選擇 hash 函數(shù)主要考察的是兩點：性能诈茧、碰撞概率产喉。

key的定位過程

key 經過哈希計算后得到哈希值，共 64 個 bit 位（64位機敢会，32位機就不討論了曾沈，現(xiàn)在主流都是64位機），計算它到底要落在哪個桶時鸥昏，只會用到最后 B 個 bit 位塞俱。還記得前面提到過的 B 嗎？如果 B = 5吏垮，那么桶的數(shù)量障涯，也就是 buckets 數(shù)組的長度是 2^5 = 32罐旗。
例如，現(xiàn)在有一個 key 經過哈希函數(shù)計算后唯蝶，得到的哈希結果是：

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

用最后的 5 個 bit 位尤莺，也就是 01010，值為 10生棍，也就是 10 號桶颤霎。這個操作實際上就是取余操作，但是取余開銷太大涂滴，所以代碼實現(xiàn)上用的位操作代替友酱。
再用哈希值的高 8 位，找到此 key 在 bucket 中的位置柔纵，這是在尋找已有的 key缔杉。最開始桶內還沒有 key，新加入的 key 會找到第一個空位搁料，放入或详。

buckets 編號就是桶編號，當兩個不同的 key 落在同一個桶中郭计，也就是發(fā)生了哈希沖突霸琴。沖突的解決手段是用鏈表法：在 bucket 中，從前往后找到第一個空位昭伸。這樣梧乘，在查找某個 key 時，先找到對應的桶庐杨，再去遍歷 bucket 中的 key选调。

這里參考曹大 github 博客里的一張圖

key定位過程

上圖中，假定 B = 5灵份，所以 bucket 總數(shù)就是 2^5 = 32仁堪。首先計算出待查找 key 的哈希，使用低 5 位 00110填渠，找到對應的 6 號 bucket弦聂，使用高 8 位 10010111，對應十進制 151揭蜒，在 6 號 bucket 中尋找 tophash 值（HOB hash）為 151 的 key横浑，找到了 2 號槽位剔桨，這樣整個查找過程就結束了屉更。

如果在 bucket 中沒找到，并且 overflow 不為空洒缀，還要繼續(xù)去 overflow bucket 中尋找瑰谜，直到找到或是所有的 key 槽位都找遍了欺冀，包括所有的 overflow bucket。

看看key的查找過程

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  //...
  // 如果 h 什么都沒有萨脑，返回零值
  if h == nil || h.count == 0 {
    return unsafe.Pointer(&zeroVal[0])
  }
  // 寫和讀沖突
  if h.flags&hashWriting != 0 {
    throw("concurrent map read and map write")
  }
  // 不同類型 key 使用的 hash 算法在編譯期確定
  alg := t.key.alg
  // 計算哈希值隐轩，并且加入 hash0 引入隨機性
  hash := alg.hash(key, uintptr(h.hash0))
  // 比如 B=5，那 m 就是31渤早，二進制是全 1
  // 求 bucket num 時职车，將 hash 與 m 相與，
  // 達到 bucket num 由 hash 的低 8 位決定的效果
  m := bucketMask(h.B)
  // b 就是 bucket 的地址
  b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
  // oldbuckets 不為 nil鹊杖，說明發(fā)生了擴容
  if c := h.oldbuckets; c != nil {
    // 如果不是同 size 擴容（看后面擴容的內容）
    // 對應條件 1 的解決方案
    if !h.sameSizeGrow() {
      // 新 bucket 數(shù)量是老的 2 倍
      m >>= 1
    }
    // 求出 key 在老的 map 中的 bucket 位置
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    // 如果 oldb 沒有搬遷到新的 bucket
    // 那就在老的 bucket 中尋找
    if !evacuated(oldb) {
      b = oldb
    }
  }
  // 計算出高 8 位的 hash
  // 相當于右移 56 位悴灵，只取高8位
  top := tophash(hash)
  //開始尋找key
  for ; b != nil; b = b.overflow(t) {
    // 遍歷 8 個 bucket
    for i := uintptr(0); i < bucketCnt; i++ {
      // tophash 不匹配，繼續(xù)
      if b.tophash[i] != top {
        continue
      }
      // tophash 匹配骂蓖，定位到 key 的位置
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      // key 是指針
      if t.indirectkey {
        // 解引用
        k = *((*unsafe.Pointer)(k))
      }
      // 如果 key 相等
      if alg.equal(key, k) {
        // 定位到 value 的位置
        v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
        // value 解引用
        if t.indirectvalue {
          v = *((*unsafe.Pointer)(v))
        }
        return v
      }
    }
  }
  return unsafe.Pointer(&zeroVal[0])
}

函數(shù)返回 h[key] 的指針积瞒，如果 h 中沒有此 key，那就會返回一個 key 相應類型的零值登下，不會返回 nil茫孔。

bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 個 key 的地址就要在此基礎上跨過 i 個 key 的大斜环肌缰贝；而我們又知道，value 的地址是在所有 key 之后畔濒，因此第 i 個 value 的地址還需要加上所有 key 的偏移揩瞪。

// 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)

map讀取的兩個操作

Go 語言中讀取 map 有兩種語法：帶 comma 和 不帶 comma。當要查詢的 key 不在 map 里篓冲，帶 comma 的用法會返回一個 bool 型變量提示 key 是否在 map 中李破；而不帶 comma 的語句則會返回一個 value 類型的零值。如果 value 是 int 型就會返回 0壹将，如果 value 是 string 類型嗤攻，就會返回空字符串。

value := maps["1"]
value2,ok := maps["1"] 

以前一直覺得好神奇诽俯，怎么實現(xiàn)的妇菱？這其實是編譯器在背后做的工作：分析代碼后，將兩種語法對應到底層兩個不同的函數(shù)暴区。

//src/runtime/map.go line 394
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer 
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

map如何擴容

使用哈希表的目的就是要快速查找到目標 key闯团，然而，隨著向 map 中添加的 key 越來越多仙粱，key 發(fā)生碰撞的概率也越來越大房交。bucket 中的 8 個 cell 會被逐漸塞滿，查找伐割、插入候味、刪除 key 的效率也會越來越低刃唤。
Go 語言采用一個 bucket 里裝載 8 個 key，定位到某個 bucket 后白群，還需要再定位到具體的 key尚胞，這實際上又用了時間換空間。
所有的 key 都落在了同一個 bucket 里帜慢，a直接退化成了鏈表笼裳，各種操作的效率直接降為 O(n)。

因此粱玲，需要有一個指標來衡量前面描述的情況侍咱，這就是 裝載因子。Go 源碼里這樣定義 裝載因子：loadFactor := count /(2^B)

count 就是 map 的元素個數(shù)密幔，2^B 表示 bucket 數(shù)量楔脯。

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

1. 裝載因子超過閾值，源碼里定義的閾值是 6.5偎箫。

2. overflow 的 bucket 數(shù)量過多：當 B 小于 15木柬，也就是 bucket 總數(shù) 2^B 小于 2^15 時，overflow 的 bucket 數(shù)量超過 2^B淹办；擴容
   當 B >= 15眉枕，也就是 bucket 總數(shù) 2^B 大于等于 2^15， overflow 的 bucket 數(shù)量超過 2^15怜森。擴容速挑。

觸發(fā)擴容的代碼如下

// If we hit the max load factor or we have too many overflow buckets,
    // and we're not already in the middle of growing, start growing.
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        
    }

// 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)
}


func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    // If the threshold is too low, we do extraneous work.
    // If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
    // "too many" means (approximately) as many overflow buckets as regular buckets.
    // See incrnoverflow for more details.
    if B > 15 {
        B = 15
    }
    // The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
    return noverflow >= uint16(1)<<(B&15)
}

第 1 點：我們知道，每個 bucket 有 8 個空位副硅，在沒有溢出姥宝，且所有的桶都裝滿了的情況下，裝載因子算出來的結果是 8恐疲。因此當裝載因子超過 6.5 時腊满，表明很多 bucket 都快要裝滿了，查找效率和插入效率都變低了培己。在這個時候進行擴容是有必要的碳蛋。

第 2 點：是對第 1 點的補充。就是說在裝載因子比較小的情況下省咨，這時候 map 的查找和插入效率也很低肃弟，而第 1 點識別不出來這種情況。表面現(xiàn)象就是計算裝載因子的分子比較小茸炒，即 map 里元素總數(shù)少愕乎，但是 bucket 數(shù)量多（真實分配的 bucket 數(shù)量多阵苇，包括大量的 overflow bucket）壁公。

不難想像造成這種情況的原因：不停地插入感论、刪除元素。先插入很多元素紊册，導致創(chuàng)建了很多 bucket比肄，但是裝載因子達不到第 1 點的臨界值，未觸發(fā)擴容來緩解這種情況囊陡。之后芳绩，刪除元素降低元素總數(shù)量，再插入很多元素撞反，導致創(chuàng)建很多的 overflow bucket妥色，但就是不會觸犯第 1 點的規(guī)定，你能拿我怎么辦遏片？overflow bucket 數(shù)量太多，導致 key 會很分散，查找插入效率低得嚇人，因此出臺第 2 點規(guī)定敛助。這就像是一座空城屋确，房子很多，但是住戶很少，都分散了灼捂，找起人來很困難悉稠。

第 2 點：是對第 1 點的補充想虎。就是說在裝載因子比較小的情況下躏哩，這時候 map 的查找和插入效率也很低，而第 1 點識別不出來這種情況。表面現(xiàn)象就是計算裝載因子的分子比較小渣磷，即 map 里元素總數(shù)少逐样，但是 bucket 數(shù)量多（真實分配的 bucket 數(shù)量多争便，包括大量的 overflow bucket）级零。

不難想像造成這種情況的原因：不停地插入、刪除元素始花。先插入很多元素妄讯，導致創(chuàng)建了很多 bucket孩锡，但是裝載因子達不到第 1 點的臨界值酷宵，未觸發(fā)擴容來緩解這種情況。之后躬窜，刪除元素降低元素總數(shù)量浇垦，再插入很多元素，導致創(chuàng)建很多的 overflow bucket荣挨，但就是不會觸犯第 1 點的規(guī)定男韧，你能拿我怎么辦？overflow bucket 數(shù)量太多默垄，導致 key 會很分散此虑，查找插入效率低得嚇人，因此出臺第 2 點規(guī)定口锭。這就像是一座空城朦前，房子很多，但是住戶很少鹃操，都分散了韭寸，找起人來很困難。

對于條件 1荆隘，元素太多恩伺，而 bucket 數(shù)量太少，很簡單：將 B 加 1椰拒，bucket 最大數(shù)量（2^B）直接變成原來 bucket 數(shù)量的 2 倍晶渠。于是，就有新老 bucket 了燃观。注意褒脯，這時候元素都在老 bucket 里，還沒遷移到新的 bucket 來仪壮。而且憨颠，新 bucket 只是最大數(shù)量變?yōu)樵瓉碜畲髷?shù)量（2^B）的 2 倍（2^B * 2）。

如果插入 map 的 key 哈希都一樣，就會落到同一個 bucket 里爽彤，超過 8 個就會產生 overflow bucket养盗，結果也會造成 overflow bucket 數(shù)過多。移動元素其實解決不了問題适篙，因為這時整個哈希表已經退化成了一個鏈表往核，操作效率變成了 O(n)。

再來看一下擴容具體是怎么做的嚷节。由于 map 擴容需要將原有的 key/value 重新搬遷到新的內存地址聂儒，如果有大量的 key/value 需要搬遷，會非常影響性能硫痰。因此 Go map 的擴容采取了一種稱為“漸進式”地方式衩婚，原有的 key 并不會一次性搬遷完畢，每次最多只會搬遷 2 個 bucket效斑。

hashGrow() 函數(shù)實際上并沒有真正地“搬遷”非春，它只是分配好了新的 buckets，并將老的 buckets 掛到了 oldbuckets 字段上缓屠。真正搬遷 buckets 的動作在 growWork() 函數(shù)中奇昙，而調用 growWork() 函數(shù)的動作是在 mapassign 和 mapdelete 函數(shù)中。也就是插入或修改敌完、刪除 key 的時候储耐，都會嘗試進行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢滨溉，具體來說就是檢查 oldbuckets 是否為 nil什湘。

func hashGrow(t *maptype, h *hmap) {
  // B+1 相當于是原來 2 倍的空間
  bigger := uint8(1)
  // 對應條件 2
  if !overLoadFactor(h.count+1, h.B) {
    // 進行等量的內存擴容，所以 B 不變
    bigger = 0
    h.flags |= sameSizeGrow
  }
  // 將老 buckets 掛到 buckets 上
  oldbuckets := h.buckets
  // 申請新的 buckets 空間
  newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
    //先把 h.flags 中 iterator 和 oldIterator 對應位清 0
    //如果 iterator 位為 1业踏，把它轉接到 oldIterator 位禽炬，使得 oldIterator 標志位變成1
    //可以理解為buckets 現(xiàn)在掛到了 oldBuckets 名下了，將對應的標志位也轉接過去
  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
  // 搬遷進度為 0
  h.nevacuate = 0
  // overflow buckets 數(shù)為 0
  h.noverflow = 0
}

主要是申請到了新的 buckets 空間勤家，把相關的標志位都進行了處理：例如標志 nevacuate 被置為 0腹尖， 表示當前搬遷進度為 0。
轉移的幾個標志位如下：

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

// 可能有迭代器使用 oldbuckets
oldIterator = 2

// 有協(xié)程正在向 map 中寫入 key
hashWriting = 4

// 等量擴容（對應條件 2）
sameSizeGrow = 8

再來看看真正執(zhí)行搬遷工作的 growWork() 函數(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)
  }
}

func (h *hmap) growing() bool {
  return h.oldbuckets != nil
}

bucket&h.oldbucketmask() 這行代碼，如源碼注釋里說的讼庇，是為了確認搬遷的 bucket 是我們正在使用的 bucket绎巨。oldbucketmask() 函數(shù)返回擴容前的 map 的 bucketmask。

搬遷過程evacuate源碼：

type evacDst struct {
  b *bmap          // 表示bucket 移動的目標地址
  i int            // 指向 x,y 中 key/val 的 index
  k unsafe.Pointer // 指向 x蠕啄，y 中的 key
  v unsafe.Pointer // 指向 x场勤，y 中的 value
}

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
  // 定位老的 bucket 地址
  b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  // 計算容量 結果是 2^B戈锻，如 B = 5，結果為32
  newbit := h.noldbuckets()
  // 如果 b 沒有被搬遷過
  if !evacuated(b) {
    // 默認是等 size 擴容和媳，前后 bucket 序號不變
    var xy [2]evacDst
    // 使用 x 來進行搬遷
    x := &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))

    // 如果不是等 size 擴容格遭，前后 bucket 序號有變
    if !h.sameSizeGrow() {
      // 使用 y 來進行搬遷
      y := &xy[1]
      // y 代表的 bucket 序號增加了 2^B
      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))
    }
    // 遍歷所有的 bucket，包括 overflow buckets b 是老的 bucket 地址
    for ; b != nil; b = b.overflow(t) {
      k := add(unsafe.Pointer(b), dataOffset)
      v := add(k, bucketCnt*uintptr(t.keysize))
      // 遍歷 bucket 中的所有 cell
      for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
        // 當前 cell 的 top hash 值
        top := b.tophash[i]
        // 如果 cell 為空留瞳，即沒有 key
        if top == empty {
          // 那就標志它被"搬遷"過
          b.tophash[i] = evacuatedEmpty
          continue
        }
        // 正常不會出現(xiàn)這種情況
        // 未被搬遷的 cell 只可能是 empty 或是
        // 正常的 top hash（大于 minTopHash）
        if top < minTopHash {
          throw("bad map state")
        }
        // 如果 key 是指針拒迅，則解引用
        k2 := k
        if t.indirectkey {
          k2 = *((*unsafe.Pointer)(k2))
        }
        var useY uint8
        // 如果不是等量擴容
        if !h.sameSizeGrow() {
          // 計算 hash 值，和 key 第一次寫入時一樣
          hash := t.key.alg.hash(k2, uintptr(h.hash0))
          // 如果有協(xié)程正在遍歷 map 如果出現(xiàn) 相同的 key 值她倘，算出來的 hash 值不同
          if h.flags&iterator != 0 && !t.reflexivekey && !t.key.alg.equal(k2, k2) {
            // useY =1 使用位置Y
            useY = top & 1
            top = tophash(hash)
          } else {
            // 第 B 位置 不是 0
            if hash&newbit != 0 {
              //使用位置Y
              useY = 1
            }
          }
        }

        if evacuatedX+1 != evacuatedY {
          throw("bad evacuatedN")
        }
        //決定key是裂變到 X 還是 Y
        b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
        dst := &xy[useY]                 // evacuation destination
        // 如果 xi 等于 8璧微，說明要溢出了
        if dst.i == bucketCnt {
          // 新建一個 bucket
          dst.b = h.newoverflow(t, dst.b)
          // xi 從 0 開始計數(shù)
          dst.i = 0
          //key移動的位置
          dst.k = add(unsafe.Pointer(dst.b), dataOffset)
          //value 移動的位置
          dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
        }
        // 設置 top hash 值
        dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
        // key 是指針
        if t.indirectkey {
          // 將原 key（是指針）復制到新位置
          *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
        } else {
          // 將原 key（是值）復制到新位置
          typedmemmove(t.key, dst.k, k) // copy value
        }
        //value同上
        if t.indirectvalue {
          *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v)
        } else {
          typedmemmove(t.elem, dst.v, v)
        }
        // 定位到下一個 cell
        dst.i++
        dst.k = add(dst.k, uintptr(t.keysize))
        dst.v = add(dst.v, uintptr(t.valuesize))
      }
    }
    // Unlink the overflow buckets & clear key/value to help GC.

    // bucket搬遷完畢 如果沒有協(xié)程在使用老的 buckets，就把老 buckets 清除掉硬梁，幫助gc
    if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
      b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
      ptr := add(b, dataOffset)
      n := uintptr(t.bucketsize) - dataOffset
      memclrHasPointers(ptr, n)
    }
  }
  // 更新搬遷進度
  if oldbucket == h.nevacuate {
    advanceEvacuationMark(h, t, newbit)
  }
}

通過前面的說明我們知道前硫，應對條件 1，新的 buckets 數(shù)量是之前的一倍靶溜，應對條件 2开瞭，新的 buckets 數(shù)量和之前相等懒震。
對于條件 1罩息，從老的 buckets 搬遷到新的 buckets，由于 bucktes 數(shù)量不變个扰，因此可以按序號來搬瓷炮，比如原來在 0 號 bucktes，到新的地方后递宅，仍然放在 0 號 buckets娘香。

對于條件 2，就沒這么簡單了办龄。要重新計算 key 的哈希烘绽，才能決定它到底落在哪個 bucket。例如俐填，原來 B = 5安接，計算出 key 的哈希后，只用看它的低 5 位英融，就能決定它落在哪個 bucket盏檐。擴容后，B 變成了 6驶悟，因此需要多看一位胡野，它的低 6 位決定 key 落在哪個 bucket。這稱為 rehash痕鳍。

rehash

因此硫豆，某個 key 在搬遷前后 bucket 序號可能和原來相等，也可能是相比原來加上 2^B（原來的 B 值）艺沼，取決于 hash 值 第 6 bit 位是 0 還是 1绝淡。

理解了上面 bucket 序號的變化，我們就可以回答另一個問題了：為什么遍歷 map 是無序的阴孟？

map 在擴容后耘眨，會發(fā)生 key 的搬遷昼榛，原來落在同一個 bucket 中的 key，搬遷后剔难，有些 key 就要遠走高飛了（bucket 序號加上了 2^B）胆屿。而遍歷的過程，就是按順序遍歷 bucket偶宫，同時按順序遍歷 bucket 中的 key非迹。搬遷后，key 的位置發(fā)生了重大的變化纯趋，有些 key 飛上高枝憎兽，有些 key 則原地不動。這樣吵冒，遍歷 map 的結果就不可能按原來的順序了纯命。

按理說每次遍歷這樣的 map 都會返回一個固定順序的 key/value 序列吧。的確是這樣痹栖，但是 Go 杜絕了這種做法亿汞，因為這樣會給新手程序員帶來誤解，以為這是一定會發(fā)生的事情揪阿，在某些情況下疗我，可能會釀成大錯。

Go 做得更絕南捂，當我們在遍歷 map 時吴裤，并不是固定地從 0 號 bucket 開始遍歷，每次都是從一個隨機值序號的 bucket 開始遍歷溺健，并且是從這個 bucket 的一個隨機序號的 cell 開始遍歷麦牺。這樣，即使你是一個寫死的 map矿瘦，僅僅只是遍歷它枕面，也不太可能會返回一個固定序列的 key/value 對了

再明確一個問題：如果擴容后，B 增加了 1缚去，意味著 buckets 總數(shù)是原來的 2 倍潮秘，原來 1 號的桶“裂變”到兩個桶。

例如易结，原始 B = 2枕荞，1號 bucket 中有 2 個 key 的哈希值低 3 位分別為：010柜候，110。由于原來 B = 2躏精，所以低 2 位 10 決定它們落在 2 號桶渣刷，現(xiàn)在 B 變成 3，所以 010矗烛、 110 分別落入 2辅柴、6 號桶。(這與數(shù)據庫的動態(tài)hash索引類似)

有一個特殊情況是：有一種 key瞭吃，每次對它計算 hash碌嘀，得到的結果都不一樣。這個 key 就是 math.NaN() 的結果歪架，它的含義是 nota number股冗，類型是 float64。當它作為 map 的 key和蚪，在搬遷的時候止状，會遇到一個問題：再次計算它的哈希值和它當初插入 map 時的計算出來的哈希值不一樣！

你可能想到了攒霹，這樣帶來的一個后果是怯疤，這個 key 是永遠不會被 Get 操作獲取的！當我使用 m[math.NaN()] 語句的時候剔蹋，是查不出來結果的旅薄。這個 key 只有在遍歷整個 map 的時候，才有機會現(xiàn)身泣崩。所以，可以向一個 map 插入任意數(shù)量的 math.NaN() 作為 key洛口。

下面通過圖來宏觀地看一下擴容前后的變化矫付。

擴容前，B = 2第焰，共有 4 個 buckets买优，lowbits 表示 hash 值的低位。假設我們不關注其他 buckets 情況挺举，專注在 2 號 bucket杀赢。并且假設 overflow 太多，觸發(fā)了等量擴容（對應于前面的條件 2）湘纵。

擴容完成后脂崔，overflow bucket 消失了，key 都集中到了一個 bucket梧喷，更為緊湊了砌左，提高了查找的效率脖咐。

假設觸發(fā)了 2 倍的擴容，那么擴容完成后汇歹，老 buckets 中的 key 分裂到了 2 個 新的 bucket屁擅。一個在 x part，一個在 y 的 part产弹。依據是 hash 的 lowbits派歌。新 map 中 0-3稱為 x part， 4-7 稱為 y part痰哨。

map遍歷

本來 map 的遍歷過程比較簡單：遍歷所有的 bucket 以及它后面掛的 overflow bucket硝皂，然后挨個遍歷 bucket 中的所有 cell。每個 bucket 中包含 8 個 cell作谭，從有 key 的 cell 中取出 key 和 value稽物，這個過程就完成了。

但是折欠，現(xiàn)實并沒有這么簡單贝或。還記得前面講過的擴容過程嗎？擴容過程不是一個原子的操作锐秦，它每次最多只搬運 2 個 bucket咪奖，所以如果觸發(fā)了擴容操作，那么在很長時間里酱床，map 的狀態(tài)都是處于一個中間態(tài)：有些 bucket 已經搬遷到新家羊赵，而有些 bucket 還待在老地方。

因此扇谣，遍歷如果發(fā)生在擴容的過程中昧捷，就會涉及到遍歷新老 bucket 的過程，這是難點所在罐寨。

關于 map 迭代靡挥，先是調用 mapiterinit 函數(shù)初始化迭代器，然后循環(huán)調用 mapiternext 函數(shù)進行 map 迭代鸯绿。

前面已經提到過跋破，即使是對一個寫死的 map 進行遍歷，每次出來的結果也是無序的瓶蝴。下面我們就可以近距離地觀察他們的實現(xiàn)了毒返。

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)
}

重點是fastrand 的部分，是一個生成隨機數(shù)的方法：它生成了隨機數(shù)舷手。用于決定從哪里開始循環(huán)迭代拧簸。更具體的話就是根據隨機數(shù)，選擇一個桶位置作為起始點進行遍歷迭代因此每次重新 for range map聚霜，你見到的結果都是不一樣的狡恬。那是因為它的起始位置根本就不固定珠叔！

...
// decide where to start
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))

// iterator state
it.bucket = it.startBucket

map的賦值和更新

，向 map 中插入或者修改 key弟劲，最終調用的是 mapassign 函數(shù)祷安。

實際上插入或修改 key 的語法是一樣的，只不過前者操作的 key 在 map 中不存在兔乞，而后者操作的 key 存在 map 中汇鞭。

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

整體來看，流程非常得簡單：對 key 計算 hash 值淡溯，根據 hash 值按照之前的流程读整，找到要賦值的位置（可能是插入新 key，也可能是更新老 key）咱娶，對相應位置進行賦值米间。

源碼大體和之前講的類似，核心還是一個雙層循環(huán)膘侮，外層遍歷 bucket 和它的 overflow bucket屈糊，內層遍歷整個 bucket 的各個 cell

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

通過前文我們知道擴容是漸進式的昧诱，如果 map 處在擴容的過程中，那么當 key 定位到了某個 bucket 后蹦哼，需要確保這個 bucket 對應的老 bucket 完成了遷移過程鳄哭。即老 bucket 里的 key 都要遷移到新的 bucket 中來（分裂到 2 個新 bucket），才能在新的 bucket 中進行插入或者更新的操作纲熏。

上面說的操作是在函數(shù)靠前的位置進行的，只有進行完了這個搬遷操作后锄俄，我們才能放心地在新 bucket 里定位 key 要安置的地址局劲，再進行之后的操作。

現(xiàn)在到了定位 key 應該放置的位置了奶赠，所謂找準自己的位置很重要鱼填。準備兩個指針，一個（ inserti）指向 key 的 hash 值在 tophash 數(shù)組所處的位置毅戈，另一個( insertk)指向 cell 的位置（也就是 key 最終放置的地址）苹丸，當然愤惰，對應 value 的位置就很容易定位出來了。這三者實際上都是關聯(lián)的赘理，在 tophash 數(shù)組中的索引位置決定了 key 在整個 bucket 中的位置（共 8 個 key）宦言，而 value 的位置需要“跨過” 8 個 key 的長度。

在循環(huán)的過程中商模，inserti 和 insertk 分別指向第一個找到的空閑的 cell奠旺。如果之后在 map 沒有找到 key 的存在，也就是說原來 map 中沒有此 key施流，這意味著插入新 key响疚。那最終 key 的安置地址就是第一次發(fā)現(xiàn)的“空位”（tophash 是 empty）。

如果這個 bucket 的 8 個 key 都已經放置滿了瞪醋，那在跳出循環(huán)后忿晕，發(fā)現(xiàn) inserti 和 insertk 都是空，這時候需要在 bucket 后面掛上 overflow bucket银受。當然践盼，也有可能是在 overflow bucket 后面再掛上一個 overflow bucket。這就說明蚓土，太多 key hash 到了此 bucket宏侍。

在正式安置 key 之前，還要檢查 map 的狀態(tài)蜀漆，看它是否需要進行擴容谅河。如果滿足擴容的條件，就主動觸發(fā)一次擴容操作确丢。

這之后绷耍，整個之前的查找定位 key 的過程，還得再重新走一次鲜侥。因為擴容之后褂始，key 的分布都發(fā)生了變化。

最后描函，會更新 map 相關的值崎苗，如果是插入新 key，map 的元素數(shù)量字段 count 值會加 1舀寓；在函數(shù)之初設置的 hashWriting 寫標志出會清零胆数。

map的刪除

寫操作底層的執(zhí)行函數(shù)是 mapdelete

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

它首先會檢查 h.flags 標志，如果發(fā)現(xiàn)寫標位是 1互墓，直接 panic必尼，因為這表明有其他協(xié)程同時在進行寫操作。

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

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

找到對應位置后但汞，對 key 或者 value 進行“清零”操作：
最后，將 count 值減 1互站，將對應位置的 tophash 值置成 Empty私蕾。

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
  if raceenabled && h != nil {
    callerpc := getcallerpc()
    pc := funcPC(mapdelete)
    racewritepc(unsafe.Pointer(h), callerpc, pc)
    raceReadObjectPC(t.key, key, callerpc, pc)
  }
  if msanenabled && h != nil {
    msanread(key, t.key.size)
  }
  if h == nil || h.count == 0 {
    return
  }
  if h.flags&hashWriting != 0 {
    throw("concurrent map writes")
  }

  alg := t.key.alg
  hash := alg.hash(key, uintptr(h.hash0))

  // Set hashWriting after calling alg.hash, since alg.hash may panic,
  // in which case we have not actually done a write (delete).
  h.flags |= hashWriting

  bucket := hash & bucketMask(h.B)
  if h.growing() {
    growWork(t, h, bucket)
  }
  b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
  top := tophash(hash)
search:
  for ; b != nil; b = b.overflow(t) {
    for i := uintptr(0); i < bucketCnt; i++ {
      if b.tophash[i] != top {
        continue
      }
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      k2 := k
      if t.indirectkey {
        k2 = *((*unsafe.Pointer)(k2))
      }
      if !alg.equal(key, k2) {
        continue
      }
      // Only clear key if there are pointers in it.
            // 對key清零
      if t.indirectkey {
        *(*unsafe.Pointer)(k) = nil
      } else if t.key.kind&kindNoPointers == 0 {
        memclrHasPointers(k, t.key.size)
      }
      v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            // 對value清零
      if t.indirectvalue {
        *(*unsafe.Pointer)(v) = nil
      } else if t.elem.kind&kindNoPointers == 0 {
        memclrHasPointers(v, t.elem.size)
      } else {
        memclrNoHeapPointers(v, t.elem.size)
      }
            // 高位hash清零
      b.tophash[i] = empty
            // 個數(shù)減一
      h.count--
      break search
    }
  }

  if h.flags&hashWriting == 0 {
    throw("concurrent map writes")
  }
  h.flags &^= hashWriting
}

Go 語言中只要是可比較的類型都可以作為 key。除開 slice胡桃，map踩叭，functions 這幾種類型，其他類型都是 OK 的翠胰。具體包括：布爾值容贝、數(shù)字、字符串之景、指針斤富、通道、接口類型锻狗、結構體满力、只包含上述類型的數(shù)組。這些類型的共同特征是支持 == 和 != 操作符轻纪， k1==k2 時油额，可認為 k1 和 k2 是同一個 key。如果是結構體刻帚，則需要它們的字段值都相等潦嘶，才被認為是相同的 key。
當用 float64 作為 key 的時候崇众，先要將其轉成 unit64 類型掂僵，再插入 key 中。
順便說一句顷歌，任何類型都可以作為 value看峻，包括 map 類型。

map的并發(fā)訪問

map 并不是一個線程安全的數(shù)據結構衙吩。同時讀寫一個 map 是不安全的，如果被檢測到溪窒，會直接 panic坤塞。

解決方法1：讀寫鎖 sync.RWMutex冯勉。將map與讀寫鎖定義在一個結構體，訪問時加鎖解鎖

解決方法2：使用golang提供的 sync.Map

func main() {
  m := sync.Map{}
  m.Store(1, 1)
  i := 0
  go func() {
    for i < 1000 {
      m.Store(1, 1)
      i++
    }
  }()

  go func() {
    for i < 1000 {
      m.Store(2, 2)
      i++
    }
  }()

  go func() {
    for i < 1000 {
      fmt.Println(m.Load(1))
      i++
    }
  }()

  for {
    runtime.GC()
  }
}

最后看一看下列代碼如果覺得和想的不一樣摹芙，可以試試并想想為什么灼狰。

    var m map[string]string //m == nil
    delete(m,"name") //不會panic
    fmt.Println(m["name"]) //返回類型默認值
    m["name"] = "Li" //panic

總結

總結一下，Go 語言中浮禾，通過哈希查找表實現(xiàn) map交胚，用鏈表法解決哈希沖突。

通過 key 的哈希值將 key 散落到不同的桶中盈电，每個桶中有 8 個 cell蝴簇。哈希值的低位決定桶序號，高位標識同一個桶中的不同 key匆帚。

當向桶中添加了很多 key熬词，造成元素過多，或者溢出桶太多吸重，就會觸發(fā)擴容互拾。擴容分為等量擴容和 2 倍容量擴容。擴容后嚎幸，原來一個 bucket 中的 key 一分為二颜矿，會被重新分配到兩個桶中。

擴容過程是漸進的嫉晶，主要是防止一次擴容需要搬遷的 key 數(shù)量過多骑疆，引發(fā)性能問題。觸發(fā)擴容的時機是增加了新元素车遂，bucket 搬遷的時機則發(fā)生在賦值封断、刪除期間，每次最多搬遷兩個 bucket舶担。

查找坡疼、賦值、刪除的一個很核心的內容是如何定位到 key 所在的位置.

參考:深度解密Go語言之map - Golang語言社區(qū)
好未來Golang源碼系列一：Map實現(xiàn)原理分析-Go語言中文網