《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(2 * 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) == 0)
n = (tab = resize()).length;//重新开辟一个Node<K,V>的数组
if ((p = tab[i = (n - 1) & 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 = 0; ; ++binCount) { if ((e = p.next) == null)
{ //------------将新节点加在链表之后---------------------------
p.next = newNode(hash, key, value, null); //-----------------------------------------
if (binCount >= TREEIFY_THRESHOLD - 1) // -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) ? 0 : oldTab.length;
int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE; return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // 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 == 0) { 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 = 0; 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 - 1)] = 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) == 0) { 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 & 0x7FFFFFFF) % 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源码的改动实在是比较大，自己只能猜想难道是在源码上修正了这个死循环的问题，但是在网上居然没有搜索到关于这个问题的任何讨论，因此，总是怀疑自己哪里肯定弄错了，但是又实在分析不出来。
转载自：http://blog.csdn.net/u010412719/article/details/52049347