元数据卡

项目	内容
前置知识	数组（第6章）
预计时间	20 分钟
完成标志	能画出 Collection 接口树，能根据场景选择正确的集合类型

---

阿花抱着一摞纸条跑进工坊："老陈让我把今天来领材料的村民登记一下。每个村人数不一样，有的12人，有的27人。"

你翻出数组准备写——发现问题了。String[100] 吧，人多了装不下，人少了浪费。想中间插一条记录？数组长度锁死了，你得亲手把后面的元素全往后挪。

你需要一种比数组更灵活的容器。

数组的痛

// 保存为 ArrayPain.java，执行 javac ArrayPain.java && java ArrayPain

public class ArrayPain {
    public static void main(String[] args) {
        String[] names = new String[100];    // 固定长度——不够灵活
        names[0] = "张三";
        names[1] = "李四";
        // 想在中间插"王五"？必须手动后移
        names[2] = names[1];
        names[1] = "王五";
        System.out.println("结果: " + names[0] + ", " + names[1] + ", " + names[2]);
    }
}

运行步骤： 保存为 ArrayPain.java，执行 javac ArrayPain.java && java ArrayPain

预期输出： 结果: 张三, 王五, 李四

每次中间插入都要手动后移——1000 条数据就是 1000 次复制。集合框架解决的就是这个问题。

Collection 丛林地图

Java 集合框架以两个顶层接口为根：

Iterable
 └── Collection (接口)
      ├── List      —— 有序、可重复、按索引存取
      │    ├── ArrayList   动态数组：查询快，增删慢（尾端除外）
      │    └── LinkedList  双向链表：增删快，查询慢
      ├── Set       —— 无序、不可重复（去重专用）
      │    ├── HashSet     基于 HashMap，O(1)
      │    └── TreeSet     基于 TreeMap，自动排序
      └── Queue     —— 队列（FIFO / 优先级）
           ├── ArrayDeque  双端队列，推荐替代 Stack
           └── PriorityQueue 按优先级出队

Map (独立接口，不与 Collection 共享继承树)
 ├── HashMap      哈希表实现，O(1) 读写
 ├── TreeMap      红黑树实现，key 自动排序
 └── LinkedHashMap 保持插入顺序

Map 虽然不在 Collection 继承树上，但也是集合框架的核心成员——每个元素是"键值对"，像工坊的库存账本，通过材料名查数量。

三分钟上手

// 保存为 CollectionDemo.java，执行 javac CollectionDemo.java && java CollectionDemo

import java.util.*;

public class CollectionDemo {
    public static void main(String[] args) {
        // List：有序可重复
        List<String> list = new ArrayList<>();
        list.add("铁锭"); list.add("木材"); list.add("铁锭");
        System.out.println("List: " + list);   // [铁锭, 木材, 铁锭]

        // Set：无序不可重复，自动去重
        Set<String> set = new HashSet<>();
        set.add("铁锭"); set.add("木材"); set.add("铁锭");
        System.out.println("Set: " + set + "  size=" + set.size()); // size=2

        // Map：键值对，通过 key 查 value
        Map<String, Integer> map = new HashMap<>();
        map.put("铁锭", 50); map.put("木材", 30);
        System.out.println("Map: 铁锭=" + map.get("铁锭")); // 50

        // Queue：FIFO 队列
        Queue<String> q = new ArrayDeque<>();
        q.offer("张三"); q.offer("李四");
        System.out.println("Queue 出队: " + q.poll()); // 张三
    }
}

运行步骤： 保存为 CollectionDemo.java，执行 javac CollectionDemo.java && java CollectionDemo

预期输出：

List: [铁锭, 木材, 铁锭]
Set: [木材, 铁锭]  size=2
Map: 铁锭=50
Queue 出队: 张三

选型决策树

按这个顺序问自己：

1. 需要通过名字/ID 查值？ → 用 Map（HashMap 默认，排序用 TreeMap）
2. 需要去重？ → 用 Set（HashSet 默认，排序用 TreeSet）
3. 主要按索引读取？ → ArrayList；频繁头尾增删？→ LinkedList

场景	选这个	别选这个
按索引读取（排行榜）	ArrayList	LinkedList（get(i) O(n)）
频繁头部插入/删除	LinkedList	ArrayList（头部插入 O(n)）
尾部追加（日志）	ArrayList	都一样
去重 + 无排序	HashSet	TreeSet（O(log n)）
去重 + 排序遍历	TreeSet	HashSet（不排序）
键值对 + 无排序	HashMap	TreeMap（O(log n)）
键值对 + 范围查询	TreeMap	HashMap（不支持）
FIFO 队列	ArrayDeque	LinkedList（更慢）

遍历集合

// 追加到 CollectionDemo.java 的 main 末尾，重新运行

List<String> items = Arrays.asList("铁锭", "木材", "皮革");
// 方式1：for-each（最常用）
for (String s : items) { System.out.println("材料: " + s); }

// 方式2：遍历 Map 的 entrySet
Map<String, Integer> m = new HashMap<>();
m.put("铁锭", 50); m.put("木材", 30);
for (Map.Entry<String, Integer> e : m.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

// 方式3：forEach + Lambda（Java 8+，最简洁）
items.forEach(s -> System.out.println(">> " + s));
m.forEach((k, v) -> System.out.println(k + " -> " + v));

预期输出：

材料: 铁锭
材料: 木材
材料: 皮革
铁锭 = 50
木材 = 30
>> 铁锭
>> 木材
>> 皮革
铁锭 -> 50
木材 -> 30

---

旅人笔记

数组长度固定、中间插入要手动挪位。集合框架的 List（有序可重复）、Set（自动去重）、Map（键值对）、Queue（FIFO）四大家族解决了这个问题。选容器先问：要不要通过键查值？要不要去重？要不要排序？回答完这三个问题，该用哪个就清楚了。

→ 下一步：List 详解

ArrayList 和 LinkedList 底层实现有何不同？ArrayList 扩容时容量翻多少倍？下一页用数据说话。

看 List 详解 →