支持一下

推荐一下《Redis 开发与运维》

在哪看的

Q3： 我们都知道Redis里面除了有链表，字典，跳表，还有压缩列表，请你简单介绍一下压缩列表的结构，然后解释一下压缩列表中的连锁更新问题。 A： 之所以叫压缩列表是因为没有指针参与的原因，结构大概是`zlbytes、 zltail、zllen、entrys、zlend`这几个构成，然后zlbytes是整个压缩列表的总字节数. 其中的entrys里面记录着所有的内容，但是因为没有指针，所以就在每个entry上添加了一个`pre_entry`用来记录上一个entry项的长度，用于遍历。 而且这里的pre_entry不是固定大小，如果前一个项大于254字节，它就会变成5个字节，其中第一个字节为0xEF，剩下4个字节则用于保存长度，这样就会导致一个问题，比如新增加一个大于254的节点，但是表头的pre_entry是1个字节，然后将其进行扩容，这样就会导致**后面的每个项都需要移位**，另外，如果这个表项修改完之后变成了大于254字节，就会后面的同样需要更新，依此类推，**就会导致连锁更新问题**。但是看书上给出的答案就发现连锁更新不会造成很严重的性能问题：**因为多个连续的临界表项才会可能被引发，对于少量节点的更新并不会影响性能**。

Q2: 我们都知道Redis里的跳表是一种平衡树的不错的替代数据结构，你可以讲一下跳表的结构，然后大概讲一下level中的前进指针的跨度是怎样生成的吧？ A: 跳表是使用类似于双向链表的结构，可以通过多个zskipListNode直接组成，也可以添加zSkipList表头后形成。首先就是同样的`header`、 `Tail`头尾指针（其中header指向的是一个表头），然后不一样的地方在于增加了`level`、`length`两个属性，一个是结点的个数，另外一个是最高的层数。然后结点的结构呢，也有几个属性（`score, object, level[], backward`）其中level数组中是不同级别，不同级别中分别对应不同的前进指针和跨度。 这里说的跨度就是前进指针的移动距离，它的生成规则也比较简单，假设最开始的时候，跳表是空的，这个时候新添加一个跳表节点，首先会随机生成一个1~32之间的数作为这个节点的层高度，然后从表头出发，用前进指针指向表尾，期间经过的节点进行连接，比如说有两个节点，都有L5，但是中间隔了两个点（高度均小于5），那么遍历后的结果就是第一个节点的第5层的前进指针的跨度是2.。跨度除了用来进行遍历，还可以用来**计算目标结点的排位**

Q1： 知道Redis的字典吧，问你个问题，字典的底层数据结构知道怎么实现的吗？Java的HashMap不是采用的是数组加链表加红黑树，为什么这里的哈希表解决键冲突的时候用的是拉链法，而没有用到红黑树呢？ A: 字典的底层数据结构就是哈希表，而且使用的是两个哈希表，第一个哈希表用于存放数据，第二个哈希表用户扩容（Rehash），字典的结构是`type`、`ht`、`rehashIndex` 、`privatedata` 而关于HashMap中的键冲突问题，首先是采用拉链法，在java 1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。（桶的数量必须大于64，小于64的时候只会扩容）发生hash碰撞时，java 1.7 会在链表的头部插入，而java 1.8会在链表的尾部插入。而且可以看到转换红黑树的时机是超过一定大小才会去转换，因为红黑树是一种自平衡二叉搜索树，它可以保证在**最坏情况**下，查找、插入和删除操作的时间复杂度为O(log n)。也就是说在规模不断增加的情况下，红黑树是比较不错的选择，但是如果规模比较小的话，就没必要采取红黑树了。 另外，Redis的哈希表会让键值对处于一个合理的区间（执行BGSAVE指令时，哈希表的负载因子大于等于1，未执行BGSAVE时，负载因子大于等于5执行扩展；哈希表的负载因子小于0.1自动执行收缩===》**执行BGSAVE命令时，Redis需要创建当前进程的子进程（写时复制优化子进程的使用效率），因此提高扩展所需要的负载因子，尽可能避免执行扩展，最大限度节约内存**），因此会自动进行Rehash去扩展与收缩，**查询性能消耗并不大，因此采取红黑树反而增加了性能耗费**。因此，并没有采用红黑树来实现哈希表的冲突扩展。