对hashMap中,等于6还是小于6红黑树会退化为链表的理解:
当对hashMap扩容时,会调用resize方法,resize会以桶(一个哈希表下标下所有元素)为单位,把元素转移到新哈希表中, 当桶为红黑树时,会调用split方法进行红黑树的扩容移动处理。
split方法中会出现红黑树退化为链表情况(整个hashMap中也只有这个方法会出现红黑树退化为链表的情况)。
split方法中,将当前红黑树分割放入lo,hi这两个变量(treeNode类型)里。可以先理解为两条链表。当lo链表中元素<=6,会将lo转换为真正的链表(Node类型),当lo链表中元素>6,则会进行树化处理, 例如对链表中节点的left,right等进行赋值,hi树同理。
以下是split方法源码:
(树化及退树化方法省略)
```java
/**
* 从hashmap桶(一个哈希表数组某个索引下的元素,可以是单个node,
* 可以是一个链表,也可以是一颗红黑树,此时为红黑树)中将红黑树分割成两棵树,
*一颗为高位树hi,一颗为低位树lo,如果hi或者lo树节点太小,该树将会退化为链表
* 再移动到新哈希表中,该方法仅在resize()方法调用到
*
* @param map 需要扩容的map,用于红黑树退化链表时,调用当前map类型的
* replacementNode方法
* @param tab 新的哈希表,存放扩容后元素
* @param index 当前索引,扩容是从索引0的桶开始向右,以桶为单位进行扩容的
* @param bit 扩容前哈希表容量
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//红黑树在node数组上的元素
TreeNode<K,V> b = this;
//loHead 低位树头结点, loTail 低位树尾结点
TreeNode<K,V> loHead = null, loTail = null;
//hiHead 高位树头结点, hiTail 高位树尾结点
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//红黑树为链表转换而成,hashmap链表节点(node类型)在转换成红黑树(treeNode类型)时
//保留了原有node节点的变量(next等等),数据,用于进行迭代器遍历,及退化为链表
//虽然是红黑树,不过保留了next,可以按照链表方式进行遍历
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//如果当前节点hash与运算扩容前map容量为0,代表扩容后索引位置不变
//扩容后索引位置不变的节点放在低位树中
if ((e.hash & bit) == 0) {
//尾结点为空,此时还未放入输入,设置头结点为e
if ((e.prev = loTail) == null)
loHead = e;
//尾结点不为空,此时已有数据,将尾结点next指向当前数据(尾插法)
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//lc,hc从0开始增加,lo树中有6个元素,则lc=6
//hi树有6个元素,则hc=6
if (loHead != null) {
//hashMap中UNTREEIFY_THRESHOLD设置为6
//lc<=6,将lo树退化为链表,也就是lc树中有6个元素,就会退化为链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
/**lc>6 将lc转化为真正的红黑树结构
*前面lc只是next赋值了,还只是链表结构
*/红黑树需要对parent,left,right等属性赋值
else {
tab[index] = loHead;
if (hiHead != null)
loHead.treeify(tab);
}
}
//hi树与lo同理
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
/**
* hi树与lo树区别:
* hi树放在扩容后哈希表的(旧哈希表index+旧哈希表容量)索引位置
* lo树放在扩容后哈希表的(旧哈希表index)索引位置
*/
结论:
1.调用到了resize方法才可能会退化,没调用即使长度小于6也不会退化
2.小于等于6,进行退化,是针对分割后lo与hi这两条链表而言的,不能等价于整个树的长度。
3.只有lo链表或者hi链表长度小于等于6,才会进行退化(此时的退化是指将当前链表节点类型从treeNode转为Node)
4.lo,hi链表大于6会进行树化的具体操作
5.如果lo为null,不会进行任何操作,hi同理。