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

问题描述

问 题

原文章： https://zhuanlan.zhihu.com/p/...

各位，为什么省去了重新计算hash值 的时间？？

jdk1.7 以及jdk1.8 对于每一个元素 都只会计算一次hash值， 计算得到hash之后就将这个hash值放置到entry中，以后都不会再次计算。比如说下面的Node

问题1 ： 那么文章重为什么说省去了计算hash值呢？

问题2： jdk1.7 和jdk1.8 中扩容 不同点在于，前者使用是hash值与数组长度-1 这个掩码进行与运算，得到Entry元素的新下标位置，得到的结果直接就是下标位置 ；

jdk1.8中是使用hash值与 数组长度 进行与运算，得到的是0 或者非零。如果是0 表示新位置下标不变，如果不是0那么表示位置有变动。

从这个表面上看，jdk1.7经过位运算之后能够直接获取到新位置下标； 而1.8 需要位运算，特殊情况下还需要加法运算，性能不是略差吗？我理解不对？

为什么很多地方都说后者jdk1.8 resize 有优化很多？？

1.8中 使用红黑树相对于链表只是提高了查找性能吧，在扩容方面有什么优化处理？

解决方案

问题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)

这篇关于java - JDK1.8和jDK1.7中hashMap扩容的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！