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

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

哈希沖突的解決方式

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

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

先看這樣一張圖:

如上圖,我們要查找一個(gè)元素,就需要從頭節(jié)點(diǎn)開始遍歷,直到找到對(duì)應(yīng)的節(jié)點(diǎn)或者是第一個(gè)大于要查找的元素的節(jié)點(diǎn)(沒找到)。時(shí)間復(fù)雜度為O(N)。

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

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

比如我們要查找16:

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

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

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

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

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

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

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

壓縮列表(ziplist)是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng),并且每個(gè)列表項(xiàng)要么就是小整數(shù)值,要么就是長度比較短的字符串,那么Redis就會(huì)使用壓縮列表來做列表鍵的底層實(shí)現(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其實(shí)不僅可以是String,也可以是數(shù)字。常規(guī)key-value緩存應(yīng)用;常規(guī)計(jì)數(shù):微博數(shù),粉絲數(shù)等。

Hash

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

List

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

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

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

Set

set 對(duì)外提供的功能與list類似是一個(gè)列表的功能,特殊之處在于 set 是可以自動(dòng)排重的。

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

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

Sorted Set

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

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