很多刚开始刷牛客的同学都会卡在“集合类”和“Map”这两节说实话这不怪大家。前面学的变量、循环、数组都是“单打独斗”到了集合和Map这儿突然冒出来一堆接口、实现类、方法名光是ArrayList和LinkedList怎么选就够纠结半天。这篇文章我就以带刷第42、43题为例把集合类和Map的考点、底层逻辑、常用方法一次讲透让零基础的同学也能直接上手写题。如果你是那种“数组还没玩明白就被扔到HashMap源码里”的初学者或者你正在刷牛客的Java入门题看到“集合类”“Map”这两个标题就头大那这篇文章就是给你准备的。我会用最直白的话拆解底层原理再带着你一行一行把题目代码写出来。文章里所有的代码都是我按实际刷题场景写的调试过、能跑你直接跟着敲就行。1. 为什么集合类和Map是刷题路上的分水岭数组能存一组数但数组的长度一旦确定就不能变了。日常写代码的时候你根本不知道用户会输入多少条数据这时候就必须用集合。集合类的出现本质上就是解决“数量不确定”和“操作复杂”这两个痛点。而Map解决的是另一个问题——“按名字找东西”。数组按下标找Map按key找这两种查找模型几乎是所有后续编程的基石。牛客把集合类和Map放在第42、43题位置非常讲究。前面的题让你用数组、循环、字符串把语法基础打牢到这里就开始考验你“用什么容器装数据”的抽象能力。这两题过了你才能无障碍地去看后面各种算法题因为算法题里几乎无处不在地用集合和Map做辅助。所以这两题刷明白意义不只是过了两道题而是你从“写代码”跨越到“设计代码”的起点。另外这两题也特别适合用来熟悉IDE的自动补全和API查找。我自己带学生的时候发现很多人写集合类代码方法名全靠背背不住就卡住。实际上集合类的方法名非常规律比如“添加”是add“删除”是remove“判断有没有”是contains“拿长度”是size你只要记住这一套规律再用IDE补全一提示基本就能顺下来。刷这两题的价值就是把这一套规律刻进肌肉记忆。提示牛客这类平台刷题时环境不带IDE自动补全有的带有的不带所以方法名最好在本地IDE里练熟再去平台提交。2. 动手写题之前先把集合框架的地图铺开2.1 List家族ArrayList和LinkedList别选错List是一个接口它的语义是“有序、可重复”的序列。所谓有序就是元素按插入顺序排列你放进a、b、c取出来就是a、b、c。可重复就是说同一个元素可以出现两次比如存两个“hello”没问题。List最常见的两个实现是ArrayList和LinkedList。ArrayList底层是数组查询快、改也快但是中间插入和删除慢因为要搬移后面的元素。LinkedList底层是双向链表两头操作特别快但中间查找慢。刷入门题的时候你只需要记住一个默认选择拿不准就用ArrayList因为大部分场景下数组搬移的开销可以忽略而链表每次get某个下标都要从头遍历写起来还容易迷糊。import java.util.ArrayList; import java.util.List; public class ListDemo { public static void main(String[] args) { ListString list new ArrayList(); list.add(Java); // 尾部添加 list.add(集合); list.add(Map); System.out.println(list.size()); // 3 System.out.println(list.get(0)); // Java数组按下标拿快 list.remove(1); // 删除下标1的“集合” System.out.println(list.contains(Map)); // true遍历找 } }这段代码里的size()、get()、remove()、contains()是你刷题时最常用的方法。注意list.remove(1)和list.remove(Java)不一样一个是按下标删一个是按元素删。初学者最容易在这里踩坑后面我会专门说。2.2 Set家族去重这件事底层是哈希Set的语义只有一句话不允许重复元素。为什么不允许重复因为它底层就是Map你没看错HashSet本质就是一个HashMap的壳元素被放进Set时是被当作Map的key存进去的。Map的key天然不能重复所以Set也就不能重复了。判断重复的标准是hashCode和equals先算hashCode定位到桶如果桶里有元素再用equals逐个比较。你如果自己定义了一个类放进HashSet却不重写hashCode和equals那两个“内容一样”的对象也会被当成不同元素。这是后面SE阶段的重难点刷牛客题阶段通常用不到自定义对象但原理你得知道不然看到“HashSet为何去重失败”的讨论会一头雾水。Set有三个常用实现HashSet无序去重最快LinkedHashSet按插入顺序去重TreeSet按自然顺序或比较器排序去重刷题场景里如果你要“去重排序”一个TreeSet直接搞定如果你只想去重不在意顺序HashSet就够了。2.3 Map的核心逻辑key-value的查找表Map不是Collection体系的一员它有自己独立的接口体系。Collection存单个元素Map存的是“键值对”。你可以把Map想成一本字典key是词条value是释义。查的时候你给一个key它直接告诉你value是多少。这个查找过程如果底层是HashMap那平均就是O(1)级别的非常快。HashMap的底层是数组链表红黑树。put一个键值对时先算key的hashCode再经过扰动函数散列到数组下标该位置为空就直接放不为空就挂在链表后面链表太长超过8且数组长度够超过64就转成红黑树。get的时候同样算hash找到桶然后在链表或红黑树里用equals找key。刷基础题阶段你不需要把红黑树背下来但你必须理解一个核心点Map是拿key来找value。所以如果你的需求是“统计每个字符出现了几次”字符是key、次数是value这个模型瞬间就清晰了。如果你要“记录学号和姓名”学号是key、姓名是value也是一样的道理。Map常用的实现有HashMap、LinkedHashMap、TreeMap、Hashtable。刷题最常用的是HashMap默认无序、查得快需要按key排序时用TreeMap需要按插入顺序遍历时用LinkedHashMap。Hashtable是老古董线程安全但是慢而且不允许null键null值不用管它。3. 第42题手把手拆解集合类操作与去重排序3.1 题面考点分析我带刷的时候拿到的题目版本大概是这样的从键盘输入若干个整数以某个结束符结束要求用集合类完成“去重 升序输出”。这道题的核心考点有三个集合类的选择、输入处理、集合遍历输出。很多初学者一上来就数组硬刚先数有几个数再建数组再去重再排序……可以是可以但代码量非常大而且容易出错。这道题就是逼你转换思维容器不是只能选数组Set本身就能去重TreeSet顺便还能排序你只需要把元素往里面一丢所有脏活累活它都替你干了。这就是刷题的意义——见识到工具本身的力量。3.2 我写的参考代码import java.util.Scanner; import java.util.TreeSet; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); TreeSetInteger set new TreeSet(); while (sc.hasNextInt()) { int num sc.nextInt(); set.add(num); } for (Integer val : set) { System.out.print(val ); } sc.close(); } }你没看错核心代码就这么几行。树结构帮你排序Set语义帮你去重遍历输出就完事了。读数据用的是hasNextInt()也就是“只要还有整数就一直读”这不依赖你事先知道有多少个数也不依赖结束符自动化判题程序会自动帮你模拟输入结束。3.3 关键方法逐行详解先说TreeSet的add()方法。前面说了TreeSet底层是TreeMap而TreeMap底层是一棵红黑树。每次add时元素会被插入到树中合适的位置树的中序遍历本身就是有序的。所以add完所有元素后你直接用foreach遍历拿到的就是升序序列。TreeSet内部会自动调用元素的compareTo方法比较大小Integer已经实现了这个接口所以不用你手动写比较器。hasNextInt()是Scanner里一个非常实用的方法。它的工作方式是先阻塞等待输入有数据时返回true没数据时返回false。在牛客这种自动判题环境里输入管道关闭后hasNextInt()会自动返回false循环自动退出不需要你写什么“输入0结束”之类的逻辑。这个细节很多新手不知道以为循环会卡住实际不会。foreach循环本质上是编译器帮你调用了迭代器。TreeSet的迭代器按照红黑树的中序遍历顺序返回元素所以输出天然有序。这里要注意一个细节foreach里你不能remove元素否则会抛ConcurrentModificationException。如果你要在遍历时删除元素得用迭代器自己的remove方法。不过这种去重排序场景用不到删除知道有这么回事就行。3.4 新手最容易写错的两个地方第一个坑是类型写错。有人写TreeSet 这是语法错误。Java泛型不支持基本类型必须用包装类Integer。int和Integer之间会自动装箱拆箱add(num)里num是int自动变成Integer对象取出来的时候foreach里的val是Integer还能直接参与运算。这个过程看起来“透明”但你要知道背后发生了装箱拆箱不然遇到null时你根本不知道为什么会空指针。第二个坑是错用HashSet。HashSet也能去重但它是无序的如果你直接用HashSet存完就输出顺序是乱的。加上排序还得再Collections.sort(new ArrayList(set))白折腾一圈。所以遇到“去重排序”这种题脑子里的第一反应应该是TreeSet而不是HashSet。这个直觉很重要刷题多了你会发现很多题目考的就是你对“哪个容器最适合当前场景”的判断力。注意TreeSet存储自定义对象时如果没实现Comparable接口add方法直接抛ClassCastException。所以以后你用TreeSet装自己的类时记得要么实现Comparable要么在new TreeSet时传一个比较器Comparator。4. 第43题手把手拆解Map的统计与遍历4.1 为什么一看到“统计次数”就应该是Map如果题目说“统计一串字符中每个字符出现的次数”80%的正确答案都要用到Map。原因很简单统计次数的本质是建立“字符-次数”的映射关系。你来一个字符我就得去查一下“这个字符之前出现过没”出现过就把次数加一没出现过就放进Map并初始化成1。这不正是Map的key查value的应用场景吗有人可能会想用两个数组一个存字符一个存次数也能做啊。能是可以但数组的index是整数字符不能直接当下标你得先想办法把每个字符映射成一个唯一的整数还得处理范围问题。Map直接帮你把key定为字符类型value定为Integer比两个数组的做法简洁得多也更不容易写出边界bug。这就是为什么我总说Map不是高级技巧它是你脑子里该有的第一反应。4.2 完整参考代码字符计数import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String line sc.nextLine(); MapCharacter, Integer map new HashMap(); for (int i 0; i line.length(); i) { char c line.charAt(i); if (c ) { continue; // 跳过空格题目一般只统计可见字符 } map.put(c, map.getOrDefault(c, 0) 1); } for (Map.EntryCharacter, Integer entry : map.entrySet()) { System.out.println(entry.getKey() entry.getValue()); } } }核心就是map.put(c, map.getOrDefault(c, 0) 1)这一行。它的逻辑如果c已经在Map里getOrDefault返回当前次数加一后覆盖回去如果c不在Map里getOrDefault返回默认值0加一变成1put进去。一句话完成“判断存在与否 更新计数”这就是Map处理统计问题最舒服的姿势。4.3 getOrDefault、put、entrySet这些方法都在干嘛put()是所有Map实现都必须有的核心方法。调用put(key, value)时HashMap先算key的hashCode定位到数组下标然后执行“插入或覆盖”的操作如果下标处没有元素直接放入如果有元素且key相等equals判断就用新value覆盖旧value并返回旧value如果有元素但key不等说明哈希碰撞了就挂到链表后面或插入红黑树。getOrDefault(key, defaultVal)是一个看起来简单但极其实用的方法。它的语义是如果Map里有这个key返回对应的value没有返回defaultVal。这个方法在刷题里简直是无价之宝因为统计场景里“没有出现过0次”这件事太常见了没有它你就得先containsKey判断再get再put要写三行代码。有它一行搞定。entrySet()返回的是Map.Entry对象的Set视图。每个Map.Entry代表一个键值对有getKey()和getValue()两个方法。用foreach遍历entrySet是遍历Map最常用的方式因为它同时拿到key和value不需要再多查一次。如果你只需要key可以遍历keySet()只遍历value就用values()。这三个方法组合起来基本覆盖了Map遍历的所有场景。4.4 遍历Map的几种姿势对比我直接给你一个表格对比你自己感受一下差异遍历方式写法适合场景注意事项entrySet()for (Map.EntryK,V e : map.entrySet())同时需要key和value最常用性能也好keySet() get()for (K k : map.keySet())只需要key或者要按key取valuevalue在循环里单独查一次多一次hashvalues()for (V v : map.values())只需要value拿不到keyforEach(Java 8)map.forEach((k, v) - {...})函数式风格需要lambda基础我的建议是前三种你必须手写熟练因为有些面试笔试环境不让你用太新的语法而且手写一遍能强化你对Map结构的记忆。forEach留到你学完lambda再用初期不要强行秀操作。另外如果你遍历TreeMap这三种方式返回的顺序都会按key的自然顺序排好版这点和HashMap不一样判断“要不要输出顺序”时选对实现类就行。5. 刷这两题最容易踩的坑我帮你提前排掉5.1 泛型基础类型写错的崩溃瞬间我见过太多次这个报错Type argument cannot be of primitive type。就是你写了ArrayList 或者HashMapchar, Integer。Java泛型必须是引用类型int要写成Integerchar要写成Character。初学者经常抱怨“为什么这么设计”很简单泛型要支持Object的方法基本类型不是Object没法统一处理。后面你会接触到基本类型专用集合比如IntList但现在你只需要记住集合和Map一律用包装类。在你写完代码后最好主动检查一遍所有尖括号里的类型是不是包装类这个习惯能省很多编译错误。5.2 remove方法的重载歧义List的remove有两个重载remove(int index)和remove(Object o)。当你写list.remove(2)时编译器会优先匹配remove(int)所以它删的是下标为2的元素而不是值为2的元素。如果你有一个List 想删掉值为2的元素你必须写list.remove(Integer.valueOf(2))。这是Java API设计里一个著名的坑牛客评论区几乎每过几期就有人问。刷题的时候如果发现“删错了”先往这个方向想。5.3 遍历时删除元素导致并发修改异常刚才提过foreach遍历集合时删除元素会抛ConcurrentModificationException。原理是集合内部有个modCount修改次数计数器迭代器在创建时会记住这个值每次next()之前都会检查当前modCount和预期值是否一致不一致就抛异常。你可能会问那我真要在遍历时删除怎么办答案是使用迭代器Iterator自己IteratorInteger it list.iterator(); while (it.hasNext()) { Integer val it.next(); if (val 3) { it.remove(); // 安全删除它会把modCount同步一致 } }这个方法在后面的算法题里会频繁碰到比如“删除链表中所有等于某个值的节点”。提前把这套规则理解透会少掉很多头发。5.4 HashMap和Hashtable别搞混面试八股文里有一道经典题HashMap和Hashtable的区别。刷题阶段你只需要记住HashMap允许key和value为nullHashtable不允许HashMap是线程不安全的但性能好单线程刷题没问题Hashtable是线程安全的但方法都加了锁性能差现在基本被淘汰了。选择题如果看到“线程安全且效率高”这种选项那是在钓鱼因为效率和线程安全往往是矛盾的。现在的官方推荐是如果需要线程安全用ConcurrentHashMap而不是Hashtable。5.5 输出格式要求牛客的判题系统对输出格式有严格检查尤其是“多余空格”。比如要求输出“1 2 3”你输出“1 2 3 ”末尾多一个空格有些判题系统能过有些判题系统就判错。我建议你养成一个好习惯用StringBuilder或一个标志位来控制空格不要无脑在循环里拼“元素空格”。这是我刷题踩过很多次后的经验看起来是小问题实际浪费的时间非常多。StringBuilder sb new StringBuilder(); for (Integer val : set) { if (sb.length() 0) { sb.append( ); } sb.append(val); } System.out.println(sb);这种写法不会有多余空格也方便你在拼完字符串后进一步处理比直接在循环里打印要灵活得多。6. 刷完这两题以后我建议你这样继续练6.1 动手把每个实现类都跑一遍你刚学的TreeSet、HashMap最好别只在牛客上用。我建议你回到本地IDE新建一个测试类把ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap这六个类全部new一遍。每个类都执行一遍添加、删除、查询、遍历用debug模式看一眼里面的结构。尤其是HashMap你把断点打在put方法上能看到它怎么计算hash、怎么找桶、怎么挂链表这个印象比读十遍文章都深刻。6.2 做两道综合题巩固一下牛客上有不少综合题比如“统计一个英文句子中不同单词的数量”或“寻找数组中出现次数超过一半的数字”。前者用Set和Map结合后者只用Map就能解。这些题目会逼着你把集合类和Map串起来用比孤立刷题效果更好。做的时候先停下来想一想“这道题我应该用List还是Set还是Map”想对容器再动手这是最重要的解题步骤。6.3 看一遍集合类的继承结构图不需要背但你要能画出这样一条链路Iterable - Collection - List/Set/Queue然后List下面有ArrayList/LinkedList/VectorSet下面有HashSet/LinkedHashSet/TreeSetMap是独立接口下面有HashMap/LinkedHashMap/TreeMap。这张图能帮你建立“接口-实现类”的坐标系以后看到任何一个类你都能立刻说出它属于哪个阵营、有什么特点。说白了集合框架的重点不是背方法而是建立坐标系方法的使用反而水到渠成。6.4 形成一个自己的“容器选择清单”根据我自己的经验等你做过的题足够多你会自然形成一套“选容器”的条件反射。我在这分享我的版本给你参考需要存一串元素且允许重复ArrayList需要频繁在头部或中间增删LinkedList虽然笔试很少考这个不允许重复且不管顺序HashSet不允许重复且要排序TreeSet不允许重复但要保持插入顺序LinkedHashSet需要键值映射、不在意顺序HashMap需要键值映射、按键排序TreeMap需要键值映射、按插入顺序遍历LinkedHashMap这套清单不是标准答案但它能帮你在看到题目需求的第一时间下意识地选到合适的容器。有了这个惯性你后面刷各种算法题都会轻松很多。最后再分享一个带刷过程中我反复跟学生强调的体会集合类和Map这部分内容初学的时候感觉像在背一堆API但其实它们背后全都是很朴素的数据结构思想。数组、链表、哈希、树这些听起来“高大上”的词落到日常写代码里就是“我该选哪个容器”。你只要亲自把这些容器一个个new出来、调试、用debug看内部变化很快就能建立属于自己的手感。刷题这件事不怕慢就怕不亲自动手拆。希望这篇带刷能帮你跨过这个坎继续往后刷的时候你会发现自己写代码的思路清晰了不止一个档次。