本文會(huì)介紹 Go 語(yǔ)言的哈希的實(shí)現(xiàn)原理是使用時(shí)應(yīng)該了解的注意事項(xiàng)，內(nèi)容全部來(lái)自 Go 語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn) 险毁，基于內(nèi)容和自己的理解，做了一些排版上的設(shè)計(jì)便于個(gè)人的學(xué)習(xí)和回顧，有興趣的可以直接閱讀 Go 語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn) 中的內(nèi)容伶跷。
設(shè)計(jì)原理
哈希函數(shù)
- 理想：哈希函數(shù)能夠?qū)⒉煌I映射到不同的索引上，哈希函數(shù)的輸出范圍大于輸入范圍秘狞。
- 實(shí)際：讓哈希函數(shù)的結(jié)果能夠盡可能的均勻分布叭莫，然后通過(guò)工程上的手段解決哈希碰撞的問(wèn)題。
- 影響結(jié)果：果使用結(jié)果分布較為均勻的哈希函數(shù)烁试，那么哈希的增刪改查的時(shí)間復(fù)雜度為
??(1)雇初；但是如果哈希函數(shù)的結(jié)果分布不均勻，那么所有操作的時(shí)間復(fù)雜度可能會(huì)達(dá)到O(n)减响。
沖突解決
- 開(kāi)放尋址法：
- 核心思想是依次探測(cè)和比較數(shù)組中的元素以判斷目標(biāo)鍵值對(duì)是否存在于哈希表中靖诗。
- 當(dāng)我們向當(dāng)前哈希表寫入新的數(shù)據(jù)時(shí)，如果發(fā)生了沖突支示，就會(huì)將鍵值對(duì)寫入到下一個(gè)索引不為空的位置刊橘，當(dāng)需要查找某個(gè)鍵對(duì)應(yīng)的值時(shí)，會(huì)從索引的位置開(kāi)始線性探測(cè)數(shù)組颂鸿，找到目標(biāo)鍵值對(duì)或者空內(nèi)存就意味著這一次查詢操作的結(jié)束促绵。
- 開(kāi)放尋址法中對(duì)性能影響最大的是裝載因子，它是數(shù)組中元素的數(shù)量與數(shù)組大小的比值嘴纺。
- 拉鏈法(Go 語(yǔ)言解決哈希碰撞時(shí)選擇的方法)：
- 一般會(huì)使用數(shù)組加上鏈表败晴，不過(guò)一些編程語(yǔ)言會(huì)在拉鏈法的哈希中引入紅黑樹(shù)以優(yōu)化性能，拉鏈法會(huì)使用鏈表數(shù)組作為哈希底層的數(shù)據(jù)結(jié)構(gòu)栽渴。
- 向當(dāng)前哈希表寫入新的數(shù)據(jù)時(shí)尖坤，會(huì)先經(jīng)過(guò)一個(gè)哈希函數(shù)，哈希函數(shù)返回的哈希會(huì)幫助我們選擇一個(gè)桶闲擦，和開(kāi)放地址法一樣慢味，選擇桶的方式是直接對(duì)哈希返回的結(jié)果取模，選擇了桶后就可以遍歷當(dāng)前桶中的鏈表了墅冷，在遍歷鏈表的過(guò)程中會(huì)遇到以下兩種情況
- 找到鍵相同的鍵值對(duì) — 更新鍵對(duì)應(yīng)的值纯路；
- 沒(méi)有找到鍵相同的鍵值對(duì) — 在鏈表的末尾追加新的鍵值對(duì)；
- 哈希表讀寫操作的主要開(kāi)銷
- 計(jì)算哈希
- 定位桶
- 遍歷鏈表
- 裝載因子 = 元素?cái)?shù)量 ÷ 桶數(shù)量
- 裝載因子越大俺榆，哈希的讀寫性能就越差感昼。在一般情況下使用拉鏈法的哈希表裝載因子都不會(huì)超過(guò) 1，當(dāng)哈希表的裝載因子較大時(shí)會(huì)觸發(fā)哈希的擴(kuò)容罐脊，創(chuàng)建更多的桶來(lái)存儲(chǔ)哈希中的元素定嗓，保證性能不會(huì)出現(xiàn)嚴(yán)重的下降蜕琴。
數(shù)據(jù)結(jié)構(gòu)
type hmap struct {
count int // 表示當(dāng)前哈希表中的元素?cái)?shù)量
flags uint8
B uint8 // 表示當(dāng)前哈希表持有的 buckets 數(shù)量，但是因?yàn)楣１碇型暗臄?shù)量都 2 的倍數(shù)宵溅，所以該字段會(huì)存儲(chǔ)對(duì)數(shù)凌简，也就是 len(buckets) == 2^B；
noverflow uint16
hash0 uint32 // 是哈希的種子恃逻，它能為哈希函數(shù)的結(jié)果引入隨機(jī)性雏搂，這個(gè)值在創(chuàng)建哈希表時(shí)確定，并在調(diào)用哈希函數(shù)時(shí)作為參數(shù)傳入寇损；
buckets unsafe.Pointer
oldbuckets unsafe.Pointer // 是哈希在擴(kuò)容時(shí)用于保存之前 buckets 的字段凸郑，它的大小是當(dāng)前 buckets 的一半；
nevacuate uintptr
extra *mapextra
}
type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap
nextOverflow *bmap
}
// hash 表的桶
type bmap struct {
tophash [bucketCnt]uint8
}
// 編譯期間 hash 表的桶
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
初始化
字面量
-
當(dāng)哈希表中的元素?cái)?shù)量少于或者等于 25 個(gè)時(shí)矛市，編譯器會(huì)將字面量初始化的結(jié)構(gòu)體轉(zhuǎn)換成以下的代碼芙沥，將所有的鍵值對(duì)一次加入到哈希表中：
hash := make(map[string]int, 3) hash["1"] = 2 hash["3"] = 4 hash["5"] = 6 -
一旦哈希表中元素的數(shù)量超過(guò)了 25 個(gè)，編譯器會(huì)創(chuàng)建兩個(gè)數(shù)組分別存儲(chǔ)鍵和值浊吏，這些鍵值對(duì)會(huì)通過(guò)如下所示的 for 循環(huán)加入哈希：
hash := make(map[string]int, 26) vstatk := []string{"1", "2", "3", ... 而昨， "26"} vstatv := []int{1, 2, 3, ... , 26} for i := 0; i < len(vstak); i++ { hash[vstatk[i]] = vstatv[i] }
運(yùn)行時(shí)
- 當(dāng)創(chuàng)建的哈希被分配到棧上并且其容量小于
BUCKETSIZE = 8時(shí)，Go 語(yǔ)言在編譯階段會(huì)使用如下方式快速初始化哈希找田，這也是編譯器對(duì)小容量的哈希做的優(yōu)化： - 當(dāng)桶的數(shù)量小于 2^4 時(shí)歌憨，由于數(shù)據(jù)較少、使用溢出桶的可能性較低墩衙，會(huì)省略創(chuàng)建的過(guò)程以減少額外開(kāi)銷务嫡；
- 當(dāng)桶的數(shù)量多于 2^4 時(shí)，會(huì)額外創(chuàng)建 2^(???4) 個(gè)溢出桶底桂；
- 正常桶和溢出桶在內(nèi)存中的存儲(chǔ)空間是連續(xù)的植袍，只是被
runtime.hmap中的不同字段引用惧眠，當(dāng)溢出桶數(shù)量較多時(shí)會(huì)通過(guò)runtime.newobject創(chuàng)建新的溢出桶籽懦。
讀寫操作
訪問(wèn)
- 賦值語(yǔ)句左側(cè)接受參數(shù)的個(gè)數(shù)會(huì)決定使用的運(yùn)行時(shí)方法：
- 當(dāng)接受一個(gè)參數(shù)時(shí)，會(huì)使用
runtime.mapaccess1氛魁，該函數(shù)僅會(huì)返回一個(gè)指向目標(biāo)值的指針暮顺； - 當(dāng)接受兩個(gè)參數(shù)時(shí)，會(huì)使用
runtime.mapaccess2秀存，除了返回目標(biāo)值之外捶码，它還會(huì)返回一個(gè)用于表示當(dāng)前鍵對(duì)應(yīng)的值是否存在的bool值： - 訪問(wèn)的過(guò)程為先通過(guò)哈希表設(shè)置的哈希函數(shù)、種子獲取當(dāng)前鍵對(duì)應(yīng)的哈希或链，再通過(guò)
runtime.bucketMask和runtime.add拿到該鍵值對(duì)所在的桶序號(hào)和哈希高位的 8 位數(shù)字惫恼。 - 哈希會(huì)依次遍歷正常桶和溢出桶中的數(shù)據(jù)，它會(huì)先比較哈希的高 8 位和桶中存儲(chǔ)的
tophash澳盐，后比較傳入的和桶中的值以加速數(shù)據(jù)的讀寫祈纯。 - 用于選擇桶序號(hào)的是哈希的最低幾位令宿，而用于加速訪問(wèn)的是哈希的高 8 位，這種設(shè)計(jì)能夠減少同一個(gè)桶中有大量相等
tophash的概率影響性能腕窥。 - 每一個(gè)桶都是一整片的內(nèi)存空間粒没，當(dāng)發(fā)現(xiàn)桶中的
tophash與傳入鍵的tophash匹配之后，就會(huì)通過(guò)指針和偏移量獲取哈希中存儲(chǔ)的鍵keys[0]并與key比較簇爆，如果兩者相同就會(huì)獲取目標(biāo)值的指針values[0]并返回癞松。
- 當(dāng)接受一個(gè)參數(shù)時(shí)，會(huì)使用
寫入
- 首先是函數(shù)會(huì)根據(jù)傳入的鍵拿到對(duì)應(yīng)的哈希和桶：
- 然后通過(guò)遍歷比較桶中存儲(chǔ)的
tophash和鍵的哈希，如果找到了相同結(jié)果就會(huì)返回目標(biāo)位置的地址入蛆。 - 如果當(dāng)前桶已經(jīng)滿了响蓉，哈希會(huì)調(diào)用
runtime.hmap.newoverflow創(chuàng)建新桶或者使用runtime.hmap預(yù)先在noverflow中創(chuàng)建好的桶來(lái)保存數(shù)據(jù)，新創(chuàng)建的桶不僅會(huì)被追加到已有桶的末尾哨毁，還會(huì)增加哈希表的noverflow計(jì)數(shù)器厕妖。 - 如果當(dāng)前鍵值對(duì)在哈希中不存在，哈希會(huì)為新鍵值對(duì)規(guī)劃存儲(chǔ)的內(nèi)存地址挑庶，通過(guò)
runtime.typedmemmove將鍵移動(dòng)到對(duì)應(yīng)的內(nèi)存空間中并返回鍵對(duì)應(yīng)值的地址val言秸。如果當(dāng)前鍵值對(duì)在哈希中存在，那么就會(huì)直接返回目標(biāo)區(qū)域的內(nèi)存地址迎捺，哈希并不會(huì)在runtime.mapassign這個(gè)運(yùn)行時(shí)函數(shù)中將值拷貝到桶中举畸，該函數(shù)只會(huì)返回內(nèi)存地址，真正的賦值操作是在編譯期間插入的凳枝。
擴(kuò)容
-
runtime.mapassign函數(shù)會(huì)在以下兩種情況發(fā)生時(shí)觸發(fā)哈希的擴(kuò)容：- 裝載因子已經(jīng)超過(guò) 6.5抄沮；
- 哈希使用了太多溢出桶；
-
runtime.mapassign還需要判斷當(dāng)前哈希是否已經(jīng)處于擴(kuò)容狀態(tài)岖瑰，避免二次擴(kuò)容造成混亂叛买。 - 如果這次擴(kuò)容是溢出的桶太多導(dǎo)致的，那么這次擴(kuò)容就是等量擴(kuò)容
sameSizeGrow蹋订，等量擴(kuò)容創(chuàng)建的新桶數(shù)量值和舊桶一樣率挣。 - 如果這是等量擴(kuò)容，那么舊桶與新桶之間是一對(duì)一的關(guān)系露戒，所以兩個(gè)
runtime.evacDst只會(huì)初始化一個(gè)椒功。而當(dāng)哈希表的容量翻倍時(shí)，每個(gè)舊桶的元素會(huì)都分流到新創(chuàng)建的兩個(gè)桶中智什。 - 總結(jié)：哈希在存儲(chǔ)元素過(guò)多時(shí)會(huì)觸發(fā)擴(kuò)容操作动漾，每次都會(huì)將桶的數(shù)量翻倍，擴(kuò)容過(guò)程不是原子的荠锭，而是通過(guò)
runtime.growWork增量觸發(fā)的旱眯，在擴(kuò)容期間訪問(wèn)哈希表時(shí)會(huì)使用舊桶，向哈希表寫入數(shù)據(jù)時(shí)會(huì)觸發(fā)舊桶元素的分流。除了這種正常的擴(kuò)容之外删豺，為了解決大量寫入础爬、刪除造成的內(nèi)存泄漏問(wèn)題，哈希引入了sameSizeGrow這一機(jī)制吼鳞，在出現(xiàn)較多溢出桶時(shí)會(huì)整理哈希的內(nèi)存減少空間的占用看蚜。
刪除
- 需要使用 Go 語(yǔ)言中的
delete關(guān)鍵字，這個(gè)關(guān)鍵字的唯一作用就是將某一個(gè)鍵對(duì)應(yīng)的元素從哈希表中刪除赔桌，無(wú)論是該鍵對(duì)應(yīng)的值是否存在供炎，這個(gè)內(nèi)建的函數(shù)都不會(huì)返回任何的結(jié)果。 -
delete關(guān)鍵字在編譯期間經(jīng)過(guò)類型檢查和中間代碼生成階段被轉(zhuǎn)換成runtime.mapdelete函數(shù)簇中的一員疾党，用于處理刪除邏輯的函數(shù)與哈希表的runtime.mapassign幾乎完全相同音诫。
