浅谈Redis中的字典、哈希算法和ReHash原理
导读
Redis 中的字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。
字典的底层实现为哈希表，每个字典带有两个哈希表，一个平时使用，另一个在进行rehash扩充空间时才使用。
字典的结构定义
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表，两个元素
dictht ht[2]
// rehash时记录的索引下标，当没有rehash时，值为-1
int rehashidx;
} dict;
==在进行 rehash时，rehashidx每迁移一个索引的entry数据就会 + 1；==
其中，哈希表dictht 的结构定义为：
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
unsigned long sizenask;
// 该哈希表已有节点的数量
unsigned long uesd;
} dictht;
其中，table是一个数组，数组的每一个元素指向 dictEntry 类型的指针，dictEntry 类型里保存着一个键值对。
在这里也可以看出哈希表的节点是链表相连来解决哈希冲突问题的，也就是链地址法。
哈希冲突与哈希算法
为了实现从键到值的快速访问，Redis使用了哈希表来保存所有键值对。键对应Redis设置的Key，而值对应的并不是值本身，而是指向具体值的指针。使用哈希表的最大好处就是可以用O(1)的时间复杂度快速找到键值对。但既然是哈希表，那么必然会有着哈希冲突的问题。
哈希冲突即指的是，当两个key的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶上。
Redis解决哈希冲突的方式是使用链式哈希，即拉链法。当多个元素指向同一个哈希桶时，在同一个哈希桶中采用链表来保存对应的数据，它们之间依次用指针连接。
哈希算法
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
reHash 过程
在哈希表中有个负载因子（load factor）来控制哈希表保存的键值对数量。而这就需要rehash（重新散列）操作来完成。其中，负载因子的计算公式为：
// 负载因子 = 哈希表已保存的节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size
哈希表扩展与收缩的条件如下：
- 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于1；
- 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于5；
上述的条件有一个满足，就会执行rehash的过程。
如果服务器正在执行BGSAVE 或者 BGREWRITEAOF时，Redis会创建当前服务器进程的子进程
rehash的过程大概分为三步：
-
给哈希表2分配更大的空间，例如是当前哈希表1的两倍；
-
把哈希表1中的数据重新映射并拷贝到哈希表2中；
-
释放哈希表1的空间；
其中，第一步分配空间的大小是由当前的rehash操作类型 以及 当前哈希表的键值对数量决定的。
-
当执行的是扩展操作，分配的空间大小 为第一个大于等于（哈希表的键值对数量 * 2） 的2^n 值；
假设 当前的键值对数量为4，那么 4 * 2 = 8，因为8 刚好等于2^3，即刚好等于第一个等于2^n的值，所以扩展空间就为 8;
-
如果执行的是收缩操作，分配的空间大小 为第一个大于等于（哈希表的键值对数量 ） 的2^n 值；
渐进式reHash
当哈希表数量多时，如果一下子将数据都复制过去，那么就很有可能对服务器造成影响。所以Redis是分多次进行rehash的，也就是渐进式rehash。
简单来说就是在第二步操作时，Redis仍然正常处理客户端请求，每处理一个请求时，从哈希表1中的第一个索引位置开始，顺带着将这个索引位置上所有的entries元素拷贝到哈希表2中；等下一次请求时，再顺带拷贝下一个索引位置的entries。
这样就很巧妙地将一次性大量拷贝的开销，分摊到多次处理请求的过程中了，避免了耗时操作，保证了数据的快速访问。
rehash时期间的哈希表操作
在进行 渐进式rehash操作时，字典的删除、查找、更新等操作会在两个哈希表中执行。例如要在字典中查找一个键的话，会先去原表中进行查询，如果找不到就会去新表查询。
而字典的添加操作一律只会保存在新表中。
