你真的懂Redis的5種基本數據結構嗎？

摘要： 你真的懂Redis的5種基本數據結構嗎？這些知識點或許你還需要看看。

本文分享自華為雲社區《你真的懂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

//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(){
  int level = 1;
  // random()返回一個[0...1)的隨機數
  while (random() < p && level < MaxLevel){ 
      level += 1;
  }
  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/**
* <p>
*      跳錶節點元素
* </p>
*
* @Author: Liziba
* @Date: 2021/7/5 21:01
*/
11public class Node {
12
  /** 節點的分數值，根據分數值來排序 */
  public Double score;
  /** 節點存儲的真實數據 */
  public String value;
  /** 當前節點的 前、後、下、上節點的引用 */
  public Node prev, next, down, up;
19
  public Node(Double score) {
      this.score = score;
      prev = next = down = up = null;
  }
24
  public Node(Double score, String value) {
      this.score = score;
      this.value = value;
  }
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/**
* <p>
*      跳錶實現
* </p>
*
* @Author: Liziba
*/
 12public class SkipList {
 13
  /** 最上層頭節點 */
  public Node head;
  /** 最上層尾節點 */
  public Node tail;
  /** 總層數 */
  public int level;
  /** 元素個數 */
  public int size;
  public Random random;
 23
  public SkipList() {
      level = size = 0;
      head = new Node(null);
      tail = new Node(null);
      head.next = tail;
      tail.prev = head;
  }
 31
  /**
   * 查詢插入節點的前驅節點位置
   *
   * @param score
   * @return
   */
  public Node fidePervNode(Double score) {
      Node p = head;
      for(;;) {
          // 當前層(level)往後遍歷，比較score，如果小於當前值，則往後遍歷
          while (p.next.value == null && p.prev.score <= score)
              p = p.next;
          // 遍歷最右節點的下一層(level)
          if (p.down != null)
              p = p.down;
          else
              break;
      }
      return p;
  }
 52
  /**
   * 插入節點，插入位置為fidePervNode(Double score)前面
   *
   * @param score
   * @param value
   */
  public void insert(Double score, String value) {
 60
      // 當前節點的前置節點
      Node preNode = fidePervNode(score);
      // 當前新插入的節點
      Node curNode = new Node(score, value);
      // 分數和值均相等則直接返回
      if (curNode.value != null && preNode.value != null && preNode.value.equals(curNode.value)
                && curNode.score.equals(preNode.score)) {
          return;
      }
 70
      preNode.next = curNode;
      preNode.next.prev = curNode;
      curNode.next = preNode.next;
      curNode.prev = preNode;
 75
      int curLevel = 0;
      while (random.nextDouble() < 1/2) {
          // 插入節點層數(level)大於等於層數(level)，則新增一層(level)
          if (curLevel >= level) {
              Node newHead = new Node(null);
              Node newTail = new Node(null);
              newHead.next = newTail;
              newHead.down = head;
              newTail.prev = newHead;
              newTail.down = tail;
              head.up = newHead;
              tail.up = newTail;
              // 頭尾節點指針修改為新的，確保head、tail指針一直是最上層的頭尾節點
              head = newHead;
              tail = newTail;
              ++level;
          }
 93
          while (preNode.up == null)
              preNode = preNode.prev;
 96
          preNode = preNode.up;
 98
          Node copy = new Node(null);
          copy.prev = preNode;
          copy.next = preNode.next;
          preNode.next.prev = copy;
          preNode.next = copy;
          copy.down = curNode;
          curNode.up = copy;
          curNode = copy;
107
          ++curLevel;
      }
      ++size;
  }
112
  /**
   * 查詢指定score的節點元素
   * @param score
   * @return
   */
  public Node search(double score) {
      Node p = head;
      for (;;) {
          while (p.next.score != null && p.next.score <= score)
              p = p.next;
          if (p.down != null)
              p = p.down;
          else // 遍歷到最底層
              if (p.score.equals(score))
                  return p;
              return null;
      }
  }
131
  /**
   * 升序輸出Skip List中的元素 （默認升序存儲，因此從列表head往tail遍歷）
   */
  public void dumpAllAsc() {
      Node p = head;
      while (p.down != null) {
          p = p.down;
      }
      while (p.next.score != null) {
          System.out.println(p.next.score + "-->" + p.next.value);
          p = p.next;
      }
  }
145
  /**
   * 降序輸出Skip List中的元素
   */
  public void dumpAllDesc() {
      Node p = tail;
      while (p.down != null) {
          p = p.down;
      }
      while (p.prev.score != null) {
          System.out.println(p.prev.score + "-->" + p.prev.value);
          p = p.prev;
      }
  }
159
160
  /**
   * 刪除Skip List中的節點元素
   * @param score
   */
  public void delete(Double score) {
      Node p = search(score);
      while (p != null) {
          p.prev.next = p.next;
          p.next.prev = p.prev;
          p = p.up;
      }
  }
173}

點擊關注，第一時間了解華為雲新鮮技術~

Tags: Redis 字元串容器數據數據結構程式設計師之家