一些常用的redis結(jié)構(gòu),底層實(shí)現(xiàn)及方法
哈希表
在redis當(dāng)中，使用哈希表作為字典的底層實(shí)現(xiàn)，底層是數(shù)組+鏈表
在向里面添加元素時候，需要計(jì)算其索引位置：index = hash & dict->ht[x].sizemask()**
哈希表采用鏈地址法來解決哈希沖突
rehash--使哈希表的大小總處在一個合理的大小，rehash的過程，是另一個哈希表（h[0]或者h(yuǎn)[1]）（大小增大或者減小2倍），然后將數(shù)據(jù)遷移過去?？紤]數(shù)據(jù)量一般都是漸進(jìn)式rehash，將遷入的過程包含在對數(shù)據(jù)庫的操作過程中
跳躍表
跳躍表與跳表是相同的目的，為鏈表加快查詢，使用拋硬幣法決定其是否上升
有序集合鍵的底層實(shí)現(xiàn)
通過在每個節(jié)點(diǎn)維持多個指向其他節(jié)點(diǎn)的指針，達(dá)到快速訪問下一個節(jié)點(diǎn)的目的
redis里面的跳躍表由兩部分組成
1，zipNod(頭)： herd（頭指針）,tail(尾指針),level(最大層數(shù)),length(長度)
2，zipList(節(jié)點(diǎn))： 由前進(jìn)指針和跨度組成（跨度表示兩個節(jié)點(diǎn)之間的距離，跨度是用來計(jì)算排序的，前進(jìn)指針是指向后面節(jié)點(diǎn)的指針）
跳躍表的結(jié)構(gòu)如下所示
跳躍表的核心就是其的查找操作。舉個例子，比如要查找14，從頭節(jié)點(diǎn)最高開始，指向9，9<14,所以繼續(xù)向后查找到21，21>14，這個時候9這個節(jié)點(diǎn)的指針下移，下一個節(jié)點(diǎn)是17，17>14.繼續(xù)下移12，12.小于該節(jié)點(diǎn)，到12節(jié)點(diǎn)，由于12節(jié)點(diǎn)之后是已經(jīng)指向過的17，所以最后沒有查找到這個節(jié)點(diǎn)，如果這個時候需要加入，則將新建節(jié)點(diǎn)，鏈到12后面，使用拋硬幣的方法判斷其是否上升，上升的話，底層依舊是12->14->17,第二層就是9->14->17.再用拋硬幣法判斷其是否上升
刪除同樣道理，就是沒有增加拋硬幣的做法
整數(shù)數(shù)組
redis的整數(shù)數(shù)組結(jié)構(gòu)里面就是結(jié)構(gòu)體里面套數(shù)組，特殊支持，就是數(shù)組的升級策略（encoding屬性從16->32->64）升級之后相應(yīng)數(shù)組的節(jié)點(diǎn)大小就會相應(yīng)擴(kuò)大(O(N))，升級策略的目的是為了節(jié)約內(nèi)存，提高靈活性。
整數(shù)集合·不支持降級操作
壓縮列表
壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)（目的---節(jié)約內(nèi)存）
由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序數(shù)據(jù)結(jié)構(gòu)（redis里面壓縮列表結(jié)構(gòu)如下）
節(jié)點(diǎn)里面有一個字段previous_entry_length記錄了前一個節(jié)點(diǎn)的長度，長度小于254字節(jié)，則需要1字節(jié)去存儲，大于則就用5字節(jié)存儲，而插入新節(jié)點(diǎn)的時候可能第一個節(jié)點(diǎn)的長度>244,造成原來e1節(jié)點(diǎn)的長度變大，造成連鎖跟新的情況。同理，刪除節(jié)點(diǎn)也會造成連鎖跟新。
HyperLogLog-基數(shù)統(tǒng)計(jì)
Redis HyperLogLog 是用來做基數(shù)統(tǒng)計(jì)的算法，基數(shù)-及所輸入元素當(dāng)中的不重復(fù)的元素個數(shù)。HyperLogLog 的優(yōu)點(diǎn)是，在輸入元素的數(shù)量或者體積非常非常大時，計(jì)算基數(shù)所需的空間總是固定 的、并且是很小的。在 Redis 里面，每個 HyperLogLog 鍵只需要花費(fèi) 12 KB 內(nèi)存，就可以計(jì)算接近 2^64 個不同元素的基 數(shù)。redis只會根據(jù)輸入元素來統(tǒng)計(jì)基數(shù)，而不會存儲數(shù)據(jù)。
常用命令：
PFADD key element [element ...]]:添加指定元素到 HyperLogLog 中。 |
|[PFCOUNT key [key ...]:返回給定 HyperLogLog 的基數(shù)估算值。 |
[PFMERGE destkey sourcekey [sourcekey ...]]:
將多個 HyperLogLog 合并為一個 HyperLogLog |
參考：小綠書
