Go map實(shí)現(xiàn)原理
深入Go的Map使用和實(shí)現(xiàn)原理
go 中的 map 也是 hashmap，由哈和(bucket)數(shù)組組成，每個(gè) bucket 可以存放若干元素(默認(rèn)8個(gè))宣赔，當(dāng)超過(guò) 8 個(gè)元素后，hmap會(huì)使用extra中的overflow指向新的 bucket 來(lái)拓展該bucket答姥；
bucket 數(shù)組 tophash 數(shù)組 data字節(jié)數(shù)組 overflow 鏈表
1. hashmap 的數(shù)據(jù)結(jié)構(gòu)：
type hmap struct {
count int // 當(dāng)前保存的元素個(gè)數(shù)
...
B uint8 // 指示bucket數(shù)組的大小
...
buckets unsafe.Pointer // bucket數(shù)組指針漓糙，數(shù)組的大小為2^B
...
}
2. bucket 的數(shù)據(jù)結(jié)構(gòu)：
type bmap struct {
tophash [8]uint8 //存儲(chǔ)哈希值的高8位
data byte[1] //key value數(shù)據(jù):key/key/key/.../value/value/value...
overflow *bmap //溢出bucket的地址
}
- tophash 數(shù)組長(zhǎng)度為 8铣缠，哈希值相同的 key 存入 bucket 時(shí)，將哈希值高位存儲(chǔ)在該數(shù)組中昆禽；
查找時(shí)蝗蛙，tophash 用來(lái)快速查找key值是否在該bucket中，而不用每次都通過(guò)真值全量進(jìn)行比較醉鳖； - data 區(qū)存放實(shí)際 key/value捡硅，存儲(chǔ)方式是 k1k2k3k4...v1v2v3v4...，節(jié)省字節(jié)對(duì)齊帶來(lái)的空間浪費(fèi)盗棵；
比如：map[int64]int8病曾，key 是 int64（8個(gè)字節(jié)），value是int8（一個(gè)字節(jié)）漾根，kv的長(zhǎng)度不同泰涂，如果按照kv格式存放，則考慮內(nèi)存對(duì)齊v也會(huì)占用int64辐怕，而按照后者存儲(chǔ)時(shí)逼蒙，8個(gè)v剛好占用一個(gè)int64。 - overflow 指向的是下一個(gè) bucket寄疏；
如果 bucket 已經(jīng)存儲(chǔ)了 8 個(gè)值是牢，bucket 會(huì)使用 overflow 指向新的 bucket 來(lái)存儲(chǔ)新的碰撞值；
哈希沖突后的數(shù)據(jù)結(jié)構(gòu)：
overflow 表示溢出的意思
3. 負(fù)載因子
負(fù)載因子用于表示哈希沖突的情況 = 鍵數(shù)量 / bucket 的數(shù)量
哈希因子需要控制在合適的大小陕截，超過(guò)闕值后需要 rehash
* 哈希因子過(guò)小驳棱，說(shuō)明空間利用率低
* 哈希因子過(guò)大，說(shuō)明沖突嚴(yán)重农曲，存取效率低
每個(gè) hash 表的實(shí)現(xiàn)對(duì)負(fù)載因子的容忍程度不同社搅，redis 中負(fù)載因子為 1 時(shí)就會(huì)觸發(fā) rehash驻债，因?yàn)?redis 的每個(gè) bucket 只能存儲(chǔ)一個(gè)鍵值對(duì)。而 go 的能存儲(chǔ) 8 個(gè)形葬，負(fù)載因子為 6.5合呐；
4. rehash
4.1 擴(kuò)容的前提條件
為保證訪問(wèn)效率，當(dāng)新元素要添加時(shí)笙以，都會(huì)檢查是否需要擴(kuò)容淌实，擴(kuò)容實(shí)際是空間換時(shí)間；
- 觸發(fā)擴(kuò)容的條件
負(fù)載因子達(dá)到了 6.5
overflow 數(shù)量 > 2^15
4.2 增量擴(kuò)容
負(fù)載因子超過(guò)闕值后猖腕，新建一個(gè) buckets拆祈，長(zhǎng)度為原來(lái)的2倍，舊 buckets 的數(shù)量逐漸搬遷至新的 buckets 中倘感。
如果數(shù)據(jù)量較大缘屹，采取漸進(jìn)式hash，每次訪問(wèn) map 都會(huì)觸發(fā)一次搬遷侠仇，每次搬遷2個(gè)鍵值對(duì)轻姿，搬遷完成后將會(huì)刪除 oldbuckets；
4.3 縮容
通過(guò)不斷地刪除逻炊，鍵值對(duì)集中在一小部分地 bucket 中互亮，overflow 中大部分是空的，經(jīng)過(guò)重新組織后 bucket 的數(shù)量會(huì)減少余素，提高訪問(wèn)效率豹休；
5 查找過(guò)程
- 根據(jù) key 算出哈希值
- 取 hash 值的低位和 hmap.B 取模確定 bucket 的位置
- 取 hash 值高位在 tophash 數(shù)組中查詢
- 如果有，則去 bucket 中找該 key
- 如果當(dāng)前 bucket 中沒(méi)有桨吊，則從 overflow 指向的 bucket 中找
- 如果當(dāng)前處于搬遷過(guò)程中威根，則優(yōu)先從 oldbucket 中查找
6 更新過(guò)程
- 根據(jù) key 算出 hash 值
- hash 值對(duì) hmap.B 取模確定 bucket 的位置
- 如果 key 存在，則更新值视乐，如果不存在則插入
