Redis中的5种基础数据结构

Redis 中的5种基础数据结构（重点）

5种基础数据类型分别是：string（字符串）、hash(字典)、list(列表)、set(集合)、zset(有序集合)

1. string(字符串) 类型

字符串是Redis中最简单的数据结构，他的内部就是一个字符数组（名字不能重复哦），如图所示。

每个string类型的key作为这个数组中的一个名称，每一个唯一的key都对应一个value数据。不同类型的数据结构的差异就在于key对应的value的结构不一样

字符串结构的Redis使用是非常广泛的，比方说我要存一个用户的信息到Redis中，就可以将用户信息（JSON类型的）序列化成字符串，然后将这个字符串作为value放到Redis中作为缓存。在需要获取这个信息时，将之前存的字符串反序列化成JSON类型返回即可。

Redis中value为字符串类型的结构，这个字符串类型的结构其实是一个动态的字符串，是可以进行修改的，内部实现类似于Java中的ArrayList，采用的是预分配冗余空间的方式来减少内存的频繁分配，如下图所示，预分配的实际空间capacity 的长度一般要大于实际占用的长度len。当字符串的长度小于1MB时，扩容的大小是当前现有空间的二倍，当字符串长度大于1MB时，扩容时一次长度只会增加1MB的空间。注意字符串的最大长度为512MB。

如果value的类型是一个整数，那么可以对这个value进行自增操作，但是需要注意，自增是有范围的，他的范围是signed long 的最大值和最小值之间，超过这个数Redis会报错的

2.list(列表)类型

Redis 中的list相当于Java中的LinkedList，是一个双向链表不是数组。所以他的增删改操作的数据非常快，时间复杂度是O(1)，相对而来带来的问题就是他的查询数据的数据较慢，时间复杂度为O(n)。因为是双线链表，所以支持从前或者从后进行遍历。结构大概如下图所示：

如果列表中的最后一个数据也被删除，则该数据结构也会被自动删除，内存被回收。

正是因为list的这种数据结构，他常被用来做异步队列使用，和之前学过的RabbitMQ很相似。

双向链表的玩法非常多，比如可以利用链表的方向来实现 队列（右进左出）、栈（右进右出）；

可以利用双向链表的索引位置来进行 慢操作 ，list中有一个方法lindex 用来获取对应索引处的value值，对链表进行索引是需要遍历整个链表的，所以当链表中的数据量越多的时候，使用lindex方法的性能会越来越差。还有一个方法是ltrim方法，他有两个参数 start index 和 end index ，主要作用是将该链表只保留这两个索引之间包括两个索引位置的数据，其他的数据删除。使用该方法时要慎用，因为他也是需要来通过遍历链表来获取对应的索引位置，所有时间复杂度较高为O(n)。

之前说Redis和LinkedList很像，但是他不单单是一个简单的LinkedList，而是一个 快速列表（quicklist） 。当数据较少时，会使用一块连续的内存进行存储，这个结构是ziplist，也叫压缩列表。当数据量较多时才会改成quicklist。这样做的好处相比于普通的双向链表节省了大量的空间，因为普通的双联链表需要附加指针空间。即使是一个简单的数据也要添加 前指针prev 和 后指针next 。quicklist的结构如下图所示。

3.hash(字典)类型

Redis中的hash（字典）相当于Java中的HashMap，他是无序的，都是 数组+链表 的的二维结构。结构如图所示：

与普通的HashMap不同的是，Redis中的hash的值只能是字符串类型的，还有他们的rehash的方式不同。Java中的rehash是将所有数据一次性全部rehash，这个是非常耗时的，Redis为了追求好性能采用的是渐进式的rehash，底层用两个数组进行维护，他不会一次性将所有的数据全部转移。当数组达到阈值需要扩容时，他会将数组2的长度设置为数组1的2倍，然后将rehashidx置换成1（默认是-1），之后没尽兴一个增删改查时这个rehashidx都会加1，如果到达的位置上有数据则将该数据转移到数组2中，而新添加的数据是存放在数组2中的，当数组1中的所有元素都转移到数组2中时，他会将之前的数组1置换成数组2，将数组2置换成数组1，然后rehashidx又恢复成-1。这样做的好处就是提高的Redis的性能！

4.set(集合)类型

Redis中的set（集合）相当于Java中的hashset，它内部的键值是 无序的 、 不可重复的 。它内部实现相当于一个特殊的字典，字典中所有的value都是一个值null。

当集合中的最后一个元素被删除时，该数据结构就会被删除、内存被回收。

我们经常用set类型存储某个活动中的中奖用户的id，因为不能重复，可以保证一个用户不能中奖两次。

5. zset(有序列表)类型

zset是Redis中特有特点的数据结构。它类似于SortedSet和HashMap的结合体，所以他有着set的特点就是value是唯一的，另一方面他给每个value赋予了一个唯一的score，代表这个value的排序权重。他的内部结构实现是一种 [[跳跃列表]] 的数据结构。

跳跃列表：

Redis中的zset（有序列表）的value是一个不重复切有序的数据类型，其底层是一种跳跃列表。

那么什么是跳跃列表呢？为什么要使用跳跃列表？

之所以使用跳跃列表是因为zset是一个有序的链表，这也就意味着他每次添加数据的时候都要计算其在底层链表中的位置，一般情况下我们会使用二分法进行定位，但是二分法只能应用于数组所以就使用到了这种和二分法思想非常相似的跳跃列表。

跳跃列表的底层非常的复杂且巧妙，它实现了数据的分层跳跃操作。比方说我将一些数据使用zset类型添加到Redis中，添加之后如下图中的L0，L0保存了添加的所有数据。跳跃列表的第一个元素是一个 哨兵Sentinel ，作为起始点他不保存数据只是指向下一个数据，进行分层时他会指向下面的第二个元素然后进行一个随机的判断，如果判断结果为 Y 则这个元素就会晋级到L1层，以此类推一直到最后一个元素；当L0的元素都进行判断完之后且L1的元素不唯一时，他会对L1中的每个元素进行判断，直到被筛选出来的那层元素唯一才算分层结束。

那么向跳跃列表中查询数据是如何实现的呢？
他会从最高层L3中的元素和要查询的元素进行比较，如果要查询的元素比L3中的元素小意味着要查询的数据在L3中元素的左边，到L2层时他会送L3层中元素的左边的元素开始判断，以此类推如果找到元素则返回地址，否则会一直向下层找如果找到最下层L0还是没有找到那么就说明该元素不存在！

如果向跳跃列表中添加元素？
首先会对这个要添加的元素进行判断，直到结果为 N 时判断结束，获取了要填的元素对应的层数。比如说要添加的元素是9 ，如果所示判断结果在L2层，此时将9和起始节点2相比结果比2大则其位置在2的右边所以将9指向2和13，到了L1层因为L1的启示是其又指向了2和11，最后到了L0时将其指向8和11最后插入成功！