前辈们常说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遍历有什么差别）；
• 方言式地理解"泛型"是什么，为什么写成Map<String, 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与HashSet

2.1 从接口到实现：先搞清楚谁是谁

Java里"集合"这个词，在笔试和实际开发中通常指java.util包下的两大体系：Collection（单列集合）和Map（双列集合）。Collection下面又分List和Set，List的特点是有序、可重复，Set的特点是无序、不可重复（这里的无序指不保证存入顺序，不是随机）。

刷题时最常用的三个实现类是：

很多人会问："我到底该背什么？"我的建议是先把这三个类的直觉建立起来。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 array），put(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、遍历全家桶

在刷题层面，必须掌握的方法有这么几个：

1. V put(K key, V value)：存入键值对。如果key已存在，覆盖旧值并返回旧值；如果是新key，返回null。这点在统计类题目里很有用。
2. V get(Object key)：根据key取值，不存在返回null。
3. V getOrDefault(Object key, V defaultValue)：不存在时返回默认值，统计次数时能少写一个if。
4. boolean containsKey(Object key)：判断key是否存在。
5. V remove(Object key)：按key删除，返回被删除的值。
6. int size()：键值对个数。
7. Set<K> keySet()：返回所有key的集合。
8. Set<Map.Entry<K, V>> entrySet()：返回所有键值对对象的集合，用于高效遍历。
9. Collection<V> values()：返回所有value。

写遍历时，我强烈建议在刷题阶段就养成用entrySet()的习惯。原因很简单：keySet()遍历时，每取一次value都要通过map.get(key)再查一遍哈希表，相当于额外做一次查找；而entrySet()直接拿到Entry对象，key和value都在里面，少了一次get的开销。数据量小看不出差别，一旦数据量大，这就是超时和不超时的分水岭。

代码模板直接背下来：

Map<String, Integer> map = new HashMap<>(); map.put("apple", 3); map.put("banana", 5); // 遍历方式一：entrySet，推荐 for (Map.Entry<String, 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²)，数据稍大直接跑不动。正确思路应当是一步步把容器选出来：

• 需要建立"单词 -> 次数"的映射关系，这显然是双列结构，直接选HashMap<String, Integer>。
• 每读一个单词，判断是否已存在。代码可写为：

Map<String, Integer> map = new HashMap<>(); for (String word : wordList) { // 用 getOrDefault 代替"先contains再get"的写法 map.put(word, map.getOrDefault(word, 0) + 1); }

• 统计完成后要按次数排序。Map本身不擅长排序，所以把entrySet转成List再排：

List<Map.Entry<String, 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 选型决策表：按题目特征直接查

下面这张表我整理了很久，几乎覆盖刷题阶段所有集合类的选择场景。你可以照着用：

这张表不是让你背的，是让你"查"的。刷题多了之后，你会形成条件反射：看到"去重"想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的成因与规避

这是新手最容易踩但踩完又摸不着头脑的异常之一。看这段代码：

List<String> 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线程安全（方法加了synchronized）；
• HashMap允许null键和null值，Hashtable不允许；
• HashMap默认初始容量16，Hashtable是11。

现代开发里基本没人用Hashtable了，并发场景请用ConcurrentHashMap。刷题阶段记住一句话：所有默认选HashMap，除非题目明确出现并发要求。

6. 两道题的参考实现思路与OJ提交细节

6.1 题42的通用解法骨架

我不会把题目原copy贴在这里（因为这类题的输入格式在不同版本牛客上略有差异），而是给你一套能跑通绝大多数"集合类操作题"的骨架。核心步骤就四个：

1. 创建Scanner读取输入；
2. 循环读取数据，按题意去重/存储；
3. 用集合方法处理；
4. 按OJ要求格式逐行输出。

一个典型示例（读取若干字符串，去除重复后按字典序输出）：

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Set<String> 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); Map<String, Integer> countMap = new HashMap<>(); while (sc.hasNext()) { String word = sc.next(); countMap.put(word, countMap.getOrDefault(word, 0) + 1); } // 按需求输出 key-value for (Map.Entry<String, 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 数组与集合互转：公式化记忆节省的时间

刷集合题时，数组和集合的互转出现频率很高。我直接给你记牢两行公式。

数组转List：

String[] arr = {"a", "b"}; List<String> 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清单，包括：

List<String> list = new ArrayList<>(); list.add("a"); list.remove("a"); list.get(0); list.size(); Map<String, Integer> map = new HashMap<>(); map.put("a", 1); map.containsKey("a"); map.getOrDefault("a", 0); Set<String> set = new HashSet<>(); set.add("a"); set.contains("a");

连续默写几天之后，手感和记单词一样形成了肌肉记忆，上OJ就不会再被这些小问题卡住。知识密度并不高，难的是把每一个方法变成"不假思索就能写对"的默认技能。这个过程没有任何捷径，但也不需要太多时间——每天十分钟，坚持一周就足够让你在刷题时摆脱低级语法错误。能走到这一步，你和这些题目之间就只剩"思路"这一件事了。