问题
最近几道面试题被问了是否了解并发情况下JDK7中HashMap发生死循环，导致CPU占用100%的问题。
由于HashMap并非是线程安全的，所以在高并发的情况下必然会出现问题，这是一个普遍的问题。
如果是在单线程下使用HashMap，自然是没有问题的，如果后期由于代码优化，这段逻辑引入了多线程并发执行，在一个未知的时间点，会发现CPU占用100%，居高不下，通过查看堆栈，你会惊讶的发现，线程都Hang在hashMap的get()方法上，服务重启之后，问题消失，过段时间可能又复现了。
这是为什么？
原因分析
在了解来龙去脉之前，我们先看看JDK7中HashMap的数据结构。
在内部，HashMap使用一个Entry数组保存key、value数据（JDK8之后是Node），当一对key、value被加入时，会通过一个hash算法得到数组的下标index，算法很简单，根据key的hash值，对数组的大小取模 hash & (length-1)，并把结果插入数组该位置，如果该位置上已经有元素了，就说明存在hash冲突，这样会在index位置生成链表。
如果存在hash冲突，最惨的情况，就是所有元素都定位到同一个位置，形成一个长长的链表，这样get一个值时，最坏情况需要遍历所有节点，性能变成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要。
当插入一个新的节点时，如果不存在相同的key，则会判断当前内部元素是否已经达到阈值（默认是数组大小的0.75），如果已经达到阈值，会对数组进行扩容，也会对链表中的元素进行rehash。
JDK7中HashMap代码
HashMap的put方法实现：
1、判断key是否已经存在
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key); 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; }
2、检查容量是否达到阈值threshold
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }
3、扩容实现
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; ... Entry[] newTable = new Entry[newCapacity]; ... transfer(newTable, rehash); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
这里会新建一个更大的数组，并通过transfer方法，移动元素。
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
第一个for循环是遍历原来的table，第二个while循环用于遍历table中每个位置的链表。也就是如果这次的Entry节点下面有链表，就会执行while循环。
由于JDK7的时候HashMap使用的是头插法，因此先来的数据会在链表尾部，后来的数据在链表头部。其实插入数据的时候是先让要插入节点的next指针指向原有的数据，然后再覆盖掉原有的数据。
例如插入数据的顺序是1,2,3，那么插入完毕之后链表如下所示。
单线程情况：
此时假设我们开始扩容，那么就会执行transfer函数。其中newTable就是扩容后的数组，其大小为原数组的两倍。
我们现在开始外层for循环，现在我们遍历到了3这个Entry了。
由于这个Entry不等于null，所以会执行while语句中的内容。
首先我们的e一开始是3，那么e.next就是2
之后开始进行rehash操作，然后得到hash值之后，我们根据这个hash值在扩容后的HashMap中获取新的插入位置的索引 i。
并且让e（3）的next指针指向这个新数组的索引为i的位置，如下：
之后执行newTable[i]=e这个语句，那么根据头插法，变成如下：
之后执行e=next，也就是让e指针指向2。
然后继续执行while中的逻辑进行头插法操作，就会发现最后的结果是这样子的。
可以发现单线程的情况下执行头插法进行扩容是没有问题的。
移动的逻辑也很清晰，遍历原来table中每个位置的链表，并对每个元素进行重新hash，在新的newTable找到归宿，并插入。（JDK8之后由于只需要两次扰动，因此性能更高，并且元素在newTable的索引要么为原本的索引位置，要么为原索引位置+此次扩容的大小）
多线程情况：
这里假设有两个线程进行扩容方法，那么就是有两个线程进入了resize方法，假设两个线程都执行到了transfer方法，并且两个线程都执行到了下面这一步，在这个时候，如果有一个线程阻塞住了。
if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); }
那么此时的table情况如下：
这两个e其实在线程之间是不互相影响的，他们在各自的线程的私有栈中。
这里假设第一个线程他在运行，另一个线程阻塞，那么第一个线程就会先进行扩容。
然后此时就和单线程扩容情况一样，扩容后如下：
此时线程2醒了，由于线程2的e指针和e.next指向的是3和2，那么由于线程1扩容之后，值没有改变，所以线程2醒来之后的情况如下：
可以发现虽然他们指向的值没有变，但是顺序已经变了，e.next.next=e
而本来应该是e.next=2，e=3这种情况的，所以他们的顺序已经相反了。
然后我们再来一下线程2的扩容：
我们刚才设定从if代码出开始阻塞，那么阻塞结束了继续进行，得到hash值之后获取在newTable中的索引位置。
然后开始第一次插入：
也就是e.next先指向扩容后数组的某个位置
到此第一次循环结束，可以发现好像没有问题，然后我们开始第二次循环：
此时next为3，以为e此时为2，e.next由于一开始倒置的问题变为了3
之后我们第三次进入while循环
此时的e.next就是NULL了，然后再让e.next指向newTable[i]，如下：
此时可以发现已经生成了一个环形了，那么3的next是2 ， 2的next又是3，那么就是无论如何这个e和e.next都在2和3之间跳动了，那么就会导致卡死再这里。
这就是再JDK7下多线程情况下HashMap的并发问题。
他会在扩容的时候从一个链表变成一个环状结构。
