之前在讲HashMap的时候提到过HashMap线程不安全，在并发环境下会发生死锁问题，将导致CPU占用率接近100%。其实死锁的说法并不很贴切，应该说是一种死循环。在JDK 1.8中，Map相关类的实现发生了很大变化，引入了红黑树的概念，本篇以JDK 1.7中的实现方式讲解HashMap的并发问题，以方便理解。
说明
JDK 1.8和JDK 1.7中，Map相关类的大体实现思想变化不大，知识引入了红黑树的概念，使得类中增加了生成红黑树的方法，相关的一些重要方法，例如添加元素，重置集合大小等方法也做出相应改变。
上述这些变化主要是为了提高集合的查询效率，思想还是原来的思想，因此JDK 1.7中的源代码更能方便理解。
HashMap并发死锁问题
该问题的成因涉及到四个方法，最初的起因是调用put()方法，跟着方法走一遍：
put()方法源码（只给出核心部分）：
public V put(K key, V value)
{
......
//计算Hash值
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//如果该key已存在，则替换掉旧的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不存在，需要增加一个结点
addEntry(hash, key, value, i);
return null;
}
当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);
}
resize()方法就是产生并发死锁的原因
void resize(int newCapacity)
{
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
......
//创建一个新的Hash Table
Entry[] newTable = new Entry[newCapacity];
//将Old Hash Table上的数据迁移到New Hash Table上
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
resize()方法的本质就是创建新的Entry数组，将原Map中的元素重新计算位置，加入到新的Map中。虽然死锁的成因是扩充时调用resize()方法，但真正的产生是发生在倒数第三行的transfer()方法中。
void transfer(Entry[] newTable)
{
Entry[] src = table;
int newCapacity = newTable.length;
//从OldTable将元素一个个拿出来，然后放到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;
//计算节点在新的Map中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
大体过程如下（摘自网上大神的博客）
transfe过程
假设hash算法就是简单的用key mod Entry数组的长度。这里一定注意e和next的指向，当并发resize()时，这两个指针对于死锁产生起着至关重要的作用。根据方法执行情况，原Map中的链表元素在新的Map中将顺序颠倒，如上图所示，经过一次resize()后key为7的节点排在了key为3的节点之前。
do {
Entry<K,V> next = e.next;
//计算节点在新的Map中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
再次黏贴这段代码就是强调这个do while循环就是产生死锁的罪魁祸首。下面模拟死锁产生的过程。
注意，并非所有情况下都会产生死锁，这也需要线程之间的默契配合，怎么讲呢，如图所示：
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);
线程一的记录状态
此时线程一，e指向key为3的节点，next指向key为7的节点。这点很重要，记下来。去执行线程二。
假设线程二正常执行，结束后的状态如下：
线程二正常执行
此时线程一被唤醒，线程一的工作空间里，e和next指向的元素依旧是key为3和7的节点。线程一开始执行。
先是执行 newTalbe[i] = e。
然后是e = next，导致了e指向了key(7)。
而下一次循环的next = e.next导致了next指向了key(3)。
线程一执行
目前还没发生问题，线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。
线程一执行
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
死锁产生
这个过程不好理解，最好多读几遍，当产生带环链表后，如果调用get()方法，将会陷入死循环，CPU占用将达到100%。解决这一问题的方式有多种。比较low的可以使用HashTable和调用Collections工具类的synchronizedMap()方法达到线程安全的目的。但由于synchronized是串行执行，在访问量很大的情况下效率很低，不推荐使用。
另外一种方式就是使用JUC包下的ConcurrentHashMap类，这个类很好的解决了多线程环境下的并发问题，之后将专门通过一篇文章详细讲解该类。
网友评论