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)志（是否處于正在寫入的狀態(tài)等）
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)      buckets（桶）的對, 如果B=5，則buckets數(shù)組的長度 = 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

上面說到hmap 中有一個(gè)buckets 數(shù)組，其中數(shù)組中的每一個(gè)元素稱為bucket（桶） ，我們也叫作 bmap。
一個(gè)桶里面會(huì)最多裝 8 個(gè) 鍵值對，這些 鍵值對 之所以會(huì)落入同一個(gè)桶，是因?yàn)樗鼈兊膋ey經(jīng)過哈希計(jì)算后，哈希結(jié)果的低B位(hmap 中的B字段)是相同的，關(guān)于key的定位我們在map的查詢中詳細(xì)說明。在桶內(nèi)，又會(huì)根據(jù) key 計(jì)算出來的 hash 值的高 8 位來決定 key 到底落入桶內(nèi)的哪個(gè)位置（一個(gè)桶內(nèi)最多有8個(gè)位置)。 下面是bmap 結(jié)構(gòu)體的定義，其中tophash是一個(gè)長度為8的數(shù)組（bucketCnt = 1 << bucketCntBits，bucketCntBits=3），用來快速定位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)，在編譯過程中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)過程中會(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對應(yīng)的tophash值

如下的tophash函數(shù)， 就是來計(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)存對齊導(dǎo)致內(nèi)存空間浪費(fèi)，所以Go采用key和value分開存儲(chǔ)的設(shè)計(jì)，更節(jié)省內(nèi)存空間

map 查找

map的查找流程如下：

map 查找流程

• 寫保護(hù)監(jiān)測：
  函數(shù)首先會(huì)檢查 map 底層hmap標(biāo)志位 flags。如果 flags 的寫標(biāo)志位此時(shí)被置 1 了，說明有其他協(xié)程在執(zhí)行“寫”操作，進(jìn)而導(dǎo)致程序 panic，這也說明了 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 是否是在寫的狀態(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)過哈希函數(shù)計(jì)算后，得到的哈希值如下（主流64位機(jī)下共 64 個(gè) bit 位）， 不同類型的key會(huì)有不同的hash函數(shù)

• 找到hash對應(yīng)的bucket：
  bucket定位：key 的hash 值的低B個(gè)bit 位，用來定位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ì)算哈希值對應(yīng)的bucket
// t.bucketsize為一個(gè)bmap的大小，通過對哈希值和桶個(gè)數(shù)取模得到桶編號(hào)，通過對桶編號(hào)和buckets起始地址進(jìn)行運(yùn)算，獲取哈希值對應(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ā)生增長一倍，則舊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ì)算哈希值對應(yīng)的舊bucket
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    // 如果舊bucket的數(shù)據(jù)沒有完成遷移，則使用舊bucket查找
    if !evacuated(oldb) {
        b = oldb
    }
}

• 遍歷查找bucket：
  通過tophash 函數(shù)定位：哈希值的高8個(gè)bit 位，用來快速判斷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 遍歷的無序性

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

• map在遍歷時(shí)，并不是從固定的0號(hào)bucket開始遍歷的，每次遍歷，都會(huì)從一個(gè)隨機(jī)值序號(hào)的bucket，再從其中隨機(jī)的cell開始遍歷
• map遍歷時(shí)，是按序遍歷bucket，同時(shí)按序遍歷bucket中和其overflow bucket中的cell。但是map在擴(kuò)容后，會(huì)發(fā)生key的搬遷，這造成原來落在一個(gè)bucket中的key，搬遷后，有可能會(huì)落到其他bucket中了，從這個(gè)角度看，遍歷map的結(jié)果就不可能是按照原來的順序了

如果想要有序遍歷map，只需對 map中的 key 先排序，再按照 key 的順序遍歷 map

3. 線程安全性

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

• map + 鎖（sync.RWMutex）
• 使用Go自帶的 sync.Map， 該map 支持并發(fā)讀寫安全, 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ā)的方式相比，減少了加鎖對性能的影響。它做了一些優(yōu)化：可以無鎖訪問read map，而且會(huì)優(yōu)先操作read map，倘若只操作read map就可以滿足要求，那就不用去操作write map(dirty)，所以在某些特定場景中它發(fā)生鎖競爭的頻率會(huì)遠(yuǎn)遠(yuǎn)小于map+RWLock的實(shí)現(xiàn)方式

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

適合讀多寫少的場景

缺點(diǎn)：

寫多的場景，會(huì)導(dǎo)致 read map 緩存失效，需要加鎖，沖突變多，性能急劇下降