點選上方藍色“後端開發雜談”關注我們, 專注于後端日常開發技術分享
map 資料結構與實際的資料結構
map 中的資料被存放在一個數組中的, 數組的元素是桶(bucket), 每個桶至多包含8個鍵值對資料. 哈希值低位(low-order bits)用于選擇桶, 哈希值高位(high-order bits)用于在一個獨立的桶中差別出鍵. 哈希值高低位示意圖如下:
image 源碼位于
src/runtime/map.go
.
結構體
// A header for a Go map.
type hmap struct {
count int // 代表哈希表中的元素個數, 調用len(map)時, 傳回的就是該字段值.
flags uint8 // 狀态标志, 下文常量中會解釋四種狀态位含義.
B uint8 // buckets(桶)的對數log_2(哈希表元素數量最大可達到裝載因子*2^B)
noverflow uint16 // 溢出桶的大概數量.
hash0 uint32 // 哈希種子.
buckets unsafe.Pointer // 指向buckets數組的指針, 數組大小為2^B, 如果元素個數為0, 它為nil.
oldbuckets unsafe.Pointer // 如果發生擴容, oldbuckets是指向老的buckets數組的指針, 老的buckets數組大小是新
// 的buckets的1/2.非擴容狀态下, 它為nil. 它是判斷是否處于擴容狀态的辨別
nevacuate uintptr // 表示擴容進度, 小于此位址的buckets代表已搬遷完成.
extra *mapextra // 這個字段是為了優化GC掃描而設計的. 當key和value均不包含指針, 并且都可以inline時使用.
// extra是指向mapextra類型的指針.
}
// mapextra holds fields that are not present on all maps.
type mapextra struct {
// 就使用 hmap 的 extra 字段來存儲 overflow buckets,
// 如果 key 和 value 都不包含指針, 并且可以被 inline(<=128 位元組), 則将 bucket type 标記為不包含指針 (使用
// ptrdata 字段, 為0表示不包含指針). 這樣可以避免 GC 掃描整個 map. 但是 bmap.overflow 是一個指針. 這時候我
// 們隻能把這些 overflow 的指針都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了.
//
// 當 key 和 elem 不包含指針時, 才使用 overflow 和 oldoverflow.
// overflow 包含的是 hmap.buckets 的 overflow bucket,
// oldoverflow 包含擴容時的 hmap.oldbuckets 的 overflow bucket.
overflow *[]*bmap
oldoverflow *[]*bmap
// 指向空閑的 overflow bucket 的指針(第一個空閑的bucket位址)
nextOverflow *bmap
}
// A bucket for a Go map.
type bmap struct {
// tophash包含此桶中每個鍵的哈希值最高位元組(高8位)資訊(也就是前面所述的high-order bits).
// 如果tophash[0]
tophash [bucketCnt]uint8
}
常量值
bmap(即map當中的bucket)記憶體結構
hmap (即map) 記憶體結構
bmap 也就是 bucket(桶)的記憶體模型圖解如下(代碼邏輯就是上述的
bmap
函數).
image
該桶的第7,8位cell還未有對應的鍵值對. 注意: key和value是各自存儲起來的, 并非想象中的 key/value/key/value…的形式. 這樣的做法好處在于消key/value之間的padding, 例如
map[int64]int
. 還有,在8個鍵值對資料後面還有一個overflow指針, 因為桶中最多隻能裝8個鍵值對, 如果有多餘的鍵值對落到目前桶, 那麼就需要再建構一個桶(溢出桶), 通過 overflow 指針連結起來.
最後, 這裡展示一個 B=4 的完整 map 結構:
image
-
參考連結
1.8 萬字詳解 Go 是如何設計 Map 的