【Redis系列】那有序集合为什么要同时使用字典和跳跃表

面试官：听说你精通Redis，那我就考考你吧

面试官：不用慌尽管说，错了也没关系😊。。。

以【面试官面试】的形式来分享技术，本期是《Redis系列》，感兴趣就关注我吧❤️

面试官：你说说Redis有什么底层数据结构支持

好的，我了解的主要有：

1. 字典
2. 跳跃表
3. 链表，Redis采用了有前置后置节点的双端链表，列表键List就是采用这种结构。

面试官思考中…

面试官：先讲讲你对字典的理解

好的，字典其实是一个集合里包含了多个键值对，类似于Java的HashMap。

它的底层包含了两个哈希表，一个平常使用，一个在迁移扩展哈希表rehash时使用。

迁移完成后，原先日常使用的旧哈希表会被清空，新的哈希表变成日常使用的。

面试官思考中…

面试官：那字典和Redis的哈希对象不是没什么区别？

有区别的，面向对象不同。

字典是Redis内部的底层数据结构支持，而Redis的哈希对象是对外提供的一种对象。

面试官思考中…

面试官：跳跃表呢

它的底层结构类似于一个值 + 保存了指向其他节点的level数组（层），而这个level数组就是用来加快访问其他节点的速度。

typedef struct zskiplistNode {
   
   
    // level数组
    struct zskiplistLevel {
   
   
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    } level[];
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
} zskiplistNode;

面试官思考中…

面试官：那有序集合为什么要同时使用字典和跳跃表来实现

这个设计主要是考虑了性能因素。

1. 如果单纯使用字典，查询时的效率很高是O(1)，但执行类似ZRANGE、ZRNK时，排序性能低。每次排序需要在内存上对字典进行排序一次，同时消耗了额外的O(n)内存空间
2. 如果单纯使用跳跃表，查询性能又会从O(1)上升到了O(logN)

所以Redis集合了两种数据结构，同时这两种数据结构通过指针来共享变量也不会浪费内存。

typedef struct zset {
   
    // 有序集合
    zskiplist *zsl; // 跳跃表
    dict *dict; // 字典
} zset;

面试官思考中…

面试官：Redis为了节约内存采用了什么数据结构知道吗

噢噢知道的。我了解的有两种。

1. 当列表键只有少数几个，且都是整数型的话，Redis会改用整数集合进行存储。
2. 当列表键只有少数几个，且都是整数型或长度短的字符型的话，Redis会改用压缩列表进行存储。

# 可以看到创建了列表键类型，但实际存储类型是ziplist

redis＞ RPUSH lst 1 3 5 10086 "hello" "world"
(integer)6
redis＞ OBJECT ENCODING lst
"ziplist"

面试官抓抓脑袋，继续看你的简历......

得想想考点你不懂的😰

未完待续。。。。。。

好了，今天的分享就先到这，我们下期【Redis系列】继续。

创作不易，不妨点赞、收藏、关注支持一下，各位的支持就是我创作的最大动力❤️