浅谈Redis中的字典、哈希算法和ReHash原理

本篇文章带大家了解一下redis中的字典、哈希算法和rehash原理，希望对大家有所帮助！

Redis 中的字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。

字典的底层实现为哈希表，每个字典带有两个哈希表，一个平时使用，另一个在进行rehash扩充空间时才使用。【相关推荐：Redis视频教程】

字典的结构定义

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操作时，字典的删除、查找、更新等操作会在两个哈希表中执行。例如要在字典中查找一个键的话，会先去原表中进行查询，如果找不到就会去新表查询。

        而字典的添加操作一律只会保存在新表中。

更多编程相关知识，请访问：编程入门！！