我在“redis存储结构”这篇文章中介绍了redis存储数据的方式——字典，redis的字典使用高效的hash table实现，这里详细介绍redis中哈希表的实现和工作原理
redis的哈希表结构
typedef struct dictht { //哈希表数组 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩码，用于计算索引值 unsigned long sizemask; //该哈希表已有的节点数量 unsigned long used; } dictht;
可以看到，redis的哈希表只是比我们常用的哈希表多了size、sizemask、used这三个额外字段，这三个字段是用来支持其它功能的，本文不详细介绍
redis的哈希表节点
typedef struct dictEntry { //键值对中的键 void *key; //键值对中的值 union { void *val; uint64_t u64; int64_t s64; double d; } v; //指向下一个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;
1.next指针是用来解决哈希冲突的，没错，redis解决哈希冲突的方案是链地址法，也就是将哈希值相同的节点用链表组织起来，而redis使用rehash保证了这个链表的长度的不会太长，后面会详细介绍
2.key指向固定的对象string，这一点在“redis存储结构”文章中已经解释过
3.value使用union来实现保存不同类型值的功能，提供了较强的灵活性，且避免了全部使用指针的情况，节约了内存
哈希表的添加过程不再赘述，属于基础数据结构的范畴
解决哈希冲突
一、rehash
上文提到，redis使用链地址法解决哈希冲突，由于哈希表的数组长度在创建时就固定了，当节点数量过多时会造成链表长度过长，导致查询的时间复杂度降为O（N），导致性能降低的一个原因是数组长度，另一个是hash算法
redis的做法是，使用两个哈希表，一个为目前使用的，另一个为空，在当前使用的哈希表节点数等于数组长度时，即将发生哈希冲突，此时将另一个哈希表数组长度设置为当前的2倍，并将旧数组中的节点迁移到新数组中，这样一来，新的哈希表成为当前所使用的，并且数组的长度得到了增长，缓解了数组空间不足造成的哈希冲突
所以redis在使用哈希表时，实际上有两个哈希表，一个供当前使用，另一个供rehash使用
typedef struct dict { … //两个Hash表，交替使用，用于rehash操作 dictht ht[2]; … } dict;
当旧哈希表的数据全部迁移到新哈希表后，旧哈希表的空间会被释放
rehash的过程可以进行多次，基于两个哈希表的交替使用来实现
一次性rehash的缺陷
按照我们的想法，当旧哈希表的节点数等于数组长度时，考虑进行rehash
1.rehash是一次性进行的吗？
2.rehash的过程中如果有新的数据添加进来，该怎么处理？
3.rehash的过程中如果要进行数据查找，去哪找？
当旧哈希表中的节点数量比较庞大时，一次性rehash会造成redis阻塞较长时间，无法响应其他请求，这显然不是redis的风格
渐进式rehash
既然一次性rehash会造成性能下降，那么分批次进行不就好了，
redis的方案是在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「旧哈希表」中索引位置上的所有 key-value 迁移到「新哈希表」 上；
回到上面的问题
分次rehash的过程中会出现数据分布的情况，也就是一些数据在新哈希表中，另一些数据在旧哈希表中：
Q:
1.rehash的过程中如果有新的数据添加进来，该怎么处理？
2.rehash的过程中如果要进行数据查找，去哪找？
A:
1.如果有新的数据添加进来，将添加到新哈希表中，保证了旧哈希表的节点数只会减少，最终为空
2.先查找旧哈希表，如果没有，再查找新哈希表
rehash触发条件
在上文简单提到，当哈希节点数等于数组长度时，我们认为即将发生哈希冲突（实际上有可能已经发生），那么rehash的具体时机是怎么确定的？
触发 rehash 操作的条件，主要有两个：
- 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
- 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。
- 当负载因子小于0.1时，程序自动进行缩容操作
负载因子 = 哈希表中当前节点数 / 哈希表数组大小
