JDK1.8中HashMap源码解析_jdk1.8 hashmap resize()方法源码解析

一、红黑树的理解

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<<30，那么它表示的二进制为1000 0000 0000 0000 0000 0000 0000 0000。
  （2）、case2
  newCap = oldCap << 1表示将oldCap左移1位，其实也就是按照oldCap*2来扩容为newCap。
  如果满足以下两个条件，则新的阈值（newThr）也扩容为旧阈值（oldThr）的2倍：
  A、新的table数组容量（newCap）<MAXIMUM_CAPACITY
  B、旧的table数组容量（oldCap）>=DEFAULT_INITIAL_CAPACITY（默认值为：16）
  DEFAULT_INITIAL_CAPACITY的默认值如下所示：
  

• 判断2：如果旧的table数组阈值大于0（即：oldThr > 0）
  （1）、如果旧的table数组容量不大于0并且它的阈值还大于0，那么说明什么呢？
  说明table数组太大了，以至于长度越界了，出现了从整数变为了负数的情况。
  如果这种情况发生了，那么就将旧的table数组的阈值作为新table数组的容量进行赋值，相当于适度的进行长度修复。

• 判断3：如果上面条件都不满足，就执行判断3

  （1）、其实通过上面判断1和判断2的分析，我们应该可以得出如下结论：那么就是当table数组没有被初始化创建的时候，就会进入到判断3的代码。在这里，会做两件事：
  A、将新的table数组长度赋值为DEFAULT_INITIAL_CAPACITY。（这个默认值为16）
  B、将新的table数组的阈值赋值为：
  DEFAULT_INITIAL_CAPACITYDEFAULT_INITIAL_CAPACITY=160.75=12（DEFAULT_INITIAL_CAPACITY默认值为0.75f）
  （2）、以上即确定了新的table数组容量（newCap）和新的table数组的阈值（newThr）

5、第四个判断部分代码源码

6、第四个判断部分代码源码解释

• 这块代码主要是为上面【判断2：如果旧的table数组阈值大于0（即：oldThr > 0）】服务的，因为上面也说过了，逻辑进入到判断2，说明旧的table数组太大了导致越界从超级大的整数变为了负数。那么，由于代码块里只是对newCap赋值了，并没有赋值newThr，所以这块逻辑中，newThr的值依然是0，满足if条件。
• 首先通过ft=0.75f*newCap，计算出新的阈值，那么下面就要进行一系列的判断，代码挺长的，但是逻辑很简单。就是说如果我这次计算出来的新的阈值（ft）小于最大容量（MAXIMUM_CAPACITY），那么就作为新的阈值了。否则，那么就默认赋值为Integer的最大值了（Integer.MAX_VALUE）

7、resize方法中第一部分代码中最后一段源码

• 其实我们能够看出来，上面的一堆代码逻辑其实就是在做一件事，就是确定新的table数组的容量（newCap）和阈值（newThr），为了下面真正要创建新的table数组做准备。
  

8、resize方法中第一部分代码中最后一段源码的解释

• 这部分代码就是创建新的table数组，并且更新全局变量threshold和table，因为这两个值表示的就是当前“生效”或“正在使用”的table数组和阈值。

2.2.2、第二部分（向table数组中插入元素）

2.2.2.1、没有发生哈希冲突

• 当我们向HashMap中插入元素的时候，其实我们最希望看到的就是没有任何的哈希冲突，即可以直接插入到table数组中。那么下面的代码就是：
  
  
• 上图源码解释：通过(n - 1) & hash来寻址，找到待插入的位置i，这里的tab就是table数组，那么发现tab[i]==null，也就是待插入的位置是空的，我们直接插入就可以了。所以，先通过newNode方法构建Node节点，然后放到table数组对应的位置i上面。

2.2.2.2、发生了哈希冲突

• 大多情况下，插入的元素都会发生哈希冲突，对于JDK8来说，就会以链表或红黑树的方式进行数据存储。我们先从整体方面看一下这块代码。

  

2.2.2.2.1、冲突的节点与待插入的节点key值相同

• 这种情况，因为不涉及到红黑树和链表，只是把旧的Node节点取出来赋值给e。
  
• 在putVal方法的最后，会有一段如下的逻辑处理：
  
• 在覆盖旧值之前，需要判断onlyIfAbsent是不是为false，这个值其实就是putVal的第4个入参，我们调用put方法的时候，put方法里默认是传onlyIfAbsent=false的。所以它的含义是，如果我们要覆盖旧值，则onlyIfAbsent=false，如果不覆盖，则onlyIfAbsent=true。
  

2.2.2.2.2、向红黑树中插入元素

• 以红黑树的方式解决哈希冲突，这部分代码很多，我们一步步来拆分分析。代码如下所示：
  
• 这里判断，如果p这个值是TreeNode类型的，那么就现在这个结构是红黑树了，那么就往红黑树中插入了。p就是我们上面通过hash寻址获得得应该插入的下标i，然后从tab[i]中获得的元素。讲到这里，我们先来介绍一下HashMap底层的两个数据结构。
• 首先是TreeNode，它的结构如下所示：
  
  
  
• 【解释】：从上图源码中可知，TreeNode其实包含两部分内容：
  （1）、树结构（父节点：parent，左子节点：left，右子节点：right）
  （2）、 链表结构（前指针：prev，后指针：next），next指针是在TreeNode祖父类HashMap.Node里面定义的。
• 继续看putTreeVal方法的具体实现
  
• 【解释】： 根据上面源码截图的红框注释，可以将putTreeVal方法分为5部分来说明，
  （1）、寻址根节点
  （2）、确定插入位置
  （3）、构造TreeNode并插入到相应的子节点位置
  （4）、红黑树平衡调整
  （5）、moveRootToFront

（1）、寻址根节点

• 由于我们要将待插入的节点放到红黑树中，所以我们需要先从根节点出发，寻找待插入的位置，那么下面代码就是负责这部分内容的：

  

• parent代表父节点，那它是谁的父节点呢？我们是通过调用p的putTreeVal来执行的，那么就是p的父节点，还记得p是吧？即：p=tab[i]，也就是table数组中i位置上的元素。如下所示：
  

• 那么如果p的父节点等于null，就说明自己就是root根节点了，如果不等于null，就说明root根节点另有它人。就需要调用root()方法来进行查找了。
  

• 那么root()方法的逻辑就是，顺着p的父类往上查找父类，直到找到一个节点它没有父节点，那么这个节点就是root节点了。

（2）、确定插入位置

• 源码代码如下
  
• 这部分代码就是对比p节点的hash值与待插入元素的hash值，如果p节点hash值大，则说明待插入的元素在p节点的左侧，如果p节点hash值小，则说明待插入的元素在p节点的右侧。如果p节点的key值就是我们待插入的key值，那么就好办了，我们直接把这个p节点作为方法的返回值return就可以了。我们可以看到最外层的for循环是无限循环的，那么就说明，每一次循环，都会慢慢的向下寻找，直到找到一个节点，它的左节点或者右节点是可以插入新Node的，那么就插入了。这个过程就像我们搜索二叉树中某个值的过程是一样的。

（3）、 构造TreeNode并插入到相应的子节点位置

• 源码代码如下
  

• 通过上面的计算，我们得出一个dir的值，它就是用来表示在节点的左侧还是右侧。
  dir=-1：表示待插入节点在p节点的左侧。
  dir=1：表示待插入的节点在p节点的右侧。

• 这块代码中涉及的局部变量值的含义
  x表示待插入的树节点。
  xp表示x节点的parent节点。
  xpn表示xp的next节点，即后置节点。

• 假设dir=-1，也就是说我们要把待插入的节点放到树节点的左侧，那么如果p.left等于null，说明p是没有左子节点的，那么我们就可以执行插入操作了，即：满足了if里面的判断。

• 然后构建一个全新的TreeNode，并维护双向链表。这里需要关注的是map.newTreeNode(h, k, v, xpn)，第四个xpn就表示要我们新建节点x链接到xp节点的后面，然后将xpn链接到x节点的后面，如下所示：
  

• 当然，除了维护好双向链表之外，最重要的，当然是将x插入到xp的左侧，即：xp.left = x;

• 新节点也建好了，双向链表也维护好了，树节点也插入完毕了。但是，这个新的树结构真的满足红黑树的要求吗？不满足怎么办呢？需要进入下一章节——红黑树平衡调整balanceInsertion(root, x)来一探究竟了。

（4）、红黑树平衡调整

• 这部分代码主要就是调整树结构，使得可以构建成一个合法的红黑树，代码如下所示：
  

• 以上的代码，其实总的分为如下部分：

• 部分一：如果x的父节点在祖父节点的左侧
  （1）、操作类型一：变色。操作条件：如果祖父节点的右节点是红色的（其实作为祖父节点的左节点也是红色的）
  （2）、操作类型二：旋转+变色。

• 部分二：如果x的父节点在祖父节点的右侧
  （1）、操作类型一：变色。操作条件：如果祖父节点的做节点是红色的（其实作为祖父节点的右节点也是红色的）
  （2）、操作类型二：旋转+变色。

• 针对变色操作和旋转+变色这两种操作逐一分析即可，为了便于理解，采用图例的方式来说明。
  (1)、变色操作
  

  (2)、旋转+变色操作
  
  (3)、左旋操作rotateLeft
  

(4)、右旋操作rotateRight

（5）、moveRootToFront

• 这个方法就是将root节点放到整条双向链表的头部，并插入到table数组中。
• 源码如下
  
• 上图源码的整个处理流程依然采用图例的方式叙述。如下所示：
  

2.2.2.2.3、像单向链表中插入元素

• 上面介绍的红黑树，是当已经转换完红黑树之后再插入数据的操作。那么就像我们刚刚new了一个HashMap对象，然后开始插入元素的时候，是会先以单向链表方式存储的。那么它所涉及的代码如下所示：
  

• 上面的源码截图看到，for里面是一个无限循环，也就是说，会从p节点开始，一直调用next去遍历链表中的每一个元素，只要遇到了和待插入的key值相同的节点，则break出无限for循环。如果都没有与待插入的key值相同，则创建新的Node，插入到链表的结尾。

• 当然，还有一个限制，就是binCount >= 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<K,V>)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、像单向链表中插入元素 】章节中有详细的介绍。那么此处，也就不在赘述了。