LESSON 05 · 集合框架

集合框架
List / Set / Map 一次打通

这节我们啃 Java 后端写代码天天用、面试年年考的部分：集合框架。重点是 HashMap 底层原理——大厂一面 80% 会问，是整个 Java 后端求职最值得花时间的一个知识点。

学完这节：你能说清 ArrayList 怎么扩容、HashSet 怎么去重、HashMap.put(k, v) 底层走过的每一步、为什么 key 必须正确实现 equals/hashCode。
1

为什么需要集合？数组的 3 个痛点

💡 动机：数组太死板，业务天天要"动态容器"

上节我们学了数组，但它有 3 个绕不开的问题：

痛点数组集合的解法
长度固定 创建时定死，不能改 ArrayList 自动扩容
只能存同类型 Object[] 也行但不优雅 泛型 List<String> 强类型
没有现成 API add/remove/contains 全得自己写 开箱即用的几十个方法

所以 Java 设计了集合框架（Collection Framework）——一组接口和实现类，让"存一组数据"这件事变得简单。

小白记法：数组 = 固定车位的停车场；集合 = 智能停车场（车多了自动扩、有编号系统、有保安巡逻）。
2

集合的"族谱"：三大接口全景

💡 动机：先把关系理清，再学单个就不乱

Java 集合框架分两大族：Collection（存单个元素）和 Map（存键值对）。

Collection<E>          // 顶层接口，存"一组东西"
├── List<E>        // 有序、可重复（"按位置"存）
│   ├── ArrayList     // 数组实现，查询快
│   └── LinkedList    // 链表实现，增删快
├── Set<E>         // 无序、不可重复（"数学集合"）
│   ├── HashSet        // 哈希实现，去重
│   ├── LinkedHashSet  // 哈希+链表，保留插入顺序
│   └── TreeSet        // 红黑树，自动排序
└── Queue<E>       // 队列，FIFO（Lesson 10 并发详讲）

Map<K, V>              // 单独一枝，存"键值对"
├── HashMap            // 哈希表，⭐⭐ 大厂 80% 问这个
├── LinkedHashMap      // 哈希+链表，保留插入顺序
├── TreeMap            // 红黑树，按 key 排序
└── ConcurrentHashMap  // 线程安全版（Lesson 10）
记忆口诀：
  • List = "列" → 有顺序、像数组，可以重复
  • Set = "集" → 数学集合，自动去重
  • Map = "映射" → key → value，像查字典
3

List 实战：ArrayList vs LinkedList

💡 动机：99% 的 List 场景，ArrayList 就够；什么时候用 LinkedList？

两种 List 内部实现完全不同，性能差异巨大：

对比ArrayListLinkedList
内部结构 数组 双向链表
查 get(i) ⭐ O(1) 数组按下标 O(n) 链表遍历
增 add() 末尾 O(1)，中间 O(n) ⭐ 头/中 O(1)
删 remove() 末尾 O(1)，中间 O(n) ⭐ 头/中 O(1)
内存占用 ⭐ 紧凑（连续数组） 每个节点多 2 个指针

ArrayList 扩容机制（⭐ 面试常问）

ArrayList 底层是 Object[]，满了要扩容——扩容是新建一个更大的数组，把旧的复制过去。

// JDK 8+ 的扩容规则
// 初始容量 10，不够时扩容为原来的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);  // >> 1 = 除以 2

// 例：10 → 15 → 22 → 33 → 49 → ...
实战建议：
  • 知道大概长度时，预先指定容量：new ArrayList<>(1000) 避免反复扩容
  • 10 万级别的 List 操作，ArrayList 几乎都是首选
  • LinkedList几乎不用——除非明确的"频繁在头部插入/删除"场景
4

Set 实战：HashSet 的去重原理 ⭐ 面试常问

💡 动机：Set 的核心是"自动去重"，怎么做到的？

HashSet 底层其实就是 HashMap，存的元素是 key，value 是一个固定的无意义对象。

// HashSet 源码（简化版）
public class HashSet<E> {
    private HashMap<E, Object> map = new HashMap<>();
    private static final Object PRESENT = new Object();  // 所有 value 都是这个

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;  // put 成功 = key 不存在 = 添加成功
    }
}

所以 Set 去重的核心 = HashMap 的 key 不重复 = hashCode + equals 共同决定。

⭐ 铁律（再强调一次，Lesson 03 提过）：
  1. 两个对象 equals 相等 → hashCode 必须相等
  2. 两个对象 hashCode 相等 → equals 不一定相等（哈希冲突）
  3. 违反这两条 → 放进 Set/Map 的对象会"丢"或"重复"
// 反例：自定义 User 没重写 hashCode/equals
User u1 = new User("张三");
User u2 = new User("张三");

Set<User> set = new HashSet<>();
set.add(u1);
set.add(u2);
System.out.println(set.size());  // → 2（应该 1！重复了）

// 修法：跟 Lesson 03 一样，IDEA 自动生成 hashCode + equals

点下面按钮，体会 ArrayList（保留重复）vs HashSet（自动去重）的区别：

ArrayList 保留重复
（还没添加）
0 个元素
HashSet 自动去重
（还没添加）
0 个元素
5

Map 实战：HashMap 的 4 个基本操作

💡 动机：HashMap 是 Java 后端写代码的"地基"

4 个方法搞定 80% 的 HashMap 用法：

Map<String, Integer> map = new HashMap<>();

// 1. 增 / 改：put（key 不存在 = 新增；key 存在 = 覆盖 value）
map.put("苹果", 3);
map.put("香蕉", 5);
map.put("苹果", 10);   // 覆盖原来的 3

// 2. 查：get（key 不存在返回 null）
System.out.println(map.get("苹果"));    // → 10
System.out.println(map.get("西瓜"));    // → null

// 3. 删：remove
map.remove("香蕉");

// 4. 遍历：3 种方式
// 方式 1：遍历 key
for (String key : map.keySet()) {
    System.out.println(key + " = " + map.get(key));
}

// 方式 2：遍历 entry（最常用）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

// 方式 3：forEach + lambda（最简洁）
map.forEach((k, v) -> System.out.println(k + " = " + v));
实战建议：
  • 查不到时想给默认值？用 getOrDefault(key, 0)
  • key 不存在才放？用 putIfAbsent(key, value)
  • 用 containsKey(key) 判断是否存在（比 get(key) != null 更明确）
6

HashMap 底层原理 ⭐⭐ 面试必问

💡 动机：大厂一面 80% 问，看你是不是"用过"还是"懂"

HashMap 内部结构：数组 + 链表 + 红黑树（JDK 8+）。三个组件缺一不可。

put(k, v) 流程（⭐⭐⭐ 必背）

// 简化版 put 源码
public V put(K key, V value) {
    // 1. 计算 key 的 hash（不是直接用 hashCode()，会再扰动一次）
    int hash = hash(key);
    // 2. 算出在数组里的下标
    int i = (table.length - 1) & hash;   // 位运算取模
    // 3. 看那个位置：
    for (Node<K,V> e = table[i]; e != null; e = e.next) {
        if (e.hash == hash && e.key.equals(key)) {
            V oldValue = e.value;
            e.value = value;        // 4a. key 存在 → 覆盖 value
            return oldValue;
        }
    }
    // 4b. key 不存在 → 新建节点加到链表
    addNode(hash, key, value, i);
    return null;
}

3 个关键机制

机制做什么为什么
hash 扰动 hash 值再 ^ (hash >>> 16)，高 16 位和低 16 位做异或 让 hashCode 分布更均匀，减少冲突
数组扩容 当 size > threshold（容量 × 0.75）时，容量 × 2 避免链表过长影响查询性能
链表 → 红黑树 当某个链表长度 > 8 且数组长度 > 64，链表转红黑树 链表 O(n) 变成红黑树 O(log n)

⭐ 一句话总结 HashMap

"HashMap = 数组找桶 + 链表/红黑树处理冲突 + 哈希均匀分布"

面试答出这一句，80% 算过。剩下的 20% 看追问深度。

常见追问（按频率）

  1. 为什么容量是 2 的幂？ → (n - 1) & hash 位运算代替 % 取模，要求 n 是 2 的幂
  2. 为什么负载因子 0.75？ → 太高容易冲突，太低浪费空间，0.75 是统计+经验值
  3. 为什么是 8 转红黑树？ → 泊松分布算出链表长度 ≥ 8 的概率只有 0.00000006，是极端情况
  4. key 可以为 null 吗？ → 可以，但只能有一个（null 被放在下标 0）
  5. HashMap 线程安全吗？ → 不安全，并发场景用 ConcurrentHashMap（Lesson 10 详讲）
7

选型速查表 + 常见面试题

💡 动机：记住这个表，能解决 90% 的选型问题
场景选什么理由
要按顺序存、可重复ArrayList查询快、99% 场景够用
要自动去重HashSetO(1) 查找、底层是 HashMap
要按插入顺序遍历LinkedHashSet/Map多了链表记录顺序
要自动按 key 排序TreeSet/TreeMap红黑树，O(log n)
键值对映射、追求性能HashMap⭐⭐ 99% 场景
并发场景ConcurrentHashMap分段锁 / CAS，线程安全
⭐ 经典面试题（背下来）：
  1. HashMap 和 Hashtable 区别？→ Hashtable 古老、synchronized 锁全表；HashMap 新、快、非线程安全
  2. HashMap 和 ConcurrentHashMap 区别？→ ConcurrentHashMap 用 CAS + synchronized 单桶锁，并发性能高 10 倍
  3. 为什么 HashMap 不直接用 hashCode()？→ hashCode() 高位可能全是 0（Object 类）或分布不均，要扰动
  4. 为什么 ConcurrentHashMap 不允许 null key/value？→ 多线程下 null 有歧义（是 put 进去的没找到？）

你的作业（分步走）

  1. ArrayList 扩容验证：写代码 new ArrayList<>() 不指定容量，循环 add 1000 个元素，打日志记录每次容量变化（10 → 15 → 22 → 33...），证明 1.5 倍扩容
  2. Set 去重验证：写个 User 类（只有 name 字段），先不重写 equals/hashCode，放进 HashSet 看 size；然后用 IDEA 自动生成两个方法，再看 size——对比两次结果
  3. Map 4 个基本操作：写个 Map<String, Integer>，用 put/get/remove/containsKey 完成"购物车添加商品 → 改数量 → 删除 → 判断是否存在"流程
  4. HashMap 容量预分配：写代码对比 new HashMap<>() 和 new HashMap<>(1000000) 添加 50 万元素的耗时（用 System.nanoTime()），体会"预分配"的好处
  5. 说出 HashMap put 流程：不看任何资料，凭记忆写下 put 的 5 个步骤（hash → 下标 → 查 key → 覆盖/新增 → 扩容判断），贴给我看哪步漏了