且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

java - JDK1.8和jDK1.7中hashMap扩容的问题

更新时间:2022-10-14 23:05:41

问题1 :文章应该说明的有问题。并没有省去了计算hash值,
如问题2的描述:

JDK7使用是hash值与数组长度-1 这个掩码进行与运算,得到Entry元素的新下标位置,得到的结果直接就是下标位置 ;
Jdk1.8中是使用hash值与 数组长度 进行与运算,得到的是0 或者非零。如果是0
表示新位置下标不变,如果不是0那么表示位置有变动,如果有变动下标位置是原位置加上数组长度

从寻找新的下标位置上看,并没有省掉计算时间,反而附加一个加法运算。

问题2:
LZ理解的没有问题。JDK8中resize方法并没有比JDK7中性能更好。Entry的key最坏的情况下在Map中是一个链表,JDK8为优化这个问题在链表数目大于8的时候转化为红黑树,但是resize中,又必需拆解和重建红黑树。

拆解过程

和普通的Entry链表一样,顺序遍历(此时只用它的next指针),使用上述判断方式,分离成需要变动和不需要变动的两个列表。

重建过程

如果列表长度小于8,去掉树结构指针,维持成一个链表
如果列表长度大于8,重新构造成一棵树。
总的来看,JDK7的resize时间复杂度n,JDK8的复杂度为nlog(n)