1回答

Jimin

2019-02-25

你好，我针对课程里的图再叙述一遍你看一下。（这里假设是按照value%hashmap数组节点个数作为value放置的数组位置，数组使用e表示）

第一张图：首先是有两个节点的时候，e[1]后面链表有3个元素5、9、11，然后需要进行扩容，数组长度由2变4之后按照5、9、11分别重新放置，并且在起始位置插入（这样插入最快，而且每次都是在链表首部插入），就变成e[1]->9->5,e[3]->11。如果没有多线程存在，这样直接操作一次就ok了。但是多线程存在，恰恰会对这个过程造成影响，第二张图开始就是模拟多线程的一种情形。

第二张图：假设有两个线程都触发了扩容操作，因为没有同步锁的存在，两个线程（上面线程1，下面是线程2）都按照自己的想法去做第一幅图里介绍的操作。假设线程1当前执行到申请了新的2倍容量的数组，然后准备处理第一个元素5，并记录下一个元素是9（next指针），此时线程1里数组索引1后面链表第一个元素是5，这时由于线程调度所分配时间片用完而出现“暂停”（cpu正常调度），此时线程2开始操作并完成了整个rehash操作。

第三张图：线程1被唤醒，继续执行第一轮循环的剩余部分。这时候线程1里现在指针指向的是5，5的next指向的是9，而线程2操作完之后9的next指针已经指向了5（第一图里最终执行完的效果）

第四张图：线程1里5处理完要处理下个元素是9，9的位置是要插入到数组索引1的链表首个位置，9这个元素处理完后，后面的元素是5，因此又要继续处理5

第五张图：当再次把元素5放到数组索引1链表头位置的时候，循环链表就出现了。

0

0