# 20260731 课堂笔记 — 迭代器、Map 集合与二叉树

- **日期**：2026-07-31
- **项目**：`c260731`
- **包路径**：`course`
- **作者**：WanJL

---

## 目录

1. [LinkedList 多接口形态（List / Queue / Deque）](#1-linkedlist-多接口形态list--queue--deque)
2. [Iterator 迭代器](#2-iterator-迭代器)
3. [Collection 体系回顾：Iterable → Collection](#3-collection-体系回顾iterable--collection)
4. [Map 集合（双列集合）与 HashMap 入门](#4-map-集合双列集合与-hashmap-入门)
5. [Map 集合的遍历（keySet + get / entrySet）](#5-map-集合的遍历keyset--get--entryset)
6. [HashMap 底层原理（哈希表结构）](#6-hashmap-底层原理哈希表结构)
7. [二叉树（二叉搜索树 / 平衡二叉树 / 红黑树）](#7-二叉树二叉搜索树--平衡二叉树--红黑树)
8. [随堂练习要点](#8-随堂练习要点)
9. [拓展阅读](#9-拓展阅读)

---

## 1. LinkedList 多接口形态（List / Queue / Deque）

### 概念

`LinkedList` 是 Java 集合框架中功能最「全面」的实现类之一，它**同时实现了多个接口**：

- `List<E>` 接口 —— 列表（线性表），有序、可重复、带索引
- `Queue<E>` 接口 —— 队列，先进先出（FIFO）
- `Deque<E>` 接口 —— 双端队列（Double Queue），两端都可以入队 / 出队

同一个 `LinkedList` 对象，可以用不同的**接口类型**去引用。声明类型不同，「看得见」的方法就不同——这是**接口多态**（编译看左边：接口类型决定可用方法；运行看右边：真实对象是 LinkedList）。

| 声明类型 | 语义 | 可见的核心方法 |
|----------|------|----------------|
| `LinkedList<Object>` | 最全的方法集合（链表本体） | 链表 + List + Queue + Deque 全部方法 |
| `List<Object>` | 列表线性表 | `add/get/set/remove`、`indexOf`、`contains` 等 |
| `Queue<Object>` | 队列（FIFO） | `offer` 入队、`poll` 出队、`peek` 查看队头 |
| `Deque<Object>` | 双端队列 | `addFirst/addLast`、`pollFirst/pollLast`、`peekFirst/peekLast`、`push/pop`（栈） |

### 代码示例

```java
// 来源：course/Demo01.java
package course;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Demo01 {
    public static void main(String[] args) {
        // 使用最全的方法 --- 链表
        LinkedList<Object> list = new LinkedList<>();
        // 如果想使用 List 的方法 --- 列表线性表
        List<Object> list1 = new LinkedList<>();
        // 如果想使用队列 --- Queue
        Queue<Object> queue = new LinkedList<>();
        // 如果想使用双端队列 --- Double Queue
        Deque<Object> deque = new LinkedList<>();
    }
}
```

### 关键理解

1. **一个对象，多种身份**：`new LinkedList<>()` 创建的是同一个对象，但可以赋予 `List`、`Queue`、`Deque` 三种「身份」。
2. **接口作为引用类型 = 能力限定**：用 `Queue` 引用时只能调用队列方法（如 `offer/poll/peek`），无法调用 `get(int)` 这类 List 方法——把能力「收窄」到所需范围。
3. **实际应用**：需要栈/队列场景时，用 `Queue`/`Deque` 引用 `LinkedList`，语义更清晰，也方便后续替换实现类。

---

## 2. Iterator 迭代器

### 概念

由于 `Collection` 集合接口继承了 `Iterable` 接口，所以我们使用的**所有单列集合**都具备 `Iterable` 的方法（`iterator()`），并且各个实现类都重写了它。

- 通过集合对象的 `iterator()` 方法获取该集合对应的**迭代器对象**（`Iterator<E>`）
- 迭代器提供**统一的遍历方式**，与集合的内部结构（数组 / 链表）无关
- 特别适合遍历没有索引的集合（如 `Set`、`LinkedList`）

### Iterator 核心方法

| 方法 | 返回值 | 说明 |
|------|--------|------|
| `boolean hasNext()` | `boolean` | 判断迭代器是否还有下一个元素 |
| `E next()` | `E` | 返回下一个元素，并把指针向后移动一位 |
| `void remove()` | `void` | 从集合中移除上次 `next()` 返回的元素（可选操作） |

迭代器内部有一个**指针**，初始位置在第一个元素之前：

```
 [元素1] → [元素2] → [元素3] → [元素4]  …  → null
   ↑
 iterator 初始位置（第一个元素之前）
```

- `hasNext()`：判断指针后是否还有元素
- `next()`：取出当前元素并把指针后移

### 代码示例

```java
// 来源：course/Demo02.java
package course;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class Demo02 {
    /*
        由于Collection集合接口继承了Iterable接口
        所以我们使用的所有的单列集合，都具有Iterable的方法，并且重写了方法
     */
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("元素1");
        list.add("元素2");
        // ... 共添加10个元素

        // 方式一：我们遍历集合 —— for + 索引（ArrayList 有索引才支持）
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        // 方式二：通过迭代器进行迭代遍历
        Iterator<String> iterator = list.iterator();   // 通过集合对象获取它对应的迭代器对象
        while (iterator.hasNext()) {                   // 判断迭代器有没有下一个元素，有就继续
            String element = iterator.next();          // 通过迭代器对象获取下一个元素
            System.out.println(element);
        }

        // 创建字符串泛型的 LinkedList 集合
        LinkedList<String> list1 = new LinkedList<>();
        // 添加10个元素 ...

        // LinkedList 同样可以使用迭代器（链表没有索引，for+get 效率低）
        Iterator<String> iterator1 = list1.iterator();
        while (iterator1.hasNext()) {
            String s = iterator1.next();
            System.out.println(s);
        }
    }
}
```

### 迭代器使用模板

```java
Iterator<E> it = 集合对象.iterator();  // 1. 获取迭代器
while (it.hasNext()) {                 // 2. 判断是否有下一个
    E e = it.next();                   // 3. 获取下一个元素并后移指针
    // 处理元素
}
```

### 注意

- **指针只能单向移动**：`next()` 只能向后，不能回退。
- `next()` 会**移动指针**，多次调用 `next()` 会跳过元素。
- 迭代过程中若集合被修改（`add/remove`），会抛出 `ConcurrentModificationException`（快速失败机制）。

---

## 3. Collection 体系回顾：Iterable → Collection

### 继承结构

```
单列集合（Collection 体系）                       双列集合（Map 体系）
Iterable<E>                     ─────────────   Map<K,V> 接口（键值对）
    │                                                │
Collection<E>                  ── 并行存在 ──>   HashMap<K,V>（最常用实现类）
    ├── List<E>                    —— 列表：有序、可重复、带索引
    │      ├── ArrayList<E>        —— 数组结构，随机访问快
    │      └── LinkedList<E>       —— 双链表结构，插入删除快
    ├── Queue<E>                   —— 队列：先进先出（FIFO）
    │      └── Deque<E>            —— 双端队列（LinkedList 实现）
    └── Set<E>                     —— 集合：不可重复
```

### LinkedList 与多个接口的关系

```
                 LinkedList<E>
                      │
        ┌─────────────┼─────────────┐
        ▼             ▼             ▼
      List<E>      Queue<E>      Deque<E>
      （线性表）   （队列FIFO）  （双端队列/栈）
```

所以代码中才能写出：

```java
List<Object> list1 = new LinkedList<>();
Queue<Object> queue = new LinkedList<>();
Deque<Object> deque = new LinkedList<>();
```

### 遍历集合的三种方式对比

| 方式 | 适用场景 | 示例 |
|------|----------|------|
| `for + size() + get(i)` | 有索引的 List（ArrayList 效率高） | `for (int i = 0; i < list.size(); i++)` |
| **Iterator 迭代器** | 所有单列集合（通用方式） | `while (it.hasNext()) { it.next(); }` |
| 增强 for（foreach） | 所有集合与数组（底层也是迭代器） | `for (String s : list)` |

---

## 4. Map 集合（双列集合）与 HashMap 入门

### 概念

`Map` 集合是一个**接口**，属于**双列集合**，与单列集合（Collection）并行存在：

```java
public interface Map<K, V>
```

- 泛型有两个：`K` 代表 **Key（键）** 的类型，`V` 代表 **Value（值）** 的类型
- 存储的基本单位是**键值对**（`<Key, Value>`）
- **键（Key）不可以重复，值（Value）可以重复**
- 简单理解：可以把 Map 的键（Key）理解成数组中的**索引**，只是这个索引是我们自己定义的；Map 的值（Value）可以理解成数组的**元素**，元素可以重复，元素之间的顺序根据索引（Key）来确定
- Map 中最常用的实现类是 **`HashMap`**

创建 `HashMap` 对象有两种方式：

```java
Map<String,Object> map = new HashMap<>();       // 方式一：接口多态，左边声明为 Map 接口
HashMap<String,Object> map1 = new HashMap<>();  // 方式二：直接用实现类
```

### Map 常用方法

#### 基本使用

| 方法 | 说明 |
|------|------|
| `V put(K key, V value)` | 向 Map 集合中添加元素（键值对） |
| `boolean containsKey(Object key)` | 判断 Map 集合中是否包含指定的 key 键 |
| `boolean containsValue(Object value)` | 判断 Map 集合中是否包含指定的 value 值 |
| `void clear()` | 清空集合，移除所有的键值对元素 |
| `boolean isEmpty()` | 判断集合是否为空 |
| `int size()` | 返回集合中的有效元素个数 |

#### 获取元素

| 方法 | 说明 |
|------|------|
| `V get(Object key)` | 根据 Key 键获取 Value 值 |
| `Set<K> keySet()` | 把当前 Map 集合中的所有 Key 组成一个 Set 集合（无序的单列集合） |
| `Collection<V> values()` | 把所有的 Value 值组合成一个单列集合 |
| `Set<Map.Entry<K,V>> entrySet()` | 返回一个单列 Set 集合，集合中每个元素都是一个 Map 的内部类（Entry）对象，即由 Map 的键值对组成的一个类型 |

### 代码示例

```java
// 来源：course/Demo03.java
package course;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Demo03 {
    public static void main(String[] args) {
        Map<String,Object> map = new HashMap<>();
        map.put("id","x1001");
        map.put("name","张三");
        map.put("age",25);
        map.put("gender","男");

        Collection<Object> values = map.values();   // 获取所有值
        System.out.println(values);                 // [男, 张三, x1001, 25]（无序，顺序≠添加顺序）
        Set<String> set = map.keySet();             // 获取所有键
        System.out.println(set);                    // [gender, name, id, age]

        HashMap<String,Object> map1 = new HashMap<>();
        map1.put("x001","张三");
        map1.put("x002","李四");
        map1.put("x003","王五");
        map1.put("x004","赵六");

        System.out.println(map1.values());          // [李四, 王五, 赵六, 张三]
        System.out.println(map1.keySet());          // [x004, x003, x002, x001]
        System.out.println(map1);                   // 直接打印：{x004=赵六, x003=王五, x002=李四, x001=张三}
    }
}
```

### 关键理解

1. **HashMap 无序**：从输出可以看到，键值对的**存储顺序与添加顺序不一致**——HashMap 底层根据键的哈希值（hashCode）决定存储位置。
2. **键不可重复，值可重复**：同一个 Key 再次 `put` 会覆盖旧值；不同 Key 可以对应相同 Value。
3. **Map 与 Collection 的关系**：二者并行——Collection 是**单列集合**（存单个元素），Map 是**双列集合**（存键值对）。
4. **keySet() / values() 的用途**：Map 本身没有索引，想遍历键或值，就先转成单列集合（Set / Collection），再用迭代器或增强 for 遍历。

---

## 5. Map 集合的遍历（keySet + get / entrySet）

### 概念

Map 存入的元素都是成对出现的（键值对），可以把它看成是「夫妻对」的集合。Map 本身**没有索引**，不能像 List 那样用 `for + get(i)` 直接遍历，需要借助以下两种方式：

**方式一（keySet + get）：间接遍历**
1. 获取所有 Key 集合，使用 `keySet()` 方法实现
2. 遍历 key 集合，获取到每一个键（可以使用 foreach）
3. 根据 key 寻找 value，使用 `get(Object key)` 方法来实现

**方式二（entrySet）：直接遍历**
1. 获取所有键值对（Entry）对象的集合，使用 `entrySet()` 方法
2. 遍历键值对对象的集合
3. 根据键值对分别获取键和值（`getKey()` / `getValue()`）

### 代码示例

```java
// 来源：course/Demo04.java
package course;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Demo04 {
    public static void main(String[] args) {
        Map<String,Object> map=new HashMap<>();
        map.put("x001","张三");
        map.put("x002","李四");
        map.put("x003","王五");
        map.put("x004","赵六");

        System.out.println("---------遍历Map集合:方式一-------------");
        //1、获取所有Key集合，使用keySet()方法实现。
        Set<String> set = map.keySet();
        //2、遍历key集合，获取到每一个键，可以使用foreach
        for (String key:set){
            //3、根据key寻找value，使用get(Object key)方法来实现
            Object value = map.get(key);
            System.out.println("key:"+key+",value:"+value);
        }
        System.out.println("---------遍历Map集合:方式二-------------");
        //1、获取所有键值对（Entry）对象的集合
        Set<Map.Entry<String, Object>> entries = map.entrySet();
        //2、遍历键值对对象的集合
        for (Map.Entry<String, Object> me:entries){
            //3、根据键值对分别获取键和值
            String key = me.getKey();
            Object value = me.getValue();
            System.out.println("key:"+key+",value:"+value);
        }
    }
}
```

### 关键理解

- **方式一是「间接遍历」**：先拿 Key 集合，再用 `get(key)` 反查 Value，每次 `get()` 都是一次哈希查找
- **方式二是「直接遍历」**：一次性拿到键值对 Entry 对象，`getKey()` / `getValue()` 直接取值，效率更高
- `Map.Entry<K,V>` 是 Map 的**内部类型**，一个 Entry 就代表一个「键值对」
- 遍历结果依然体现 HashMap 的**无序**特性（顺序 ≠ 添加顺序）

---

## 6. HashMap 底层原理（哈希表结构）

### 概念

`HashMap` 是实现了 Map 接口的一种基于**哈希表结构**实现的集合：

- 哈希表本质来讲，可以理解为 **数组 + 链表**
- HashMap 依赖 `hashCode` 方法和 `equals` 方法来保证**键 Key 的唯一**
- 所以**自定义类型**如果想存入 HashMap 的 Key 中，就**一定要重写 `hashCode()` 和 `equals()` 方法**

### 哈希值

哈希值是 JDK 根据**对象的地址、字符串或数字**算出来的 `int` 类型的数值。获取方式：调用 Object 类中的 `hashCode()`，返回的就是哈希码值。

哈希值的特点：
1. **同一个对象**多次调用 `hashCode()`，返回的哈希值是**相同**的
2. **默认情况下**，不同的对象哈希值是不同的；重写 `hashCode()` 可以让我们实现不同对象的哈希值相同
3. 一般是在**多个对象的所有属性值完全相同时**，`hashCode()` 需要返回相同的哈希值

### 哈希表结构演示

```java
// 来源：course/Demo05.java（注释部分）
// 上面的数组是默认长度为 16 的数组，添加键值对时先计算键的哈希值（int 整数）
张三  --hash运算（hashCode）  --> 15
李四  --hash运算（hashCode）  --> 87
王五  --hash运算（hashCode）  --> 66
赵六  --hash运算（hashCode）  --> 20
wanjl --hash运算（hashCode）  --> 15    // 与"张三"哈希值相同 → 挂在同一位置的链表上
哈么么 --hash运算（hashCode）  --> 70
```

### JDK 1.7 及之前：数组 + 链表

存入流程：
1. 创建**默认长度为 16**、**默认负载因子 0.75** 的数组，数组名 `table`
2. 根据元素的哈希值跟数组长度进行计算，计算出应该存入的位置
3. 判断当前位置是否为 `null`，是 `null` 就直接存入
4. 如果位置不是 `null`（已有元素），就调用 `equals` 方法比较两个元素的属性值，判断是不是同一个
5. 如果是同一个就不存了；**不是同一个则存入**，老的元素挂在新元素的下边（形成链表）

> 能让两个相同哈希值的对象以链表的方式挂到后面，原因只有一个：**哈希值相同，但 equals 比较不同**。

**风险和弊端**：如果出现越来越多哈希值相同、但 `equals` 比较为 `false` 的元素，就会导致**链表过长，性能下降**。

### JDK 1.8 之后：数组 + 链表 / 红黑树

Java 1.8 之后引入了**红黑树**，1.8 之后的 HashMap 有两种形态：

- **第 1 种**：数组 + 链表（哈希表）
- **第 2 种**：在哈希表满足了某些条件后，从「数组 + 链表」转换为「数组 + 红黑树」，保证性能不会降低

简单来说：**链表的节点数超过 8 个，且数组长度大于 64 时，链表就转为红黑树**（两个条件需**同时满足**）。

### HashMap 关键常量

| 常量 | 值 | 说明 |
|------|-----|------|
| `DEFAULT_INITIAL_CAPACITY` | `16`（`1 << 4`） | 数组默认长度 |
| `DEFAULT_LOAD_FACTOR` | `0.75f` | 默认负载因子，已存入元素超过数组长度 × 0.75 就对数组扩容 |
| `TREEIFY_THRESHOLD` | `8` | **树化阈值**：链表节点长度超过 8 就转为红黑树 |
| `UNTREEIFY_THRESHOLD` | `6` | 当节点长度小于 6 时，从红黑树退化回链表 |
| `MIN_TREEIFY_CAPACITY` | `64` | 数组 + 链表转红黑树的**第 2 个条件**：数组长度必须大于 64 |

### 总结（HashMap 结构要点）

```java
// 来源：course/Demo05.java（注释部分·总结）
1、HashMap的结构是 数组+链表
2、达到一定条件，会转为 数组+红黑树
3、树化条件：数组长度大于64，链表节点长度超过8。
4、链表节点长度小于6就退化回链表。
```

1. **HashMap 的结构是「数组 + 链表」**，达到一定条件后转为「数组 + 红黑树」
2. **树化条件（两个需同时满足）**：① 数组长度大于 64（`MIN_TREEIFY_CAPACITY`）② 链表节点长度超过 8（`TREEIFY_THRESHOLD`）
3. **退化条件**：链表节点长度小于 6（`UNTREEIFY_THRESHOLD`）就退化回链表，避免频繁树化/退化造成抖动

### 代码示例

```java
// 来源：course/Demo05.java（本类为理论注释讲解，无 main 方法）
package course;

public class Demo05 {
    /*
        HashMap集合
            HashMap集合是实现了Map接口的一种基于【哈希表结构】实现的集合。
            HashMap集合依赖 hashCode方法和equals方法来保证 键Key的唯一。
            所以如果自定义类型想要存入到HashMap的Key中，就一定要重写【hashCode方法和equals方法】
        ...
        （核心内容见上方各小节）
     */
}
```

---

## 7. 二叉树（二叉搜索树 / 平衡二叉树 / 红黑树）

### 概念

**二叉树**是一种特殊的树形结构，在二叉树中，**任意一个节点的度小于等于 2**。

- **节点**：在树结构中，每一个元素称为节点
- **度**：每一个节点的子节点数量称为度

二叉树是集合底层结构（如 HashMap 的红黑树）的基础，演进路线为：**二叉树 → 二叉搜索树 → 平衡二叉树（AVL）→ 红黑树**。

### 二叉搜索树（Binary Search Tree）

二叉搜索树（二叉查找树、二叉排序树）是一种特殊的二叉树：

- 每一个节点最多有两个子节点
- **左子树**上的所有节点都**小于**根节点的值
- **右子树**上的所有节点都**大于**根节点的值

**添加节点的规则**：
- 比根节点小的，存左边
- 比根节点大的，存右边
- 一样的不存

示例：依次添加 `7  4  10  5  6`

```
        7
    4     10
       5
          6
```

### 平衡二叉树（AVL）

平衡二叉树也是一种特殊的二叉搜索树：

- 二叉树**左右的子节点的高度差不超过 1**
- 任意节点的左右两个子树都是一棵平衡二叉树（递归定义）
- **触发旋转的时机**：当添加一个子节点后，这棵树不再是平衡二叉树了
- 旋转方式：**左旋** 和 **右旋**

**左旋**：把根节点的右侧往左拉，原先的右子节点变为新的根节点，并且把多余的左子节点让出来，给已经降级的根节点当右子节点。

```
     7                                      7
  4     10             左旋 ->           4     11
           11                                10  12
             12
```

**右旋**：将根节点的左侧往右拉，左子节点变为新的父节点，并且把多余的右子节点让出来，给已经降级的父节点当左子节点。

**平衡二叉树的四种旋转情况**：

| 情况 | 不平衡原因（插入位置） | 旋转方式 |
|------|------------------------|----------|
| **左左（LL）** | 根节点左子树的左子树插入节点 | 直接对整体进行**右旋** |
| **左右（LR）** | 根节点左子树的右子树插入节点 | 先在左子树对应节点位置**左旋**，再对整体**右旋** |
| **右右（RR）** | 根节点右子树的右子树插入节点 | 直接对整体进行**左旋** |
| **右左（RL）** | 根节点右子树的左子树插入节点 | 先在右子树对应节点位置**右旋**，再对整体**左旋** |

### 红黑树（Red-Black Tree）

红黑树是一种特殊的平衡二叉树。它不是**高度平衡**的，它的平衡是通过自己的**红黑规则**来实现的。

**红黑规则**：
1. 每一个节点要么是红色的，要么是黑色的
2. **根节点必须是黑色的**
3. 如果一个节点没有子节点或没有父节点，那么该节点相应的指针属性值就是 `Nil`，这些 Nil 视为**叶子节点**，每个叶子节点都是黑色的
4. 如果某一个节点是红色的，那么它的子节点必须是黑色的——**不能出现两个红色节点相连**的情况
5. 对于每一个节点，从该节点到它所有后代叶子节点的**简单路径**上，都包含**相同数量的黑色节点**
6. 当向红黑树插入子节点的时候，默认节点是**红色**的（除非不满足红黑规则），效率更高

**添加节点时如何保持红黑规则**：
1. **根节点位置**：直接变为黑色
2. **非根节点位置，父节点为黑色**：新节点默认红色，无需调整
3. **非根节点位置，父节点为红色**，需要判断：
   - **叔叔节点是红色**：① 将父节点设置为黑色 ② 将叔叔节点设置为黑色 ③ 将祖父节点设置为红色 ④ 如果祖父节点是根节点，根节点再次变为黑色
   - **叔叔节点是黑色**：① 将父节点设置为黑色 ② 将祖父节点设置为红色 ③ 以祖父节点为支点进行旋转

**与集合框架的联系**：Java 集合中**完全使用红黑树实现的，是 `TreeMap`**。

### 与 HashMap 的联系

在上一节（HashMap 底层原理）我们了解到：JDK 1.8 之后的 HashMap 在链表长度 > 8 且数组长度 > 64 时，会把链表**树化**为红黑树。本节深入讲解了红黑树的理论基础——它由 二叉树 → 二叉搜索树 → 平衡二叉树（AVL）→ 红黑树 一步步演进而来。

---

## 8. 随堂练习要点

### 练习一：LinkedList 多接口引用

**核心步骤**：
1. 创建 `LinkedList<Object>` 对象
2. 分别用 `LinkedList`、`List`、`Queue`、`Deque` 四种类型引用它
3. 体会「声明类型不同 → 可见方法不同」的接口多态

**思考**：
- 用 `Queue` 引用时，能否调用 `get(int)`？—— 不能，编译错误，Queue 接口中没有该方法
- 为什么说 LinkedList 既能当队列又能当栈？—— 它实现了 Deque，Deque 提供了 `push/pop`（栈）和 `addFirst/addLast`（双端队列）

### 练习二：Iterator 迭代器遍历

**核心步骤**：
1. 创建一个 `ArrayList<String>`，添加 10 个元素
2. 用 `for + get(i)` 遍历
3. 用 `iterator()` 获取迭代器，`while (hasNext())` + `next()` 遍历
4. 再对 `LinkedList<String>` 执行同样的迭代器遍历

**思考**：
1. `hasNext()` 和 `next()` 分别做什么？—— 判断是否存在下一个元素 / 取出下一个元素并移动指针
2. 为什么 LinkedList 用 `for + get(i)` 效率低？—— 每次 `get(i)` 都要从头遍历节点，时间复杂度 O(n)，而迭代器沿链表逐个移动只需 O(1)
3. 增强 for 的底层机制是什么？—— 编译器会把 foreach 翻译成迭代器遍历

### 练习三：Map 集合键值对操作

**核心步骤**：
1. 创建一个 `HashMap<String,Object>`，用 `put()` 添加一组学生信息（`id` / `name` / `age` / `gender`）
2. 用 `keySet()` 获取所有键（返回 `Set<String>`）
3. 用 `values()` 获取所有值（返回 `Collection<Object>`）
4. 直接打印 `map` 观察 HashMap 的无序特性

**思考**：
1. Map 与 Collection 有什么区别？—— Collection 是单列集合（存单个元素），Map 是双列集合（存键值对）
2. 为什么 HashMap 打印时顺序和添加顺序不一致？—— 底层根据键的 hashCode 哈希决定存储位置
3. 为什么 `keySet()` 返回 Set？—— 键不可重复，正好符合 Set 的不可重复特性

### 练习四：遍历 Map 集合（两种方式）

**核心步骤**：
1. 创建 `HashMap<String,Object>`，用 `put()` 添加 4 组键值对
2. **方式一**：`keySet()` 获取所有键 → foreach 遍历键 → `get(key)` 获取值
3. **方式二**：`entrySet()` 获取所有 Entry → foreach 遍历 → `getKey()` / `getValue()` 获取键值
4. 对比两种方式的遍历输出

**思考**：
1. keySet 方式为什么比 entrySet 方式多一次查找？—— keySet 拿到 key 后还要用 `get(key)` 反查 value，entrySet 直接同时拿到键和值
2. `Map.Entry<String,Object>` 中的泛型怎么理解？—— 键是 String 类型，值是 Object 类型，Entry 就是这个键值对的类型
3. foreach 遍历 `Set<Map.Entry<...>>` 的底层是什么？—— 编译器翻译成迭代器遍历

### 练习五：HashMap 底层原理理解

**核心步骤**：
1. 阅读 Demo05 的注释，画出「数组 + 链表」的哈希表结构图
2. 手写一个自定义类，重写 `hashCode()` 和 `equals()`，验证它能作为 HashMap 的 Key
3. 说出 JDK1.7 和 JDK1.8 的 HashMap 结构差异

**思考**：
1. 为什么 HashMap 的 Key 要求重写 `hashCode()` 和 `equals()`？—— 哈希表要计算 Key 的存储位置（hashCode），并判断两个 Key 是否相同（equals），二者缺一不可
2. 为什么 JDK1.8 要引入红黑树？—— 防止哈希冲突导致链表过长、查询退化为 O(n)，红黑树保证 O(log n) 的查询效率
3. 负载因子 0.75 的含义？—— 当已存元素个数超过容量 × 0.75 时触发扩容（默认 16 → 扩容后约 32）

### 练习六：二叉树理论理解（二叉搜索树 / 红黑树）

**核心步骤**：
1. 阅读 Demo06 的注释，画出二叉搜索树的构建过程（`7 4 10 5 6`）
2. 手写一段数字序列，演示二叉搜索树的添加规则（小左大右、相同不存）
3. 说出 AVL 平衡二叉树的四种旋转情况（LL/LR/RR/RL）分别如何旋转
4. 记住红黑树的 6 条红黑规则，说明 HashMap 树化的原因

**思考**：
1. 二叉搜索树和普通二叉树的区别？—— 二叉搜索树多了「左小右大」的排序约束，查找效率可达 O(log n)
2. 为什么要引入 AVL / 红黑树？—— 防止二叉搜索树退化成链表（如按顺序插入 1~10），保证树的高度平衡、性能稳定
3. 红黑树相比 AVL 的优势？—— 红黑树不是高度平衡，插入/删除的旋转次数更少，综合性能更优；TreeMap 完全用红黑树实现

### 随堂练习参考解答（已提供代码）

对应课堂练习题的参考解答已写入授课代码：

| 练习 | 参考代码路径 |
|------|-------------|
| 进阶 1：自定义类作为 HashMap 的 Key | [`exericse/exericse01/Student.java`](./../授课代码/c260731/src/exericse/exericse01/Student.java) + [`StudentKeyTest.java`](./../授课代码/c260731/src/exericse/exericse01/StudentKeyTest.java) |
| 进阶 2：单词词频统计器 | [`exericse/exericse02/WordCountDemo.java`](./../授课代码/c260731/src/exericse/exericse02/WordCountDemo.java) |

---

## 9. 拓展阅读

### 官方文档

- [Iterable 接口 (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Iterable.html)
- [Iterator 迭代器 (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Iterator.html)
- [LinkedList (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedList.html)
- [Queue (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Queue.html)
- [Deque (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Deque.html)
- [Map 接口 (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Map.html)
- [HashMap (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/HashMap.html)
- [TreeMap (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/TreeMap.html)
- [Map.Entry (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Map.Entry.html)
- [Object.hashCode() (JDK 17)](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#hashCode())
- [红黑树 Red-Black Tree（Wikipedia）](https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91)
- [二叉搜索树 Binary Search Tree（Wikipedia）](https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91)
- [平衡二叉树 AVL 树（Wikipedia）](https://zh.wikipedia.org/wiki/AVL%E6%A0%91)

### 推荐阅读

- 《Java 核心技术 卷 I》第 9 章 集合 —— 迭代器与 foreach 的关系、Map 集合
- 《Effective Java》第 3 版 第 58 条：优先使用 foreach 循环而非传统 for 循环
- 《Java 编程思想》第 17 章 容器深入研究 —— 散列与哈希码
- 《算法（第 4 版）》第 3.3 节 红黑二叉查找树 —— 红黑树原理与实现

### 相关知识点

| 前置知识 | 当前知识 | 后续知识 |
|----------|----------|----------|
| ArrayList 底层原理（0729） | LinkedList 多接口形态（List/Queue/Deque） | ListIterator（双向迭代） |
| LinkedList 双链表理论（0730） | Iterator 迭代器 | 增强 for / forEach 方法 |
| 泛型与集合体系（0729） | Iterable → Collection 继承体系 | Set 集合与 Map 迭代 |
| Collection 单列集合体系 | Map 集合 / HashMap 入门 | Map 遍历（entrySet）、HashMap 底层哈希表 |
| equals/hashCode 重写（0728） | HashMap 底层原理（数组+链表/红黑树） | HashMap 扩容机制、哈希冲突优化 |
| HashMap 红黑树（本节 6） | 二叉树 / 二叉搜索树 / AVL / 红黑树 | TreeMap 与 Set 集合、树结构源码分析 |