hashMap的循环链表形成

原文地址：https://www.cnblogs.com/tilamisu007/p/9438356.html

1、 当前hashmap的状态如下，有两个线程同时对它扩容。

image.png

2、 假设线程1先开始扩容，遍历tab[0]的链表，按照链表的先后顺序进行rehash。假设A和B节点，恰好又在同一个tab元素里面。线程1对A节点rehash结束后，读取A节点next节点是B。这个时候，线程1正好被中断。如下：

image.png

当前线程正在处理B节点，但是还尚未加入tab中。

3、线程1暂停后，线程2开始，并且先完成扩容。如下：

image.png

线程2正常且先完成扩容。把它赋值给了原来的hashMap的tab数组了。

4、这个时候线程1被唤醒了，继续步骤2，对节点B继续扩容。把B节点插入tab[0]位置，并且把B.next = A。这步完成后，就和步骤3一模一样。老的B节点next本来是null的，但是线程2扩容后，B的next是A节点。线程1就以为还没扩容完，继续对A进行扩容。当执行A节点的时候，发现tab[0]的链表结尾已经是A了。那么就把这个节点提升到该链表的表头。即把A.next = tab[0]。而这个时候的tab[0]就是B。变成了如下：

image.png

ps：扩容的时候，会重跑一遍老的hashmap，对节点进行重新插入。而插入节点是直接插入到链表头部。所以，第四步中的A节点，虽然已经在链表尾部了，但是由于多线程的原因，又插入了一遍A，把它提升到链表头部了。形成了循环。