HashMap底层的扩容机制（以及2倍扩容的原因）

2023-11-20 21:06| 来源: 网络整理| 查看: 265

文章目录 HashMap底层的扩容机制resize扩容resize源码源码文字说明HashMap底层为什么是2倍扩容？

HashMap底层的扩容机制 resize扩容

HashMap会在两个地方进行resize(扩容): 在这里插入图片描述

1 ，HashMap实行了懒加载, 新建HashMap时不会对table进行赋值, 而是到第一次插入时, 进行resize时构建table; 2，当HashMap.size 大于 threshold时, 会进行resize;threshold的值，当第一次构建时, 如果没有指定HashMap.table的初始长度, 就用默认值16, 否则就是指定的值; 然后不管是第一次构建还是后续扩容, threshold = table.length * loadFactor;

在Java8的扩容中，不是简单的将原数组中的每一个元素取出进行重新hash映射，而是做移位检测。所谓移位检测的含义具体是针对HashMap做映射时的&运算所提出的，通过上文对&元算的分析可知，映射的本质即看hash值的某一位是0还是1，当扩容以后，会相比于原数组多出一位做比较，由多出来的这一位是0还是1来决定是否进行移位，而具体的移位距离，也是可知的，及位原数组的大小，我们来看下表的分析，假定原表大小16。

在这里插入图片描述

由上表可知，是否移位，由扩容后表示的最高位是否1为所决定，并且移动的方向只有一个，即向高位移动。因此，可以根据对最高位进行检测的结果来决定是否移位，从而可以优化性能，不用每一个元素都进行移位，

resize源码 final Node[]resize(){ Node[]oldTab=table; int oldCap=(oldTab==null)?0:oldTab.length; int oldThr=threshold; int newCap,newThr=0; if(oldCap>0){ // 如果当前哈希桶容量超过最大值2^30，直接返回旧哈希桶大小 // 到达上线 threshold 设置最大阈值返回表示之后就不再扩容了，随便存，随便hash冲 // 突去，就这么大，无限增加红黑树节点了 if(oldCap>=MAXIMUM_CAPACITY){ threshold=Integer.MAX_VALUE; return oldTab; } // 按照两倍扩容后，如果容量没有达到上限 // 并且旧容量已经超过16 // newCap翻倍，则按照两倍的方式扩容 else if((newCap=oldCap float ft=(float)newCap*loadFactor; // 如果新容量和阈值都是在2^30以内，下一次库哦哦荣的阈值则为ft // 否则改为最大值 newThr=(newCap for(int j=0;j oldTab[j]=null; if(e.next==null) newTab[e.hash&(newCap-1)]=e; else if(e instanceof TreeNode) ((TreeNode)e).split(this,newTab,j,oldCap); else{ // preserve order Node loHead=null,loTail=null; Node hiHead=null,hiTail=null; Node 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; } } } } } return newTab; } 源码文字说明

1 如果table == null, 则为HashMap的初始化, 生成空table返回即可;

2 如果table不为空, 需要重新计算table的长度, newLength = oldLength

【本文地址】

公司简介

联系我们