多維度深入分析Redis的5種基本數據結構
一、簡介
Redis中所有的的數據結構都是通過一個唯一的字符串key來獲取相應的value數據。
Redis有5種基礎數據結構，分別是：
- string（字符串）
- list（列表）
- hash（字典）
- set（集合）
- zset（有序集合）
其中l(wèi)ist、set、hash、zset這四種數據結構是容器型數據結構，它們共享下面兩條通用規(guī)則：
- create if not exists：容器不存在則創(chuàng)建
- drop if no elements：如果容器中沒有元素，則立即刪除容器，釋放內存
本文將詳細講述的是Redis的5種基礎數據結構。
二、string（字符串）
1、string(字符串)相關介紹
1.1 string(字符串)的內部結構
string(字符串)是Redis最簡單也是使用最廣泛的數據結構，它的內部是一個字符數組。如圖所示：
Redis中string(字符串)是動態(tài)字符串，允許修改；它在結構上的實現類似于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 批量鍵值對
批量鍵值讀取和寫入最大的優(yōu)勢在于節(jié)省網絡傳輸開銷
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 不存在創(chuàng)建存在不更新
上面的set操作不存在創(chuàng)建，存在則更新；此時如果需要存在不更新的場景，那么可以使用如下這個指令
?
setnx -> 不存在創(chuàng)建存在不更新
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的區(qū)間訪問內，[-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 -> 自定義累加值
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為整數的自增區(qū)間
最大值：
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雙向列表的特性，因此其也被用于異步隊列的使用。實際開發(fā)中將需要延后處理的任務結構體序列化成字符串，放入Redis的隊列中，另一個線程從這個列表中獲取數據進行后續(xù)處理。其流程類似如下的圖：
?
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)是個鏈表數據結構，它的遍歷是慢操作，所以涉及到遍歷的性能將會遍歷區(qū)間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指的是一塊連續(xù)的內存存儲空間，Redis底層對于list(列表)的存儲，當元素個數少的時候，它會使用一塊連續(xù)的內存空間來存儲，這樣可以減少每個元素增加prev和next指針帶來的內存消耗，最重要的是可以減少內存碎片化問題。
?
3.1 常見的鏈表結構示意圖
每個node節(jié)點元素，都會持有一個prev->執(zhí)行前一個node節(jié)點和next->指向后一個node節(jié)點的指針（引用），這種結構雖然支持前后順序遍歷，但是也帶來了不小的內存開銷，如果node節(jié)點僅僅是一個int類型的值，那么可想而知，引用的內存比例將會更大。
3.2 ziplist示意圖
ziplist是一塊連續(xù)的內存地址，他們之間無需持有prev和next指針，能通過地址順序尋址訪問。
3.3 quicklist示意圖
quicklist是由多個ziplist組成的雙向鏈表。
四、hash（字典）?
1、hash(字典)相關介紹
1.1 hash(字典)的內部結構
Redis的hash(字典)相當于Java語言中的HashMap，它是根據散列值分布的無序字典，內部的元素是通過鍵值對的方式存儲。
hash(字典)的實現與Java中的HashMap（JDK1.7）的結構也是一致的，它的數據結構也是數組+鏈表組成的二維結構，節(jié)點元素散列在數組上，如果發(fā)生hash碰撞則使用鏈表串聯在數組節(jié)點上。
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(字典)具有如下的優(yōu)缺點：
- 讀取可以部分讀取，節(jié)省網絡流量
- 存儲消耗的高于單個字符串的存儲
2 hash(字典)相關指令
2.1 hash(字典)常用指令
hset -> hash(字典)插入值，字典不存在則創(chuàng)建 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
127.0.0.1:6379> sismember name lisi # 包含返回1 (integer) 1 127.0.0.1:6379> sismember name tianqi # 不包含返回0 (integer) 0
scard -> 獲取集合的長度
scard key
1127.0.0.1:6379> scard name 2(integer) 4
spop -> 彈出元素，count指彈出元素的個數
spop key [count]
127.0.0.1:6379> spop name # 默認彈出一個 "wangwu" 127.0.0.1:6379> spop name 3 1) "lisi" 2) "zhangsan" 3) "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 …]
127.0.0.1:6379> zadd name 10 zhangsan (integer) 1 127.0.0.1:6379> zadd name 10.1 lisi (integer) 1 127.0.0.1:6379> zadd name 9.9 wangwu (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]
127.0.0.1:6379> zrange name 0 -1 # 獲取所有元素，按照score的升序輸出 1) "wangwu" 2) "zhangsan" 3) "lisi" 127.0.0.1:6379> zrange name 0 1 # 獲取第一個和第二個slot的元素 1) "wangwu" 2) "zhangsan" 127.0.0.1:6379> zadd name 10 tianqi # 在上面的基礎上添加score為10的元素 (integer) 1 127.0.0.1:6379> zrange name 0 2 # key相等則按照value字典排序輸出 1) "wangwu" 2) "tianqi" 3) "zhangsan" 127.0.0.1:6379> zrange name 0 -1 WITHSCORES # WITHSCORES 輸出權重 1) "wangwu" 2) "9.9000000000000004" 3) "tianqi" 4) "10" 5) "zhangsan" 6) "10" 7) "lisi" 8) "10.1"
3、zrevrange -> 按照score權重從大到小輸出集合中的元素，權重相同則按照value的字典逆序排序
其中成員的位置按 score 值遞減(從大到小)來排列。 具有相同 score 值的成員按字典序的逆序(reverse lexicographical order)排列。 除了成員按 score 值遞減的次序排列這一點外， ZREVRANGE 命令的其他方面和 ZRANGE key start stop [WITHSCORES] 命令一樣
zrevrange key start stop [WITHSCORES]
127.0.0.1:6379> zrevrange name 0 -1 WITHSCORES 1) "lisi" 2) "10.1" 3) "zhangsan" 4) "10" 5) "tianqi" 6) "10" 7) "wangwu" 8) "9.9000000000000004"
4、zcard -> 當 key 存在且是有序集類型時，返回有序集的基數。 當 key 不存在時，返回 0
zcard key
127.0.0.1:6379> zcard name (integer) 4
5、zscore -> 返回有序集 key 中，成員 member 的 score 值，如果 member 元素不是有序集 key 的成員，或 key 不存在，返回 nil
zscore key member z
127.0.0.1:6379> zscore name zhangsan "10" 127.0.0.1:6379> zscore name liziba (nil)
6、zrank -> 返回有序集 key 中成員 member 的排名。其中有序集成員按 score 值遞增(從小到大)順序排列。
排名以 0 為底，也就是說，score 值最小的成員排名為 0
zrank key member
127.0.0.1:6379> zrange name 0 -1 1) "wangwu" 2) "tianqi" 3) "zhangsan" 4) "lisi" 127.0.0.1:6379> zrank name wangwu (integer) 0
7、zrangebyscore -> 返回有序集 key 中，所有 score 值介于 min 和 max 之間(包括等于 min 或 max )的成員。有序集成員按 score 值遞增(從小到大)次序排列。
min 和 max 可以是 -inf 和 +inf ，這樣一來，你就可以在不知道有序集的最低和最高 score 值的情況下，使用 [ZRANGEBYSCORE]這類命令。
默認情況下，區(qū)間的取值使用閉區(qū)間，你也可以通過給參數前增加 ( 符號來使用可選的[開區(qū)間]小于或大于)
zrangebyscore key min max [WITHSCORES] [LIMIT offset count]
127.0.0.1:6379> zrange name 0 -1 WITHSCORES # 輸出全部元素 1) "wangwu" 2) "9.9000000000000004" 3) "tianqi" 4) "10" 5) "zhangsan" 6) "10" 7) "lisi" 8) "10.1" 127.0.0.1:6379> zrangebyscore name 9 10 1) "wangwu" 2) "tianqi" 3) "zhangsan" 127.0.0.1:6379> zrangebyscore name 9 10 WITHSCORES # 輸出分數 1) "wangwu" 2) "9.9000000000000004" 3) "tianqi" 4) "10" 5) "zhangsan" 6) "10" 127.0.0.1:6379> zrangebyscore name -inf 10 # -inf 從負無窮開始 1) "wangwu" 2) "tianqi" 3) "zhangsan" 127.0.0.1:6379> zrangebyscore name -inf +inf # +inf 直到正無窮 1) "wangwu" 2) "tianqi" 3) "zhangsan" 4) "lisi" 127.0.0.1:6379> zrangebyscore name (10 11 # 10 < score <=11 1) "lisi" 127.0.0.1:6379> zrangebyscore name (10 (10.1 # 10 < socre < -11 (empty list or set) 127.0.0.1:6379> zrangebyscore name (10 (11 1) "lisi"
8、zrem -> 移除有序集 key 中的一個或多個成員，不存在的成員將被忽略
zrem key member [member …]
127.0.0.1:6379> zrange name 0 -1 1) "wangwu" 2) "tianqi" 3) "zhangsan" 4) "lisi" 127.0.0.1:6379> zrem name zhangsan # 移除元素 (integer) 1 127.0.0.1:6379> zrange name 0 -1 1) "wangwu" 2) "tianqi" 3) "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動態(tài)圖
先通過一張動圖來了解Skip List的插入節(jié)點元素的流程，此圖來自維基百科。
2.3 Skip List算法性能分析
2.3.1 計算隨機層數算法
首先分析的是執(zhí)行插入操作時計算隨機數的過程，這個過程會涉及層數的計算，所以十分重要。對于節(jié)點他有如下特性：
- 節(jié)點都有第一層的指針
- 節(jié)點有第i層指針，那么第i+1層出現的概率為p
- 節(jié)點有最大層數限制，MaxLevel
計算隨機層數的偽代碼：
論文中的示例
Java版本
public int randomLevel(){
int level = 1;
// random()返回一個[0...1)的隨機數
while (random() < p && level < MaxLevel){
level += 1;
}
return level;
}
代碼中包含兩個變量P和MaxLevel，在Redis中這兩個參數的值分別是：
1p = 1/4 2MaxLevel = 64
2.3.2 節(jié)點包含的平均指針數目
Skip List屬于空間換時間的數據結構，這里的空間指的就是每個節(jié)點包含的指針數目，這一部分是額外的內內存開銷，可以用來度量空間復雜度。random()是個隨機數，因此產生越高的節(jié)點層數，概率越低（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)
- ……
得出節(jié)點的平均層數（節(jié)點包含的平均指針數目）：
所以Redis中p=1/4計算的平均指針數目為1.33
?
2.3.3 時間復雜度計算
以下推算來自論文內容
假設p=1/2，在以p=1/2生成的16個元素的跳過列表中，我們可能碰巧具有9個元素，1級3個元素，3個元素3級元素和1個元素14級（這不太可能，但可能會發(fā)生）。我們該怎么處理這種情況？如果我們使用標準算法并在第14級開始我們的搜索，我們將會做很多無用的工作。那么我們應該從哪里開始搜索？此時我們假設SkipList中有n個元素，第L層級元素個數的期望是1/p個；每個元素出現在L層的概率是p^(L-1), 那么第L層級元素個數的期望是 n * (p^L-1)；得到1 / p =n * (p^L-1)
1 / p = n * (p^L-1) n = (1/p)^L L = log(1/p)^n
所以我們應該選擇MaxLevel = log(1/p)^n
定義：MaxLevel = L(n) = log(1/p)^n
?
推算Skip List的時間復雜度，可以用逆向思維，從層數為i的節(jié)點x出發(fā)，返回起點的方式來回溯時間復雜度，節(jié)點x點存在兩種情況：
- 節(jié)點x存在(i+1)層指針，那么向上爬一級，概率為p，對應下圖situation c.
- 節(jié)點x不存在(i+1)層指針，那么向左爬一級，概率為1-p，對應下圖situation b.
設C(k) = 在無限列表中向上攀升k個level的搜索路徑的預期成本（即長度）那么推演如下：
C(0)=0 C(k)=(1-p)×(情況b的查找長度) + p×(情況c的查找長度) C(k)=(1-p)(C(k)+1) + p(C(k-1)+1) C(k)=1/p+C(k-1) C(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每個節(jié)點元素由節(jié)點key、節(jié)點value和指向當前節(jié)點所在level的指針數組組成
2.2 Skip List查詢
假設初始Skip List跳躍列表中已經存在這些元素，他們分布的結構如下所示：
此時查詢節(jié)點88，它的查詢路線如下所示：
從Skip List跳躍列表最頂層level3開始，往后查詢到10 < 88 && 后續(xù)節(jié)點值為null && 存在下層level2level2 10往后遍歷，27 < 88 && 后續(xù)節(jié)點值為null && 存在下層level1level1 27往后遍歷，88 = 88，查詢命中
2.3 Skip List插入
Skip List的初始結構與2.3中的初始結構一致，此時假設插入的新節(jié)點元素值為90，插入路線如下所示：
查詢插入位置，與Skip List查詢方式一致，這里需要查詢的是第一個比90大的節(jié)點位置，插入在這個節(jié)點的前面， 88 < 90 < 100構造一個新的節(jié)點Node(90)，為插入的節(jié)點Node(90)計算一個隨機level，這里假設計算的是1，這個level時隨機計算的，可能時1、2、3、4…均有可能，level越大的可能越小，主要看隨機因子x ，層數的概率大致計算為 (1/x)^level ，如果level大于當前的最大level3，需要新增head和tail節(jié)點節(jié)點構造完畢后，需要將其插入列表中，插入十分簡單步驟 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);
2.4 Skip List刪除
刪除的流程就是查詢到節(jié)點，然后刪除，重新將刪除節(jié)點左右兩邊的節(jié)點以鏈表的形式組合起來即可，這里不再畫圖
?
4、手寫實現一個簡單Skip List
實現一個Skip List比較簡單，主要分為兩個步驟：
- 定義Skip List的節(jié)點Node，節(jié)點之間以鏈表的形式存儲，因此節(jié)點持有相鄰節(jié)點的指針，其中prev與next是同一level的前后節(jié)點的指針，down與up是同一節(jié)點的多個level的上下節(jié)點的指針
- 定義Skip List的實現類，包含節(jié)點的插入、刪除、查詢，其中查詢操作分為升序查詢和降序查詢（往后和往前查詢），這里實現的Skip List默認節(jié)點之間的元素是升序鏈表
3.1 定義Node節(jié)點
Node節(jié)點類主要包括如下重要屬性：
- score -> 節(jié)點的權重，這個與Redis中的score相同，用來節(jié)點元素的排序作用
- value -> 節(jié)點存儲的真實數據，只能存儲String類型的數據
- prev -> 當前節(jié)點的前驅節(jié)點，同一level
- next -> 當前節(jié)點的后繼節(jié)點，同一level
- down -> 當前節(jié)點的下層節(jié)點，同一節(jié)點的不同level
- up -> 當前節(jié)點的上層節(jié)點，同一節(jié)點的不同level
package com.liziba.skiplist;
/**
* <p>
* 跳表節(jié)點元素
* </p>
*
* @Author: Liziba
* @Date: 2021/7/5 21:01
*/
public class Node {
/** 節(jié)點的分數值，根據分數值來排序 */
public Double score;
/** 節(jié)點存儲的真實數據 */
public String value;
/** 當前節(jié)點的 前、后、下、上節(jié)點的引用 */
public Node prev, next, down, up;
public Node(Double score) {
this.score = score;
prev = next = down = up = null;
}
public Node(Double score, String value) {
this.score = score;
this.value = value;
}
}
3.2 SkipList節(jié)點元素的操作類
SkipList主要包括如下重要屬性：
- head -> SkipList中的頭節(jié)點的最上層頭節(jié)點（level最大的層的頭節(jié)點），這個節(jié)點不存儲元素，是為了構建列表和查詢時做查詢起始位置的，具體的結構請看2.3中的結構
- tail -> SkipList中的尾節(jié)點的最上層尾節(jié)點（level最大的層的尾節(jié)點），這個節(jié)點也不存儲元素，是查詢某一個level的終止標志
- level -> 總層數
- size -> Skip List中節(jié)點元素的個數
- random -> 用于隨機計算節(jié)點level，如果 random.nextDouble() < 1/2則需要增加當前節(jié)點的level，如果當前節(jié)點增加的level超過了總的level則需要增加head和tail(總level)
package com.liziba.skiplist;
import java.util.Random;
/**
* <p>
* 跳表實現
* </p>
*
* @Author: Liziba
*/
public class SkipList {
/** 最上層頭節(jié)點 */
public Node head;
/** 最上層尾節(jié)點 */
public Node tail;
/** 總層數 */
public int level;
/** 元素個數 */
public int size;
public Random random;
public SkipList() {
level = size = 0;
head = new Node(null);
tail = new Node(null);
head.next = tail;
tail.prev = head;
}
/**
* 查詢插入節(jié)點的前驅節(jié)點位置
*
* @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;
// 遍歷最右節(jié)點的下一層(level)
if (p.down != null)
p = p.down;
else
break;
}
return p;
}
/**
* 插入節(jié)點，插入位置為fidePervNode(Double score)前面
*
* @param score
* @param value
*/
public void insert(Double score, String value) {
// 當前節(jié)點的前置節(jié)點
Node preNode = fidePervNode(score);
// 當前新插入的節(jié)點
Node curNode = new Node(score, value);
// 分數和值均相等則直接返回
if (curNode.value != null && preNode.value != null && preNode.value.equals(curNode.value)
&& curNode.score.equals(preNode.score)) {
return;
}
preNode.next = curNode;
preNode.next.prev = curNode;
curNode.next = preNode.next;
curNode.prev = preNode;
int curLevel = 0;
while (random.nextDouble() < 1/2) {
// 插入節(jié)點層數(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;
// 頭尾節(jié)點指針修改為新的，確保head、tail指針一直是最上層的頭尾節(jié)點
head = newHead;
tail = newTail;
++level;
}
while (preNode.up == null)
preNode = preNode.prev;
preNode = preNode.up;
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;
++curLevel;
}
++size;
}
/**
* 查詢指定score的節(jié)點元素
* @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;
}
}
/**
* 升序輸出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;
}
}
/**
* 降序輸出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;
}
}
/**
* 刪除Skip List中的節(jié)點元素
* @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;
}
}
}
到此這篇關于多維度深入分析Redis的5種基本數據結構的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支持本站。
版權聲明：本站文章來源標注為YINGSOO的內容版權均為本站所有，歡迎引用、轉載，請保持原文完整并注明來源及原文鏈接。禁止復制或仿造本網站，禁止在非www.sddonglingsh.com所屬的服務器上建立鏡像，否則將依法追究法律責任。本站部分內容來源于網友推薦、互聯網收集整理而來，僅供學習參考，不代表本站立場，如有內容涉嫌侵權，請聯系alex-e#qq.com處理。
關注官方微信