本文介绍了“Redis中的字典分析、哈希算法和重散列原理”的相关知识。很多人在实际案例的操作中会遇到这样的困难。让边肖带领你学习如何处理这些情况。希望大家认真阅读，学点东西！
Redis中的字典被广泛用于实现Redis的各种功能，包括数据库和哈希键。
字典的底层实现为哈希表，每个字典有两个哈希表，一个用于正常使用，另一个用于重新散列扩展。
字典的结构定义
typedefstructdict{
//特定于类型的函数。
dictType * type
//私有数据
void * privdata
//哈希表，两个元素。
字典[2]
//重新散列时记录的索引下标，或者没有重新散列时记录的-1。
internathashidx；
} dict==当执行重新散列时，对于每个迁移的索引，重新散列的条目数据将为1；==
哈希表字典的结构定义为：
typedefstructdictht {
//哈希表数组
dictEntry * *表；
//哈希表大小。
unsignedlongsize
//哈希表大小掩码，用于计算索引值。
unsignedlongsizenask
//哈希表中现有节点的数量。
unsignedlonguesd
} dictht其中，table是一个数组，数组的每个元素都指向一个dictEntry类型的指针，键值对存储在dictEntry类型中。
这里还可以看到，哈希表的节点通过链表连接，解决哈希冲突问题，也就是链地址法。
哈希冲突与哈希算法
为了实现从键到值的快速访问，Redis使用哈希表保存所有键-值对。键对应Redis设置的Key，而值不对应值本身，而是指向具体值的指针.使用哈希表最大的好处是可以快速找到时间复杂度为O(1)的键值对。但是，既然是散列表，就必然会有哈希冲突.的问题
哈希冲突是指两个密钥的哈希值和哈希桶计算对应关系时，正好落在同一个哈希桶上。
Redis解决哈希冲突的方式是使用链式哈希，或者拉链法.当多个元素指向同一个哈希桶时，使用链表将对应的数据存储在同一个哈希桶中，并通过指针依次连接。
00-1010向字典中添加新的键值对时，程序需要先根据键值对计算哈希值和索引值，然后根据索引值将包含新键值对的哈希表节点放在哈希表数组的指定索引上。
00-1010哈希表中有一个负载因子来控制哈希表中存储的键值对的数量。这需要重新散列操作才能完成。其中，荷载系数的计算公式为：
//加载因子=哈希表中保存的节点数/哈希表的大小。
荷载系数=ht [0]的膨胀和收缩条件。已使用/ht [0]。大小散列表如下：
服务器目前未执行BGSAVE命令或BGREWRITEAOF命令，哈希表加载因子大于等于1；
目前服务器正在执行BGSAVE命令或BGREWRITEAOF命令，哈希表的加载因子大于等于5；
如果满足上述条件之一，将执行重新散列过程。
如果服务器正在执行BGSAVE或BGREWR。
ITEAOF时，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操作时，字典的删除、查找、更新等操作会在两个哈希表中执行。例如要在字典中查找一个键的话，会先去原表中进行查询，如果找不到就会去新表查询。
而字典的添加操作一律只会保存在新表中。
“分析Redis中的字典、哈希算法和ReHash原理”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/70314.html