链表

链表的数据结构

一目了然，因为C底层没有链表结构，所以Redis自己实现了，是一个双端链表。
但不仅如此，Redis还设计了一个list结构体来持有链表使得操作起来很简易。

举个例子：

链表总结:

• 双端链表，取某个节点的前置节点和后置节点，取表头节点与表位节点的复杂度都为O(1)。
• list中由链表的长度，程序获取链表长度时不需遍历，因此复杂度为O(1)。
• 无环链表，表头的pre与表尾的next都为null。

字典

Redis中的字典，类似于Java中的Map，都是属于键值对，并且键都是独一无二的，通过键来取得值，或者通过键删除等。底层使用哈希表来进行实现，一个哈希表中有多个节点，每个节点来保存一个键值对。

哈希表的数据结构

table属性是一个数组，用来指向哈希表的节点。
sizemask的值为size-1，用来添加节点时，对节点的键的hashcode取余接着存入哈希表中。

取余其实可以直接用除，例如一个table的长度为4，这时要添加一个键，hashcode为17(随便取得，实际使用时应用hash算法使得键的分布越散越好)，那他所要添加的槽也就是17%4=1但这样的操作在计算机中十分缓慢，因此使用与操作：17&（4-1）=1，结果是相同。这就是sizemask的用处，在Java中Hashmap中也可以看到这样的影子。

空的哈希表:

哈希表节点的数据结构

Redis中哈希表中使用拉链法解决键冲突，因此next就是下个节点的指针。

字典的数据结构

• type与privdata是针对不同类型的数据结构，为多态字典而设置。
• 可以看到，这个字典持有不止一个哈希表，难道一个字典有两个哈希表吗？
  不是的，另外一个哈希表是扩容时使用的也就是rehash时使用。
• rehashidx是rehash的进度，每完成一个键的迁移，就会加一，-1时就为结束。

Redis使用MurmurHash2算法来计算键的哈希值，具体的落槽方法前面已经讲过，这里就不展开了哈。

rehash

在Java中HashMap的负载因子为0.75，也就是说出于性能和空间的考虑，当table上的数据为整个表的0.75时就会进行扩容。Redis也存在相同的操作，为了让负载因子不会太大或太小，程序会对哈希表的大小进行扩容或缩减。
扩容步骤如下：

1. 为字典的另一个哈希表ht[1]分配空间，也就是ht[0]长度的2次幂
2. 将保存在ht[0]上次键值对rehash到ht[1]上，需要重新进行计算键的哈希值与索引值也就是落槽点，然后放置。
3. 当全部迁移完毕时，释放ht[0]，将ht[1]设置为ht[0]，并为ht[1]重新创建一个空包哈希表，为下次扩容做准备。

扩容条件：

1. 服务器没有执行BGSAVE或者BGREWRITEAOF命令，且哈希表的负载因子大于等于1
2. 服务器正在执行BGSAVE或者BGREWRITEAOF命令，且哈希表的负载因子大于等于5

这两个命令与Redis的备份有关，因此负载因子的不同还是最大限度的节约内存。

收缩条件：哈希表的负载因子小于0.1

但是rehash这个操作并不是一次性全部完成的，是渐进式rehash，分多次、渐进式完成。原因是当哈希表中存在几千万的键值对时，一次性完成rehash可能造成服务器一段时间停止服务。
渐进式rehash步骤：

1. 为ht[1]分配空间，使得字典拥有两个哈希表
2. 把字典结构体中的rehashidx置为0代表rehash工作正式开始进行
3. 在rehash期间中，每次迁徙一个键值对，rehashidx就会加一
4. 当ht[0]全部被rehash到另一个表时，置rehashidx为-1代表操作已完成。、

当rehash时，查找、删除、更新操作会在两个表都进行，先从ht[0]操作操作不到再在ht[1]操作。
而新增操作只会在ht[1]中进行，这样可以保证ht[0]只减不增。