learnNote

主题

Chapter 14 · 集合框架（Collections Framework） ​

数组太死板，Java 集合是"会自动伸缩的容器"。

🎯 本章目标 ​

  • 理解 集合框架的整体结构
  • 掌握 List、Set、Queue、Map 的核心实现类
  • 学会选用合适的集合（性能 / 排序 / 唯一性）
  • 用对 迭代器（Iterator）
  • 知道 ArrayList vs LinkedList、HashMap vs TreeMap 的区别

1. 为什么需要集合？ ​

数组的痛点：

  • 长度固定（声明就死）
  • 类型单一
  • 操作笨重（删除一个元素要手动挪动）

集合解决：

  • 动态伸缩
  • 提供丰富 API（增删改查、排序、查找）
  • 配合泛型类型安全

2. 集合框架全景 ​

集合框架

                     Iterable
                        │
                  ┌─────┴─────┐
              Collection      Map
            ┌─────┼─────┐   ┌──┼──┐
          List  Set  Queue  HashMap  TreeMap  LinkedHashMap
           │     │     │
       ArrayList HashSet  LinkedList
       LinkedList TreeSet  PriorityQueue
       Vector     LinkedHashSet

💡 注意：Map 不属于 Collection！它是单独的体系。

3. List：有序、可重复 ​

实现类底层特点
ArrayList ⭐动态数组查找快 O(1)，增删慢 O(n)
LinkedList双向链表增删快 O(1)，查找慢 O(n)
Vector数组（synchronized）线程安全（很少用，用 CopyOnWriteArrayList 代替）

常用操作 ​

java
List<String> list = new ArrayList<>();
list.add("a");                  // 末尾添加
list.add(0, "x");               // 指定位置插入
list.set(1, "b");               // 修改
list.get(0);                    // 获取
list.remove("a");               // 按对象删
list.remove(0);                 // 按下标删
list.size();
list.contains("b");
list.isEmpty();
list.indexOf("b");

for (String s : list) { ... }                // for-each
list.forEach(System.out::println);            // JDK 8 forEach

List.of("a", "b", "c");                       // JDK 9+ 不可变 List

ArrayList vs LinkedList ​

操作ArrayListLinkedList
随机访问 get(i)O(1) ✓O(n)
末尾添加O(1) 摊销O(1)
中间插入 / 删除O(n)（要挪动）O(1)（节点切换）
内存紧凑每个节点要存指针

经验：90% 场景用 ArrayList，频繁头尾增删才用 LinkedList。

ArrayList vs LinkedList

4. Set：唯一不重复 ​

实现类底层特点
HashSet ⭐HashMap无序，O(1)，最常用
LinkedHashSetLinkedHashMap按插入顺序
TreeSet红黑树自动排序 O(log n)
java
Set<String> set = new HashSet<>();
set.add("a");
set.add("a");                  // 重复，不加入
System.out.println(set.size()); // 1

set.contains("a");             // O(1)

💡 Set 去重的关键：元素必须正确实现 equals() + hashCode()！

5. Queue & Deque：队列与双端队列 ​

java
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);              // 入队
queue.offer(2);
Integer head = queue.poll(); // 出队（队头）

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);               // 入栈
stack.push(2);
Integer top = stack.pop();   // 出栈

PriorityQueue<Integer> pq = new PriorityQueue<>();   // 默认小顶堆
pq.offer(3); pq.offer(1); pq.offer(2);
while (!pq.isEmpty()) System.out.println(pq.poll());  // 1 2 3

💡 Stack 类已过时，用 ArrayDeque 当栈用！

6. Map：键值对 ​

Map 实现对比

实现类底层特点
HashMap ⭐数组+链表+红黑树无序，O(1)，最常用
LinkedHashMap同上 + 双向链表按插入顺序
TreeMap红黑树按 key 自动排序 O(log n)
Hashtable数组+链表线程安全（已过时，用 ConcurrentHashMap）

常用操作 ​

java
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 3);
map.put("apple", 10);                 // 覆盖

map.get("apple");                      // 10
map.containsKey("apple");              // true
map.containsValue(3);
map.size();
map.remove("banana");

// JDK 8+ 增强方法
map.getOrDefault("cherry", 0);
map.putIfAbsent("apple", 999);         // 已存在不覆盖
map.computeIfAbsent("cherry", k -> 0);
map.merge("apple", 1, Integer::sum);   // 累加

// 遍历
for (Map.Entry<String, Integer> e : map.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}
map.forEach((k, v) -> System.out.println(k + " -> " + v));

map.keySet();
map.values();

// JDK 9+ 不可变 Map
Map.of("a", 1, "b", 2);

HashMap 内部结构（高频面试） ​

  • JDK 8 之前：数组 + 链表
  • JDK 8 之后：数组 + 链表 + 红黑树（链表长度 ≥ 8 时转红黑树）
  • 默认初始容量 16，加载因子 0.75
  • key 用 hashCode() 算桶位置，用 equals() 在桶内比较

7. 集合选型指南 ​

需要 key-value? 
├─ 是 → Map
│  ├─ 要排序 → TreeMap
│  ├─ 要保留插入顺序 → LinkedHashMap
│  └─ 默认 → HashMap ⭐
│
└─ 否 → Collection
   ├─ 要唯一? 
   │  ├─ 是 → Set
   │  │  ├─ 要排序 → TreeSet
   │  │  ├─ 要保留插入顺序 → LinkedHashSet
   │  │  └─ 默认 → HashSet ⭐
   │  └─ 否 → List
   │      ├─ 频繁随机访问 → ArrayList ⭐
   │      └─ 频繁头尾增删 → LinkedList / ArrayDeque
   └─ 要队列语义? 
      ├─ FIFO → ArrayDeque (作 Queue)
      ├─ LIFO → ArrayDeque (作 Stack)
      └─ 优先级 → PriorityQueue

8. Iterator 与并发修改异常 ​

java
List<String> list = new ArrayList<>(List.of("a", "b", "c"));

// ❌ 边遍历边删除（ConcurrentModificationException）
for (String s : list) {
    if (s.equals("b")) list.remove(s);    // 抛异常！
}

// ✅ 用 Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("b")) it.remove();      // 安全
}

// ✅ JDK 8+
list.removeIf(s -> s.equals("b"));

9. 实战练习 ​

文件内容
ListDemo.javaList 全部操作 + 性能对比
SetDemo.javaSet 三大实现去重 + 排序
MapDemo.javaMap 全部操作 + 三大实现对比
WordCount.java用 Map 实现词频统计
StudentManager.java综合：学生管理系统

10. 浏览器演示 ​

打开 demo.html：

  • 集合操作可视化
  • ArrayList vs LinkedList 性能对比
  • HashMap 内部结构动画

11. 面试可能会问什么？ ​

Q1: ArrayList 和 LinkedList 区别？ ​

维度ArrayListLinkedList
底层动态数组双向链表
随机访问O(1)O(n)
头尾增删头 O(n) / 尾 O(1)O(1)
中间增删O(n)O(n)（找位置）
内存紧凑每节点带指针

结论：90% 用 ArrayList。

Q2: HashMap 底层数据结构？ ​

  • JDK 8+：数组 + 链表 + 红黑树
  • 链表长度 ≥ 8 → 转红黑树（树化阈值）
  • 红黑树节点 ≤ 6 → 退回链表（去树化阈值）
  • 默认容量 16，扩容阈值 16 × 0.75 = 12

Q3: HashMap 为什么扩容总是 2 倍？ ​

为了让 (n - 1) & hash（按位与）等价于取模，速度更快。

Q4: HashMap 是线程安全的吗？ ​

不是。多线程下用：

  • Collections.synchronizedMap(map)（粗暴加锁）
  • ConcurrentHashMap ⭐（推荐，分段锁/CAS）

Q5: 重写 equals 为什么要重写 hashCode？ ​

HashMap/HashSet 先按 hashCode 找桶，再用 equals 比较。如果两对象 equals 为 true 但 hashCode 不同，会被存到不同桶，去重失效。

Q6: Iterator 与 for-each 区别？ ​

for-each 底层就是 Iterator。区别：

  • for-each 不能调 remove
  • Iterator 可以调 it.remove()

Q7: ArrayList 默认初始容量？怎么扩容？ ​

  • 初始容量 10（JDK 8）
  • 扩容：旧容量 + 旧容量 / 2 = 1.5 倍

🎁 本章小结 ​

✅ List：有序可重复  | ArrayList ⭐  / LinkedList
✅ Set：唯一不重复    | HashSet ⭐    / TreeSet / LinkedHashSet
✅ Queue：FIFO/LIFO  | ArrayDeque   / PriorityQueue
✅ Map：键值对        | HashMap ⭐   / TreeMap / LinkedHashMap
✅ 重写 equals 必重写 hashCode
✅ 边遍历边删用 Iterator.remove() 或 removeIf

🔗 导航 ​