【收藏看】关于面试常见问题：Redis有哪些数据结构？

面试场景

Redis作为时下最火的缓存中间件之一，面试的时候面试官肯定会问Redis的相关内容，而往往问的第一个问题就是：你知道Redis有哪几种数据结构吗？你们项目中使用到了哪些数据结构？是怎么使用的？

当你收到这样的三连击之后，是不是蒙了，于是你就如实回答：Redis支持存储5种类型的值：String（字符串类型）、List（列表类型）、Hash（哈希表类型）、Set（无序集合类型）、Zset（有序集合类型）；我们项目中只使用了String类型；主要是用作缓存的，比如我们有一个某某某功能，把某某某信息作为一个字符串缓存到Redis中。

如果你只回答这么多，显然是不能满足面试官的胃口的，面试官问这个问题的初衷是想知道你是否了解这5种数据结构的底层实现原理，只有了解它们的底层实现，你才更加清楚它们的区别及使用场景。

本篇文章将针对上面的问题，详细介绍Redis五种数据类型的底层实现，以及它们的使用场景。

Redis支持存储的五种数据类型

Redis是一种存储key-value的内存型数据库，它的key都是字符串类型，value支持存储5种类型的数据：String（字符串类型）、List（列表类型）、Hash（哈希表类型、即key-value类型）、Set（无序集合类型，元素不可重复）、Zset（有序集合类型，元素不可重复）。

针对这5种数据类型，Redis在底层都是使用的redisObject对象表示的。redisObject有3个重要的属性：type、encoding、ptr。其中，type表示value的数据类型，也就是我们上面说的5种数据类型（REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET、REDIS_ZSET）；encoding表示value的编码，即底层使用了哪种数据结构；ptr是一个指向保存value的底层数据结构的指针。其中type和ptr属性不用做过多的解释，一看就知道什么意思，本篇文章主要分析value的encoding编码，也就是不同数据类型的value对应的底层数据结构是什么以及数据结构的原理分析。

Redis中，不同的数据类型和编码的对象关系如下：

为了更清楚地看清他们之间的关系，可以参考下图：

接下来，我们就开始基于5种数据类型展开，分析他们使用的数据结构和实现原理。

String

String类型是Redis中最常使用的数据类型，String对象的encoding有三种：INT、EMBSTR、RAW。

如果value保存的是一个整数值，并且这个整数值可以用Long类型表示，那么value使用的encoding就是INT，并将ptr的值直接设置为value值（long ptr = 123;）。

如果value保存的是一个字符串，当字符串的长度小于等于44字节时，value使用的encoding是EMBSTR，当字符串长度大于44字节时，value使用的encoding是RAW（44字节的界限是Redis3.2之后的最新界限，3.2版本之前是39字节）。

当value的编码为EMBSTR或者RAW时，Redis是如何存储value这个字符串的呢？我们知道，Redis是使用C语言写的，但Redis底层存储字符串时，并没有直接使用C语言的char*字符数组实现，而是自己封装了一种单独的数据结构，这种数据结构叫做SDS（simple dynamic string），翻译成中文就是简单动态字符串。Redis之所以这样做，是因为在某些常用的情况下，C语言的字符串满足不了需求：

（1）C语言中的字符串是以字符数组的形式表示的，所以，如果要获取字符串的长度，需要遍历这个字符数组才能得到，查询时间复杂度是O(N)；

（2）C语言中，字符串的结束是以“\0”作为标识的，也就是说，当遍历一个字符串的时候，碰到“\0”就会自动结束。因此，C语言中的字符串中是不能带有“\0”这个字符的，这就会限制很多使用场景，比如图片、音频、视频这样的二进制数据就无法使用C语言的字符串存储。

● SDS（简单动态字符串）

Redis自己封装的SDS数据结构就解决了C语言字符串的不足。SDS中定义了4个属性：

len：表示字符串的长度。主要作用是当查询字符串长度的时候，直接返回该字段的值，而不用通过遍历字符数组得到，查询时间复杂度为O(1)；

alloc：分配给字符串的空间。这个字段的主要作用是在修改字符串的时候，可以先通过alloc-len计算得到当前剩余的空间大小，然后判断剩余的空间是否满足新的字符串的空间要求，如果不满足要求，则进行自动扩容后再执行修改操作（小于1MB时翻倍扩容，大于1MB时按1MB扩容）；

flags：表示SDS的类型。Redis3.2版本后，Redis定义了5种不同类型的SDS结构：

这5种类型的区别主要是它们内部定义的len和alloc成员变量的数据类型不同。Redis会根据要存储字符串的长度自动选择合适的SDS类型，以达到节省内存空间的目的。

buf[]：字符数组，用来保存实际的字符串的值。该数组中可以存储任意字符，包括“\0”，所以，SDS数据结构可以存储任意类型的字符串，包括图片、音频和视频二进制数据等。

List

List也是我们经常使用的一种数据类型，它是一个列表，支持存储重复的数据。

在Redis3.2版本之前，List对象的encoding有两种：ZIPLIST和LINKEDLIST。当List列表中每个字符串的长度都小于64字节并且List列表中元素数量小于512个时，List对象使用ZIPLIST编码；其他情况使用LINKEDLIST编码。

● ZIPLIST（压缩列表）

在说Redis的ZIPLIST之前，先来看下什么是压缩列表。压缩列表是一种内存紧凑型的数据结构，它的设计思想就是为了节约内存空间。它借鉴了数组的存储思路，占用一块连续的内存空间，但又与数组有些许区别。因为数组要求每个元素占用同样的空间，所以数组会以最大长度的字符串大小作为每个元素的大小：

这样就会造成部分空间的浪费，所以，为了保证占用内存的连续性以及节省更多的内存空间，可以对数组进行压缩，使每个元素的大小为实际存储的大小：

但这样压缩之后，遍历这个数组的时候就会出现问题，因为不知道每个元素的大小，所以无法计算出每个元素的具体位置，所以，我们需要给每个元素增加一个长度的属性length，用来标识当前节点元素的大小，这样在遍历的时候就可以正常计算出下个元素节点的位置了，这就构成了最简单的压缩列表的数据结构：

Redis的ZIPLIST就是基于上面的压缩列表做了自己的封装，先来看下ZIPLIST的整体结构：

在ZIPLIST中，包括以下主要属性：

（1）zlbytes：记录整个ZIPLIST占用的内存字节数，即ZIPLIST的大小；

（2）zltail：记录ZIPLIST中尾结点距离起始地址的偏移量（字节数），通过该偏移量可以直接得到最后一个entry节点，方便从尾结点开始遍历列表；

（3）zllen：记录ZIPLIST的节点数量，即entry节点的数量，通过该属性，可以直接得到ZIPLIST的长度；

（4）entry压缩型列表：存储具体数据的节点，每个entry节点中包含3个属性：prevlen（上一个节点的字节大小）、encoding（记录content的类型和长度）、content（当前节点的实际数据）。

（5）zlend：ZIPLIST的结束标识，是一个固定值：0xFF（十进制255）。

ZIPLIST的好处就是极大的节省了内存空间，但它的缺点也很多，首先，它不能存储太多的元素，否则它的遍历效率就会很低；其次，当新增或者修改某个元素时，会重新分配内存，甚至可能会引起连锁更新的问题。什么是连锁更新呢？简单来说就是我只更新了一个元素，但由于某种原因，导致所有的元素都要做一次更新的动作，大大降低了效率。

那ZIPLIST是如何出现连锁更新的呢？这就要看entry节点中prevlen属性占用空间大小了。prevlen属性记录的是上一个节点的大小，当上一个节点的大小小于254字节时，prevlen属性需要用1字节的空间来保存这个长度值；当上一个节点的大小大于等于254字节时，prevlen属性需要用5字节的空间来保存这个长度值。

那假如现在有一个ZIPLIST，它里面的节点大小都在250~253字节之间，此时我修改了第一个节点，致使它的大小变为了260字节，由于260字节超过了254字节，所以下个节点的prevlen属性需要的空间就从1字节变为了5字节，这就导致第二个节点的大小也超过了254字节，引起第三个节点的更新……这样连锁更新下去，直至最后一个结点：

因此，ZIPLIST只适用于保存的节点数量不多的场景。

● LINKEDLIST（双向链表）

双向链表应该都了解过，我之前的文章中也写过双向链表的一些知识，不了解的可以去看下我之前的文章：LRU算法详解，里面有关于双向链表的解释，以及如何操作双向链表的节点等。Redis中的LINKEDLIST数据结构就是基于双向链表实现的。首先还是看下LINKEDLIST的数据结构图：

可以看到，LINKEDLIST中包含了3个属性：head、tail和len。其中head和tail分别表示一个双向链表的头节点和尾结点，len表示双向链表的长度。除此之外，LINKEDLIST还封装了3个经常使用到的方法：dup（复制节点值）、free（释放节点值）和match（比较节点值），方便了对LINKEDLIST做一些常用的操作。

要说LINKEDLIST有哪些优点，其实就是在说双向链表的优点，首先，LINKEDLIST中维护了双向链表的head节点和tail节点，所以LINKEDLIST可以直接获取到head和tail节点，时间复杂度为O(1)；其次，双向链表的每个listNode节点中，都维护了自己上一个节点prev和下一个节点next的定义，所以，获取某个节点的上一和下一节点的时间复杂度也是O(1)；然后，LINKEDLIST中维护了链表长度的变量len，所以可以直接获取到链表长度，时间复杂度也是O(1)。

但LINKEDLIST的缺陷也很明显：首先，相比于ZIPLIST，双向链表的每个节点的内存并不是连续的，也就无法很好的利用CPU缓存；其次，双向链表的遍历需要从一端开始向另一端遍历，查询一个节点的时间复杂度是O(N)。

● QUICKLIST（快速列表）

由于ZIPLIST和LINKEDLIST都存在不可避免的缺陷，所以，Redis3.2版本之后，引入了一种新的数据结构：QUICKLIST（快速列表）。List对象的底层数据结构也由之前的ZIPLIST和LINKEDLIST变为了新的QUICKLIST。

QUICKLIST结合了ZIPLIST和LINKEDLIST的优点，它是一个以压缩列表（ZIPLIST）为节点的双向链表（LINKEDLIST）。先看一下它的数据结构图：

可以看到，QUICKLIST的数据结构与LINKEDLIST总体上是很相似的，都包含一个双向链表，并且都维护了双向链表的head节点和tail节点，以及链表的节点数量。最大的区别就是双向链表中存储的value值的类型发生了变化，QUICKLIST中使用的链表节点是quicklistNode，quicklistNode中一样包含有指向上一节点和下一节点的指针，它最大的特点是它存储的value是一个指向ZIPLIST的指针zl，ZIPLIST的最大大小由QUICKLIST中的fill属性设置，当某个节点的ZIPLIST的大小超过了fill指定的大小，就会在链表中新建一个ZIPLIST保存到新的quicklistNode节点中。

quicklistNode节点中除了包含prev、next、zl这三个必要的属性之外，还包含一些其他的属性，比如sz，表示当前节点的ZIPLIST占用的总字节数；还有count，表示ZIPLIST中的元素数量。

Set

Set与List差不多，也是一个列表，不过Set不能存储重复的数据，并且Set是一个无序列表。Set对象的编码有两种：INTSET和HASHTABLE。当集合中保存的所有元素都是整数，并且元素个数不超过512个时，Set对象的底层使用INTSET编码；其他情况下统一使用HASHTABLE编码。

● INTSET

INTSET的结构很简单，它只有3个属性：encoding、length、contents。encoding表示编码方式，有INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64三种类型，代表元素的取值范围。length表示集合的元素总数。contents是一个数组，用来存储元素值。

这里要特别说明一下INTSET的encoding属性，Redis在决定INTSET使用哪种encoding时，是根据集合中最大的元素的大小决定的，如果最大的元素大小在INTSET_ENC_INT16允许范围内，那么就会使用INTSET_ENC_INT16。所以，这样就会出现一个encoding升级的现象，也就是encoding从低位向高位转变。

例如，现在有一个INTSET，它的长度是3，它的encoding是INTSET_ENC_INT16（范围在-32,768~32,767），此时，向集合中添加一个新的元素40000，由于40000超过了INTSET_ENC_INT16类型允许的范围，所以，需要将INTSET的encoding升级为INTSET_ENC_INT32，升级过程如下：

（1）按照新的元素的类型，重新给原来的元素分配空间，并给新添加的元素也分配空间；

（2）将原来的元素从后向前转换成新的类型，并将转换类型后的元素放到指定的位置上；

（3）将新元素放到content数组的末尾。

这样设计的优点在于，Redis可以根据添加的元素大小自动选择合适的encoding类型，可以尽可能地节省content数组占用的内存空间。但也有个缺点，那就是encoding只支持升级，不支持降级，比如上面例子中，我们把40000这个元素从集合中移除，虽然剩下的元素都在INTSET_ENC_INT16的范围内，但它的encoding并不会变为INTSET_ENC_INT16，而是继续使用INTSET_ENC_INT32。

● HASHTABLE

HASHTABLE（哈希表）是一个保存key-value键值对的数据结构，它与Java中的HashMap类似，每个key都是唯一的，可以通过key修改或查询value。首先看下HASHTABLE的数据结构图：

HASHTABLE主要包含4个属性：

（1）table：哈希表的主要组成部分，它是一个数组，数组中每个元素的类型都是dictEntry，dictEntry除了保存了key和value之外，还有一个next属性，这个属性使用来干什么的呢？我们在向哈希表中添加key-value时，会先对key做Hash运算得到一个哈希值，然后根据该哈希值得到具体的key的位置。但随着数据的增多，就有可能产生哈希冲突（即两个key的哈希值相同），那怎么解决哈希冲突呢？next属性就是用来解决哈希冲突的，当两个key的哈希值相同的时候，就将新的key放到原来key的下面组成一个链表，这样就可以将哈希冲突的key正常保存到哈希表中，这种解决哈希冲突的方式就是常用的链式哈希法。比如上图中的key2、key5、key6三个key就是哈希冲突后组成的一条链表。

（2）size：dictEntry数组的长度。

（3）used：哈希表中的key的数量。

（4）sizemask：哈希表大小掩码，主要用来计算数组下标。

哈希表使用链式哈希法虽然很好地解决了哈希冲突的问题，但随着存储数据量的增大，哈希冲突的可能性也会越来越高，这样就会导致链表越来越长。当一个链表很长的时候，如果我们要查询某个key，可能需要遍历整个链表才能找到，查询的时间复杂度变为了O(n)，会大大降低查询效率。

所以，在数据量达到一定数量时，Redis会对哈希表做扩容，然后将原来的key重新经过哈希运算（rehash）后放到扩容后数组的指定位置处。触发rehash的条件有两个，只要满足其中任意一个条件，就会做rehash操作：

（1）负载因子大于等于1，并且Redis服务器没有在执行BGSAVE命令或BGREWRITEAOF命令时，将会执行rehash操作。

（2）负载因子大于等于5时，说明此时该哈希表的哈希冲突已经很严重了，将强制执行rehash操作。

其中，负载因子=哈希表以保存的节点数量 / 哈希表大小。

为了方便扩容，Redis在使用哈希表时，单独定义了一个dict结构，dict中包含两个dictht哈希表ht[0]和ht[1]，在默认情况下，只使用ht[0]，不会给ht[1]分配空间。

当dictht[0]中的数据量增大触发扩容时，就会通过以下步骤进行哈希表的扩容和对key的rehash操作：

（1）给哈希表ht[1]分配空间，分配空间的大小为2的n次方中第一个大于ht[0].used * 2的值。比如上图中，ht[0].used的值为6，2的3次方<6*2<2的4次方，则n=4，即分配的空间大小为16；

（2）将ht[0]中的元素经过rehash运算后迁移到ht[1]中；

（3）迁移完成后，释放ht[0]的空间，并把ht[1]设置为ht[0]；

（4）创建一个新的ht[1]哈希表，为下次扩容做准备。

通过扩容并且rehash操作，可以有效地解决哈希冲突的问题，但当哈希表中数据量很大的时候，rehash动作就会耗费很长的时间，影响使用。针对这一问题，Redis使用渐进式rehash方法解决。

渐进式rehash的意思是，不一次性把所有数据rehash到新的哈希表中，而是在每次对哈希表元素进行增删改查时，顺带着对原哈希表中某个下标处的所有数据rehash到新的哈希表中，然后下次对哈希表增删改查时，再把下一下标处的所有元素rehash到新的哈希表中，直到原哈希表中的所有数据全部rehash完成后，整个渐进式rehash动作结束。这样就巧妙地解决了一次性hash带来的耗时问题。

在渐进式rehash过程中，两个哈希表ht[0]和ht[1]时同时存在的，并且两个哈希表中都会存储一部分的数据，所以，在对哈希表进行查询、修改、删除操作时，会先从ht[0]中查找，找不到就会去ht[1]中查找。但想哈希表中新增数据时，只能添加到ht[1]中，这样才能确保ht[0]中的数据越来越少，可以顺利完成rehash操作。

ZSet

ZSet与Set差不多，都是不能存储重复值的列表，唯一的区别是ZSet是一个有序的列表，ZSet列表中的元素都有一个score（分数）的属性，用来表示排序的权重，score越小，排序越靠前。比如我们向zset中添加三个元素one、three、two，他们的score是1/3/2，那查询结果就会自动按score排序。

ZSet对象的底层编码有两种：ZIPLIST和SKIPLIST。ZIPLIST我们上面已经介绍过了，这里着重介绍一下SKIPLIST这种数据结构。

● SKIPLIST

SKIPLIST，俗称跳表，我们先来看一下什么是跳表。跳表是一个基于有序链表实现的可以快速查找元素的数据结构。下图是一个普通的有序链表：

当我们在这个链表中查询某个元素的时候，需要从头开始一个一个向后查找，查询时间复杂度时O(n)，比如我们要查找7这个元素，需要遍历7次才能找到。那有没有什么办法提升查询效率呢？既然这个链表是有序的，那查找7这个元素的时候，可不可以跳过前面的部分元素，直接查找到7附近的元素，然后再进一步定位到7这个元素呢？这样不就可以适当地减少查询次数了吗。于是，初级版的跳表结构就诞生了：

在原链表结构的基础上，每跳过一个元素，使相隔的两个元素相连，在第一层链表的上层组成一条新的链表，我们在查找元素7的时候，先遍历第二层链表，如果遍历节点的元素值小于7，那么继续向后遍历，直到遍历到元素8，发现8大于7，就说明元素7的节点在元素6和元素8节点之间（因为链表是有序的），此时，再从元素6所在节点开始，遍历第一层的链表，然后就顺利得到元素7返回。这样，只需要遍历5次就可以得到结果，链表越长，节省次数的效果越明显，基本可以节省一半左右的时间。

基于这种思想，我们还可以基于第二层链表继续添加第三层链表，结构如下图：

这种结构中，如果我们要查找元素8，那么只需要遍历2次就可以得到结果，而在上面的两种结构中则分别需要8次和4次。所以，当链表非常长的时候，这种跳表结构可以让我们跳过很多下层节点，大大地提高查询效率。

上面介绍的这种跳表结构中，上面一层链表的节点数量始终是下面一层链表节点数量的一半，这样在插入新元素的时候会有问题，比如现在添加一个1.5进去，要维持这种关系的话，那么1.5节点之后所有的节点都要重新调整，这就导致时间复杂度重新退化成O(n)。

针对这一问题，SKIPLIST做了优化，它不要求上下层链表的节点个数严格按照1:2的方式实现，而是在添加节点时，算出一个随机数作为该节点的层数。随机数的算法是：先生成一个范围在0~1的随机数，如果这个随机数小于1/4（即0.25），则层数就增加一层，然后循环这个步骤，直到生成的随机数大于1/4，最后得到的层数即为新节点的层数。这种算法相当于是每增加一层的概率只有25%，层数越高，概率越小。

这样，添加新节点时只需要改变新节点前后节点的指针即可，其他节点不受影响，完美地解决了添加节点的耗时问题。

Redis中的SKIPLIST与上面传统的SKIPLIST类似，不过有些许不同。由于ZSet的特性，要求每个元素除了带有自身的value值以外，还有一个代表排序权重的score属性，所以，Redis封装了自己的SKIPLIST节点，结构如下：

其中，ele用来保存字符串格式的value值；score保存元素的分数；backward是一个后项指针，指向链表的上一个节点，方便倒序查找，只有最底层的链表是一个双向链表；level[]数组是一个前项指针数组，保存每层链表上的前向指针和跨度，跨度用来计算节点的排名。

有了zskiplistNode结构之后，Redis中的SKIPLIST结构就出来了：

zskiplist中分别定义了一个zskiplistNode类型header节点和tail节点，表示跳表的头节点和尾节点；还有一个length属性，表示节点数量；最后还有一个level属性，表示当前跳表中一共有多少层链表。

Hash

Hash对象就类似于Java中的对象，Hash对象中有很多属性以及属性的值，我们可以直接修改Hash对象中某个属性的值，而不用修改整个Hash对象。

Hash对象的底层编码有两种：ZIPLIST和HASHTABLE。这两种数据结构在上面都已经介绍过了，这里就说一下什么情况下使用哪种数据结构。当Hash对象中保存的属性的数量小于512个，并且所有键值对的长度都小于64字节时，使用ZIPLIST结构，其他情况下都是用HASHTABLE结构。

5种数据类型的使用场景

想要知道哪种数据类型适用于哪些场景，无非就是看他们的优点有哪些，然后看这些优点能做到哪些事情。

■ String类型：这种类型就不必过多介绍场景了，相信只要使用过redis的人都用过这种类型，这里就简单举几个例子：保存用户token，保存图片视频等二进制文件等；当存储数字时，还可以使用它的incr命令进行数字的原子性递增，可以用来统计数量。

■ List类型：Redis在存储List类型时，我们可以用LPUSH命令向List的左侧添加数据，然后用RPOP命令从List右侧取出数据，根据这个特性，我们就可以实现一个生产消费模式，生产者向List的一端添加数据，消费者从另一端取出数据，这样就实现了一个消息队列。

■ Set类型：Set类型的特点就是没有重复数据的列表，所以可以使用Set类型进行去重，也可以用于给用户打标签，然后根据标签中的内容给用户推送对应领域的消息。

■ ZSet类型：ZSet的特点是有序的集合，所以，我们可以使用该类型来实现自动排序的功能。例如新闻热搜排行榜，可以给每条新闻设置不同的score来达到自动排序的效果。

■ Hash类型：Hash类型经常用于存储一些对象类型的数据，比如我们可以把User对象存到Hash类型中，当需要修改User的某个属性的值时，可以直接修改对应的属性值，而不用修改整个User对象。

以上内容就是就是我分享的关于Redis数据结构的底层结构原理，如果想要对Redis的设计及实现有更多的了解，推荐看下下边《Redis设计与实现》这本书：

该书行文流畅，思路清晰，对Redis的各个方面的设计思想及实现原理都进行了非常详细的讲解，相信你读完该书之后，会对Redis的内部构造以及运作机制更加了解，实际使用起来也会更加得心应手。

点关注不迷路，跟我一起学技术！

关注同名微信公众号【Java架构成长之路】获取更多文章~