哈希表typedef struct dictht {
   // 哈希表數(shù)組
   dictEntry **table;
   // 哈希表大小
   unsigned long size;
   // 哈希表大小掩碼,用于計算索引值
   // 總是等于size-1
   unsigned long sizemark;
   // 該哈希表已有節(jié)點的數(shù)量
   unsigned long used;
} dichht;
哈希算法

當字典被用作數(shù)據(jù)庫的底層實現(xiàn),或者哈希鍵的底層實現(xiàn)時,Redis使用MurmurHash算法。這種算法的優(yōu)點在于即使輸入的鍵是規(guī)律的,算法仍能給出一個個很好的隨機分布性,并且算法的計算速度非常快。

哈希沖突的解決方式

Redis的哈希表使用鏈地址法來解決鍵沖突,每個哈希表節(jié)點都有一個next指針,多個哈希表節(jié)點可以用這個單向鏈表連接起來,這就解決了鍵沖突的問題。

特性字典被廣泛用于實現(xiàn)Redis的各種功能,其中包括數(shù)據(jù)庫和哈希鍵。Redis中的字典使用哈希表作為底層結(jié)構(gòu)實現(xiàn),每個字典帶有兩個哈希表,一個平時使用,另一個僅在進行rehash時使用。Redis使用MurmurHash2算法來計算鍵的哈希值。哈希表使用鏈地址法來解決鍵沖突。跳躍表

先看這樣一張圖:

如上圖,我們要查找一個元素,就需要從頭節(jié)點開始遍歷,直到找到對應的節(jié)點或者是第一個大于要查找的元素的節(jié)點(沒找到)。時間復雜度為O(N)。

這個查找效率是比較低的,但如果我們把列表的某些節(jié)點拔高一層,如下圖,例如把每兩個節(jié)點中有一個節(jié)點變成兩層。那么第二層的節(jié)點只有第一層的一半,查找效率也就會提高。

查找的步驟是從頭節(jié)點的頂層開始,查到第一個大于指定元素的節(jié)點時,退回上一節(jié)點,在下一層繼續(xù)查找。

比如我們要查找16:

從頭節(jié)點的最頂層開始,先到節(jié)點7。7的下一個節(jié)點是39,大于16,因此我們退回到7從7開始,在下一層繼續(xù)查找,就可以找到16。

這個例子中遍歷的節(jié)點不比一維列表少,但是當節(jié)點更多,查找的數(shù)字更大時,這種做法的優(yōu)勢就體現(xiàn)出來了。還是上面的例子,如果我們要查找的是39,那么只需要訪問兩個節(jié)點(7、39)就可以找到了。這比一維列表要減少一半的數(shù)量。

為了避免插入操作的時間復雜度是O(N),skiplist每層的數(shù)量不會嚴格按照2:1的比例,而是對每個要插入的元素隨機一個層數(shù)。

隨機層數(shù)的計算過程如下:

每個節(jié)點都有第一層那么它有第二層的概率是p,有第三層的概率是p*p不能超過最大層數(shù)zskiplistNodetypedef struct zskiplistNode {
   // 后退指針
   struct zskiplistNode *backward;
   // 分值 權(quán)重
   double score;
   // 成員對象
   robj *obj;
   // 層
   struct zskiplistLevel {
       // 前進指針
       struct zskiplistNode *forward;
       // 跨度
       unsigned int span;
   } leval[];
} zskiplistNode;

一般來說,層的數(shù)量越多,訪問其他節(jié)點的速度越快。

zskipListtypedef struct zskiplist {
   // 表頭節(jié)點和表尾節(jié)點
   struct zskiplistNode *header, *tail;
   // 表中節(jié)點的數(shù)量
   unsigned long length;
   // 表中層數(shù)最大的節(jié)點的層數(shù)
   int leval;
} zskiplist;
特性跳躍表是有序集合的底層實現(xiàn)之一Redis的跳躍表實現(xiàn)由zskiplist和zskiplistNode兩個結(jié)構(gòu)組成,其中zskiplist用于保存跳躍表信息(比如表頭節(jié)點、表尾節(jié)點、長度),而zskiplistNode則用于表示跳躍表節(jié)點每個跳躍表節(jié)點的層高都是1至32之間的隨機數(shù)在同一個跳躍表中,多個節(jié)點可以包含相同的分值,但每個節(jié)點的成員對象必須是唯一的。跳躍表中的節(jié)點按照分值大小進行排序,當分值相同時,節(jié)點按照成員對象的大小進行排序。跳表是一種實現(xiàn)起來很簡單,單層多指針的鏈表,它查找效率很高,堪比優(yōu)化過的二叉平衡樹,且比平衡樹的實現(xiàn)。壓縮列表“

壓縮列表(ziplist)是列表鍵和哈希鍵的底層實現(xiàn)之一。當一個列表鍵只包含少量列表項,并且每個列表項要么就是小整數(shù)值,要么就是長度比較短的字符串,那么Redis就會使用壓縮列表來做列表鍵的底層實現(xiàn)。

特性

看他的名字就能看出來,是為了節(jié)省內(nèi)存造的列表結(jié)構(gòu)。

3、Redis常見數(shù)據(jù)結(jié)構(gòu)以及使用場景分別是什么?

String

String數(shù)據(jù)結(jié)構(gòu)是簡單的key-value類型,value其實不僅可以是String,也可以是數(shù)字。常規(guī)key-value緩存應用;常規(guī)計數(shù):微博數(shù),粉絲數(shù)等。

Hash

Hash 是一個 string 類型的 ?eld 和 value 的映射表,hash 特別適合用于存儲對象,后續(xù)操作的時候,你可以直接僅 僅修改這個對象中的某個字段的值。比如我們可以Hash數(shù)據(jù)結(jié)構(gòu)來存儲用戶信息,商品信息等。

List

list 就是鏈表,Redis list 的應用場景非常多,也是Redis最重要的數(shù)據(jù)結(jié)構(gòu)之一,比如微博的關注列表,粉絲列表, 消息列表等功能都可以用Redis的 list 結(jié)構(gòu)來實現(xiàn)。

Redis list 的實現(xiàn)為一個雙向鏈表,即可以支持反向查找和遍歷,更方便操作,不過帶來了部分額外的內(nèi)存開銷。

另外可以通過 lrange 命令,就是從某個元素開始讀取多少個元素,可以基于 list 實現(xiàn)分頁查詢,這個很棒的一個功 能,基于 Redis 實現(xiàn)簡單的高性能分頁,可以做類似微博那種下拉不斷分頁的東西(一頁一頁的往下走),性能高。

Set

set 對外提供的功能與list類似是一個列表的功能,特殊之處在于 set 是可以自動排重的。

當你需要存儲一個列表數(shù)據(jù),又不希望出現(xiàn)重復數(shù)據(jù)時,set是一個很好的選擇,并且set提供了判斷某個成員是否在 一個set集合內(nèi)的重要接口,這個也是list所不能提供的�？梢曰�于 set 輕易實現(xiàn)交集、并集、差集的操作。

比如:在微博應用中,可以將一個用戶所有的關注人存在一個集合中,將其所有粉絲存在一個集合。Redis可以非常 方便的實現(xiàn)如共同關注、共同粉絲、共同喜好等功能。這個過程也就是求交集的過程,具體命令如下:sinterstore key1 key2 key3將交集存在key1內(nèi)。

Sorted Set

和set相比,sorted set增加了一個權(quán)重參數(shù)score,使得集合中的元素能夠按score進行有序排列。

舉例:在直播系統(tǒng)中,實時排行信息包含直播間在線用戶列表,各種禮物排行榜,彈幕消息(可以理解為按消息維 度的消息排行榜)等信息,適合使用 Redis 中的 SortedSet 結(jié)構(gòu)進行存儲。