Node.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; } } }
treeifyBin 链表树化
如果 hashmap 的长度小于 64 会优先选择拓容，否则会当前冲突 key 所在的结构由链表转换为红黑树。 这个是 jdk 1.8 才有的新特征，hashmap 在 hash 冲突后可能由链表变化为红黑树结构。这样做的目的是为了提高读写效率。
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 不一定树化还可能是拓容，需要看数组的长度是否小于 64 MIN_TREEIFY_CAPACITY if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // hd 头节点, tl 尾节点 TreeNode<K,V> hd = null, tl = null; do { // 将链表转换为树结构 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); } }
replacementTreeNode 方法
replacementTreeNode 方法主要是将 Node 转换为 TreeNode
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); }
TreeNode#treeify 方法
treeify 方法主要是将树结构转换为红黑树。
final void treeify(Node<K,V>[] tab) { // 根节点默认为 null TreeNode<K,V> root = null; // 链表遍历，x 指向当前节点，next 指向下一个节点 for (TreeNode<K,V> x = this, next; x != null; x = next) { // 下一个节点 next = (TreeNode<K,V>)x.next; // 设置当前节点的 left, right 为 null x.left = x.right = null; // 如果没有根节点 if (root == null) { // 当前父节点为 null x.parent = null; // 当前红色节点属性设置为 false (把当前节点设置为黑色) x.red = false; // 根节点指向当前节点 root = x; } // 如果已经存在根节点 else { // 获取当前链表的 key K k = x.key; // 获取当前节点的 hash int h = x.hash; // 定义当前 key 所属类型 Class<?> kc = null; // 从根节点开始遍历，此遍历设置边界，只能从内部跳出 for (TreeNode<K,V> p = root;;) { // dir 标识方向（左右）ph 标识当前节点的 hash 值 int dir, ph; // 当前节点的 key K pk = p.key; // 如果当前节点 hash 值大于当前 链表节点的 hash 值 if ((ph = p.hash) > h) // 标识当前节链表节点会放在当前红黑树节点的左侧 dir = -1; else if (ph < h) // 右侧 dir = 1; // 如果两个节点的 key 的 hash 值相等，那么通过其他方式进行比较 // 如果当前链表节点的 key 实现了comparable 接口，并且当前树节点和链表节点是相同的 class 实例，那么通过 comparable 比较 // 如果还是相等再通过 tieBreakOrder 比较一次 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; // 保存当前树节点 // 如果 dir 小于等于 0: 当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左子节点， // 也可能是左子节点或者右子节点或者更深层次的节点 // 如果dir 大于等于 0: 当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右子节点， // 也可能是右子节点或者左子节点或者更深层次的节点 // 如果当前树节点不是叶子，那么最终以当前树节点的左子节点或者右子节点为起始几点，然后再重新开始寻找自己当前链表节点的位置。 // 如果当前树节点就是叶子节点，那么更具 dir 的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。 // 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了 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; } } } } // 把所有的链表节点都遍历之后，最终构造出来的树可能是经历多个平衡操作，根节点目前到底是链表的那个节点是不确定的 // 因为我们需要基于树来做查找，所以就应该把 tab[N] 得到的对象一定是根节点对象，而且是链表的第一个节点对象，所以要做对应的调整。 // 把红黑树的节点设置为所在数组槽的第一个元素 // 说明: TreeNode 既是一个红黑树也是一个双向链表 // 这个方法做的事情是保证树根节点一定要成为链表的首节点 moveRootToFront(tab, root); }
balanceInsertion 树平衡
这个方法分析之前，我们可以先看看红黑树的规则：红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
- 性质1. 节点是红色或黑色。
- 性质2. 根节点是黑色。
- 性质3. 所有叶子都是黑色。（叶子是NIL结点）
- 性质4. 每个红色节点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
- 性质5. 从任一节节点其每个叶子的所有路径都包含相同数目的黑色节点。
// root 为根节点 // x 为需要插入的节点 // 最后返回的是一个平很后的根节点 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { // 查询节点标记为红色 x.red = true; // 设置一个只可以内部退出的循环 // 变量说明: // xp 当前节点, xpp 父节点的父节点, xppl 父节点的父节点的左节点, xppr 父节点的父节点的右节点 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { // 如果父节点为空， 说明当前节点就是根节点，那么直接把当前接待你标记为黑色返回当前节点。 if ((xp = x.parent) == null) { x.red = false; return x; } // 如果当前节点为黑设色并且当前父节点为 null, 或者 // 父节点为红色，但是 xpp 节点为空 else if (!xp.red || (xpp = xp.parent) == null) return root; // 当前节点等于 xppl if (xp == (xppl = xpp.left)) { //xppr != null 并且 是红色 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; xp.red = false; xpp.red = true; x = xpp; // 当前节点等于 xpp, 进入下一次循环 } else { if (x == xp.right) { // 当前节点是父节点的右子节点 root = rotateLeft(root, x = xp); //父节点左旋 xpp = (xp = x.parent) == null ? null : xp.parent; // 获取 xpp } if (xp != null) { // 父节点不为空 xp.red = false; // 父节点设置为黑色 if (xpp != null) { // xpp 不为空 xpp.red = true; // xpp 为红色 root = rotateRight(root, xpp); // xpp 右旋转 } } } } else { // 如果 xp 是 xpp 的右节点 if (xppl != null && xppl.red) { // xppl 不为空，并且为红色 xppl.red = false; // xppl 设置为黑色 xp.red = false; // 父节点为黑色 xpp.red = true; // xpp 为红色 x = xpp; // x = xpp 进入下次循环 } else { if (x == xp.left) { // 当前节点为父节点的左子节点 root = rotateRight(root, x = xp); // 根节点你右旋转 xpp = (xp = x.parent) == null ? null : xp.parent; // xpp = xp.parent } if (xp != null) { // xp != null xp.red = false; // xp 为黑色 if (xpp != null) { // xpp != null xpp.red = true; // xpp 为红色 root = rotateLeft(root, xpp); // 左旋 } } } } } } // 节点左旋转 // root 当前根节点 // p 指定选装的节点 // 返回旋转后的根接待你（平衡涉及左旋右旋根根节点改变，所以需要返回最新的根节点） // 示意图 // pp pp // | | // p ---> r // / \ / \ // l r p rr // / \ / \ // rl rr l rl // 旋转做了几件事情？ // 1. 将 rl 设置为 p 的子接待你，将 rl 设置为父节点 p // 2. 将 r 的父节点设置 pp, 将 pp 的左子节点设或者右子接待你设置为 r // 3. 将 r 的左子节点设置为 p, 将 p 的父节点设置为 r static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> r, pp, rl; // 左旋的节点以及需要左旋的节点的右节点不为空 if (p != null && (r = p.right) != null) { // 要左旋转的右子节点 = rl , if ((rl = p.right = r.left) != null) // 设置 rl 父亲节点设置为 p rl.parent = p; // 将 r 的父节点设置为 p 的父节点，如果 pp == null if ((pp = r.parent = p.parent) == null) // 染黑 (root = r).red = false; else if (pp.left == p) // 判断父节点是在 pp 的左边还是右边 pp.left = r; // 如果是左子节点，把 pp.letf = r else pp.right = r; // 如果是右子节点, pp.reight = r r.left = p; // 最后将 r的左子节点设置为 p p.parent = r; // 最后将 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 方法
把所有的链表节点都遍历之后，最终构造出来的树可能是经历多个平衡操作，根节点目前到底是链表的那个节点是不确定的。 因为我们需要基于树来做查找，所以就应该把 tab[N] 得到的对象一定是根节点对象，而且是链表的第一个节点对象，所以要做对应的调整。 把红黑树的节点设置为所在数组槽的第一个元素，这个方法做的事情是保证树根节点一定要成为链表的首节点。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { int n; // root 节点不为空， 并且表不为空， 并且数组长度大于 0 if (root != null && tab != null && (n = tab.length) > 0) { // 当前 Node 所在槽位 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; // rp 前驱节点为 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) // 原来的头节点前驱节点指向新的头节点 root 节点 first.prev = root; // root 节点的后驱节点指向之前的头节点 root.next = first; // root 由于是头节点所以前驱节点为 null root.prev = null; } assert checkInvariants(root); } }
