所以這篇文章不準(zhǔn)備把 map 寫成 runtime 源碼導(dǎo)讀，也不想把它變成一份機械八股。主線只抓三件事：

• 它為什么能這么快；
• 它為什么會沖突；
• 它為什么需要擴容和同步；

再此聲明下，文章主體采用經(jīng)典 Go map 來講，也就是大家最熟悉的 hmap / bmap / overflow bucket 這種；
只會在關(guān)鍵處補上 Swiss Table 風(fēng)格Go從 1.24 開始，就優(yōu)化為了Swiss Table 方案

1. 一語戳破哈希表

哈希表解決的問題很直接：給我一個 key，我不想從頭遍歷到尾，我想盡快知道它大概率應(yīng)該放在哪，查的時候也直接去那個位置附近找。

map[string]int 之所以平均查找復(fù)雜度能做到 O(1)，靠的從而不是魔法，而是以下兩步：

1. 對 key 做哈希，得到一個哈希值。
2. 用哈希值去定位存儲位置。

可真正麻煩的地方不在 “定位” ，而在 “沖突” 。不同 key 經(jīng)過哈希后，完全可能落到同一個位置。于是，任何一個成熟的哈希表實現(xiàn)都得回答三個問題：

• 沖突來了怎么放
• 數(shù)據(jù)變多了怎么擴
• 并發(fā)訪問時怎么保住一致性

Go map 的底層設(shè)計，本質(zhì)上就是圍著這三件事在做權(quán)衡。

2. 經(jīng)典版：Go map 到底長什么樣

go1.24之前，用的都是經(jīng)典版本
再此我先強調(diào)一句：本模塊講解的是 hmap / bmap / overflow bucket 這套設(shè)計。

2.1hmap解決什么問題

hmap 不負(fù)責(zé)一條一條存業(yè)務(wù)數(shù)據(jù)，它更像整個 map 的總控結(jié)構(gòu)。它關(guān)心的是：

• 現(xiàn)在總共有多少元素
• 現(xiàn)在有多少個桶
• 當(dāng)前桶數(shù)組在哪
• 如果正在擴容，舊桶數(shù)組在哪
• 舊桶搬遷到哪一步了

把源碼結(jié)構(gòu)體簡化一下，大概就長這樣：

hmap
├── count       // 元素個數(shù)
├── B           // 桶數(shù)量的對數(shù)，桶數(shù)約等于 2^B
├── buckets     // 當(dāng)前桶數(shù)組
├── oldbuckets  // 擴容中的舊桶數(shù)組
└── nevacuate   // 漸進(jìn)式遷移進(jìn)度

如果你把 map 想成一家公司，hmap 不是一線員工，它更像調(diào)度層。真正存 key/value 的，是下面的桶。

一句話總結(jié)：

hmap 是經(jīng)典 Go map 實現(xiàn)里的總控結(jié)構(gòu)，真正的 key/value 主要放在 bucket 里，hmap 負(fù)責(zé)管理桶數(shù)組、元素數(shù)量和擴容狀態(tài)。

2.2bmap解決什么問題

bmap 可以理解成單個桶的結(jié)構(gòu)。一個桶里最多放 8 組 key/value，這也是很多人記住的那個點。

把源碼簡化一下，大概長這樣：

bmap
├── tophash[8]
├── key[0] ... key[7]
├── value[0] ... value[7]
└── overflow *bmap

這里有兩個常見誤區(qū)。

第一個誤區(qū)是：
一些新手可能認(rèn)為一個桶里的元素的完整哈希值都是一樣？！
NO！當(dāng)然不是。更準(zhǔn)確的說法是，這些 key 的哈希結(jié)果里，用來“選桶”的那一部分相同，所以它們落進(jìn)了同一個桶；完整哈希值可以不同。

我舉個簡化例子。
假設(shè)當(dāng)前一共只有 8 個桶，也就是只看哈希結(jié)果的低 3 位來選桶：

keyA 的 hash = 10101100
keyB 的 hash = 01111100

這兩個完整哈希值顯然不一樣，但它們低 3 位同樣是 100，于是還是會進(jìn)入同一個 bucket。沖突的本質(zhì)從來都不是“哈希值完全一樣”，而是“映射到了同一個桶”。

第二個誤區(qū)是：
桶就是個小鏈表。
這也不對。經(jīng)典 Go map 的主路徑還是連續(xù)內(nèi)存里的桶，overflow bucket 只是桶滿之后的補救手段，不是把鏈表當(dāng)成主存儲結(jié)構(gòu)。
原因也很現(xiàn)實，鏈表節(jié)點分散，指針跳轉(zhuǎn)多，對現(xiàn)代 CPU cache 不友好。

2.3tophash[8]到底在干什么

很多人都了解過 tophash[8]，但沒真理解它解決了什么問題。

它解決的問題是：進(jìn)了桶以后，不想每個槽位都直接拿真實 key 去做重比較。尤其 key 是字符串、長結(jié)構(gòu)體的時候，直接比 key 就會很費勁。

所以經(jīng)典實現(xiàn)會先做一層粗篩：

• 哈希值的低位先拿去選桶
• 哈希值里再取一小段高位摘要，存進(jìn) tophash[i]
• 桶內(nèi)查找時先比 tophash
• 只有摘要對上了，才繼續(xù)比真正的 key

也就是說，tophash[8] 不是完整哈希值，它更像 8 個槽位各自的“門牌號縮寫”。
另外它還會兼任一些狀態(tài)位，比如標(biāo)記空槽位或搬遷狀態(tài)。

一句話總結(jié)：

tophash[8] 是桶內(nèi) 8 個槽位對應(yīng)的哈希摘要數(shù)組，作用是先粗篩，再做真實 key 比較，減少無效比較成本。

2.4overflow bucket是怎么來的

一個桶最多就 8 組 key/value。那第 9 個、10 個怎么辦？經(jīng)典實現(xiàn)的做法是掛 overflow bucket。

這也是經(jīng)典版 Go map 中最容易被記成一段死知識的話：超過 8 個后通過 overflow bucket 處理。這個結(jié)論本身沒錯，但如果只記到這里，基本只是停留在記憶層面。

更有價值的理解其實是：
overflow bucket 只是沖突壓力的緩沖區(qū)，不是最終解法。
因為一旦同一個桶后面掛了很多 overflow，查找路徑就會變長，插入和刪除也都會更慢。它能救場，但不適合長期背鍋。
所以真正的解法還是擴容和重新分布數(shù)據(jù)。

如果想要一個更直觀的例子，可以這樣想。
下面這個示例不是 Go runtime 的真實哈希過程，只是為了說明“多個 key 進(jìn)同一個桶”的現(xiàn)象：

m := map[int]string{
    1:  "a",
    9:  "b",
    17: "c",
}

如果把整數(shù)的低位簡化成選桶依據(jù)，在只有 8 個桶的時候，1、9、17 都可能落到同一個桶里。桶內(nèi)位置先用完，后來的沖突元素就只能先掛到 overflow bucket。
然后越來越長…

3. 擴容不是“多加幾個桶”那么簡單

大家經(jīng)常會有這樣一個疑問：
為什么舊桶里的數(shù)據(jù)要搬到新桶里？為什么不能以后新數(shù)據(jù)放新桶，舊數(shù)據(jù)繼續(xù)留在舊桶？

這個問題其實很有價值，因為它正好卡在很多人“只會背結(jié)論，但沒想通原因”的地方。

3.1 為什么舊桶必須搬

因為桶數(shù)量一變，key 到桶的映射規(guī)則也會變。

假設(shè)原來有 4 個桶，某個 key 按舊規(guī)則落在桶 1?，F(xiàn)在擴容成 8 個桶，同一個 key 按新規(guī)則再算，可能就不在 1，而是到了 5。

可以用一個二進(jìn)制例子理解：

某 key 的 hash = 0101

原來 4 個桶，只看低 2 位：01 -> 桶 1
擴容成 8 個桶，看低 3 位：101 -> 桶 5

如果舊數(shù)據(jù)不搬，新查找邏輯會按 8 個桶的規(guī)則去桶 5 找，但數(shù)據(jù)還躺在舊桶 1 里，結(jié)果就是查不到。
問題不是“老數(shù)據(jù)懶得搬”，問題是映射規(guī)則已經(jīng)變了。

所以擴容的本質(zhì)不是“以后多幾個位置可用”，而是“整張表的分布規(guī)則變了，舊數(shù)據(jù)也得跟著重分布”。

3.2 為什么 Go 要做漸進(jìn)式擴容

如果一次性把整張大 map 全量搬完，單次寫操作的延遲會很難看。
對于后端服務(wù)來說，這種抖動很危險，尤其是在高峰流量下。

經(jīng)典 Go map 里的做法正是漸進(jìn)式搬遷：

• 先分配新桶數(shù)組
• 舊桶數(shù)組暫時保留
• 后續(xù)的插入、刪除、更新過程中，順手搬一點舊數(shù)據(jù)(一般是兩個)
• 搬完以后，oldbuckets 不再被引用，后續(xù)交給 GC 回收

這樣單次操作的成本更平滑，不容易在某一個請求上突然炸出大延遲。

3.3 增量擴容和等量擴容

經(jīng)典實現(xiàn)里，擴容不止一種。

增量擴容 出現(xiàn)在整體裝載因子上來了，桶數(shù)真的不夠用了。這時桶數(shù)量會翻倍，舊桶里的元素搬遷后，通常只會落到兩個位置之一：原位置，或者原位置加上舊桶數(shù)。

等量擴容 則更像一次“整理內(nèi)務(wù)”。桶總數(shù)不變，但 overflow 太多了，說明歷史沖突、刪除留下的空洞、桶內(nèi)分布不緊湊，已經(jīng)把鏈拉長了。這時運行時會分配一套同樣大小的新桶，把舊桶和 overflow 里的有效數(shù)據(jù)重新壓實。它不一定讓理論容量變大，但會把歷史包袱清掉。

一句話概括：

• 增量擴容是在加容量
• 等量擴容是在去包袱

4. 并發(fā)安全：原生 map 為什么不能裸奔

Go 原生 map 并不保證并發(fā)安全。
雖然這句話大家都知道，但最好不要只停在“官方就是這么規(guī)定”上。

更實在的理解是：
map 內(nèi)部會維護桶、搬遷狀態(tài)、溢出結(jié)構(gòu)這些運行時不變量。多個 goroutine 一邊讀一邊寫，或者同時寫，很容易把這些狀態(tài)搞亂。輕則數(shù)據(jù)競爭，重則運行時直接報 concurrent map writes。

工程上最常見的做法還是 map + sync.RWMutex：

type SafeMap struct {
    mu sync.RWMutex
    m  map[string]int
}

它的優(yōu)點很樸素：

• 強類型，編譯期友好
• 復(fù)合邏輯容易放進(jìn)同一個臨界區(qū)
• 業(yè)務(wù)不變量也能一起保護

它的代價也很明確：鎖粒度通常就是整張 map。

sync.Map 不是“語法更高級的 map”，它是標(biāo)準(zhǔn)庫提供的并發(fā)專用結(jié)構(gòu)。
當(dāng)前 Go 版本里，sync.Map 底層已經(jīng)基于 internal/sync.HashTrieMap，不是很多舊文章里那套 read + dirty 的雙層結(jié)構(gòu)了。

它更適合兩類場景：

• 某個 key 寫入一次，之后被大量讀取，比如只增不改的緩存
• 不同 goroutine 主要操作不同 key 集合，鎖競爭能被明顯攤薄

如果你的場景是復(fù)雜業(yè)務(wù)狀態(tài)、強類型、多個字段需要一起維護，map + sync.RWMutex 往往還是更穩(wěn)的選擇。
sync.Map 的價值不在于“它更高級”，而在于它是一個為并發(fā)訪問模式做過專門優(yōu)化的結(jié)構(gòu)。

如果再往下看一層，HashTrieMap 的思路也值得知道：
它不是一張大表外面套一把大鎖，而是一棵并發(fā)哈希 Trie。讀路徑大量依賴原子讀，寫入時只鎖局部節(jié)點。這也是它在高并發(fā)、讀多寫少場景里更容易把爭用壓下去的原因。
(鎖局部，而非全局)

5. 現(xiàn)版本的Go Map-Go 1.24版本之后

上方大部分文章采用的都是經(jīng)典 Go map。雖然這些依舊適合學(xué)習(xí)，也非常適合大多數(shù)面試場景。但畢竟是舊版本了。

如果別人追問的是“當(dāng)前新版本 Go 的 map 實現(xiàn)”，我們就不能把 hmap + bmap + overflow bucket 說成唯一答案了。

因為從 Go 1.24 開始，官方內(nèi)置 map 已經(jīng)切到基于 Swiss Table 的實現(xiàn)。新版本中：

• group，每組 8 個 slot
• control word，用來并行檢查組內(nèi)槽位狀態(tài)
• open addressing / probing，也就是開放尋址和探測
• 為了保住增量增長的延遲特性，Go 自己又做了適配，不是直接照搬 C++ 版本

這里最容易被問到的一個小坑是“為什么有人說 16 個槽位”。
那通常是在說別的 Swiss Table 實現(xiàn)，比如 Abseil 的一些設(shè)計討論；
Go 當(dāng)前內(nèi)置 map 的 group 大小仍然是 8，不是 16。

總結(jié)：

Go map 本質(zhì)上一直都是哈希表。經(jīng)典實現(xiàn)可以用 hmap / bmap / overflow bucket 解釋；如果按 Go 1.24+ 之后的實現(xiàn)，更準(zhǔn)確的說法就要基于 Swiss Table 的 group + control word + probing了。

6. 回顧 / 自測

對于Go Map你更應(yīng)該了解什么？
在讀完本篇文章之后，希望你可以打破：

Go map 底層是哈希表，核心結(jié)構(gòu)是 hmap，桶是 bmap，一個桶 8 個 key/value，超過了走 overflow bucket。

不只是知道這樣的表層認(rèn)知。你也可以在琢磨以下問題：

• 同一個桶里的元素不要求完整哈希值一樣，只是選桶那部分結(jié)果一樣
• tophash 是桶內(nèi)快速篩選，不是完整哈希值
• overflow bucket 不是終局方案，overflow 多了會拖慢查找，所以需要擴容
• 擴容后舊數(shù)據(jù)必須搬，因為映射規(guī)則變了
• Go 做的是漸進(jìn)式擴容，目的是控制單次操作延遲
• 原生 map 不并發(fā)安全，sync.Map 也不是所有場景都比 map + RWMutex 更適合
• 如果再補一句 Go 1.24+ 已經(jīng)切到 Swiss Table，這個回答就更完整

希望你可以把這些設(shè)計背后的“為什么”給琢磨出來。

7. 總結(jié)

如果只給你 40 秒，可以這么說：

Go map 本質(zhì)上是哈希表。按經(jīng)典實現(xiàn)方式來說，頂層是 hmap，下面維護 bucket，也就是 bmap。一個桶最多放 8 組 key/value，key 先通過哈希定位到桶，桶內(nèi)再借助 tophash 做快速篩選；如果桶滿了，會先掛 overflow bucket。但 overflow 多了會影響性能，所以 Go 會觸發(fā)擴容，并通過漸進(jìn)式遷移把舊桶數(shù)據(jù)逐步搬到新桶里。原生 map 不支持讀寫并發(fā)安全，工程上通常用 map + sync.RWMutex，特定讀多寫少場景可以考慮 sync.Map。如果按 Go 1.24+ 的之后版本的實現(xiàn)，則內(nèi)置的 map 已經(jīng)演進(jìn)到 Swiss Table 風(fēng)格了。`

如果你是為了優(yōu)化項目而來，則本篇文章真正值得帶走的就不是上方那一段標(biāo)準(zhǔn)答案了，而是下面這四個判斷：

• map 快，是因為先算哈希再定位，不是因為它“天然免費”
• 沖突不可避免，桶、摘要和擴容都是圍著沖突成本做優(yōu)化
• 擴容的難點從來不是“申請更多空間”，而是“低延遲地重分布舊數(shù)據(jù)”
• 并發(fā)安全不是 map 自己送的能力，什么時候該鎖、什么時候該用 sync.Map，要按訪問模式判斷

到此這篇關(guān)于Go map 底層原理實現(xiàn)的文章就介紹到這了,更多相關(guān)Go map 底層內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論