浅谈HashMap在高并发下的问题

前言

总所周知，HashMap不是线程安全的，在高并发情况下会出现问题。特别是，在java1.7中，多线程的HashMap会出现CPU 100%的严重问题。这个问题是怎样产生的，后续版本还会有这个问题吗（指java8及后续版本）？下面就来用通俗的语言讲解下。

解析

关于这个问题，是由于java7多线程扩容机制下链表变为循环链表，再获取该链表导致的。

看下java7中扩容的代码。java7中HashMap的实现为数组+链表的形式，没有红黑树。

java7扩容的原则很简单，新数组长度为原数组2倍。遍历原数组，将数组每个位置（有可能为空，有可能只有一个数组，有可能是一个链表）重新哈希，放到对应的新数组上。全部遍历完后更改数组指针，指向新数组。需要注意的是，这里重哈希将链表元素放到新数组，使用的是头插法。

 // 扩容核心方法，基本思想就是遍历数据，使用头插法将旧数组元素移到新数组。 void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; // 遍历旧数组 for (Entry e : table) { // 元素不为空。遍历该位置链表 while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; // 头插法,新节点next指向该位置首节点 newTable[i] = e; // 新元素归位 e = next; // 指向下一个节点，继续遍历 } } } void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; // 创建新数组 transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 扩容 table = newTable;  // 更改指针 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }

这里处理的话，如果单线程情况下不会有问题。如果在多线程情况下，会导致链表在扩容过程中形成循环链表。

形成循环链表的原因在于多线程和头插法。试想，两个线程在添加元素时，同时发现该扩容了，然后同时发起扩容过程。由上述代码可知，扩容完成之前是在自己的线程里创建一个新数组。等扩容完成后（也就是将原数组元素迁移到新数组后）再更改指针指向新扩容数组。

举例初始HashMap是这样的

假设两个线程同时扩容，一个线程扩容到一半后被挂起。（标识了某链表的e和next）,另一个线程执行扩容，且完成了扩容。

红色的数组和元素表示线程1，也就是扩容一半挂起的线程，而线程二已完成扩容。观察完成扩容的线程二，在3的位置，该链表的位置顺序已经改变（原数组顺讯为3->7,现在反过来了，这是使用头插法的效果，你也可以对着代码试试）。从图中也可以看出，线程1，2分别创建了自己的新数组，并在自己的新数组中完成扩容。

这时线程1开始执行。熟悉下它即将执行的代码。

 // transfer 方法循环部分 while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; // 头插法,新节点next指向该位置首节点 newTable[i] = e; // 新元素归位 e = next; // 指向下一个节点，继续遍历 } 

下面线程1将使用头插法将元素插入线程1新建的数组中去。注意此时e指向的是Key3,next指向的是Key7。不用想也知道后面操作会有问题。因为现在的next指针指的不是e的下一个元素，而是它的前一个元素！

如果继续走代码的话，把Key3(当前e指向元素)放入新数组后，再把Key7放入新数组，后面会放哪个元素？当然又是Key3了，因为Key7next是Key3,这样就形成了死循环。

java8的改进

• 添加了红黑树，当链表长度大于8时，会将链表转为红黑树。
• 扩容后，新数组中的链表顺序依然与旧数组中的链表顺序保持一致。具体JDK8是用 head 和 tail 来保证链表的顺序和之前一样，这样就不会产生循环引用。也就没有死循环了。
• 虽然修复了死循环的BUG，但是HashMap 还是非线程安全类，仍然会产生数据丢失等问题。