1. 底層原理

hmap

Go中的map是一個(gè)指針，占用8個(gè)字節(jié)闭翩，指向底層的hmap結(jié)構(gòu)體(hash表)，在源碼包src/runtime/map.go中定義了該結(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/reflectdata/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)   代表哈希表中的元素個(gè)數(shù)迄埃，調(diào)用len(map)時(shí)疗韵，返回的就是該字段值
    flags     uint8  //  狀態(tài)標(biāo)志（是否處于正在寫(xiě)入的狀態(tài)等）
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)      buckets（桶）的對(duì), 如果B=5，則buckets數(shù)組的長(zhǎng)度 = 2^B=32侄非，意味著有32個(gè)桶
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details,      溢出桶的數(shù)量
    hash0     uint32 // hash seed      生成hash的隨機(jī)數(shù)種子

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.       指向buckets數(shù)組的指針蕉汪，數(shù)組大小為2^B，如果元素個(gè)數(shù)為0逞怨，它為nil者疤。
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing  .如果發(fā)生擴(kuò)容，oldbuckets是指向老的buckets數(shù)組的指針叠赦，老的buckets數(shù)組大小是新的buckets的1/2;非擴(kuò)容狀態(tài)下驹马，它為nil。
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)     表示擴(kuò)容進(jìn)度眯搭，小于此地址的buckets代表已搬遷完成

    extra *mapextra // optional fields
}

map 結(jié)構(gòu)

bmap

上面說(shuō)到hmap 中有一個(gè)buckets 數(shù)組窥翩，其中數(shù)組中的每一個(gè)元素稱為bucket（桶） ，我們也叫作 bmap鳞仙。
一個(gè)桶里面會(huì)最多裝 8 個(gè) 鍵值對(duì)寇蚊，這些 鍵值對(duì) 之所以會(huì)落入同一個(gè)桶，是因?yàn)樗鼈兊膋ey經(jīng)過(guò)哈希計(jì)算后棍好，哈希結(jié)果的低B位(hmap 中的B字段)是相同的仗岸，關(guān)于key的定位我們?cè)趍ap的查詢中詳細(xì)說(shuō)明。在桶內(nèi)借笙，又會(huì)根據(jù) key 計(jì)算出來(lái)的 hash 值的高 8 位來(lái)決定 key 到底落入桶內(nèi)的哪個(gè)位置（一個(gè)桶內(nèi)最多有8個(gè)位置)扒怖。 下面是bmap 結(jié)構(gòu)體的定義，其中tophash是一個(gè)長(zhǎng)度為8的數(shù)組（bucketCnt = 1 << bucketCntBits业稼，bucketCntBits=3）盗痒，用來(lái)快速定位key，如果key的tophash 值在這個(gè)數(shù)組中低散，則代表該key在該桶中

// A bucket for a Go map.
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.
}

上面bmap結(jié)構(gòu)是靜態(tài)結(jié)構(gòu)俯邓，在編譯過(guò)程中runtime.bmap會(huì)拓展成以下結(jié)構(gòu)體：

type bmap struct{
    tophash [8]uint8
    keys [8]keytype 
    // keytype 由編譯器編譯時(shí)候確定
    values [8]elemtype 
    // elemtype 由編譯器編譯時(shí)候確定
    overflow uintptr 
    // overflow指向下一個(gè)bmap，overflow是uintptr而不是*bmap類型熔号，保證bmap完全不含指針稽鞭，是為了減少gc，溢出桶存儲(chǔ)到extra字段中
}

tophash就是用于實(shí)現(xiàn)快速定位key的位置引镊，在實(shí)現(xiàn)過(guò)程中會(huì)使用key的hash值的高8位作為tophash值朦蕴，存放在bmap的tophash字段中. 同時(shí)還會(huì)存儲(chǔ)一些狀態(tài)值篮条， 表明當(dāng)前的桶單元的狀態(tài)，這些狀態(tài)值都小于minTopHash吩抓。為了避免key哈希值的高8位值和這些狀態(tài)值相等涉茧，產(chǎn)生混淆情況，所以當(dāng)key哈希值高8位若小于minTopHash時(shí)候琴拧，自動(dòng)將其值加上minTopHash作為該key的tophash降瞳。桶單元的狀態(tài)值如下：

emptyRest = 0 // 表明此桶單元為空，且更高索引的單元也是空
emptyOne = 1 // 表明此桶單元為空
evacuatedX = 2 // 用于表示擴(kuò)容遷移到新桶前半段區(qū)間
evacuatedY = 3 // 用于表示擴(kuò)容遷移到新桶后半段區(qū)間
evacuatedEmpty = 4 // 用于表示此單元已遷移
minTopHash = 5 // key的tophash值與桶狀態(tài)值分割線值蚓胸，小于此值的一定代表著桶單元的狀態(tài)挣饥，大于此值的一定是key對(duì)應(yīng)的tophash值

如下的tophash函數(shù)， 就是來(lái)計(jì)算key的tophash 值沛膳，可以看到扔枫， 如果小于minTopHash（5）， 加上minTopHash作為該key的tophash

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

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

注意到 key 和 value 是各自放在一起的锹安，并不是 key/value/key/value/... 這樣的形式短荐，當(dāng)key和value類型不一樣的時(shí)候，key和value占用字節(jié)大小不一樣叹哭，使用key/value這種形式可能會(huì)因?yàn)閮?nèi)存對(duì)齊導(dǎo)致內(nèi)存空間浪費(fèi)忍宋，所以Go采用key和value分開(kāi)存儲(chǔ)的設(shè)計(jì)，更節(jié)省內(nèi)存空間

map 查找

map的查找流程如下：

map 查找流程

• 寫(xiě)保護(hù)監(jiān)測(cè)：
  函數(shù)首先會(huì)檢查 map 底層hmap標(biāo)志位 flags风罩。如果 flags 的寫(xiě)標(biāo)志位此時(shí)被置 1 了糠排，說(shuō)明有其他協(xié)程在執(zhí)行“寫(xiě)”操作，進(jìn)而導(dǎo)致程序 panic超升，這也說(shuō)明了 map 不是線程安全的入宦。flags標(biāo)識(shí)如下：

// flags
iterator = 1 // there may be an iterator using buckets
oldIterator = 2 // there may be an iterator using oldbuckets
hashWriting = 4 // a goroutine is writing to the map
sameSizeGrow = 8 // the current map growth is to a new map of the same size

// 判斷map 是否是在寫(xiě)的狀態(tài)，如果是的話室琢，則拋出異常乾闰，所以map 不是線程安全的
     if h.flags&hashWriting != 0 {
         throw("concurrent map read and map write")
     }

• 計(jì)算hash：
  計(jì)算map 中的key 的hash 值

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

hasher 函數(shù)類型為 func(unsafe.Pointer, uintptr) uintptr , 將傳入key的指針地址，和hmap的hash 種子
key經(jīng)過(guò)哈希函數(shù)計(jì)算后盈滴，得到的哈希值如下（主流64位機(jī)下共 64 個(gè) bit 位）涯肩， 不同類型的key會(huì)有不同的hash函數(shù)

• 找到hash對(duì)應(yīng)的bucket：
  bucket定位：key 的hash 值的低B個(gè)bit 位，用來(lái)定位key所存放的bucket
  如果當(dāng)前map正在擴(kuò)容中巢钓，并且定位到的舊bucket數(shù)據(jù)還未完成遷移病苗，則使用舊的bucket（擴(kuò)容前的bucket oldbuckets ）

// 桶的個(gè)數(shù)m-1，即 1<<B-1,B=5時(shí)竿报，則有0~31號(hào)桶
m := bucketMask(h.B)
// 計(jì)算哈希值對(duì)應(yīng)的bucket
// t.bucketsize為一個(gè)bmap的大小，通過(guò)對(duì)哈希值和桶個(gè)數(shù)取模得到桶編號(hào)继谚，通過(guò)對(duì)桶編號(hào)和buckets起始地址進(jìn)行運(yùn)算烈菌，獲取哈希值對(duì)應(yīng)的bucket
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 是否在擴(kuò)容
if c := h.oldbuckets; c != nil {
  // 桶個(gè)數(shù)已經(jīng)發(fā)生增長(zhǎng)一倍阵幸，則舊bucket的桶個(gè)數(shù)為當(dāng)前桶個(gè)數(shù)的一半
    if !h.sameSizeGrow() {
        // There used to be half as many buckets; mask down one more power of two.
        m >>= 1
    }
    // 計(jì)算哈希值對(duì)應(yīng)的舊bucket
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    // 如果舊bucket的數(shù)據(jù)沒(méi)有完成遷移，則使用舊bucket查找
    if !evacuated(oldb) {
        b = oldb
    }
}

• 遍歷查找bucket：
  通過(guò)tophash 函數(shù)定位：哈希值的高8個(gè)bit 位芽世，用來(lái)快速判斷key是否已在當(dāng)前bucket中挚赊，如果不在的話，需要去bucket的overflow中查找

示例：
假設(shè)某個(gè)key的hash 值為1001011100001111011011001000111100101010001001011001010101000110,其中hmap的B=5 即 有2^5 =32 個(gè)桶（0-31號(hào)）, 如下圖所示：

map key 沖突解決方式

而Go map也采用 鏈地址法解決沖突蔑鹦，具體就是插入key到map中時(shí)，當(dāng)key定位的桶填滿8個(gè)元素后（這里的單元就是桶箕宙，不是元素）嚎朽，將會(huì)創(chuàng)建一個(gè)溢出桶（overflow ），并且將溢出桶插入當(dāng)前桶所在鏈表尾部

2. map 遍歷的無(wú)序性

使用 range 多次遍歷 map 時(shí)輸出的 key 和 value 的順序可能不同柬帕。主要原因有2點(diǎn)：

• map在遍歷時(shí)哟忍，并不是從固定的0號(hào)bucket開(kāi)始遍歷的，每次遍歷陷寝，都會(huì)從一個(gè)隨機(jī)值序號(hào)的bucket锅很，再?gòu)钠渲须S機(jī)的cell開(kāi)始遍歷
• map遍歷時(shí)，是按序遍歷bucket凤跑，同時(shí)按序遍歷bucket中和其overflow bucket中的cell爆安。但是map在擴(kuò)容后，會(huì)發(fā)生key的搬遷饶火，這造成原來(lái)落在一個(gè)bucket中的key鹏控，搬遷后，有可能會(huì)落到其他bucket中了肤寝，從這個(gè)角度看当辐，遍歷map的結(jié)果就不可能是按照原來(lái)的順序了

如果想要有序遍歷map，只需對(duì) map中的 key 先排序鲤看，再按照 key 的順序遍歷 map

3. 線程安全性

map默認(rèn)是并發(fā)不安全的缘揪，同時(shí)對(duì)map進(jìn)行并發(fā)讀寫(xiě)時(shí)，程序會(huì)通過(guò)map 的寫(xiě)保護(hù)監(jiān)測(cè)機(jī)制來(lái)拋出panic異常
要想實(shí)現(xiàn)并發(fā)安全义桂，有如下兩種方式

• map + 鎖（sync.RWMutex）
• 使用Go自帶的 sync.Map找筝， 該map 支持并發(fā)讀寫(xiě)安全, sync.Map采取了 “空間換時(shí)間” 的機(jī)制，冗余了兩個(gè)數(shù)據(jù)結(jié)構(gòu)慷吊，分別是：read 和 dirty

type Map struct {
   mu Mutex
   read atomic.Value // readOnly
   dirty map[interface{}]*entry
   misses int
}

和原始map+RWLock的實(shí)現(xiàn)并發(fā)的方式相比袖裕，減少了加鎖對(duì)性能的影響。它做了一些優(yōu)化：可以無(wú)鎖訪問(wèn)read map溉瓶，而且會(huì)優(yōu)先操作read map急鳄，倘若只操作read map就可以滿足要求谤民，那就不用去操作write map(dirty)，所以在某些特定場(chǎng)景中它發(fā)生鎖競(jìng)爭(zhēng)的頻率會(huì)遠(yuǎn)遠(yuǎn)小于map+RWLock的實(shí)現(xiàn)方式

優(yōu)點(diǎn)：

適合讀多寫(xiě)少的場(chǎng)景

缺點(diǎn)：

寫(xiě)多的場(chǎng)景疾宏，會(huì)導(dǎo)致 read map 緩存失效张足，需要加鎖，沖突變多坎藐，性能急劇下降