前辈们常说Java的集合和Map是面试必考题这话一点都不夸张。我见过太多零基础的朋友视频课刷了好几套讲ArrayList、HashMap的时候头头是道可一到牛客上做这种带集合类、Map的题目手就僵住了——要么不知道用哪个容器要么方法名拼错要么输出格式不对被OJ判错。牛客第42、43题这种手把手带刷的关卡就是专门治这个毛病的。本文我按自己的刷题习惯把集合类、Map的核心方法从底层原理到实战调用完整捋一遍全程零基础友好每一步都有对应代码和踩坑提醒希望你读完能直接打开编辑器跑起来。刷题这事有个特点看得懂不代表写得对写得对不代表一次能过。真正拉开差距的是知不知道容器内部发生了什么以及遇到具体场景能不能秒选容器。这篇文章不会只讲API列表我会从这道题常见的考察面出发把List、Set、Map三兄弟的关系、HashMap的存储逻辑、笔试中常见的坑全串起来你把它当一份带注释的刷题笔记来用就行。1. 42、43题到底考什么先把刷题目标拆清楚1.1 这类题目在牛客的常见形态与考察意图先说结论牛客入门序列里的42、43题出题形式通常围绕键盘输入一组数据用集合收纳再按要求遍历输出。比如给你若干行字符串或数字让你去重、统计次数、按顺序取出。难度本身不高但它刻意把考点压在了两件事上一是集合类的实例化和基本操作二是Map的键值对处理。这两点恰好是零基础学习者最容易眼高手低的地方。我在给新人讲这题时习惯先把考察意图点出来会不会正确导包、声明一个ArrayList或HashMap知不知道常用方法的返回值比如put返回什么、add返回什么能不能在遍历Map时选对方式keySet遍历和entrySet遍历有什么差别方言式地理解泛型是什么为什么写成MapString, Integer而不是裸Map。这四点在实际笔试里全会以能不能写出无语法错误代码的形式呈现。不要小看语法层的东西很多人在本地IDE里靠自动补全写代码一到OJ的在线编辑器里就原形毕露。1.2 为什么零基础最容易在看起来简单的题上翻车这些题看起来就十几行代码但翻车率极高。我总结下来主要有三个原因第一集合类的继承关系没有建立。很多新手知道ArrayList能存东西但不知道它实现的是List接口更不清楚Collection是所有单列集合的根接口。于是当题目换了个马甲——比如要你用LinkedList实现栈式操作或者用Set去重——人就懵了。第二Map的遍历模板没背熟。这题只要涉及Map十个新人里至少有五个人会写for (String key : map)编译时才发现Map根本不能这样直接遍历。一个Iterator活生生用不好。说白了还是对Map是由Entry组成的这个底层认知缺课。第三输出格式不符合OJ要求。牛客判题特别严格多一个空格、少一个换行都判错。很多人集合操作全对最后挂在System.out.println的拼接上。所以说别急着把题刷完先把知识点底座的每一块砖对齐。接下来几个部分就是按这个思路帮你对齐的。2. 集合接口背后的三个常用实现ArrayList、LinkedList与HashSet2.1 从接口到实现先搞清楚谁是谁Java里集合这个词在笔试和实际开发中通常指java.util包下的两大体系Collection单列集合和Map双列集合。Collection下面又分List和SetList的特点是有序、可重复Set的特点是无序、不可重复这里的无序指不保证存入顺序不是随机。刷题时最常用的三个实现类是实现类父接口底层结构特点常见用途ArrayListList动态数组查询快、增删慢按索引读取、顺序存储LinkedListList双向链表增删快、查询慢频繁头尾操作HashSetSetHashMap的键位去重、判断存在统计不重复元素很多人会问我到底该背什么我的建议是先把这三个类的直觉建立起来。ArrayList就想象成一个会自动扩容的数组LinkedList就像一条链子HashSet则是只关心有没有不关心第几个的袋子。有了这个直觉你看到题目描述时选容器就快了。2.2 高频核心方法逐个拆解以刷这题时最常碰到的ArrayList为例必须滚瓜烂熟的方法至少有这些boolean add(E e)追加到末尾返回是否成功。注意它返回boolean允许重复元素。void add(int index, E element)指定位置插入后面元素整体后移。E remove(int index)按下标删返回被删元素。boolean remove(Object o)按对象删只删第一个匹配项。E get(int index)按下标取。int size()元素个数不是容量。boolean contains(Object o)是否包含某元素。int indexOf(Object o)返回第一次出现的下标没有则-1。void clear()清空。Object[] toArray()转成数组注意返回的是Object[]。这里特别提醒一个新手误区size()是小写很多人在快捷键补全的环境里敲习惯了不觉得一旦换成OJ的纯手写环境很容易写成Length之类的。数组是length属性字符串是length()方法集合是size()方法——这三者的差异是笔试常设陷阱务必焊死在脑子里。HashSet的方法相对少关键就是add()返回boolean这个特性当元素已存在时add返回false。很多聪明解法利用这一点做去重或判断效率比先contains再add高一点代码也更简洁。2.3 LinkedList的独特操作要额外记LinkedList除了List的常规方法还多出addFirst、addLast、removeFirst、removeLast、getFirst、getLast这些操作两端的方法。刷题时一旦遇到头插法尾插法栈操作之类的描述优先想到它。虽然也可以拿ArrayList实现但在频繁头插时性能差异是非常明显的——ArrayList每次头插都要把所有元素整体往后挪O(n)的代价在数据量大时会直接导致超时。我有个经验可以分享平时练习时试着把一个经典题目分别用ArrayList和LinkedList写一遍不看结果就感受方法调用的差异。这种体感训练比背十遍API都有效。3. HashMap是把钥匙put、get、遍历的底层逻辑3.1 从数组链表视角理解HashMap的存储这部分的标题既然叫Map含方法详解那HashMap一定是重点中的重点。牛客的43题但凡带上统计、分组、映射这些关键词九成要用到它。HashMap的底层在JDK 1.8之后是数组链表红黑树的结构。你可以这样理解HashMap有一个桶数组bucket arrayput(key, value)时先计算key的hashCode再经过扰动函数算出下标把键值对放进对应桶里。如果多个key算到了同一个桶就用链表把它们串起来当链表长度超过阈值默认为8且数组容量达到64时链表会转成红黑树以加速查找。get(key)的过程与之对称算出下标如果桶里只有一个节点就直接返回如果是链表或红黑树就用key的equals逐个比对。明白这个过程后很多看似玄乎的问题就通了为什么重写equals必须重写hashCode因为HashMap先找桶靠hashCode桶内比对靠equals。两个对象equals相同但hashCode不同会落进不同桶导致get不到。为什么String和Integer适合当key因为它们的hashCode和equals实现是稳定的不易出错。为什么自定义类当key有风险因为你可能没重写这两个方法。3.2 方法详解put、get、containsKey、remove、遍历全家桶在刷题层面必须掌握的方法有这么几个V put(K key, V value)存入键值对。如果key已存在覆盖旧值并返回旧值如果是新key返回null。这点在统计类题目里很有用。V get(Object key)根据key取值不存在返回null。V getOrDefault(Object key, V defaultValue)不存在时返回默认值统计次数时能少写一个if。boolean containsKey(Object key)判断key是否存在。V remove(Object key)按key删除返回被删除的值。int size()键值对个数。SetK keySet()返回所有key的集合。SetMap.EntryK, V entrySet()返回所有键值对对象的集合用于高效遍历。CollectionV values()返回所有value。写遍历时我强烈建议在刷题阶段就养成用entrySet()的习惯。原因很简单keySet()遍历时每取一次value都要通过map.get(key)再查一遍哈希表相当于额外做一次查找而entrySet()直接拿到Entry对象key和value都在里面少了一次get的开销。数据量小看不出差别一旦数据量大这就是超时和不超时的分水岭。代码模板直接背下来MapString, Integer map new HashMap(); map.put(apple, 3); map.put(banana, 5); // 遍历方式一entrySet推荐 for (Map.EntryString, Integer entry : map.entrySet()) { String key entry.getKey(); Integer value entry.getValue(); System.out.println(key value); } // 遍历方式二keySet简单但效率略低 for (String key : map.keySet()) { Integer value map.get(key); System.out.println(key value); } // 遍历方式三JDK 8 的 Lambda代码最简洁 map.forEach((key, value) - System.out.println(key value));3.3 put方法返回值的一个冷门但实用的点我把这一点单独拿出来说因为它和牛客这类入门的统计题直接相关。很多人不知道put返回的是被覆盖的旧值。当你写Integer oldValue map.put(key, 1);如果key之前不存在oldValue是null如果key之前已存在oldValue就是之前的次数。利用这个特性有些题能写出很巧妙的单行逻辑。不过对零基础来说我更推荐先用getOrDefault把逻辑写清楚等熟练了再考虑这种骚操作。另外提醒一句不要在生产代码里依赖Map的遍历顺序。HashMap不保证顺序LinkedHashMap按插入序TreeMap按键的自然序。刷题时如果题目要求按出现顺序或排序输出一定会有对应的容器选择别默认HashMap有序。4. 刷题时的容器选型List、Set、Map谁该上场4.1 一个统计单词次数题的完整推演这章我用一个非常典型的例题来演示容器选型全过程它几乎是牛客42、43的常见变体输入若干行英文单词统计每个单词出现的次数最后按出现次数降序输出次数相同的按单词字典序升序。零基础拿到这题第一反应可能是用两个数组一个存单词一个存次数这样也能做但极端情况下一万个不重复单词数组的查找和维护就是O(n²)数据稍大直接跑不动。正确思路应当是一步步把容器选出来需要建立单词 - 次数的映射关系这显然是双列结构直接选HashMapString, Integer。每读一个单词判断是否已存在。代码可写为MapString, Integer map new HashMap(); for (String word : wordList) { // 用 getOrDefault 代替先contains再get的写法 map.put(word, map.getOrDefault(word, 0) 1); }统计完成后要按次数排序。Map本身不擅长排序所以把entrySet转成List再排ListMap.EntryString, Integer list new ArrayList(map.entrySet()); list.sort((a, b) - { if (!a.getValue().equals(b.getValue())) { return b.getValue() - a.getValue(); // 次数降序 } return a.getKey().compareTo(b.getKey()); // 字典序升序 });最后遍历list输出。这个例子里用了三个容器各司其职HashMap负责高效统计ArrayList负责承载排序Map.Entry负责表达一组键值对。你把容器选型的逻辑理清了代码自然就长出来了而不是靠记一整道题的答案。4.2 选型决策表按题目特征直接查下面这张表我整理了很久几乎覆盖刷题阶段所有集合类的选择场景。你可以照着用题目特征推荐容器理由需要按下标取元素、顺序遍历ArrayList查询O(1)频繁在头部或尾部插入删除LinkedList两端操作O(1)去重且不关心顺序HashSet天然去重去重同时要维护去重后的插入顺序LinkedHashSet双向链表维护顺序去重并要求排序输出TreeSet红黑树自然有序一个key映射一个valueHashMap通用映射映射且要求按key排序TreeMapkey有序映射且要求按插入序输出LinkedHashMap插入序既要频繁查存在又要取最早插入的元素LinkedHashSet配合队列综合结构这张表不是让你背的是让你查的。刷题多了之后你会形成条件反射看到去重想Set看到映射想Map看到顺序想List或LinkedXxx。4.3 时间复杂度意识从O(n²)到O(n)选择容器的本质是在选数据结构选数据结构的本质是在选时间复杂度。零基础阶段就要建立这个意识否则刷题量上去了会非常痛苦。用一个最简单的场景说明题目要求判断一批数字中是否存在重复值。方式一双层for循环逐个比较时间O(n²)。方式二用HashSet挨个add由于HashSet的add是平均O(1)整体O(n)。方式三先排序再相邻比较O(n log n)。同样一道题三种思路差距在大数据量下就是天壤之别。牛客的判题系统对超时判得很严很多新手算法思路上没错但一跑就超时八成是容器没选对导致复杂度爆了。所以我特别建议每做完一道集合相关的题追问自己一句我的时间复杂度是多少哪怕答案不完全准确这个习惯也会逼你去思考容器背后的数据结构而不是停留在API调用层。5. 笔试与OJ环境下的高频坑equals、hashCode与并发修改5.1 自定义对象进Map一个我必须反复强调的坑刷题时自定义类当key的情况不多但一旦遇到往往是连环坑。我见过一个真实案例定义一个Student类想用HashMap统计不同学生的信息结果两个学号相同、姓名相同的学生被当成两个不同的key放进了Map统计直接错误。原因就是Student没有重写equals和hashCode。HashMap判断key是否相同先比hashCode再比equals。默认实现下两个new出来的对象即使在业务上相同hashCode也不一样于是永远落进不同桶get的时候也找不回来。如果你要在刷题中自定义key类记得遵循黄金法则equals方法和hashCode方法必须同时重写参与equals比较的字段必须参与hashCode计算重写时优先用Objects.hash(...)或IDE自动生成不要手写hash算法。当然技巧层面也有替代方案把对象的唯一标识字段比如学号拼成一个String作为Map的key比如String key student.getId() _ student.getName()。这样就不需要动自定义类适合刷题场景快速实现。5.2 indexOf和contains的代价为什么List.contains要慎用ArrayList.contains底层是遍历所有元素逐个equals时间复杂度O(n)。如果你在循环里反复调用list.contains(someValue)整体复杂度会变成O(n²)。这一点在数据量小的入门题里感知不到但我见过牛客上不少题数据规模到十万级时List.contains直接让程序超时。那怎么判断存不存在答案是换容器。如果只需要判断存在性用HashSet它的contains是平均O(1)如果需要同时保持顺序用LinkedHashSet。换句话说contains这个操作不是在任意容器里调用都一样的你选择容器时就要想好我会不会频繁contains。5.3 遍历时删除元素ConcurrentModificationException的成因与规避这是新手最容易踩但踩完又摸不着头脑的异常之一。看这段代码ListString list new ArrayList(Arrays.asList(a, b, c)); for (String s : list) { if (s.equals(b)) { list.remove(s); // 抛出ConcurrentModificationException } }原因在于for-each语法糖背后是Iterator迭代期间结构被修改Iterator发现modCount不一致直接抛异常。规避姿势有三种用Iterator显式遍历调用iterator.remove()用list.removeIf(条件)这是JDK 8引入的简洁方案先把要删的元素收集到一个新List遍历结束后统一removeAll。刷题时最省心的其实是第三种思路的变体把不符合条件的元素收集到新集合最后一步输出新集合根本不去动原集合。这既避开了并发修改异常又让代码逻辑变得非常清晰。5.4 为什么HashMap和Hashtable总被拿来对比牛客刷题未必直接考这个但它是面试的常客。简单说HashMap线程不安全Hashtable线程安全方法加了synchronizedHashMap允许null键和null值Hashtable不允许HashMap默认初始容量16Hashtable是11。现代开发里基本没人用Hashtable了并发场景请用ConcurrentHashMap。刷题阶段记住一句话所有默认选HashMap除非题目明确出现并发要求。6. 两道题的参考实现思路与OJ提交细节6.1 题42的通用解法骨架我不会把题目原copy贴在这里因为这类题的输入格式在不同版本牛客上略有差异而是给你一套能跑通绝大多数集合类操作题的骨架。核心步骤就四个创建Scanner读取输入循环读取数据按题意去重/存储用集合方法处理按OJ要求格式逐行输出。一个典型示例读取若干字符串去除重复后按字典序输出import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); SetString set new TreeSet(); while (sc.hasNext()) { set.add(sc.next()); } for (String s : set) { System.out.println(s); } sc.close(); } }这里用TreeSet一箭双雕即去重又排序。不要觉得这种写法太简单不算算法在OJ场景里能用标准库解决就绝不自己造轮子——这是效率准则不是偷懒。6.2 题43的通用解法骨架Map相关的题目骨架略微不同核心是统计或映射import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); MapString, Integer countMap new HashMap(); while (sc.hasNext()) { String word sc.next(); countMap.put(word, countMap.getOrDefault(word, 0) 1); } // 按需求输出 key-value for (Map.EntryString, Integer entry : countMap.entrySet()) { System.out.println(entry.getKey() entry.getValue()); } sc.close(); } }如果是次数统计后还要排顺序的题参考第4.1小节的list排序模板。注意sort里的比较器写法我曾经见过有人把return b.getValue() - a.getValue()误写成return b.getValue() a.getValue()排序结果全乱。这种低级错误非常急躁但确实会发生。写完排序比较器后自己拿3个数据手算一遍再提交能省不少罚时。6.3 牛客提交时最容易忽略的隐藏门槛在牛客做题代码逻辑之外还有几个隐形扣分点我一一说明类名必须是Main。你把类名写成Solution或者Test编译就挂这是最冤的错误。不要带上package语句。本地IDE通常会加包名或自动生成OJ里这属于编译错误。Scanner用完可以不关但关了更规范。注意如果用sc.next()读取换行符会被自动跳过不会干扰后续读取。输出时小心多余空格。尤其最后一个元素很多题目要求行尾不能有空格。稳妥做法是收集到列表后统一用String.join拼接或者控制循环下标在最后一个时不打印空格。变量命名虽然不影响判题但影响你调试的速度。我建议key、value用英文全称别用a、b、c不然报错了你都分不清哪一行。7. 平台提交之外几个能提升效率的刷题习惯7.1 本地IDE和OJ编辑器的差异适应很多人问我本地写得好好的复制到牛客就编译不过怎么回事多数原因是环境差异。本地IDE默认帮你导入了部分包或者自动补全了方法签名OJ编辑器没有这些智能辅助。所以你在本地练习时建议关闭自动补全强制手写import java.util.*;以及方法名这一步能提前适应OJ的裸环境。另外一个实用技巧在本地跑通样例后特意测试一下边界输入。比如空输入、只有一个元素、全部重复元素、大量数据。牛客的测试用例往往就藏着这些边界本地样例通过不代表这些边界也能过。7.2 数组与集合互转公式化记忆节省的时间刷集合题时数组和集合的互转出现频率很高。我直接给你记牢两行公式。数组转ListString[] arr {a, b}; ListString list new ArrayList(Arrays.asList(arr));注意Arrays.asList返回的是一个固定大小的List不能add和remove所以要用new ArrayList(...)再包装一次这才是我们平时说的可变List。List转数组String[] newArr list.toArray(new String[0]);这里new String[0]是惯用写法实际数组大小会被自动调整。刷题时别再纠结传0还是传size传0就对了。7.3 刻意练习键盘上敲不出来的细节最后我想分享一个个人体感零基础阶段最容易出问题的不是算法思路而是方法名的精确拼写。getOrDefault、entrySet、getKey、getValue、Collections.sort、Arrays.sort这些在IDE自动补全里都太容易了一旦脱离自动补全拼错率惊人。我自己的笨办法是每天抽出十分钟在记事本里默写一份常用集合类的API清单包括ListString list new ArrayList(); list.add(a); list.remove(a); list.get(0); list.size(); MapString, Integer map new HashMap(); map.put(a, 1); map.containsKey(a); map.getOrDefault(a, 0); SetString set new HashSet(); set.add(a); set.contains(a);连续默写几天之后手感和记单词一样形成了肌肉记忆上OJ就不会再被这些小问题卡住。知识密度并不高难的是把每一个方法变成不假思索就能写对的默认技能。这个过程没有任何捷径但也不需要太多时间——每天十分钟坚持一周就足够让你在刷题时摆脱低级语法错误。能走到这一步你和这些题目之间就只剩思路这一件事了。