JDK7之前hashmap链表采用头插法为什么会导致循环链表？

hashmap发生哈希碰撞之后形成的链表在早的jdk版本会采用头插法的方法也就是新插入的值作为链表的头部。这种方法在单线程的情况下没有什么问题这里扩容的时候要说一点当扩容的时候会创建一个新哈希表这个时候链表插入新表的方法是一个个的去拿头结点数据然后按照头插法的方法插入桶bucket代码如下这里解释一下next()和next是不一样的前者是方法是拿取当前指向的数据后指针后移而next就是一个指向下一个数据的指针类似于节点中的首尾指针┌─────┐ ┌─────┐ ┌─────┐│ 3 │ │ 2 │ │ 1 ││next─ ┼ →│ next─┼→│ next─ ┼───→ null└─────┘ └─────┘ └─────┘↑ ↑ ↑e e.next e.next.next当遍历到table中链表的时候是从头结点开始遍历而这个时候的头结点其实是我们最后插入的值EntryKVnexte.next;-----将遍历到的链表中的这个数据的尾指针赋值给nexti是根据我们的哈希值从而定位到的扩容后的新表当中的桶的索引标之后开始转移完成扩容e.nextnewTable[i];即e的尾指针指向转移后的新桶位如下然后newTable[i]e;将e的值放入新桶位也就是如下enext之后新e的值就是next依次循环换成转移最终变为比如原本链表数据是3--2--1--NULL那么就会先取3到新的map表中之后头插法2--3--NULL,最后是1--2--3--NULL我们不难发现这个时候其实链表的顺序已经颠倒了但对于单线程来说没有安全隐患但如果是多线程就可能会出现一种危险的情况比如线程1和线程2在扩容的时候指向了链表头3这个时候线程1拿到了cpu给的时间片资源线程2则暂时阻塞那么就会产生如下的情况这个时候线程1完成了扩容如下但恰好这个时候线程2苏醒那么我们不难发现其实e2和next2的指向已经相反了因为这个时候线程2依旧 e23e2.next2,但其实链表顺序已经颠倒了这个时候线程2开始扩容此时条件判断e并不为空之后EntryK,V next2e2.next;e2.nextnewTable[i]newTable[i]e2;e2next2执行完毕如下我们不难发现现在的e2.next其实指向了这个3然后我们再来进行循环操作看看发生什么EntryK,V next2e2.next;-------此时这个next2就是3e2.nextnewTable[i];------此时的2指向了新的坑位newTable[i]e2;按照头插法插入成为链表头部但是e2next2 这里的next2也就是3也就是此时的e变为了3然后我们发现循环还能继续因为eNULL所以继续进行操作EntryK,V next2e2.next;-----这个时候next其实就是指向了空然后e2.nextnewTable[i];------这一步就是e2.next指向了2newTable[i]e2;e2;next2;最终变为如下图这就是环形链表形成的原因也就是为什么hashmap早期的头插法在多线程并发的时候可能会导致循环链表发生死循环,而改为尾插法之后就不会有这种问题了因为扩容迁移是从头节点摘取尾部迁移插入所以并不会导致迁移后的链表顺序颠倒