你真的懂Redis的5種基本數據結構嗎？這些知識點或許你還需要看看（圖文并茂，淺顯易懂，建議收藏）

一、簡介

Redis中所有的的數據結構都是通過一個唯一的字符串key來獲取相應的value數據。

Redis有5種基礎數據結構，分別是：

string（字符串）

list（列表）

hash（字典）

set（集合）

zset（有序集合）

其中list、set、hash、zset這四種數據結構是容器型數據結構，它們共享下面兩條通用規則：

create if not exists：容器不存在則創建

drop if no elements：如果容器中沒有元素，則立即刪除容器，釋放內存

本文將詳細講述的是Redis的5種基礎數據結構。

二、string（字符串）

1、string(字符串)相關介紹

1.1 string(字符串)的內部結構

string(字符串)是Redis最簡單也是使用最廣泛的數據結構，它的內部是一個字符數組。如圖所示：

Redis中string(字符串)是動態字符串，允許修改；它在結構上的實現類似于Java中的ArrayList（默認構造一個大小為10的初始數組），這是冗余分配內存的思想，也稱為預分配；這種思想可以減少擴容帶來的性能消耗。

1.2 string(字符串)的擴容

當string(字符串)的大小達到擴容閾值時，將會對string(字符串)進行擴容，string(字符串)的擴容主要有以下幾個點：

長度小于1MB，擴容后為原先的兩倍; length = length * 2

長度大于1MB，擴容后增加1MB; length = length + 1MB

字符串的長度最大值為 512MB

2、string(字符串)的指令

2.1 單個鍵值對增刪改查操作

set -> key 不存在則新增，存在則修改

set key value

get -> 查詢，返回對應key的value，不存在返回(nil)

get key

del -> 刪除指定的key(key可以是多個)

del key [key …]

示例：

1127.0.0.1:6379> set name liziba 2OK 3127.0.0.1:6379> get name 4"liziba" 5127.0.0.1:6379> set name liziba001 6OK 7127.0.0.1:6379> get name 8"liziba001" 9127.0.0.1:6379> del name 10(integer) 1 11127.0.0.1:6379> get name 12(nil)

2.2 批量鍵值對

批量鍵值讀取和寫入最大的優勢在于節省網絡傳輸開銷

mset -> 批量插入

mset key value [key value …]

mget -> 批量獲取

mget key [key …]

示例：

1127.0.0.1:6379> mset name1 liziba1 name2 liziba2 name3 liziba3 2OK 3127.0.0.1:6379> mget name1 name2 name3 41) "liziba1" 52) "liziba2" 63) "liziba3"

2.3 過期set命令

過期set是通過設置一個緩存key的過期時間，使得緩存到期后自動刪除從而失效的機制。

方式一：

expire key seconds

示例：

1127.0.0.1:6379> set name liziba 2OK 3127.0.0.1:6379> get name 4"liziba" 5127.0.0.1:6379> expire name 10 # 10s 后get name 返回 nil 6(integer) 1 7127.0.0.1:6379> get name 8(nil)

方式二：

setex key seconds value

示例：

1127.0.0.1:6379> setex name 10 liziba # 10s 后get name 返回 nil 2OK 3127.0.0.1:6379> get name 4(nil)

2.4 不存在創建存在不更新

上面的set操作不存在創建，存在則更新；此時如果需要存在不更新的場景，那么可以使用如下這個指令

setnx -> 不存在創建存在不更新

setnx key value

示例：

1127.0.0.1:6379> get name 2(nil) 3127.0.0.1:6379> setnx name liziba 4(integer) 1 5127.0.0.1:6379> get name 6"liziba" 7127.0.0.1:6379> setnx name liziba_98 # 已經存在再次設值，失敗 8(integer) 0 9127.0.0.1:6379> get name 10"liziba"

2.5計數

string(字符串)也可以用來計數，前提是value是一個整數，那么可以對它進行自增的操作。自增的范圍必須在signed long的區間訪問內，[-9223372036854775808,9223372036854775808]

incr -> 自增1

incr key

示例：

1127.0.0.1:6379> set fans 1000 2OK 3127.0.0.1:6379> incr fans # 自增1 4(integer) 1001

incrby -> 自定義累加值

incrby key increment

1127.0.0.1:6379> set fans 1000 2OK 3127.0.0.1:6379> incr fans 4(integer) 1001 5127.0.0.1:6379> incrby fans 999 6(integer) 2000

測試value為整數的自增區間

最大值：

1127.0.0.1:6379> set fans 9223372036854775808 2OK 3127.0.0.1:6379> incr fans 4(error) ERR value is not an integer or out of range

最小值：

1127.0.0.1:6379> set money -9223372036854775808 2OK 3127.0.0.1:6379> incrby money -1 4(error) ERR increment or decrement would overflow

三、list（列表）

1、list(列表)相關介紹

1.1 list(列表)的內部結構

Redis的列表相當于Java語言中的LinkedList，它是一個雙向鏈表數據結構（但是這個結構設計比較巧妙，后面會介紹），支持前后順序遍歷。鏈表結構插入和刪除操作快，時間復雜度O(1)，查詢慢，時間復雜度O(n)。

1.2 list(列表)的使用場景

根據Redis雙向列表的特性，因此其也被用于異步隊列的使用。實際開發中將需要延后處理的任務結構體序列化成字符串，放入Redis的隊列中，另一個線程從這個列表中獲取數據進行后續處理。其流程類似如下的圖：

2、list(列表)的指令

2.1 右進左出—隊列

隊列在結構上是先進先出（FIFO）的數據結構（比如排隊購票的順序），常用于消息隊列類似的功能，例如消息排隊、異步處理等場景。通過它可以確保元素的訪問順序。

lpush -> 從左邊邊添加元素

lpush key value [value …]

rpush -> 從右邊添加元素

rpush key value [value …]

llen -> 獲取列表的長度

llen key

lpop -> 從左邊彈出元素

lpop key

1127.0.0.1:6379> rpush code java c python # 向列表中添加元素 2(integer) 3 3127.0.0.1:6379> llen code # 獲取列表長度 4(integer) 3 5127.0.0.1:6379> lpop code # 彈出最先添加的元素 6"java" 7127.0.0.1:6379> lpop code 8"c" 9127.0.0.1:6379> lpop code 10"python" 11127.0.0.1:6379> llen code 12(integer) 0 13127.0.0.1:6379> lpop code 14(nil)

2.2 右進右出——棧

棧在結構上是先進后出（FILO）的數據結構（比如彈夾壓入子彈，子彈被射擊出去的順序就是棧），這種數據結構一般用來逆序輸出。

lpush -> 從左邊邊添加元素

lpush key value [value …]

rpush -> 從右邊添加元素

rpush key value [value …]

rpop -> 從右邊彈出元素

rpop code

1127.0.0.1:6379> rpush code java c python 2(integer) 3 3127.0.0.1:6379> rpop code # 彈出最后添加的元素 4"python" 5127.0.0.1:6379> rpop code 6"c" 7127.0.0.1:6379> rpop code 8"java" 9127.0.0.1:6379> rpop code 10(nil)

2.3 慢操作

列表(list)是個鏈表數據結構，它的遍歷是慢操作，所以涉及到遍歷的性能將會遍歷區間range的增大而增大。注意list的索引運行為負數，-1代表倒數第一個，-2代表倒數第二個，其它同理。

lindex -> 遍歷獲取列表指定索引處的值

lindex key ind

lrange -> 獲取從索引start到stop處的全部值

lrange key start stop

ltrim -> 截取索引start到stop處的全部值，其它將會被刪除

ltrim key start stop

1127.0.0.1:6379> rpush code java c python 2(integer) 3 3127.0.0.1:6379> lindex code 0 # 獲取索引為0的數據 4"java" 5127.0.0.1:6379> lindex code 1 # 獲取索引為1的數據 6"c" 7127.0.0.1:6379> lindex code 2 # 獲取索引為2的數據 8"python" 9127.0.0.1:6379> lrange code 0 -1 # 獲取全部 0 到倒數第一個數據 == 獲取全部數據 101) "java" 112) "c" 123) "python" 13127.0.0.1:6379> ltrim code 0 -1 # 截取并保理 0 到 -1 的數據 == 保理全部 14OK 15127.0.0.1:6379> lrange code 0 -1 161) "java" 172) "c" 183) "python" 19127.0.0.1:6379> ltrim code 1 -1 # 截取并保理 1 到 -1 的數據 == 移除了索引為0的數據 java 20OK 21127.0.0.1:6379> lrange code 0 -1 221) "c" 232) "python"

3、list(列表)深入理解

Redis底層存儲list(列表)不是一個簡單的LinkedList，而是quicklist ——“快速列表”。關于quicklist是什么，下面會簡單介紹，具體源碼我也還在學習中，后面大家一起探討。

quicklist是多個ziplist(壓縮列表)組成的雙向列表；而這個ziplist(壓縮列表)又是什么呢？ziplist指的是一塊連續的內存存儲空間，Redis底層對于list(列表)的存儲，當元素個數少的時候，它會使用一塊連續的內存空間來存儲，這樣可以減少每個元素增加prev和next指針帶來的內存消耗，最重要的是可以減少內存碎片化問題。

3.1 常見的鏈表結構示意圖

每個node節點元素，都會持有一個prev->執行前一個node節點和next->指向后一個node節點的指針（引用），這種結構雖然支持前后順序遍歷，但是也帶來了不小的內存開銷，如果node節點僅僅是一個int類型的值，那么可想而知，引用的內存比例將會更大。

3.2 ziplist示意圖

ziplist是一塊連續的內存地址，他們之間無需持有prev和next指針，能通過地址順序尋址訪問。

3.3 quicklist示意圖

quicklist是由多個ziplist組成的雙向鏈表。

四、hash（字典）

1、hash(字典)相關介紹

1.1 hash(字典)的內部結構

Redis的hash(字典)相當于Java語言中的HashMap，它是根據散列值分布的無序字典，內部的元素是通過鍵值對的方式存儲。

hash(字典)的實現與Java中的HashMap（JDK1.7）的結構也是一致的，它的數據結構也是數組+鏈表組成的二維結構，節點元素散列在數組上，如果發生hash碰撞則使用鏈表串聯在數組節點上。

1.2 hash(字典)擴容

Redis中的hash(字典)存儲的value只能是字符串值，此外擴容與Java中的HashMap也不同。Java中的HashMap在擴容的時候是一次性完成的，而Redis考慮到其核心存取是單線程的性能問題，為了追求高性能，因而采取了漸進式rehash策略。

漸進式rehash指的是并非一次性完成，它是多次完成的，因此需要保理舊的hash結構，所以Redis中的hash(字典)會存在新舊兩個hash結構，在rehash結束后也就是舊hash的值全部搬遷到新hash之后，新的hash在功能上才會完全替代以前的hash。

1.3 hash(字典)的相關使用場景

hash(字典)可以用來存儲對象的相關信息，一個hash(字典)代表一個對象，hash的一個key代表對象的一個屬性，key的值代表屬性的值。hash(字典)結構相比字符串來說，它無需將整個對象進行序列化后進行存儲。這樣在獲取的時候可以進行部分獲取。所以相比之下hash(字典)具有如下的優缺點：

讀取可以部分讀取，節省網絡流量

存儲消耗的高于單個字符串的存儲

2 hash(字典)相關指令

2.1 hash(字典)常用指令

hset -> hash(字典)插入值，字典不存在則創建 key代表字典名稱，field 相當于 key，value是key的值

hset key field value

hmset -> 批量設值

hmset key field value [field value …]

示例：

17.0.0.1:6379> hset book java "Thinking in Java" # 字符串包含空格需要""包裹 2(integer) 1 3127.0.0.1:6379> hset book python "Python code" 4(integer) 1 5127.0.0.1:6379> hset book c "The best of c" 6(integer) 1 7127.0.0.1:6379> hmset book go "concurrency in go" mysql "high-performance MySQL" # 批量設值 8OK

hget -> 獲取字典中的指定key的value

hget key field

hgetall -> 獲取字典中所有的key和value，換行輸出

hgetall key

示例：

1127.0.0.1:6379> hget book java 2"Thinking in Java" 3127.0.0.1:6379> hgetall book 41) "java" 52) "Thinking in Java" 63) "python" 74) "Python code" 85) "c" 96) "The best of c"

hlen -> 獲取指定字典的key的個數

hlen key

舉例：

1127.0.0.1:6379> hlen book 2(integer) 5

2.2 hash(字典)使用小技巧

在string(字符串)中可以使用incr和incrby對value是整數的字符串進行自加操作，在hash(字典)結構中如果單個子key是整數也可以進行自加操作。

hincrby -> 增對hash(字典)中的某個key的整數value進行自加操作

hincrby key field increment

1127.0.0.1:6379> hset liziba money 10 2(integer) 1 3127.0.0.1:6379> hincrby liziba money -1 4(integer) 9 5127.0.0.1:6379> hget liziba money 6"9"

注意如果不是整數會報錯。

1127.0.0.1:6379> hset liziba money 10.1 2(integer) 1 3127.0.0.1:6379> hincrby liziba money 1 4(error) ERR hash value is not an integer

五、set（集合）

1、set(集合)相關介紹

1.1 set(集合)的內部結構

Redis的set(集合)相當于Java語言里的HashSet，它內部的鍵值對是無序的、唯一的。它的內部實現了一個所有value為null的特殊字典。

集合中的最后一個元素被移除之后，數據結構被自動刪除，內存被回收。

1.2 set(集合)的使用場景

set(集合)由于其特殊去重復的功能，我們可以用來存儲活動中中獎的用戶的ID，這樣可以保證一個用戶不會中獎兩次。

2、set(集合)相關指令

sadd -> 添加集合成員，key值集合名稱，member值集合元素，元素不能重復

sadd key member [member …]

1127.0.0.1:6379> sadd name zhangsan 2(integer) 1 3127.0.0.1:6379> sadd name zhangsan # 不能重復，重復返回0 4(integer) 0 5127.0.0.1:6379> sadd name lisi wangwu liumazi # 支持一次添加多個元素 6(integer) 3

smembers -> 查看集合中所有的元素，注意是無序的

smembers key

1127.0.0.1:6379> smembers name # 無序輸出集合中所有的元素 21) "lisi" 32) "wangwu" 43) "liumazi" 54) "zhangsan"

sismember -> 查詢集合中是否包含某個元素

sismember key member

1127.0.0.1:6379> sismember name lisi # 包含返回1 2(integer) 1 3127.0.0.1:6379> sismember name tianqi # 不包含返回0 4(integer) 0

scard -> 獲取集合的長度

scard key

1127.0.0.1:6379> scard name 2(integer) 4

spop -> 彈出元素，count指彈出元素的個數

spop key [count]

1127.0.0.1:6379> spop name # 默認彈出一個 2"wangwu" 3127.0.0.1:6379> spop name 3 41) "lisi" 52) "zhangsan" 63) "liumazi"

六、zset（有序集合）

1、zset(有序集合)相關介紹

1.1 zset(有序集合)的內部結構

zset(有序集合)是Redis中最常問的數據結構。它類似于Java語言中的SortedSet和HashMap的結合體，它一方面通過set來保證內部value值的唯一性，另一方面通過value的score（權重）來進行排序。這個排序的功能是通過Skip List（跳躍列表）來實現的。

zset(有序集合)的最后一個元素value被移除后，數據結構被自動刪除，內存被回收。

1.2 zset(有序集合)的相關使用場景

利用zset的去重和有序的效果可以由很多使用場景，舉兩個例子：

存儲粉絲列表，value是粉絲的ID，score是關注時間戳，這樣可以對粉絲關注進行排序

存儲學生成績，value使學生的ID，score是學生的成績，這樣可以對學生的成績排名

2、zset(有序集合)相關指令

1、zadd -> 向集合中添加元素，集合不存在則新建，key代表zset集合名稱，score代表元素的權重，member代表元素

zadd key [NX|XX] [CH] [INCR] score member [score member …]

1127.0.0.1:6379> zadd name 10 zhangsan 2(integer) 1 3127.0.0.1:6379> zadd name 10.1 lisi 4(integer) 1 5127.0.0.1:6379> zadd name 9.9 wangwu 6(integer) 1

2、zrange -> 按照score權重從小到大排序輸出集合中的元素，權重相同則按照value的字典順序排序([lexicographical order])

超出范圍的下標并不會引起錯誤。 比如說，當 start 的值比有序集的最大下標還要大，或是 start > stop 時， zrange 命令只是簡單地返回一個空列表。 另一方面，假如 stop 參數的值比有序集的最大下標還要大，那么 Redis 將 stop 當作最大下標來處理。

可以通過使用 WITHSCORES 選項，來讓成員和它的 score 值一并返回，返回列表以 value1,score1, …, valueN,scoreN 的格式表示。 客戶端庫可能會返回一些更復雜的數據類型，比如數組、元組等。

zrange key start stop [WITHSCORES]

1127.0.0.1:6379> zrange name 0 -1 # 獲取所有元素，按照score的升序輸出 21) "wangwu" 32) "zhangsan" 43) "lisi" 5127.0.0.1:6379> zrange name 0 1 # 獲取第一個和第二個slot的元素 61) "wangwu" 72) "zhangsan" 8127.0.0.1:6379> zadd name 10 tianqi # 在上面的基礎上添加score為10的元素 9(integer) 1 10127.0.0.1:6379> zrange name 0 2 # key相等則按照value字典排序輸出 111) "wangwu" 122) "tianqi" 133) "zhangsan" 14127.0.0.1:6379> zrange name 0 -1 WITHSCORES # WITHSCORES 輸出權重 151) "wangwu" 162) "9.9000000000000004" 173) "tianqi" 184) "10" 195) "zhangsan" 206) "10" 217) "lisi" 228) "10.1"

3、zrevrange -> 按照score權重從大到小輸出集合中的元素，權重相同則按照value的字典逆序排序

其中成員的位置按 score 值遞減(從大到小)來排列。 具有相同 score 值的成員按字典序的逆序(reverse lexicographical order)排列。 除了成員按 score 值遞減的次序排列這一點外， ZREVRANGE 命令的其他方面和 ZRANGE key start stop [WITHSCORES] 命令一樣

zrevrange key start stop [WITHSCORES]

1127.0.0.1:6379> zrevrange name 0 -1 WITHSCORES 21) "lisi" 32) "10.1" 43) "zhangsan" 54) "10" 65) "tianqi" 76) "10" 87) "wangwu" 98) "9.9000000000000004"

4、zcard -> 當 key 存在且是有序集類型時，返回有序集的基數。 當 key 不存在時，返回 0

zcard key

1127.0.0.1:6379> zcard name 2(integer) 4

5、zscore -> 返回有序集 key 中，成員 member 的 score 值，如果 member 元素不是有序集 key 的成員，或 key 不存在，返回 nil

zscore key member z

1127.0.0.1:6379> zscore name zhangsan 2"10" 3127.0.0.1:6379> zscore name liziba 4(nil)

6、zrank -> 返回有序集 key 中成員 member 的排名。其中有序集成員按 score 值遞增(從小到大)順序排列。

排名以 0 為底，也就是說，score 值最小的成員排名為 0

zrank key member

1127.0.0.1:6379> zrange name 0 -1 21) "wangwu" 32) "tianqi" 43) "zhangsan" 54) "lisi" 6127.0.0.1:6379> zrank name wangwu 7(integer) 0

7、zrangebyscore -> 返回有序集 key 中，所有 score 值介于 min 和 max 之間(包括等于 min 或 max )的成員。有序集成員按 score 值遞增(從小到大)次序排列。

min 和 max 可以是 -inf 和 +inf ，這樣一來，你就可以在不知道有序集的最低和最高 score 值的情況下，使用 [ZRANGEBYSCORE]這類命令。

默認情況下，區間的取值使用閉區間，你也可以通過給參數前增加 ( 符號來使用可選的[開區間]小于或大于)

zrangebyscore key min max [WITHSCORES] [LIMIT offset count]

1127.0.0.1:6379> zrange name 0 -1 WITHSCORES # 輸出全部元素 21) "wangwu" 32) "9.9000000000000004" 43) "tianqi" 54) "10" 65) "zhangsan" 76) "10" 87) "lisi" 98) "10.1" 10127.0.0.1:6379> zrangebyscore name 9 10 111) "wangwu" 122) "tianqi" 133) "zhangsan" 14127.0.0.1:6379> zrangebyscore name 9 10 WITHSCORES # 輸出分數 151) "wangwu" 162) "9.9000000000000004" 173) "tianqi" 184) "10" 195) "zhangsan" 206) "10" 21127.0.0.1:6379> zrangebyscore name -inf 10 # -inf 從負無窮開始 221) "wangwu" 232) "tianqi" 243) "zhangsan" 25127.0.0.1:6379> zrangebyscore name -inf +inf # +inf 直到正無窮 261) "wangwu" 272) "tianqi" 283) "zhangsan" 294) "lisi" 30127.0.0.1:6379> zrangebyscore name (10 11 # 10 < score <=11 311) "lisi" 32127.0.0.1:6379> zrangebyscore name (10 (10.1 # 10 < socre < -11 33(empty list or set) 34127.0.0.1:6379> zrangebyscore name (10 (11 351) "lisi"

8、zrem -> 移除有序集 key 中的一個或多個成員，不存在的成員將被忽略

zrem key member [member …]

1127.0.0.1:6379> zrange name 0 -1 21) "wangwu" 32) "tianqi" 43) "zhangsan" 54) "lisi" 6127.0.0.1:6379> zrem name zhangsan # 移除元素 7(integer) 1 8127.0.0.1:6379> zrange name 0 -1 91) "wangwu" 102) "tianqi" 113) "lisi"

七、Skip List

1、簡介

跳表全稱叫做跳躍表，簡稱跳表。跳表是一個隨機化的數據結構，實質就是一種可以進行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現快速查找。跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。

Skip List(跳躍列表)這種隨機的數據結構，可以看做是一個二叉樹的變種，它在性能上與紅黑樹、AVL樹很相近；但是Skip List(跳躍列表)的實現相比前兩者要簡單很多，目前Redis的zset實現采用了Skip List(跳躍列表)（其它還有LevelDB等也使用了跳躍列表）。

RBT紅黑樹與Skip List(跳躍列表)簡單對比：

RBT紅黑樹

插入、查詢時間復雜度O(logn)

數據天然有序

實現復雜，設計變色、左旋右旋平衡等操作

需要加鎖

Skip List跳躍列表

插入、查詢時間復雜度O(logn)

數據天然有序

實現簡單，鏈表結構

無需加鎖

2、Skip List算法分析

2.1 Skip List論文

這里貼出Skip List的論文，需要詳細研究的請看論文，下文部分公式、代碼、圖片出自該論文。

Skip Lists: A Probabilistic Alternative to Balanced Trees

https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf

2.2 Skip List動態圖

先通過一張動圖來了解Skip List的插入節點元素的流程，此圖來自維基百科。

2.3 Skip List算法性能分析

2.3.1 計算隨機層數算法

首先分析的是執行插入操作時計算隨機數的過程，這個過程會涉及層數的計算，所以十分重要。對于節點他有如下特性：

節點都有第一層的指針

節點有第i層指針，那么第i+1層出現的概率為p

節點有最大層數限制，MaxLevel

計算隨機層數的偽代碼：

論文中的示例

Java版本

1public int randomLevel(){ 2 int level = 1; 3 // random()返回一個[0...1)的隨機數 4 while (random() < p && level < MaxLevel){ 5 level += 1; 6 } 7 return level; 8}

代碼中包含兩個變量P和MaxLevel，在Redis中這兩個參數的值分別是：

1p = 1/4 2MaxLevel = 64

2.3.2 節點包含的平均指針數目

Skip List屬于空間換時間的數據結構，這里的空間指的就是每個節點包含的指針數目，這一部分是額外的內內存開銷，可以用來度量空間復雜度。random()是個隨機數，因此產生越高的節點層數，概率越低（Redis標準源碼中的晉升率數據1/4，相對來說Skip List的結構是比較扁平的，層高相對較低）。其定量分析如下：

level = 1 概率為1-p

level >=2 概率為p

level = 2 概率為p(1-p)

level >= 3 概率為p^2

level = 3 概率為p^2(1-p)

level >=4 概率為p^3

level = 4 概率為p^3(1-p)

……

得出節點的平均層數（節點包含的平均指針數目）：

所以Redis中p=1/4計算的平均指針數目為1.33

2.3.3 時間復雜度計算

以下推算來自論文內容

假設p=1/2，在以p=1/2生成的16個元素的跳過列表中，我們可能碰巧具有9個元素，1級3個元素，3個元素3級元素和1個元素14級（這不太可能，但可能會發生）。我們該怎么處理這種情況？如果我們使用標準算法并在第14級開始我們的搜索，我們將會做很多無用的工作。那么我們應該從哪里開始搜索？此時我們假設SkipList中有n個元素，第L層級元素個數的期望是1/p個；每個元素出現在L層的概率是p^(L-1), 那么第L層級元素個數的期望是 n * (p^L-1)；得到1 / p =n * (p^L-1)

11 / p = n * (p^L-1) 2n = (1/p)^L 3L = log(1/p)^n

所以我們應該選擇MaxLevel = log(1/p)^n

定義：MaxLevel = L(n) = log(1/p)^n

推算Skip List的時間復雜度，可以用逆向思維，從層數為i的節點x出發，返回起點的方式來回溯時間復雜度，節點x點存在兩種情況：

節點x存在(i+1)層指針，那么向上爬一級，概率為p，對應下圖situation c.

節點x不存在(i+1)層指針，那么向左爬一級，概率為1-p，對應下圖situation b.

設C(k) = 在無限列表中向上攀升k個level的搜索路徑的預期成本（即長度）那么推演如下：

1C(0)=0 2C(k)=(1-p)×(情況b的查找長度) + p×(情況c的查找長度) 3C(k)=(1-p)(C(k)+1) + p(C(k-1)+1) 4C(k)=1/p+C(k-1) 5C(k)=k/p

上面推演的結果可知，爬升k個level的預期長度為k/p，爬升一個level的長度為1/p。

由于MaxLevel = L(n)， C(k) = k / p，因此期望值為：(L(n) – 1) / p；將L(n) = log(1/p)^n 代入可得：(log(1/p)^n - 1) / p；將p = 1 / 2 代入可得：2 * log2^n - 2，即O(logn)的時間復雜度。

3、Skip List特性及其實現

2.1 Skip List特性

Skip List跳躍列表通常具有如下這些特性

Skip List包含多個層，每層稱為一個level，level從0開始遞增

Skip List 0層，也就是最底層，應該包含所有的元素

每一個level/層都是一個有序的列表

level小的層包含level大的層的元素，也就是說元素A在X層出現，那么 想X>Z>=0的level/層都應該包含元素A

每個節點元素由節點key、節點value和指向當前節點所在level的指針數組組成

2.2 Skip List查詢

假設初始Skip List跳躍列表中已經存在這些元素，他們分布的結構如下所示：

此時查詢節點88，它的查詢路線如下所示：

從Skip List跳躍列表最頂層level3開始，往后查詢到10 < 88 && 后續節點值為null && 存在下層level2

level2 10往后遍歷，27 < 88 && 后續節點值為null && 存在下層level1

level1 27往后遍歷，88 = 88，查詢命中

2.3 Skip List插入

Skip List的初始結構與2.3中的初始結構一致，此時假設插入的新節點元素值為90，插入路線如下所示：

查詢插入位置，與Skip List查詢方式一致，這里需要查詢的是第一個比90大的節點位置，插入在這個節點的前面， 88 < 90 < 100

構造一個新的節點Node(90)，為插入的節點Node(90)計算一個隨機level，這里假設計算的是1，這個level時隨機計算的，可能時1、2、3、4…均有可能，level越大的可能越小，主要看隨機因子x ，層數的概率大致計算為 (1/x)^level ，如果level大于當前的最大level3，需要新增head和tail節點

節點構造完畢后，需要將其插入列表中，插入十分簡單步驟 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);

2.4 Skip List刪除

刪除的流程就是查詢到節點，然后刪除，重新將刪除節點左右兩邊的節點以鏈表的形式組合起來即可，這里不再畫圖

4、手寫實現一個簡單Skip List

實現一個Skip List比較簡單，主要分為兩個步驟：

定義Skip List的節點Node，節點之間以鏈表的形式存儲，因此節點持有相鄰節點的指針，其中prev與next是同一level的前后節點的指針，down與up是同一節點的多個level的上下節點的指針

定義Skip List的實現類，包含節點的插入、刪除、查詢，其中查詢操作分為升序查詢和降序查詢（往后和往前查詢），這里實現的Skip List默認節點之間的元素是升序鏈表

3.1 定義Node節點

Node節點類主要包括如下重要屬性：

score -> 節點的權重，這個與Redis中的score相同，用來節點元素的排序作用

value -> 節點存儲的真實數據，只能存儲String類型的數據

prev -> 當前節點的前驅節點，同一level

next -> 當前節點的后繼節點，同一level

down -> 當前節點的下層節點，同一節點的不同level

up -> 當前節點的上層節點，同一節點的不同level

1package com.liziba.skiplist; 2 3/** 4 *

5 * 跳表節點元素 6 *

7 * 8 * @Author: Liziba 9 * @Date: 2021/7/5 21:01 10 */ 11public class Node { 12 13 /** 節點的分數值，根據分數值來排序 */ 14 public Double score; 15 /** 節點存儲的真實數據 */ 16 public String value; 17 /** 當前節點的 前、后、下、上節點的引用 */ 18 public Node prev, next, down, up; 19 20 public Node(Double score) { 21 this.score = score; 22 prev = next = down = up = null; 23 } 24 25 public Node(Double score, String value) { 26 this.score = score; 27 this.value = value; 28 } 29}

3.2 SkipList節點元素的操作類

SkipList主要包括如下重要屬性：

head -> SkipList中的頭節點的最上層頭節點（level最大的層的頭節點），這個節點不存儲元素，是為了構建列表和查詢時做查詢起始位置的，具體的結構請看2.3中的結構

tail -> SkipList中的尾節點的最上層尾節點（level最大的層的尾節點），這個節點也不存儲元素，是查詢某一個level的終止標志

level -> 總層數

size -> Skip List中節點元素的個數

random -> 用于隨機計算節點level，如果 random.nextDouble() < 1/2則需要增加當前節點的level，如果當前節點增加的level超過了總的level則需要增加head和tail(總level)

1package com.liziba.skiplist; 2 3import java.util.Random; 4 5/** 6 *

7 * 跳表實現 8 *

9 * 10 * @Author: Liziba 11 */ 12public class SkipList { 13 14 /** 最上層頭節點 */ 15 public Node head; 16 /** 最上層尾節點 */ 17 public Node tail; 18 /** 總層數 */ 19 public int level; 20 /** 元素個數 */ 21 public int size; 22 public Random random; 23 24 public SkipList() { 25 level = size = 0; 26 head = new Node(null); 27 tail = new Node(null); 28 head.next = tail; 29 tail.prev = head; 30 } 31 32 /** 33 * 查詢插入節點的前驅節點位置 34 * 35 * @param score 36 * @return 37 */ 38 public Node fidePervNode(Double score) { 39 Node p = head; 40 for(;;) { 41 // 當前層(level)往后遍歷，比較score，如果小于當前值，則往后遍歷 42 while (p.next.value == null && p.prev.score <= score) 43 p = p.next; 44 // 遍歷最右節點的下一層(level) 45 if (p.down != null) 46 p = p.down; 47 else 48 break; 49 } 50 return p; 51 } 52 53 /** 54 * 插入節點，插入位置為fidePervNode(Double score)前面 55 * 56 * @param score 57 * @param value 58 */ 59 public void insert(Double score, String value) { 60 61 // 當前節點的前置節點 62 Node preNode = fidePervNode(score); 63 // 當前新插入的節點 64 Node curNode = new Node(score, value); 65 // 分數和值均相等則直接返回 66 if (curNode.value != null && preNode.value != null && preNode.value.equals(curNode.value) 67 && curNode.score.equals(preNode.score)) { 68 return; 69 } 70 71 preNode.next = curNode; 72 preNode.next.prev = curNode; 73 curNode.next = preNode.next; 74 curNode.prev = preNode; 75 76 int curLevel = 0; 77 while (random.nextDouble() < 1/2) { 78 // 插入節點層數(level)大于等于層數(level)，則新增一層(level) 79 if (curLevel >= level) { 80 Node newHead = new Node(null); 81 Node newTail = new Node(null); 82 newHead.next = newTail; 83 newHead.down = head; 84 newTail.prev = newHead; 85 newTail.down = tail; 86 head.up = newHead; 87 tail.up = newTail; 88 // 頭尾節點指針修改為新的，確保head、tail指針一直是最上層的頭尾節點 89 head = newHead; 90 tail = newTail; 91 ++level; 92 } 93 94 while (preNode.up == null) 95 preNode = preNode.prev; 96 97 preNode = preNode.up; 98 99 Node copy = new Node(null); 100 copy.prev = preNode; 101 copy.next = preNode.next; 102 preNode.next.prev = copy; 103 preNode.next = copy; 104 copy.down = curNode; 105 curNode.up = copy; 106 curNode = copy; 107 108 ++curLevel; 109 } 110 ++size; 111 } 112 113 /** 114 * 查詢指定score的節點元素 115 * @param score 116 * @return 117 */ 118 public Node search(double score) { 119 Node p = head; 120 for (;;) { 121 while (p.next.score != null && p.next.score <= score) 122 p = p.next; 123 if (p.down != null) 124 p = p.down; 125 else // 遍歷到最底層 126 if (p.score.equals(score)) 127 return p; 128 return null; 129 } 130 } 131 132 /** 133 * 升序輸出Skip List中的元素 （默認升序存儲，因此從列表head往tail遍歷） 134 */ 135 public void dumpAllAsc() { 136 Node p = head; 137 while (p.down != null) { 138 p = p.down; 139 } 140 while (p.next.score != null) { 141 System.out.println(p.next.score + "-->" + p.next.value); 142 p = p.next; 143 } 144 } 145 146 /** 147 * 降序輸出Skip List中的元素 148 */ 149 public void dumpAllDesc() { 150 Node p = tail; 151 while (p.down != null) { 152 p = p.down; 153 } 154 while (p.prev.score != null) { 155 System.out.println(p.prev.score + "-->" + p.prev.value); 156 p = p.prev; 157 } 158 } 159 160 161 /** 162 * 刪除Skip List中的節點元素 163 * @param score 164 */ 165 public void delete(Double score) { 166 Node p = search(score); 167 while (p != null) { 168 p.prev.next = p.next; 169 p.next.prev = p.prev; 170 p = p.up; 171 } 172 } 173}

Java Redis 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。