Golang 中的 map 詳解

一、什么是 map？

1、map 的定義

  在計(jì)算機(jī)科學(xué)里，被稱為相關(guān)數(shù)組、map、符號表或者字典，是由一組 <key, value> 對組成的抽象數(shù)據(jù)結(jié)構(gòu)，并且同一個 key 只會出現(xiàn)一次。

  兩個關(guān)鍵點(diǎn)：map 是由 key-value 對組成的；key 只會出現(xiàn)一次。

  map 的設(shè)計(jì)也被稱為 “The dictionary problem（字典問題）”，它的任務(wù)是設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)用來維護(hù)一個集合的數(shù)據(jù)，并且可以同時對集合進(jìn)行增刪查改的操作。

2、map 的數(shù)據(jù)結(jié)構(gòu)

  最主要的數(shù)據(jù)結(jié)構(gòu)有兩種：哈希查找表（Hash table）、搜索樹（Search tree）。

• 哈希查找表（Hash table）
    哈希查找表使用哈希函數(shù)將 key 分配到不同的桶（bucket，也就是數(shù)組的不同 index），開銷主要在哈希函數(shù)的計(jì)算以及數(shù)組的常數(shù)訪問時間，在很多場景下，哈希查找表的性能很高。

• 搜索樹（Search tree）
    搜索樹一般采用自平衡搜索樹，包括：AVL 樹，紅黑樹。

  哈希查找表的平均查找效率是 O(1)，最差是 O(N)，如果哈希函數(shù)設(shè)計(jì)的很好，最壞的情況基本不會出現(xiàn)。自平衡搜索樹法的最差搜索效率是 O(logN)。遍歷自平衡搜索樹，返回的 key 序列，一般會按照從小到大的順序；而哈希查找表則是亂序的。

二、Golang 中 map 的類型

  Golang 中 map 是一個指針，占用 8 個字節(jié)。當(dāng)使用 make 創(chuàng)建 map 時，底層調(diào)用的是 makemap() 函數(shù)，makemap() 函數(shù)返回的是一個指針，因?yàn)榉祷氐氖侵羔槪?map 作為參數(shù)的時候，函數(shù)內(nèi)部能修改map。

func makemap(t *maptype, hint int, h *hmap) *hmap {}

三、map 的底層實(shí)現(xiàn)

   源碼位于 src\runtime\map.go 中。

  golang 中 map 底層使用的是哈希查找表，用鏈表來解決哈希沖突。每個 map 的底層結(jié)構(gòu)是 hmap，是由若干個結(jié)構(gòu)為 bmap 的 bucket 組成的數(shù)組，每個 bucket 底層都采用鏈表結(jié)構(gòu)。

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

type hmap struct {
	count      int            // map中元素的數(shù)量，調(diào)用len()直接返回此值
	flags      uint8          // 狀態(tài)標(biāo)識符，key和value是否包指針、是否正在擴(kuò)容、是否已經(jīng)被迭代
	B          uint8          // map中桶數(shù)組的數(shù)量，桶數(shù)組的長度的對數(shù)，len(buckets) == 2^B，可以最多容納 6.5 * 2 ^ B 個元素，6.5為裝載因子
	noverflow  uint16         // 溢出桶的大概數(shù)量，當(dāng)B小于16時是準(zhǔn)確值，大于等于16時是大概的值
	hash0      uint32         // 哈希種子，用于計(jì)算哈希值，為哈希函數(shù)的結(jié)果引入一定的隨機(jī)性
	buckets    unsafe.Pointer // 指向桶數(shù)組的指針，長度為 2^B ，如果元素個數(shù)為0，就為 nil
	oldbuckets unsafe.Pointer // 指向一個舊桶數(shù)組，用于擴(kuò)容，它的長度是當(dāng)前桶數(shù)組的一半
	nevacuate  uintptr        // 搬遷進(jìn)度，小于此地址的桶數(shù)組遷移完成
	extra      *mapextra      // 可選字段，用于gc，指向所有的溢出桶，避免gc時掃描整個map，僅掃描所有溢出桶就足夠了
}

// 溢出桶結(jié)構(gòu)
type mapextra struct {
	overflow    *[]*bmap // 指針數(shù)組，指向所有溢出桶
	oldoverflow *[]*bmap // 指針數(shù)組，發(fā)生擴(kuò)容時，指向所有舊的溢出桶
	nextOverflow *bmap // 指向所有溢出桶中下一個可以使用的溢出桶
}

bmap的結(jié)構(gòu)：

type bmap struct {
    tophash [bucketCnt]uint8    // bucketCnt=8，// 存放key哈希值的高8位，用于決定kv鍵值對放在桶內(nèi)的哪個位置
}

//實(shí)際上編輯期間會動態(tài)生成一個新的結(jié)構(gòu)體
type bmap struct {
	topbits  [8]uint8     // 存放key哈希值的高8位，用于決定kv鍵值對放在桶內(nèi)的哪個位置
	keys     [8]keytype   // 存放key的數(shù)組
	values   [8]valuetype // 存放value的數(shù)組
	pad      uintptr      // 用于對齊內(nèi)存
	overflow uintptr      // 指向下一個桶，即溢出桶，拉鏈法
}

  buckets是一個bmap數(shù)組，數(shù)組的長度就是 2^B。每個bucket固定包含8個key和value，實(shí)現(xiàn)上面是一個固定的大小連續(xù)內(nèi)存塊，分成四部分：tophash 值，8個key值，8個value值，指向下個bucket的指針。

  tophash 值用于快速查找key是否在該bucket中，當(dāng)插入和查詢運(yùn)行時都會使用哈希哈數(shù)對key做哈希運(yùn)算，獲取一個hashcode，取高8位存放在bmap tophash字段中。

  桶里面會最多裝 8 個 key，這些 key 之所以會落入同一個桶，是因?yàn)樗鼈兘?jīng)過哈希計(jì)算后，哈希結(jié)果是“一類”的。在桶內(nèi)，又會根據(jù) key 計(jì)算出來的 hash 值的高 8 位來決定 key 到底落入桶內(nèi)的哪個位置（一個桶內(nèi)最多有8個位置）。

  如圖，B=5 表示hmap的有2^5=32個bmap，buckets是一個bmap數(shù)組，其長度為32，每個bmap有8個key。

  桶結(jié)構(gòu)的很多字段得在編譯時才會動態(tài)生成，比如key和values等

  桶結(jié)構(gòu)中，之所以所有的key放一起，所有的value放一起，而不是key/value一對對的一起存放，目的便是在某些情況下可以省去pad字段，節(jié)省內(nèi)存空間。由于內(nèi)存對齊的原因，key0/value0/key1/value1… 這樣的形式可能需要更多的補(bǔ)齊空間，比如 map[int64]int8 ，1字節(jié)的value后面需要補(bǔ)齊7個字節(jié)才能保證下一個key是 int64 對齊的。

  golang中的map使用的內(nèi)存是不會收縮的，只會越用越多。

  每個 bucket 設(shè)計(jì)成最多只能放 8 個 key-value 對，如果有第 9 個 key-value 落入當(dāng)前的 bucket，那就需要再構(gòu)建一個溢出桶 bucket ，通過 overflow 指針連接起來。

四、map 的擴(kuò)容

1、裝載因子（平均每個桶存儲的元素個數(shù)）

  Go的裝載因子閾值常量：6.5，map 最多可容納 6.5*2^B 個元素。

  裝載因子等于 map中元素的個數(shù) / map的容量，即len(map) / 2^B。裝載因子用來表示空閑位置的情況，裝載因子越大，表明空閑位置越少，沖突也越多。隨著裝載因子的增大，哈希表線性探測的平均用時就會增加，這會影響哈希表的性能，當(dāng)裝載因子大于70%，哈希表的性能就會急劇下降，當(dāng)裝載因子達(dá)到100%，整個哈希表就會完全失效，這個時候，查找和插入任意元素的復(fù)雜度都是O(N),因?yàn)樾枰闅v所有元素。

  另外裝載因子與擴(kuò)容、遷移等重新散列(rehash) 行為有直接關(guān)系：

• 在程序運(yùn)行時，會不斷地進(jìn)行插入、刪除等，會導(dǎo)致 bucket 不均，內(nèi)存利用率低，需要遷移。
• 在程序運(yùn)行時，出現(xiàn)裝載因子過大，需要做擴(kuò)容，解決 bucket 過大的問題。

為什么裝載因子是6.5？不是8？不是1？  裝載因子是哈希表中的一個重要指標(biāo)，主要目的是為了平衡 buckets 的存儲空間大小和查找元素時的性能高低。實(shí)際上這是 Go 官方的經(jīng)過認(rèn)真的測試得出的數(shù)字，一起來看看官方的這份測試報(bào)告。包含四個指標(biāo)：

• loadFactor：負(fù)載因子，也叫裝載因子；
• %overflow：溢出率，有溢出 bukcet 的百分比；
• bytes/entry：平均每對 key/alue 的開銷字節(jié)數(shù)；
• hitprobe：查找一個存在的 key 時，要查找的平均個數(shù)；
• missprobe：查找一個不存在的 key 時，要查找的平均個數(shù)。

  Go 官方發(fā)現(xiàn)：裝載因子越大，填入的元素越多，空間利用率就越高，但發(fā)生沖突的幾率就變大；反之，裝數(shù)因子越小，填入的元素越少，沖突發(fā)生的幾率減小，但空間利用率低，而且還會提高擴(kuò)容操作的次數(shù)。

  根據(jù)這份測試結(jié)果和討論，Go 官方取了一個相對適中的值，把 Go 中的 map 的負(fù)數(shù)因子硬編碼為 6.5，這就是 6.5 的選擇緣由。這意味著在 Go 語言中，當(dāng) map存儲的元素個數(shù)大于或等于 6.5*桶個數(shù) 時，就會發(fā)擴(kuò)容行為。

2、觸發(fā) map 擴(kuò)容的時機(jī)（插入、刪除key）

• 當(dāng)裝載因子超過6.5時，擴(kuò)容一倍，屬于增量擴(kuò)容；
• 當(dāng)使用的溢出桶過多時，重新分配一樣大的內(nèi)存空間，屬于等量擴(kuò)容；
  （實(shí)際上沒有擴(kuò)容，主要是為了回收空閑的溢出桶，節(jié)省空間，提高 map 的查找和插入效率）

為什么會出現(xiàn)這種情況？
  這種情況可能是因?yàn)閙ap刪除的特性導(dǎo)致的。當(dāng)我們不斷向哈希表中插入數(shù)據(jù)，并且將他們又全部刪除時，其內(nèi)存占用并不會減少，因?yàn)閯h除只是將桶對應(yīng)位置的tophash置nil而已。
  這種情況下，就會不斷的積累溢出桶造成內(nèi)存泄露，為了解決這種情況，采用了等量擴(kuò)容的機(jī)制，一旦哈希表中出現(xiàn)了過多的溢出桶，會創(chuàng)建新桶保存數(shù)據(jù)，gc會清理掉老的溢出桶，從而避免內(nèi)存泄露。

如何定義溢出桶是否太多需要等量擴(kuò)容呢？兩種情況：

• 當(dāng)B小于15時，溢出桶的數(shù)量超過2^B，屬于溢出桶數(shù)量太多，需要等量擴(kuò)容；
• 當(dāng)B大于等于15時，溢出桶數(shù)量超過2^15，屬于溢出桶數(shù)量太多，需要等量擴(kuò)容。

3、擴(kuò)容策略（怎么擴(kuò)容？）

  Go 會創(chuàng)建一個新的 buckets 數(shù)組，新的 buckets 數(shù)組的容量是舊buckets數(shù)組的兩倍（或者和舊桶容量相同），將原始桶數(shù)組中的所有元素重新散列到新的桶數(shù)組中。這樣做的目的是為了使每個桶中的元素?cái)?shù)量盡可能平均分布，以提高查詢效率。舊的buckets數(shù)組不會被直接刪除，而是會把原來對舊數(shù)組的引用去掉，讓GC來清除內(nèi)存。

  在map進(jìn)行擴(kuò)容遷移的期間，不會觸發(fā)第二次擴(kuò)容。只有在前一個擴(kuò)容遷移工作完成后，map才能進(jìn)行下一次擴(kuò)容操作。

4、搬遷策略

  由于map擴(kuò)容需要將原有的kv鍵值對搬遷到新的內(nèi)存地址，如果一下子全部搬完，會非常的影響性能。go 中 map 的擴(kuò)容采用漸進(jìn)式的搬遷策略，原有的 key 并不會一次性搬遷完畢，一次性搬遷會造成比較大的延時，每次最多只會搬遷 2 個 bucket，將搬遷的O(N)開銷均攤到O(1)的賦值和刪除操作上。

  上面說的 hashGrow() 函數(shù)實(shí)際上并沒有真正地“搬遷”，它只是分配好了新的 buckets，并將老的 buckets 掛到了 oldbuckets 字段上。真正搬遷 buckets 的動作在 growWork() 函數(shù)中，而調(diào)用 growWork() 函數(shù)的動作是在 mapassign 和 mapdelete 函數(shù)中。也就是插入或修改、刪除 key 的時候，都會嘗試進(jìn)行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢，具體來說就是檢查 oldbuckets 是否為 nil。

五、解決哈希沖突

1、開放尋址法

  如果發(fā)生哈希沖突，從發(fā)生沖突的那個單元起，按一定的次序，不斷重復(fù)，從哈希表中尋找一個空閑的單元，將該鍵值對存儲在該單元中。具體的實(shí)現(xiàn)方式包括線性探測法、平方探測法、隨機(jī)探測法和雙重哈希法等。開放尋址法需要的表長度要大于等于所需要存放的元素?cái)?shù)量。

2、鏈地址法

  基于數(shù)組 + 鏈表 實(shí)現(xiàn)哈希表，數(shù)組中每個元素都是一個鏈表，將每個桶都指向一個鏈表，當(dāng)哈希沖突發(fā)生時，新的鍵值對會按順序添加到該桶對應(yīng)的鏈表的尾部。在查找特定鍵值對時，可以遍歷該鏈表以查找與之匹配的鍵值對。

3、兩種方案的比較

• 內(nèi)存利用率
    對于鏈地址法，基于 數(shù)組 + 鏈表 進(jìn)行存儲，鏈表節(jié)點(diǎn)可以在需要時再創(chuàng)建，開放尋址法需要事先申請好足夠內(nèi)存，因此鏈地址法對內(nèi)存的利用率高。
• 適用場景
    鏈地址法對裝載因子的容忍度會更高，適合存儲大對象、大數(shù)據(jù)量的哈希表，而且相較于開放尋址法，它更加靈活，支持更多的優(yōu)化策略，比如可采用紅黑樹代替鏈表。但是鏈地址法需要額外的空間來存儲指針。
    對于開放尋址法，它只有數(shù)組一種數(shù)據(jù)結(jié)構(gòu)就可完成存儲，繼承了數(shù)組的優(yōu)點(diǎn)，對CPU緩存友好，易于序列化操作，但是它對內(nèi)存的利用率不高，且發(fā)生沖突時代價更高。當(dāng)數(shù)據(jù)量明確、裝載因子小，適合采用開放尋址法。

總結(jié) 

到此這篇關(guān)于Golang中的map操作方法的文章就介紹到這了,更多相關(guān)Golang中map詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論