HashMap在1.8之前插入元素采用头插法的危害性

看一下jdk1.7中HashMap扩容是如何移动元素的：


每个节点中存储的内容为：hash值、key、value、next（下一个节点的内容）

假设一个长度为4的HashMap，现在已经存在3个元素了，当再插入一个元素时，Map将会扩容。

此时有两个线程同时进行put操作：

假设线程B刚遍历到Entry3的时候，运行到这句话时线程被挂起。

对于线程B来说：
此时的 e为Entry3，next为Entry2
而假设线程A畅通无阻的完成了rehash，完成后，结果如下图： （图中e和next代表线程B的两个引用）

之后线程B重新拿到时间片开始运行，继续往下运行。

计算出Entry3的下标 i 同样为3，因为线程A计算结果就为3。

根据线程A已经计算后的结果，线程B运行这三句代码后：e为Entry2，next也为Entry2

开始一轮新的循环后，运行至此：

Entry2的next为Entry3，故此时：e为Entry2，next为Entry3

接着执行下面三行，将Entry2使用头插法插入头结点：

则此时：e为Entry3，next也为Entry3

第三次循环，运行至此：

Entry3的next为null，故此时：e为Entry3，next为null
最后一步运行三句代码时：

注意：
第一行的结果为：Entry3.next=Entry2；
第二行的结果为：Entry插入到头结点，即线程A的Entry2的位置
第三行的结果为：e置为null，本次while循环结束
线程A、B完整运行后：
A—>：头结点为Entry2，Entry2.next = Entry3
B—>：头结点为Entry3，Entry3.next = Entry2
形成了环形链表！

此时问题并为发生，但当调用get方法，参数为一个不存在的key，而这个key的hash值恰好为3时，由于位置3存在环形链表，则会进入死循环！

总结：

链表头插法的会颠倒原来一个散列桶里面链表的顺序。在并发的时候原来的顺序被另外一个线程a颠倒了，而被挂起线程b恢复后拿扩容前的节点和顺序继续完成第一次循环后，又遵循a线程扩容后的链表顺序重新排列链表中的顺序，最终形成了环。

尾插法的好处：

• 使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

• Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。

• Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。

虽然jdk8后HashMap在多线程情况下扩容时不会出现死循环的情况，但是在多线程情况下仍不推荐使用HashMap。因为HashMap中的put/get方法并未加锁，这意味着无法保证上一秒put的值，下一秒取到的是原值，所以线程安全无法保证。多线程下推荐使用ConcurrentHashMap。