一、概述

在golang中map類型是實(shí)際開發(fā)過程中經(jīng)常使用到的數(shù)據(jù)類型，比如在微服務(wù)框架中存放[client,service]這樣的映射汁展，還有在實(shí)現(xiàn)長連接通信[client_id,connection]昙啄，再例如rpc框架中[service_id, service_impl]等等。在其實(shí)際的定義中：

• 1获三、底層
  map實(shí)際上是一個(gè)hashtable旁蔼，存放的數(shù)據(jù)是被放置到一個(gè)數(shù)組buckets.每個(gè)bucket最多能夠存放8個(gè)key/value對(duì)锨苏。而對(duì)應(yīng)的數(shù)據(jù)則根據(jù)其hash(key)的bits低階位來選擇對(duì)應(yīng)的bucket，而對(duì)應(yīng)的高階位則用來區(qū)分在同一個(gè)bucket中不同的key-value內(nèi)容棺聊。一旦當(dāng)前的bucket里面的鍵值對(duì)個(gè)數(shù)超過8個(gè)伞租，則會(huì)通過鏈表的方式拓展其他的bucket。
• 2限佩、擴(kuò)容
  當(dāng)hashtable增長需要擴(kuò)容時(shí)葵诈，則通過分配一個(gè)容量是當(dāng)數(shù)組buckets兩倍的新數(shù)組來存放鍵值對(duì)，并將舊的buckets中的key-value逐步copy到新的buckets中犀暑。需要注意一點(diǎn)：當(dāng)map進(jìn)行擴(kuò)容時(shí)其對(duì)應(yīng)的iterator遍歷舊的table驯击，同時(shí)也會(huì)檢查新的table，防止對(duì)應(yīng)的bucket移到新的table中耐亏。
• 3徊都、查詢
  可以通過Map iterator遍歷buckets數(shù)組，按照遍歷的順序返回keys(當(dāng)前bucket--->chain序號(hào)[當(dāng)存放鍵值對(duì)>8個(gè)時(shí)會(huì)以鏈表的存放到擴(kuò)展的bucket]--->bucket索引)广辰，在實(shí)現(xiàn)map iterator為了保證其iterator語義暇矫，并不會(huì)在bucket中移動(dòng)keys，一旦這樣做了則會(huì)導(dǎo)致keys會(huì)被獲取到0次或2次择吊。
• 4李根、負(fù)載系數(shù)
  在實(shí)際的應(yīng)用我們會(huì)面臨一個(gè)問題：當(dāng)table出現(xiàn)太多overflow情況就需要擴(kuò)展更多的bucket來支撐，反之几睛，若是太小的話又會(huì)造成空間的浪費(fèi)房轿。
  接下來我們先通過源碼了解下map的實(shí)現(xiàn)。

二所森、源碼

type hmap struct {
    count     int // 元素格式
    flags     uint8
    B      uint8  // 包含的buckets數(shù)loadFactor * 2^B items)
    noverflow uint16 // overflow時(shí)拓展的buckets數(shù)
    hash0     uint32 // hash種子

    buckets    unsafe.Pointer // buckets數(shù)組指針
    oldbuckets unsafe.Pointer // 擴(kuò)容時(shí)用于復(fù)制的數(shù)組
    nevacuate  uintptr   // 擴(kuò)容時(shí)copy到新table的buckets數(shù)

    extra *mapextra // 可選(見下文)
}

首先呢囱持，map是一個(gè)由若干個(gè)bucket(對(duì)應(yīng)bmap)組成的數(shù)組，并且每個(gè)bucket存放不超過8個(gè)鍵值對(duì)key-value的元素焕济，則由key通過哈希算法將其歸入不同的bucket中纷妆。一旦某個(gè)bucket中元素超過8個(gè)元素就會(huì)觸發(fā)overflow，hmap則通過extra字段對(duì)應(yīng)的mapextra的overflow字段來拓展該bucket晴弃。

bmap結(jié)構(gòu):bmap就是前面在hmap中提到的bucket

type bmap struct {  
    tophash [bucketCnt]uint8
}

從源碼可以了解到tophash包含了在一個(gè)bucket中每個(gè)key對(duì)應(yīng)的hash值的高階位部分掩幢，一旦tophash[0] < minTopHash則tophash[0]就變成evacuation狀態(tài)。
在這里tophash通過記錄當(dāng)前bucket中8個(gè)key的hash值的高8位上鞠，在每次查找對(duì)應(yīng)的key時(shí)不需要做全等判斷际邻，提高查找速度。
在每個(gè)bucket(bmap)中存放的數(shù)據(jù)格式：key1key2...keynval1val2...valn芍阎，將所有的keys放置到一起枯怖，再將所有的values放置到一起，相對(duì)于以交替方式存放key能曾、value：key1/val1/key2/val2/.../.../keyn/valn/要復(fù)雜的多度硝；不過通過這種方式能夠在key和value長度不同時(shí)肿轨，能夠節(jié)省padding的空間，比如定義map[int64]int8蕊程，相鄰的4個(gè)int8能夠存放到一個(gè)內(nèi)存單元椒袍，若是使用key、value交替則會(huì)導(dǎo)致每個(gè)int8會(huì)被padding占用單獨(dú)的內(nèi)存單元.

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

整個(gè)hmap不僅包含一個(gè)tophash藻茂，還包括8個(gè)鍵值對(duì)和一個(gè)overflow指針驹暑，這樣使得overflow以鏈表的結(jié)構(gòu)出現(xiàn)，一般都是通過指針來訪問鍵值對(duì)和overflow的內(nèi)容辨赐。

mapextra結(jié)構(gòu)源碼：主要用于當(dāng)bukcets元素超過8個(gè)鍵值對(duì)時(shí)优俘，通過鏈表的方式來解決對(duì)應(yīng)的內(nèi)容放置。其包含了map上不存在的fields掀序。

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

    nextOverflow *bmap//指向下一個(gè)overflow的bucket
}

詳見：runtime/map.go源碼

三帆焕、實(shí)例

測(cè)試代碼如下：

var intMap map[int]int
var cnt = 8192

func main() {
    printMemStats() //打印出memory情況

    initMap()  // 創(chuàng)建map
    runtime.GC()  // 強(qiáng)制執(zhí)行GC
    printMemStats() // 在強(qiáng)制GC之后 再打印memory情況

    log.Println(len(intMap))  // 查看map的元素個(gè)數(shù)
    for i := 0; i < cnt; i++ {
        delete(intMap, i) // 執(zhí)行delete的操作
    }
    log.Println(len(intMap)) // 驗(yàn)證執(zhí)行delete操作對(duì)實(shí)際map的元素個(gè)數(shù)影響

    runtime.GC()  // 強(qiáng)制執(zhí)行GC
    printMemStats()

    intMap = nil  // 將map置為nil 釋放其占用的內(nèi)存空間
    runtime.GC()
    printMemStats()
}

func initMap() {
    intMap = make(map[int]int, cnt)

    for i := 0; i < cnt; i++ {
        intMap[i] = i
    }
}

func printMemStats() {
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    log.Printf("Alloc = %v TotalAlloc = %v Sys = %v NumGC = %v\n", m.Alloc/1024, m.TotalAlloc/1024, m.Sys/1024, m.NumGC)
}

輸出結(jié)果

2019/03/19 10:17:17 Alloc = 128 TotalAlloc = 128 Sys = 4868 NumGC = 0
2019/03/19 10:17:17 Alloc = 449 TotalAlloc = 500 Sys = 6338 NumGC = 1
2019/03/19 10:17:17 8192
2019/03/19 10:17:17 0
2019/03/19 10:17:17 Alloc = 451 TotalAlloc = 503 Sys = 6402 NumGC = 2
2019/03/19 10:17:17 Alloc = 138 TotalAlloc = 504 Sys = 6402 NumGC = 3

結(jié)論如下：

• NumGC 是垃圾回收次數(shù)；Alloc 是對(duì)對(duì)象大小不恭，單位是 KB叶雹；Sys 是從 OS 獲取的內(nèi)存大小，單位是 KB换吧；
• 第一行折晦，沒有進(jìn)行過 GC，默認(rèn)真用了 100 KB 的內(nèi)存沾瓦；
• map初始化完成之后進(jìn)行一次 GC满着，此時(shí)內(nèi)存占了 422 KB；
• 接下來就是執(zhí)行delete操作贯莺，可以看到map已經(jīng)被清空了漓滔，也執(zhí)行了一次 GC，但是內(nèi)存沒有被釋放乖篷；
• 最后把map置為空，內(nèi)存才被釋放透且。

四撕蔼、優(yōu)化

1、刪除

delete對(duì)應(yīng)的源碼

從源碼中可以看到：外層的循環(huán)就是在遍歷整個(gè) map秽誊，刪除的核心就在那個(gè)empty鲸沮。它修改了當(dāng)前 key 的標(biāo)記，而不是直接刪除了內(nèi)存里面的數(shù)據(jù)【只是標(biāo)記為empty锅论，并沒有真正刪除其對(duì)應(yīng)的數(shù)據(jù)】

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
        ...省略代碼
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            b.tophash[i] = empty
            h.count--
        }
    }
     ...省略代碼
}

需要注意：若是用map做緩存讼溺，而每次更新只是部分更新，更新的 key 如果偏差比較大最易，有可能會(huì)有內(nèi)存逐漸增長而不釋放的問題怒坯。
不過很多人可能很奇怪為嘛要以這種方式來設(shè)計(jì)map的刪除操作呢：在遍歷map的時(shí)候刪除里面的元素炫狱，頁可以刪除沒有遍歷到的元素，那么為了保證刪除了之后遍歷不發(fā)生異常剔猿，是不能將對(duì)應(yīng)位置空間釋放掉會(huì)觸發(fā)panic视译。那么這算不算內(nèi)存泄漏呢？
若是后續(xù)繼續(xù)對(duì)當(dāng)前的map進(jìn)行write操作归敬，寫入的值剛好命中前面已被“刪除”的bucket酷含，則會(huì)將當(dāng)面bucket的empty內(nèi)容進(jìn)行覆蓋。在這一點(diǎn)上是不能算內(nèi)存泄漏的汪茧。
在實(shí)際一些高性能椅亚、高并發(fā)的場景下，使用map來用來內(nèi)存存儲(chǔ)可能會(huì)帶來一些挑戰(zhàn)舱污，我們可能使用如下的方式來進(jìn)行map的優(yōu)化：

• 1呀舔、去除無用、重復(fù)的存儲(chǔ)使用
• 2、盡量少用map或map的value盡量少為指針奔脐，太多的指針類型會(huì)造成GC掃描時(shí)間的增加铜幽；
• 3、若是用map用作緩存存儲(chǔ)省古，當(dāng)每次只更新部分，更新的key若是偏差較大丧失，會(huì)有可能造成內(nèi)存逐漸增長而不釋放的問題豺妓，可以通過定時(shí)拷貝map的方式來解決，數(shù)十萬的int64內(nèi)存拷貝<100ms的布讹。^_
• 4琳拭、釋放map所占的內(nèi)存 則通過map=nil

2、查詢

訪問map中key源碼

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
        ...省略部分源碼
    // do some race detect things
    // do some memory sanitizer thins
 
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0])
    }
    if h.flags&hashWriting != 0 {  // 檢測(cè)是否并發(fā)寫描验，map不是gorountine安全的
        throw("concurrent map read and map write")
    }
    alg := t.key.alg  // 哈希算法 alg -> algorithm
    hash := alg.hash(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
        // 如果老的bucket沒有被移動(dòng)完白嘁，那么去老的bucket中尋找
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // There used to be half as many buckets; mask down one more power of two.
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
        // 尋找過程：不斷比對(duì)tophash和key
    top := tophash(hash)

        ...省略部分源碼

    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))
            if t.indirectkey {
                k = *((*unsafe.Pointer)(k))
            }
            if alg.equal(key, k) {
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                if t.indirectvalue {
                    v = *((*unsafe.Pointer)(v))
                }
                return v
            }
        }
    }
        return unsafe.Pointer(&zeroVal[0])
}

常見問題

Q：刪除掉map中的元素是否會(huì)釋放內(nèi)存？
A：不會(huì)膘流，刪除操作僅僅將對(duì)應(yīng)的tophash[i]設(shè)置為empty絮缅，并非釋放內(nèi)存。若要釋放內(nèi)存只能等待指針無引用后被系統(tǒng)gc

Q：如何并發(fā)地使用map呼股？
A：map不是goroutine安全的耕魄，所以在有多個(gè)gorountine對(duì)map進(jìn)行寫操作是會(huì)panic。多gorountine讀寫map是應(yīng)加鎖（RWMutex）彭谁，或使用sync.Map（不過不太推薦使用）

Q：map的iterator是否安全吸奴？
A：map的delete并非真的delete，所以對(duì)迭代器是沒有影響的，是安全的则奥。

參考文章

golang map源碼詳解
Golang map 如何進(jìn)行刪除操作考润？