Redis教程

redis的字典扩容

本文主要是介绍redis的字典扩容,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

why:

  Redis的字典使用哈希表作为底层实现。
  在字典容量不足,或者使用率非常低的时候,需要做对应的扩容,或者缩容操作。

 

what:

  字典结构如下:

 

 

 

 

   具体代码:

 

 

 

 

 

 

 

 

  

  字典(dict)中:type属性和privdata属性是针对不同类型的键值对,而创建多态字典而设置的。
    type属性是一个指向dictType结构的指针,每个dictType结构保存了一组用于操作特定类型键值对的函数。Redis会为用途不同的字典设置不同类型的特定函数。
    privadata属性则保存了需要传给那些类型特定函数的可选参数。

    ht属性是一个包含了两个项的数组,数组中每个项都是一个dictht哈希表,一般情况下,字典只使用ht[0]哈希表,而ht[1]哈希表只对ht[0]哈希表进行rehash时使用。

 

how:

  扩/缩容大小:

    如果是扩容操作,ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂;

    如果是收缩操作,ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂;

 

  扩容过程:

    1、为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表,并将rehashindex的值设置为0,表示rehash工作正式开始;

    2、每次操作(增、删、改、查)外(由于两个哈希表的存在,需要在2个数据源上操作),还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1],当rehash工作完成以后,rehashindex的值+1;

    3、rehash结束,即:ht[0]数据全部到ht[1]。这时将rehashindex的值设置为-1;

 

  扩容步骤图:

    1、开始

   

 

     2、初始默认hash长度为4,当元素个数与hash表长度一致时,就发生扩容,hash长度变为原来的二倍

 

     3、开始rehash:每次的增删改查,rehashidx+1,然后执行对应原hash表rehashidx索引位置的rehash

 

 

diff:

  和java的hashmap区别:

    1、hashmap没有容量缩小的操作,而字典中如果当负载因子小于0.1的时候,会缩;

    2、字典中哈希冲突后采用的链地址法解决冲突,当链表过长的时候没有转化为红黑树;java中hashmap(jdk1.8)当链表长度超过8,而且数组长度超过64的时候会转为红黑树(可能:redis还是更看重内存空间的宝贵性,实现红黑树更耗费内存);

    3、redis 的字典实现rehash的时候采用的是渐进式rehash,也就是rehash这个动作不是一次性集中性完成的;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

这篇关于redis的字典扩容的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!