JDK1.8中HashMap源码解析

一、红黑树的理解 1.1、 2-3树 1.1.1、 2-3的理解

• 红黑树是一种自平衡的二叉树，它可以避免二分搜索树在极端的情况下蜕化成链表的情况。那么什么是红黑树呢？要想便于了解红黑树，我们先了解一下跟它息息相关的2-3树。

• 2-3树是一种绝对平衡的多叉树，在这棵树中，任意一个节点，它的左右子树的高度是相同的。如下所示：

• 正如上面介绍过的，2-3树是一个多叉树。那为什么叫做2-3树呢？ 因为规则定义，2-3树分为两种节点，分别为：2-节点和3-节点。其中，2-节点表示节点中保存一个元素，3-节点则表示节点中保存两个元素。

1.1.2、 如何生成一个2-3树的演示示例

• 首先：向2-3树中插入30和25

• 当再插入37的时候，一个节点就容纳了3个元素了，那么就要进行分裂操作了，如下图所示：

• 然后，我们再插入20和33，可以正常的容纳这两个元素。

• 我们再继续插入17和43，那么出现了两个节点都分别容纳了3个元素，那么这两个节点都需要进行分裂操作了。

• 插入27和35，两个节点都可以容纳这两个新插入的元素。

• 那么再最后插入22，结果发现，一个节点容纳了3个元素，要进行分裂，但是分裂后，叶子节点的高度不一致了，那么就要再进行聚合操作，如下所示：

1.2、 红黑树 1.2.1、2-3树转换为红黑树（采用左倾红黑树的方式）

• 将2-3树转换为红黑树，转换规则如下图所示：

• 我们可以根据上面的转换规则，进行转换操作。下图是我们上面讲2-3树的时候，构造的。

• 那么我们按照规则进行转换，如下图所示：

• 我们按照树形结构进行修整，那么就是我们今天要介绍的红黑树。如下图所示：

1.2.2、红黑树的理解

1、我们已经了解了如何从2-3树转变为红黑树，那么，什么样的树才叫红黑树呢？难道把节点标记为红色和黑色就是红黑树了吗？当然不是！如果想称为红黑树的一员，一定要满足以下五个条件：

• 条件一：每个节点要么是红色，要么是黑色。
• 条件二：根节点一定是黑色的。
• 条件三：每个叶子节点一定是黑色。
• 条件四：如果一个节点是红色，那么它的左右子节点一定都是黑色的。
• 条件五：从任意一个节点到叶子节点，所经过的黑色节点的数量一样多。

2、条件三里面的描述，说每个叶子节点一定是黑色，但是你上面从2-3树转变的红黑树，叶子节点也不全都是黑色啊。比如33这个节点不就是红色吗？

• 因为没有画上空叶子（即：NULL LEAF），所以，33并不是叶子节点。红黑树的叶子节点是黑色的NULL LEAF。完整的红黑树，如下所示：

二、HashMap的源码概述

要是用HashMap的时候，我们首先会通过HashMap的构造方法创建HashMap，然后通过put方法向HashMap对象赋值。那么我们就可以通过构造函数+put这两点进行源码的切入点。

2.1、HashMap的构造函数

• HashMap的构造方法。
• 通过上图中源码可以看到只有一行代码，即给loadFactor赋值。loadFactor是HashMap的加载因子，也就是说，元素所占的空间达到加载因子的规定值的时候，那么就会执行扩容。
• 初始化加载因子的时候，赋值给它DEFAULT_LOAD_FACTOR属性。DEFAULT_LOAD_FACTOR这个值是0.75f，如下图所示：
• 通过上面截图，加载因子默认被赋值为0.75f，其实HashMap的结构在JDK8之前是【数组+链表】，而从JDK8之后，存储结构就变为了【数组+链表+红黑树】了。那么这个0.75的含义就是：如果数组中存储的元素长度达到了原长度的75%或者3/4的话，那么就需要执行扩容操作了。

2.2、put方法

• put方法的源码
• put方法里面，只是调用了putVal方法，如下图是putVal方法源码
• putVal方法一共执行了三部分内容，分别是： （1）、第一部分：创建table数组。 （2）、 第二部分：向table数组中赋值，这里面分为哈希不冲突和哈希冲突两种情况。 （3）、第三部分：如果超过阈值，则进行扩容操作。

2.2.1、第一部分（创建table数组）

• 源码如下

• 源码解释

  在if判断中，当table数组（即：底层存储HashMap元素的数组）等于null或者table数组的长度为0，那么就执行resize()方法进行扩容操作。

2.2.1.1、resize方法

1、 resize方法源码如下

2、 resize方法里面代码逻辑主要分为两大部分

• 第一部分：就是上面截图中这部分内容主要是针对旧的数组来确定新扩容的数组容量、阈值，然后创建新的table数组。
• 第二部分：就是if (oldTab != null) {…} 这部分的代码内容，这里主要是要针对旧的table数组及链表或红黑树向新的table数组中迁移的过程，因为新的table数组长度改变了，那么自然而然会导致hash寻址的时候有些元素位置产生了变化，那么就要设计到拆分链表或红黑树的操作。而且，其中如果分裂后的长度变小到一定的程度，那么原本的红黑树也会蜕化为链表，这部分详细的内容，当我们讲到红黑树那块代码的时候再详细去说。
• 对于我们第一次往HashMap中插入数据这个场景，本来就没有所谓的旧table数组，所以第二部分的数据迁移跟我们就没什么关系了，所以，我们暂时只需要关注第一部分就可以了。

3、resize方法中第一部分变量的含义 （1）、全局变量

• table： 当前所使用的table数组。
• threshold： 当前所使用的table数组的阈值。
• loadFactor： 当前所使用的table数组的加载因子。

（2）、局部变量

• oldTab： 表示旧的table数组。
• oldThr： 表示旧table数组的阈值。
• oldCap： 表示旧table数组的容量/长度。
• newTab： 表示新的table数组。
• newThr： 表示新table数组的阈值。
• newCap： 表示新table数组的容量/长度。

4、resize方法中第一部分每段源码的分析

1、源码如下 2、源码解释

• 由于我们是第一次调用put方法，所以table还没有被初始化，那么它是为null的，所以oldTab也等于null，oldCap就等于0了。
• threshold的默认值是0，所以oldThr也等于0。

3、三个判断部分代码源码如下 4、三个判断部分代码源码解释

• 判断1：如果旧的table数组长度大于0（即：oldCap > 0） （1）、case1 如果旧table数组长度大于等于最大容量（MAXIMUM_CAPACITY），那么阈值threshold就被赋值为Integer的最大值，返回旧的table数组。 Integer.MAX_VALUE的值为2的31次方减1，也就是二进制的 0111 1111 1111 1111 1111 1111 1111 1111。 MAXIMUM_CAPACITY的默认值为1= TREEIFY_THRESHOLD - 1，首先我们要说明的是，binCount是从0开始的，那么其实对应的是链表中的第2个元素，而TREEIFY_THRESHOLD默认值为8，则只要binCount >= 8-1，则尝试转变红黑树（是否转变，还要看treeifyBin里面的逻辑）。那么当binCount >=7的时候，其实就是链表中的元素已经超过8个了。下面，我们就来着重看一下treeifyBin方法的实现逻辑是什么？

（1）、treeifyBin方法

• 源码如下 - 源码解释如下
• treeifyBin可以分为两部分逻辑： A-> 如果table数组长度小于64，则只扩容table数组，不转换为红黑树。 B-> 否则，将链表转换为红黑树。

（1.1）、针对table数组进行扩容

• 这部分逻辑代码都在resize()方法中，它的源码如下所示：

• 首先，我们执行put(0, “a0”)和put(1,""a1)，那么HashMap的存储方式是这样的：

• 继续执行put方法，put(16, “a16”), put(32, “a32”), put(48, “a48”), put(64, “a64”), put(80, “a80”), put(96, “a96”), put(112, “a112”) 那么存储结构如下图所示：

• 由于下标为0的位置只是存储了8个节点，并没有出发扩容，那么我们就继续往下标为0的位置插入元素，即：put(128, “a128”)，那么下标为0的位置达到了9个元素，满足了触发扩容的条件，但是由于table数组的长度为16，所以不会转为红黑树。扩容和数据迁移后，存储结构如下所示：

• 从上面的途中我们可以看到，原本长度为9的链表，被拆分成了两条链表，其中：低位链表保存了5个节点的数据，高位链表保存了4个节点的数据。

• 我们介绍完链表的分裂和迁移之后，就来再回过头看一下 ((TreeNode)e).split(this, newTab, j, oldCap)的处理逻辑吧。split的源码如下所示：

• 其实针对红黑树的拆分方式与单向链表的拆分方式异曲同工，都是将一个整体拆分为高位和低位两部分。那么不同的是，当拆分后的高低位双向链表中存储的数据小于等于6个的时候，那么就没有必要使用红黑树的结构了，因为红黑树的特点是，在大数据量的情况下，查询比链表快太多了，但是由于每次插入或者删除节点，都需要重新调整红黑树的结构，以满足红黑树的约束，所以，这方面没有链表速度快。所以，当元素很少的情况下，就直接采用链表了。这部分涉及了untreeity方法，我们看一下untreeity的源码：

• 上图源码解释

• 就是遍历TreeNode双向链表，把每个节点转变为Node类型的节点，然后再拼装成一个单向链表即可。

• 上面说的是将整个链表拆分为高低位两链条表后，元素较少的情况会进行红黑树转为单向链表，那么如果这两条链表数据依然很多怎么办呢？那么就把这两部分创建两个新的红黑树就可以了。这部分设计的方式是treeify()，源码如下所示：

• 看完上图的注释，其实我们应该能够感受到，这个跟我们在【 2.2.2.2.2、 向红黑树中插入元素】中介绍的内容是一样的。其实就是三个步骤： A-》步骤一：将待插入的节点插入到红黑树中。 B-》步骤二：由于树形结构变化了，所以要对红黑树的平衡进行调整。 C-》 步骤三：如果由于对红黑树进行了调整，有可能造成root节点的变化，那么就要把最新的root节点放到双向链表的头部，并插入到table数组中。

（1.2）、链表转换为红黑树

• 介绍完链表的扩容后，来介绍一下红黑树的转换，如下所示：
• 在红框标注的部分中，我们又见到了treeify方法了，这个就是我们刚刚介绍完的方法，用来构造红黑树的。
• 这部分代码就是将链表中的每个节点Node转换为TreeNode类型，并调用treeify方法构造红黑树。treeify方法由于上面已经有详细的介绍了。

2.2.3、第三部分（执行table扩容操作）

• 那么当我们一直往HashMap中插入元素的时候，总会有把table数组填满的时候，那么table数组容量越小，针对大量数据就需要构建横向链表或红黑树，也就是说，哈希冲突就越容易发生。为了减少这种情况发生，table会根据约定好的阈值，即总容量的2/3或0.75，如果超过了这个阈值，则会进行table数组的扩容操作，代码如下所示：

• resize方法我们在上面的章节中已经介绍完毕了。只是把它拆成了两部分，第一部分是在【2.2.1、第一部分（创建table数组）】章节中介绍了，剩下的部分，是在【2.2.2.2.3、像单向链表中插入元素 】章节中有详细的介绍。那么此处，也就不在赘述了。