准确的讲应该是 JDK1.7 的 HashMap 链表会有死循环的可能,因为JDK1.7是采用的头插法,在多线程环境下有可能会使链表形成环状,从而导致死循环。JDK1.8做了改进,用的是尾插法,不会产生死循环。
那么,链表是怎么形成环状的呢?
关于这一点的解释,我发现网上文章抄来抄去的,而且都来自左耳朵耗子,更惊奇的是,连配图都是一模一样的。(别问我为什么知道,因为我也看过耗子叔的文章,哈哈。然而,菜鸡的我,那篇文章,并没有看懂。。。)
我实在看不下去了,于是一怒之下,就有了这篇文章。我会照着源码一步一步的分析变量之间的关系怎么变化的,并有配图哦。
我们从 put()方法开始,最终找到线程不安全的那个方法。这里省略中间不重要的过程,我只把方法的跳转流程贴出来:
//添加元素方法 -> 添加新节点方法 -> 扩容方法 -> 把原数组元素重新分配到新数组中 put() --> addEntry() --> resize() --> transfer()问题就发生在 transfer 这个方法中。
我们假设,原数组容量只有2,其中一条链表上有两个元素 A,B,如下图
现在,有两个线程都执行 transfer 方法。每个线程都会在它们自己的工作内存生成一个newTable 的数组,用于存储变化后的链表,它们互不影响(这里互不影响,指的是两个新数组本身互不影响)。但是,需要注意的是,它们操作的数据却是同一份。
因为,真正的数组中的内容在堆中存储,它们指向的是同一份数据内容。就相当于,有两个不同的引用 X,Y,但是它们都指向同一个对象 Z。这里 X、Y就是两个线程不同的新数组,Z就是堆中的A,B 等元素对象。
假设线程一执行到了上图1中所指的代码①处,恰好 CPU 时间片到了,线程被挂起,不能继续执行了。 记住此时,线程一中记录的 e = A , e.next = B。
然后线程二正常执行,扩容后的数组长度为 4, 假设 A,B两个元素又碰撞到了同一个桶中。然后,通过几次 while 循环后,采用头插法,最终呈现的结构如下:
此时,线程一解挂,继续往下执行。注意,此时线程一,记录的还是 e = A,e.next = B,因为它还未感知到最新的变化。
我们主要关注图1中标注的①②③④处的变量变化:
/** * next = e.next * e.next = newTable[i] * newTable[i] = e; * e = next; */ //第一次循环,(伪代码) e=A;next=B; e.next=null //此时线程一的新数组刚初始化完成,还没有元素 newTab[i] = A->null //把A节点头插到新数组中 e=B; //下次循环的e值第一次循环结束后,线程一新数组的结构如下图:
然后,由于 e=B,不为空,进入第二次循环。
//第二次循环 e=B;next=A; //此时A,B的内容已经被线程二修改为 B->A->null,然后被线程一读到,所以B的下一个节点指向A e.next=A->null // A->null 为第一次循环后线程一新数组的结构 newTab[i] = B->A->null //新节点B插入之后,线程一新数组的结构 e=A; //下次循环的 e 值第二次循环结束后,线程一新数组的结构如下图: