本文目錄如下，閱讀本文后，將一網(wǎng)打盡下面Golang Map相關(guān)面試題
我們提供的服務(wù)有：網(wǎng)站建設(shè)、網(wǎng)站制作、微信公眾號(hào)開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、紫金ssl等。為成百上千家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的紫金網(wǎng)站制作公司
Go中的map是一個(gè)指針，占用8個(gè)字節(jié)，指向hmap結(jié)構(gòu)體; 源碼 src/runtime/map.go 中可以看到map的底層結(jié)構(gòu)
每個(gè)map的底層結(jié)構(gòu)是hmap，hmap包含若干個(gè)結(jié)構(gòu)為bmap的bucket數(shù)組。每個(gè)bucket底層都采用鏈表結(jié)構(gòu)。接下來，我們來詳細(xì)看下map的結(jié)構(gòu)
bmap 就是我們常說的“桶”，一個(gè)桶里面會(huì)最多裝 8 個(gè) key，這些 key 之所以會(huì)落入同一個(gè)桶，是因?yàn)樗鼈兘?jīng)過哈希計(jì)算后，哈希結(jié)果是“一類”的，關(guān)于key的定位我們?cè)趍ap的查詢和插入中詳細(xì)說明。在桶內(nèi)，又會(huì)根據(jù) key 計(jì)算出來的 hash 值的高 8 位來決定 key 到底落入桶內(nèi)的哪個(gè)位置（一個(gè)桶內(nèi)最多有8個(gè)位置)。
bucket內(nèi)存數(shù)據(jù)結(jié)構(gòu)可視化如下：
注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding字段，節(jié)省內(nèi)存空間。
當(dāng) map 的 key 和 value 都不是指針，并且 size 都小于 128 字節(jié)的情況下，會(huì)把 bmap 標(biāo)記為不含指針，這樣可以避免 gc 時(shí)掃描整個(gè) hmap。但是，我們看 bmap 其實(shí)有一個(gè) overflow 的字段，是指針類型的，破壞了 bmap 不含指針的設(shè)想，這時(shí)會(huì)把 overflow 移動(dòng)到 extra 字段來。
map是個(gè)指針，底層指向hmap，所以是個(gè)引用類型
golang 有三個(gè)常用的高級(jí)類型 slice 、map、channel, 它們都是 引用類型 ，當(dāng)引用類型作為函數(shù)參數(shù)時(shí)，可能會(huì)修改原內(nèi)容數(shù)據(jù)。
golang 中沒有引用傳遞，只有值和指針傳遞。所以 map 作為函數(shù)實(shí)參傳遞時(shí)本質(zhì)上也是值傳遞，只不過因?yàn)?map 底層數(shù)據(jù)結(jié)構(gòu)是通過指針指向?qū)嶋H的元素存儲(chǔ)空間，在被調(diào)函數(shù)中修改 map，對(duì)調(diào)用者同樣可見，所以 map 作為函數(shù)實(shí)參傳遞時(shí)表現(xiàn)出了引用傳遞的效果。
因此，傳遞 map 時(shí)，如果想修改map的內(nèi)容而不是map本身，函數(shù)形參無需使用指針
map 底層數(shù)據(jù)結(jié)構(gòu)是通過指針指向?qū)嶋H的元素 存儲(chǔ)空間 ，這種情況下，對(duì)其中一個(gè)map的更改，會(huì)影響到其他map
map 在沒有被修改的情況下，使用 range 多次遍歷 map 時(shí)輸出的 key 和 value 的順序可能不同。這是 Go 語言的設(shè)計(jì)者們有意為之，在每次 range 時(shí)的順序被隨機(jī)化，旨在提示開發(fā)者們，Go 底層實(shí)現(xiàn)并不保證 map 遍歷順序穩(wěn)定，請(qǐng)大家不要依賴 range 遍歷結(jié)果順序。
map 本身是無序的，且遍歷時(shí)順序還會(huì)被隨機(jī)化，如果想順序遍歷 map，需要對(duì) map key 先排序，再按照 key 的順序遍歷 map。
map默認(rèn)是并發(fā)不安全的，原因如下：
Go 官方在經(jīng)過了長時(shí)間的討論后，認(rèn)為 Go map 更應(yīng)適配典型使用場(chǎng)景（不需要從多個(gè) goroutine 中進(jìn)行安全訪問），而不是為了小部分情況（并發(fā)訪問），導(dǎo)致大部分程序付出加鎖代價(jià)（性能），決定了不支持。
場(chǎng)景: 2個(gè)協(xié)程同時(shí)讀和寫，以下程序會(huì)出現(xiàn)致命錯(cuò)誤：fatal error: concurrent map writes
如果想實(shí)現(xiàn)map線程安全，有兩種方式：
方式一：使用讀寫鎖 map + sync.RWMutex
方式二：使用golang提供的 sync.Map
sync.map是用讀寫分離實(shí)現(xiàn)的，其思想是空間換時(shí)間。和map+RWLock的實(shí)現(xiàn)方式相比，它做了一些優(yōu)化：可以無鎖訪問read map，而且會(huì)優(yōu)先操作read map，倘若只操作read map就可以滿足要求(增刪改查遍歷)，那就不用去操作write map(它的讀寫都要加鎖)，所以在某些特定場(chǎng)景中它發(fā)生鎖競(jìng)爭(zhēng)的頻率會(huì)遠(yuǎn)遠(yuǎn)小于map+RWLock的實(shí)現(xiàn)方式。
golang中map是一個(gè)kv對(duì)集合。底層使用hash table，用鏈表來解決沖突 ，出現(xiàn)沖突時(shí)，不是每一個(gè)key都申請(qǐng)一個(gè)結(jié)構(gòu)通過鏈表串起來，而是以bmap為最小粒度掛載，一個(gè)bmap可以放8個(gè)kv。在哈希函數(shù)的選擇上，會(huì)在程序啟動(dòng)時(shí)，檢測(cè) cpu 是否支持 aes，如果支持，則使用 aes hash，否則使用 memhash。
map有3鐘初始化方式，一般通過make方式創(chuàng)建
map的創(chuàng)建通過生成匯編碼可以知道，make創(chuàng)建map時(shí)調(diào)用的底層函數(shù)是 runtime.makemap 。如果你的map初始容量小于等于8會(huì)發(fā)現(xiàn)走的是 runtime.fastrand 是因?yàn)槿萘啃∮?時(shí)不需要生成多個(gè)桶，一個(gè)桶的容量就可以滿足
makemap函數(shù)會(huì)通過 fastrand 創(chuàng)建一個(gè)隨機(jī)的哈希種子，然后根據(jù)傳入的 hint 計(jì)算出需要的最小需要的桶的數(shù)量，最后再使用 makeBucketArray 創(chuàng)建用于保存桶的數(shù)組，這個(gè)方法其實(shí)就是根據(jù)傳入的 B 計(jì)算出的需要?jiǎng)?chuàng)建的桶數(shù)量在內(nèi)存中分配一片連續(xù)的空間用于存儲(chǔ)數(shù)據(jù)，在創(chuàng)建桶的過程中還會(huì)額外創(chuàng)建一些用于保存溢出數(shù)據(jù)的桶，數(shù)量是 2^(B-4) 個(gè)。初始化完成返回hmap指針。
找到一個(gè) B，使得 map 的裝載因子在正常范圍內(nèi)
Go 語言中讀取 map 有兩種語法：帶 comma 和 不帶 comma。當(dāng)要查詢的 key 不在 map 里，帶 comma 的用法會(huì)返回一個(gè) bool 型變量提示 key 是否在 map 中；而不帶 comma 的語句則會(huì)返回一個(gè) value 類型的零值。如果 value 是 int 型就會(huì)返回 0，如果 value 是 string 類型，就會(huì)返回空字符串。
map的查找通過生成匯編碼可以知道，根據(jù) key 的不同類型，編譯器會(huì)將查找函數(shù)用更具體的函數(shù)替換，以優(yōu)化效率：
函數(shù)首先會(huì)檢查 map 的標(biāo)志位 flags。如果 flags 的寫標(biāo)志位此時(shí)被置 1 了，說明有其他協(xié)程在執(zhí)行“寫”操作，進(jìn)而導(dǎo)致程序 panic。這也說明了 map 對(duì)協(xié)程是不安全的。
key經(jīng)過哈希函數(shù)計(jì)算后，得到的哈希值如下（主流64位機(jī)下共 64 個(gè) bit 位）：
m: 桶的個(gè)數(shù)
從buckets 通過 hash m 得到對(duì)應(yīng)的bucket，如果bucket正在擴(kuò)容，并且沒有擴(kuò)容完成，則從oldbuckets得到對(duì)應(yīng)的bucket
計(jì)算hash所在桶編號(hào)：
用上一步哈希值最后的 5 個(gè) bit 位，也就是 01010 ，值為 10，也就是 10 號(hào)桶（范圍是0~31號(hào)桶）
計(jì)算hash所在的槽位:
用上一步哈希值哈希值的高8個(gè)bit 位，也就是 10010111 ，轉(zhuǎn)化為十進(jìn)制，也就是151，在 10 號(hào) bucket 中尋找** tophash 值（HOB hash）為 151* 的 槽位**，即為key所在位置，找到了 2 號(hào)槽位，這樣整個(gè)查找過程就結(jié)束了。
如果在 bucket 中沒找到，并且 overflow 不為空，還要繼續(xù)去 overflow bucket 中尋找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。
通過上面找到了對(duì)應(yīng)的槽位，這里我們?cè)僭敿?xì)分析下key/value值是如何獲取的：
bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 個(gè) key 的地址就要在此基礎(chǔ)上跨過 i 個(gè) key 的大??；而我們又知道，value 的地址是在所有 key 之后，因此第 i 個(gè) value 的地址還需要加上所有 key 的偏移。
通過匯編語言可以看到，向 map 中插入或者修改 key，最終調(diào)用的是 mapassign 函數(shù)。
實(shí)際上插入或修改 key 的語法是一樣的，只不過前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中。
mapassign 有一個(gè)系列的函數(shù)，根據(jù) key 類型的不同，編譯器會(huì)將其優(yōu)化為相應(yīng)的“快速函數(shù)”。
我們只用研究最一般的賦值函數(shù) mapassign 。
map的賦值會(huì)附帶著map的擴(kuò)容和遷移，map的擴(kuò)容只是將底層數(shù)組擴(kuò)大了一倍，并沒有進(jìn)行數(shù)據(jù)的轉(zhuǎn)移，數(shù)據(jù)的轉(zhuǎn)移是在擴(kuò)容后逐步進(jìn)行的，在遷移的過程中每進(jìn)行一次賦值（access或者delete）會(huì)至少做一次遷移工作。
1.判斷map是否為nil
每一次進(jìn)行賦值/刪除操作時(shí)，只要oldbuckets != nil 則認(rèn)為正在擴(kuò)容，會(huì)做一次遷移工作，下面會(huì)詳細(xì)說下遷移過程
根據(jù)上面查找過程，查找key所在位置，如果找到則更新，沒找到則找空位插入即可
經(jīng)過前面迭代尋找動(dòng)作，若沒有找到可插入的位置，意味著需要擴(kuò)容進(jìn)行插入，下面會(huì)詳細(xì)說下擴(kuò)容過程
通過匯編語言可以看到，向 map 中刪除 key，最終調(diào)用的是 mapdelete 函數(shù)
刪除的邏輯相對(duì)比較簡(jiǎn)單，大多函數(shù)在賦值操作中已經(jīng)用到過，核心還是找到 key 的具體位置。尋找過程都是類似的，在 bucket 中挨個(gè) cell 尋找。找到對(duì)應(yīng)位置后，對(duì) key 或者 value 進(jìn)行“清零”操作，將 count 值減 1，將對(duì)應(yīng)位置的 tophash 值置成 Empty
再來說觸發(fā) map 擴(kuò)容的時(shí)機(jī)：在向 map 插入新 key 的時(shí)候，會(huì)進(jìn)行條件檢測(cè)，符合下面這 2 個(gè)條件，就會(huì)觸發(fā)擴(kuò)容：
1、裝載因子超過閾值
源碼里定義的閾值是 6.5 (loadFactorNum/loadFactorDen)，是經(jīng)過測(cè)試后取出的一個(gè)比較合理的因子
我們知道，每個(gè) bucket 有 8 個(gè)空位，在沒有溢出，且所有的桶都裝滿了的情況下，裝載因子算出來的結(jié)果是 8。因此當(dāng)裝載因子超過 6.5 時(shí)，表明很多 bucket 都快要裝滿了，查找效率和插入效率都變低了。在這個(gè)時(shí)候進(jìn)行擴(kuò)容是有必要的。
對(duì)于條件 1，元素太多，而 bucket 數(shù)量太少，很簡(jiǎn)單：將 B 加 1，bucket 最大數(shù)量( 2^B )直接變成原來 bucket 數(shù)量的 2 倍。于是，就有新老 bucket 了。注意，這時(shí)候元素都在老 bucket 里，還沒遷移到新的 bucket 來。新 bucket 只是最大數(shù)量變?yōu)樵瓉碜畲髷?shù)量的 2 倍( 2^B * 2 ) 。
2、overflow 的 bucket 數(shù)量過多
在裝載因子比較小的情況下，這時(shí)候 map 的查找和插入效率也很低，而第 1 點(diǎn)識(shí)別不出來這種情況。表面現(xiàn)象就是計(jì)算裝載因子的分子比較小，即 map 里元素總數(shù)少，但是 bucket 數(shù)量多（真實(shí)分配的 bucket 數(shù)量多，包括大量的 overflow bucket）
不難想像造成這種情況的原因：不停地插入、刪除元素。先插入很多元素，導(dǎo)致創(chuàng)建了很多 bucket，但是裝載因子達(dá)不到第 1 點(diǎn)的臨界值，未觸發(fā)擴(kuò)容來緩解這種情況。之后，刪除元素降低元素總數(shù)量，再插入很多元素，導(dǎo)致創(chuàng)建很多的 overflow bucket，但就是不會(huì)觸發(fā)第 1 點(diǎn)的規(guī)定，你能拿我怎么辦？overflow bucket 數(shù)量太多，導(dǎo)致 key 會(huì)很分散，查找插入效率低得嚇人，因此出臺(tái)第 2 點(diǎn)規(guī)定。這就像是一座空城，房子很多，但是住戶很少，都分散了，找起人來很困難
對(duì)于條件 2，其實(shí)元素沒那么多，但是 overflow bucket 數(shù)特別多，說明很多 bucket 都沒裝滿。解決辦法就是開辟一個(gè)新 bucket 空間，將老 bucket 中的元素移動(dòng)到新 bucket，使得同一個(gè) bucket 中的 key 排列地更緊密。這樣，原來，在 overflow bucket 中的 key 可以移動(dòng)到 bucket 中來。結(jié)果是節(jié)省空間，提高 bucket 利用率，map 的查找和插入效率自然就會(huì)提升。
由于 map 擴(kuò)容需要將原有的 key/value 重新搬遷到新的內(nèi)存地址，如果有大量的 key/value 需要搬遷，會(huì)非常影響性能。因此 Go map 的擴(kuò)容采取了一種稱為“漸進(jìn)式”的方式，原有的 key 并不會(huì)一次性搬遷完畢，每次最多只會(huì)搬遷 2 個(gè) bucket。
上面說的 hashGrow() 函數(shù)實(shí)際上并沒有真正地“搬遷”，它只是分配好了新的 buckets，并將老的 buckets 掛到了 oldbuckets 字段上。真正搬遷 buckets 的動(dòng)作在 growWork() 函數(shù)中，而調(diào)用 growWork() 函數(shù)的動(dòng)作是在 mapassign 和 mapdelete 函數(shù)中。也就是插入或修改、刪除 key 的時(shí)候，都會(huì)嘗試進(jìn)行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢，具體來說就是檢查 oldbuckets 是否為 nil。
如果未遷移完畢，賦值/刪除的時(shí)候，擴(kuò)容完畢后（預(yù)分配內(nèi)存），不會(huì)馬上就進(jìn)行遷移。而是采取 增量擴(kuò)容 的方式，當(dāng)有訪問到具體 bukcet 時(shí)，才會(huì)逐漸的進(jìn)行遷移（將 oldbucket 遷移到 bucket）
nevacuate 標(biāo)識(shí)的是當(dāng)前的進(jìn)度，如果都搬遷完，應(yīng)該和2^B的長度是一樣的
在evacuate 方法實(shí)現(xiàn)是把這個(gè)位置對(duì)應(yīng)的bucket，以及其沖突鏈上的數(shù)據(jù)都轉(zhuǎn)移到新的buckets上。
轉(zhuǎn)移的判斷直接通過tophash 就可以，判斷tophash中第一個(gè)hash值即可
遍歷的過程，就是按順序遍歷 bucket，同時(shí)按順序遍歷 bucket 中的 key。
map遍歷是無序的，如果想實(shí)現(xiàn)有序遍歷，可以先對(duì)key進(jìn)行排序
為什么遍歷 map 是無序的？
如果發(fā)生過遷移，key 的位置發(fā)生了重大的變化，有些 key 飛上高枝，有些 key 則原地不動(dòng)。這樣，遍歷 map 的結(jié)果就不可能按原來的順序了。
如果就一個(gè)寫死的 map，不會(huì)向 map 進(jìn)行插入刪除的操作，按理說每次遍歷這樣的 map 都會(huì)返回一個(gè)固定順序的 key/value 序列吧。但是 Go 杜絕了這種做法，因?yàn)檫@樣會(huì)給新手程序員帶來誤解，以為這是一定會(huì)發(fā)生的事情，在某些情況下，可能會(huì)釀成大錯(cuò)。
Go 做得更絕，當(dāng)我們?cè)诒闅v map 時(shí)，并不是固定地從 0 號(hào) bucket 開始遍歷，每次都是從一個(gè)**隨機(jī)值序號(hào)的 bucket 開始遍歷，并且是從這個(gè) bucket 的一個(gè) 隨機(jī)序號(hào)的 cell **開始遍歷。這樣，即使你是一個(gè)寫死的 map，僅僅只是遍歷它，也不太可能會(huì)返回一個(gè)固定序列的 key/value 對(duì)了。
golang 中 map的實(shí)現(xiàn)結(jié)構(gòu)為： 哈希表 + 鏈表。 其中鏈表，作用是當(dāng)發(fā)生hash沖突時(shí)，拉鏈法生成的結(jié)點(diǎn)。
可以看到， []bmap 是一個(gè)hash table， 每一個(gè) bmap是我們常說的“桶”。 經(jīng)過hash 函數(shù)計(jì)算出來相同的hash值， 放到相同的桶中。 一個(gè) bmap中可以存放 8個(gè) 元素， 如果多出8個(gè)，則生成新的結(jié)點(diǎn)，尾接到隊(duì)尾。
以上是只是靜態(tài)文件 src/runtime/map.go 中的定義。 實(shí)際上編譯期間會(huì)給它加料 ，動(dòng)態(tài)地創(chuàng)建一個(gè)新的結(jié)構(gòu)：
上圖就是 bmap的內(nèi)存模型， HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 字段，節(jié)省內(nèi)存空間。
每個(gè) bmap設(shè)計(jì)成 最多只能放 8 個(gè) key-value 對(duì) ，如果有第 9 個(gè) key-value 落入當(dāng)前的 bmap，那就需要再構(gòu)建一個(gè) bmap，通過 overflow 指針連接起來。
map創(chuàng)建方法:
我們實(shí)際上是通過調(diào)用的 makemap ，來創(chuàng)建map的。實(shí)際工作只是初始化了hmap中的各種字段，如：設(shè)置B的大小， 設(shè)置hash 種子 hash 0.
注意 :
makemap 返回是*hmap 指針， 即 map 是引用對(duì)象， 對(duì)map的操作會(huì)影響到結(jié)構(gòu)體內(nèi)部 。
使用方式
對(duì)應(yīng)的是下面兩種方法
map的key的類型，實(shí)現(xiàn)了自己的hash 方式。每種類型實(shí)現(xiàn)hash函數(shù)方式不一樣。
key 經(jīng)過哈希計(jì)算后得到hash值，共 64 個(gè) bit 位。 其中后B 個(gè)bit位置， 用來定位當(dāng)前元素落在哪一個(gè)桶里， 高8個(gè)bit 為當(dāng)前 hash 值的top hash。 實(shí)際上定位key的過程是一個(gè)雙重循環(huán)的過程， 外層循環(huán)遍歷 所有的overflow， 內(nèi)層循環(huán)遍歷 當(dāng)前bmap 中的 8個(gè)元素 。
舉例說明： 如果當(dāng)前 B 的值為 5， 那么buckets 的長度 為 2^5 = 32。假設(shè)有個(gè)key 經(jīng)過hash函數(shù)計(jì)算后，得到的hash結(jié)果為：
外層遍歷bucket 中的鏈表
內(nèi)層循環(huán)遍歷 bmap中的8個(gè) cell
建議先不看此部分內(nèi)容，看完后續(xù) 修改 map中元素 - 擴(kuò)容 操作后 再回頭看此部分內(nèi)容。
擴(kuò)容前的數(shù)據(jù)：
等量擴(kuò)容后的數(shù)據(jù)：
等量擴(kuò)容后，查找方式和原本相同， 不多做贅述。
兩倍擴(kuò)容后的數(shù)據(jù)
兩倍擴(kuò)容后，oldbuckets 的元素，可能被分配成了兩部分。查找順序如下：
此處只分析 mapaccess1 ,。 mapaccess2 相比 mapaccess1 多添加了是否找到的bool值， 有興趣可自行看一下。
使用方式：
步驟如下：
擴(kuò)容條件 ：
擴(kuò)容的標(biāo)識(shí) ： h.oldbuckets ！= nil
假設(shè)當(dāng)前定位到了新的buckets的3號(hào)桶中，首先會(huì)判斷oldbuckets中的對(duì)應(yīng)的桶有沒有被搬遷過。 如果搬遷過了，不需要看原來的桶了，直接遍歷新的buckets的3號(hào)桶。
擴(kuò)容前：
等量擴(kuò)容結(jié)果
雙倍擴(kuò)容會(huì)將old buckets上的元素分配到x， y兩個(gè)部key 1 B == 0 分配到x部分，key 1 B == 1 分配到y(tǒng)部分
注意： 當(dāng)前只對(duì)雙倍擴(kuò)容描述， 等量擴(kuò)容只是重新填充了一下元素， 相對(duì)位置沒有改變。
假設(shè)當(dāng)前map 的B == 5，原本元素經(jīng)過hash函數(shù)計(jì)算的 hash 值為：
因?yàn)殡p倍擴(kuò)容之后 B = B + 1，此時(shí)B == 6。key 1 B == 1, 即 當(dāng)前元素rehash到高位，新buckets中 y 部分. 否則 key 1 B == 0 則rehash到低位，即x 部分。
使用方式：
可以看到，每一遍歷生成迭代器的時(shí)候，會(huì)隨機(jī)選取一個(gè)bucket 以及 一個(gè)cell開始。 從前往后遍歷，再次遍歷到起始位置時(shí)，遍歷完成。
map 是Go語言中基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，在日常的使用中經(jīng)常被用到。但是它底層是如何實(shí)現(xiàn)的呢？
總體來說golang的map是hashmap，是使用數(shù)組+鏈表的形式實(shí)現(xiàn)的，使用拉鏈法消除hash沖突。
golang的map由兩種重要的結(jié)構(gòu)，hmap和bmap(下文中都有解釋)，主要就是hmap中包含一個(gè)指向bmap數(shù)組的指針，key經(jīng)過hash函數(shù)之后得到一個(gè)數(shù)，這個(gè)數(shù)低位用于選擇bmap(當(dāng)作bmap數(shù)組指針的下表)，高位用于放在bmap的[8]uint8數(shù)組中，用于快速試錯(cuò)。然后一個(gè)bmap可以指向下一個(gè)bmap(拉鏈)。
Golang中map的底層實(shí)現(xiàn)是一個(gè)散列表，因此實(shí)現(xiàn)map的過程實(shí)際上就是實(shí)現(xiàn)散表的過程。在這個(gè)散列表中，主要出現(xiàn)的結(jié)構(gòu)體有兩個(gè)，一個(gè)叫 hmap (a header for a go map)，一個(gè)叫 bmap (a bucket for a Go map，通常叫其bucket)。這兩種結(jié)構(gòu)的樣子分別如下所示：
hmap :
圖中有很多字段，但是便于理解map的架構(gòu)，你只需要關(guān)心的只有一個(gè)，就是標(biāo)紅的字段： buckets數(shù)組 。Golang的map中用于存儲(chǔ)的結(jié)構(gòu)是bucket數(shù)組。而bucket(即bmap)的結(jié)構(gòu)是怎樣的呢？
bucket ：
相比于hmap，bucket的結(jié)構(gòu)顯得簡(jiǎn)單一些，標(biāo)紅的字段依然是“核心”，我們使用的map中的key和value就存儲(chǔ)在這里?！案呶还Ｖ怠睌?shù)組記錄的是當(dāng)前bucket中key相關(guān)的“索引”，稍后會(huì)詳細(xì)敘述。還有一個(gè)字段是一個(gè)指向擴(kuò)容后的bucket的指針，使得bucket會(huì)形成一個(gè)鏈表結(jié)構(gòu)。例如下圖：
由此看出hmap和bucket的關(guān)系是這樣的：
而bucket又是一個(gè)鏈表，所以，整體的結(jié)構(gòu)應(yīng)該是這樣的：
哈希表的特點(diǎn)是會(huì)有一個(gè)哈希函數(shù)，對(duì)你傳來的key進(jìn)行哈希運(yùn)算，得到唯一的值，一般情況下都是一個(gè)數(shù)值。Golang的map中也有這么一個(gè)哈希函數(shù)，也會(huì)算出唯一的值，對(duì)于這個(gè)值的使用，Golang也是很有意思。
Golang把求得的值按照用途一分為二：高位和低位。
如圖所示，藍(lán)色為高位，紅色為低位。 然后低位用于尋找當(dāng)前key屬于hmap中的哪個(gè)bucket，而高位用于尋找bucket中的哪個(gè)key。上文中提到：bucket中有個(gè)屬性字段是“高位哈希值”數(shù)組，這里存的就是藍(lán)色的高位值，用來聲明當(dāng)前bucket中有哪些“key”，便于搜索查找。 需要特別指出的一點(diǎn)是：我們map中的key/value值都是存到同一個(gè)數(shù)組中的。數(shù)組中的順序是這樣的:
并不是key0/value0/key1/value1的形式，這樣做的好處是：在key和value的長度不同的時(shí)候，可 以消除padding(內(nèi)存對(duì)齊)帶來的空間浪費(fèi) 。
現(xiàn)在，我們可以得到Go語言map的整個(gè)的結(jié)構(gòu)圖了：(hash結(jié)果的低位用于選擇把KV放在bmap數(shù)組中的哪一個(gè)bmap中，高位用于key的快速預(yù)覽，用于快速試錯(cuò))
map的擴(kuò)容
當(dāng)以上的哈希表增長的時(shí)候，Go語言會(huì)將bucket數(shù)組的數(shù)量擴(kuò)充一倍，產(chǎn)生一個(gè)新的bucket數(shù)組，并將舊數(shù)組的數(shù)據(jù)遷移至新數(shù)組。
加載因子
判斷擴(kuò)充的條件，就是哈希表中的加載因子(即loadFactor)。
加載因子是一個(gè)閾值，一般表示為：散列包含的元素?cái)?shù) 除以 位置總數(shù)。是一種“產(chǎn)生沖突機(jī)會(huì)”和“空間使用”的平衡與折中：加載因子越小，說明空間空置率高，空間使用率小，但是加載因子越大，說明空間利用率上去了，但是“產(chǎn)生沖突機(jī)會(huì)”高了。
每種哈希表的都會(huì)有一個(gè)加載因子，數(shù)值超過加載因子就會(huì)為哈希表擴(kuò)容。
Golang的map的加載因子的公式是：map長度 / 2^B(這是代表bmap數(shù)組的長度，B是取的低位的位數(shù))閾值是6.5。其中B可以理解為已擴(kuò)容的次數(shù)。
當(dāng)Go的map長度增長到大于加載因子所需的map長度時(shí)，Go語言就會(huì)將產(chǎn)生一個(gè)新的bucket數(shù)組，然后把舊的bucket數(shù)組移到一個(gè)屬性字段oldbucket中。注意：并不是立刻把舊的數(shù)組中的元素轉(zhuǎn)義到新的bucket當(dāng)中，而是，只有當(dāng)訪問到具體的某個(gè)bucket的時(shí)候，會(huì)把bucket中的數(shù)據(jù)轉(zhuǎn)移到新的bucket中。
如下圖所示：當(dāng)擴(kuò)容的時(shí)候，Go的map結(jié)構(gòu)體中，會(huì)保存舊的數(shù)據(jù)，和新生成的數(shù)組
上面部分代表舊的有數(shù)據(jù)的bucket，下面部分代表新生成的新的bucket。藍(lán)色代表存有數(shù)據(jù)的bucket，橘黃色代表空的bucket。
擴(kuò)容時(shí)map并不會(huì)立即把新數(shù)據(jù)做遷移，而是當(dāng)訪問原來舊bucket的數(shù)據(jù)的時(shí)候，才把舊數(shù)據(jù)做遷移，如下圖：
注意：這里并不會(huì)直接刪除舊的bucket，而是把原來的引用去掉，利用GC清除內(nèi)存。
map中數(shù)據(jù)的刪除
如果理解了map的整體結(jié)構(gòu)，那么查找、更新、刪除的基本步驟應(yīng)該都很清楚了。這里不再贅述。
值得注意的是，找到了map中的數(shù)據(jù)之后，針對(duì)key和value分別做如下操作：
1
2
3
4
1、如果``key``是一個(gè)指針類型的，則直接將其置為空，等待GC清除；
2、如果是值類型的，則清除相關(guān)內(nèi)存。
3、同理，對(duì)``value``做相同的操作。
4、最后把key對(duì)應(yīng)的高位值對(duì)應(yīng)的數(shù)組index置為空。
重慶分公司
重慶分公司
