Golang 中的 map 詳解

一、什么是 map？

1、map 的定義

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

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

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

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

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

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

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

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

二、Golang 中 map 的類型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、map 的擴(kuò)容

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

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

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

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

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

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

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

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

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

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

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

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

如何定義溢出桶是否太多需要等量擴(kuò)容呢？?jī)煞N情況：

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

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

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

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

4、搬遷策略

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

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

五、解決哈希沖突

1、開(kāi)放尋址法

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

2、鏈地址法

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

3、兩種方案的比較

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

總結(jié) 

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

最新評(píng)論