本博客微信公共账号：hadoop123（微信号为：hadoop-123），分享hadoop技术内幕，hadoop最新技术进展，发布hadoop相关职位和求职信息，hadoop技术交流聚会、讲座以及会议等。二维码如下：

Redis是个key/value存储系统，学过数据结构的人都知道，key/value最简单的数据结果就是哈希表（当然，还有其他方式，如B-树，二叉平衡树等），hash表的性能取决于两个因素：hash表的大小和解决冲突的方法。这两个是矛盾的：hash表大，则冲突少，但是用内存过大；而hash表小，则内存使用少，但冲突多，性能低。一个好的hash表会权衡这两个因素，使内存使用量和性能均尽可能低。在Redis中，哈希表是所有其他数据结构的基础，对于其他所有数据结构，如：string，set，sortedset，均是保存到hash表中的value中的，这个可以很容易的通过设置value的类型为void*做到。本文详细介绍了Redis中hash表的设计思想和实现方法。

【注】 本文的源代码分析是基于redis-2.4.3版本的。

下图是从淘宝中摘得的图片，主要描述Redis中hash表的组织方式。

在Redis中，hash表被称为字典（dictionary），采用了典型的链式解决冲突方法，即：当有多个key/value的key的映射值（每对key/value保存之前，会先通过类似HASH(key) MOD N的方法计算一个值，以便确定其对应的hash table的位置）相同时，会将这些value以单链表的形式保存；同时为了控制哈希表所占内存大小，redis采用了双哈希表(ht[2])结构，并逐步扩大哈希表容量（桶的大小）的策略，即：刚开始，哈希表ht[0]的桶大小为4，哈希表ht[1]的桶大小为0，待冲突严重（redis有一定的判断条件）后，ht[1]中桶的大小增为ht[0]的两倍，并逐步(注意这个词：”逐步”)将哈希表ht[0]中元素迁移（称为“再次Hash”）到ht[1]，待ht[0]中所有元素全部迁移到ht[1]后，再将ht[1]交给ht[0]（这里仅仅是C语言地址交换），之后重复上面的过程。

Redis哈希表的实现位于文件dict.h和dict.c中，主要数据结构如下：

//hash表结构，含有两个hash表，以实现增量再hash算法。
 

//hash表中每一项key/value，若key的映射值，以单链表的形式保存
 

//每种hash table的类型，里面既有成员函数，又有成员变量，完全是模拟的C++类，注意，每个函数带有的privdata均为预留参数
 

 

 当第一个表的元素数目大于桶数目且元素数目与桶数目比值大于5时，hash 表就会扩张，扩大后新表的大小为旧表的2倍。
 
 

 
 

 为了避免一次性转移带来的开销，Redis采用了平摊开销的策略，即：将转移代价平摊到每个基本操作中，如：dictAdd、dictReplace、dictFind中，每执行一次这些基本操作会触发一个桶中元素的迁移操作。在此，有读者可能会问，如果这样的话，如果旧hash
 table非常大，什么时候才能迁移完。为了提高前移速度，Redis有一个周期性任务serverCron，每隔一段时间会迁移100个桶。
 
 

 

 下面分析一下dictAdd函数：
 
 

 首先，检查hash table是否正在rehash操作，如果是，则分摊一个rehash开销：
 
 

 然后，检查该key/value的key是否已经存在，如果存在，则直接返回：
 
 

 需要注意的是，决定是否需要进行rehash是在查找操作（_dictKeyIndex）中顺便做的：
 
 

 

 接着，会通过hash算法定位该key的位置，并创建一个dictEntry节点，插入到对应单链表中：
 
 

 

 这就是整个dictAdd函数的流程。其他操作类似，均是刚开始分摊rehash开销（如果需要），然后通过hash方法定位位置，并进行相应的逻辑操作。
 
 

 
 

 

注意：我们今天所有的一切都是基于 JDK 8，JDK 8 的实现和 JDK 7 有重大区别。

前面我们分析了 hashCode 和 hash 算法的原理，其实都是为我们解析 HashMap 做铺垫，因为 HashMap 确实比较复杂（如果你每一行代码都看的话，每个位移都纠结的话），虽然总的来说，HashMap 不过是 Node 数组加 链表和红黑树。但是里面的细节确是无比的优雅和有趣。楼主为什么选择 put 方法来讲呢？因为从楼主看来，HashMap 的精髓就在 put 方法中。

HashMap 的解析从楼主来看，主要可以分为几个部分：

1. hash 算法（这个我们之前说过了，今天就不再赘述了）
2. 通过 hash 计算下标并检查 hash 是否冲突，也就是对应的下标是否已存在元素。
3. 通过判断是否含有元素，决定是否创建还是追加链表或树。
4. 判断已有元素的类型，决定是追加树还是追加链表。
5. 判断是否超过阀值，如果超过，则重新散列数组。
6. Java 8 重新散列时是如何优化的。

首先我们来一个测试例子：

一个简单的不能再简单的使用 HashMap 的例子，其中包含了对于 HashMap 来说关键的 3 个步骤，初始化，put 元素，get 元素。

由于我们预计会放入一个元素，出于性能考虑，我们将容量设置为 2，既保证了性能，也节约了空间（置于为什么，我们在之前的文章中讲过）。

那么我们就看看 new 操作的时候做了些什么事情：

上面是 HashMap 的两个构造方法，其中，我们设置了初始容量为 2， 而默认的加载因子我们之前说过：0.75，当然也可以自己设置，但 0.75 是最均衡的设置，没有特殊要求不要修改该值，加载因子过小，理论上能减少 hash 冲突，加载因子过大可以节约空间，减少 HashMap 中最耗性能的操作：reHash。

从代码中我可以看到，如果我们设置的初始化容量小于 0，将会抛出异常，如果加载因子小于 0 也会抛出异常。同时，如果初始容量大于最大容量，则重新设置为最大容量。

我们开最后两行代码，首先，对负载因子进行赋值，这个没什么可说的。
牛逼的是下面一行代码：this.threshold = tableSizeFor(initialCapacity); 可以看的出来这个动作是计算阀值，上面是阀值呢？阀值就是，如果容器中的元素大于阀值了，就需要进行扩容，那么这里的这行代码，就是根据初始容量进行阀值的计算。

我们进入到该方法查看：

一通或运算和无符号右移运算，那么这个运算的的最后结果是什么呢？这里其实就是如果用户输入的值不是 2 的幂次方（我们通过之前的分析，应该直到初始容量如果不是 2 的幂次方会有多么不好的结果）。通过位移运算和或运算，最后得到一定是 2 的幂次方，并且是那个离那个数最近的数字，我们仔细看看该方法：

| : 或运算，第一个操作数的的第 n 位于第二个操作数的第 n 位 只要有一个是 1，那么结果的第 n 为也为 1，否则为 0

首先，将容量减 1，我们后面就知道了。然后将该数字无符号右移 1，2，4，8，16，总共移了 32 位，刚好是一个 int 类型的长度。在移动的过程中，还对该数字进行或运算，为了方便查看，楼主写一下 2 进制的运算过程，假如我输入的是 10，明显不是 2 的幂次方。我们看看会怎么样：

最后，1111 也就是 15 ，15 + 1 = 16，刚好就是距离 10 最近的并且没有变小的 2 的幂次方数。可以说这个算法非常的牛逼。楼主五体投地。

但是如果是 16 呢，并且没有不减一，我们看看什么结果：

最后的数字就是 31 ，31+ 1 = 32，同样也是上升到了更大的 2 次幂的数字。但是这不是我想要的结果，所以，JDK 的作者在之前先减去了 1. 防止出现这样的问题。

我们仔细观察其算法的过程，可以说，任何一个 int 数字，都能找到离他最近的 2 的幂次方数字（并且比他大）。

好了。到这里就完成了初始化，不过请注意，这里设置的阀值并不是最终的阀值，最终的阀值我们会在后面详细说明。这里我们更加关注这个算法。真的牛逼啊。

2. 通过 hash 计算下标并检查 hash 是否冲突，也就是对应的下标是否已存在元素。

初始化好了 HashMap，我们接着就调用了 put 方法，该方法如下：

其中调用 hash 方法，该方法我们之前已经深入讨论过，今天就不赘述了，如果有同学没有看过，也不要紧，看完这篇 再去看 或者 看完那篇 再来 看这篇都可以。有点绕。好，然后调用了 puVal 方法，我们看看该方法：

该方法可以说是 HashMap 的核心方法，楼主已经在该方法中写满了注释。楼主说一下该方法的步骤：

1. 判断数组是否为空，如果是空，则创建默认长度位 16 的数组。
2. 通过与运算计算对应 hash 值的下标，如果对应下标的位置没有元素，则直接创建一个。
3. 如果有元素，说明 hash 冲突了，则再次进行 3 种判断。
   1. 判断两个冲突的 key 是否相等，equals 方法的价值在这里体现了。如果相等，则将已经存在的值赋给变量 e。最后更新 e 的 value，也就是替换操作。
   2. 如果 key 不相等，则判断是否是红黑树类型，如果是红黑树，则交给红黑树追加此元素。
   3. 如果 key 既不相等，也不是红黑树，则是链表，那么就遍历链表中的每一个 key 和给定的 key 是否相等。如果，链表的长度大于等于 8 了，则将链表改为红黑树，这是 Java8 的一个新的优化。
4. 最后，如果这三个判断返回的 e 不为 null，则说明 key 重复，则更新 key 对应的 value 的值。
5. 对维护着迭代器的 modCount 变量加一。
6. 最后判断，如果当前数组的长度已经大于阀值了。则重新 hash。

3. 通过判断是否含有元素，决定是否创建还是追加链表或树。

首先判断是否含有元素，通过什么判断呢？

这个算式根据 hash 值获取对应的下标，具体是什么原理，我们在上一篇文章已经说了原因。这里也不在赘述了。如果 hash 值没有冲突，则创建一个 Node 对象，参数是 hash 值，key，value，还有为 null 的 next 属性。下面是构造函数。

如果没有冲突，后面紧接着就走 ++modCount，然后，判断容量是否大于阀值（默认是 12）。如果大于，则调用 resize 方法，重新散列。resize 方法我们后面详细分析。

4. 判断已有元素的类型，决定是追加树还是追加链表。

如果 hash 冲突了怎么办？我们刚刚说会有 3 种判断：

1. 判断两个冲突的 key 是否相等，equals 方法的价值在这里体现了。如果相等，则将已经存在的值赋给变量 e。最后更新 e 的 value，也就是替换操作。
2. 如果 key 不相等，则判断是否是红黑树类型，如果是红黑树，则交给红黑树追加此元素。
3. 如果 key 既不相等，也不是红黑树，则是链表，那么就遍历链表中的每一个 key 和给定的 key 是否相等。如果，链表的长度大于等于 8 了，则将链表改为红黑树，这是 Java8 的一个新的优化。

注意：在链表的循环中，有一个方法 treeifyBin，这个方法在链表长度大于等于 8 的时候会调用，那么该方法的内容是什么呢？

该方法虽然主要功能是替换链表结构为红黑树，但是在替换前，会先判断，如果数组是 null 或者数组的长度小于 64，则重新散列，因为重新散列会拆分链表，使得链表的长度变短。提高性能。如果长度大于 64 了。就只能将链表变为红黑树了。

5. 判断是否超过阀值，如果超过，则重新散列数组。

最后，判断是否阀值，如果超过则进行散列；

我们知道，阀值默认是 16，那么 resize 方法就是重新散列的核心方法，我们看看该方法实现：

该方法可以说还是比较复杂的。初始的时候也是调用的这个方法，当链表数超过 8 的时候同时数组长度小于 64 的时候也是调用的这个方法。该方法步骤如下：

1. 判断容量是否大于 0，如果大于 0，并且容量已将大于最大值，则设置阀值为 int 最大值，并返回，如果老的容量乘以 2 小于最大容量，且老的容量大于等于 16，则更新阀值。也就是乘以 2.
2. 如果老的阀值大于 0，则新的容量等于老的阀值。注意：这里很重要。还记的我们之前使用 new 操作符的时候，会设置阀值为 2 的幂次方，那么这里就用上了那个计算出来的数字，也就是说，就算我们设置的不是 2 的幂次方，HashMap 也会自动将你的容量设置为 2 的幂次方。
3. 如果老的阀值和容量都不大于 0，则认为是一个新的数组，默认初始容量为 16，阀值为 16 * 0.75f，也就是 12。
4. 如果，新的阀值还是 0，那么就使用我们刚刚设置的容量（HashMap 帮我们算的），通过乘以 0.75，得到一个阀值，然后判断算出的阀值是否合法：如果容量小于最大容量并且阀值小于最大容量，那么则使用该阀值，否则使用 int 最大值。
5. 将刚刚的阀值设置打当前 Map 实例的阀值属性中。
6. 将刚刚的数组设置到当前 Map 实例的数组属性中。
7. 如果老的数组不是 null，则将老数组中的值重新散列到新数组中。如果是 null，直接返回新数组。

那么，将老鼠组重新散列的过程到底是怎么样的呢？

6. Java 8 重新散列时是如何优化的。

这里楼主重新贴了上面的代码，因为这段代码比较重要。还是说一下该部分代码的步骤。

1. 首先循环老数组。下标从 0 开始，如果对应下标的值不是 null，则判断该值有没有 next 节点，也就是判断是否是链表。
2. 如果不是链表，则根据新的数组长度重新 hash 该元素。
3. 如果该节点是树，则调用红黑树的 split 方法，传入当前对象和新数组还有下标，该方法会重新计算红黑树中的每个 hash 值，如果重新计算后，树中元素的 hash 值不同，则重新散列到不同的下标中。达到拆分红黑树的目的，提高性能。具体如何拆分下面再说。
4. 之后的判断就是链表，在 Java8 中，该部分代码不是简单的将旧链表中的数据拷贝到新数组中的链表就完了，而是会对旧的链表进行重新 hash，如果 hash 得到的值和之前不同，则会从旧的链表中拆出，放到另一个下标中去，提高性能，刚刚的红黑树也是这么做的。

这里的重新 hash 不是使用的 [e.hash & (newCap - 1)] 方法，而是使用更加效率的方法，直接 hash 老的数组容量，就没有了减一的操作，可见 JDK 的作者为了性能可以说是无所不用其极了。

其实我们的注释已经写了，但是楼主还是再解释一遍吧：

oldCap 假如是 16，那么二进制为 10000，扩容变成 100000，也就是 32. 当旧的 hash 值 与运算 10000，结果是 0 的话，那么 hash 值的右起第五位肯定也是 0，那么该于元素的下标位置也就不变。但如果不是 0 是 1 的话，说明该 hash 值变化了，那么就需要对这个元素重新散列放置。那么应该放哪里呢？如果是 16，那么最左边是 1 的话，说明 hash 值变大了 16，那么只需要在原有的基础上加上 16 便好了。

这段代码还有一个需要注意的地方：在 JDK 7 中，这里的的代码是不同的，在并发情况下会链表会变成环状，形成死锁。而 JDK 8 已经修复了该问题，但是仍然不建议使用 HashMap 并发编程。

截至到这里，我们的 HashMap 的 put 方法已经剖析完了，此次可以说收获不小：

我们知道了，无论我们如何设置初始容量，HashMap 都会将我们改成 2 的幂次方，也就是说，HashMap 的容量百分之百是 2 的幂次方，因为 HashMap 太依赖他了。但是，请注意：如果我们预计插入 7 条数据，那么我们写入 7，HashMap 会设置为 8，虽然是 2 的幂次方，但是，请注意，当我们放入第 7 条数据的时候，就会引起扩容，造成性能损失，所以，知晓了原理，我们以后在设置容量的时候还是自己算一下，比如放 7 条数据，我们还是都是设置成 16，这样就不会扩容了。

HashMap 的默认加载因子是 0.75，虽然可以修改，但是出于安全考虑，除非你经过大量测试，请不要修改此值，HashMap 使用此值基本是平衡了性能和空间的取舍。

HashMap 扩容的时机是，容器中的元素数量 > 负载因此 * 容量，如果负载因子是 0.75，容量是 16，那么当容器中数量达到 13 的时候就会扩容。还有，如果某个链表长度达到了 8，并且容量小于 64，则也会用扩容代替红黑树。

HashMap 在 JDK 7 中并发扩容的时候是非常危险的，非常容易导致链表成环状。但 JDK 8 中已经修改了此 bug。但还是不建议使用。强烈推荐并发容器 ConcurrentHashMap。

HashMap 扩容的时候，不管是链表还是红黑树，都会对这些数据进行重新的散列计算，然后缩短他们的长度，优化性能。在进行散列计算的时候，会进一步优化性能，减少减一的操作，直接使用 & 运算。可谓神来之笔。

总之，HashMap 中的优秀的设计思想值得我们去学习，最让楼主震惊的就是那个将任意一个数变成了 2 的幂次方的数，并且该数字很合理，说实话，如果让楼主写，楼主是写不出来的。

所以，请努力吧，现在做不到，不代表以后做不到，通过学习优秀的源码，一定能够提高我们的编码能力。

对了，今天是 2017 年的最后一天，明天就是 2018 年了，借这篇文章祝大家新年快乐。每个人都能实现自己的新年愿望。