你真的懂Redis的5种基本数据结构吗？这些知识点或许你还需要看看（图文并茂，浅显易懂，建议收藏）

待我称王封你为后i 2021-07-25 01:01 173阅读 0赞

## 一、简介 ##

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最简单也是使用最广泛的数据结构，它的内部是一个字符数组。如图所示：

![string(字符串).png][string_.png]

Redis中string(字符串)是动态字符串，允许修改；它在结构上的实现类似于Java中的ArrayList（默认构造一个大小为10的初始数组），这是冗余分配内存的思想，也称为预分配；这种思想可以减少扩容带来的性能消耗。  
![string(字符串)预置空间.png][string_.png 1]

**1.2 string(字符串)的扩容**

当string(字符串)的大小达到扩容阈值时，将会对string(字符串)进行扩容，string(字符串)的扩容主要有以下几个点：

1.  长度小于1MB，扩容后为原先的两倍; length = length \* 2
2.  长度大于1MB，扩容后增加1MB; length = length + 1MB
3.  字符串的长度最大值为 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)。

![list结构简图.png][list_.png]

**1.2 list(列表)的使用场景**

根据Redis双向列表的特性，因此其也被用于异步队列的使用。实际开发中将需要延后处理的任务结构体序列化成字符串，放入Redis的队列中，另一个线程从这个列表中获取数据进行后续处理。其流程类似如下的图：

![list用于异步队列示意图.png][list_.png 1]

### 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类型的值，那么可想而知，引用的内存比例将会更大。

![常见链表结构.png][.png]

**3.2 ziplist示意图**

ziplist是一块连续的内存地址，他们之间无需持有prev和next指针，能通过地址顺序寻址访问。

![ziplist内存示意图.png][ziplist_.png]

**3.3 quicklist示意图**

quicklist是由多个ziplist组成的双向链表。

![quicklist示意图.png][quicklist_.png]

##  ##

## 四、hash（字典） ##

### 1、hash(字典)相关介绍 ###

**1.1 hash(字典)的内部结构**

Redis的hash(字典)相当于Java语言中的HashMap，它是根据散列值分布的无序字典，内部的元素是通过键值对的方式存储。

![hash无序字典键值对存储 (1).png][hash_ _1_.png]

hash(字典)的实现与Java中的HashMap（JDK1.7）的结构也是一致的，它的数据结构也是数组+链表组成的二维结构，节点元素散列在数组上，如果发生hash碰撞则使用链表串联在数组节点上。  
![hash结构 (1).png][hash_ _1_.png 1]

**1.2 hash(字典)扩容**

Redis中的hash(字典)存储的value只能是字符串值，此外扩容与Java中的HashMap也不同。Java中的HashMap在扩容的时候是一次性完成的，而Redis考虑到其核心存取是单线程的性能问题，为了追求高性能，因而采取了渐进式rehash策略。  
渐进式rehash指的是并非一次性完成，它是多次完成的，因此需要保理旧的hash结构，所以Redis中的hash(字典)会存在新旧两个hash结构，在rehash结束后也就是旧hash的值全部搬迁到新hash之后，新的hash在功能上才会完全替代以前的hash。

![hash-\_rehash.png][hash-_rehash.png]

**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的特殊字典。  
集合中的最后一个元素被移除之后，数据结构被自动删除，内存被回收。

![set结构 (1).png][set_ _1_.png]

**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被移除后，数据结构被自动删除，内存被回收。

![zset的内部数据结构.png][zset_.png]

**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红黑树

1.  插入、查询时间复杂度O(logn)
2.  数据天然有序
3.  实现复杂，设计变色、左旋右旋平衡等操作
4.  需要加锁

Skip List跳跃列表

1.  插入、查询时间复杂度O(logn)
2.  数据天然有序
3.  实现简单，链表结构
4.  无需加锁

### 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][https_www.cl.cam.ac.uk_teaching_2005_Algorithms_skiplists.pdf]

**2.2 Skip List动态图**

先通过一张动图来了解Skip List的插入节点元素的流程，此图来自维基百科。

![20210707234100804.gif][]

**2.3 Skip List算法性能分析**

**2.3.1 计算随机层数算法**

首先分析的是执行插入操作时计算随机数的过程，这个过程会涉及层数的计算，所以十分重要。对于节点他有如下特性：

*  节点都有第一层的指针
 *  节点有第i层指针，那么第i+1层出现的概率为p
 *  节点有最大层数限制，MaxLevel

计算随机层数的伪代码：  
**论文中的示例**

![image.png][]

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)
 *  ……

得出节点的平均层数（节点包含的平均指针数目）：

![2195619-b17ca123586244cc.webp][]

所以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.

![image.png][image.png 1]

设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跳跃列表通常具有如下这些特性

1.  Skip List包含多个层，每层称为一个level，level从0开始递增
2.  Skip List 0层，也就是最底层，应该包含所有的元素
3.  每一个level/层都是一个有序的列表
4.  level小的层包含level大的层的元素，也就是说元素A在X层出现，那么 想X>Z>=0的level/层都应该包含元素A
5.  每个节点元素由节点key、节点value和指向当前节点所在level的指针数组组成

**2.2 Skip List查询**

假设初始Skip List跳跃列表中已经存在这些元素，他们分布的结构如下所示：

![Skip List 跳跃列表初始.png][Skip List _.png]

此时查询节点88，它的查询路线如下所示：  
![Skip List 跳跃列表查询.png][Skip List _.png 1]

1.  从Skip List跳跃列表最顶层level3开始，往后查询到10 < 88 && 后续节点值为null && 存在下层level2
2.  level2 10往后遍历，27 < 88 && 后续节点值为null && 存在下层level1
3.  level1 27往后遍历，88 = 88，查询命中

**2.3 Skip List插入**

Skip List的初始结构与2.3中的初始结构一致，此时假设插入的新节点元素值为90，插入路线如下所示：

1.  查询插入位置，与Skip List查询方式一致，这里需要查询的是第一个比90大的节点位置，插入在这个节点的前面， 88 < 90 < 100
2.  构造一个新的节点Node(90)，为插入的节点Node(90)计算一个随机level，这里假设计算的是1，这个level时随机计算的，可能时1、2、3、4…均有可能，level越大的可能越小，主要看随机因子x ，层数的概率大致计算为 (1/x)^level ，如果level大于当前的最大level3，需要新增head和tail节点
3.  节点构造完毕后，需要将其插入列表中，插入十分简单步骤 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);

![Skip List插入节点.png][Skip List_.png]

**2.4 Skip List删除**

删除的流程就是查询到节点，然后删除，重新将删除节点左右两边的节点以链表的形式组合起来即可，这里不再画图

### 4、手写实现一个简单Skip List ###

实现一个Skip List比较简单，主要分为两个步骤：

1.  定义Skip List的节点Node，节点之间以链表的形式存储，因此节点持有相邻节点的指针，其中prev与next是同一level的前后节点的指针，down与up是同一节点的多个level的上下节点的指针
2.  定义Skip List的实现类，包含节点的插入、删除、查询，其中查询操作分为升序查询和降序查询（往后和往前查询），这里实现的Skip List默认节点之间的元素是升序链表

**3.1 定义Node节点**

Node节点类主要包括如下重要属性：

1.  score -> 节点的权重，这个与Redis中的score相同，用来节点元素的排序作用
2.  value -> 节点存储的真实数据，只能存储String类型的数据
3.  prev -> 当前节点的前驱节点，同一level
4.  next -> 当前节点的后继节点，同一level
5.  down -> 当前节点的下层节点，同一节点的不同level
6.  up -> 当前节点的上层节点，同一节点的不同level

1package com.liziba.skiplist;
     2
     3/**
     4 * <p>
     5 *      跳表节点元素
     6 * </p>
     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主要包括如下重要属性：

1.  head -> SkipList中的头节点的最上层头节点（level最大的层的头节点），这个节点不存储元素，是为了构建列表和查询时做查询起始位置的，具体的结构请看2.3中的结构
2.  tail -> SkipList中的尾节点的最上层尾节点（level最大的层的尾节点），这个节点也不存储元素，是查询某一个level的终止标志
3.  level -> 总层数
4.  size -> Skip List中节点元素的个数
5.  random -> 用于随机计算节点level，如果 random.nextDouble() < 1/2则需要增加当前节点的level，如果当前节点增加的level超过了总的level则需要增加head和tail(总level)

1package com.liziba.skiplist;
      2
      3import java.util.Random;
      4
      5/**
      6 * <p>
      7 *      跳表实现
      8 * </p>
      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}

[string_.png]: /images/20210724/a9e4d993bc2f46558f0735345d82eb92.png
[string_.png 1]: /images/20210724/d7d380df1ffc41ab8d8d8b1ab4fe0115.png
[list_.png]: /images/20210724/0c42e00737c049acad98b51fdfcf2231.png
[list_.png 1]: /images/20210724/24a3fbc5484e452eb6635bb45ec329e6.png
[.png]: /images/20210724/ecf49a723ffb4be787800f7206d4dd0c.png
[ziplist_.png]: /images/20210724/f37fd61712b94edcb1aa0cc33ae638c7.png
[quicklist_.png]: /images/20210724/d03a9523f0704b9cb4ef15ab64a27a73.png
[hash_ _1_.png]: /images/20210724/a27f311ece0d46949f0a69536642c449.png
[hash_ _1_.png 1]: /images/20210724/06544c03a4f642738ecaf2e9ad4a7e19.png
[hash-_rehash.png]: /images/20210724/2771f0773d654ece8a8e6318bf6efe7c.png
[set_ _1_.png]: /images/20210724/23784febc2eb4e9aabce499415371a03.png
[zset_.png]: /images/20210724/5fc9f72864fb49c095840a7532a515bb.png
[https_www.cl.cam.ac.uk_teaching_2005_Algorithms_skiplists.pdf]: https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf
[20210707234100804.gif]: /images/20210724/2ed3c5e408c740c98f6a2d0d413dc445.png
[image.png]: /images/20210724/c71dc283c4c949b38acccd55d890c4e0.png
[2195619-b17ca123586244cc.webp]: /images/20210724/f47f894865064132aa2edb7b953c5601.png
[image.png 1]: /images/20210724/78658434e8524dcf93384345c084724d.png
[Skip List _.png]: /images/20210724/cedcfba9d5aa4bb1be0ab583a0726e73.png
[Skip List _.png 1]: /images/20210724/e8c28ce19df84abb9274bf6b2e35322d.png
[Skip List_.png]: /images/20210724/b0552ad2ca1b481a845ce21a490329c2.png