我们之前讲的Redis对象Hash这些是一种数据类型，而今天这个学习笔记hashtable是这些类型的具体底层实现。注意要辨别。
那么第一个问题，什么是HASHTABLE?
HASHTABLE，可以想象成目录，要翻看什么内容，直接通过目录能找到页数，翻过去看。如果没有目录，我们需要一页一页往后翻，效率很低。在计算机世界里，HASHTABLE就扮演着这样一个快速索引的角色，通过HASHTABLE我们可以只用O(1)时间复杂度就能快速找到key对应的value。
接着我们看第二个问题，即HASHTABLE的结构
/* This is our hash table structure. */ typedef struct dictt { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictt;最外层是一个封装的dictht结构，具体的字段含义如下:
- table:指向实际hash存储。存储可以看做一个数组，所以是*table的表示，石C语言中*table可以表示一个数组。
- size:哈希表大小。实际就是dictEntry有多少元素空间。size是桶数，不包含链表上的节点
- sizemask: 哈希表大小的掩码表示，总是等于size-1。这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面，规则Index=hash&sizemask。
- used:表示已有节点数量。通过这个字段可以很方便地查询到目前HASHTABLE元素总量。
由上述的定义我们可以知道，used的数量可能大于size
进入第三个知识点，Hash表渐进式扩容:
渐进式扩容顾名思义就是一点一点慢慢扩容，而不是一股脑直接做完，那具体流程是怎样的呢?其实为了实现渐进式扩容，Redis中没有直接把dictht暴露给上层，而是再封装了一层:
可以看到dict结构里面，包含了两个dictht结构，也就是2个HASHTABLE结构。dictEntry是链表结构，也就是用拉链法解决Hash冲突，用的是头插法。
实际上平常使用的就是一个HASHTABLE，在触发扩容之后，就会两个HASHTABLE同时使用，详细过程是这样的:当向字典添加元素时，发现需要扩容就会进行Rehash。Rehash的流程大概分成三步:
首先，为新Hash表ht[1]分配空间。新表大小为第一个大于等于原表2倍used的2次方幂。举个例子，原表如果used=500，2倍就是1000，那第一个大于1000的2次方幂则为1024。此时字典同时持有ht[0]和ht[1]两个哈希表。字典的偏移索引rehashidx从静默状态-1，设置为0，表示Rehash工作正式开始。
我们来观察一下rehashidx在途中状态的变化:
初始状态：
在开始 rehash 之前，
rehashindex被设置为 -1，表示没有进行 rehash。当需要开始 rehash 时，
rehashindex被设置为 0，第一个桶（索引为0）开始移。
迁移过程：
每次执行增、删、查、改等操作时，Redis 会顺带迁移
rehashindex所指向的桶中的所有键值对到新的哈希表。迁移完一个桶后，
rehashindex会加1，指向下一个桶。这样，每次操作只迁移一个桶，避免了集中迁移导致的长时间阻塞。
完成迁移：
当
rehashindex递增到超过旧哈希表的大小（size）时，表示所有桶都已经迁移完毕。此时，rehash 完成，旧哈希表被释放，新哈希表替换旧哈希表，
rehashindex被重置为 -1。
关于空桶的处理：
在迁移过程中，如果当前
rehashindex指向的桶是空的，那么 Redis 会跳过这个桶，并将rehashindex加1，继续检查下一个桶。这样可以确保迁移过程不会因为遇到空桶而停滞，直到所有非空桶都被迁移。
随着字典操作的不断执行，最后会在某个时间点ht[0]的所有键值对被rehash至ht[1],此时h[1]会替代h[0]，然后rehashidx被设置为-1代表扩容结束
| 停止时机 | 触发条件 | rehashidx值 | ht[0].used |
|---|---|---|---|
| 正常完成 | 所有键已迁移 | < size | = 0 |
| 提前完成 | 中途used=0 | < size | = 0 |
| 空桶限制 | 遇到太多空桶 | < size | > 0 |
| 遍历完成 | 达到size边界 | = size | 应该=0 |
总结一下，渐进式扩容的核心就是操作时顺带迁移。
讲了扩容是怎么实现的，肯定大家会想着，我们啥时候会进行扩容呢?这就是我们最后一个学习的问题，扩容与缩容时机是什么时候?
Redis提出了一个负载因子的概念，负载因子表示目前RedisHASHTABLE的负载情况，是游刃有余，还是不堪重负了。我们设负载因子为k，那么k=ht[0].used/ht[0].size，也就是使用空间和总空间大小的比例。Redis会根据负载因子的情况来扩容:
- 负载因子大于等于1，说明此时空间已经非常紧张。新数据是在链表上叠加的，越来越多的数据其实无法在0(1)时间复杂度找到，还需要遍历一次链表，如果此时服务器没有执行BGSAVE或BGREWRITEAOF这两个命令，就会发生扩容。
- 负载因子大于5，这时候说明HASHTABLE真的已经不堪重负了，此时即使是有复制命令在进行，也要进行Rehash扩容。
Redis的扩容策略基于负载因子和写时复制机制的权衡：当负载因子≥1时，哈希表性能开始下降，本应触发扩容，但如果此时正在执行BGSAVE或BGREWRITEAOF（会fork子进程并使用写时复制技术），扩容将导致内存页被大量修改，使内存占用量短时间内近翻倍增长，因此Redis选择暂不扩容以优先保证内存稳定；而当负载因子≥5时，哈希表性能已严重恶化，即便有子进程运行，Redis也会强制扩容，因为此时性能损失已远超内存增长的成本。
扩容是数据太多存不下了，那如果太富裕呢，比如原来可能数据较多，发生了扩容，但后面数据不再需要，被删除了，此时多余的空间就是一种浪费。缩容过程其实和扩容是相似的，也是渐进式缩容，这里不赘述。同样的，Redis还是用负载因子来控制什么时候缩容:当负载因子小于0.1，即负载率小于10%，此时进行缩容，新表大小为第一个大于等于原表used的2次方幂。当然，如果有BGSAVE或BGREWRITEAOF这两个复制命令，缩容也会受影响，不会进行。
声明: 本篇笔记仅为学习时整理的笔记以及疑问解决点，无其他任何商业用途，如有侵权联系即删。
