哈喽，大家好，我是了不起。
之前给大家介绍了Redis的基本数据结构，
后来听说了一个故事：
一个Java程序员去面试，前面面试问了几个 Java 的相关问题，回答还不错，接下来面试官就问了一句：看来 Java 基础还不错，Java HashMap 你熟悉吧？
回答：那家伙老熟了，工作经常用，有看过源码。红黑树链表都能给你整明白了！（心里默念：随便问吧，八股文和源码早都烂熟于心）
接着面试官说了这么一段话：
那好的，我们来聊聊 Redis 字典吧。
------------------------------------------
借着这个故事，我们聊一下Redis 字典，并对比Java中HashMap的一些异同。
1.前言
我们回顾一下之前讲到的Redis的字典结构，示意图如下：
图片
Redis的字典本质上来说也是数组+链表的数据结构，这与Java中HashMap的数据结构很类似。
由上述结构示意图也能看出，字典dict中维护了一个ht数组，而且只有两个元素，这两个元素是其扩容的关键点，这个我们后面会讲到。
Redis中的哈希对象在以下条件时，使用ziplist编码，
- 哈希对象保存的所有键值的字符串长度都小于64字节
- 哈希对象保存的键值对数量小于512个。
否则哈希对象会使用hashtable编码， 而hashtable则时使用了字典作为底层实现的。
如下redis 哈希对象编码由ziplist 变成hashtable
图片
2.增加元素与键冲突
当不同的键值经过哈希算法与散列算法之后被分配到了同一个哈希表数组的同一个索引上，那么这之后就会有键冲突。
Redis 哈希表解决哈希冲突同样是使用了链表地址法。使用哈希节点的next指针来链接同一个哈希表数组索引上的元素。不过Redis会将新添加的哈希节点加入到链表的表头位置。
如下所示：如果程序要将键值对 （k2 , v2 ） 添加到如下的哈希表中，而且计算的书的索引为1，那么和 （k1 v1） 将产生冲突。解决冲突时，会将两个节点使用next指针链接起来。而且会将新节点添加到链表表头的位置。
图片
哈希表1
图片
链表解决hash冲突之后的哈希表
3.rehash 扩容过程
哈希表不断的增加元素，其元素数量达到一定的比例之后，程序会对哈希表进行相应的扩展。通过执行rehash （重新散列）操作完成操作。其步骤如下：
- 执行扩展操作时会将字典中的ht[1] 哈希表大小设置成 第一个大于等于 ht[0] 的 ht[0].used * 2 的 2^n (2的n次幂)
- 将保存早ht[0] 中的所有的键值对 rehash到ht[1] 上， rehash过程中会重新计算哈希值和索引值。
- 当ht[0]中所有的键值对都迁移到ht[1]上时，释放ht[0], 并将ht[1] 设置成 ht[0]， 并在ht[1]上建一个空的哈希表。
将下图中的字典做rehash操作：
图片
图片
图片
图片
以上是一个rehash的过程示意。
4.渐进式rehash
上面讲的是一个rehash的理论过程，redis实际操作时并不会一次将所有的迁移一次性完成。
如果键值对数量非常庞大，那么迁移过程必然需要花费一点时间。由此可知，服务器也不可能一次将所有的键值对迁移，需要分多次，逐渐将ht[0] 里面的键值对迁移到ht[1]中，
其步骤如下：
- 首先会给ht[1]分配内存空间，此时redis字典拥有两个哈希表
- 字典中维护一个rehashidx的计数器，将其值设置为0，表示rehash工作开始
- 在rehash期间，程序依然可以进行增删改查的操作，除此之外还会顺带将ht[0]上 rehashidx索引上所有的键值对rehash到ht[1]上，rehash的工作完成后会将rehashidx的值加1
- 随着字典的操作，ht[0]上的所有键值全部都rehash到ht[1]上时，程序会将rehashidx的值设为-1 ，表示rehash操作已经完成
在渐进式rehash的过程中，redis字典依然是可以进行增删改查的操作， 其中增加元素的时候会将元素直接保存到ht[1]中， 而删除，查找，更新的操作会在两个哈希表中进行， 查找时会先在ht[0]中进行查找，然后会在ht[1]中进行查找。以上措施可以保证ht[0]中的元素只会减少，最终变成空表。
总结
Redis字典和Java中的HashMap的相似点和不同。
相似之处：
不同之处：
