Java源码解析HashMap的resize函数

2023-09-01 21:26:04 235

HashMap的resize函数，用于对HashMap初始化或者扩容。

首先看一下该函数的注释，如下图。从注释中可以看到，该函数的作用是初始化或者使table的size翻倍。如果table是null，那么就申请空间进行初始化。否则，因为我们在使用2的指数的扩张，在原来table的每个位置的元素，在新的table中，他们要么待在原来的位置，要么移动2的指数的偏移。从这里可以看出，扩容前table每个位置上如果有多个元素，元素之间组成链表时，在扩容后，该链表中的元素，有一部分会待在原地，剩下的元素会往后移动2的指数的偏移。

/**
*Initializesordoublestablesize.Ifnull,allocatesin
*accordwithinitialcapacitytargetheldinfieldthreshold.
*Otherwise,becauseweareusingpower-of-twoexpansion,the
*elementsfromeachbinmusteitherstayatsameindex,ormove
*withapoweroftwooffsetinthenewtable.
*@returnthetable
**/

接下来看一下resize的代码，如下

finalNode[]resize(){
Node[]oldTab=table;
intoldCap=(oldTab==null)?0:oldTab.length;
intoldThr=threshold;
intnewCap,newThr=0;
if(oldCap>0){
if(oldCap>=MAXIMUM_CAPACITY){
threshold=Integer.MAX_VALUE;
returnoldTab;
}
elseif((newCap=oldCap<<1)=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr<<1;//doublethreshold
}
elseif(oldThr>0)//initialcapacitywasplacedinthreshold
newCap=oldThr;
else{//zeroinitialthresholdsignifiesusingdefaults
newCap=DEFAULT_INITIAL_CAPACITY;
newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);
}
if(newThr==0){
floatft=(float)newCap*loadFactor;
newThr=(newCap[]newTab=(Node[])newNode[newCap];
table=newTab;
if(oldTab!=null){
for(intj=0;je;
if((e=oldTab[j])!=null){
oldTab[j]=null;
if(e.next==null)
newTab[e.hash&(newCap-1)]=e;
elseif(einstanceofTreeNode)
((TreeNode)e).split(this,newTab,j,oldCap);
else{//preserveorder
NodeloHead=null,loTail=null;
NodehiHead=null,hiTail=null;
Nodenext;
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;
}
}
}
}
}
returnnewTab;
}

扩容的过程分为两部分，第一部分是对threshold和table的初始化或者重新计算，第二部分是对HashMap中的元素进行重新放置。初始化的过程比较简单，基本就是使用默认值，初始化HashMap的各个成员变量。重新计算时，是会申请一个2倍大小的Node数组，用作的新的HashMap的存储空间。

之后的过程是，对原来HashMap中的每一个位置进行遍历，把该位置上的各个元素重新放置到新的table中。所以在循环的过程中，会定义loHead，loTail，hiHead，hiTail，分别表示留着原地的链表的头和尾，移动到更高位置的链表的头和尾。这里需要注意一点，在jdk1.8中，扩容后链表中元素的顺序和扩容前链表中元素的位置，是相同的，并不会像jdk1.7那样会发生逆序。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接

Java源码解析HashMap的resize函数

热门推荐

随机推荐