Java8 HashMap扩容算法实例解析

时间:2021-05-20

这篇文章主要介绍了Java8 HashMap扩容算法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

Java8的HashMap扩容过程主要就是集中在resize()方法中

final Node<K,V>[] resize() { // ...省略不重要的 }

其中,当HashMap扩容完毕之后,需要对原有的数据进行转移。因为容量变大了,部分元素的位置因此要变更,因而出现了下面的这个转移过程。

转移过程大致是:依次从旧数组里取值,然后从该值对应的链表上依次取出节点,对节点取模分别放入lo链表和hi链表,当链表中节点遍历完后,分别把lo链表和hi链表放入新数组的不同位置。

在看到如下第15行时,我在想,为什么(e.hash & oldCap)== 0时就放入lo链表,否则就是hi链表?

说到这个问题,那我们就要回顾下HashMap存入新元素的过程了。看下面的第45行,可以发现插入时是使用(n - 1) & hash来计算位置的,即数组长度-1,而扩容移位是使用数组长度n计算的,那这是为什么呢?

for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } }}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // ...省略不重要的 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // ...省略不重要的}

像我们看Java8的HashMap源码,应该都应该知道HashMap的底层数组长度都是2的n方的值

那么我们就假设一个底层数组长度为8的HashMap模拟进行插入元素和扩容移位的过程

长度n=8 ----> 0x1000

n-1   ----> 0x0111

此时写入两个元素,两个元素的hash值分别为hash1 = 0x0101,hash2 = 0x1101

hash1 & n-1 = 0x0101

hash2 & n-1 = 0x0101

两个hash取模后的结果是一致的,所以它们会在同一个地方组成链表

那么此时如果要进行扩容移位呢?

hash1 & n = 0x0000

hash2 & n = 0x1000

此时两者的结果是不一样的,并且相差0x1000即10进制的8即数组长度.。

所以这也就是为什么上图15行只判断==0的原因,因为这个取模结果只有0和1两种值(数组长度是2的n次方,只有除了符号位外的最高位为1)

而两个取模结果等于数组长度,这也就是为什么上图第32和36行那么处理的原因。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章