day06｜java.util 包下的常用 API：集合（Collection、List、Set）

本日有两条主线。上半场是异常——代码在编译或执行过程中出问题时，程序怎样把”这次操作没能按约定完成”这件事表达出来，并带回到有能力处理它的地方；下半场是集合（一）——当一组数据需要动态增删、还需要按索引访问或自动去重时，用哪种容器来组织，以及它们底层的数组、链表、哈希表、红黑树各自带来什么代价。学完后应能回答：编译时异常和运行时异常差在哪、throws 和 try…catch 该怎么选、迭代器为什么不能在遍历时用集合自己的方法删元素、ArrayList/LinkedList/HashSet/LinkedHashSet/TreeSet 分别在什么场景下用。

本日 PPT 目录（第 2 页 / 第 7 页）：异常 → 认识异常 → 自定义异常 → 异常的处理 → 集合体系概述 → Collection 的常用方法 → Collection 的遍历方式 → List 集合 → Set 集合 → 注意事项：集合的并发修改异常问题。

三点说明（供复习时核对）：

• 课件第 1 页标题是「异常、集合(一)」，本日只讲 Collection 这一支；Map（双列集合）与 Collections 工具类在 day07。
• 课件里多处「常见方法」页在抽取文本中只留下 [表格] 占位、没有表体。本文按课件的题目页与配套示例工程还原这些表格，还原处已标注「（表格按课件题目整理）」。
• PPT 抽出的 79 张图片中绝大多数是装饰文字图（如「数组的特点」「查询快、增删慢」）、卡通与表情包，与知识点无关，已按规范舍弃；本文只内嵌少量真正有信息量的截图与结构图。

1. 认识异常

1.1 异常是什么

课件第 6 页的定义很直接：异常是代码在编译或者执行的过程中可能出现的错误。

课件的引入例子是两行注定出错的代码（第 3 页）：

int[] arr = {10, 20, 30};
System.out.println(arr[3]);   // 下标越界
System.out.println(10 / 0);   // 除数为 0

这两行分别会在运行时抛出不同类型的异常对象，控制台会把异常的类型、消息和出错位置打成一段堆栈信息：

课件用这两段报错说明：异常对象本身携带了出错类型 + 出错原因 + 出错位置三样信息，这正是后面「异常的作用」那一节的基础。

1.2 异常的体系结构

异常的根类是 java.lang.Throwable，它下面分成两支：

java.lang.Throwable
├── Error                       ← 系统级别错误，开发人员不用管
└── Exception                   ← 程序可能出现的问题，我们用的就是它
    ├── RuntimeException        ← 运行时异常（及其子类）
    └── 其他异常…               ← 编译时异常

课件对两支的定位（第 4 页原话）：

• Error：代表的系统级别错误（属于严重问题），也就是说系统一旦出现问题，sun 公司会把这些问题封装成 Error 对象给出来。说白了，Error 是给 sun 公司自己用的，不是给我们程序员用的，因此我们开发人员不用管它。
• Exception：叫异常，它代表的才是我们程序可能出现的问题，所以程序员通常会用 Exception 以及它的孩子来封装程序出现的问题。

课件第 18 页把 Map 体系的 LinkedHashMap 误写成 LinedHashMap，属笔误（见第 3.1 节）。

1.3 编译时异常与运行时异常

课件第 6 页给出的分类依据：

类别	判断依据	编译阶段的表现	课件举的例子
运行时异常	继承自 RuntimeException 的异常或其子类	编译阶段不报错，运行时才出现	数组索引越界异常
编译时异常	没有继承 RuntimeException 的异常	编译阶段就会出错	日期解析异常

课件说法：「编译时异常：没有继承 RuntimeException 的异常，编译阶段就会出错。」；更准确的表述：编译时异常并不表示错误发生在编译期——它表示编译器要求你「要么 try…catch 处理、要么在方法上 throws 声明」的受检异常，真正的失败仍然发生在运行期，只是编译器提前把这类必须表态的异常拦下来了。

（补充说明）JDK 里的对应术语是 checked / unchecked exception；Error、RuntimeException 及其子类属于非受检，其余 Exception 子类属于受检。

2. 异常的作用与自定义异常

2.1 异常的作用

课件第 8 页用连续四张图给出两条作用：

1. 异常是用来查寻系统 Bug 的关键参考信息。（异常堆栈里带着类名、方法名、行号，是定位问题最快的入口）
2. 异常可以作为方法内部的一种特殊返回值，以便通知上层调用者底层的执行情况。

第 2 条是理解后面「异常的处理」的关键：当一个方法没法在自己的职责范围内决定怎么处理失败时，它可以把失败「返回」给调用者——只不过这个返回值不是 return，而是抛出的异常对象。

2.2 自定义异常

课件第 9–10 页说明了为什么要自定义：

Java 无法为这个世界上全部的问题都提供异常类来代表，如果企业自己的某种问题想通过异常来表示，以便用异常来管理该问题，那就需要自己来定义异常类了。

自定义异常分两类，定义步骤完全对称：

种类	定义方式	效果
自定义编译时异常	定义一个异常类继承 Exception；重写构造器；通过 throw new 异常类(xxx) 来创建异常对象并抛出	编译阶段就报错，提醒更加强烈
自定义运行时异常	定义一个异常类继承 RuntimeException；重写构造器；通过 throw new 异常类(xxx) 来创建异常对象并抛出	编译阶段不报错，提醒不强烈，运行时才可能出现

以本日作业三的 ATM 取钱场景为例，把上面的规则落成代码（按课件描述整理）：

// 自定义运行时异常：取款金额不合法
public class MoneyIllegalException extends RuntimeException {

    public MoneyIllegalException() {
    }

    public MoneyIllegalException(String message) {
        super(message);   // 把失败原因交给父类保存，getMessage() 可以取回
    }
}

public void drawMoney(double money) {
    if (money > balance) {
        // 创建异常对象并抛出，通知调用者这次取款没有完成
        throw new MoneyIllegalException("余额不足，当前余额为：" + balance);
    }
    balance -= money;
}

选择建议（按课件两条效果反推）：希望调用方必须面对这个失败、否则编译不过，就继承 Exception；这个失败属于用法/数据错误、让它在运行时暴露即可，就继承 RuntimeException。

3. 异常的处理

课件把处理方式分成两大类（第 5 页与第 14 页内容一致，第 14 页多给了推荐写法）。

3.1 抛出异常（throws）

在方法上使用 throws 关键字，可以将方法内部出现的异常抛出去给调用者处理。

方法 throws 异常1, 异常2, 异常3 ... {
}

// 推荐方式
方法 throws Exception {
}
// Exception 代表可以捕获一切异常

throws 只负责「声明」，它并不处理异常；异常会沿着方法调用链一路往上走，直到某一层接住它。

3.2 捕获异常（try…catch）

直接捕获程序出现的异常。

try {
    // 监视可能出现异常的代码！
} catch (异常类型1 变量) {
    // 处理异常
} catch (异常类型2 变量) {
    // 处理异常
}

// 推荐方式
try {
    // 可能出现异常的代码！
} catch (Exception e) {
    e.printStackTrace();   // 直接打印异常对象的信息
}
// Exception 代表可以捕获一切异常

（补充说明）课件把 throws Exception / catch (Exception e) 称为「推荐方式」，是从「最外层集中兜底」的开发习惯出发的；catch 多个分支时应遵守先具体、后一般的顺序，否则子类分支永远匹配不到。

3.3 开发中对于异常的常见处理方式

课件第 13 页把实际项目里的做法归为三种：

1. 捕获异常，记录异常并响应合适的信息给用户（最常见：把技术异常转成用户看得懂的提示）；
2. 捕获异常，尝试重新修复（例如网络抖动后重试）；
3. 异常，抛给调用者（当前方法无法处理，交给上层决定）。

课件第 15 页的总结给出了工程上的默认姿势：

在开发中异常的常见处理方式是：底层的异常抛出去给最外层，最外层集中捕获处理。

也就是说：底层方法用 throws 声明并向上传播，只在真正有能力恢复、转换或展示失败的那一层 try…catch。

4. 集合体系概述

集合是一种容器，用来装数据的，类似于数组，但集合的大小可变，开发中也非常常用。

4.1 单列集合与双列集合

课件第 18–19 页把集合分成两套体系：

• Collection 代表单列集合，每个元素（数据）只包含一个值。
• Map 代表双列集合，每个元素包含两个值（键值对）。课件用「脉劫 5 元 / 康帅傅 3 元 / 粤利粤 10 元」这类「商品名 → 价格」的对应关系来演示键值对。

整体体系结构：

Collection<E>（接口）
├── List<E>（接口）          → ArrayList<E>、LinkedList<E>
│                              还有 Vector / Stack 等（本日不讲）
└── Set<E>（接口）           → HashSet<E>、LinkedHashSet<E>、TreeSet<E>

Map<K, V>（接口）            → HashMap<K, V>、LinkedHashMap<K, V>、TreeMap<K, V>

课件第 18 页的图里 LinkedHashMap 被拼成了 LinedHashMap，属课件笔误。Map 不继承 Collection，是并列的另一棵树。

4.2 List 与 Set 两大系列的特点

课件第 20 页原话：

List 系列集合：添加的元素是有序、可重复、有索引。 ArrayList、LinkedList：有序、可重复、有索引。 Set 系列集合：添加的元素是无序、不重复、无索引。 HashSet：无序、不重复、无索引； LinkedHashSet：有序、不重复、无索引。 TreeSet：按照大小默认升序排序、不重复、无索引。

系列	有序性	是否可重复	有无索引	实现类
List	有序（保留添加顺序）	可重复	有索引	ArrayList、LinkedList
Set	HashSet 无序 / LinkedHashSet 有序 / TreeSet 按大小排序	不重复	无索引	HashSet、LinkedHashSet、TreeSet

课件第 21 页的自测三问：单列集合的代表是 Collection、双列集合的代表是 Map；Collection 下有 List、Set 两大体系。

（补充说明）List 的「有序」指元素有位置、按下标排列，不等于按数值大小自动排序；Set 的「有序/无序」指的是「迭代顺序是否等于添加顺序」，TreeSet 则是按比较结果排序——三者的「序」含义不同，这是最容易混淆的地方。

5. Collection 的常用方法

课件第 23 页先回答了「为啥要先学 Collection 的常用方法」：

Collection 是单列集合的祖宗，它规定的方法（功能）是全部单列集合都会继承的。

所以记住一张表，List 和 Set 的方法就基本会了。

（表格按课件题目整理，课件原表为图片、抽取文本中只有 [表格] 占位）

方法	说明
public boolean add(E e)	把给定的对象添加到当前集合中
public void clear()	清空集合中所有的元素
public boolean remove(E e)	把给定的对象在当前集合中删除
public boolean contains(Object obj)	判断当前集合中是否包含给定的对象
public boolean isEmpty()	判断当前集合是否为空
public int size()	返回集合中元素的个数
public Object[] toArray()	把集合中的元素，存储到数组中

（补充说明）remove 与 contains 判断的是「按相等规则是否命中」，对 Set 的去重、对存自定义对象的集合尤为重要，见第 8.4 节。

6. Collection 的遍历方式

课件导航页（第 25 / 29 / 33 页）列出三种遍历方式，并特意追问一句「以前学习的普通 for 呢？」——这个问题留到 List 一节回答。

6.1 迭代器

迭代器是用来遍历集合的专用方式（数组没有迭代器），在 Java 中迭代器的代表是 Iterator。

获取迭代器（Collection 提供）：

方法	说明
Iterator<E> iterator()	得到迭代器对象，默认指向当前集合的索引 0

Iterator 迭代器中的常用方法：

方法	说明
boolean hasNext()	询问当前位置是否有元素存在
E next()	获取当前位置的元素，并同时将迭代器对象移向下一个位置

遍历代码（课件第 27 页，同一段代码在页面上重复演示了每一步的指针位置）：

Iterator<String> it = lists.iterator();
while (it.hasNext()) {
    String ele = it.next();
    System.out.println(ele);
}

课件用集合 ["赵敏", "小昭", "素素", "灭绝"] 演示执行流程：iterator() 得到迭代器后默认指向索引 0；每调用一次 next() 取走当前元素并把指针后移一位；当 hasNext() 返回 false（课件图中标出的最后一个状态）时循环结束。

课件第 28 页的自测问答：如何获取集合的迭代器？——Iterator<E> iterator()，默认指向当前集合的索引 0。通过迭代器获取集合的元素，如果取元素越界会出现什么异常？——NoSuchElementException（所以必须先用 hasNext() 判断）。

6.2 增强 for 循环

格式：

for (元素的数据类型 变量名 : 数组或者集合) {
    // 在此处使用变量即可，该变量就是元素
}

示例：

Collection<String> c = new ArrayList<>();
// ...
for (String s : c) {
    System.out.println(s);
}

课件强调三点：

• 增强 for 既可以用遍历集合，也可以用来遍历数组；
• 增强 for 遍历集合，本质就是迭代器遍历集合的简化写法；
• 修改增强 for 中的变量值不会影响到集合中的元素（第 31 页用一个 "q" 的赋值演示：循环变量只是元素的一个副本，改它不改变集合里的 "a" "b" "c"）。

第 2 点在第 9 章会直接决定「遍历时删元素」会不会报错。

6.3 Lambda 表达式

得益于 JDK 8 开始的新技术 Lambda 表达式，提供了一种更简单、更直接的方式来遍历集合。

先看匿名内部类的写法，再看 Lambda 的简化：

Collection<String> lists = new ArrayList<>();
// ...
lists.forEach(new Consumer<String>() {
    @Override
    public void accept(String s) {
        System.out.println(s);
    }
});

lists.forEach(s -> {
    System.out.println(s);
});

// 参数只有一个、方法体只有一行时还可以更短
// lists.forEach(s -> System.out.println(s));

（表格按课件整理）

方法	说明
void forEach(Consumer<? super E> action)	结合 Lambda 表达式遍历集合

6.4 以前学的普通 for 呢

普通 for 依赖 get(int index) 取元素，而 get(int index) 是 List 因为有索引才提供的特有方法（第 7.1 节）。Collection 接口本身不提供按索引取值，所以普通 for 只能用来遍历 List 系列，不能用来遍历 Set。

6.5 案例：遍历集合中的自定义对象

课件第 35–37 页给了「展示多部电影信息」的案例。

• 需求：展示多部电影信息。
• 分析：每部电影都是一个对象，多部电影要使用集合装起来；遍历集合中的 3 个电影对象，输出每部电影的详情信息。

课件直接引用了豆瓣电影 Top 250 的页面作为数据结构参照：

电影类：

public class Movie {
    private String name;     // 片名
    private double score;    // 评分
    private String acotr;    // 主演（课件拼写为 acotr）

    public Movie(String name, double score, String acotr) {
        this.name = name;
        this.score = score;
        this.acotr = acotr;
    }

    // ... getter + setter
    public String getName() { return name; }
    public double getScore() { return score; }
    public String getAcotr() { return acotr; }

    @Override
    public String toString() {
        return name + " " + score + " " + acotr;
    }
}

测试类：

public class SystemDemo {
    public static void main(String[] args) {
        Collection<Movie> movies = new ArrayList<>();
        movies.add(new Movie("《肖生克的救赎》", 9.7, "罗宾斯"));
        movies.add(new Movie("《霸王别姬》", 9.6, "张国荣、张丰毅"));
        movies.add(new Movie("《阿甘正传》", 9.5, "汤姆.汉克斯"));
        System.out.println(movies);

        for (Movie movie : movies) {
            System.out.println("片名：" + movie.getName());
            System.out.println("评分：" + movie.getScore());
            System.out.println("主演：" + movie.getAcotr());
        }
    }
}

课件第 36 页把类名、变量名和内存示意图画在同一页（SystemDemo / Movie / movices 混排），抽取文本顺序被打乱，上面的代码是按语义重新拼回的。

集合存储对象的原理（课件第 36–37 页的内存图与问答）：集合中存储的是元素对象的地址。movies 变量在栈内存中指向堆内存里的集合对象，集合内部（数组或哈希表）的每个格子存放的是 Movie 对象的地址，而不是对象本身——所以第 2.1 节说的「集合与对象的关系」在内存上就是「容器持有引用」。

第 37 页的自测题答案也在这里：集合中存储的是元素对象的地址。

7. List 集合

课件导航（第 38 / 42 / 44 页）：特点、特有方法 → 遍历方式 → ArrayList 集合的底层原理 → LinkedList 集合的底层原理。

7.1 特点与特有方法

List 系列集合特点：有序，可重复，有索引。 ArrayList：有序，可重复，有索引。 LinkedList：有序，可重复，有索引。

List 集合因为支持索引，所以多了很多与索引相关的方法，当然，Collection 的功能 List 也都继承了。

（表格按课件题目整理）

方法	说明
void add(int index, E element)	在此集合中的指定位置插入指定的元素
E remove(int index)	删除指定索引处的元素，返回被删除的元素
E set(int index, E element)	修改指定索引处的元素，返回被修改的元素
E get(int index)	返回指定索引处的元素

（补充说明）这里有个经典重载陷阱：list.remove(2) 删除的是索引 2 的元素，list.remove("java") 删除的是内容为 “java” 的元素；对 List<Integer> 来说 remove(2) 与 remove(Integer.valueOf(2)) 结果完全不同。本日作业第 8 题和第 11 题考的就是这一点。

7.2 List 集合支持的遍历方式

课件第 43 页列出四种：

• for 循环（因为 List 集合有索引）；
• 迭代器；
• 增强 for 循环；
• Lambda 表达式。

比 Collection 多出来的那一种，正是 6.4 节回答的普通 for。

7.3 ArrayList 集合的底层原理

底层基于数组实现。

课件第 46–49 页用「A B C E F G D」+ 下标 0～6 的格子图，配三句话总结数组这种存储方式的表现：

• 查询速度快（注意：是根据索引查询数据快）：查询数据通过地址值和索引定位，查询任意数据耗时相同。
• 删除效率低：可能需要把后面很多的数据进行前移。
• 添加效率极低：可能需要把后面很多的数据后移，再添加元素；或者也可能需要进行数组的扩容。

接着第 50–58 页用逐步动画演示了 ArrayList 的扩容过程：

1. 利用无参构造器创建的集合，会在底层创建一个默认长度为 0 的数组（elementData）。
2. 添加第一个元素时，底层会创建一个新的长度为 10 的数组。
3. 数组里同时维护 size 变量——它既是元素个数，也是下次存入的位置。
4. 存满时，会扩容 1.5 倍（10 → 15）。
5. 如果一次添加多个元素，1.5 倍还放不下，则新创建数组的长度以实际为准。课件举例：在已有 10 个元素的基础上再 addAll 11 个数据，新数组长度直接是 21。

List<String> list1 = new ArrayList<>();
list1.add("a");
// ...
List<String> list2 = new ArrayList<>();
list2.add("a11");
// ...
list1.addAll(list2);   // 把集合 list2 的数据全部倒入到 list1 集合

课件说法：「添加第一个元素时，底层会创建一个新的长度为 10 的数组」；更准确的表述：容量 10 不是在构造时就分配，而是延迟初始化——构造时给的是空数组，第一次 add 触发扩容时才分配 10。（补充说明）「1.5 倍」和「长度 21」都是 JDK 的具体实现细节，复习时理解「按需扩容、新长度取两者较大值」即可，不必背数字。

应用场景（第 59–60 页问答）：

• 适合：根据索引查询数据，比如根据随机索引取数据（高效），或者数据量不是很大时。
• 不适合：数据量大的同时，又要频繁地进行增删操作。

7.4 LinkedList 集合的底层原理

基于双链表实现。

课件第 63 页的结点图给出了链表的本质：

链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址。（双向链表的结点还额外包含前一个结点的地址。）

第 63–66 页用 A、B、D、E 四个结点演示了「创建一个链表 → 在 B、D 之间添加 C → 删除 C、E 之间的 D」的全过程，两个动作都只改指针：

• 插入 C：① 让 C 的下一个结点地址指向 D；② 让 B 的下一个结点地址指向 C。
• 删除 D：① 让 C 的下一个结点地址指向 E；② 数据 D 本身不再被引用。

于是链表的特点：

• 查询慢：无论查询哪个数据都要从头开始找。
• 增删相对快。
• 课件第 67 页补充：对首尾元素进行增删改查的速度是极快的。

第 67 页还并排画了单向链表与双向链表的结点结构对比图。

LinkedList 新增了很多首尾操作的特有方法：

（表格按课件题目整理）

方法	说明
public void addFirst(E e)	在该列表开头插入指定的元素
public void addLast(E e)	将指定的元素追加到此列表的末尾
public E getFirst()	返回此列表的第一个元素
public E getLast()	返回此列表的最后一个元素
public E removeFirst()	从此列表中删除并返回第一个元素
public E removeLast()	从此列表中删除并返回最后一个元素

应用场景（第 69–74 页）：LinkedList 可以用来实现队列，也可以用来实现栈。

课件对队列的描述是「先进先出，后进后出」，并画了一端开口入队、另一端开口出队的示意图：

课件对栈的描述是「后进先出，先进后出」，数据进入栈模型的过程称为压/进栈（push），离开栈模型的过程称为弹/出栈（pop），栈只有一端开口，分成栈顶与栈底：

（补充说明）用 LinkedList 当栈用时对应 push() / pop()，当队列用时对应 addLast() / removeFirst()；课件这一页只讲了模型和适用场景，没有给出代码。

8. Set 集合

课件导航（第 76 / 79 / 104 / 108 页）：特点 → HashSet 集合的底层原理 → LinkedHashSet 集合的底层原理 → TreeSet 集合。

8.1 特点

Set 系列集合特点：无序（添加数据的顺序和获取出的数据顺序不一致）、不重复、无索引。 HashSet：无序、不重复、无索引。 LinkedHashSet：有序、不重复、无索引。 TreeSet：排序、不重复、无索引。

课件还特别提醒：

注意：Set 要用到的常用方法，基本上就是 Collection 提供的！自己几乎没有额外新增一些常用功能！

也就是说 Set 没有 get(int index)，想按位置取元素只能靠遍历。

8.2 前置知识：哈希值

在正式了解 HashSet 集合的底层原理前，我们需要先搞清楚一个前置知识：哈希值！

• 哈希值就是一个 int 类型的数值，Java 中每个对象都有一个哈希值。
• Java 中的所有对象，都可以调用 Object 类提供的 hashCode 方法，返回该对象自己的哈希值：public int hashCode()。
• 取值范围就是 int 的范围（-21 亿多 ~ 21 亿多）。课件用「45 亿个对象 → 只有 21 亿多 × 2 个哈希值」提示了哈希碰撞的必然性。

对象哈希值的特点：

• 同一个对象多次调用 hashCode() 方法返回的哈希值是相同的。
• 不同的对象，它们的哈希值一般不相同，但也有可能会相同（哈希碰撞）。

8.3 HashSet 集合的底层原理

HashSet 基于哈希表实现。哈希表是一种增删改查数据性能都较好的数据结构。

• JDK 8 之前，哈希表 = 数组 + 链表
• JDK 8 开始，哈希表 = 数组 + 链表 + 红黑树

JDK 8 之前 HashSet 的详细流程（课件第 82–99 页，用 0～15 共 16 个格子的 table[] 数组逐步演示）：

1. 创建一个默认长度 16、默认加载因子为 0.75 的数组，数组名 table；
2. 使用元素的哈希值对数组的长度做运算，计算出应存入的位置；
3. 判断当前位置是否为 null，如果是 null 直接存入；
4. 如果不为 null，表示有元素，则调用 equals 方法比较属性值：相等则不存；不相等则存入数组。
   • JDK 8 之前：新元素存入数组，占老元素位置，老元素挂下面；
   • JDK 8 开始之后：新元素直接挂在老元素下面。
5. 当数组存满到 16 × 0.75 = 12 时，就自动扩容，每次扩容为原先的两倍。

JDK 8 开始：当链表长度超过 8，且数组长度 ≥ 64 时，自动将链表转成红黑树。课件的小结是：

JDK8 开始后，哈希表中引入了红黑树后，进一步提高了操作数据的性能。

（补充说明）课件第 87 / 96 页的红黑树示意图上把底层数组标注成了 Segment[]——那是 JDK 7 里 HashMap 的分段锁结构，与 HashSet/HashMap 的 table 数组不是一回事。以课件第 82–86 页的 table[] 为准。

8.4 理解树结构

课件在第 89–95 页插了一组「树」的示意图，作为理解红黑树的前置知识。

二叉树：每个节点最多有两个子节点。课件给出的术语：

术语	含义
根节点	最顶层的节点
父节点 / 左子节点 / 右子节点	结点的上下关系
左子树 / 右子树	以子节点为根的子树
度	每一个节点的子节点数量
树高	树的总层数

二叉树中，任意节点的度 ≤ 2。每个节点在内存中可以表示为「父节点地址 + 值 + 左子节点地址 + 右子节点地址」。

二叉查找树（二叉排序树）的存放规则，课件用一张卡片概括：

二叉查找树存在的问题：当数据已经是排好序的（课件用 7、10、11、12、13 依次插入演示），树会退化成一条斜链，导致查询的性能与单链表一样，查询速度变慢。

平衡二叉树：在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。

红黑树：就是可以自平衡的二叉树。红黑树是一种增删改查数据性能相对都较好的结构。

8.5 HashSet 去重复

课件第 100–103 页先抛出一个问题：

比如内容一样的两个学生对象存入到 HashSet 集合中去，HashSet 集合是不能去重复的！ HashSet 集合默认不能对内容一样的两个不同对象去重复！

原因是 8.3 节的第 4 步：HashSet 先用哈希值定位、再用 equals 比较；如果类没有重写这两个方法，用的就是 Object 的默认实现（比较地址 / 返回地址推导出的哈希值），两个内容相同的新对象自然被判为「不相等」。

结论：

如果希望 Set 集合认为 2 个内容一样的对象是重复的，必须重写对象的 hashCode() 和 equals() 方法。

课件的需求与实现步骤：

• 需求：创建一个存储学生对象的集合，存储多个学生对象，使用程序实现在控制台遍历该集合，要求：学生对象的成员变量值相同，我们就认为是同一个对象。
• 分析：定义学生类 → 创建 HashSet 集合对象 → 创建学生对象 → 把学生添加到集合 → 在学生类中重写两个方法 hashCode() 和 equals()（自动生成即可） → 遍历集合（增强 for）。

public class Student {
    private String name;
    private int age;

    // 构造器、getter / setter 省略

    // 均为 IDEA 自动生成的形式
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

（补充说明）重写要遵守两条约定：equals 为 true 的两个对象 hashCode 必须相同；hashCode 相同不代表对象相等（还要过 equals 这一关）。另外，对象一旦加入哈希集合，就不要修改参与这两个方法的字段。

8.6 LinkedHashSet 集合的底层原理

依然是基于哈希表（数组、链表、红黑树）实现的。但是，它的每个元素都额外多了一个双链表的机制记录它前后元素的位置。

特点与原理小结（第 107 页问答）：

• 特点：有序、不重复、无索引。
• 底层基于哈希表，使用链表记录添加顺序。

也就是说：LinkedHashSet 在 HashSet 的哈希表之外挂了一条双向链表，遍历时顺着这条链表走，得到的就是添加顺序——去重能力来自哈希表，顺序能力来自链表。

8.7 TreeSet 集合

特点（第 109 页）：

不重复、无索引、可排序（默认升序排序，按照元素的大小，由小到大排序），底层是基于红黑树实现的排序。

课件给出的三条注意：

• 对于数值类型：Integer、Double，默认按照数值本身的大小进行升序排序。
• 对于字符串类型：默认按照首字符的编号升序排序。
• 对于自定义类型如 Student 对象，TreeSet 默认是无法直接排序的（因为 Java 不知道按什么比大小）。

自定义排序规则（第 110 页）：TreeSet 集合存储自定义类型的对象时，必须指定排序规则，支持两种方式：

方式	做法
方式一	让自定义的类（如学生类）实现 Comparable 接口，重写里面的 compareTo 方法来指定比较规则
方式二	通过调用 TreeSet 集合有参数构造器，设置 Comparator 对象（比较器对象）来指定比较规则：public TreeSet(Comparator<? super E> comparator)

两种方式中，关于返回值的规则（第 111 页）：

• 如果认为第一个元素 > 第二个元素，返回正整数即可；
• 如果认为第一个元素 < 第二个元素，返回负整数即可；
• 如果认为第一个元素 = 第二个元素，返回 0 即可，此时 TreeSet 集合只会保留一个元素，认为两者重复。

课件还特别提醒：

如果类本身有实现 Comparable 接口，TreeSet 集合同时也自带比较器，默认使用集合自带的比较器排序。

（补充说明）方式二的写法大致如下，课件只给了构造器签名，未给出代码：

TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        return Double.compare(o1.getScore(), o2.getScore());   // 按分数升序
    }
});

课件第 112 页自测答案重申：TreeSet 可排序、不重复、无索引，底层红黑树，增删改查性能较好；自定义类型有两种指定比较规则的方式。

第 109 页还配了一张「你让我怎么玩？！」的吐槽图，正好对应「自定义类型默认不能排序、必须先说清按什么比」这件事。

8.8 该选哪个集合

课件第 113 页再次给出完整体系特点，第 114 页按业务需求给了五条选择建议：

需求	选择	特点与底层
记住添加顺序 + 存重复元素 + 频繁按索引查询	ArrayList	有序、可重复、有索引，底层数组（常用）
记住添加顺序 + 增删首尾数据较多	LinkedList	有序、可重复、有索引，底层双链表
不在意顺序 + 无重复元素 + 增删改查都要快	HashSet	无序、不重复、无索引，底层哈希表（常用）
记住添加顺序 + 无重复元素 + 增删改查都要快	LinkedHashSet	有序、不重复、无索引，底层哈希表 + 双链表
要对元素排序 + 无重复元素 + 增删改查都要快	TreeSet	可排序、不重复、无索引，底层红黑树

9. 注意事项：集合的并发修改异常

课件第 116 页把这个问题单独拎出来作为一个章节：

• 使用迭代器遍历集合时，又同时在删除集合中的数据，程序就会出现并发修改异常的错误。
• 由于增强 for 循环遍历集合就是迭代器遍历集合的简化写法，因此使用增强 for 循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误。

怎么保证遍历集合同时删除数据时不出 bug？

1. 使用迭代器遍历集合，但用迭代器自己的删除方法删除数据即可（Iterator.remove()）：

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String ele = it.next();
    if ("java".equals(ele)) {
        it.remove();    // 用迭代器自己的删除方法
    }
}

2. 如果能用 for 循环遍历时：可以倒着遍历并删除；或者从前往后遍历，但删除元素后做 i-- 操作。

// 倒着遍历并删除
for (int i = list.size() - 1; i >= 0; i--) {
    if ("java".equals(list.get(i))) {
        list.remove(i);
    }
}

// 从前往后遍历，删除后 i--
for (int i = 0; i < list.size(); i++) {
    if ("java".equals(list.get(i))) {
        list.remove(i);
        i--;
    }
}

（补充说明）这个异常的名字是 ConcurrentModificationException；它并不是「多线程才有的问题」，单线程里边迭代边做结构性修改同样会触发——它的作用就是尽早暴露误用，不是线程安全保障。

10. 作业与练习

作业文档：day06-异常、Collection/day06作业/作业06/day06作业.md

一、选择题（12 题）——覆盖本日全部知识块：异常分类、所有异常的父类、try…catch…finally 结构（可以有多个 catch、可以没有 catch、finally 不是必需）、catch 子类在前导致的编译错误、throws Exception 该加在哪几行、迭代器说法辨析、泛型集合 ArrayList<String> 里 add(true) 的编译失败、遍历删除 "java" 的正确写法（倒序遍历）、List 的遍历方式、增强 for 的写法、迭代器遍历中 add 触发 ConcurrentModificationException、ArrayList 与 LinkedList 的对比。

二、今日单词：Exception、RuntimeException、throws、throw、List、Set、Collection、ArrayList、LinkedList、HashSet、LinkedHashSet、TreeSet。

三、简答题（6 题）：什么是异常、为什么要有这么多异常类；异常的体系结构涉及哪些类；List 与 Set 的区别；什么是迭代器、什么是并发修改异常、如何解决；ArrayList 的底层数据结构与特点；LinkedList 的底层数据结构与特点。

四、排错题（4 题）：

• 迭代器遍历中写 list.remove(str) 会抛 ConcurrentModificationException，应改成 it.remove()；
• 数组越界：arr 的最大索引为 2 却取了索引 3；
• finally 中的语句总会执行，即使前面抛出了空指针异常且没有 catch；
• 重写方法不能抛出更宽的编译时异常（父类方法没声明 ParseException 时，子类重写方法不能抛出它）。

五、代码题（3 题）：

• 第一题 抓阄游戏：5 个名称集合 + 5 个阄集合，遍历名称集合，随机生成索引从阄集合中取出并删除该元素，输出结果——练 List 的随机索引访问与删除；
• 第二题 斗地主发牌：创建 4 个 List（3 个玩家 + 底牌），遍历牌盒把牌存入对应集合，看牌即遍历集合；【选做】对每人手上的牌按 [3,4,5,6,7,8,9,10,J,Q,K,A,2,王] 排序；
• 第三题【选做】ATM 取钱金额校验：在 AtmServiceImpl 的 drawMoney 方法中加入校验逻辑，提示信息放 Entry 类，考虑使用自定义异常。

11. 复习要点

1. 异常的根接口/根类是 Throwable；Error 是系统级严重问题、开发人员不管，Exception 才是程序员要封装的程序问题；Exception 下再分受检（编译时）与非受检（运行时）两支。
2. 判断标准：继承自 RuntimeException 的是运行时异常（编译不报错、运行才出问题），没有继承 RuntimeException 的是编译时异常（编译阶段就必须处理或声明）。课件把编译时异常说成「编译阶段就会出错」，更准确的说法是「编译器强制要求你 try/catch 或 throws」。
3. 异常的两个作用：查找 Bug 的关键参考信息、作为方法内部的特殊返回值通知上层调用者；处理方式有捕获并提示、捕获并修复、向上抛出三种，工程默认姿势是「底层抛、最外层集中捕获」。
4. 自定义异常两条路线：继承 Exception（提醒强烈、必须处理）或继承 RuntimeException（编译不报错、运行才暴露），都要重写构造器并用 throw new 异常类(xxx) 抛出。
5. Collection 是单列集合的祖宗，Map 是双列集合；List = 有序 + 可重复 + 有索引，Set = 不重复 + 无索引（HashSet 无序、LinkedHashSet 有序、TreeSet 可排序）。注意三种「序」的含义不同。
6. 三种遍历：迭代器（iterator() / hasNext() / next()，越界取元素抛 NoSuchElementException）、增强 for（本质是迭代器的简化写法，改循环变量不影响集合元素）、Lambda（forEach）；普通 for 只有 List 能用，因为只有它有索引。
7. ArrayList 基于数组：按索引查询快（地址值 + 索引定位），增删需要移动元素且可能扩容；无参构造默认空数组、第一次 add 分配长度 10、满后扩 1.5 倍、一次加太多则按实际长度。适合「按索引查询、数据量不大」，不适合「数据量大又频繁增删」。
8. LinkedList 基于双链表：结点不连续、含数据值与前后结点地址，查询慢、增删相对快、首尾操作极快；可用来实现队列（先进先出）与栈（后进先出）。
9. HashSet 基于哈希表：JDK 8 之前是数组 + 链表，JDK 8 开始是数组 + 链表 + 红黑树；流程是「哈希值算位置 → 空位直接存 → 非空用 equals 比属性值 → 相等不存、不等挂链」；默认 16 长度 + 0.75 加载因子，存到 12 翻倍扩容，链表长度 > 8 且数组长度 ≥ 64 转红黑树。
10. 想让 Set 认为内容相同的两个对象重复，必须重写 hashCode() 和 equals()；LinkedHashSet 在哈希表之外用双链表记住添加顺序；TreeSet 默认不可排自定义类型，需要用 Comparable（compareTo）或 Comparator（构造器）指定规则，返回 0 即视为重复只保留一个。
11. 迭代器遍历（含增强 for）时用集合自身的方法删元素会抛 ConcurrentModificationException；解决办法是用 Iterator.remove()，或改用倒序 for 删除、正序删除后补 i--。