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

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是否超過(guò)了我們?cè)O(shè)定的閾值threshold，如果超過(guò)，需要resizeif(size++>=threshold)

resize(2*table.length);}新建一個(gè)更大尺寸的hash表，然后把數(shù)據(jù)從老的Hash表中遷移到新的Hash表中。voidresize(intnewCapacity){Entry[]oldTable=table;intoldCapacity=oldTable.length;......//創(chuàng)建一個(gè)新的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里摘一個(gè)元素出來(lái)，然后放到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的過(guò)程并發(fā)下的Rehash1）假設(shè)我們有兩個(gè)線程。用紅色和淺藍(lán)色標(biāo)注。再回頭看一下transfer代碼中的這個(gè)細(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