HashMap1.7和1.8的区别

发布时间:2024年01月20日

HashMap1.7和1.8的区别

1.JDK1.7用的是头插法,而JDK1.8及之后使用的都是尾插法

那么为什么要这样做呢?因为JDK1.7是用单链表进行的纵向延伸,当采用头插法时,再多线程环境下并发扩容的时候,会容易出现环形链表死循环问题。但是在JDK1.8之后使用尾插法,能够避免出现逆序且链表死循环的问题。

2.扩容流程不同:

1.8是扩容前插入键值,连同旧的键值一起转移,一起计算,1.7是扩容后,扩容后进行插入,旧数据转移到新的数组之后,然后再单独计算插入的位置。为什么1.8是插入之后再整体计算扩容,主要是为了减少红黑树和链表来回转换的频率

3.扩容后数据存储位置的计算方式也不一样:

要说清楚这个,先得说说HASHMAP如何求桶的位置

HashMap求桶的位置一共分为三个过程:

1)求key的hashcode 2)将hashcode的高16位和低16位进行异或操作。

至此我们完成了hash方法,求得了该元素的hash值。源码在下方

static final int hash(Object key) {
 ?  int h;
 ?  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3)(n - 1) & hash ,将hash值与length-1进行与操作,求桶的位置

 if ((p = tab[i = (n - 1) & hash]) == null)
 ? ? ? ? ?  tab[i] = newNode(hash, key, value, null);

无论是JDK7还是JDK8,HashMap的扩容都是每次扩容为原来的两倍,即会产生一个新的数组newtable,我们需要把原来数组中的元素全部放到新的只不过元素求桶的位置的方法不太一样。

在JDK7中就是按照我上述写的三个步骤重新对元素求桶的位置,但是第三步与的值是新的数组的长度-1,也就是newCap-1。

但是JDK8中就不是和newCap,而是直接和oldCap进行与运算,也就是与旧数组的长度(oldCap)进行与操作。下面的是伪代码:

if ((e.hash & oldCap) == 0) {
newTab[j] = loHead;
}else{
?
newTab[j + oldCap] = hiHead;
}

与oldCap与的结果如果是0,那么就代表当前元素的桶位置不变。 反之,那么扩容后桶的位置就是原位置+原数组长度(oldCap)

4.数据结构不同

JDK1.7的时候使用的是数组+ 单链表的数据结构。但是在JDK1.8及之后时,使用的是数组+链表+红黑树的数据结构(当链表的深度达到8的时候,也就是默认阈值,就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O(n)变成O(logN)提高了效率),小于6的时候,又会转换为链表。为什么是8,容器中节点分布在hash桶中的频率遵循泊松分布,桶的长度超过8的概率非常非常小。

文章来源:https://blog.csdn.net/Fxdll/article/details/135709051
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。