建筑大家好，我是北军。之前给大家介绍了Redis的基本数据结构，本文介绍Redis字典的rehash过程。并比较了Java中HashMap的一些异同。一、前言我们先来回顾一下前面提到的Redis字典结构。示意图如下：Redis的字典本质上是一个数组+链表的数据结构，和Java中的HashMap数据结构很像。从上面的结构图也可以看出，字典dict中维护了一个ht数组，只有两个元素。这两个要素是它扩展的关键点，我们后面会讲到。Redis中的哈希对象在以下情况下使用ziplist编码。哈希对象中存储的所有键值的字符串长度小于64字节。hash对象存储的键值对数量小于512，否则hash对象会使用hashtable编码，hashtable会使用字典作为底层实现。下面redis哈希对象编码由ziplist改为hashtable。2.添加元素和键冲突当不同的键值被赋值给同一个哈希表数组的同一个索引，经过散列和散列算法之后，那么之后就会出现键冲突。Redis哈希表也是使用链表地址的方式来解决哈希冲突的。使用哈希节点的next指针将同一哈希表数组索引上的元素链接起来。但是，Redis会将新添加的哈希节点添加到链表的头部位置。如下：如果程序要将键值对(k2,v2)加入到下面的哈希表中，计算出来的书的索引为1，那么就会和(k1v1)冲突。解决冲突时，两个节点使用next指针链接。并且新节点将被添加到链表头部的位置。哈希表1链表解决哈希冲突后的哈希表3.Rehash扩容过程哈希表不断增加元素。当元素个数达到一定比例后，程序将对哈希表进行相应的扩展。这是通过执行重新散列（rehashing）操作来完成的。步骤如下：在进行扩容操作时，会将字典中ht[1]哈希表的大小设置为第一个大于等于ht[0]的ht[0].used*22^n（n次方的2）。ht[0]中存储的所有键值对都会被rehash到ht[1]，rehash过程中会重新计算hash值和索引值。当ht[0]中的所有键值对迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并创建一个空的哈希表。对下图中的字典进行rehash操作：ht[0].used为4,4*2=8,2的3次方8是2大于4的n次方即程序会将ht[1]的大小设置为8并分配空间。结构如下：将ht[0]上的所有键值对rehash到ht[1]，如下图：释放ht[0]，将ht[1]设置为ht[0]，然后然后给ht[1]分配一个空白哈希表如下图所示：上图是rehash过程的示意图。4.Progressiverehash以上是rehash的一个理论过程。在实际运行中，redis不会一次完成所有的迁移。如果键值对的数量非常多，迁移过程肯定需要一段时间。由此可见，服务端不可能一次迁移所有的键值对。需要分成多次，逐步将ht[0]中的键值对迁移到ht[1]中。步骤如下：首先，将内存空间分配给ht[1]。这时候redis字典有两个哈希表。字典中维护了一个rehashidx计数器，其值设置为0，表示rehash工作开始。在rehash期间，程序仍然可以增删改查。此外，它还会将ht[0]上的rehashidx索引上的所有键值对重新哈希到ht[1]。rehash工作完成后，会对rehashidx的值加1。随着字典的操作，当ht[0]上的所有键值都rehash到ht[1]时，程序会将rehashidx的值设置为-1，表示rehash操作已经完成。在progressiverehash的过程中，仍然可以对redis字典进行增删改查。添加元素时，元素会直接保存在ht[1]中，删除、查找、更新操作会在两个ha中进行，查找时会在ht[0]中查找，然后进行在ht[1]中搜索。上述措施可以使ht[0]中的元素只会减少，最终变成一个空列表。综上所述，Redis字典使用哈希表作为底层，每个字典维护两个哈希表，ht[0]是主要使用的哈希表，ht[1]仅在rehash过程表中使用。哈希表底层也采用了数组+链表的结构，类似于Java中的HashMap，只是在Java8之后增加了一棵红黑树，在某些情况下会替换掉链表。当向哈希表中添加元素遇到哈希冲突时，会将新添加的元素放在链表的头部，而JavaHashMap会将其放在链表的尾部。在扩容过程中，redis字典是逐渐扩容的，扩容过程中还是可以进行操作的，而Java的HashMap的扩容需要一次性完成。
