42张图，带你真正搞懂redis数据类型的底层( 五 ) _redis

前一节点的长度小于 254 字节，则 previous_entry_length长度为1字节
前一节点的长度小于 254 字节，则 previous_entry_length长度为5字节假如现在有一组压缩列表，长度都在250字节至253字节之间，突然新增一新节点 new，长度大于等于254字节，会出现：

文章插图

g3
程序需要不断的对压缩列表进行空间重分配工作，直到结束。
除了增加操作，删除操作也有可能带来“连锁更新” 。请看下面这张图，ziplist 中所有 entry 节点的长度都在250字节至253字节之间，big节点长度大于254字节，small节点小于254字节：

文章插图

在我看来，压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的entry数；压缩列表在表尾还有一个 zlend，表示列表结束罢了。
字典“
又叫符号表或者关联数组、或映射（map），是一种用于保存键值对的抽象数据结构。字典中的每一个键key都是唯一的，通过key可以对值来进行查找或修改。C语言中没有内置这种数据结构的实现，所以字典依然是 Redis自己实现的；示例：
”
redis > SET msg "hello world"OK（“msg”，“hello world”）这个就是字典;
哈希表结构：

typedef struct dictht{//哈希表数组dictEntry **table;//哈希表大小unsigned long size;//哈希表大小掩码，用于计算索引值//总是等于 size-1unsigned long sizemask;//该哈希表已有节点的数量unsigned long used; }dictht

哈希表是数组(表）table 组成，table里面每个元素都是指向 dict.h 或者 dictEntry 这个结构，dictEntry 结构：

typedef struct dictEntry{//键void *key;//值union{void *val;uint64_tu64;int64_ts64;}v;//指向下一个哈希表节点，形成链表struct dictEntry *next;}dictEntry

哈希表就略微有点复杂。哈希表的制作方法一般有两种，一种是：开放寻址法，一种是拉链法。redis的哈希表的制作使用的是拉链法。
整体结构如图：

文章插图

哈希1
“
也是分为两部分：左边橘黄色部分和右边蓝色部分，同样，也是”统筹“和”实施“的关系。具体哈希表的实现，都是在蓝色部分实现的,好！先来看看蓝色部分：
”

文章插图

这也会分为左右两边“统筹”和“实施”的两部分。
右边部分很容易理解：就是通常用拉链表实现的哈希表的样式；数组就是bucket，一般不同的key首先会定位到不同的bucket，若key重复，就用链表把冲突的key串起来。
新建key的过程：

文章插图

哈3
假如重复了：

文章插图

哈4
rehash“
再来看看哈希表总体图中左边橘黄色的“统筹”部分，其中有两个关键的属性：ht和 rehashidx 。ht是一个数组，有且只有俩元素ht[0]和ht[1];其中，ht[0]存放的是 redis中使用的哈希表，而ht[1]和rehashidx和哈希表是有 rehash 有关系的。
”
rehash指的是重新计算键的哈希值和索引值，然后将键值对重排的过程。
加载因子（load factor）=ht[0].used/ht[0].size；
扩容和收缩标准扩容：

没有执行BGSAVE和BGREWRITEAOF指令的情况下，哈希表的加载因子大于等于1 。
正在执行 BGSAVE和BGREWRITEAOF指令的情况下，哈希表的加载因子大于等于5。

收缩:

加载因子小于0.1时，程序自动开始对哈希表进行收缩操作;

扩容和收缩的数量；扩容：第一个大于等于 ht[0].used*2的 2^n(2的n次方幂);
收缩：第一个大于等于 ht[0].used的 2^n(2的n次方幂) 。(以下部分属于细节分析，可以跳过直接看扩容步骤)
对于收缩，我当时陷入了疑虑：收缩标准是加载因子小于0.1 的时候，也就是说假如哈希表中有4个元素的话，哈希表的长度只要大于40，就会进行收缩，假如有一个长度大于40，但是存在的元素为4 即( ht[0].used为4)的哈希表，进行收缩，那收缩后的值为多少？