1. 从一个线上告警说起为什么JDK8的HashMap扩容值得反复看很多同学觉得HashMap这东西面试前背一背“数组链表红黑树”“负载因子0.75”“扩容2倍”就完事了真到线上出问题的时候日志里一堆线程卡在HashMap.resize上CPU飙到90%以上才开始回头翻源码。我印象很深的一次某服务在晚高峰突然大面积超时堆栈抓下来一看几十个业务线程全停在transfer相关的调用链上——那是JDK7的经典问题环形链表导致get操作死循环。后来升级到JDK8同样的压力场景下虽然不再死循环了但扩容带来的停顿依然存在只是表现形式从“死循环”变成了“CPU瞬时冲高响应毛刺”。所以这篇东西我不打算写成又一篇“HashMap八股文”而是把JDK8扩容这块真正拆开讲透为什么JDK8要把头插法改成尾插法、扩容时元素到底怎么重新分布、高低位链表拆分这个设计到底妙在哪、1.8里还有哪些坑是文档不会告诉你的。核心关键词就三个JDK8 HashMap、扩容、尾插法。适合已经会基本用HashMap、但想搞清楚底层到底发生什么的同学也适合被扩容问题坑过、想彻底弄明白的运维和中间件方向的朋友。先把结论摆前面JDK8的扩容不是简单地把每个元素重新hash一遍再塞进去而是利用容量永远是2的幂这个特性通过一次位运算就把原链表拆成“低位链”和“高位链”两条分别挂到新数组的两个位置上。这个设计让扩容从“逐个rehash”变成了“批量搬迁”而尾插法则是保证搬迁过程中链表顺序稳定、避免环形结构的关键。下面一层层剥。2. 扩容这件事JDK8到底改了什么2.1 先搞清楚扩容的触发条件HashMap的扩容不是随便触发的它有一个明确的阈值叫threshold等于容量 × 负载因子。默认容量16、负载因子0.75那么阈值就是12。也就是说当你往表里放第13个元素准确说是size超过12的时候就会触发一次扩容。这里有个容易搞混的点触发扩容的是size不是数组占用槽位的数量。举个例子如果所有元素都hash到了同一个桶里形成一条长链表那么数组可能只用了1个槽位但size已经到13了照样扩容。反过来如果元素分散在12个不同槽位每个槽位1个元素size到13同样扩容。所以判断依据始终是键值对总数。扩容的入口在putVal方法里放完元素后有这么一段if (size threshold) resize();注意是size之后比较也就是先加再判断。这个细节在分析并发场景时很重要因为size的自增不是原子的多线程下可能两个线程同时判断为需要扩容然后都去执行resize这就是并发问题的源头之一。2.2 容量为什么必须是2的幂这是理解整个扩容机制的地基。JDK8里计算元素落在哪个桶用的是(n - 1) hashn是数组长度。当n是2的幂时n-1的二进制是低位全1比如n16n-115二进制1111。这时候(n-1) hash等价于hash % n但位运算比取模快得多。这就是为什么容量一定要是2的幂——为了让取模运算能用位与替代。那如果构造HashMap时传了个不是2的幂的初始容量呢比如new HashMap(10)。它不会直接用10而是通过tableSizeFor方法把你传的数向上取到最近的2的幂10会变成16。这个方法的实现很巧妙用了一连串无符号右移和或运算把最高位1后面的所有位都填成1最后加1。你可以自己拿几个数试一下比如传17会得到32传100会得到128。提示如果你明确知道要存多少元素初始化时直接传预期数量避免多次扩容。但要注意传进去的值会被向上取整到2的幂而且实际阈值是容量乘0.75所以想存100个元素传100进去最终容量是128阈值是96还是会扩容一次。稳妥做法是传预期数量 / 0.75 1。2.3 头插法与尾插法的分水岭JDK7的扩容用的是头插法新来的元素往链表头部塞。这个做法在单线程下没问题但多线程并发扩容时两个线程同时操作同一条链表可能把链表指针指反形成环形结构。之后任何一次get操作落到这个环上就会无限循环CPU直接打满。这就是当年那个著名的“HashMap死循环”问题。JDK8改成了尾插法新元素往链表尾部挂。这个改动本身不能完全解决并发安全问题HashMap本来就不是线程安全的但它消除了扩容时形成环形的可能。因为尾插法在搬迁时保持了元素的相对顺序不会出现指针反转。注意这里说的是“消除了扩容导致环形结构的可能”不是说HashMap在并发下就安全了并发put依然可能丢数据、size不准该用ConcurrentHashMap还是得用。尾插法的另一个好处是顺序稳定。头插法会把链表顺序颠倒尾插法保持原序。这在某些依赖遍历顺序的场景下虽然规范上不保证顺序会让人少踩一些坑。3. 扩容的核心高低位链表拆分到底怎么算3.1 一次位运算替代重新hash这是JDK8扩容最精髓的地方。JDK7扩容时每个元素都要重新计算hash (newCap - 1)相当于把所有元素重新hash一遍。JDK8不这么干它利用了一个数学性质。假设旧容量是16新容量是32。对于任意一个hash值它和15做与运算得到旧位置和31做与运算得到新位置。这两个位置有什么关系关键看hash值的第5位因为16是2的4次方第5位是新增的那一位。如果hash的第5位是0那么hash 31的结果和hash 15一样元素留在原位置。如果hash的第5位是1那么hash 31的结果等于hash 15 16也就是原位置加上旧容量。用代码表示就是if ((e.hash oldCap) 0) { // 留在低位链位置不变 } else { // 挂到高位链位置 原位置 oldCap }注意这里是e.hash oldCap不是e.hash (oldCap - 1)。oldCap是16二进制10000只有第5位是1。所以这个与运算就是在检查hash的第5位。这个设计把“重新计算位置”简化成了“检查一个bit”效率提升非常明显。3.2 loHead/loTail与hiHead/hiTail四指针拆链具体实现上JDK8用了四个指针来拆分链表NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null);这段代码遍历原链表把每个节点按e.hash oldCap的结果分到两条链上。lo链留在新数组的j位置hi链挂到j oldCap位置。整个过程只遍历一次链表不需要重新计算hash也不需要为每个节点单独找位置。我实测过一个极端场景一张表里所有元素都hash到同一个桶形成一条1000个节点的链表。JDK7扩容要重新计算1000次hash和取模JDK8只需要遍历一次、做1000次位与判断然后两条链直接挂过去。在扩容这个环节JDK8的耗时大概只有JDK7的三分之一到一半元素越多差距越明显。3.3 红黑树节点怎么拆如果桶里已经是红黑树了链表长度超过8且数组长度达到64时会树化扩容时不能简单按链表拆。JDK8的处理逻辑是先按链表的方式遍历树节点用同样的高低位规则拆成两条链然后判断每条链的长度。如果链长度小于等于6退化成普通链表。如果链长度大于6重新树化成红黑树。这里有个细节树化阈值是8退化阈值是6中间留了个7作为缓冲避免在7附近反复树化和退化造成性能抖动。这个“留缓冲”的思路在很多地方都能看到比如线程池的核心线程数和最大线程数之间也会留余量。if (loHead ! null) { if (lc UNTREEIFY_THRESHOLD) tab[index] loHead.untreeify(map); else { tab[index] loHead; if (hiHead ! null) loHead.treeify(tab); } }注意if (hiHead ! null)这个判断如果高位链为空说明整棵树都还在低位那就不用重新树化直接复用原来的树结构。只有两条链都不为空时才需要把低位链重新树化。这个优化省掉了一次不必要的树化操作。4. 手把手跟一遍resize的完整流程4.1 新容量和新阈值的确定resize方法开头先判断旧容量if (oldCap 0) { if (oldCap MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return oldTab; } else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThreshold oldThreshold 1; }逻辑很清晰如果旧容量已经达到最大容量2的30次方就把阈值设为Integer.MAX_VALUE不再扩容。否则新容量等于旧容量左移一位也就是乘2。如果旧容量大于等于默认初始容量16新阈值也乘2。如果旧容量是0但阈值大于0说明是初始化时指定了容量但还没放元素这时候把容量设为阈值。如果两者都是0就用默认值16和12。注意oldCap 1在oldCap接近最大值时可能溢出成负数所以前面有oldCap MAXIMUM_CAPACITY的判断兜底。这个边界处理在实际写代码时很容易漏掉。4.2 数据搬迁的两种路径新数组创建好之后遍历旧数组的每个槽位。如果槽位为空就跳过如果只有一个节点就直接放到新位置如果是链表或树就走拆分逻辑。单节点的处理最简单if (e.next null) newTab[e.hash (newCap - 1)] e;这里还是用了e.hash (newCap - 1)因为单节点没有链表结构直接算新位置就行不需要走高低位拆分。链表和树的处理就是前面讲的高低位拆分。整个搬迁过程是顺序遍历旧数组、逐个槽位处理不是一次性把所有元素拿出来重新分配。这个顺序很重要因为它保证了搬迁过程中旧数组的结构是稳定的不会出现某个槽位被处理两次的情况。4.3 一个具体的数字例子假设旧容量16新容量32。现在有一个hash值为0b10101十进制21的元素。旧位置21 15 5检查第5位21 16 16不为0所以是高位链新位置5 16 21验证21 31 21正确再假设hash值为0b01101十进制13旧位置13 15 13检查第5位13 16 0是低位链新位置还是13验证13 31 13正确你可以拿几个数自己算一下会发现规律非常稳定第5位为0的留在原位第5位为1的移动到原位加16的位置。扩容到64、128也是同样的道理只是检查的bit位往上移。5. 那些文档不会告诉你的坑5.1 扩容时的并发问题依然存在尾插法解决了环形链表但没解决并发安全问题。多线程同时put时可能出现两个线程同时判断size超过阈值都执行resize导致数据覆盖。一个线程在扩容搬迁另一个线程在put可能把元素放到已经被搬迁过的旧槽位导致元素丢失。size字段不是volatile的多线程下读到的值可能不准。我见过有同学说“JDK8的HashMap是线程安全的”这完全是误解。只要有多线程写就必须用ConcurrentHashMap或者加锁没有例外。5.2 初始容量传太大反而浪费有人为了“避免扩容”初始化时直接传个100万。结果就是创建了一个容量为1048576的数组每个槽位8字节引用光数组本身就占8MB。如果实际只存了几百个元素绝大部分槽位是空的内存浪费严重。合理的做法是根据实际数据量估算。比如预计存10万个元素传100000 / 0.75 1 133334向上取到2的幂是131072。这样阈值是98304存10万个元素会扩容一次到262144。如果想完全不扩容传100000 / 0.75再向上取整但这样数组会偏大。我个人的经验是留20%余量就够了没必要追求零扩容。5.3 负载因子0.75不是随便定的0.75这个值是时间和空间权衡的结果。负载因子越高数组利用率越高但哈希冲突概率越大链表越长查询越慢。负载因子越低冲突越少但数组越大内存浪费越多。从概率论角度在理想哈希下负载因子为0.75时一个桶里元素数量的期望值大约是0.75出现长链表的概率很低。如果调到1.0冲突概率明显上升调到0.5内存占用翻倍但查询性能提升有限。所以0.75是个比较平衡的点。当然如果你的场景读多写少、对查询延迟极其敏感可以适当调低负载因子比如0.5。但要注意这会增加扩容频率和内存占用。反过来如果内存紧张、对性能要求不高可以调到0.8甚至0.9但别超过1.0。5.4 树化不是一超过8就发生链表长度超过8只是树化的必要条件之一还有一个条件是数组长度必须达到64。如果数组长度小于64即使链表长度到8了也只会扩容而不是树化。这个设计是为了避免在小数组上过早树化因为小数组扩容成本低扩容后链表自然就短了。if (binCount TREEIFY_THRESHOLD - 1) { if (tab.length MIN_TREEIFY_CAPACITY) resize(); else treeifyBin(tab, hash); }所以如果你发现链表很长但没树化先看看数组长度是不是还没到64。6. 常见问题速查与排查思路问题现象可能原因排查方法解决思路CPU飙高堆栈在resize频繁扩容或并发扩容jstack看线程栈jstat看GC频率预设合理初始容量改用ConcurrentHashMapget操作变慢链表过长或树化失败打印桶分布看最大链表长度检查hashCode实现调整负载因子内存占用异常初始容量过大或负载因子过低dump堆看HashMap实例大小按实际数据量估算容量元素丢失多线程并发put检查是否有共享HashMap加锁或换ConcurrentHashMap扩容后顺序变化正常现象HashMap不保证顺序无需要顺序用LinkedHashMap关于hashCode实现这里多说一句。如果你自定义的对象作为key一定要同时重写hashCode和equals。只重写equals不重写hashCode会导致两个相等的对象hash值不同落到不同桶里HashMap就找不到它们。这个坑我见过太多次了尤其是用IDE自动生成时只勾了equals没勾hashCode。提示排查HashMap问题时可以用反射拿到table字段遍历每个槽位统计链表长度分布。如果发现某个槽位链表特别长基本就是hashCode分布不均的问题。7. 几个能直接抄的优化实践第一初始化时给合理容量。这是收益最明显的一条。比如一个请求级别的缓存Map预计存50个元素直接new HashMap(64)阈值48基本不会扩容。比默认16然后扩容两次要快得多。第二key尽量用不可变对象。String、Integer这些就很好它们的hashCode会缓存计算一次就够了。如果用可变对象做key修改后hash值变了就再也找不到原来的entry了还会造成内存泄漏。第三遍历时用entrySet而不是keySet。for (K key : map.keySet()) { map.get(key); }这种写法每次get都要重新算hash、找桶而entrySet直接拿键值对省掉一次查找。数据量大的时候差距很明显。第四多线程场景直接上ConcurrentHashMap。别想着用Collections.synchronizedMap那个是在每个方法上加锁并发度很低。ConcurrentHashMap在JDK8里用了CASsynchronized锁单个桶并发性能好得多。第五关注扩容时的停顿。如果HashMap很大比如几十万元素一次扩容要搬迁所有元素可能造成几十毫秒的停顿。对延迟敏感的服务要么预设足够大的容量避免扩容要么考虑用支持增量扩容的结构。我在实际项目里踩过最深的坑是一个全局缓存Map在流量突增时反复扩容每次扩容都触发一次Full GC导致服务雪崩。后来改成启动时预热、预设容量问题就消失了。所以别小看这一个new HashMap(capacity)关键时候能救命。最后分享一个看源码的小技巧别一上来就逐行读先画图。把数组、链表、四个拆分指针的关系画出来再对着代码看理解速度会快很多。尤其是高低位拆分那块画一遍图比读十遍代码都管用。
1. 从一个线上告警说起为什么JDK8的HashMap扩容值得反复看很多同学觉得HashMap这东西面试前背一背“数组链表红黑树”“负载因子0.75”“扩容2倍”就完事了真到线上出问题的时候日志里一堆线程卡在HashMap.resize上CPU飙到90%以上才开始回头翻源码。我印象很深的一次某服务在晚高峰突然大面积超时堆栈抓下来一看几十个业务线程全停在transfer相关的调用链上——那是JDK7的经典问题环形链表导致get操作死循环。后来升级到JDK8同样的压力场景下虽然不再死循环了但扩容带来的停顿依然存在只是表现形式从“死循环”变成了“CPU瞬时冲高响应毛刺”。所以这篇东西我不打算写成又一篇“HashMap八股文”而是把JDK8扩容这块真正拆开讲透为什么JDK8要把头插法改成尾插法、扩容时元素到底怎么重新分布、高低位链表拆分这个设计到底妙在哪、1.8里还有哪些坑是文档不会告诉你的。核心关键词就三个JDK8 HashMap、扩容、尾插法。适合已经会基本用HashMap、但想搞清楚底层到底发生什么的同学也适合被扩容问题坑过、想彻底弄明白的运维和中间件方向的朋友。先把结论摆前面JDK8的扩容不是简单地把每个元素重新hash一遍再塞进去而是利用容量永远是2的幂这个特性通过一次位运算就把原链表拆成“低位链”和“高位链”两条分别挂到新数组的两个位置上。这个设计让扩容从“逐个rehash”变成了“批量搬迁”而尾插法则是保证搬迁过程中链表顺序稳定、避免环形结构的关键。下面一层层剥。2. 扩容这件事JDK8到底改了什么2.1 先搞清楚扩容的触发条件HashMap的扩容不是随便触发的它有一个明确的阈值叫threshold等于容量 × 负载因子。默认容量16、负载因子0.75那么阈值就是12。也就是说当你往表里放第13个元素准确说是size超过12的时候就会触发一次扩容。这里有个容易搞混的点触发扩容的是size不是数组占用槽位的数量。举个例子如果所有元素都hash到了同一个桶里形成一条长链表那么数组可能只用了1个槽位但size已经到13了照样扩容。反过来如果元素分散在12个不同槽位每个槽位1个元素size到13同样扩容。所以判断依据始终是键值对总数。扩容的入口在putVal方法里放完元素后有这么一段if (size threshold) resize();注意是size之后比较也就是先加再判断。这个细节在分析并发场景时很重要因为size的自增不是原子的多线程下可能两个线程同时判断为需要扩容然后都去执行resize这就是并发问题的源头之一。2.2 容量为什么必须是2的幂这是理解整个扩容机制的地基。JDK8里计算元素落在哪个桶用的是(n - 1) hashn是数组长度。当n是2的幂时n-1的二进制是低位全1比如n16n-115二进制1111。这时候(n-1) hash等价于hash % n但位运算比取模快得多。这就是为什么容量一定要是2的幂——为了让取模运算能用位与替代。那如果构造HashMap时传了个不是2的幂的初始容量呢比如new HashMap(10)。它不会直接用10而是通过tableSizeFor方法把你传的数向上取到最近的2的幂10会变成16。这个方法的实现很巧妙用了一连串无符号右移和或运算把最高位1后面的所有位都填成1最后加1。你可以自己拿几个数试一下比如传17会得到32传100会得到128。提示如果你明确知道要存多少元素初始化时直接传预期数量避免多次扩容。但要注意传进去的值会被向上取整到2的幂而且实际阈值是容量乘0.75所以想存100个元素传100进去最终容量是128阈值是96还是会扩容一次。稳妥做法是传预期数量 / 0.75 1。2.3 头插法与尾插法的分水岭JDK7的扩容用的是头插法新来的元素往链表头部塞。这个做法在单线程下没问题但多线程并发扩容时两个线程同时操作同一条链表可能把链表指针指反形成环形结构。之后任何一次get操作落到这个环上就会无限循环CPU直接打满。这就是当年那个著名的“HashMap死循环”问题。JDK8改成了尾插法新元素往链表尾部挂。这个改动本身不能完全解决并发安全问题HashMap本来就不是线程安全的但它消除了扩容时形成环形的可能。因为尾插法在搬迁时保持了元素的相对顺序不会出现指针反转。注意这里说的是“消除了扩容导致环形结构的可能”不是说HashMap在并发下就安全了并发put依然可能丢数据、size不准该用ConcurrentHashMap还是得用。尾插法的另一个好处是顺序稳定。头插法会把链表顺序颠倒尾插法保持原序。这在某些依赖遍历顺序的场景下虽然规范上不保证顺序会让人少踩一些坑。3. 扩容的核心高低位链表拆分到底怎么算3.1 一次位运算替代重新hash这是JDK8扩容最精髓的地方。JDK7扩容时每个元素都要重新计算hash (newCap - 1)相当于把所有元素重新hash一遍。JDK8不这么干它利用了一个数学性质。假设旧容量是16新容量是32。对于任意一个hash值它和15做与运算得到旧位置和31做与运算得到新位置。这两个位置有什么关系关键看hash值的第5位因为16是2的4次方第5位是新增的那一位。如果hash的第5位是0那么hash 31的结果和hash 15一样元素留在原位置。如果hash的第5位是1那么hash 31的结果等于hash 15 16也就是原位置加上旧容量。用代码表示就是if ((e.hash oldCap) 0) { // 留在低位链位置不变 } else { // 挂到高位链位置 原位置 oldCap }注意这里是e.hash oldCap不是e.hash (oldCap - 1)。oldCap是16二进制10000只有第5位是1。所以这个与运算就是在检查hash的第5位。这个设计把“重新计算位置”简化成了“检查一个bit”效率提升非常明显。3.2 loHead/loTail与hiHead/hiTail四指针拆链具体实现上JDK8用了四个指针来拆分链表NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null);这段代码遍历原链表把每个节点按e.hash oldCap的结果分到两条链上。lo链留在新数组的j位置hi链挂到j oldCap位置。整个过程只遍历一次链表不需要重新计算hash也不需要为每个节点单独找位置。我实测过一个极端场景一张表里所有元素都hash到同一个桶形成一条1000个节点的链表。JDK7扩容要重新计算1000次hash和取模JDK8只需要遍历一次、做1000次位与判断然后两条链直接挂过去。在扩容这个环节JDK8的耗时大概只有JDK7的三分之一到一半元素越多差距越明显。3.3 红黑树节点怎么拆如果桶里已经是红黑树了链表长度超过8且数组长度达到64时会树化扩容时不能简单按链表拆。JDK8的处理逻辑是先按链表的方式遍历树节点用同样的高低位规则拆成两条链然后判断每条链的长度。如果链长度小于等于6退化成普通链表。如果链长度大于6重新树化成红黑树。这里有个细节树化阈值是8退化阈值是6中间留了个7作为缓冲避免在7附近反复树化和退化造成性能抖动。这个“留缓冲”的思路在很多地方都能看到比如线程池的核心线程数和最大线程数之间也会留余量。if (loHead ! null) { if (lc UNTREEIFY_THRESHOLD) tab[index] loHead.untreeify(map); else { tab[index] loHead; if (hiHead ! null) loHead.treeify(tab); } }注意if (hiHead ! null)这个判断如果高位链为空说明整棵树都还在低位那就不用重新树化直接复用原来的树结构。只有两条链都不为空时才需要把低位链重新树化。这个优化省掉了一次不必要的树化操作。4. 手把手跟一遍resize的完整流程4.1 新容量和新阈值的确定resize方法开头先判断旧容量if (oldCap 0) { if (oldCap MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return oldTab; } else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThreshold oldThreshold 1; }逻辑很清晰如果旧容量已经达到最大容量2的30次方就把阈值设为Integer.MAX_VALUE不再扩容。否则新容量等于旧容量左移一位也就是乘2。如果旧容量大于等于默认初始容量16新阈值也乘2。如果旧容量是0但阈值大于0说明是初始化时指定了容量但还没放元素这时候把容量设为阈值。如果两者都是0就用默认值16和12。注意oldCap 1在oldCap接近最大值时可能溢出成负数所以前面有oldCap MAXIMUM_CAPACITY的判断兜底。这个边界处理在实际写代码时很容易漏掉。4.2 数据搬迁的两种路径新数组创建好之后遍历旧数组的每个槽位。如果槽位为空就跳过如果只有一个节点就直接放到新位置如果是链表或树就走拆分逻辑。单节点的处理最简单if (e.next null) newTab[e.hash (newCap - 1)] e;这里还是用了e.hash (newCap - 1)因为单节点没有链表结构直接算新位置就行不需要走高低位拆分。链表和树的处理就是前面讲的高低位拆分。整个搬迁过程是顺序遍历旧数组、逐个槽位处理不是一次性把所有元素拿出来重新分配。这个顺序很重要因为它保证了搬迁过程中旧数组的结构是稳定的不会出现某个槽位被处理两次的情况。4.3 一个具体的数字例子假设旧容量16新容量32。现在有一个hash值为0b10101十进制21的元素。旧位置21 15 5检查第5位21 16 16不为0所以是高位链新位置5 16 21验证21 31 21正确再假设hash值为0b01101十进制13旧位置13 15 13检查第5位13 16 0是低位链新位置还是13验证13 31 13正确你可以拿几个数自己算一下会发现规律非常稳定第5位为0的留在原位第5位为1的移动到原位加16的位置。扩容到64、128也是同样的道理只是检查的bit位往上移。5. 那些文档不会告诉你的坑5.1 扩容时的并发问题依然存在尾插法解决了环形链表但没解决并发安全问题。多线程同时put时可能出现两个线程同时判断size超过阈值都执行resize导致数据覆盖。一个线程在扩容搬迁另一个线程在put可能把元素放到已经被搬迁过的旧槽位导致元素丢失。size字段不是volatile的多线程下读到的值可能不准。我见过有同学说“JDK8的HashMap是线程安全的”这完全是误解。只要有多线程写就必须用ConcurrentHashMap或者加锁没有例外。5.2 初始容量传太大反而浪费有人为了“避免扩容”初始化时直接传个100万。结果就是创建了一个容量为1048576的数组每个槽位8字节引用光数组本身就占8MB。如果实际只存了几百个元素绝大部分槽位是空的内存浪费严重。合理的做法是根据实际数据量估算。比如预计存10万个元素传100000 / 0.75 1 133334向上取到2的幂是131072。这样阈值是98304存10万个元素会扩容一次到262144。如果想完全不扩容传100000 / 0.75再向上取整但这样数组会偏大。我个人的经验是留20%余量就够了没必要追求零扩容。5.3 负载因子0.75不是随便定的0.75这个值是时间和空间权衡的结果。负载因子越高数组利用率越高但哈希冲突概率越大链表越长查询越慢。负载因子越低冲突越少但数组越大内存浪费越多。从概率论角度在理想哈希下负载因子为0.75时一个桶里元素数量的期望值大约是0.75出现长链表的概率很低。如果调到1.0冲突概率明显上升调到0.5内存占用翻倍但查询性能提升有限。所以0.75是个比较平衡的点。当然如果你的场景读多写少、对查询延迟极其敏感可以适当调低负载因子比如0.5。但要注意这会增加扩容频率和内存占用。反过来如果内存紧张、对性能要求不高可以调到0.8甚至0.9但别超过1.0。5.4 树化不是一超过8就发生链表长度超过8只是树化的必要条件之一还有一个条件是数组长度必须达到64。如果数组长度小于64即使链表长度到8了也只会扩容而不是树化。这个设计是为了避免在小数组上过早树化因为小数组扩容成本低扩容后链表自然就短了。if (binCount TREEIFY_THRESHOLD - 1) { if (tab.length MIN_TREEIFY_CAPACITY) resize(); else treeifyBin(tab, hash); }所以如果你发现链表很长但没树化先看看数组长度是不是还没到64。6. 常见问题速查与排查思路问题现象可能原因排查方法解决思路CPU飙高堆栈在resize频繁扩容或并发扩容jstack看线程栈jstat看GC频率预设合理初始容量改用ConcurrentHashMapget操作变慢链表过长或树化失败打印桶分布看最大链表长度检查hashCode实现调整负载因子内存占用异常初始容量过大或负载因子过低dump堆看HashMap实例大小按实际数据量估算容量元素丢失多线程并发put检查是否有共享HashMap加锁或换ConcurrentHashMap扩容后顺序变化正常现象HashMap不保证顺序无需要顺序用LinkedHashMap关于hashCode实现这里多说一句。如果你自定义的对象作为key一定要同时重写hashCode和equals。只重写equals不重写hashCode会导致两个相等的对象hash值不同落到不同桶里HashMap就找不到它们。这个坑我见过太多次了尤其是用IDE自动生成时只勾了equals没勾hashCode。提示排查HashMap问题时可以用反射拿到table字段遍历每个槽位统计链表长度分布。如果发现某个槽位链表特别长基本就是hashCode分布不均的问题。7. 几个能直接抄的优化实践第一初始化时给合理容量。这是收益最明显的一条。比如一个请求级别的缓存Map预计存50个元素直接new HashMap(64)阈值48基本不会扩容。比默认16然后扩容两次要快得多。第二key尽量用不可变对象。String、Integer这些就很好它们的hashCode会缓存计算一次就够了。如果用可变对象做key修改后hash值变了就再也找不到原来的entry了还会造成内存泄漏。第三遍历时用entrySet而不是keySet。for (K key : map.keySet()) { map.get(key); }这种写法每次get都要重新算hash、找桶而entrySet直接拿键值对省掉一次查找。数据量大的时候差距很明显。第四多线程场景直接上ConcurrentHashMap。别想着用Collections.synchronizedMap那个是在每个方法上加锁并发度很低。ConcurrentHashMap在JDK8里用了CASsynchronized锁单个桶并发性能好得多。第五关注扩容时的停顿。如果HashMap很大比如几十万元素一次扩容要搬迁所有元素可能造成几十毫秒的停顿。对延迟敏感的服务要么预设足够大的容量避免扩容要么考虑用支持增量扩容的结构。我在实际项目里踩过最深的坑是一个全局缓存Map在流量突增时反复扩容每次扩容都触发一次Full GC导致服务雪崩。后来改成启动时预热、预设容量问题就消失了。所以别小看这一个new HashMap(capacity)关键时候能救命。最后分享一个看源码的小技巧别一上来就逐行读先画图。把数组、链表、四个拆分指针的关系画出来再对着代码看理解速度会快很多。尤其是高低位拆分那块画一遍图比读十遍代码都管用。
