Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方，欢迎指正~
转载请注明出处https://blog.lzoro.com。

前言

基于JDK1.8。

JDK1.8之前，HashMap并没有采用红黑树，所以哈希桶上的链表过长时，就会有效率问题。

JDK1.8，则在HashMap引入了红黑树，当链表长度超过指定阈值(默认为8)，则进行树化并提供相关操作(增删查等)，提高了操作效率。

之前阅读了HashMap的源码，但是由于篇幅关系，略过了链表树化后红黑树的相关操作，本着打破砂锅问到底的精神，来看下红黑树在HashMap中的应用。

打破沙锅问到底，是一个成语，拼音为：dǎ pò shā guō wèn dào dǐ，其 比喻追究事情的根底，其出处自 宋·黄庭坚《拙轩颂》。

红黑树

什么是红黑树？

是这样的吗（开个玩笑，不存在的）。

是这样的，这才对吧，有红有黑。

科普时间，it KePu's tims.

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

以上科普信息由度娘提供。

性质

红黑树不仅是二叉查找树，它还必须满足5个性质

• 1.节点非黑即红
• 2.根节点是黑色
• 3.每个叶节点（NIL节点，空节点）是黑色的
• 4.每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

满足了以上性质的二叉查找树的就是红黑树，如果是初次接触的话，是不是看完有点懵，不要慌，接着往下看。

红黑树的效率相对较高，所以它被用来存储相关数据，基本的操作有增加/删除/查找，在这些操作之后可能会破坏红黑树的性质，所以需要相关操作来维护以让红黑树符合上面的性质要求。

而这里提到的相关操作有

• 变色
• 左旋
• 右旋

左旋右旋

是不是对红黑树的任意操作之后，它都还能满足上面的提交的条件呢。

答案是No。

所以也就有了旋转的存在。

旋转跳跃，我闭着眼，尘嚣看不见 你沉醉了没。（请不要唱，快拉回你的心思）

嗯，旋转分为左旋和右旋。

左旋

将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，并修改相关引用。

右旋

是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，并修改相关的引用。

是不是还是有点迷糊，那么再来两张动图帮助下理解~

懒人自有妙计，不过要有版权意识。
动图来源：https://blog.csdn.net/sun_tttt/article/details/65445754

是不是明白一些了~~

基本的关于红黑树概念介绍完毕，需要深入了解的小伙伴请移步搜索引擎。

接下来，坐好了，将车门焊死，准备发车了。

HashMap中的红黑树

先看下HashMap内部类TreeNode<K,V>的定义，它继承了LinkedHashMap.Entry<K,V>

类java.util.HashMap 第1791行起 /** * 二叉树实体. 继承 LinkedHashMap.Entry (顺序扩展节点) * * linked node. */ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { //红黑树父节点(链) TreeNode<K,V> parent; // red-black tree links //左节点 TreeNode<K,V> left; //右节点 TreeNode<K,V> right; //前置节点 TreeNode<K,V> prev; // needed to unlink next upon deletion //红黑标志 boolean red; /** * 构造函数 */ TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } /** * 返回根节点 */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } //先略去部分功能代码 ... } 

在看相关的功能代码之前，先来看下HahsMap中红黑树左旋和右旋的实现

HashMap中的红黑树 - 左旋

/** * 红黑树左旋操作 */ static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> r, pp, rl; //p不为null且p的右子树不为null if (p != null && (r = p.right) != null) { //将r(p的右子树)的左子树变成p的右子树 //有点拗口 o(╥﹏╥)o //下面会用一个图示来说明 if ((rl = p.right = r.left) != null) //修改父节点引用，rl是r(p的右子树)的左子树 rl.parent = p; //将r(p的右子树)的父节点变成p的父节点（左旋过程，将右子树变成自己的父节点） if ((pp = r.parent = p.parent) == null) //如果p节点的父节点为null，证明p是根节点（子树的根节点） //将r变成根节点（子树的根节点），并变成黑色（符合性质） (root = r).red = false; //如果存在父节点且p是该节点的左子树 else if (pp.left == p) //将r(p的右子树)变成该节点的左子树 pp.left = r; //如果存在父节点且p节点是该节点的右子树 else //将r(p的右子树)变成该节点的右子树 pp.right = r; //将r(p的左子树)变成p（左旋中，将左子树变成自己的父节点） r.left = p; //r变成p的父节点 p.parent = r; } return root; } 

下面用图示来说明上面的步骤，会比较简单明了不拗口

一、p没有父节点（可以理解为p是根节点）

一、p有父节点

HashMap中的红黑树 - 右旋

/** * 红黑树右旋操作 */ static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> l, pp, lr; //p不为null且p的左子树不为null if (p != null && (l = p.left) != null) { //将l(p的左子树)的右子树变成p的左子树 if ((lr = p.left = l.right) != null) //修改父节点引用，lr是l(p的左子树)的右子树 lr.parent = p; //将l(p的右子树)的父节点变成p的父节点（右旋过程，将左子树变成自己的父节点） if ((pp = l.parent = p.parent) == null) //将l变成根节点（子树的根节点），并变成黑色（符合性质） (root = l).red = false; //如果存在父节点且p是该节点的右子树 else if (pp.right == p) pp.right = l; //如果存在父节点且p是该节点的左子树 else pp.left = l; //将l(p的右子树)变成p（右旋中，将右子树变成自己的父节点） l.right = p; p.parent = l; } return root; } 

类似的下面用图演示过程

一、p没有父节点（可以理解为p是根节点）

一、p有父节点

右旋

---

理解了HashMap中红黑树的左旋和右旋，下面看一下几个比较重要的方法

treeify

顾名思义：树化。当哈希桶中的链表长度超过阈值(默认8)的话，就会对链表进行树化，具体来看一下实现。

调用链如下

1、HashMap第643行treeifyBin(tab, hash);，判断阈值，超过则进行树化

2、HashMap第754行，treeifyBin实现，第771行调用TreeNode的树化实现

/** * 替换哈希桶中给定哈希索引的元素 * 如果哈希桶太小，则resize */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //判断哈希桶 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //调整扩容 resize(); //在哈希桶中获取指定位置的元素 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //替换成树节点 do { //这里的replacementTreeNode调用了TreeNode的构造函数进行构造 TreeNode<K,V> p = replacementTreeNode(e, null); //维护顺序 if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); //修改哈希桶中对应下标的指向为树的头结点 if ((tab[index] = hd) != null) //执行红黑树化 hd.treeify(tab); } } 

3、HashMap第1897行，treeify实现

/** * 红黑树化 * @return 树的根节点 */ final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; //循环整理 for (TreeNode<K,V> x = this, next; x != null; x = next) { //取出下一个链表节点 next = (TreeNode<K,V>)x.next; //将x节点的左右节点设置为null x.left = x.right = null; //判断当前红黑树是否有根节点 if (root == null) { //如果没有根节点 //当前节点的父节点设置为null x.parent = null; //设置颜色为黑色（根节点为黑色） x.red = false; //将x节点设置为根节点 root = x; } //当前红黑树存在根节点 else { //获取x节点的key K k = x.key; //获取x节点的hash int h = x.hash; //key的class Class<?> kc = null; //从根节点遍历，将x节点插入到红黑树中 for (TreeNode<K,V> p = root;;) { //定义dir(方向),ph(节点hash) int dir, ph; //取出p节点的key K pk = p.key; //当p节点的hash大于x节点的hash时 if ((ph = p.hash) > h) //左侧 dir = -1; else if (ph < h) //右侧 dir = 1; //如果上面的if分支没走，则证明两个节点key的hash值相等，需要通过其他方式进行比较 //如果当前节点(x)的key的类实现了comparable接口，且当前循环节点(p)是相同Class的实例 //那么就通过comparable进行比较 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) //若还是相等，就通过tieBreakOrder比较 dir = tieBreakOrder(k, pk); //先缓存p节点 TreeNode<K,V> xp = p; //根据dir方向，来选择在左侧还是右侧插入 //并判断是否为null if ((p = (dir <= 0) ? p.left : p.right) == null) { //选择的左/右子树为null //将原来的p节点(现xp)设置为x的父节点 x.parent = xp; //如果dir 小于等于0 //将x节点放置在原p(现xp)节点的左侧 if (dir <= 0) xp.left = x; //如果dir 大于0 //将x节点放置在原p(现xp)节点的右侧 xp.right = x; //调用balanceInsertion进行插入平衡 root = balanceInsertion(root, x); break; } } } } //确保哈希桶指定位置存储的节点是红黑树的根节点 moveRootToFront(tab, root); } /** * 确保哈希桶指定位置存储的节点是红黑树的根节点 */ 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]; //如果不是红黑树的根节点 if (root != first) { Node<K,V> rn; //指向红黑树的根节点 tab[index] = root; TreeNode<K,V> rp = root.prev; //整理节点顺序 if ((rn = root.next) != null) ((TreeNode<K,V>)rn).prev = rp; if (rp != null) rp.next = rn; if (first != null) first.prev = root; root.next = first; root.prev = null; } //递归做一个恒定校验 assert checkInvariants(root); } } 

4、HashMap第2206行，balanceInsertion实现

这个方法实现了红黑树插入节点后的平衡(为了满足平衡性)，方法的分支较多，如果没有很透彻理解红黑树的相关概念和操作，一时间会容易迷惑，下面代码对整体流程进行了注释，但是仍然比较晦涩，后面会带上图示，加深理解。

/** * 插入平衡 */ static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { //将x节点设为红色（新插入节点一开始为红色） x.red = true; //一个没有边界的循环(需要内部跳出) for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //取出x的父节点并判断是否为null if ((xp = x.parent) == null) { //x没有父节点 x.red = false;//变色(黑色) return x;//x为根节点发那会 } //如果x存在父节点且x的父节点为黑色或x的父父节点不存在 else if (!xp.red || (xpp = xp.parent) == null) //返回root return root; //如果x的父节点是父父节点的左孩子 if (xp == (xppl = xpp.left)) { //父父节点的右孩子不为null且为红色 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false;//变色(黑) xp.red = false;//变色(黑) xpp.red = true;//变色(红) x = xpp; } else { //x是父节点的右孩子 if (x == xp.right) { //左旋 root = rotateLeft(root, x = xp); //处理x的父父节点 xpp = (xp = x.parent) == null ? null : xp.parent; } //x的父节点存在 if (xp != null) { xp.red = false;//变色 //x的父父节点存在 if (xpp != null) { xpp.red = true;//变色 //右旋 root = rotateRight(root, xpp); } } } } //如果x的父节点是父父节点的右孩子 else { //x的父父节点的左孩子存在且为红色 if (xppl != null && xppl.red) { xppl.red = false;//变色(黑) xp.red = false;//变色(黑) xpp.red = true;//变色(红) x = xpp; } else { //如果x是父节点的左孩子 if (x == xp.left) { //右旋 root = rotateRight(root, x = xp); //处理x的父父节点 xpp = (xp = x.parent) == null ? null : xp.parent; } //如果x的父节点存在 if (xp != null) { xp.red = false;//变色(黑) //如果x的父父节点存在 if (xpp != null) { xpp.red = true;//变色(红) //左旋 root = rotateLeft(root, xpp); } } } } } } 

下面用图示，举个栗子~

栗子在这里

假如有如下一个链表，里面的数字代表hash值（先不考虑hash分布）

然后按照链表顺序取出节点进行红黑树插入，以及插入后平衡操作（左旋右旋/变色），来看一下整个过程

综合上面的描述和图示，大概可以把链表转红黑树的操作总结如下

1、将链表的首节点当做临时的红黑树根节点，左右孩子置为null 2、循环按顺序取出链表的节点，进行红黑树插入，和插入后平衡 2.1、取出链表节点，经过hash比较，插入到红黑树合适的位置(保证平衡性) 2.2、由于插入的节点会破坏红黑树的性质，所以需要进行插入后平衡 2.2.1、新插入的节点置为红色 2.2.2、父节点和父父节点的null判断和颜色判断 2.2.2.1、判断新插入节点的父节点是否存在，不存在则返回 2.2.2.1、如果父节点是黑色的，或者父父节点不存在着，则返回 2.2.3、父节点是父父节点的左孩子还是右孩子判断 2.2.3.1、是左孩子且兄弟节点存在并且是红色，则执行相应的变色，然后进行下一轮判断。 2.2.3.2、是左孩子当兄弟节点不存在（或者是黑色），则执行相应的左旋/右旋。 2.2.3.3、是右孩子且兄弟节点存在并且是红色，则执行相应的变色，然后进行下一轮判断。 2.2.3.4、是右孩子当兄弟节点不存在（或者是黑色），则执行相应的左旋/右旋。 3、链表循环完毕后，确保哈希桶指定位置存储的是红黑树的根节点 嗯，没了。细节请看源码和图示，如果觉得迷糊，可以自己动手画画图，或者Debug。 

untreeify

有了树化，肯定也有非树化。

有起有落，月缺月圆，凡事要有平衡。一本正经地胡说八道。

突然就斗起了表情。

没错，这个方法就是将红黑树退化成链表，俗称链表化。

入口有几个地方

• 节点删除时，红黑树的大小低于阈值，退化成链表。2035行tab[index] = first.untreeify(map); // too small
• 扩容/调整容量时，调用split方法

/** * 红黑树链表化 */ final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; //循环，将红黑树转成链表 for (Node<K,V> q = this; q != null; q = q.next) { //构造一个普通链表节点 Node<K,V> p = map.replacementNode(q, null); //维护顺序 if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; } 

putTreeVal

嗯，没什么好说的，红黑树的节点插入。

对应上篇博客的链表节点插入，但相比链表来说会比较复杂。不过流程与之前提到过的树化当中的单一节点插入没有太大区别，也是从红黑树的根节点进行遍历，寻找合适的位置插入，并进行插入后的平衡(变色/左旋/右旋)，待插入平衡后，确保存储在哈希桶指定位置的节点是红黑树的根节点。

/** * 红黑树版本的节点插入 */ 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; 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) { 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; xp.next = x; x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; //插入到合适的位置和，可能破坏红黑树的性质，所以需要进行插入平衡 //插入平衡后，需要确保哈希桶下标位置上存储的节点是红黑树的节点 //这些在上面的树化过程都有提到，此处不再赘述 moveRootToFront(tab, balanceInsertion(root, x)); return null; } } } 

getTreeNode

红黑树中的节点查找。

对应链表的节点查找，在链表树化后，节点的查找就是红黑树实现的。查找的逻辑还是比较清晰的，因为红黑树是自平衡二叉查找树，节点左子树都比自己小，右子树都比自己大，所以根据给定的hash，可以确定从左子树还是右子树查找，然后循环进行定位，知道最终找到节点或者不存在该节点时，结束查找。

/** * 红黑树节点查找的入口方法 */ final TreeNode<K,V> getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } /** * 根据给定的hash和key，从红黑树的根节点开始进行查找 */ final TreeNode<K,V> find(int h, Object k, Class<?> kc) { TreeNode<K,V> p = this; do { int ph, dir; K pk; //取出左子树和右子树，根据hash和key进行查找 TreeNode<K,V> pl = p.left, pr = p.right, q; //根据hash大小决定取左子树还是右子树 if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; //如果在节点相等，就返回 else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.find(h, k, kc)) != null) return q; else p = pl; } while (p != null); return null; } 

removeTreeNode

移除红黑树节点。

对应链表节点的移除，红黑树版本的节点移除相比链表会复杂一些，因为涉及到维护红黑树的平衡性和相关性质。

/** * 移除给定节点, 调用该方法时要确保节点存在. * 因为无法交换存在叶子节点的内部节点内容，所以这会比典型的红黑树节点删除来得复杂 * 遍历过程中"next"指针指向的继任节点是可访问的，所以我们交换了树的连接. * 如果当前树节点太少，则将二叉树替换成简单形式 * (2-6节点测试触发，取决于树的结构) */ final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { int n; //判断哈希桶 if (tab == null || (n = tab.length) == 0) return; //下标 int index = (n - 1) & hash; //取出指定下标的根节点 TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; //继任节点和前置节点 TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; //前置节点不存在，则证明要移除的节点是根节点 if (pred == null) //将继任节点往前移 tab[index] = first = succ; else //前置节点存在，则将继任节点连接到前置节点（移除本节点） pred.next = succ; //判断继任节点是否存在 if (succ != null) //存在的话，修改前置引用 succ.prev = pred; //这个时候first为null，则表示哈希桶指定位置可能只有一个节点 if (first == null) //返回 return; //获取根节点 if (root.parent != null) root = root.root(); //根节点不存在或者根节点的左子树/右子树不存在或者左左子树不存在 //该判断是作为链表化的阈值 if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) { //红黑树太小，进行链表化 tab[index] = first.untreeify(map); // too small return; } //取得要移除的节点，左子树，右子树 TreeNode<K,V> p = this, pl = left, pr = right, replacement; //左右子树同时存在 if (pl != null && pr != null) { TreeNode<K,V> s = pr, sl; //循环查找继任节点 while ((sl = s.left) != null) // find successor s = sl; //交换p和s的颜色 boolean c = s.red; s.red = p.red; p.red = c; // swap colors TreeNode<K,V> sr = s.right; TreeNode<K,V> pp = p.parent; //相等则证明p是s的直接父节点（只有一个层级） if (s == pr) { // p was s's direct parent //交换位置 p.parent = s; s.right = p; } //如果是多个层级 else { //取出s的父节点 TreeNode<K,V> sp = s.parent; //下面操作仍然是交换p和s的位置 if ((p.parent = sp) != null) { if (s == sp.left) sp.left = p; else sp.right = p; } if ((s.right = pr) != null) pr.parent = s; } //清空p的右子树引用 p.left = null; //调整相关引用 if ((p.right = sr) != null) sr.parent = p; if ((s.left = pl) != null) pl.parent = s; if ((s.parent = pp) == null) root = s; else if (p == pp.left) pp.left = s; else pp.right = s; //确定替换节点 if (sr != null) replacement = sr; else replacement = p; } //只有左子树存在 else if (pl != null) replacement = pl; //只有右子树存在 else if (pr != null) replacement = pr; //左右子树都不存在 else replacement = p; //判断替换的节点是不是自身 if (replacement != p) { //不是自身的话，则执行相关替换操作 TreeNode<K,V> pp = replacement.parent = p.parent; if (pp == null) root = replacement; else if (p == pp.left) pp.left = replacement; else pp.right = replacement; p.left = p.right = p.parent = null; } //判断p的颜色 //如果p是红色节点，则将根节点赋值给r //如果p是黑色节点，则进行删除平衡(类似于插入平衡) //这里的r要存储红黑树的根节点 TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); //如果替换节点是自身的话 if (replacement == p) { // detach //进行分离操作 TreeNode<K,V> pp = p.parent; p.parent = null; if (pp != null) { if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; } } if (movable) //确保哈希桶下标指定位置存储的是红黑树根节点 moveRootToFront(tab, r); } 

split

只有在resize的时候被调用，作用是在哈希桶扩容/调整容量时，将红黑树拆分成两颗树，在红黑树太小时进行链表化等操作。

具体看源码注释。

/** * Splits nodes in a tree bin into lower and upper tree bins, * or untreeifies if now too small. Called only from resize; * see above discussion about split bits and indices. * * @param map the map * @param tab the table for recording bin heads * @param index the index of the table being split * @param bit the bit of hash to split on */ final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order //拆分成两棵树 TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; //遍历节点 for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; //将e的next引用置空，目的是从e断开 e.next = null; //将e的hash和bit(其实就是oldCap)相与（是不是很熟悉，其实跟链表的操作类似） //为0的放到lower树 if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } //不为0放到upper树 else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } //判断lower树是否为null if (loHead != null) { //判断是否需要链表化 if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } //判断upper树是否为null if (hiHead != null) { //判断是否需要链表化 if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } } 

到这里，关于HashMap中的红黑树相关内容基本上都介绍完毕了，篇幅有点长，没法面面俱到，呼~~（放松一下）。

后话

本来想着每个方法和每个操作流程都画图解释比较直观。

但是后面花现，画图，真的是他喵了太耗费精力了。

我花4，除了动图之外，其他的图都是我自己画的。对了，开头的那棵树除外。当然，表情包也不是。

其他图示留待后面时间充裕了补上吧。

溜了溜了，有帮助的话给格子点个赞呗。