本文转载自微信公众号《Java极客技术》，作者鸭血范。转载本文请联系Java极客技术公众号。最近，阿芬的一个朋友出去面试，回来就向阿芬抱怨说，面试官不按套路出牌，直接打乱了他的节奏。事情是这样的。上次面试问了几个Java相关的问题。我朋友回答的很好。然后面试官问：看来Java基础还不错。你熟悉JavaHashMap吗？我的朋友回答。工作中经常用到，看过源码。朋友本来以为，你随便来吧，这个问题之前已经准备好了，随便问问就可以了。谁知，面试官的下一句：“好吧，我们来说说Redis字典。”他直接被逼了。阿芬朋友没怎么研究redis字典，所以不知道这个问题的答案。“当然，如果面试的时候真的不懂，那就不懂就回答，直接进入下一题，不要胡乱回答。”不过，阿芬觉得这个问题有点可惜。其实Redis字典的基本原理和HashMap是差不多的，所以我们其实可以套用这个的原理，也可以不用答满分，不过也能考个及格分~如果你真的面试过程中遇到这个问题，我们可以从以下三个方面来回答。数据结构元素添加过程扩展字典数据结构说到字典大家可能比较陌生，但是我们都知道Redis本身提供了KV查询方式。这个KV其实是通过底层或者通过字典来保存的。此外，Redis支持多种数据类型，其中一种就是Hashkey，也可以用来存储KV数据。阿芬刚开始了解这个数据结构的时候，我还以为是用字典实现的呢。事实上，情况并非如此。最初创建哈希键时，默认使用另一种数据结构——“ZIPLIST”（压缩列表）来节省内存空间。但是，一旦满足以下任一条件，Hashkey的数据结构就会变成字典，从而加快查询速度。哈希表中键或值的长度大于server.hash_max_ziplist_value（默认为64）。zip列表中的节点数大于server.hash_max_ziplist_entries（默认为512）。在创建Redis字典时，默认会创建一个哈希表数组，保存两个哈希表。其中，ht[0]哈希表是在key值第一次加入字典时分配内存空间，另外一个ht[1]只有在后面扩容/缩容后才会分配空间。字典中的哈希表其实就相当于Java的HashMap。我们知道Java采用数组加链表/红黑树的实现方式。事实上，哈希表也使用了类似的数据结构。哈希表结构如下：表属性是一个数组，数组元素存储一个dictEntry结构，与HashMap中的Entry类型完全相似，该结构存储一个KV键值对。同时为了解决hash冲突的问题，dictEntry中有一个next指针，指向下一个dictEntry，这样就形成了dictEntry的链表。现在回过头来对比Java中的HashMap，可以发现两者的数据结构基本相同。只不过HashMap为了解决链表过长的问题，拖慢了查询速度。在JDK1.8中，当链表元素过多时，使用红黑树的数据结构。让我们开始添加新元素并了解其工作原理。添加元素的过程当我们向一个新的字典中添加元素时，会默认为字典中的ht[0]哈希表分配空间。默认情况下，哈希表表数组的大小为4（“DICT_HT_INITIAL_SIZE”）。新添加的元素的key值会经过哈希算法确定哈希表数组的位置，然后添加到对应的位置，如图：继续添加元素，此时如果两个不同的键通过哈希算法产生相同的哈希值，从而发生哈希冲突。假设我们现在哈希表中有3个元素：我们新增一个元素，如果此时数组的位置3发生碰撞，Redis会使用链表来解决哈希碰撞。“注意，新元素会放在链表的头节点，这样做的目的是因为新加入的元素有很大概率会被再次访问，放在头节点会提高访问速度。”这里我们对比一下添加元素的过程，可以发现Redis的过程其实和JDK1.7版本的HashMap类似。当我们添加的元素越来越多时，hash碰撞会越来越频繁，从而导致链表的长度过长。在极端情况下，O(1)查询效率会降低到O(N)查询效率。为此，必须扩展字典，这将触发字典重新散列操作。扩容Redis在进行Rehash扩容操作时，会先为字典未使用的ht[1]哈希表分配更多的空间。?画外音：ht[1]哈希表大小是第一个2^2（2的n次方）大于等于ht[0].used*2?然后ht[0中的所有键值对]迁移到ht[1]。为简单起见，忽略指向空节点。当所有节点迁移完成后，ht[0]占用的空间会被释放，ht[1]会被置为ht[0]。扩展操作需要将ht[0]的所有键值对重新散列为ht[1]。中止服务。另外，如果每次rehash都会阻塞当前操作，对客户端处理是很不友好的。为了避免rehash对服务器的影响，Redis采用了渐进迁移的方式，将数据迁移慢慢分散到多个操作步骤中。这个操作依赖于字典中的一个属性rehashidx，它是一个索引位置计数器，记录了哈希表的表数组中的元素。默认值为“-1”。假设扩容前的字典如图所示：当rehash操作开始时，rehashidx会被设置为“0”。在此期间，每次收到add、delete、search、update命令，除了执行这些命令外，ht[0]哈希表的rehashidx位置的元素也会被rehash到ht[1]顺便一提。假设此时收到对“K3”键的查询操作，Redis首先执行查询操作，然后Redis会将ht[0]哈希表上表数组的rehashidx索引上的所有节点迁移到ht[1].操作完成后，将rehashidx属性的值加1。最后，当所有键值对都重新哈希到ht[1]时，rehashidx将被重置为-1。progressiverehash操作虽然减少了工作量，但是带来了key-value操作的复杂度。这是因为在progressiverehash操作的过程中，Redis并不能清楚的知道key是在ht[0]中还是在ht[1]中，所以此时Redis不得不去查找两个hash表。以搜索为例，Redis首先查询ht[0]，如果没有找到，会继续搜索ht[1]。除了查询，更新和删除也会执行上述操作。加法运算其实没有那么麻烦，因为ht[0]不会用到，所以全部加到ht[1]就可以了。最后再对比一下JavaHashMap的扩容操作。这是一次性手术。每次扩容都需要将所有的键值对迁移到一个新的数组中，所以如果数据量大的话，时间会比较长。总结Redis字典使用哈希表作为底层实现。每个字典包含两个哈希表，一个用于正常使用，一个仅用于重新哈希操作。总的来说，哈希表真的很像Java的HashMap，底层实现也是数组加链表的数据结构。最后，当哈希表扩容时，会采用渐进的rehash操作，将所有键值对慢慢迁移到新的哈希表中。其实理解了Redis字典的原理，再对比Java的HashMap，其实可以发现两者有这么多相似之处。所以在学习这类知识的时候，不要只是死记硬背，我们需要了解它背后的原理，知其然，知其所以然。帮助信息https://redisbook.readthedocs.io/en/latest/internal-datastruct/dict.html
