Sherfiter's wiki for fun

第 10 章 · 集合类

数组定长、手写扩容、自己实现链表,这些苦役到本章全部退役:Java 集合框架把数据结构课的每个结构都做成了开箱即用的类,而且接口统一、类型安全。本章按「List 怎么选、Set 什么时候用、Map 为什么是第一神器」的顺序推进,中间插播两个必踩的坑(ConcurrentModificationException 和 hashCode 契约),这两个坑我都替你踩过。

10.1 框架全景:两大族

Collection(单个元素的集合)
├── List(有序、可重复):ArrayList / LinkedList
└── Set (不重复):HashSet / TreeSet
Map(键值对,键不重复)
├── HashMap / TreeMap

通用操作都定义在接口上(add/remove/contains/size),声明时写接口、创建时选实现(List<String> list = new ArrayList<>()),这是 8.2 节「面向接口编程」的第一块主阵地:以后想把 ArrayList 换成 LinkedList,只改 new 那半行。

10.2 List:两个实现的真实差异

ArrayList 底层是动态数组(数据结构课第 2 章的 SeqList 的官方版):随机访问 O(1),中间插删 O(n),扩容时整体搬家(第 1 章的摊还分析:均摊尾部追加仍是 O(1))。LinkedList 底层是双向链表:头尾增删 O(1),随机访问 O(n)(要顺着链走)。

面试标准答案是「频繁插删用 LinkedList」,但数据结构课第 12 章的实测给你另一个视角:LinkedList 的每个节点是散落的堆对象,缓存不友好,现实中绝大多数场景 ArrayList 全面胜出(包括很多「频繁插删」场景,因为 ArrayList 的连续内存+ System.arraycopy 太快)。我的实战建议:默认 ArrayList,LinkedList 只在「确定需要 O(1) 头插 + 当队列用」时考虑(而且 Java 有更合适的 ArrayDeque)。

List<String> list = new ArrayList<>();
list.add("a");                    // 尾加
list.get(0);                      // 下标访问
list.remove(0);                   // 按下标删(注意和按对象删的重载区分)
list.set(0, "b");                 // 替换

10.3 Map:第一神器

键值对存储,日常代码的出镜率最高:

Map<String, Integer> count = new HashMap<>();
for (String w : words)
    count.merge(w, 1, Integer::sum);      // 有则加一,无则置一,一行顶四行
System.out.println(count.get("the"));     // O(1) 查
count.getOrDefault("foo", 0);             // 不存在给默认值,防 null
for (var e : count.entrySet())            // 遍历键值对
    System.out.println(e.getKey() + "=" + e.getValue());

底层是哈希表(数据结构课第 7 章:桶 + 链,链长了转红黑树),O(1) 读写。HashMap 的两个契约都来自第 8 章:键的 equals 和 hashCode 必须配套重写(否则「存进去找不到」),所以 String 和 Integer 能直接当键(它们都正确实现了)。需要按键排序换 TreeMap(红黑树,数据结构课第 5 章),需要保持插入顺序换 LinkedHashMap。

那个让我痛苦过的坑,展示一遍:

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : list)
    if (x % 2 == 0) list.remove(x);       // 抛 ConcurrentModificationException!

增强 for 底层用迭代器,循环中直接改集合,迭代器的「修改计数器」对不上,当场抛异常(这是一种保护:否则行为不可预测)。正解是迭代器自己的 remove,或 list.removeIf(x -> x % 2 == 0)(一行,内部帮你安全处理)。

10.4 Set:去重与存在性

Set<String> seen = new HashSet<>();
if (seen.add(word)) { ... }               // add 返回 false = 已存在,妙用

HashSet 哈希实现无序 O(1);TreeSet 红黑树有序 O(log n),能 first()/last()/floor()。「两个数组找交集」这类题,Set 比双重循环优雅得多(把小数组进 Set,大数组 contains 一遍)。Map 的键集合(map.keySet())天然就是 Set,去重思想同源。

10.5 泛型:编译期的类型警察

List<String> list = new ArrayList<>();    // 菱形语法,JDK 7 起右边可省类型
list.add(42);                             // 编译错误!在编译期就拦住
String s = list.get(0);                   // 不用强转,JDK 5 之前必须 (String)

泛型让「容器里装什么」成为类型的一部分,JDK 5 之前集合里存 Object、取出靠强转、装错类型运行时才炸(ClassCastException),泛型把这些全部提前到编译期。自定义泛型 class Box<T> { T value; } 一学就会;底层实现是类型擦除(运行期泛型信息被抹掉,List<String> 和 List<Integer> 运行时是同一个类),这个细节解释了「不能 new T()」「不能泛型数组」等限制,面试常考。

常见错误

  • 边遍历边 remove。10.3 的 ConcurrentModificationException;用 removeIf 或迭代器。
  • 自定义类当 HashMap 键,只重写 equals。hashCode 契约破坏,对象「失踪」;让 IDE 生成,两个一起。
  • 拿 LinkedList 当万能表。理论上灵活,实测被 ArrayList 碾压(10.2 的实测视角);想清楚再选。
  • 集合里塞基本类型的坑。List<int> 不存在(泛型要对象),自动装箱救场但批量装箱有性能税(第 9 章),大数据量考虑 IntStream 或数组。

练习

  1. 实现:词频统计(第 9 章练习的 HashMap 版):读一段文本,merge 一行搞定;再打印出现次数前三的词(entrySet 流式排序,或转 List 按 value 排)。
  2. 动手:复现 ConcurrentModificationException(抄 10.3 代码),然后用 removeIf 和「迭代器 remove」两种方式修复,对比可读性。
  3. 动手:验证 10.2 的实测结论:ArrayList 和 LinkedList 各插入 10 万元素到头部并遍历求和,计时;再尾部追加同样测,写一段实测结论(预期颠覆面试标准答案)。
  4. 思考:类型擦除让 Java 泛型「编译期检查、运行期无信息」,C++ 模板「每类型生成一份代码」。对比两者的空间/速度/二进制大小,再想想为什么 Kotlin、C# 选择了「泛型保留到运行时」(reified)的路线。
豫ICP备2026027944号