哈希表结构如下所示：

其中 table 属性是个数组 ，其中数组元素保存一种 dictEntry 的结构 ， 这个结构完全类似与 HashMap 中的 Entry 类型 ， 这个结构存储一个 KV 键值对 。
同时 ， 为了解决 hash 碰撞的问题 ， dictEntry 存在一个 next 指针 ， 指向下一个dictEntry  ， 这样就形成dictEntry 的链表 。

现在 ， 我们回头对比 Java 中 HashMap ， 可以发现两者数据结构基本一致 。
只不过 HashMap 为了解决链表过长问题导致查询变慢 ， JDK1.8 时在链表元素过多时采用红黑树的数据结构 。
下面我们开始添加新元素 ， 了解这其中的原理 。
元素增加过程当我们往一个新字典中添加元素 ， 默认将会为字典中 ht[0
 哈希表分配空间 ， 默认情况下哈希表 table 数组大小为 4（DICT_HT_INITIAL_SIZE） 。
新添加元素的键值将会经过哈希算法 ， 确定哈希表数组的位置 ， 然后添加到相应的位置如图所示：

继续增加元素 ， 此时如果两个不同键经过哈希算法产生相同的哈希值 ， 这样就发生了哈希碰撞 。
假设现在我们哈希表中拥有是三个元素 ， ：

我们再增加一个新元素 ， 如果此时刚好在数组 3 号位置上发生碰撞 ， 此时 Redis 将会采用链表的方式解决哈希碰撞 。

注意 ， 新元素将会放在链表头结点 ， 这么做目的是因为新增加的元素 ， 很大概率上会被再次访问 ， 放在头结点增加访问速度 。
这里我们在对比一下元素添加过程 ， 可以发现 Redis 流程其实与 JDK 1.7 版本的 HashMap 类似 。
当我们元素增加越来越多时 ， 哈希碰撞情况将会越来越频繁 ， 这就会导致链表长度过长 ， 极端情况下 O(1) 查询效率退化成 O(N) 的查询效率 。
为此 ， 字典必须进行扩容 ， 这样就会使触发字典 rehash 操作 。
扩容当 Redis 进行 Rehash 扩容操作 ， 首先将会为字典没有用到 ht[1
 哈希表分配更大空间 。

画外音：ht[1
 哈希表大小为第一个大于等于 ht[0
.used*2 的 2^2(2的n 次方幂)

然后再将 ht[0
 中所有键值对都迁移到 ht[1
 中 。

当节点全部迁移完毕 ， 将会释放 ht[0
占用空间并将 ht[1
 设置为 ht[0
。

扩容 操作需要将 ht[0
所有键值对都 Rehash 到 ht[1
 中 ， 如果键值过多 ， 假设存在十亿个键值对 ， 这样一次性的迁移 ， 势必导致服务器会在一段时间内停止服务 。
另外如果每次 rehash 都会阻塞当前操作 ， 这样对于客户端处理非常不友好 。
为了避免 rehash对服务器的影响 ， Redis 采用渐进式的迁移方式 ， 慢慢将数据迁移分散到多个操作步骤 。
这个操作依赖字典中一个属性 rehashidx这是一个索引位置计数器 ， 记录下一个哈希表 table 数组上元素 ， 默认情况为值为 -1 。
假设此时扩容前字典如图所示：

当开始 rehash 操作 ， rehashidx将会被设置为 0  。
这个期间每次收到增加 ， 删除 ， 查找 ， 更新命令 ， 除了这些命令将会被执行以外 ， 还会顺带将 ht[0
哈希表在 rehashidx 位置的元素 rehash 到 ht[1
 中 。
假设此时收到一个 K3 键的查询操作 ， Redis 首先执行查询操作 ， 接着 Redis 将会为 

• 酷睿处理器|关键数据出炉，京东比阿里差远了
• CPU|阿里反贪第一人蒋芳，入职23年将7名高层送入狱，连马云都可以查
• 阿里巴巴|社区团购是互联网巨头的宝地，美团拼多多发展强劲，阿里坐不住了
• 阿里巴巴|被苹果无辜“踢出局”，引发央视点名，国产制造该何去何从？
• javascript|Web前端培训：什么是 MEAN Stack？
• 零售业|阿里再生独角兽，估值百亿美元，马云果然有远见
• MIUI|数字人民币APP正式上线，扯下了阿里的“遮羞布”
• javascript|奢侈品级别音响B&W加持，峰米向行业第一发起冲击？
• meta|阿里云到底有多强大？一起来盘点一下它骄人的战绩
• 阿里巴巴|一块桌面版3070显卡的价格，就够买一个3070笔记本，还能剩点