一文了解go hashmap（數據結構、實現原理、讀寫操作）

這是看著別人的文章結合源碼來整理的自己一套理解

理解 Golang 哈希表 Map 的原理?draveness.me

通過數據結構、實現原理、讀寫操作來了解go hashmap

數據結構

hash有2個關鍵數據結構:hmapbmap

hmap:runtime/map.go

type hmap struct {
    count       int 
    flags       uint8
    B           uint8  
    noverflow   uint16 
    hash0       uint32 
    buckets     unsafe.Pointer 
    oldbuckets  unsafe.Pointer
    nevacuate   uintptr
    extra       *mapextra 
}

count元素數量

B2^B個buckets桶

noverflowbuckets溢出桶的數量，近似值

buckets桶

oldbuckets擴容時指向原buckets桶

bmap:runtime/map.gocmd/compile/internal/gc/reflect.go

type bmap struct {
    topbits     [8]uint8
    keys        [8]keytype
    elems       [8]elemtype
    pad         uintptr
    overflow    uintptr
}

哈希表中桶的真正結構其實是在編譯期間運行的函數bmap中被『動態(tài)』創(chuàng)建的， 代碼在cmd/compile/internal/gc/reflect.go

topbits存儲hash值的高8位，通過比對高8位減少鍵值對訪問次數以提高性能

keys/elems數組

pad內存對齊

overflow溢出桶，map存儲數據過多時使用

實現原理

時間復雜度: O(1)

hash函數和hash沖突解決方法

hash函數

實現哈希表的關鍵點在于如何選擇哈希函數，哈希函數的選擇在很大程度上能夠決定哈希表的讀寫性能，在理想情況下，哈希函數應該能夠將不同鍵映射到不同的索引上，這要求哈希函數輸出范圍大于輸入范圍，但是由于鍵的數量會遠遠大于映射的范圍，所以在實際使用時，這個理想的結果是不可能實現的。

hash沖突

開放尋址法：對數組中的元素依次比較鍵值對是否存在于數組

拉鏈法： 使用數組加上鏈表

讀寫操作

讀

計算出key的hash

用最后的“B”位來確定在哪個桶（“B”就是前面說的那個，B為4，就有16個桶，0101用十進制表示為5，所以在5號桶）

根據key的前8位快速確定是在哪個格子（額外說明一下，在bmap中存放了每個key對應的tophash，是key的前8位）

最終還是需要比對key完整的hash是否匹配，如果匹配則獲取對應value

如果都沒有找到，就去下一個overflow找

寫

通過key的后“B”位確定是哪一個桶

通過key的前8位快速確定是否已經存在

最終確定存放位置，如果8個格子已經滿了，沒地方放了，那么就重新創(chuàng)建一個bmap作為溢出桶連接在overflow

擴容

條件：

裝載因子大于6.5

溢出桶 大于15個

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again
    }
    ...
}

方式：

等量擴容

翻倍擴容
編輯：hfy