JDK1.8 HashMap 并发扩容数据丢失问题分析一、核心结论JDK 1.8 的 HashMap 仅通过尾插法解决了 JDK1.7 并发扩容时环形链表死循环问题但没有解决并发扩容导致的数据丢失问题HashMap 依旧线程不安全多线程同时触发扩容依然会出现元素丢失、数据覆盖现象。二、场景前置条件HashMap 原始数组 table 容量 2数组下标 1 位置链表3 - 7 - 5存在两个并发线程线程 A、线程 B同时执行扩容resize()方法JDK1.8 扩容逻辑按节点 hash 高位区分原链表拆分为两条子链表低位链表留在原下标高位链表迁移至原下标 原容量位置采用尾插法迁移节点三、线程调度时序复现数据丢失过程步骤 1两线程同时进入扩容逻辑线程 A 中途阻塞线程 A、B 同步读取旧数组开始遍历下标 1 的链表迁移节点线程 A 遍历到节点e3预存下一个节点引用next7此时 CPU 切换线程 A 被阻塞挂起。步骤 2线程 B 完整执行扩容完成数组替换线程 B 不受阻塞完整遍历整条链表3-7-5按 hash 拆分迁移元素 5hash 高位为 0留在新数组下标 1元素 3、7hash 高位为 1迁移至新数组下标 3形成链表3-7-null线程 B 完成全部节点迁移将扩容后的新数组赋值给 HashMap 全局变量table旧数组引用失效。此时内存中最新 table 状态table[1] 5table[3] 3 - 7 - null步骤 3线程 A 恢复时间片基于旧引用继续遍历丢数据线程 A 被唤醒后持有的仍是扩容前旧链表的引用继续执行循环先处理节点e3完成迁移读取预存的next7赋值给e继续处理节点 7读取节点 7 的后继指针7.next nullnext赋值为 null循环判定next null直接终止链表遍历。步骤 4最终结果 —— 元素 5 永久丢失线程 A 只遍历了3、7两个节点完全没有读取到节点 5不会对 5 做任何迁移操作线程 A 迁移完成后覆盖数组最终新数组中不存在元素 5数据丢失。
JDK1.8 HashMap 并发扩容数据丢失问题分析一、核心结论JDK 1.8 的 HashMap 仅通过尾插法解决了 JDK1.7 并发扩容时环形链表死循环问题但没有解决并发扩容导致的数据丢失问题HashMap 依旧线程不安全多线程同时触发扩容依然会出现元素丢失、数据覆盖现象。二、场景前置条件HashMap 原始数组 table 容量 2数组下标 1 位置链表3 - 7 - 5存在两个并发线程线程 A、线程 B同时执行扩容resize()方法JDK1.8 扩容逻辑按节点 hash 高位区分原链表拆分为两条子链表低位链表留在原下标高位链表迁移至原下标 原容量位置采用尾插法迁移节点三、线程调度时序复现数据丢失过程步骤 1两线程同时进入扩容逻辑线程 A 中途阻塞线程 A、B 同步读取旧数组开始遍历下标 1 的链表迁移节点线程 A 遍历到节点e3预存下一个节点引用next7此时 CPU 切换线程 A 被阻塞挂起。步骤 2线程 B 完整执行扩容完成数组替换线程 B 不受阻塞完整遍历整条链表3-7-5按 hash 拆分迁移元素 5hash 高位为 0留在新数组下标 1元素 3、7hash 高位为 1迁移至新数组下标 3形成链表3-7-null线程 B 完成全部节点迁移将扩容后的新数组赋值给 HashMap 全局变量table旧数组引用失效。此时内存中最新 table 状态table[1] 5table[3] 3 - 7 - null步骤 3线程 A 恢复时间片基于旧引用继续遍历丢数据线程 A 被唤醒后持有的仍是扩容前旧链表的引用继续执行循环先处理节点e3完成迁移读取预存的next7赋值给e继续处理节点 7读取节点 7 的后继指针7.next nullnext赋值为 null循环判定next null直接终止链表遍历。步骤 4最终结果 —— 元素 5 永久丢失线程 A 只遍历了3、7两个节点完全没有读取到节点 5不会对 5 做任何迁移操作线程 A 迁移完成后覆盖数组最终新数组中不存在元素 5数据丢失。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
