Java HashMap源码及并发环境常见问题解决

2023-07-16 16:36:03 92

HashMap源码简单分析：

1一切需要从HashMap属性字段说起：

/**Thedefaultinitialcapacity-MUSTbeapoweroftwo.初始容量*/
staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka16

/**
*Themaximumcapacity,usedifahighervalueisimplicitlyspecified
*byeitheroftheconstructorswitharguments.
*MUSTbeapoweroftwo<=1<<30.最大容量
*/
staticfinalintMAXIMUM_CAPACITY=1<<30;

/**
*Theloadfactorusedwhennonespecifiedinconstructor.*默认的负载因子，当map的size>=负载因子*capacity时候并且插入元素时候的table[i]!=null进行扩容*扩容判断逻辑：java.util.HashMap#addEntry函数中*
*/
staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;

/**
*Anemptytableinstancetosharewhenthetableisnotinflated.
*/
staticfinalEntry[]EMPTY_TABLE={};

/**
*Thetable,resizedasnecessary.LengthMUSTAlwaysbeapoweroftwo.哈希表
*/
transientEntry[]table=(Entry[])EMPTY_TABLE;

/**
*Thenumberofkey-valuemappingscontainedinthismap.map的大小
*/
transientintsize;

/**
*Thenextsizevalueatwhichtoresize(capacity*loadfactor).
*@serial
*/
//Iftable==EMPTY_TABLEthenthisistheinitialcapacityatwhichthe
//tablewillbecreatedwheninflated.扩容的阈值=capacity*负载因子
intthreshold;

/**
*Theloadfactorforthehashtable.负载因子，默认是0.75，可以在创建HashMap时候通过构造函数指定
*
*@serial
*/
finalfloatloadFactor;

/**
*ThenumberoftimesthisHashMaphasbeenstructurallymodified
*Structuralmodificationsarethosethatchangethenumberofmappingsin
*theHashMaporotherwisemodifyitsinternalstructure(e.g.,
*rehash).ThisfieldisusedtomakeiteratorsonCollection-viewsof
*theHashMapfail-fast.(SeeConcurrentModificationException).*修改次数：例如进行rehash或者返回hashMap视图时候如果发生修改可以fast-fail
*/
transientintmodCount;

/**
*Thedefaultthresholdofmapcapacityabovewhichalternativehashingis
*usedforStringkeys.Alternativehashingreducestheincidenceof
*collisionsduetoweakhashcodecalculationforStringkeys.
*
*Thisvaluemaybeoverriddenbydefiningthesystemproperty
*{@codejdk.map.althashing.threshold}.Apropertyvalueof{@code1}
*forcesalternativehashingtobeusedatalltimeswhereas
*{@code-1}valueensuresthatalternativehashingisneverused.*rehash时候判断的一个阈值
*/
staticfinalintALTERNATIVE_HASHING_THRESHOLD_DEFAULT=Integer.MAX_VALUE;

2:接下来查看一下HashMap的put方法：

/**
*Associatesthespecifiedvaluewiththespecifiedkeyinthismap.
*Ifthemappreviouslycontainedamappingforthekey,theold
*valueisreplaced.
*
*@paramkeykeywithwhichthespecifiedvalueistobeassociated
*@paramvaluevaluetobeassociatedwiththespecifiedkey
*@returnthepreviousvalueassociatedwithkey,or
*nulliftherewasnomappingforkey.
*(Anullreturncanalsoindicatethatthemap
*previouslyassociatednullwithkey.)
*/
publicVput(Kkey,Vvalue){
if(table==EMPTY_TABLE){//初始化哈希表
inflateTable(threshold);
}
if(key==null)//如果key为null存储到table[0]位置
returnputForNullKey(value);
inthash=hash(key);//计算hash值
inti=indexFor(hash,table.length);//计算entry在table中的位置
//for循环逻辑用于修改key对应的value的
for(Entrye=table[i];e!=null;e=e.next){
Objectk;
if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
VoldValue=e.value;
e.value=value;
e.recordAccess(this);
returnoldValue;//如果是更新返回旧值
}
}
//修改次数++
modCount++;
//添加元素到哈希表中
addEntry(hash,key,value,i);
//如果是添加元素则返回null
returnnull;
}

3put中调用的inflateTable方法：

/**
*Inflatesthetable.
*/
privatevoidinflateTable(inttoSize){
//Findapowerof2>=toSize
//计算大于等于toSize的最小的2的整数次幂的值
intcapacity=roundUpToPowerOf2(toSize);
//计算扩容阈值
threshold=(int)Math.min(capacity*loadFactor,MAXIMUM_CAPACITY+1);
//初始化哈希表
table=newEntry[capacity];
//更新一下rehash的判断条件，便于以后判断是否rehash
initHashSeedAsNeeded(capacity);
}

4put方法中调用的indexFor方法：

/**
*Returnsindexforhashcodeh.返回哈希值对应的哈希表索引
*/
staticintindexFor(inth,intlength){
//assertInteger.bitCount(length)==1:"lengthmustbeanon-zeropowerof2";
//使用&操作，而不使用取余原因：均匀分布在哈希表中。length-1目的是：由于table的长度都是2的整数次幂进行扩容，length-1的二进制全是1，计算效率高
returnh&(length-1);
}

5put方法中调用的addEntry方法：

/**
*Addsanewentrywiththespecifiedkey,valueandhashcodeto
*thespecifiedbucket.Itistheresponsibilityofthis
*methodtoresizethetableifappropriate.
*
*Subclassoverridesthistoalterthebehaviorofputmethod.
*/
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
//判断是否扩容，只有size大于等于阈值而且当前插入table[i]!=null(就是able[i]已经被占用则扩容)
if((size>=threshold)&&(null!=table[bucketIndex])){
resize(2*table.length);
hash=(null!=key)?hash(key):0;
//如果需要扩容的话则需要更新再次重新计算哈希表位置
bucketIndex=indexFor(hash,table.length);
}
//将值插入到哈希表中
createEntry(hash,key,value,bucketIndex);
}

6addEntry方法中调用的createEntry方法：

/**
*LikeaddEntryexceptthatthisversionisusedwhencreatingentries
*aspartofMapconstructionor"pseudo-construction"(cloning,
*deserialization).Thisversionneedn'tworryaboutresizingthetable.
*
*SubclassoverridesthistoalterthebehaviorofHashMap(Map),
*clone,andreadObject.
*/
voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){
//获取到哈希表指定位置
Entrye=table[bucketIndex];
//链表的头插入方式进行插入，插入逻辑在Entry的构造器中。然后将新节点存储到table[bucketIndex]中
table[bucketIndex]=newEntry<>(hash,key,value,e);
size++;//更新size即可
}

Entry构造器：

/**
*
*@paramhhash值
*@paramkkey
*@paramvvalue
*@paramn原始链表
*/
Entry(inth,Kk,Vv,Entryn){
value=v;
//将原始链表接该节点后面
next=n;
key=k;
hash=h;
}

7接下来看一下java.util.HashMap#addEntry扩容机制：

当进行扩容时候需要重新计算哈希值和在哈希表中的位置。

voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
//满足扩容条件进行扩容
if((size>=threshold)&&(null!=table[bucketIndex])){
//扩容，2倍进行扩容
resize(2*table.length);
//重新计算哈数值
hash=(null!=key)?hash(key):0;
//重新计算哈希表中的位置
bucketIndex=indexFor(hash,table.length);
}

createEntry(hash,key,value,bucketIndex);
}

接下来看一下java.util.HashMap#resize方法：

/**
*Rehashesthecontentsofthismapintoanewarraywitha
*largercapacity.Thismethodiscalledautomaticallywhenthe
*numberofkeysinthismapreachesitsthreshold.
*
*IfcurrentcapacityisMAXIMUM_CAPACITY,thismethoddoesnot
*resizethemap,butsetsthresholdtoInteger.MAX_VALUE.
*Thishastheeffectofpreventingfuturecalls.
*
*@paramnewCapacitythenewcapacity,MUSTbeapoweroftwo;
*mustbegreaterthancurrentcapacityunlesscurrent
*capacityisMAXIMUM_CAPACITY(inwhichcasevalue
*isirrelevant).
*/
voidresize(intnewCapacity){
Entry[]oldTable=table;
intoldCapacity=oldTable.length;
if(oldCapacity==MAXIMUM_CAPACITY){//判断当前old容量是否最最大容量，是的话更新阈值
threshold=Integer.MAX_VALUE;
return;
}
//创建新的表
Entry[]newTable=newEntry[newCapacity];
//元素转移，根据initHashSeedAsNeeded结果判断是否进行rehash
transfer(newTable,initHashSeedAsNeeded(newCapacity));
//新表赋给table
table=newTable;
//更新阈值
threshold=(int)Math.min(newCapacity*loadFactor,MAXIMUM_CAPACITY+1);
}

关于HashMap在并发情况下的常见问题，其实在多线程环境下使用HashMap本来就是有风险错误的，但是一般面试却喜欢这么问，下面列举一下自己印象中的常见问题：

1：在进行扩容时候，其他线程是否可以进行进行插入操作（多线程环境下可能会导致HashMap进入死循环，此处暂不考虑）？

答：首先HashMap就不是一个线程安全的容器，所以在多线程环境下使用就是错误的。其次在扩容时候可以进行插入的，但是不安全。例如：

当主线程在调用transfer方法进行复制元素：

/**
*TransfersallentriesfromcurrenttabletonewTable.
*/
voidtransfer(Entry[]newTable,booleanrehash){
intnewCapacity=newTable.length;
for(Entrye:table){
while(null!=e){
Entrynext=e.next;
if(rehash){
e.hash=null==e.key?0:hash(e.key);
}
inti=indexFor(e.hash,newCapacity);
e.next=newTable[i];
newTable[i]=e;
e=next;
}
}
}

此时另一个线程在添加新元素是可以的，新元素添加到table中。如果子线程需要扩容的话可以进行扩容，然后将新容器赋给table。而此时主线程转移元素的工作就是将table中元素转移到newTable中。注意main线程的transfer方法：

如果main线程刚进入transfer方法时候newTable大小是32的话，由于子线程的添加操作导致table此时元素如果有128的话。则128个元素就会存储到大小为32的newTable中（此处不会扩容）。这就会导致HashMap性能下降！！！

可以使用多线程环境进行debug查看即可确定（推荐Idea的debug，的确强大，尤其是EvaluateExpression功能）。

2：进行扩容时候元素是否需要重新Hash？

这个需要具体情况判断，调用initHashSeedAsNeeded方法判断（判断逻辑这里先不介绍）。

/**
*Rehashesthecontentsofthismapintoanewarraywitha
*largercapacity.Thismethodiscalledautomaticallywhenthe
*numberofkeysinthismapreachesitsthreshold.
*
*IfcurrentcapacityisMAXIMUM_CAPACITY,thismethoddoesnot
*resizethemap,butsetsthresholdtoInteger.MAX_VALUE.
*Thishastheeffectofpreventingfuturecalls.
*
*@paramnewCapacitythenewcapacity,MUSTbeapoweroftwo;
*mustbegreaterthancurrentcapacityunlesscurrent
*capacityisMAXIMUM_CAPACITY(inwhichcasevalue
*isirrelevant).
*/
voidresize(intnewCapacity){
Entry[]oldTable=table;
intoldCapacity=oldTable.length;
if(oldCapacity==MAXIMUM_CAPACITY){
threshold=Integer.MAX_VALUE;
return;
}

Entry[]newTable=newEntry[newCapacity];
//initHashSeedAsNeeded判断是否需要重新Hash
transfer(newTable,initHashSeedAsNeeded(newCapacity));
table=newTable;
threshold=(int)Math.min(newCapacity*loadFactor,MAXIMUM_CAPACITY+1);
}

然后进行转移元素：

/**
*TransfersallentriesfromcurrenttabletonewTable.
*/
voidtransfer(Entry[]newTable,booleanrehash){
intnewCapacity=newTable.length;
//多线程环境下，如果其他线程导致table快速扩大。newTable在此处无法扩容会导致性能下降。但是如果后面有再次调用put方法的话可以再次触发resize。
for(Entrye:table){
while(null!=e){
Entrynext=e.next;
if(rehash){//判断是否需要重新Hash
e.hash=null==e.key?0:hash(e.key);
}
inti=indexFor(e.hash,newCapacity);
e.next=newTable[i];
newTable[i]=e;
e=next;
}
}
}

3：如何判断是否需要重新Hash？

/**
*Initializethehashingmaskvalue.Wedeferinitializationuntilwe
*reallyneedit.
*/
finalbooleaninitHashSeedAsNeeded(intcapacity){

//hashSeed降低hash碰撞的hash种子，初始值为0
booleancurrentAltHashing=hashSeed!=0;
//ALTERNATIVE_HASHING_THRESHOLD：当map的capacity容量大于这个值的时候并满足其他条件时候进行重新hash
booleanuseAltHashing=sun.misc.VM.isBooted()&&(capacity>=Holder.ALTERNATIVE_HASHING_THRESHOLD);
//TODO异或操作，二者满足一个条件即可rehash
booleanswitching=currentAltHashing^useAltHashing;
if(switching){
//更新hashseed的值
hashSeed=useAltHashing?sun.misc.Hashing.randomHashSeed(this):0;
}
returnswitching;
}

4：HashMap在多线程环境下进行put操作如何导致的死循环？

死循环产生时机：

当两个线程同时需要进行扩容，而且对哈希表同一个桶（table[i]）进行扩容时候，一个线程刚好确定e和next元素之后，线程被挂起。此时另一个线程得到cpu并顺利对该桶完成转移（需要要求被转移之后的线程1中的e和next指的元素在新哈希表的同一个桶中，此时e和next被逆序了）。接着线程从挂起恢复回来时候就会陷入死循环中。参考：https://coolshell.cn/articles/9606.html

产生原因：主要由于并发操作，对用一个桶的两个节点构成了环，导致对环进行无法转移完毕元素陷入死循环。

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

Java HashMap源码及并发环境常见问题解决

热门推荐

随机推荐