【你问我答】HashMap形成环的原因是什么？

jdk1.7的transfer()是用头插法，让新的链表和原来的是倒着的，所以这时候假如有两个线程，第一个线程只执行resize()中的transfer()到while循环中Entry next = e.next这一步挂起了 ; 然后就第二个线程又开始执行扩容，第二个线程执行成功，其实这时候已经完成了扩容的任务，且链表里的顺序 已经倒置了（因为采用的头插法。原链表的头先插入，尾部后插入），这时候第一个线程唤醒继续执行，也是类似线程二的方式，while循环，链表反转。（但是线程二已经线程一将原尾部的引用修改了，指向头部）这时候线程一再反转就把新链表的尾巴又指向头了，然后就造成了环。（链表中只有两个元素扩容。）

首先要明确一点，HashMap形成环（并发死链）只会发生在jdk7及以前版本。在多个线程同时对容器进行扩容时会出现该现象。 HashMap在进行扩容时调用resize()方法，该方***创建一个新的Entry数组，再调用transfer()方法吧原数组上的元素转移到新创建的数组上。 由于jdk7及以前采用头插法，也就是说，新table中链表上元素的顺序和旧列表相反。 在多个线程同时执行扩容操作时，会造成链表成环。 Entry<K,V> next = e.next; // 1 处 e.next = newTable[i]; // 2 处 例如：假设 map 中初始元素，数组的[1]索引上的链表元素为[1] (1,35)->(35,16)->(16,null) 括号中前一个为链表的节点元素，后一个为其指向的下一个元素。 线程 a 执行到 1 处 ，此时局部变量 e 为 (1,35)，而局部变量 next 为 (35,16) 线程 a 挂起线程 b 开始执行。 第一次循环 [1] (1,null) 第二次循环 [1] (35,1)->(1,null) 第三次循环 [1] (35,1)->(1,null) [17] (16,null) 切换回线程 a，此时局部变量 e 和 next 被恢复，引用没变但内容变了：e 的内容被改为 (1,null)，而 next 的内容被改为 (35,1) 并链向 (1,null) 第一次循环 [1] (1,null) 第二次循环，注意这时 e 是 (35,1) 并链向 (1,null) 所以 next 又是 (1,null) [1] (35,1)->(1,null) 第三次循环，e 是 (1,null)，而 next 是 null，但 e 被放入链表头，这样 e.next 变成了35（2 处） [1] (1,35)->(35,1)->(1,35) 已经是死链了 jdk8以后采用尾插法，即转以后新table中链表上元素的顺序和旧列表相同，这样就不会出现并发死链的情况，但是多个线程情况下仍然会出现数据覆盖的情况。所以我们要想保证线程安全，在使用HashMap时就要加锁或者采用线程安全的容器，比如ConcurrentHashMap、Hashtable或者使用Collections.synchronizedMap(Map)创建线程安全的map集合。