前提常识
字典，又被称为符号表（symbol table）或映射（map），其实简略地能够了解为键值对key-value。
比方Java的常见汇合类HashMap，就是用来存储键值对的。
字典中的键（key）都是惟一的，因为这个个性，咱们能够依据键（key）查找到对应的值（value），又或者进行更新和删除操作。
字典dict的实现
Redis的字典应用了哈希表作为底层实现，一个哈希表外面能够有多个哈希表节点，每个节点也保留了对应的键值对。
Redis的字典dict构造如下：
typedef struct dict { //类型特定函数 //是一个指向dictType构造的指针，能够使dict的key和value可能存储任何类型的数据 dictType *type; //公有数据 //公有数据指针，不是探讨的重点，暂疏忽 void *privdata; //哈希表 dictht ht[2]; //rehash 索引 //当 rehash 不在进行时，值为 -1 int rehashidx;}咱们重点关注两个属性就能够：
- ht 属性：
能够看到ht属性是一个 size为2 的 dictht哈希表数组，在平时状况下，字典只用到 ht[0]，ht[1] 只会在对 ht[0] 哈希表进行rehash时才会用到。
- rehashidx 属性：
它记录了rehash目前的进度，如果当初没有进行rehash，那么它的值为-1，能够了解为rehash状态的标识。
下图就是一个一般状态下的字典：
理论的数据在 ht[0] 中存储；ht[1] 起辅助作用，只会在进行rehash时应用，具体作用包含rehash的内容咱们会在前面进行具体介绍。
哈希算法定位索引
PS：如果你有HashMap的相干常识，晓得如何计算索引值，那么你能够跳过这一部分。
如果咱们当初模仿将 hash值从0到5的哈希表节点 放入 size为4的哈希表数组 中，也就是将蕴含键值对的哈希表节点放在哈希表数组的指定索引上。
对应索引的计算公式：
index = hash & ht[x].sizemask
看不懂没关系，能够简略的了解为hash值对哈希表数组的size值求余；
比方下面 hash值为0的节点，0 % 4 = 0，所以放在索引0的地位上，
hash值为1的节点，1 % 4 = 1，所以放在索引1的地位上，
hash值为5的节点，5 % 4 = 1，也等于1，也会被调配在索引1的地位上，并且因为dictEntry节点组成的链表没有指向链表表尾的指针，所以会将新节点增加在链表的表头地位，排在已有节点的后面。
咱们把下面索引雷同从而造成链表的状况叫键抵触，而且因为造成了链表！那么就意味着查找等操作的复杂度变高了！
例如你要查找hash=1的节点，你就只能先依据hash值找到索引为1的地位，而后找到hash=5的节点，再通过next指针能力找到最初的后果，也就意味着键抵触产生得越多，查找等操作破费的工夫也就更多。
如果解决键抵触？rehash！
其实rehash操作很好了解，能够简略地了解为哈希表数组扩容或膨胀操作，即将原数组的内容从新hash放在新的数组里。
比方还是下面的数据，咱们这次把它们放在 size等于8的哈希表数组 里。
如下图，此时size = 8，hash为5的键值对，从新计算索引：5 % 8 = 5，所以这次会放在索引5的地位上。
那么如果咱们还要找hash=1的节点，因为没有键抵触，天然也没有链表，咱们能够间接通过索引来找到对应节点。
能够看到，因为rehash操作数组扩容的缘故，键抵触的状况少了，进而咱们能够更高效地进行查找等操作。
触发rehash操作的条件
首先咱们先引入一个参数，叫做负载因子（load_factor），要留神的是：它与HashMap中的负载因子代表的含意不同；在HashMap里负载因子loadFactor作为一个默认值为0.75f的常量存在，而在redis的dict这里，它是一个会动态变化的参数，等于哈希表的 used属性值/size属性值，也就是 理论节点数/哈希表数组大小。如果一个size为4的哈希表有4个哈希节点，那么此时它的负载因子就是1；size为8的哈希表有4个哈希节点，那么此时它的负载因子就是0.5。
满足上面任一条件，程序就会对哈希表进行rehash操作：
扩容操作条件：
- 服务器目前没有执行 BGSAVE 或者 BGREWRITEAOF 命令，负载因子大于等于1。
- 服务器目前正在执行 BGSAVE 或者 BGREWRITEAOF 命令，负载因子大于等于5。
膨胀操作条件：
- 负载因子小于0.1时。
BGSAVE 和 BGREWRITEAOF 命令能够对立了解为redis的实现长久化的操作。
- BGSAVE 示意通过fork一个子过程，让其创立RDB文件，父过程持续解决命令申请。
- BGREWRITEAOF 相似，不过是进行AOF文件重写。
渐进式rehash？rehash的过程是怎么样的？
首先咱们晓得redis是单线程，并且对性能的要求很高，然而rehash操作如果碰到了数量多的状况，比方须要迁徙百万、千万的键值对，宏大的计算量可能会导致服务器在一段时间里挂掉！
为了防止rehash对服务器性能造成影响，redis会分屡次、渐进式地进行rehash，即渐进式rehash。
（能够了解粗略地了解为程序有闲暇再来进行rehash操作，不影响其余命令的失常执行）
对哈希表进行渐进式rehash的步骤如下：
首先为 ht[1] 哈希表调配空间，size的大小取决于要执行的操作，以及 ht[0] 以后的节点数量（即ht[0]的used属性值）：
- 扩大操作，ht[1]的size值为第一个大于等于ht[0].used属性值乘以2的 2^n
- 膨胀操作，ht[1]的size值为第一个小于ht[0].used属性值的 2^n
（有没有很相熟，其实跟Java中的HashMap、ConcurrentHashMap操作相似）
- 将哈希表的rehashidx值从-1置为0，示意rehash工作开始。
- 节点转移，从新计算键的hash值和索引值，再将节点搁置到ht[1]哈希表的对应索引地位上。
- 每次rehash工作实现后，程序会将rehashidx值加一。
（这里的每次rehash就指渐进式rehash）
- 当ht[0]的所有节点都转移到ht[1]之后，开释ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白的hash表，期待下次rehash再用到。（其实就是数据转移到ht[1]后，再复原为 ht[0]贮存理论数据，ht[1]为空白表的状态）
- 最初程序会将rehashidx的值重置为-1，代表rehash操作已完结。
进行渐进式rehash的时候会影响字典的其余操作吗？
因为在进行渐进式rehash的时候，字典会同时用到ht[0]和ht[1]这两个哈希表，所以在这期间，字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表进行；而进行增加操作时，会直接插入到ht[1]。
比方查找一个键时，程序会先在ht[0]外面查找，没找到的话再去ht[1]里进行查找。
搜材料的时候还看到好多评论，都对逻辑产生了疑难，还举了例子说有问题，但我认真看了下，其实都是疏忽了删除和更新都会在两个哈希表进行的前提条件。
写在最初的最初
我是苏易困，大家也能够叫我易困，一名Java开发界的小学生，文章可能不是很优质，但肯定会很用心。
间隔上次更新都过来了良久，一是因为上海的疫情有点重大，始终没静下心来好好整顿常识，还有就是发现自己得先很好地消化完常识才可能整理出来，不然其实各方面播种不大；所以前面也会本人先认真消化后再整顿分享，不会谋求速度，但会认真总结整顿。
因为疫情要始终封到4月1号，咱们小区还有1例阳性，更不晓得到什么时候了，每天早上也要定闹钟抢菜，但还抢不到，因为没有绿叶菜的补给，我感觉曾经得口腔溃疡了，还好买到了维C泡腾片，感觉能够略微缓缓。
疫情掰扯这么多，其实我和大家一样，我有想吃的美食，有想去的中央，更有马上想见到的人，所以最初还是心愿疫情可能连忙好起来~