共计 3244 个字符，预计需要花费 9 分钟才能阅读完成。
前提常识🧀
字典，又被称为符号表（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 泡腾片，感觉能够略微缓缓。
疫情掰扯这么多，其实我和大家一样，我有想吃的美食，有想去的中央，更有马上想见到的人，所以最初还是心愿疫情可能连忙好起来~
