這是看著別人的文章結(jié)合源碼來(lái)整理的自己一套理解

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

通過(guò)數(shù)據(jù)結(jié)構(gòu)、實(shí)現(xiàn)原理、讀寫操作來(lái)了解go hashmap

數(shù)據(jù)結(jié)構(gòu)

hash有2個(gè)關(guān)鍵數(shù)據(jù)結(jié)構(gòu):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元素?cái)?shù)量

B2^B個(gè)buckets桶

noverflowbuckets溢出桶的數(shù)量，近似值

buckets桶

oldbuckets擴(kuò)容時(shí)指向原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
}

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

topbits存儲(chǔ)hash值的高8位，通過(guò)比對(duì)高8位減少鍵值對(duì)訪問次數(shù)以提高性能

keys/elems數(shù)組

pad內(nèi)存對(duì)齊

overflow溢出桶，map存儲(chǔ)數(shù)據(jù)過(guò)多時(shí)使用

實(shí)現(xiàn)原理

時(shí)間復(fù)雜度: O(1)

hash函數(shù)和hash沖突解決方法

hash函數(shù)

實(shí)現(xiàn)哈希表的關(guān)鍵點(diǎn)在于如何選擇哈希函數(shù)，哈希函數(shù)的選擇在很大程度上能夠決定哈希表的讀寫性能，在理想情況下，哈希函數(shù)應(yīng)該能夠?qū)⒉煌I映射到不同的索引上，這要求哈希函數(shù)輸出范圍大于輸入范圍，但是由于鍵的數(shù)量會(huì)遠(yuǎn)遠(yuǎn)大于映射的范圍，所以在實(shí)際使用時(shí)，這個(gè)理想的結(jié)果是不可能實(shí)現(xiàn)的。

hash沖突

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

拉鏈法： 使用數(shù)組加上鏈表

讀寫操作

讀

計(jì)算出key的hash

用最后的“B”位來(lái)確定在哪個(gè)桶（“B”就是前面說(shuō)的那個(gè)，B為4，就有16個(gè)桶，0101用十進(jìn)制表示為5，所以在5號(hào)桶）

根據(jù)key的前8位快速確定是在哪個(gè)格子（額外說(shuō)明一下，在bmap中存放了每個(gè)key對(duì)應(yīng)的tophash，是key的前8位）

最終還是需要比對(duì)key完整的hash是否匹配，如果匹配則獲取對(duì)應(yīng)value

如果都沒有找到，就去下一個(gè)overflow找

寫

通過(guò)key的后“B”位確定是哪一個(gè)桶

通過(guò)key的前8位快速確定是否已經(jīng)存在

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

擴(kuò)容

條件：

裝載因子大于6.5

溢出桶 大于15個(gè)

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
    }
    ...
}

方式：

等量擴(kuò)容

翻倍擴(kuò)容
編輯：hfy