HashMap的并发问题前言HashMap是Java中最常用的集合类之一但它在线程不安全这一点上坑了无数开发者。本文将深入剖析HashMap在多线程环境下的两个经典问题JDK 1.7的死循环问题JDK 1.8的数据丢失问题一、生活中的并发问题类比可以将其理解为图书馆整理书架想象这样一个场景小明和小红是两个图书管理员他们需要把旧书架的书搬到新书架。旧书架书是按照A→B→C的顺序排列的新书架空的准备放书整理规则每次拿一本书放到新书架的最前面头插法并发事故现场小明拿起书A准备搬突然被叫走去接电话小红趁小明不在把剩下的书全搬完了C→B小明回来手里还拿着书A继续按原计划放书结果书A和书B互相指着对方形成了环二、JDK 1.7的死循环问题2.1 源码分析voidtransfer(Entry[]newTable){Entry[]srctable;intnewCapacitynewTable.length;for(intj0;jsrc.length;j){EntryK,Vesrc[j];if(e!null){src[j]null;do{EntryK,Vnexte.next;// 记录下一个节点intiindexFor(e.hash,newCapacity);// 计算新位置e.nextnewTable[i];// 头插法当前节点的next指向新数组的头部newTable[i]e;// 将当前节点放入新数组头部enext;// 继续处理下一个节点}while(e!null);}}}2.2 头插法头插法的特点是后插入的在前面导致链表反转。正常单线程执行原链表A → B → C → null 处理A后A → null 处理B后B → A → null 处理C后C → B → A → null 结果链表反转了2.3 并发执行如何形成环初始状态旧数组位置1A → B → null新数组空线程1执行到暂停点eAnextB// 刚计算完新位置i还没来得及放CPU时间片用完线程2完整执行第1步处理A → newTable[i] A → null 第2步处理B → newTable[i] B → A → null 结果新数组变成 B → A → null线程1恢复执行此时线程1的局部变量还是e A但A现在指向nullnext BB现在指向A// 第1轮循环处理AA.nextnewTable[i]// A.next B因为newTable[i]现在是BnewTable[i]A// 新数组变成 A → B → A → B...环形成了// 第2轮循环处理BB.nextnewTable[i]// B.next AnewTable[i]B// 新数组变成 B → A → B...// 无限循环...2.4 后果当调用get()方法时如果命中这个桶就会在环形链表中无限循环CPU飙升到100%三、JDK 1.8的改进与遗留问题3.1 尾插法解决死循环JDK 1.8改用尾插法保持原链表顺序// JDK 1.8的put方法简化版finalVputVal(inthash,Kkey,Vvalue,...){// ... 省略其他代码for(intbinCount0;;binCount){if((ep.next)null){p.nextnewNode(hash,key,value,null);// 尾插法break;}}// ...}尾插法的好处原链表A → B → C迁移后A → B → C顺序不变不会形成环3.2 但数据丢失问题依然存在场景1桶为空的覆盖// 两个线程同时执行这段代码if((ptab[i(n-1)hash])null)tab[i]newNode(hash,key,value,null);执行时序时间线程A线程Btab[i]的状态t1检查tab[i]null → truenullt2检查tab[i]null → truenullt3tab[i] newNode(A)节点At4tab[i] newNode(B)节点BA丢失结果线程A插入的数据被线程B覆盖A丢失。场景2链表尾部的覆盖// 两个线程同时在链表尾部添加for(intbinCount0;;binCount){if((ep.next)null){p.nextnewNode(hash,key,value,null);// 并发覆盖点break;}}执行时序时间线程A线程B链表状态t1遍历到尾部准备插入YX → nullt2遍历到尾部准备插入ZX → nullt3p.next newNode(Y)X → Y → nullt4p.next newNode(Z)X → Z → nullY丢失场景3size计数错误if(sizethreshold)// 非原子操作resize();执行时序初始size 8, threshold 12 线程A读取size8 → 加1 → size9 线程B读取size8 → 加1 → size9 实际插入了2个元素但size只增加了1 本该扩容时没扩容导致性能下降四、图解对比JDK 1.7 死循环并发异常AB正常情况ABCnullJDK 1.8 数据丢失结果B aloneA丢失线程B插入检查空位插入B覆盖A线程A插入检查空位准备插入A五、如何正确使用5.1 三种解决方案对比方案优点缺点适用场景Collections.synchronizedMap简单性能差全表锁并发量低Hashtable现成的性能差遗留系统ConcurrentHashMap性能好稍复杂高并发推荐5.2 ConcurrentHashMap的正确姿势// 推荐使用MapString,StringmapnewConcurrentHashMap();// Java 8 的优雅操作map.computeIfAbsent(key,k-value);map.merge(key,value,(old,new)-oldnew);// 原子操作map.putIfAbsent(key,value);// 不存在才放入六、总结JDK版本演进JDK 1.7头插法 → 并发死循环JDK 1.8尾插法 → 解决了死循环但仍有数据丢失永远记住多线程环境下用ConcurrentHashMap面试金句“HashMap在单线程环境下完美工作但在多线程并发put时JDK 1.7可能形成环形链表导致死循环JDK 1.8虽然通过尾插法解决了死循环但仍然存在数据覆盖丢失的问题。因此在并发场景下必须使用ConcurrentHashMap。”
HashMap的并发问题
HashMap的并发问题前言HashMap是Java中最常用的集合类之一但它在线程不安全这一点上坑了无数开发者。本文将深入剖析HashMap在多线程环境下的两个经典问题JDK 1.7的死循环问题JDK 1.8的数据丢失问题一、生活中的并发问题类比可以将其理解为图书馆整理书架想象这样一个场景小明和小红是两个图书管理员他们需要把旧书架的书搬到新书架。旧书架书是按照A→B→C的顺序排列的新书架空的准备放书整理规则每次拿一本书放到新书架的最前面头插法并发事故现场小明拿起书A准备搬突然被叫走去接电话小红趁小明不在把剩下的书全搬完了C→B小明回来手里还拿着书A继续按原计划放书结果书A和书B互相指着对方形成了环二、JDK 1.7的死循环问题2.1 源码分析voidtransfer(Entry[]newTable){Entry[]srctable;intnewCapacitynewTable.length;for(intj0;jsrc.length;j){EntryK,Vesrc[j];if(e!null){src[j]null;do{EntryK,Vnexte.next;// 记录下一个节点intiindexFor(e.hash,newCapacity);// 计算新位置e.nextnewTable[i];// 头插法当前节点的next指向新数组的头部newTable[i]e;// 将当前节点放入新数组头部enext;// 继续处理下一个节点}while(e!null);}}}2.2 头插法头插法的特点是后插入的在前面导致链表反转。正常单线程执行原链表A → B → C → null 处理A后A → null 处理B后B → A → null 处理C后C → B → A → null 结果链表反转了2.3 并发执行如何形成环初始状态旧数组位置1A → B → null新数组空线程1执行到暂停点eAnextB// 刚计算完新位置i还没来得及放CPU时间片用完线程2完整执行第1步处理A → newTable[i] A → null 第2步处理B → newTable[i] B → A → null 结果新数组变成 B → A → null线程1恢复执行此时线程1的局部变量还是e A但A现在指向nullnext BB现在指向A// 第1轮循环处理AA.nextnewTable[i]// A.next B因为newTable[i]现在是BnewTable[i]A// 新数组变成 A → B → A → B...环形成了// 第2轮循环处理BB.nextnewTable[i]// B.next AnewTable[i]B// 新数组变成 B → A → B...// 无限循环...2.4 后果当调用get()方法时如果命中这个桶就会在环形链表中无限循环CPU飙升到100%三、JDK 1.8的改进与遗留问题3.1 尾插法解决死循环JDK 1.8改用尾插法保持原链表顺序// JDK 1.8的put方法简化版finalVputVal(inthash,Kkey,Vvalue,...){// ... 省略其他代码for(intbinCount0;;binCount){if((ep.next)null){p.nextnewNode(hash,key,value,null);// 尾插法break;}}// ...}尾插法的好处原链表A → B → C迁移后A → B → C顺序不变不会形成环3.2 但数据丢失问题依然存在场景1桶为空的覆盖// 两个线程同时执行这段代码if((ptab[i(n-1)hash])null)tab[i]newNode(hash,key,value,null);执行时序时间线程A线程Btab[i]的状态t1检查tab[i]null → truenullt2检查tab[i]null → truenullt3tab[i] newNode(A)节点At4tab[i] newNode(B)节点BA丢失结果线程A插入的数据被线程B覆盖A丢失。场景2链表尾部的覆盖// 两个线程同时在链表尾部添加for(intbinCount0;;binCount){if((ep.next)null){p.nextnewNode(hash,key,value,null);// 并发覆盖点break;}}执行时序时间线程A线程B链表状态t1遍历到尾部准备插入YX → nullt2遍历到尾部准备插入ZX → nullt3p.next newNode(Y)X → Y → nullt4p.next newNode(Z)X → Z → nullY丢失场景3size计数错误if(sizethreshold)// 非原子操作resize();执行时序初始size 8, threshold 12 线程A读取size8 → 加1 → size9 线程B读取size8 → 加1 → size9 实际插入了2个元素但size只增加了1 本该扩容时没扩容导致性能下降四、图解对比JDK 1.7 死循环并发异常AB正常情况ABCnullJDK 1.8 数据丢失结果B aloneA丢失线程B插入检查空位插入B覆盖A线程A插入检查空位准备插入A五、如何正确使用5.1 三种解决方案对比方案优点缺点适用场景Collections.synchronizedMap简单性能差全表锁并发量低Hashtable现成的性能差遗留系统ConcurrentHashMap性能好稍复杂高并发推荐5.2 ConcurrentHashMap的正确姿势// 推荐使用MapString,StringmapnewConcurrentHashMap();// Java 8 的优雅操作map.computeIfAbsent(key,k-value);map.merge(key,value,(old,new)-oldnew);// 原子操作map.putIfAbsent(key,value);// 不存在才放入六、总结JDK版本演进JDK 1.7头插法 → 并发死循环JDK 1.8尾插法 → 解决了死循环但仍有数据丢失永远记住多线程环境下用ConcurrentHashMap面试金句“HashMap在单线程环境下完美工作但在多线程并发put时JDK 1.7可能形成环形链表导致死循环JDK 1.8虽然通过尾插法解决了死循环但仍然存在数据覆盖丢失的问题。因此在并发场景下必须使用ConcurrentHashMap。”
