前一篇文章中提到，当执行put操作的时候，会出现桶碰撞的情况，这时候桶索引值相同的键值对会以一个链表的形式存在于hash桶中，但是当链表长度很长的时候，查找的性能会很低，JDK1.8中对此进行了优化，当链表的长度超过TREEIFY_THRESHOLD（8）的时候，链表会树化，即通过treeifyBin()方法转换成红黑树。
在看代码之前，我们回忆一下二叉搜索树的插入逻辑insert(Node node, Node root)，将node结点插入到root树中
1、如果root == null，则root = node；
2、从根结点开始遍历，如果node.value < 当前结点.value，插入到左子树，否则插入到右子树，
3、如果当前结点的左儿子为空，且node.value < 当前结点.value，插入到当前结点的左儿子，
4、如果当前结点的右儿子为空，且node.value > 当前结点.value，插入到当前结点的右儿子。
现在具体来看看treeifyBin()的代码：
static final int MIN_TREEIFY_CAPACITY = 64;
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//这里还有一个限制条件，当table的长度小于MIN_TREEIFY_CAPACITY（64）时，只是进行扩容
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 {
//将链表中的结点转换为树结点，形成一个新链表
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) //将新的树结点链表赋给第index个桶
hd.treeify(tab); //执行 TreeNode中的treeify()方法
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
从上面的代码可以看出，链表长度大于8而且整个map中的键值对大于等于MIN_TREEIFY_CAPACITY (64)时，才进行链表到红黑树的转换。
上面的代码很简单，重点看一下treeify( )方法：
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 void treeify(Node<K,V>[] tab) {//将链表转换成红黑树
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {//遍历链表中的每一个TreeNode，当前结点为x
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { //对于第一个树结点，当前红黑树的root == null，所以第一个结点是树的根，设置为黑色
x.parent = null;
x.red = false;
root = x;
}
else { //对于余下的结点：
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root; ; ) {//从根结点开始遍历，寻找当前结点x的插入位置
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) //如果当前结点的hash值小于根结点的hash值，方向dir = -1；
dir = -1;
else if (ph < h) //如果当前结点的hash值大于根结点的hash值，方向dir = 1；
dir = 1;
else if ((kc == null && //如果x结点的key没有实现comparable接口，或者其key和根结点的key相等（k.compareTo(x) == 0）仲裁插入规则
(kc = comparableClassFor(k)) == null) || //只有k的类型K直接实现了Comparable<K>接口，才返回K的class，否则返回null，间接实现也不行。
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk); //仲裁插入规则
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { //如果p的左右结点都不为null，继续for循环，否则执行插入
x.parent = xp;
if (dir <= 0) //dir <= 0，插入到左儿子
xp.left = x;
else //否则插入到右结点
xp.right = x;
root = balanceInsertion(root, x); //插入后进行树的调整，使之符合红黑树的性质
break;
}
}
}
}
moveRootToFront(tab, root); //Ensures that the given root is the first node of its bin.
}
}
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
从上面的代码可以看出，将结点插入到红黑树的时候，比较的是hash值，然后根据比较结果判断插入左子树还是右子树。
总结
-
整个过程大体上分为两部分：插入树结点元素，具体可以参考二叉搜索树的插入操作；插入完之后开始调整红黑树，使之符合红黑树的特性。
-
插入的时候，先比较key的hash值来决定插入方向，如果hash值相等的话，再比较
compare方法，如果key所属对象没有直接实现Comparable接口，或者compare方法返回0，执行tieBreakOrder，比较两个key所属Class的name，如果还相等，也就是两个对象是同一个类型，那么调用本地方法为两个对象生成hashCode值，再进行比较，hashCode相等的话返回-1。
参考
1、https://blog.csdn.net/qpzkobe/article/details/79533237
2、https://blog.csdn.net/weixin_42340670/article/details/80673127
网友评论