多(duo)線程下HashMap的死循(xun)環問題
多線程下[HashMap]的問題：
1、多線程put操作(zuo)后(hou)，get操作(zuo)導致死循(xun)環。
2、多線程put非NULL元素后，get操作得(de)到NULL值。
3、多(duo)線程put操作，導致元素丟失。
本次主要關注[HashMap]-死循(xun)環問(wen)題。
為何出現死循環？
大家都知道，HashMap采用鏈表解決Hash沖突，具體的HashMap的分析可以參考一下Java集合---HashMap源碼剖析 的分析。因為是鏈表結構，那么就很容易形成閉合的鏈路，這樣在循環的時候只要有線程對這個HashMap進行get操作就會產生死循環。但是，我好奇的是，這種閉合的鏈路是如何形成的呢。在單線程情況下，只有一個線程對HashMap的數據結構進行操作，是不可能產生閉合的回路的。那就只有在多線程并發的情況下才會出現這種情況，那就是在put操作的時候，如果size>initialCapacity*loadFactor，那么這時候HashMap就會進行rehash操作，隨之HashMap的結構就會發生翻天覆地的變化。很有可能就是在兩個線程在這個時候同時觸發了rehash操作，產生了閉合的回路。
下(xia)面我們從源碼中一(yi)步一(yi)步地分析這(zhe)種回(hui)路是如何(he)產生的。先(xian)看一(yi)下(xia)put操作：
存儲數據put
public V put(K key, V value)
{
......
//算(suan)Hash值(zhi)
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//如果該key已被插(cha)入，則替換掉舊的value （鏈接操作）
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//該key不(bu)存(cun)在，需(xu)要增加(jia)一個結(jie)點
addEntry(hash, key, value, i);
return null;
}
當我們往HashMap中put元素(su)的(de)(de)時候(hou)，先(xian)根據key的(de)(de)hash值得到這個元素(su)在(zai)(zai)數組(zu)中的(de)(de)位置(zhi)（即下標），然后就可以把這個元素(su)放到對(dui)應的(de)(de)位置(zhi)中了(le)。 如果這個元素(su)所在(zai)(zai)的(de)(de)位置(zhi)上(shang)已(yi)經存放有其他元素(su)了(le)，那么在(zai)(zai)同一個位子上(shang)的(de)(de)元素(su)將以鏈(lian)表的(de)(de)形(xing)式存放，新加入的(de)(de)放在(zai)(zai)鏈(lian)頭，而先(xian)前加入的(de)(de)放在(zai)(zai)鏈(lian)尾。
檢查容量是否超標addEntry
void addEntry(int hash, K key, V value, int bucketIndex)
{
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//查看(kan)當(dang)前(qian)的(de)size是否超(chao)過(guo)了我們設定(ding)的(de)閾值threshold，如(ru)果超(chao)過(guo)，需要resize
if (size++ >= threshold)
resize(2 * table.length);
}
可以看到，如果現在size已經(jing)超(chao)過了threshold，那么就要進(jin)行resize操作(zuo),新建(jian)一個更大尺寸的hash表，然后把數據從老的Hash表中(zhong)遷移到新的Hash表中(zhong)：
調整(zheng)Hash表(biao)大小resize
void resize(int newCapacity)
{
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
......
//創建一個新(xin)的(de)Hash Table
Entry[] newTable = new Entry[newCapacity];
//將(jiang)Old Hash Table上的數據(ju)遷移到New Hash Table上
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
當table[]數(shu)(shu)組容(rong)量(liang)較(jiao)小，容(rong)易產生哈希碰撞，所以，Hash表的尺(chi)寸和容(rong)量(liang)非常的重(zhong)要。一般來說，Hash表這個容(rong)器當有(you)(you)數(shu)(shu)據要插入時，都會檢(jian)查容(rong)量(liang)有(you)(you)沒有(you)(you)超(chao)(chao)過(guo)設定(ding)的thredhold，如果超(chao)(chao)過(guo)，需(xu)要增大(da)Hash表的尺(chi)寸，這個過(guo)程(cheng)稱為resize。
多(duo)個(ge)線程(cheng)同時(shi)往HashMap添加新元素時(shi)，多(duo)次resize會有一(yi)定概率(lv)出現死循環，因為(wei)每(mei)次resize需(xu)要把舊(jiu)的數(shu)據映射到新的哈希表，這一(yi)部分(fen)代碼在HashMap#transfer() 方法(fa)，如下：
void transfer(Entry[] newTable)
{
Entry[] src = table;
int newCapacity = newTable.length;
//下面(mian)這(zhe)段代碼的意思是：
// 從OldTable里(li)摘一個元素出來，然后放到NewTable中
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
綠色部分代碼是導致多線程(cheng)使用(yong)hashmap出現CUP使用(yong)率驟增，從而多個線程(cheng)阻塞的罪魁禍首。
更多(duo)細節分析參見資(zi)料：