共计 2885 个字符，预计需要花费 8 分钟才能阅读完成。
最近，小黑哥的一个敌人进来面试，回来跟小黑哥埋怨，面试官不按套路出牌，间接打乱了他的节奏。
事件是这样的，后面面试问了几个 Java 的相干问题，我敌人答复还不错，接下来面试官就问了一句：看来 Java 根底还不错，Java HashMap 你相熟吧？
我敌人答复。工作常常用，有看过源码。
我敌人原本想着，你轻易来吧，这个问题之前曾经筹备好了，轻易问吧。
谁晓得，面试官上面一句：
那好的，咱们来聊聊 Redis 字典吧。
间接将他整蒙逼。
小黑哥的敌人因为没怎么钻研过 Redis 字典，所以这题就间接答复不晓得了。
当然，如果面试中真不知道，那就答复不理解，间接下一题，不要乱答。
不过这一题，小黑哥感觉还是很惋惜，其实 Redis 字典基本原理与 HashMap 差不多，那咱们其实能够套用这其中的原理，不求答复满分，然而怎么也能够得个及格分吧~
面试过程真要碰到这个问题，咱们能够从上面三个方面答复。
- 数据结构
- 元素减少过程
- 扩容
字典数据结构
说起字典，兴许大家比拟生疏，然而咱们都晓得 Redis 自身提供 KV 查问的形式，这个 KV 就是其实通过底层就是通过字典保留。
另外，Redis 反对多种数据类型，其中一种类型为 Hash 键，也能够用来存储 KV 数据。
小黑哥刚开始理解的这个数据结构的时候，原本认为这个就是应用字典实现。其实并不是这样的，初始创立 Hash 键，默认应用另外一种数据结构 -ZIPLIST(压缩列表)，以此节俭内存空间。
不过一旦以下任何条件被满足，Hash 键的数据结构将会变为字典，放慢查问速度。
- 哈希表中某个键或某个值的长度大于
server.hash_max_ziplist_value（默认值为64）。 - 压缩列表中的节点数量大于
server.hash_max_ziplist_entries（默认值为512）。
Redis 字典新建时默认将会创立一个哈希表数组，保留两个哈希表。
其中 ht[0] 哈希表在第一次往字典中增加键值时分配内存空间，而另一个 ht[1] 将会在下文中扩容 / 缩容才会进行空间调配。
字典中哈希表其实就等同于 Java HashMap，咱们晓得 Java 采纳数组加链表 / 红黑树的实现形式，其实哈希表也是应用相似的数据结构。
哈希表构造如下所示：
其中 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 将会为 ht[0]哈希表上 table 数组第 rehashidx 索引上所有节点都迁徙到 ht[1] 中。
当操作实现之后，再将 rehashidx 属性值加 1。
最初当所有键值对都 rehash 到 ht[1]中时，rehashidx将会被从新设置为 -1。
尽管渐进式的 rehash 操作缩小了工作量，然而却带来键值操作的复杂度。
这是因为在渐进式 rehash 操作期间，Redis 无奈明确晓得键到底在 ht[0]中，还是在 ht[1] 中, 所以这个时候 Redis 不得不查找两个哈希表。
以查找为例，Redis 首先查问 ht[0]，如果没找到将会持续查找 ht[1], 除了查问以外，更新，删除也会执行如上的操作。
增加操作其实就没这么麻烦，因为 ht[0] 不会在应用，那就对立都增加到 ht[1] 中就好了。
最初咱们再比照一下 Java HashMap 扩容操作，它是一个一次性操作，每次扩容须要将所有键值对都迁徙到新的数组中，所以如果数据量很大，耗费工夫就会久。
总结
Redis 字典应用哈希表作为底层实现，每个字典蕴含两个哈希表，一个平时应用，一个仅在 rehash 操作中应用。
哈希表总的来说，跟 Java HashMap 真的很相似，底层实现也是一个数组加链表数据结构。
最初，当对哈希表进行扩容操作工夫，将会采纳渐进性 rehash 操作，缓缓将所有键值对迁徙到新哈希表中。
其实理解 Redis 字典的其中的原理，再去比拟 Java HashMap，其实能够发现这两者有如此多的类似点。
所以学习这类常识时，不要仅仅去背，咱们要理解其底层原理，知其然知其所以然。
帮忙材料
- https://redisbook.readthedocs…
欢送关注我的公众号：程序通事，取得日常干货推送。如果您对我的专题内容感兴趣，也能够关注我的博客：studyidea.cn
