头插法多线程不可用的原因

为什么头插法多线程下不可用我们以HashMap扩容时用的头插法举例子:JDK 1.7 HashMap 扩容时的头插法迁移逻辑// 旧数组Entry[]oldTabletable;// 新数组容量翻倍Entry[]newTablenewEntry[oldCapacity*2];// 遍历旧数组的每个桶for(inti0;ioldTable.length;i){// 拿到当前桶的头节点eEntryK,VeoldTable[i];// 如果这个桶不为空就遍历链表while(e!null){// 【关键1】先保存e的下一个节点next// 因为接下来要修改e的next指针不保存就会丢失后面的链表EntryK,Vnexte.next;// 【关键2】计算e在新数组中的索引intnewIndexindexFor(e.hash,newTable.length);// 【关键3】头插法把e插入到新数组newIndex位置的链表头部// 步骤1e的next指向新数组当前的头节点e.nextnewTable[newIndex];// 步骤2新数组的头指针指向enewTable[newIndex]e;// 【关键4】处理下一个节点enext;}}// 扩容完成把table指向新数组tablenewTable;一、单线程下头插法迁移的完整演示我们用最简单的例子一步一步看单线程下头插法是如何工作的。初始状态旧数组容量 2桶 0 的链表A → B → null假设 A 和 B 的 hash 值在新数组容量 4中计算出的索引都是 0这样它们会被迁移到同一个桶执行迁移代码步骤第一次循环e Anext e.next→next B保存 A 的下一个节点计算新索引newIndex 0头插法插入 A 到新数组桶 0e.next newTable[0]→A.next null因为新数组桶 0 现在是空的newTable[0] A→ 新数组桶 0A → nulle next→e B准备处理下一个节点当前状态旧数组桶 0A → B → null还没修改新数组桶 0A → null第二次循环e Bnext e.next→next null保存 B 的下一个节点计算新索引newIndex 0头插法插入 B 到新数组桶 0e.next newTable[0]→B.next A新数组桶 0 当前的头是 AnewTable[0] B→ 新数组桶 0B → A → nulle next→e null循环结束最终状态旧数组桶 0A → B → null新数组桶 0B → A → null关键点原来的链表A → B经过头插法迁移后变成了B → A顺序完全反转了。这是头插法最核心的特点也是多线程并发下可能产生死循环的根源。二、多线程下死循环是如何一步步形成的现在我们有了头插法的基础再回头看死循环就会一目了然。场景还是用上面的例子旧数组桶 0 的链表A → B → null两个线程 T1 和 T2 同时扩容。步骤 1T1 执行到一半被挂起T1 开始执行迁移代码执行完第一次循环的第一步EntryK,VeoldTable[i];// e Awhile(e!null){EntryK,Vnexte.next;// next B// 就在这里T1的CPU时间片用完了被挂起// 后面的代码还没执行intnewIndexindexFor(e.hash,newTable.length);...}此时 T1 的栈中保存着e Anext BT1 还没有修改任何节点的 next 指针。步骤 2T2 完整完成了迁移T2 获得 CPU 时间片完整执行了整个迁移过程和我们上面单线程的演示一样。T2 执行完成后T2 的新数组桶 0B → A → null全局的节点指针被修改了B.next AA.next null这是最关键的一步节点是存在于堆内存中的所有线程共享。T2 修改了 A 和 B 的 next 指针T1 对此完全不知情。步骤 3T1 被唤醒继续执行T1 从挂起的地方恢复执行它的栈中还是e Anext BT1 会继续执行它剩下的代码T1 继续执行第一次循环e A// 已经执行过的EntryK,V next e.next; // next BintnewIndexindexFor(e.hash,newTable.length);// newIndex 0// 头插法插入A到T1自己的新数组桶0e.nextnewTable[newIndex];// A.next nullT1的新数组桶0是空的newTable[newIndex]e;// T1的新数组桶0A → nullenext;// e B准备处理下一个节点当前 T1 的状态T1 的新数组桶 0A → nulle BT1 执行第二次循环e BEntryK,Vnexte.next;// 【致命一步】// 现在e是BB的next已经被T2改成了A// 所以 next A而不是我们预期的nullintnewIndexindexFor(e.hash,newTable.length);// newIndex 0// 头插法插入B到T1的新数组桶0e.nextnewTable[newIndex];// B.next AT1的新数组桶0当前头是AnewTable[newIndex]e;// T1的新数组桶0B → A → nullenext;// e A准备处理下一个节点当前 T1 的状态T1 的新数组桶 0B → A → nulle AT1 执行第三次循环e AEntryK,Vnexte.next;// A.next null这个是对的intnewIndexindexFor(e.hash,newTable.length);// newIndex 0// 头插法插入A到T1的新数组桶0e.nextnewTable[newIndex];// A.next BT1的新数组桶0当前头是BnewTable[newIndex]e;// T1的新数组桶0A → B → A → ...enext;// e null循环结束最终结果T1 的新数组桶 0 中链表变成了A → B → A → B → ...一个无限循环的闭环三、为什么 JDK 1.7 要用头插法既然头插法有这么大的问题为什么 JDK 1.7 还要用它性能原因头插法不需要遍历链表找尾部插入速度是 O(1)比尾插法快很多。设计初衷HashMap 本来就不是为多线程环境设计的设计者认为并发场景应该用Hashtable或者ConcurrentHashMap。四、JDK 1.8 的解决方案JDK 1.8 将扩容时的插入方式改为尾插法迁移时会保持链表的原有顺序不会出现反转因此彻底避免了循环引用的产生。再次强调即使 JDK 1.8 解决了死循环问题HashMap 仍然不是线程安全的。多线程环境下仍然会出现数据丢失、覆盖等问题并发场景请务必使用ConcurrentHashMap。