golang map底層原理

映射是一個(gè)集合，可以使用類似處理數(shù)組和切片的方式迭代映射中的元素。但映射是無序的集合萎庭，意味著沒有辦法預(yù)測鍵值對(duì)被返回的順序。即便使用同樣的順序保存鍵值對(duì)齿拂，每次迭代映射的時(shí)候順序也可能不一樣驳规。無序的原因是映射的實(shí)現(xiàn)使用了散列表。go語言中的map采用的是哈希查找表署海，由一個(gè)key通過哈希函數(shù)得到哈希值吗购，64位系統(tǒng)中就生成一個(gè)64bit的哈希值，由這個(gè)哈希值將key對(duì)應(yīng)到不同的桶（bucket）中砸狞，當(dāng)有多個(gè)哈希映射到相同的的桶中時(shí)捻勉，使用鏈表解決哈希沖突。
hash函數(shù)
golang中的map使用hash查找刀森，就是將key做hash運(yùn)算得到一個(gè)哈希值踱启，根據(jù)哈希值確定key-value落在哪個(gè)bucket的哪個(gè)cell。hash算法和CPU有關(guān)，如果cpu支持aes埠偿，那么使用aes hash透罢，否則使用memhash。
數(shù)據(jù)結(jié)構(gòu)

// 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 // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8  //map狀態(tài)標(biāo)識(shí),比如是否在被寫或遷移等
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed隨機(jī)hash種子

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}
//用**mapextra**來存儲(chǔ)key和value都不是指針類型的map冠蒋，并且大小都小于128字節(jié)羽圃，這樣可以避免GC掃描整個(gè)map
// mapextra holds fields that are not present on all maps.
type mapextra struct {
    // If both key and elem do not contain pointers and are inline, then we mark bucket
    // type as containing no pointers. This avoids scanning such maps.
    // However, bmap.overflow is a pointer. In order to keep overflow buckets
    // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
    // overflow and oldoverflow are only used if key and elem do not contain pointers.
    // overflow contains overflow buckets for hmap.buckets.
    // oldoverflow contains overflow buckets for hmap.oldbuckets.
    // The indirection allows to store a pointer to the slice in hiter.
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // nextOverflow holds a pointer to a free overflow bucket.
    nextOverflow *bmap
}
// A bucket for a Go map.
//**bmap**可以理解為buckets of map的縮寫，它就是map中bucket的本體抖剿，即存key和value數(shù)據(jù)的“桶”
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

根據(jù)哈希函數(shù)將key生成一個(gè)hash值朽寞，其中低位hash用來判斷桶的位置，高位hash確定在桶中的哪個(gè)cell斩郎。低位哈希就是哈希值的低B位脑融，hmap結(jié)構(gòu)體中的B，比如B為5孽拷，2^5=32吨掌，即該map有32個(gè)桶，只需要取哈希值的低5位就可以確定當(dāng)前key-value落在哪個(gè)桶(bucket)中脓恕；高位哈希即tophash，是指哈希值的高8bits窿侈，根據(jù)tophash來確定key在桶中的位置炼幔。每個(gè)桶可以存儲(chǔ)8對(duì)key-value，存儲(chǔ)結(jié)構(gòu)不是key/value/key/value...史简，而是key/key..value/value乃秀，這樣可以避免字節(jié)對(duì)齊時(shí)的padding，節(jié)省內(nèi)存空間圆兵。
當(dāng)不同的key根據(jù)哈希得到的tophash和低位hash都一樣跺讯，發(fā)生哈希碰撞，這個(gè)時(shí)候就體現(xiàn)overflow pointer字段的作用了殉农。桶溢出時(shí)刀脏，就需要把key-value對(duì)存儲(chǔ)在overflow bucket（溢出桶），overflow pointer就是指向overflow bucket的指針超凳。如果overflow bucket也溢出了呢愈污？那就再給overflow bucket新建一個(gè)overflow bucket，用指針串起來就形成了鏈?zhǔn)浇Y(jié)構(gòu)轮傍，map本身有2^B個(gè)bucket暂雹，只有當(dāng)發(fā)生哈希碰撞后才會(huì)在bucket后鏈?zhǔn)皆黾觨verflow bucket。
map內(nèi)存布局
擴(kuò)容

裝填因子是否大于6.5
裝填因子 = 元素個(gè)數(shù)/桶個(gè)數(shù)创夜，大于6.5時(shí)杭跪，說明桶快要裝滿，需要擴(kuò)容

overflow bucket是否太多
當(dāng)bucket的數(shù)量 < 2^15，但overflow bucket的數(shù)量大于桶數(shù)量
當(dāng)bucket的數(shù)量 >= 2^15涧尿，但overflow bucket的數(shù)量大于2^15

雙倍擴(kuò)容：裝載因子多大系奉，直接翻倍，B+1现斋；擴(kuò)容也不是申請一塊內(nèi)存喜最，立馬開始拷貝，每一次訪問舊的buckets時(shí)庄蹋，就遷移一部分瞬内，直到完成，舊bucket被GC回收限书。

等量擴(kuò)容：重新排列虫蝶，極端情況下，重新排列也解決不了倦西，map成了鏈表能真，性能大大降低，此時(shí)哈希種子hash0的設(shè)置扰柠，可以降低此類極端場景的發(fā)生粉铐。
查找
根據(jù)key計(jì)算出哈希值
根據(jù)哈希值低位確定所在bucket
根據(jù)哈希值高8位確定在bucket中的存儲(chǔ)位置
當(dāng)前bucket未找到則查找對(duì)應(yīng)的overflow bucket。
對(duì)應(yīng)位置有數(shù)據(jù)則對(duì)比完整的哈希值卤档，確定是否是要查找的數(shù)據(jù)
如果當(dāng)前處于map進(jìn)行了擴(kuò)容蝙泼，處于數(shù)據(jù)搬移狀態(tài)，則優(yōu)先從oldbuckets查找劝枣。
插入
根據(jù)key計(jì)算出哈希值
根據(jù)哈希值低位確定所在bucket
根據(jù)哈希值高8位確定在bucket中的存儲(chǔ)位置
查找該key是否存在汤踏，已存在則更新，不存在則插入
map無序
map的本質(zhì)是散列表舔腾，而map的增長擴(kuò)容會(huì)導(dǎo)致重新進(jìn)行散列溪胶，這就可能使map的遍歷結(jié)果在擴(kuò)容前后變得不可靠，Go設(shè)計(jì)者為了讓大家不依賴遍歷的順序稳诚，故意在實(shí)現(xiàn)map遍歷時(shí)加入了隨機(jī)數(shù)哗脖，讓每次遍歷的起點(diǎn)--即起始bucket的位置不一樣，即不讓遍歷都從bucket0開始采桃，所以即使未擴(kuò)容時(shí)我們遍歷出來的map也總是無序的懒熙。