《Java困惑》：多并發情況下HashMap是否還會産生死循環
今天本來想看下了ConcurrentHashMap的源碼，ConcurrentHashMap是Java 5中支援高并發、高吞吐量的線程安全HashMap實作，
在看很多部落格在介紹ConcurrentHashMap之前，都說HashMap适用于單線程通路，這是因為HashMap的所有方法都沒有進行鎖同步，是以是線程不安全的，不僅如此，當多線程通路的時候還容易産生死循環。
雖然自己在前幾天的時候看過HashMap的源碼，感覺思路啥啥的都還清楚，對于多線程通路隻知道HashMap是線程不安全的，但是不知道HashMap在多線程并發的情況下會産生死循環呢，為什麼會産生,何種情況下才會産生死循環呢？？？
正由于有這個問題，于是先将分析ConcurrentHashMap的源碼的事情給放了一放，開始在網上查找這個問題的原因。
看了如下的部落格，寫的都挺好的，下面隻列出最主要的一篇：
1、http://coolshell.cn/articles/9606.html/comment-page-1#comments (最源頭的一篇文章,下面的截圖均來自于這篇文章)
看的其它部落格和資料或者是來自于上面這篇文章或者是說的意思差不多。
聲明：
由于上面部落格中所分析的HashMap的源碼和我目前所看到的源碼不一緻，發現改動挺大的。目前我的JDK的版本是：jdk1.8.0_45.
這篇博文想讨論的問題是：在目前jdk1.8.0_45源碼下，還存不存在上面列出的博文中所将到的這種死循環的問題,個人的答案是：不存在了。若有錯，請批評指正
原HashMap的源碼産生死循環的過程
下面貼出原HashMap的源碼，這是原部落格分析的基礎，是以，截圖如下：
第一篇部落格中所貼出的HashMap的源碼如下：
個人小結：根據原HashMap的源碼，當我們想往HashMap中添加某個元素
<K,V>
時，假如根據k的hash值找到的存儲位置是在table中的index，且剛好此位置已經有了元素，即發生了碰撞，碰撞的處理方式為：将此元素加在此位置的連結清單的頭部，注意，是加在連結清單頭部。
在addEntry方法的代碼中很容易的看出這一點。而addEntry方法是在put方法中檢測該key在該位置不存在時調用的。
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);
//檢視目前的size是否超過了我們設定的門檻值threshold，如果超過，需要resize
if (size++ >= threshold)
resize( * table.length);
}
就因為是将結點加在連結清單的頭部，是以就出現了原博文中介紹的死循環問題。
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);
死循環的産生具體過程描述如下(圖解可以看原博文)：
第一步：假設線程1剛記錄下來e=3,next=7 就切換到線程2執行
第二步：線程2執行完resize的全過程，結果如下：table[3]—>7——>3——>null.
第三步：現在又切換到線程1繼續執行，會進行如下三輪循環
1）第一輪循環，e = 3,next = 7,由于線程1和線程2的newTab是獨立的，是以，此輪循環的結果為：newTab[3]—->3—->null;
2)第二輪循環，e = 7,next = 3(此next就是節點e=7的下一個節點，線上程2中改變的)，是以，結果為：newTab[3]—–>7—->3—->null.
3）第三輪循環，e = 3,next = null（此next就是此時節點e=3的下一個節點，為null，在第一輪循環中改變的），是以，結果為：
newTab[3]—->3<———>7(這裡的雙箭頭表示節點3的下一個節點為節點7，節點7的下一個節點為3)。就這樣循環就産生了。
當下次我們用get方法來擷取get(key)方法來擷取此可以與節點3和7相同的hash值的value時就進行了死循環中。
現在HashMap源碼中不會産生上面介紹的死循環
為避免誤會，特此聲明，JDK版本為：jdk1.8.0_45
HashMap源碼中的put方法的源碼如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == )
n = (tab = resize()).length;//重新開辟一個Node<K,V>的數組
if ((p = tab[i = (n - ) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = ; ; ++binCount) {
if ((e = p.next) == null) {
//------------将新節點加在連結清單之後---------------------------
p.next = newNode(hash, key, value, null);
//-----------------------------------------
if (binCount >= TREEIFY_THRESHOLD - ) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
resize方法的代碼如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? : oldTab.length;
int oldThr = threshold;
int newCap, newThr = ;
if (oldCap > ) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << ; // double threshold
}
else if (oldThr > ) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == ) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = ; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//第j個位置如果有節點
oldTab[j] = null;
if (e.next == null)//第j個位置隻有一個節點情況
newTab[e.hash & (newCap - )] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
//-----------------保持着原來的順序，并沒有倒序-------------------------//
Node<K,V> next;
do {
next = e.next;//儲存next
//一個接一個，和原來的順序一緻
if ((e.hash & oldCap) == ) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
在上面的代碼中(//——-//位置)，我們可以看到現在的HashMap是将新節點加在了連結清單的最後面，而不是最前面。
是以，如果按照現在HashMap的源碼的思路，則正常的Rehash過程如下(隻需看第三步，第二步也應該改下順序)：
現在我們把上面産生死循環的例子搬移到這裡來看是否還會産生死循環呢？？
過程描述如下：
第一步：假設線程1剛記錄下來e=3,next=7 就切換到線程2執行
第二步：線程2執行完resize的全過程，結果如下：table[3]—>3——>7——>null.
第三步：現在又切換到線程1繼續執行，會進行如下2輪循環結束
1）第一輪循環，e = 3,next = 7,由于線程1和線程2的newTab是獨立的，是以，此輪循環的結果為：newTab[3]—->3—->null;
2)第二輪循環，e = 7,next = null(此next為null，線上程2中改變的)，是以，結果為：newTab[3]—–>3—->7—->null.
就這樣結束了，正常運作，不會産生死循環。
Hashtable
最後要說的一點是：Hashtable的put方法的加入節點的方式是加入到連結清單的頭結點。但是，Hashtable是線程安全的，更不會有這個問題
Hashtable的addEntry方法代碼如下：
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & ) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
小結
以上，是自己在看一些博文之後說HashMap會産生死循環之後自己看目前HashMap源碼的的一點思考，不知道是否正确，若有錯，請指正，這個問題也在困擾着我。
為什麼困擾着我呢？
由于HashMap源碼的改動實在是比較大，自己隻能猜想難道是在源碼上修正了這個死循環的問題，但是在網上居然沒有搜尋到關于這個問題的任何讨論，是以，總是懷疑自己哪裡肯定弄錯了，但是又實在分析不出來。