一.redis 中使用的字典
redis的字典是由hash表實(shí)現(xiàn)的揪阿，代碼主要是在dict.cpp/dict.h中
ht是一個(gè)指向dictht指針數(shù)組损同，一般只使用ht[0],ht[1]在rehash 的時(shí)候使用，rehshidx作為是否在rehash的標(biāo)志顷编，table是一個(gè)dictEntry地址數(shù)組指針，hash算法采用的是murmur2算法(目前已出到murmur3)，計(jì)算hash值并與sizemark進(jìn)行取模操作得到table的index扬跋，解決沖突采用鏈地址法，由于dictEntry鏈表并沒有尾指針凌节，所以插入是頭插方式钦听，dict的結(jié)構(gòu)大概是醬紫的如下圖
key的個(gè)數(shù)為used ，size為table長(zhǎng)度
如果used> size and redis 沒有執(zhí)行 BGSAVE?命令或者?BGREWRITEAOF?命令或者正在 執(zhí)行?BGSAVE?命令或者?BGREWRITEAOF and??超過(guò)負(fù)載閾值 的情況下 允許rehash 倍奢，擴(kuò)展后的table是大于原table2倍的最小2次冪朴上，考慮是否在執(zhí)行?BGSAVE?命令或者?BGREWRITEAOF 是因?yàn)樽髡卟幌朐谧舆M(jìn)程執(zhí)行保存操作使用寫時(shí)復(fù)制時(shí)使用過(guò)多內(nèi)存(for Redis, as we use copy-on-write and don't want to move too much memory around when there is a child performing saving operations.)
在負(fù)載閾值小于0.1的情況下會(huì)進(jìn)行緊縮操作，緊縮后的table是大于used值的最小2次冪
在遷移的時(shí)候會(huì)生成一個(gè)新的table付給 ht[1],ht[0]被不斷的遷到ht[1]中卒煞，新增操作也只在ht[1]中進(jìn)行痪宰，查找會(huì)依次在兩個(gè)表中進(jìn)行，如果沒有找到的話畔裕，不管是擴(kuò)展還是緊縮操作都不會(huì)立即一次性完成衣撬，而是在redis 字典進(jìn)程插入，獲取等操作是進(jìn)行一定數(shù)量或者一定時(shí)間片段的遷移(1毫秒)扮饶，直到遷移成功具练，遷移完成，將ht[1]付給ht[0]甜无，ht[1]被置空
二.golang 中的map
golang 中的map是用hash表實(shí)現(xiàn)的,源碼路徑為runtime/hashmap.go?
其中buckets 和 oldbuckets是map兩個(gè)桶扛点，一般只用buckets，在map過(guò)大岂丘，或者map負(fù)載過(guò)大會(huì)進(jìn)行rehash陵究，bucket大小為2^B次方大小，flag記錄當(dāng)前map狀態(tài)
flag值為
map在hashWriting時(shí)再寫會(huì)拋出錯(cuò)誤奥帘，sameSizeGrow為假時(shí)rehash擴(kuò)大原buckets的2倍畔乙，否則新的buckets和原buckets大小一致
每個(gè)buckets默認(rèn)存儲(chǔ)8個(gè)key
但buckets不是直接存儲(chǔ)key，每個(gè)key的hash值的低位表示所存儲(chǔ)桶的索引翩概，而高位存儲(chǔ)在tophash數(shù)組中牲距，每個(gè)bucket首先存儲(chǔ)的就是一個(gè)tophash數(shù)組返咱，用于遍歷快速找到key，0到4不是有效的hash值牍鞠，在tophash數(shù)組后面是key咖摹，key的后面是value，key value并不是按照我們常規(guī)的key/value/key/value/... 這樣子存儲(chǔ)而是按照key/key/..../value/value/...存儲(chǔ)這樣存儲(chǔ)是為了節(jié)省padding空間假如 在map[int64]int8中难述，4個(gè)相鄰的int8可以存儲(chǔ)在同一個(gè)內(nèi)存單元中萤晴。如果使用kv交錯(cuò)存儲(chǔ)的話，每個(gè)int8都會(huì)被padding占用單獨(dú)的內(nèi)存單元（為了提高尋址速度）胁后，再后面是一個(gè)overflow指針店读，在默認(rèn)的8個(gè)key存滿之后，多出key value對(duì)會(huì)組成新的bucket掛在之前的bucket后面攀芯，由overflow指針指向屯断，再多是同樣處理，所以golang的map用的是主要還是鏈地址法解決沖突
如果超出擴(kuò)展閾值或者太多overflow鏈表侣诺，map就會(huì)進(jìn)行擴(kuò)展殖演，原來(lái)的bucket會(huì)變成oldbucket，新的bucket 是原bucket 的兩倍年鸳，如果只是太多overflow鏈表而不是超過(guò)了擴(kuò)展閾值則新的bucket和之前的大小一樣趴久，相當(dāng)于做了個(gè)緊縮操作，函數(shù)為hashGrow()會(huì)創(chuàng)建新的bucket搔确，舊的bucket會(huì)地址會(huì)賦值給oldbuckets指針彼棍，散列操作在growWork()函數(shù) ,擴(kuò)展不是一次性完成的而是在插入，刪除時(shí)一次遷移一個(gè)或者兩個(gè)(本次操作的bucket和上次還沒有再擴(kuò)展的bucket)?
tophash值再0到4之間有特殊意義
顯然存儲(chǔ)整個(gè)hash值會(huì)浪費(fèi)很多空間座硕，而且作者似乎不想每次都比較key值，bucket中只存儲(chǔ)了hash值得高8位
總結(jié)：
相似的地方 ：
1.都使用2個(gè)hashtable畦幢，其中一個(gè)一般不使用坎吻，在擴(kuò)展和收縮的時(shí)候會(huì)從一個(gè)遷移到另一個(gè)
2.都是漸進(jìn)的rehash，不是一次性的完成rehash操作宇葱，出于對(duì)性能的考慮瘦真，都選擇了每次執(zhí)行查插刪改的時(shí)候順帶進(jìn)行一定量的rehash的操作，這樣既不會(huì)一次占用太多執(zhí)行時(shí)間黍瞧，也會(huì)最終把遷移完成
3.都用鏈地址法解決沖突诸尽，雖然實(shí)現(xiàn)細(xì)節(jié)上稍有不同(云風(fēng)大神說(shuō)lua是閉散列的我沒有研究)
4.兩個(gè)hashtable的長(zhǎng)度都是2的n次冪，更容易進(jìn)行取模操作印颤，擴(kuò)展操作也是2倍操作
不同的地方：
1.golang實(shí)現(xiàn)更復(fù)雜一些您机，雖然都是用鏈表解決沖突，但是golang更講究對(duì)內(nèi)存的管理，盡量用一段連續(xù)的內(nèi)存际看，而redis就直接用鏈表了咸产，redis用了更多內(nèi)存存儲(chǔ)鏈表的指針，golang雖然也存儲(chǔ)了的指針仲闽，但只是overflow指針脑溢，但是有把hash值得高位存起來(lái)
2.因?yàn)間olang的存儲(chǔ)結(jié)構(gòu)，取值基本是地址加偏移量的操作赖欣，而redis都是取地址再查找屑彻，命中率沒有那么高，但是golan管理更加復(fù)雜
3.golang hash值得低位是桶索引顶吮，高位是用來(lái)快速查找key且被存儲(chǔ)社牲，而redis的hash值只用來(lái)定位桶，查找key是直接比較悴了，并沒有存儲(chǔ)hash值
4.redis的hash算法是murmur2算法搏恤，golang map使用的算法是受 xxhash和cityhash啟發(fā)的新算法，源碼在runtime/hash32.go,runtime/hash64.go中
遺漏：
沒有深看golang的map的緊縮算法,只看到在overflow鏈表過(guò)多而整個(gè)map沒有過(guò)負(fù)載的情況下會(huì)rehash让禀，但是新的buckets數(shù)量和原buckets大小一致
參考：
http://wudaijun.com/2016/09/go-notes-1-datastructures/
https://blog.yiz96.com/golang-map/
https://blog.codingnow.com/2013/08/reading_golang_source.html
以上挑社，如有錯(cuò)誤歡迎指出
