基本数据结构

redis有9种基本数据结构，string,list,hash,set,zset,bitmap,GeoHash,HyperLogLog,Streams。今天先讨论一下前面5种常见的数据结构。

字符串string

string表示的是一个可变的字节数组，我们初始化字符串的内容、可以拿到字符串的长度，可以获取string的子串，可以覆盖string的子串内容，可以追加子串。

Redis的字符串是动态字符串，是可以修改的字符串，内部结构实现上类似于Java的ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，如图中所示，内部为当前字符串实际分配的空间capacity一般要高于实际字符串长度len。当字符串长度小于1M时，扩容都是加倍现有的空间，如果超过1M，扩容时一次只会多扩1M的空间。需要注意的是字符串最大长度为512M。

127.0.0.1:6379> set name zhangsan # 初始化字符串
OK
127.0.0.1:6379> strlen name # 获取字符串长度
(integer) 8
127.0.0.1:6379> getrange name 3 5 # 获取子串
"ngs"
127.0.0.1:6379> setrange name 3 abc # 替换子串
(integer) 8
127.0.0.1:6379> get name # 获取字符串内容
"zhaabcan"
127.0.0.1:6379> append name hello # 追加子串
(integer) 13
127.0.0.1:6379> get name
"zhaabcanhello"

如果value是数字，还能做计数器使用

127.0.0.1:6379> set count 10
OK
127.0.0.1:6379> get count
"10"
127.0.0.1:6379> incrby count 2 # 增加2
(integer) 12
127.0.0.1:6379> decrby count 1 # 减去1
(integer) 11
127.0.0.1:6379> incr count # 增加1
(integer) 12
127.0.0.1:6379> decr count # 减去1
(integer) 11

还可以设置过期时间

127.0.0.1:6379> expire count 60 # 设置过期时间，单位是秒
(integer) 1
127.0.0.1:6379> ttl count # 获取过期时间
(integer) 50
127.0.0.1:6379> ttl count # -2 表示不存在或者已过期
(integer) -2
127.0.0.1:6379> ttl name # -1 表示没有过期时间
(integer) -1
127.0.0.1:6379> ttl test # -2 表示不存在或者已过期
(integer) -2

链表list

Redis将列表数据结构命名为list而不是array，是因为列表的存储结构用的是链表而不是数组，而且链表还是双向链表。因为它是链表，所以随机定位性能较弱，首尾插入删除性能较优。如果list的列表长度很长，使用时我们一定要关注链表相关操作的时间复杂度。

负下标链表元素的位置使用自然数0,1,2,….n-1表示，还可以使用负数-1,-2,…-n来表示，-1表示「倒数第一」，-2表示「倒数第二」，那么-n就表示第一个元素，对应的下标为0。

队列／堆栈链表可以从表头和表尾追加和移除元素，结合使用rpush/rpop/lpush/lpop四条指令，可以将链表作为队列或堆栈使用，左向右向进行都可以

127.0.0.1:6379> lpush language go # 插入第一个元素go
(integer) 1
127.0.0.1:6379> rpush language java # 在右边插入java
(integer) 2
127.0.0.1:6379> rpush language ruby # 在右边插入ruby
(integer) 3
127.0.0.1:6379> lpush language python # 在左边插入python
(integer) 4
127.0.0.1:6379> llen language # 获取list长度
(integer) 4
127.0.0.1:6379> lindex language 0 # 获取指定位置的内容
"python"
127.0.0.1:6379> lrange language 0 3 # 获取指定区间的呢绒
1) "python"
2) "go"
3) "java"
4) "ruby"
127.0.0.1:6379> lset language 3 c++ # 修改指定位置内容
OK
127.0.0.1:6379> lrange language 0 3
1) "python"
2) "go"
3) "java"
4) "c++"
127.0.0.1:6379> linsert language before go ruby # 在指定位置前面插入元素
(integer) 5
127.0.0.1:6379> lrange language 0 -1 # 获取list所有内容
1) "python"
2) "ruby"
3) "go"
4) "java"
5) "c++"
127.0.0.1:6379> rpush language go # 在右边插入go
(integer) 6
127.0.0.1:6379> lrange language 0 -1 # 获取list所有内容
1) "python"
2) "ruby"
3) "go"
4) "java"
5) "c++"
6) "go"
127.0.0.1:6379> lrem language 2 go # 删除2个元素值为go的节点
(integer) 2
127.0.0.1:6379> lrange language 0 -1
1) "python"
2) "ruby"
3) "java"
4) "c++"
127.0.0.1:6379> ltrim language 1 2 # 保留区间[1,2]的元素
OK
127.0.0.1:6379> lrange language 0 -1
1) "ruby"
2) "java"

哈希hash

哈希等价于Java语言的HashMap或者是Python语言的dict，在实现结构上它使用二维结构，第一维是数组，第二维是链表，hash的内容key和value存放在链表中，数组里存放的是链表的头指针。通过key查找元素时，先计算key的hashcode，然后用hashcode对数组的长度进行取模定位到链表的表头，再对链表进行遍历获取到相应的value值，链表的作用就是用来将产生了「hash碰撞」的元素串起来。Java语言开发者会感到非常熟悉，因为这样的结构和HashMap是没有区别的。哈希的第一维数组的长度也是 $2^n$

127.0.0.1:6379> hset h go "go lang is good" # 设置一个key,value
(integer) 1
127.0.0.1:6379> hmset h java "java is good too" c++ "c++ is good too" # 设置2个key,value
OK
127.0.0.1:6379> hget h go # 获取指定key
"go lang is good"
127.0.0.1:6379> hmget h go c++ # 获取指定多个key
1) "go lang is good"
2) "c++ is good too"
127.0.0.1:6379> hgetall h # 获取所有key,value
1) "go"
2) "go lang is good"
3) "java"
4) "java is good too"
5) "c++"
6) "c++ is good too"
127.0.0.1:6379> hkeys h # 获取所有key
1) "go"
2) "java"
3) "c++"
127.0.0.1:6379> hvals h # 获取所有value
1) "go lang is good"
2) "java is good too"
3) "c++ is good too"
127.0.0.1:6379> hset h python "python is not good"
(integer) 1
127.0.0.1:6379> hdel c++ python # 删除2个key
(integer) 0
127.0.0.1:6379> hgetall h # 获取所有key
1) "go"
2) "go lang is good"
3) "java"
4) "java is good too"
5) "c++"
6) "c++ is good too"
7) "python"
8) "python is not good"
127.0.0.1:6379> hdel h c++ python # 删除2个key
(integer) 2
127.0.0.1:6379> hgetall h
1) "go"
2) "go lang is good"
3) "java"
4) "java is good too"
127.0.0.1:6379> hexists h go # 判断key是否存在。有时候只需要判断key是否存在，不需要获取值
(integer) 1
127.0.0.1:6379> hincrby h c 1 # 如果值是数字，可以当做计数器用。注意没有hdecrby命令
(integer) 1
127.0.0.1:6379> hgetall h
1) "go"
2) "go lang is good"
3) "java"
4) "java is good too"
5) "count"
6) "10"
7) "c"
8) "1"
127.0.0.1:6379> hincrby h c 2 # 把c加2，变成3
(integer) 3
127.0.0.1:6379> hgetall h
1) "go"
2) "go lang is good"
3) "java"
4) "java is good too"
5) "count"
6) "10"
7) "c"
8) "3"
127.0.0.1:6379> hincrby h c 4 # 把c加4，变成7
(integer) 7
127.0.0.1:6379> hgetall h
1) "go"
2) "go lang is good"
3) "java"
4) "java is good too"
5) "count"
6) "10"
7) "c"
8) "7"
127.0.0.1:6379>

扩容当hash内部的元素比较拥挤时(hash碰撞比较频繁)，就需要进行扩容。扩容需要申请新的两倍大小的数组，然后将所有的键值对重新分配到新的数组下标对应的链表中(rehash)。如果hash结构很大，比如有上百万个键值对，那么一次完整rehash的过程就会耗时很长。这对于单线程的Redis里来说有点压力山大。所以Redis采用了渐进式rehash的方案。它会同时保留两个新旧hash结构，在后续的定时任务以及hash结构的读写指令中将旧结构的元素逐渐迁移到新的结构中。这样就可以避免因扩容导致的线程卡顿现象。

缩容 Redis的hash结构不但有扩容还有缩容，从这一点出发，它要比Java的HashMap要厉害一些，Java的HashMap只有扩容。缩容的原理和扩容是一致的，只不过新的数组大小要比旧数组小一倍。

集合set

Java程序员都知道HashSet的内部实现使用的是HashMap，只不过所有的value都指向同一个对象。Redis的set结构也是一样，它的内部也使用hash结构，所有的value都指向同一个内部值。

127.0.0.1:6379> sadd s a b c # 创建名称为s的set，并且添加a,b,c 3个元素
(integer) 3
127.0.0.1:6379> smembers s # 读取所有元素
1) "a"
2) "b"
3) "c"
127.0.0.1:6379> srem s a c # 删除2个元素
(integer) 2
127.0.0.1:6379> smembers s
1) "b"
127.0.0.1:6379> sismember s  b # 判断b是否存在，1表示存在，0表示不存在
(integer) 1
127.0.0.1:6379> sismember s a # 判断a是否存在
(integer) 0

有序集合zset

SortedSet(zset)是Redis提供的一个非常特别的数据结构，一方面它等价于Java的数据结构Map<String, Double>，可以给每一个元素value赋予一个权重score，另一方面它又类似于TreeSet，内部的元素会按照权重score进行排序，可以得到每个元素的名次，还可以通过score的范围来获取元素的列表。
zset底层实现使用了两个数据结构，第一个是hash，第二个是跳跃列表，hash的作用就是关联元素value和权重score，保障元素value的唯一性，可以通过元素value找到相应的score值。跳跃列表的目的在于给元素value排序，根据score的范围获取元素列表

127.0.0.1:6379> zadd z 1 go 2 java 3 python 4 c++ # 增加4个元素
(integer) 4
127.0.0.1:6379> zcard z # 获取元素个数
(integer) 4
127.0.0.1:6379> zincrby z 3 java # 给元素java的权重增加3，变成5
"5"
127.0.0.1:6379> zrange z 0 3 # 获取排名从0到3的元素
1.  "go"
2.  "python"
3.  "c++"
4.  "java"
127.0.0.1:6379> zrank z go # 获取go的排名
(integer) 0
127.0.0.1:6379> zrank z java # 获取java的排名
(integer) 3
127.0.0.1:6379> zrevrank z java # 获取java的逆向排名
(integer) 0
127.0.0.1:6379> zscore z go # 获取go的分数
"1"
127.0.0.1:6379> zscore z java # 获取java的分数
"5"
127.0.0.1:6379> zrangebyscore z 0 4 # 按分数获取[0,4]的元素
1.  "go"
2.  "python"
3.  "c++"
127.0.0.1:6379> zrangebyscore z 0 4 withscores # 按分数获取[0,4]的元素，并且展示分数
4.  "go"
5.  "1"
6.  "python"
7.  "3"
8.  "c++"
9.  "4"
127.0.0.1:6379> zrevrangebyscore z 4 0 withscores # 逆序按分数获取[4,0]的元素，并且展示分数
10. "c++"
11. "4"
12. "python"
13. "3"
14. "go"
15. "1"
127.0.0.1:6379> zrangebyscore z -inf +inf withscores # 正序获取所有元素，并且带分数。-inf表示负无穷大，+inf表示正无穷大
1.  "go"
2.  "1"
3.  "python"
4.  "3"
5.  "c++"
6.  "4"
7.  "java"
8.  "5"
127.0.0.1:6379> zremrangebyrank z 0 1 # 按范围删除[0,1]2个元素
(integer) 2
127.0.0.1:6379> zrangebyscore z -inf +inf withscores
1.  "c++"
2.  "4"
3.  "java"
4.  "5"
127.0.0.1:6379> zremrangebyscore z 4 4 # 按分数删除[4,4]的元素
(integer) 1
127.0.0.1:6379> zrangebyscore z -inf +inf withscores
5.  "java"
6.  "5"

内部存储结构

================重点================

光了解上面五种基本数据结构还不足以满足面试官的要求，还必须了解他们的内部存储结构。

上面五种基本数据结构是对用户而言的，他们在内存中是以什么样的数据结构或者说编码方式实现呢？下面就来学习一下

数据结构	内部编码
string	int，raw，embstr
hash	ziplist，hashtable
list	ziplist，linkedlist，quicklist
set	intset，hashtable
zset	ziplist，skiplist

图形表示如下：

redis可以使用object encoding命令查看内部编码模式。

Redis这样设计有两个好处：

可以偷偷的改进内部编码，而对外的数据结构和命令没有影响，这样一旦开发出更优秀的内部编码，无需改动对外数据结构和命令。
多种内部编码实现可以在不同场景下发挥各自的优势。例如ziplist比较节省内存，但是在列表元素比较多的情况下，性能会有所下降。这时候Redis会根据配置选项将列表类型的内部实现转换为linkedlist。

String的三种内部编码

int：8个字节的长整型
raw: 小于等于39个字节的字符串
embstr: 大于39个字节的字符串

hash的两种内部编码

ziplist: 当hash元素个数小于hash-max-ziplist-entries（默认512个），并且元素大小小于hash-max-ziplist-value(默认64字节)。redis会使用ziplist作为hash的内部实现
hashtable: 当hash无法满足ziplist实现时，会使用hashtable作为hash内部实现。因为此时ziplist的读写性能会下降，而hashtable的时间复杂度是O(1)

注意：当hash的内部实现由ziplist转变成hashtable后，就算后续缓存的内容全部替换了，redis也会一直使用hashtable作为内部实现

list的三种内部编码

ziplist（压缩列表）：当列表内元素个数小于hash-max-ziplist-entries，并且元素大小小于hash-max-ziplist-value，redis会使用ziplist作为list集合的内部实现。
linkedlist（链表）：当列表无法满足ziplist实现时，会使用linkedlist作为内部实现。
quicklist：此数据结构是redis 3.2版本之后新增的数据结构，它结合了ziplist+linkedlist。

注意：list和hash一样，只能有ziplist转变为linkedlist，不能有linkedlist转变为ziplist。

set的两种内部编码

intset（整数集合）：当集合内元素都是整数且个数小于set-max-intset-entries（默认512个），redis会使用intset作为集合的实现，从而减少内存的使用。
hashtable（哈希表）：当集合无法满足intset实现时，redis会使用hashtable作为集合的实现。

zset的两种内部编码

ziplist（压缩列表）：当有序集合内元素个数小于等于zset-max-ziplist-entries（默认128个），并且每个元素的值都小于zset-max-ziplist-value（默认64字节）。redis会使用ziplist作为集合内部实现，可以减少内存的使用。
skiplist（跳表）：当有序集合不满足ziplist作为内部实现时，使用skiplist作为内部实现，因为此时ziplist的读写效率会有降低

压缩链表ziplist

压缩链表是一块连续的内存，减少了很多内存碎片和指针的内存占用，进而节约了内存。

entity结构如下

跳表skiplist

哈希表hash

redis中的hash表用的是拉链法

inset

整数集合是一块连续的内存

redis对象

Redis 内部使用一个 redisObject 对象来表示所有的 key 和 value。

类型type:就是第一部分讲的五种常见基本类型
encoding:就是第二部分讲的底层编码方式
*ptr：就是指向具体的数据内容，它是用encoding指定的编码格式存放的，获取数据的时候使用对应的解码方式获取真正数据

总结

本文讲解了redis五种常见的数据结构string,list,hash,set,zset及其基本用法。
讲解了每种数据结构的内部存储方式（编码方式）。redis为了节省内存，实现了多种编码方式，每种数据结构根据元素数量和大小的不同采取不同的编码方式。
着重讲了一下ziplist,skiplist,hash原理等。
redis其他几种高级数据结构用的少，感兴趣的可以自己去了解。
vm 字段：只有打开了 Redis 的虚拟内存功能，此字段才会真正的分配内存，该功能默认是关闭状态的。 Redis 使用 redisObject 来表示所有的 key/value 数据是比较浪费内存的，当然这些内存管理成本的付出主要也是为了给 Redis 不同数据类型提供一个统一的管理接口，实际作者也提供了多种方法帮助我们尽量节省内存使用。