1. 引言
map 是 Go 語言中使用頻率極高的數據結構，它提供了快速的鍵值對存取能力。雖然 map 的使用非常簡單，但其底層的實現卻是一個精心設計的哈希表，它需要高效地處理哈希計算、數據存儲、擴容以及最關鍵的——哈希沖突。
本文將解剖 map 的底層數據結構，詳細闡述其查找、賦值和擴容過程，特別是它是如何解決哈希沖突的。
2. map 的核心數據結構
Go map 的運行時表示是 runtime.hmap 結構體，其關鍵字段如下：
// src/runtime/map.go
type hmap struct {count int // map 中元素的個數，即 len(m)flags uint8B uint8 // buckets 的對數，buckets 數量 = 2^Bnoverflow uint16 // 溢出桶的大致數量hash0 uint32 // 哈希種子buckets unsafe.Pointer // 指向 bucket 數組的指針，大小為 2^Boldbuckets unsafe.Pointer // 在擴容時，指向舊的 bucket 數組nevacuate uintptr // 擴容進度計數器// ...
}
map 的核心是一個 bucket 數組。每個 bucket 是一個 runtime.bmap 結構：
// 一個 bucket 最多可以存放 8 個鍵值對
const bucketCnt = 8type bmap struct {tophash [bucketCnt]uint8 // 存儲每個 key 哈希值的高 8 位// keys and values follow
}
B: 決定了map有多少個 bucket，總數是 2B。buckets: 是一個指針，指向一個連續的 bucket 數組。bmap(bucket):tophash: 這是一個巧妙的優化。它存儲了每個 key 的哈希值的高 8 位 (top hash)。在查找 key 時，可以先快速比較這 8 位，如果tophash都不匹配，就無需再比較完整的 key，從而加速查找。鍵和值:
bmap結構體之后，緊跟著存儲了 8 個 key 和 8 個 value。它們在內存上是連續的。
溢出桶 (Overflow Bucket): 如果一個 bucket 的 8 個槽位都滿了，
map會通過一個指針將這個 bucket 與一個溢出桶鏈接起來，形成一個鏈表。
3. map 的工作流程
a) 寫入/賦值 (map[key] = value)
哈希計算: 使用哈希函數計算
key的哈希值hash。定位 Bucket: 使用
hash的低 B 位來決定這個key應該落在哪個 bucket 中。例如，bucketIndex = hash & (2^B - 1)。定位槽位:
計算
hash的高 8 位tophash。遍歷目標 bucket 的
tophash數組，看是否存在相同的tophash。如果
tophash相同，再完整地比較key是否相同。如果
key已存在，則更新對應的value。如果
key不存在，就在 bucket 中找一個空槽位，存入tophash,key和value。
處理沖突與溢出: 如果當前 bucket 的 8 個槽位都滿了，
map會創建一個新的溢出桶，并讓當前 bucket 指向它。新的鍵值對將被存入這個溢出桶。
b) 查找 (value, ok := map[key])
查找過程與寫入類似。通過哈希值定位到 bucket，然后先比較 tophash，再比較完整的 key。會依次遍歷 bucket 和其所有鏈接的溢出桶，直到找到 key 或者遍歷完所有溢出桶。
c) 擴容 (Grow)
當以下任一條件滿足時，map 會觸發擴容：
負載因子超限:
map中元素的數量count/ bucket 數量2^B> 6.5。溢出桶過多:
map的溢出桶數量過多時（當 B < 15 時，noverflow >= 2^B），也會觸發擴容，這主要是為了解決因大量刪除操作導致的內存空洞問題。
擴容方式:
等量擴容: 如果是因溢出桶過多觸發，
map會創建一個與原 bucket 數組大小相同的新數組，然后將數據重新排列（rehash），目的是消除內存碎片。翻倍擴容: 如果是因負載因子超限觸發，
map會創建一個兩倍大的 bucket 數組（B會加 1）。
漸進式擴容 (Incremental Evacuation): 為了避免因擴容導致長時間的 STW，Go map 的擴容是漸進式的。
擴容時,?
map不會一次性將所有數據從oldbuckets搬到buckets。而是每當對
map進行一次寫入或刪除操作時，會順便“搬運”一到兩個 bucket 的數據。查詢操作可能會同時在
oldbuckets和buckets中進行。整個搬運過程會分散到多次操作中，直到
oldbuckets中的數據全部遷移完畢。
