1. 哈希表结构
Redis 哈希表就是类似 Java 中 HashMap。
哈希表是由 dictht 结构体定义，table 是一个数组，数组中每个元素是一个指向 dictEntry 结构的指针。 
dictEntry 是哈希表的节点，每个节点保存着一个键值对 key、value，value 可以是一个指针、或者是一个 unit64_t 或 int64_t 整数。
next 属性则是一个指向另一个哈希表节点的指针，形成一个链表，主要也是为了解决哈希冲突问题。比如下图（一个空的哈希表）：
索引值相同的两个节点使用链表连接起来：
2. 字典数据结构
提到哈希表的话顺便了解以下字典数据结构，毕竟它的底层就是哈希表实现的。字典定义如下：
type：指向 dictType 指针，保存了操作特定类型键值对的函数，Redis 为不同用途的字典设置不同的类型特定函数。
privdata：保存了需要传递给不同特定函数的可选参数。
ht[2]：两个哈希表，字典使用的哈希表是 ht[0]，ht[1] 则是当对 ht[0] 哈希表进行 rehash 时使用。
trehashidx：记录当前 rehash 进度，没有进行 rehash 则为 -1。
普通状态下的字典：
3. 解决哈希冲突
将一个键值对添加到字典时，需要计算其哈希值和索引值，接着根据索引值将新节点放到哈希表数组的指定索引上。
计算哈希值：
1 | hash = dict->type->hashFunction(key) |
计算索引值：
1 | hash & dict->ht[x].sizemask |
键冲突：当两个或以上数量的键进行哈希之后索引值一样，也就是说两个节点要放在同一个同桶里，这时可能就会存在覆盖(冲突)，那么就得解决这种冲突了。
Redis解决键冲突的方法：链地址法(separate chaining)——拉链法，假设你已了解 Java HashMap 原理，这里链地址法原理就不细说了。
解决哈希冲突有哪些方法？
- 再哈希法
- 链地址法
- 开放地址法
- 建立公共溢出区
4. 扩容/缩容
为什么要进行扩容或缩容？
扩容原因：当 hashtable 存储的元素过多，可能由于碰撞也过多，导致其中某链表很长，最后致使查找和插入时间复杂度很大。因此当元素超多一定的时候就需要扩容。
缩容原因：当元素数量比较少的时候就需要缩容以节约不必要的内存。为了让哈希表的负载因子（load factor）维持在一个合理的范围内，会使用 rehash（重新散列）操作对哈希表进行相应的扩展或收缩。负载因子的计算公式：哈希表已保存节点数量 / 哈希表大小load_factor = ht[0].used / ht[0].size
扩容条件（满足任意一个即可）:
Redis 服务器目前没有在执行 BGSAVE 或 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1。
Redis服务器目前在执行 BGSAVE 或 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5。
为什么 BGSAVE 或 BGREWRITEAOF 命令是否在执行，Redis 服务器哈希表执行扩容所需的负载因子不相同（1或5）？
- BGSAVE：用于在后台异步保存当前数据库的数据到磁盘。
- BGREWRITEAOF：用于异步执行一个 AOF（ Append Only File ） 文件重写操作。
因为当执行 BGSAVE 或 BGREWRITEAOF 命令过程中，Redis 需要创建服务器进程的子进程，操作系统采用的是 COW，即写时复制 copy-on-write 的技术来优化子进程的使用效率。所以在子进程存在时，服务器会提高执行扩容所需的负载因子，从而尽可能避免在子进程存在期间进行扩容，可以避免不必要的内存写入操作，最大限度节约内存。
缩容的条件：哈希表的负载因子小于0.1。
5. rehash
对字典的哈希表 rehash 步骤：
- 为 ht[1] 分配空间：扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0] .used*2 的 2 的 n 次幂；收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2 的 n 次幂。
- 将 ht[0] 中的数据转移到 ht[1] 中，在转移的过程中，重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 的指定位置。
- 当 ht[0] 的所有键值对都迁移到了 ht[1] 之后（ht[0] 变为空表），将 ht[0] 释放，然后将 ht[1] 设置成 ht[0]，最后为 ht[1] 分配一个空白哈希表。
开始哈希前：
为 ht[1] 分配空间，ht[0].used 当前值为 4，8 恰好是第一个大于等于 4 的 2 的 N 次幂，那么当前就会将 ht[1] 哈希表大小设置为 8。
将 ht[0] 的键值对都 rehash 到 ht[1]：
释放 ht[0]，将 ht[1] 设置为 ht[0]，ht[1] 再设置为空的哈希表：
6. 渐进式 rehash
在元素数量较少时，rehash 会非常快的进行，但是当元素数量达到几百万、甚至几个亿时进行 rehash 将会是一个非常耗时的操作。如果一次性将成万上亿的元素的键值对 rehash 到 ht[1]，庞大的计算量可能会导致服务器在一段时间内停止服务，这是非常危险的！所以，rehash 这个动作不能一次性、集中式的完成，而是分多次、渐进式地完成。
渐进式 rehash 步骤：
- 为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
- 在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为 0，表示 rehash 工作正式开始。
- 在 rehash 进行期间，每次对字典执行 CRUD：添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成之后，程序将 rehashidx + 1(表示下次将 rehash 下一个桶)。
- 随着字典操作的不断执行，最终在某个时间点上，ht[0] 的所有键值对都会被 rehash 至 ht[1]，这时程序将 rehashidx 属性的值设为 -1，表示 rehash 完成。
渐进式 rehash 的好处：在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。
准备进行渐进式 rehash：
此时 rehashidx = 0，也就是会将索引为 0 的键值对进行迁移：
接着，rehashidx 继续递增，假如到最后将索引 3 的进行迁移：
渐进式 rehash 结束：
在迁移过程中，会不会造成读少数据？
不会，因为在迁移时，首先会从 ht[0] 读取数据，如果 ht[0] 读不到，则会去 ht[1] 读。
在迁移过程中，新增加的数据会存放在哪个 ht？
迁移过程中，新增的数据只会存在 ht[1] 中，而不会存放到 ht[0]，ht[0] 只会减少不会新增。