Redis 学习笔记 08：数据结构与对象小结

我是架构精进之路，点击上方“关注”，坚持每天为你分享技术干货，私信我回复“01”，送你一份程序员成长进阶大礼包。

通过前面几篇文章，主要介绍了 Redis 基础数据结构知识。

Redis 有 5 个基本数据结构，string、list、hash、set 和 zset。它们是日常开发中使用频率非常高应用最为广泛的数据结构，需要吃透才行。

string

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

计数器

如果字符串的内容是一个整数，那么还可以将字符串当成计数器来使用。

计数器是有范围的，它不能超过 Long.Max，不能低于 Long.MIN

过期和删除 字符串可以使用 del 指令进行主动删除，可以使用 expire 指令设置过期时间，到点会自动删除，这属于被动删除。可以使用 ttl 指令获取字符串的寿命。

list

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

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

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

快速列表

如果再深入一点，你会发现 Redis 底层存储的还不是一个简单的 linkedlist，而是称之为快速链表 quicklist 的一个结构。首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist，也即是压缩列表。它将所有的元素紧挨着一起存储，分配的是一块连续的内存。当数据量比较多的时候才会改成 quicklist。因为普通的链表需要的附加指针空间太大，会比较浪费空间。比如这个列表里存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next。所以 Redis 将链表和 ziplist 结合起来组成了 quicklist。也就是将多个 ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。

hash

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

set

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

• 增加元素 可以一次增加多个元素

• 读取元素 使用 smembers 列出所有元素，使用 scard 获取集合长度，使用 srandmember 获取随机 count 个元素，如果不提供 count 参数，默认为 1

• 删除元素 使用 srem 删除一到多个元素，使用 spop 删除随机一个元素

• 判断元素是否存在 使用 sismember 指令，只能接收单个元素

sorted set

SortedSet(zset)是 Redis 提供的一个非常特别的数据结构，一方面它等价于 Java 的数据结构 Map<String, Double>，可以给每一个元素 value 赋予一个权重 score，另一方面它又类似于 TreeSet，内部的元素会按照权重 score 进行排序，可以得到每个元素的名次，还可以通过 score 的范围来获取元素的列表。

zset 底层实现使用了两个数据结构，第一个是 hash，第二个是跳跃列表，hash 的作用就是关联元素 value 和权重 score，保障元素 value 的唯一性，可以通过元素 value 找到相应的 score 值。跳跃列表的目的在于给元素 value 排序，根据 score 的范围获取元素列表。

跳跃列表

zset 内部的排序功能是通过「跳跃列表」数据结构来实现的，它的结构非常特殊，也比较复杂。

- END -

作者：架构精进之路，专注软件架构研究，技术学习与个人成长，关注并私信我回复“01”，送你一份程序员成长进阶大礼包。



Thanks for reading!