JDK1.8版本HashMap源码分析之put篇

JDK1.8版本HashMap源码分析之put篇

HashMap的put()方法、putVal()方法 HashMap的treeifyBin方法TreeNode的treeify()方法TreeNode的balanceInsertion()方法TreeNode的旋转方法TreeNode的moveRootToFront()方法TreeNode的putTreeVal()方法

HashMap的put()方法、putVal()方法

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { // 调用putVal方法添加键值对 return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none * HashMap方法，添加键值对 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 初始化判断，初始扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 根据键的哈希值计算索引位置，如果位置上没有节点，把键值对封装成一个Node节点放在索引位置上 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 如果索引位置有节点（可能是Node也可能是TreeNode） else { Node<K,V> e; K k; // 判断索引位置的节点和键是否相同，先判断hash是否一致（hash不相同也可以映射到同一个位置）再判断值是否相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果索引位置节点是TreeNode，说明是一棵红黑树，利用红黑树的putTreeVal方法添加键值对 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 如果不是红黑树，那就是链表了 else { // 遍历链表节点 for (int binCount = 0; ; ++binCount) { // 如果节点为空，那么说明当前链表上没有这个键，封装一个Node插入到链表尾部即可 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 遍历次数，就是链表节点的数量，如果数量到达默认的阈值，调用HashMap的treeifyBin方法，判断是否有必要转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果节点不为空，就判断是否和键相同 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // e不为空，表示键存在索引位置的数据结构中（节点、链表、红黑树） if (e != null) { // existing mapping for key V oldValue = e.value; // 根据参数，判断是否需要覆盖旧值 if (!onlyIfAbsent || oldValue == null) e.value = value; // 空方法，用于子类覆写 afterNodeAccess(e); return oldValue; } } ++modCount; // 添加键值对后，判断是否超过扩容阈值 if (++size > threshold) resize(); // 空方法，用于子类覆写 afterNodeInsertion(evict); return null; }

在上述方法中，涉及到三种情况：第一种情况，数组索引位置没有键值对，处理方式就是直接把待添加键值对封装成Node添加到索引位置即可；第二种情况，如果数组索引位置有键值对，而且封装的TreeNode节点，处理方式是调用红黑树的插入方法，把待添加键值对添加到红黑树中；第三种情况，同样数组索引位置有键值对，但是封装的是Node节点，处理方式就比较复杂，首先把待添加键值对封装成Node节点添加到链表尾部，然后判断当前链表长度，如果到达阈值（TREEIFY_THRESHOLD变量），就判断是扩容还是转换为红黑树（treeifyBin方法）。 我们循序渐进的看，首先，第一种情况不需要再分析，我们先来分析第三种情况，因为第二种情况其实是第二种情况的后续。

HashMap的treeifyBin方法

/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. * 方法的这段注释的意思大概是，当HashMap的底层数组太小的时候，HashMap会进行扩容 * 否则，根据hash把对应索引位置的链表结构的节点，转换成红黑树 * * 从这段注释，我们了解到，并不是链表到达一定长度就一定会转换成红黑树结构， * 是否转换成红黑树结构，还和table的大小有关 */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 如果tab是空或者长度小于阈值，就进行扩容，不需要转换为红黑树 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 如果tab长度大于阈值，默认是64，进行红黑树转换 else if ((e = tab[index = (n - 1) & hash]) != null) { // 定义两个变量，hd用来记录头结点，tl用来记录尾节点 TreeNode<K,V> hd = null, tl = null; // 这段do-while的意思是，把原来组成链表的所有Node节点，重新用TreeNode封装一下，然后链接起来，节点连接的顺序不变 do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) // 头节点 hd = p; else { // 遍历把节点链接到一起 p.prev = tl; tl.next = p; } tl = p; // tl指向最后一个节点 } while ((e = e.next) != null); // 让数组索引位置指向hd，也就是头结点，然后做红黑树转换 if ((tab[index] = hd) != null) hd.treeify(tab); } }

从上述方法中，我们知道当链表长度到达一定阈值（默认为8）时，会调用一个方法，判断是否需要转换红黑树，判断的依据就是构成HashMap的数组长度是否达到阈值（默认为64），如果还没有，那么只进行扩容即可，不会转换。真正的转换红黑树的方法是treeify方法，这个方法是TreeNode的方法，接下来具体分析该方法。

TreeNode的treeify()方法

/** * Forms tree of the nodes linked from this node. * 从当前结点（链表的头结点），把链接的节点，构成树结构 * @return root of tree */ final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; // 从当前节点开始，沿着链表的next的指针，向后遍历 for (TreeNode<K,V> x = this, next; x != null; x = next) { // 先记录next节点 next = (TreeNode<K,V>)x.next; // 重置左右节点为null x.left = x.right = null; if (root == null) { // 把x定义为根节点 x.parent = null; x.red = false; root = x; } else { // 当前节点的键和键的hash K k = x.key; int h = x.hash; Class<?> kc = null; // 从根节点开始，遍历当前的树，判断当前链表节点应该放在树的哪个位置 for (TreeNode<K,V> p = root;;) { int dir, ph; // 需要比较的树节点的键 K pk = p.key; // 根据hash判断，hash小，沿着树的左子树查找 if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; // hash相同，根据比较接口的函数结果判断 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) // 比较函数无法比较出结果的话，按照默认方式比较，即比较类的名称->比较类的名称的哈希值 dir = tieBreakOrder(k, pk); // 以上步骤，确定了新的节点的插入路径，下边，需要沿着具体的路径找到最终的叶子节点的位置，然后链接上即可 TreeNode<K,V> xp = p; // 保存p的引用 // 根据dir，选择p的左子树还是右子树 // 如果对应为null，那么就是要插入的位置，如果不是null，那么以p为根节点，继续遍历树，p的重新赋值在下边if判断里 if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; // 在这里调整红黑树的结构，让它符合红黑树的特征 root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); }

上述这个方法，比较复杂，首先这个方法是TreeNode的方法，由一个TreeNode节点调用。我们首先要知道一点，那就是转换成红黑树之前的链表，顺序是按照添加的先后顺序链接的。红黑树，它首先是一颗二叉查找树，然后才是红黑树，所以它对节点的大小是有要求的。然后我们分析这段代码，该方法，由链表头部的节点调用，对于它在树中的位置，是不确定的，所以，这里先把它当做根节点，然后，依次遍历链表的每个节点，插入到树的叶子节点上，没插入一个节点，就平衡一下红黑树（调用balanceInsertion方法），保证红黑树特征。 接下来我们看一下，如何平衡红黑树，同样，该方法也是TreeNode的方法

TreeNode的balanceInsertion()方法

/** * 向树中插入节点时，平衡树的方法，root为当前根节点，x为插入节点 * 该方法返回的是根节点 */ static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { // 先把插入节点定义为红色节点，这样可以保证从根节点到每个叶子节点路径上具有相同黑色节点的特征 x.red = true; for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { // xp定义为x节点的parent节点，如果为null，那x就是根节点，置为黑色，返回即可。 if ((xp = x.parent) == null) { x.red = false; return x; } // xp不是根节点，那么这里分两种情况，那就是xp是红还是黑 // 如果xp是黑的，那么x作为红色节点插入到xp后边，是不会对红黑树结构产生任何影响，直接返回根节点root即可。 // 如果xp是红的，但是xp的父节点xpp是null，这种情况暂时没有考虑到什么情况下会发生，因为如果xp的父节点是null，那么xp一定是根节点，根节点一定是黑色的 else if (!xp.red || (xpp = xp.parent) == null) return root; // 执行到这里，说明xp一定是红色，这时候插入一个红色x到xp的下边，就破坏了红黑树特征 // 判断xp如果是它父节点的左子节点， if (xp == (xppl = xpp.left)) { // 判断xp是否有兄弟节点，并且是红色的 // 因为如果xp只是单纯的变色，保证x是红的xp是黑的符合红黑树特征， // 那么xxp的左子树路径上就多了一个黑色节点，这时候需要考虑是否右子树路径上黑色节点的数量 if ((xppr = xpp.right) != null && xppr.red) { // 如果右子树右红色的节点，那么同时把xp和它的兄弟变色变成黑的即可满足红黑树的特征 xppr.red = false; xp.red = false; // 这里把xpp变成红色，考虑到如果xpp颜色不变化，那么包含xpp的分支路径上就比别的路径 // 上多了一个黑色节点（它的左右子节点都变为了黑色），所以把xpp变为红色，来减少黑色节点数量， // 这样，就保证xpp这棵子树的黑色节点整体总数不变，不会影响到其他的分支 xpp.red = true; // xpp树已经满足了标准红黑树，这里将x赋值之后，把xpp当做一个节点来看待。 // 当满足之前的两个退出条件后，就退出for循环，后边原理相同 x = xpp; } // 执行这里说明xp没有兄弟节点，或者说兄弟节点是黑色的 // 这就要分两种情况 else { // 如果x是xp的右节点，左旋转即可，让xp成为x的左子节点，x替换xp // xpp xpp // / \ / \ // xp C ====> x C // \ / // x xp // 如上图，xp是红色的，x是红色的，xpp、C是黑色的。 // 通过左旋转，变色后，x和C互为兄弟节点，xp变成x的左子节点，xp变为黑色 // 如此，xpp左路径上，红黑节点数不变，xpp右子树不被影响 if (x == xp.right) { root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } // 如果x不是右子树，而是左子树，那就需要右旋转 if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } // 如果xp是xpp的右节点 else { // xpp有左节点，并且是红的，一样，把xp和兄弟节点都变成黑色的，xpp变成红色 if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } // 如果xpp没有左节点或者不是红的，也是通过左右旋转调整红黑树结构 else { if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } }

看上述代码，首先，把添加的节点定义成红色，因为，这样对当前平衡的红黑树侵入最小的，更大限度的满足红黑树特征，我们回顾一下红黑树的特征：第一，满足每个节点要么是黑色要么是红色；第二，根节点是黑色；第三，每个叶子节点是黑色，这里的叶子节点和标准二叉查找树的叶子节点不同，这里指的是为null的叶子节点；第四，红色节点的子节点必须是黑色的；第五，从任何一个节点开始，到它任何一个子孙节点的路径上的黑色节点数量必须一样。通过这些特征，我们发现，把添加的节点定为红色，只可能违反第四条特征，也就是说红色节点的子节点必须是黑色，说白了，我们只需要考虑插入节点的父节点是不是红色。从上边的代码我们也看出来了，所有的操作（变色、旋转）其实都是针对这种情况做的调整。接下来我们简单了解一下旋转的代码

TreeNode的旋转方法

/** * 左旋转，root是根节点，p是旋转操作的轴节点 */ static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> r, pp, rl; // p的右节点、父节点、右节点的左节点 if (p != null && (r = p.right) != null) { if ((rl = p.right = r.left) != null) rl.parent = p; if ((pp = r.parent = p.parent) == null) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; } static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> l, pp, lr; if (p != null && (l = p.left) != null) { if ((lr = p.left = l.right) != null) lr.parent = p; if ((pp = l.parent = p.parent) == null) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; }

关于左右旋转，不好理解的话，可以自己边画图边理解，还是比较简单的，这里不做阐述了。

到这里，关于链表转换为红黑树的逻辑我们已经分析的差不多了，还差最后一个方法，moveRootToFront()，该方法的作用是

TreeNode的moveRootToFront()方法

/** * Ensures that the given root is the first node of its bin. * 直译过来的意思就是，确保给定的root是在容器中的第一个节点 * 也就是说，通过键的hash定位到数组的索引位置时，第一个访问的节点应该是根节点 */ static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { int index = (n - 1) & root.hash; // 当前索引位置访问的第一个节点 TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // root节点是我们平衡红黑树平衡出来的节点，如果first不是root，这就是这个方法需要做的事情 if (root != first) { Node<K,V> rn; // 直接把索引指向root节点 tab[index] = root; // 我们从TreeNode的数据结构可以知道，红黑树不仅仅是树结构，其实内部还维护了链表结构 // 如果仅仅把索引指向root节点，但是当前的root并不是链表结构的头结点，我们需要把root同时设置为头结点 // 这里的方式是，先把root从整个链表中拿掉，也就是说让root的前后两个节点绕过root，通过prev、next指针相连 // 然后，让first的prev指向root，这样，root就是头节点了 // 先拿到root的prev节点 TreeNode<K,V> rp = root.prev; // 如果root的下一个节点不是空，那么让这个节点的prev指向root的prev if ((rn = root.next) != null) ((TreeNode<K,V>)rn).prev = rp; // 如果next的prev也不是空，那么就让它的next指向root的next节点 if (rp != null) rp.next = rn; // 通过以上两步，就让root的前后节点直接相连了 // 接下来把root放到first的前边 if (first != null) first.prev = root; root.next = first; root.prev = null; } // 断言，检查树是否符合规则 assert checkInvariants(root); } }

好了，以上就是链表变成树的最后一步。 至此，链表如何变成树，我们全都剖析完毕。我们来整理一下整体的流程，首先，新的键值对会添加到链表的尾部，达到阈值，触发变成树的检查，当不满足条件的时候，也就是默认数组长度不够64时，只是做了扩容操作，如果满足条件，就会触发变成树的操作，首先把原来无序链表的节点重新封装，然后从头遍历，取出第一个作为根节点，然后做添加操作，每添加一个键值对，都可能导致树结构的错乱，需要平衡这棵树，直到所有节点都添加到树中，最后确保索引位置的节点是这棵树的根节点，整个流程就完了。 最后我们分析一下添加时的另外一个流程，如果这个索引下已经是一棵红黑树了，如何处理呢？其实了解过之前的逻辑，这块就很简单了，直接封装键值对为TreeNode，然后调用树添加方法即可。我们来看看是不是这么做的。

TreeNode的putTreeVal()方法

/** * Tree version of putVal. * * TreeNode方法，添加键值对到红黑树中 * @param map hashmap对象 * @param tab hashmap数组对象 * @param h 键的哈希值 * @param k 键 * @param v 值 */ final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; // 找到红黑树的根节点 TreeNode<K,V> root = (parent != null) ? root() : this; // 从根节点开始遍历红黑树 for (TreeNode<K,V> p = root;;) { int dir, ph; K pk; // 比较键和根节点的哈希值，确定下一步的遍历分支 if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; // 如果键和根节点哈希值一致，判断键和根节点是否相同，如果相同，直接返回根节点 else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; // 如果键和根节点哈希值一致，值不同，而且键没有实现了Comparable接口或者通过接口方法跟根节点比较的结果相同 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { // 根据标识位（该逻辑只执行一次），从根节点左右子树中分别查找键，如果找到了就返回 if (!searched) { TreeNode<K,V> q, ch; searched = true; if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) return q; } // 如果在左右子树中都没找到键，说明键不存在，用默认的方式比较根节点和键，判断键的存储分支 dir = tieBreakOrder(k, pk); } TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { // xp是每次循环p的引用，当执行到这时，p的引用就是null叶子节点的父节点 // 把xp的next指向的Node节点，封装成TreeNode节点，然后，根据之前的判断，链接到xp的左子节点或右子节点上 Node<K,V> xpn = xp.next; TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; // 然后把next指针指向重新封装的TreeNode节点上 xp.next = x; // 当然，也要把新的TreeNode节点的parent和prev指针指向xp x.parent = x.prev = xp; // 如果xp的next指针指向的xpn节点不是null节点，那么需要把它的prev指针指向到新的 if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; // 平衡 调整根节点 moveRootToFront(tab, balanceInsertion(root, x)); return null; } } }

看到上边这段代码，是不是觉得简单了很多，很多代码都是和上边相同的。所以不做过多解释了。 至此，整个添加逻辑就分析完了~