博客

HashMap中链表树化的条件

第一次写这么长 如有错误 欢迎大家指正

测试用到的Student对象已经重写的hashcode()方法和equals()方法

当map的容量大于等于64 且链表的长度大于等于8时 再次向这个链表中put元素 这个链表就会进行树化

可以看出 这是一个 容量为64 且已经在索引位置为

1

的位置有一个长度为8的链表 若此时再次往索引位置为1的位置放元素 链表就会树化


再次往索引位置为1 地方放一个Student对象:







判断是否进行树化的代码:




p刚开始指向table表中索引位置为1 的元素 然后用e指向p.next 判断e是否为空 (就是判断p.next是否为空) 若为空 直接将要添加的元素 挂载p.next的位置上即可

这里因为p所在的索引位置已经有一个长度为8的链表 所以不会进入到第一个if判断

若p.next不为null 经过for循环和这两个if判断



p不断向下移动 直到移动到链表中的第八个元素 此时p.next 就为null了 进入第一个if判断 此时经过了8次循环

binCount

从0变为了7 此时就进入了

if (binCount >= TREEIFY_THRESHOLD - 1)

判断 **TREEIFY_THRESHOLD ** 为8 就是判断是否进行树化的一个属性

这个判断条件成立 就会进行树化

 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
      treeifyBin(tab, hash);
       break;

第二个if判断

若要存放的元素的hash值 相等 且两个经过equals为true

就表示存放的元素和链表中这个位置的元素是相同的 直接break p指针不再移动

容量大于等于64 和 链表长度大于等于8 这两个条件缺一不可 缺一个就不会进行树化

容量小于64 而链表长度大于等于8 的情况:

table表的容量为16 而索引位置为1的地方有一个长度为8的链表 若此时再次往这个位置存储元素 链表不会进行树化 而是见table表的容量扩大二倍

关键点在于:


判断table表的长度是否到达了最小树化容量

static final int MIN_TREEIFY_CAPACITY = 64;


若没有达到 不会进行树化 而是将table表扩容