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

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

哈希沖突的解決方式

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

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

先看這樣一張圖:

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

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

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

比如我們要查找16:

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

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

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

隨機層數的計算過程如下:

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

一般來說,層的數量越多,訪問其他節點的速度越快。

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

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

特性

看他的名字就能看出來,是為了節省內存造的列表結構。

3、Redis常見數據結構以及使用場景分別是什么?

String

String數據結構是簡單的key-value類型,value其實不僅可以是String,也可以是數字。常規key-value緩存應用;常規計數:微博數,粉絲數等。

Hash

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

List

list 就是鏈表,Redis list 的應用場景非常多,也是Redis最重要的數據結構之一,比如微博的關注列表,粉絲列表, 消息列表等功能都可以用Redis的 list 結構來實現。

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

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

Set

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

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

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

Sorted Set

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

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