HashMap用在并发场景的问题

扩容过程

HashMap在扩容的时候，会将元素插入链表头部，即头插法。如下图，原来是A->B->C，扩容后会变成C->B->A”。

之所以选择使用头插法，是因为JDK的开发者认为，后插入的数据被使用到的概率更高，更容易成为热点数据，而通过头插法把它们放在队列头部，就可以使查询效率更高。

并发现象

• JDK7循环引用（死循环）

假设有两个线程A和B，它们都在进行rehash操作。线程A处理到第i个元素时被挂起，线程B继续处理，处理完后线程A继续执行，此时线程A看到的链表顺序和原始链表顺序不一样，这就可能会形成环形链表。

如果在JDK7中，有两个线程同时对HashMap进行put操作，并且这两个put操作导致HashMap需要进行rehash，那么可能会出现一个线程看到的链表顺序和另一个线程看到的链表顺序不一致的问题，从而导致循环引用的产生。

在JDK8中，变成了尾插法，就没有循环引用的问题。

• 多线程put的时候，size的个数和真正的个数不一样
• 多线程put的时候，可能会把上一个put的值覆盖掉
• 和其他不支持并发的集合一样，HashMap也采用了fast-fail操作，当多个线程同时put和get的时候，会抛出并发异常
• 当既有get操作，又有扩容操作的时候，有可能数据刚好被扩容换了桶，导致get不到数据。

JDK7为什么将rehash的节点作为新链表的根节点（头插法）

在重新映射的过程中，如果不将rehash的节点作为新链表的根节点，而是使用普通的做法，遍历新链表中的每一个节点，然后将rehash的节点放到新链表的尾部。这种做法不仅需要遍历老桶中的链表，还需要遍历新桶中的链表，时间复杂度是O(n^2)，显然是不太符合预期的，所以需要将rehash的节点作为新桶中链表的根节点，这样就不需要二次遍历，时间复杂度就会降低到O(N)

JDK8如何解决这个问题

之所以会发生这个死循环问题，是因为在JDK 1.8之前的版本中，HashMap是采用头插法进行扩容的，这个问题其实在JDK 1.8中已经被修复了，改用尾插法。