JavaHashMap多線程環境下的死循環分析王舜1Hash表數據結構簡單地說一下HashMap這個經典的數據結構。HashMap通常會用一個指針數組（假設為table[]）來做分散所有的key，當一個key被加入時，會通過Hash算法通過key算出這個數組的下標i，然后就把這個<key,value>插到table[i]中。如果有兩個不同的key被算在了同一個i，那么就叫沖突，又叫碰撞，這樣會在table[i]上形成一個鏈表。缺陷：如果table[]的尺寸很小，比如只有2個，如果要放進10個keys的話，那么碰撞非常頻繁，于是一個O(1)的查找算法，就變成了鏈表遍歷，性能變成了O(n)，這是Hash表的缺陷。Rehash：Hash表的尺寸和容量非常的重要。一般來說，Hash表這個容器當有數據要插入時，都會檢查容量有沒有超過設定的thredhold，如果超過，需要增大Hash表的尺寸，但是這樣一來，整個Hash表里的無素都需要被重算一遍。這叫rehash，這個成本相當的大。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不存在，需要增加一個結點

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

resize(2*table.length);}新建一個更大尺寸的hash表，然后把數據從老的Hash表中遷移到新的Hash表中。voidresize(intnewCapacity){Entry[]oldTable=table;intoldCapacity=oldTable.length;......//創建一個新的HashTableEntry[]newTable=newEntry[newCapacity];//將OldHashTable上的數據遷移到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的過程并發下的Rehash1）假設我們有兩個線程。用紅色和淺藍色標注。再回頭看一下transfer代碼中的這個細節：do{Entry<K,V>next=e.next;//<--假設線程一執行到這里就被調度掛起了inti=indexFor(e.hash,newCapacity);e.next=newTable[i];newTable[i]=e;e