20260731 课堂笔记 — LinkedList 多接口形态 / Iterator 迭代器 / Map集合（入门·遍历·底层原理）

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

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`（栈）

代码示例

// 来源：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<>();
    }
}

关键理解

一个对象，多种身份：new LinkedList<>() 创建的是同一个对象，但可以赋予 List、Queue、Deque 三种「身份」。
接口作为引用类型 = 能力限定：用 Queue 引用时只能调用队列方法（如 offer/poll/peek），无法调用 get(int) 这类 List 方法——把能力「收窄」到所需范围。
实际应用：需要栈/队列场景时，用 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()：取出当前元素并把指针后移

代码示例

// 来源：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);
        }
    }
}

迭代器使用模板

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）  （双端队列/栈）

所以代码中才能写出：

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）并行存在：

public interface Map<K, V>

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

创建 HashMap 对象有两种方式：

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 的键值对组成的一个类型

代码示例

// 来源：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=张三}
    }
}

关键理解

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

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

概念

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

方式一（keySet + get）：间接遍历

获取所有 Key 集合，使用 keySet() 方法实现
遍历 key 集合，获取到每一个键（可以使用 foreach）
根据 key 寻找 value，使用 get(Object key) 方法来实现

方式二（entrySet）：直接遍历

获取所有键值对（Entry）对象的集合，使用 entrySet() 方法
遍历键值对对象的集合
根据键值对分别获取键和值（getKey() / getValue()）

代码示例

// 来源：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()，返回的就是哈希码值。

哈希值的特点：

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

哈希表结构演示

// 来源：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 及之前：数组 + 链表

存入流程：

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

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

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

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

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

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

简单来说：链表的节点数超过 8 个，就转为红黑树。

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

代码示例

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

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

7. 随堂练习要点

练习一：LinkedList 多接口引用

核心步骤：

创建 LinkedList<Object> 对象
分别用 LinkedList、List、Queue、Deque 四种类型引用它
体会「声明类型不同 → 可见方法不同」的接口多态

思考：

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

练习二：Iterator 迭代器遍历

核心步骤：

创建一个 ArrayList<String>，添加 10 个元素
用 for + get(i) 遍历
用 iterator() 获取迭代器，while (hasNext()) + next() 遍历
再对 LinkedList<String> 执行同样的迭代器遍历

思考：

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

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

核心步骤：

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

思考：

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

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

核心步骤：

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

思考：

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

练习五：HashMap 底层原理理解

核心步骤：

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

思考：

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

前置知识	当前知识	后续知识
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 扩容机制、哈希冲突优化

20260731-笔记.md 24 KB History Raw

20260731 课堂笔记 — LinkedList 多接口形态 / Iterator 迭代器 / Map集合（入门·遍历·底层原理）

目录

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

概念

代码示例

关键理解

2. Iterator 迭代器

概念

Iterator 核心方法

代码示例

迭代器使用模板

注意

3. Collection 体系回顾：Iterable → Collection

继承结构

LinkedList 与多个接口的关系

遍历集合的三种方式对比

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

概念

Map 常用方法

基本使用

获取元素

代码示例

关键理解

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

概念

代码示例

关键理解

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

概念

哈希值

哈希表结构演示

JDK 1.7 及之前：数组 + 链表

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

HashMap 关键常量

代码示例

7. 随堂练习要点

练习一：LinkedList 多接口引用

练习二：Iterator 迭代器遍历

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

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

练习五：HashMap 底层原理理解

8. 拓展阅读

官方文档

推荐阅读

相关知识点

20260731-笔记.md 24 KB

History Raw