golang 的 map 使用的是 hash map 基本結構 下麵截取自源碼，已翻譯 // runtime/map.go:117 // go map 定義,hashmap 縮寫 type hmap struct { count int // map 里文件數 flags uint8 // map ...
golang 的 map 使用的是 hash map
基本結構
下麵截取自源碼，已翻譯
// runtime/map.go:117
// go map 定義,hashmap 縮寫
type hmap struct {
count int // map 里文件數
flags uint8 // map 當前是否在寫入，一般為 hashWriting = 4 （寫入中）或 0 （空閑）
B uint8 // 桶的數量，2^B 個
noverflow uint16 // 溢出桶的數量
hash0 uint32 // hash 隨機數，從 hmap 創建開始就不變
buckets unsafe.Pointer // 存儲桶的指針，存放 2^B 個桶的地址
oldbuckets unsafe.Pointer // 舊存儲桶的地址，在擴容時候用
nevacuate uintptr // 記錄疏散桶進度 TODO
extra *mapextra // 當 bucket 不含指針時，記錄所有溢出桶的地址，加快 gc
}
// runtime/map.go:151
// 一個桶的設計
type bmap struct {
tophash [bucketCnt]uint8 // 高 64 位存儲每個 key 的信息
// 後面跟 8 個 key
// 然後跟 8 個 value
// 下一個溢出桶地址
}
初始化
m := make(map[int]string) // 初始化一個empty的 map，所有參數都是 0，用的方法是h := new(hmap) 參考runtime/map.go:294
m2 := make(map[int]string,100) // 初始化一個大小為 128 的 map
m3 := map[int]string{1:"a"} // 初始化 1 個桶的 map
我的golang是 1.21 版本（go version go1.21.1 darwin/arm64）
先分析使用 make 的情況，當 make 的第二個參數不填或者<=8的時候，調用的是 makemap_small(runtime/map.go:294) 函數，但我本地看彙編代碼並沒有發現 makemap_small 函數，應該是編譯器有別的優化，具體可以深入研究一下，其他版本的 golang 還沒測。
這裡其實進行了很簡單的記憶體分配和隨機種子，所以找不到也可以理解
// runtime/map.go:294
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand() // 隨機 hash 種子
return h
}
當第二個參數 >8的時候，會調用 makemap(runtime/map.go:305) 函數，這個從彙編代碼可以看到，會進行 bucket 的記憶體分配
// runtime/map.go:305
func makemap(t *maptype, hint int, h *hmap) *hmap {
mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
if overflow || mem > maxAlloc {
hint = 0
}
// 這塊跟 makemap_small是一樣的
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand()
// 這塊主要是計算桶的數量
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// 這塊進行 bucket 的初始化
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
同時在 key 是 32 位，64 位，string 時，都用的同一樣的創建 map，但是插入、讀取、刪除函數有各自的優化，否則就用通用的插入讀取刪除
插入
先對 key 進行 hash（hash 函數運行時得到，根據處理器有關，一般是 aes），得到 64 位的哈希值
用哈希值的低 B (hmap.B) 位來確定該 key 落入哪個桶內
再用哈希值的高 8 位尋找在 bucket 里的位置
然後依次找到空的位置，將 key，value 寫入 bucekt 里的對應位置
如果當前 bucket 滿了，會觸發溢出桶，新建一個 bucket 的操作
讀取
讀取和插入類似，先對 key 進行 hash 運算得到 64 位 hash 值
然後依次計算低 B 位，高 8 位
然後找到對應的桶，再依次找高八位相同的值，再比較 key，所以能作為 map 的 key 的一定是可比較的類型，也就是支持==操作
如果找不到返回預設值
擴容
map 在元素增加過多或過於稀疏都會發生擴容
- 當裝載因數大於 6.5，會發生擴容
- 當溢出桶的數量過多，但是裝載因數卻 < 6.5，說明map 比較稀疏，就需要sameSizeGrow，稱作等量擴容
擴容
擴容就是增加一倍的 bucket 數量，把原來的某個 bucket 的元素重新取低B位，然後放到新的桶里
等量擴容
等量擴容也是走的擴容流程，只不過B 不+1，只是新建一個 bucket，將原來 bucket 里的數據搬遷到新的 bucket 里，當有多個溢出桶時候可能會壓縮成一個，就沒有溢出桶了
遍歷
首先明確，map 在 range 遍歷的時候返回的是值的拷貝，而不是原值，所以對遍歷的值的修改對原值不會影響，如果遍歷的 value 是指針的話，就相當於拿指針修改，就會有影響，但是 map 里存的值不會變
map 在遍歷的時候先隨機一個種子，然後從一個隨機的 bucket 和隨機的位置開始遍歷
如果在擴容中，會查看 bucket 是否正在擴容，如果是正在擴容，回去老的 bucket 就是 oldbuckets 那遍歷
難點
擴容
map 的主要難點就是擴容相關
併發
map 在寫入時會將 flag 置為hashWriting，其他協程有寫操作時候，會 panic
參考
深入解析Golang的map設計
逐行拆解 Go map 源碼
Go語言基礎結構 —— Map(哈希表)
golang map 從源碼分析實現原理（go 1.14）
我可能並不會使用golang map
GO語言設計與實現-3.3哈希表
Go 程式員面試筆試寶典-哈希表
