JavaHashMap多線程環(huán)境下的死循環(huán)分析王舜1Hash表數(shù)據(jù)結(jié)構(gòu)簡單地說一下HashMap這個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。HashMap通常會用一個指針數(shù)組（假設(shè)為table[]）來做分散所有的key，當(dāng)一個key被加入時，會通過Hash算法通過key算出這個數(shù)組的下標(biāo)i，然后就把這個<key,value>插到table[i]中。如果有兩個不同的key被算在了同一個i，那么就叫沖突，又叫碰撞，這樣會在table[i]上形成一個鏈表。缺陷：如果table[]的尺寸很小，比如只有2個，如果要放進(jìn)10個keys的話，那么碰撞非常頻繁，于是一個O(1)的查找算法，就變成了鏈表遍歷，性能變成了O(n)，這是Hash表的缺陷。Rehash：Hash表的尺寸和容量非常的重要。一般來說，Hash表這個容器當(dāng)有數(shù)據(jù)要插入時，都會檢查容量有沒有超過設(shè)定的thredhold，如果超過，需要增大Hash表的尺寸，但是這樣一來，整個Hash表里的無素都需要被重算一遍。這叫rehash，這個成本相當(dāng)?shù)拇?。HashMap的rehash源代碼Put一個Key,Value對到Hash表中：publicVput(Kkey,Vvalue){......//算Hash值inthash=hash(key.hashCode());inti=indexFor(hash,table.length);//如果該key已被插入，則替換掉舊的value（鏈接操作）for(Entry<K,V>e=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++;//該key不存在，需要增加一個結(jié)點

addEntry(hash,key,value,i);returnnull;}檢查容量是否超標(biāo)voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){Entry<K,V>e=table[bucketIndex];table[bucketIndex]=newEntry<K,V>(hash,key,value,e);//查看當(dāng)前的size是否超過了我們設(shè)定的閾值threshold，如果超過，需要resizeif(size++>=threshold)

resize(2*table.length);}新建一個更大尺寸的hash表，然后把數(shù)據(jù)從老的Hash表中遷移到新的Hash表中。voidresize(intnewCapacity){Entry[]oldTable=table;intoldCapacity=oldTable.length;......//創(chuàng)建一個新的HashTableEntry[]newTable=newEntry[newCapacity];//將OldHashTable上的數(shù)據(jù)遷移到NewHashTable上

transfer(newTable);table=newTable;threshold=(int)(newCapacity*loadFactor);}遷移的源代碼，注意紅色處：voidtransfer(Entry[]newTable){Entry[]src=table;intnewCapacity=newTable.length;//下面這段代碼的意思是：//從OldTable里摘一個元素出來，然后放到NewTable中for(intj=0;j<src.length;j++){Entry<K,V>e=src[j];if(e!=null){src[j]=null;do{

Entry<K,V>next=e.next;inti=indexFor(e.hash,newCapacity);

e.next=newTable[i];newTable[i]=e;e=next;}while(e!=null);}}}正常的ReHash的過程并發(fā)下的Rehash1）假設(shè)我們有兩個線程。用紅色和淺藍(lán)色標(biāo)注。再回頭看一下transfer代碼中的這個細(xì)節(jié)：do{Entry<K,V>next=e.next;//<--假設(shè)線程一執(zhí)行到這里就被調(diào)度掛起了inti=indexFor(e.hash,newCapacity);e.next=newTable[i];newTable[i]=e;e