HashMap 熟悉吧？好的，那就来聊聊 Redis 字典吧！

HashMap 熟悉吧？好的，那就来聊聊 Redis 字典吧！

最近，阿粉的一个朋友出去面试，回来跟阿粉抱怨，面试官不按套路出牌，直接打乱了他的节奏。

事情是这样的，前面面试问了几个 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 ，其实可以发现这两者有如此多的相似点。

所以学习这类知识时，不要仅仅去背，我们要了解其底层原理，知其然知其所以然。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。