翻了翻前几天的笔记day05结束的时候我说“集合框架值得单独拿出一篇来写”今天就用这篇JAVA学习笔记day06来填坑。前面几天我们一直在跟基础语法、面向对象、异常处理打交道到了集合这块说实话才是真正开始接触Java日常开发里最常用、也最容易写出问题代码的地方。我的计划是把集合框架里最核心的HashMap拎出来讲透不光是会用还得知道它底层发生了什么、为什么JDK 8要改成那样的结构、什么场景下它会变慢、哪些API用起来和我们直觉相反。这一篇的内容量不小但读完之后你再看集合相关的问题应该会比以前清晰很多。这篇笔记适合正在学Java基础、准备找工作刷题、或者写了两年代码但一直对HashMap一知半解的同学。我不打算把整个集合框架的所有类都过一遍那样又长又散而是挑最典型的HashMap作为主线牵一发动全身把集合框架的关键设计思路都带出来。1. 为什么day06必须先讲HashMap集合框架里的核心枢纽今天早上我花了一个多小时扒拉集合框架的继承体系发现一个很有意思的事情如果你把集合框架比作一个工具箱HashMap就是那把被拿出来用次数最多的螺丝刀——到处都能见到它但很多人拧螺丝的方式其实是错的。1.1 ArrayList和HashMap两个最常用集合的定位差异我见过很多刚学Java的同学一开始对HashMap有误解觉得它不就是个“存键值对的东西”。这个理解没错但不完整。举个实际的例子。假设我要记录班里每个学生的成绩如果用ArrayList我需要写一个Student类保存姓名和分数然后遍历去找。而用HashMap我可以直接map.put(张三, 89)然后map.get(张三)一秒取出结果。这背后是两个完全不同的数据结构逻辑ArrayList依赖下标它的查询快是因为结构简单HashMap依赖哈希值它的查询快是因为通过散列直接定位。但说说我踩过的坑吧。早期我用HashMap的时候总喜欢在上面做遍历然后拼字符串。后来才发现如果你只是要遍历所有的key或者value需要分清楚遍历的是哪个视角。比如map.keySet()拿到的key集合、map.values()拿到的value集合、map.entrySet()拿到的是键值对。这三个视角迭代出来的元素类型完全不一样很多人包括当年的我会用错。1.2 哈希表的通用思路用空间换时间的典型代表我们在day04学数组的时候说过数组的随机访问是O(1)这个快是基于“我知道下标”的前提。HashMap的核心思想就是把“我要找的key”通过一个哈希函数映射成“数组的一个下标”然后直接用下标去访问。这个思路大家可以用生活里的场景来类比你去一个超大的图书馆借书每本书的编号是按照某种规则生成的。你不需要从第一排书架开始一本一本找而是先根据编号规则算出这本书大概在哪个区再走到那个区去精确查找。HashMap就是那个“编号规则”加上“分区存放”的组合体。哈希函数本身不是Java发明的概念但在HashMap里这个函数的实现质量直接决定了散列是否均匀、查找是否高效。我在实际调试的时候遇到过一种情况自定义了一个对象作为key结果这个对象的哈希值分布非常差大量的对象落在同一个数组位置上HashMap直接退化成了链表查询慢得离谱。这个问题在后面的章节我会专门展开说。1.3 为什么不建议把整个集合框架背下来这里插一段我的学习体会。很多同学学集合的时候会去背“哪个类是线程安全的”“哪个类底层是数组”这类结论。但我觉得死记这些结论是有代价的——你会失去判断力。比如有人背过“HashMap不是线程安全的”然后写代码的时候用Hashtable替代。可实际情况是Hashtable因为所有方法都加了锁并发性能很差现代并发场景下更多人用ConcurrentHashMap。但这些结论不是靠背的而是靠理解哈希表和并发模型推出来的。所以day06这篇笔记我的侧重点是让你看懂HashMap的“设计逻辑”而不是给你一份“API速查表”。把逻辑看懂了很多问题不用背也能推导出来。2. HashMap的底子从数组到链表再到红黑树的层层递进我第一次看HashMap的源码时发现它底层结构挺复杂的数组里面套链表链表还可能变成红黑树。当时我就想为什么要搞这么复杂直接像ArrayList那样纯数组不行吗答案是如果纯数组key的哈希值万一冲突了就没地方放了。2.1 哈希冲突是怎么发生的鸽笼原理的现实版HashMap底层维护了一个Node数组每个Node是一个链表节点既可以存key、value也可以指向下一个节点。我们往HashMap里放数据流程是这样的对key调用hashCode()方法得到一个int值。对这个int值进行二次扰动运算让高16位也参与进来。用扰动后的结果和数组长度减一做按位与得到数组下标。如果该下标位置是空的直接放入如果不是空的说明哈希冲突了就把新节点挂到链表或红黑树上。关于第4步哈希冲突的本质可以用一个生活化的例子解释假设你有一个能放十个包裹的储物柜但有一百个人都要来存东西储物柜的格子肯定不够用必然后来的人得跟前面的人挤在同一个格子里。数组长度和哈希值的组合决定了冲突的概率一旦冲突HashMap就得用额外结构来存这些“挤在一起”的元素。我在学习的时候一开始不理解为什么取下标要用“数组长度减一做按位与”而不是直接用hash % length取模。后来查了资料发现当数组长度是2的幂时hash (length - 1)等价于hash % length但位运算比取模快得多。这也是HashMap要求数组长度必须是2的幂的根本原因。这个细节你在读源码时如果不留意会觉得纯属巧合。2.2 JDK 7到JDK 8链表改红黑树这个改动为什么重要JDK 8之前HashMap如果发生哈希冲突新的节点是头插法插入链表也就是后来的节点放在链表头部。这样做的好处是插入效率高不用从头遍历到尾坏处是在并发扩容的情况下可能形成环形链表从此get操作进入死循环CPU飙到100%。我早年在某公司的内部交流群里看到有位前辈分享过一个线上事故某台机器在请求高峰期CPU被打满排查了几天最后定位到就是HashMap在多线程环境下扩容导致的死循环。那时候还是JDK 7为主这个坑几乎是所有面试必问的经典题。JDK 8做了两处关键改动一是链表插入方式从头插改成了尾插二是当链表长度超过阈值8、且数组长度达到64时链表会树化成红黑树。尾插法修复了扩容时的环形链表问题红黑树则是为了对抗大量冲突时的性能退化。我当时读源码读到TreeNode的时候卡了一下。红黑树涉及左旋、右旋、变色如果从头讲一遍那又是另一篇笔记。这里我建议你只需要理解结论红黑树是一种自平衡的二叉查找树它能保证在最坏情况下查找的复杂度也是O(log n)而链表是O(n)。冲突少的时候链表更省空间冲突多了就升级成树这是在时间和空间之间做的一个动态平衡。2.3 put和get的完整执行流程从调用到返回看源码时把put和get的流程理清楚胜过看十篇博客。我用自己的话给你走一遍。put(key, value)的执行流程如果底层的Node数组是空的先调用resize()初始化数组默认容量是16。计算key的哈希值和下标。如果下标位置是null创建新Node直接放进去结束。如果下标位置不为null说明有元素了如果该位置的key和传入的key完全一样用equals判断直接覆盖旧值。如果该位置是红黑树节点走树的插入逻辑。否则走链表逻辑遍历链表如果找到相同key就覆盖如果遍历到尾部还没找到就在尾部插入新节点。插入后检查链表长度是否超过8超过则尝试树化。插入完成后size加1检查是否需要扩容。get(key)的执行流程计算key的哈希值和下标。如果该下标位置是null返回null。如果该位置的首个节点就是目标节点直接返回。如果该位置是树节点在树中查找。如果是链表遍历链表查找。这里有一个非常值得注意的细节查找和覆盖时判断key相等是先比较哈希值间接通过数组下标体现再比较equals。所以两个对象的hashCode()相等但equals()不相等它们会落在同一个数组位置上反之如果hashCode()不同这两个对象根本不会被分到同一个数组位置甚至不会发生任何比较。我在实际项目中用过一次hashCode()只返回固定值的类做key结果所有元素全部挤在一个桶里插入时速度还行一查询就明显变慢。这个场景恰好帮我加深了对整个结构的理解。3. 扩容机制HashMap性能的隐藏开关如果你只是背“HashMap初始容量16负载因子0.75”那面试还能应付但写代码时遇到性能问题你根本不知道从哪下手。这一节我想把扩容机制掰开揉碎讲清楚。3.1 负载因子为什么是0.75一个你不知道的计算逻辑负载因子load factor的含义是HashMap在自动扩容前可以装多满。默认值是0.75意思是当元素个数达到容量乘以0.75时就触发扩容。那为什么是0.75而不是0.5或者1.0呢网上能找到的解释通常是“时间和空间的折中”。我想进一步拆解一下如果负载因子是1.0意味着数组满了才扩容空间利用率很高但哈希冲突会非常严重链表的平均长度变大查询性能下降。如果负载因子是0.5冲突很少性能很好但有一半的数组槽位是空的空间浪费太大。0.75是经过权衡后的经验值这也是源码注释里提到的“在时间和空间成本之间取得平衡”。有的源码分析文章还会提到0.75和哈希冲突的泊松分布有关系。我读过源码注释里面确实给出了一个概率表负载因子0.75时桶中链表长度达到8的概率已经极其低链表长度到8是树化的阈值到6是退化的阈值。8和6中间隔了一个数的容忍区间目的就是防止链表在边界条件附近反复树化和退化。我说一个我在工作中实际遇到的场景。某次做一个数据上报功能需要往Map里塞几十万条临时数据。一开始用的Map初始容量就是默认16结果频繁扩容扩容要重新计算哈希并搬移所有节点整个批量处理慢了两倍不止。后来我把初始容量直接设置为预计元素数量除以负载因子再加一点余量比如预计放10万条初始容量就设为133334左右的2的幂实际上用131072扩容次数瞬间变成0性能提升非常明显。3.2 扩容时的数据搬移为什么JDK 8的扩容可以不重新计算hash很多不理解扩容机制的同学以为扩容就是把数组变大然后把原数据复制过去。其实扩容还要处理每个节点的新位置。JDK 7的扩容逻辑比较直接遍历所有节点重新计算哈希值和下标然后插入新数组。JDK 8做了一点优化因为数组长度是2的幂元素在新数组中的下标只可能是原来的下标或者“原下标加原数组长度”这两个位置。判断依据是新增的那一位bit是0还是1。这个优化也许初看你不太容易消化。我举个例子假设原来数组长度是16某个元素原来落在下标5的位置。扩容到32之后它要么还在5要么在5加16的位置也就是21。判断时看key的哈希值第5位二进制位如果是0就留在原位如果是1就挪到高位去。正因为有了这个特性JDK 8resize()代码里才有那段看起来像“把链表拆成两条”的逻辑。我当时学习这块时画了好几遍二进制推演才彻底明白。这里强烈建议你也拿笔算一下别满足于“背结论”。因为这个细节在面试HashMap原理时是极其高频的考点更重要的是它体现了一个工程优化思想利用结构本身的特性减少重复计算。3.3 扩容触发的临界判断先扩容还是先插入在写put逻辑时源码里插入节点后的下一步是if (size threshold) resize();所以是“先插入后判断是否扩容”。这意味着每次put可能触发一次扩容但扩容操作在put之后发生而不是之前。这个顺序对理解HashMap的size变化很有帮助。比如你知道预期的元素数量是某个值提前设好初始容量就能避免在运行过程中反复扩容。这个经验我在做数据预热、构建大Map的时候屡试不爽——如果你没有设置初始容量HashMap在元素数接近容量的75%时就会扩容频繁扩容的代价虽然单个看起来不大但批量场景下叠加起来非常可观。我整理了一个简单的初始容量估算表供你参考预计元素数量默认负载因子0.75建议初始容量2的幂100100 / 0.75 ≈ 134256 或 12810001000 / 0.75 ≈ 13342048 或 10241000010000 / 0.75 ≈ 1333416384 或 8192100000100000 / 0.75 ≈ 133334131072 或 262144注意这个表不是让你精确保数而是提供一个量级概念。实际上Java提供了带初始容量的构造方法new HashMap(initialCapacity)你传入的值内部会计算成最接近的2的幂。4. 容易忽视的API细节从key的选择说起前面讲的是底层原理现在我们回到日常使用的API层面把几个我见过最多人踩坑的点串一遍。说句实话讲原理的人很多但把日常API用对的人真的不多。4.1 自定义对象作为keyequals和hashCode的契约有一种典型的bug我几乎每隔一段时间就能在代码里遇到用自定义对象当HashMap的key但对象没有重写equals()和hashCode()导致两个字段值完全相同的对象被当成不同的key存进去了却取不出来。为什么因为HashMap判断key相等的标准是先看哈希值是否一致再看equals()是否为true。如果没重写这两个方法那么equals()比较的是对象引用两个new出来的对象明明内容一样在HashMap眼里却是完全不同的key。这是Java里不容忽视的契约问题。我在某个项目里做过一个缓存原本用String作为key后来重构时换成了一个包含多个字段的自定义对象当key。当时想当然地以为只要字段相同就算同一个key结果缓存命中率直接掉到低谷排查了半天才发现是equals和hashCode没有重写。后来我总结了一个习惯只要自定义类要放进集合、特别是HashMap/HashSet第一步先检查它的equals和hashCode是否配对实现。顺带一提如果对象的hashCode()返回值每次都不一样那这个对象作为key简直是灾难——同一个key可能存进去之后再也找不到。所以对于不可变对象作为key的情况我强烈建议让key的字段尽量不可变这是最容易规避麻烦的做法。4.2 遍历时删除元素ConcurrentModificationException是怎么来的“在遍历HashMap的时候删元素”也是高频踩坑点。你可能会遇到ConcurrentModificationException然后一脸蒙圈我没开多线程啊怎么会并发修改这个异常并不是只有多线程才会触发它在单线程下也会出现。原因是HashMap里有一个modCount字段记录结构被修改的次数。迭代器创建时会保存一份expectedModCount每次迭代时检查两者是否一致。如果你在迭代过程中调用了map.remove(key)modCount变了迭代器立刻抛出异常。正确的删除方式是使用迭代器自己的remove()方法或者在JDK 8之后用removeIf// 错误的写法 for (String key : map.keySet()) { if (condition(key)) { map.remove(key); // 抛 ConcurrentModificationException } } // 正确的写法 map.keySet().removeIf(key - condition(key));这个细节看起来小但稍不注意就在清理过期缓存、筛选数据等场景里翻车。我觉得它的根源还是在于对“迭代器是快速失败的”这个设计思想理解不够。4.3 computeIfAbsent这类“新API”的适用场景JDK 8给Map加了很多好用的方法比如computeIfAbsent、merge、getOrDefault。其中computeIfAbsent是我用得最多的。它解决的问题非常常见如果Map里没有这个key就通过一个表达式计算出新的value并放进去如果有就什么都不做。以前老版本的写法要三步判断是否包含key、创建value、put进去。现在一行搞定MapString, ListInteger map new HashMap(); // 等价于如果key不存在创建一个空List放进去然后向这个List添加元素 map.computeIfAbsent(students, k - new ArrayList()).add(18);不过这里有一个坑computeIfAbsent的回调函数里不能再对同一个Map做结构变更操作否则可能引起递归或并发问题。我在代码评审里见过有人computeIfAbsent的回调里直接操作同一个Map的其他key这种写法语义混乱很容易出bug。我会更倾向把它当成一个原子性的“检查并写入”操作来用。4.4 map.getOrDefault与null值的区分getOrDefault(key, defaultValue)是很多人用来避免空指针的好帮手但如果Map里真实存的value就是null这个方法会返回defaultValue从而掩盖“这个key存在但值为空”的事实。有一个真实的例子某个配置系统允许把key配置成空值用来表示“有这样一个配置位但当前值为空”。结果取配置时用了getOrDefault默认值被无脑返回导致逻辑判断出了问题。这是我第一次意识到API的便利性背后往往藏着语义陷阱用之前一定得想清楚“key不存在”和“key存在但值为null”是否需要区分。如果你确实需要区分这两种情况可以这样if (map.containsKey(key)) { // key存在哪怕是null也走这里 } else { // key不存在 }5. 实战排查一次HashMap性能退化问题的完整复盘理论讲了不少我们来看一个具体的排查过程。这个例子来自我在一个模拟项目X里的真实经历里面涉及的知识点恰好都是前面章节讲过的。5.1 现象接口响应越来越慢当时我负责一个数据处理模块功能是接收一批外部数据按类型分组后做聚合统计。用的数据结构是一个HashMapString, ArrayListDataItem。在数据量小的时候一切正常但随着数据量增长到一定规模整个模块的吞吐量明显下降最直观的表现是某个接口的平均响应时间从几十毫秒涨到了几秒。一开始我以为是数据库慢查询查了一圈发现数据库没有瓶颈。后来我怀疑是不是GC问题把JVM参数打印出来观察也没什么异常。最后我把目光落到了那个HashMap上。5.2 定位key的哈希分布有问题我做了个简单的统计把日志里出现的所有分组key拉出来计算它们的哈希值再模拟放到一个长度为16的数组里看每个桶里有多少个元素。结果让我吃了一惊有将近40%的数据集中在一个桶里。原因很快找到了这个数据分组用的key是一个业务字符串而这个字符串的前缀高度重复比如OSS_001、OSS_002这种格式。虽然整个字符串不一样但它们的hashCode()如果因为前缀相似而存在大量碰撞就会导致很多元素落在同一个桶里。当时我在日志里打了一个针对性的采样模拟分组key落在各个桶的分布情况然后用柱状图看得很清楚——大部分桶空空如也一个桶挤了几百条剩下的零星分散。这种情况下HashMap的查询效率已经从“直接下标定位”退化成了“遍历几百个节点的链表”不慢才怪。5.3 修复换key结构而不是盲目换集合类我的修复方案不是把HashMap换成别的集合类而是更改分组key的构造方式。具体做法是不再把拼接好的字符串直接当key而是用一个专门设计的不可变类内部把几个字段已经拆分好的分段进行组合哈希计算。这样每个字段的hashCode分别参与运算碰撞概率大大下降。改完之后我重新跑了一次相同的分布测试桶的填充明显均匀多了接口响应时间也回到了几十毫秒级别。这个经历给我的启发是HashMap本身没有问题问题往往出在key的哈希质量上。如果你的业务key天然具有高重复前缀可以考虑用组合哈希或者对key做一次散列优化。我把这次排查的关键点整理成了一个简单的问题排查清单供你参考症状可能原因定位方法大批量写入后查询变慢未设置初始容量扩容频繁打印扩容日志观察resize次数固定key集下get变慢key哈希分布不均匀链表过长模拟计算桶内元素数量偶发性CPU飙高并发下扩容形成环形链表JDK 7线程转储查看堆栈偶发ConcurrentModificationException遍历时外部修改了Map代码审查确认迭代期间是否有结构性修改6. 从HashMap看集合框架的学习路线给正在入门的人一点建议这是day06的最后一个部分。我不打算总结什么大道理只想从一个一路踩坑过来的人的角度分享几条对学集合框架真正有帮助的经验。第一条经验不要跳过源码。我知道很多人对读源码有恐惧认为那是大牛才干的事。实际上HashMap源码里最核心的几个方法就几百行配合断点调试一个下午就能过一遍。我学得最扎实的一天就是边在IDE里下断点边往HashMap里put数据的那个下午一步步看它是怎么计算出下标、怎么挂链表、怎么扩容的。这个过程比任何博客都直观。第二条经验把“为什么”挂在嘴边。比如“为什么默认容量是16”——因为2的幂有利于位运算“为什么链表长度到8才树化”——因为8对应极低的冲突概率“为什么负载因子是0.75”——因为空间和时间的中庸。这些问题想通了哪怕隔了很长时间再遇到你也一定能推导出答案而不是靠背。第三条经验结合并发场景来理解。单线程下HashMap的性能其实并不复杂真正的转折点在并发。等你看完了HashMap再去看ConcurrentHashMap你会发现它的锁粒度设计、CAS思想、扩容时的并发迁移逻辑几乎就是把HashMap的原理做了一次分布式升级。这是一个很好的学习阶梯我当时就是顺着这个路线把集合框架串起来的。第四条经验在实践中建立“容量预估”意识。如果你正在写一个会大量put数据的代码花几秒钟想想Map会有多大、要不要指定初始容量。这不仅是性能问题也是代码习惯问题。我见过很多线上问题最后查到最后都跟没有预估容量、导致频繁扩容有关。我一直觉得一份合格的学习笔记不应该只是知识点的堆砌更应该是思考路径的记录。今天这篇day06从HashMap的底层原理一路写到API细节和实战排查我希望你学到的不只是“HashMap是什么”而是“当它出现问题时你该从哪些角度去定位”。下一站我打算写一写线程池那是另一个日常开发中又常用又容易踩坑的主题到时候我们接着聊。