分析Redis中的字典、哈希算法和ReHash原理

本篇内容介绍了“分析Redis中的字典、哈希算法和ReHash原理”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！Redis 中的字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。字典的底层实现为哈希表，每个字典带有两个哈希表，一个平时使用，另一个在进行rehash扩充空间时才使用。==在进行 rehash时，rehashidx每迁移一个索引的entry数据就会 + 1；==其中，哈希表dictht 的结构定义为：其中，table是一个数组，数组的每一个元素指向 dictEntry 类型的指针，dictEntry 类型里保存着一个键值对。在这里也可以看出哈希表的节点是链表相连来解决哈希冲突问题的，也就是链地址法。 为了实现从键到值的快速访问，Redis使用了哈希表来保存所有键值对。键对应Redis设置的Key，而值对应的并不是值本身，而是指向具体值的指针。使用哈希表的最大好处就是可以用O(1)的时间复杂度快速找到键值对。但既然是哈希表，那么必然会有着哈希冲突的问题。哈希冲突即指的是，当两个key的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶上。Redis解决哈希冲突的方式是使用链式哈希，即拉链法。当多个元素指向同一个哈希桶时，在同一个哈希桶中采用链表来保存对应的数据，它们之间依次用指针连接。当要将一个新的键值对添加到字典里面时，程序需要先根据键值对计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。 在哈希表中有个负载因子（load factor）来控制哈希表保存的键值对数量。而这就需要rehash（重新散列）操作来完成。其中，负载因子的计算公式为：哈希表扩展与收缩的条件如下：服务器目前没有在执行 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 值； 当哈希表数量多时，如果一下子将数据都复制过去，那么就很有可能对服务器造成影响。所以Redis是分多次进行rehash的，也就是渐进式rehash。 简单来说就是在第二步操作时，R免费主机域名edis仍然正常处理客户端请求，每处理一个请求时，从哈希表1中的第一个索引位置开始，顺带着将这个索引位置上所有的entries元素拷贝到哈希表2中；等下一次请求时，再顺带拷贝下一个索引位置的entries。 这样就很巧妙地将一次性大量拷贝的开销，分摊到多次处理请求的过程中了，避免了耗时操作，保证了数据的快速访问。 在进行 渐进式rehash操作时，字典的删除、查找、更新等操作会在两个哈希表中执行。例如要在字典中查找一个键的话，会先去原表中进行查询，如果找不到就会去新表查询。 而字典的添加操作一律只会保存在新表中。“分析Redis中的字典、哈希算法和ReHash原理”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注云技术网站，小编将为大家输出更多高质量的实用文章！

相关推荐: EBS AR模块常用表分析

本篇内容介绍了“EBS AR模块常用表分析”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！AR 模块常用表应收事务处理相关表SELECT * FROMar.ar_…