03-集合与泛型

阶段：入门篇 ｜ 建议时长：5 天 ｜ 前置：02-面向对象与核心类.md

学习目标

• 能默画集合框架总图：Collection（List/Set/Queue）与 Map 两棵树及常用实现类。
• 能说清 ArrayList 扩容机制（1.5 倍）与 ArrayList vs LinkedList 的选型结论。
• 能完整讲述 HashMap 的 put 流程、扩容、树化条件及 1.7 vs 1.8 差异。
• 掌握泛型通配符与 PECS 原则，能解释类型擦除的表现。
• 会用 Iterator 正确遍历删除，理解 fail-fast 机制。

核心知识点

集合框架总图

面试官想听：你脑中有全局地图，能按「是否有序、是否可重复、是否线程安全」给常用类定位。

Iterable
 └─ Collection
     ├─ List（有序可重复）: ArrayList / LinkedList / Vector(旧)
     ├─ Set（不重复）:      HashSet / LinkedHashSet / TreeSet
     └─ Queue（队列）:      LinkedList / ArrayDeque / PriorityQueue
Map（键值对，不属于 Collection）
     ├─ HashMap / LinkedHashMap（保持插入序）/ TreeMap（按 key 排序）
     └─ Hashtable(旧) / ConcurrentHashMap（并发）

• 存取定位口诀：要「按下标/顺序」用 List；要「去重」用 Set；要「key 查 value」用 Map；要「排队/FIFO」用 Queue。
• 线程安全：Vector 的方法都用 synchronized 修饰（所以”下列集合中线程安全的是”这类题选它）、Hashtable 同理；而 ArrayList/HashMap/LinkedList 等常用实现类都不是线程安全的（并发场景见 ConcurrentHashMap、CopyOnWriteArrayList）。注意 Vector/Hashtable 是早期遗留类，全表加锁性能差，现代并发场景不推荐，只是面试会考”谁线程安全”。

ArrayList 扩容机制

面试官想听：说出默认容量 10、1.5 倍扩容、数组拷贝成本，以及为什么最好预估容量。

• 底层是 Object[] elementData；new ArrayList<>() 初始为空数组，首次 add 时才分配容量 10。
• 扩容：容量不足时 newCapacity = oldCapacity + (oldCapacity >> 1)，即 1.5 倍，通过 Arrays.copyOf 把旧数组复制到新数组，O(n)。
• 大数据量场景用 new ArrayList<>(expectedSize) 指定初始容量，避免反复扩容拷贝。
• 中间插入/删除需要 System.arraycopy 移动元素，平均 O(n)；随机访问 get(i) 直接下标寻址 O(1)。

ArrayList vs LinkedList

面试官想听：别只背「一个数组一个链表」，重点在随机访问性能、内存局部性和 CPU 缓存友好度。

• 注意：LinkedList 的「增删快」仅指头尾；即使删中间找到了节点，ArrayList 批量移动在 CPU 缓存下常常更快。

Set 三兄弟

• HashSet：基于 HashMap（元素作 key，共享 PRESENT 占位对象）；无序；add 依赖 hashCode + equals 去重。
• LinkedHashSet：HashSet + 双向链表记录插入顺序，遍历按插入序，稍慢于 HashSet。
• TreeSet：基于 TreeMap（红黑树），按 key 自然序或 Comparator 排序，增删查 O(log n)；元素必须可比较（实现 Comparable 或传入比较器）。
• 去重自定义类必须同时重写 equals 和 hashCode，否则去重失效。

HashMap 用法与底层入门

面试官想听：put 流程讲得完整、有条理，能带出树化、扩容、容量为 2 的幂三个子问题。

• 结构（Java 8+）：数组 + 链表 + 红黑树；数组每个槽位叫桶（bucket）。
• put 流程：计算 hash(key)（key 的 hashCode 高 16 位异或低 16 位，让散列更均匀）→ (n-1) & hash 定位桶 → 空桶直接放入 → 链表则尾插并逐个 equals 判重 → 链表长度 ≥ 8 且数组长度 ≥ 64 时树化为红黑树（查找 O(n) 降为 O(log n)）；树节点数 ≤ 6 退化为链表 → 插入后若 size > capacity * 0.75 触发扩容。
• 扩容：容量翻倍（2 倍），重新分配元素；Java 8 中元素新位置要么在原下标 j，要么在 j + oldCap（高位 bit 决定），无需重新计算 hash。
• 默认容量 16，负载因子 0.75，容量始终是 2 的幂。

为什么容量必须是 2 的幂？ 使 (n-1) & hash 等价于取模但更快（位运算），且 n-1 的二进制全 1 让散列分布均匀。

1.7 vs 1.8 的区别：

• 1.7：数组 + 链表，头插法；扩容后可能环形链表导致死循环（多线程下）；1.8 改尾插法避免。
• 1.8 引入红黑树优化长链表；hash 计算从 4 次位运算+5 次异或简化为 1 次异或。
• 1.7 先扩容后插入，1.8 先插入后扩容。

LinkedHashMap：插入序与 LRU

• LinkedHashMap = HashMap + 双向链表维护顺序，遍历顺序可控：
  • new LinkedHashMap<>() 默认 accessOrder=false，按插入顺序遍历——想要「遍历 HashMap 时按插入序输出」，答案就是它。
  • new LinkedHashMap<>(16, 0.75f, true) 传 accessOrder=true 后按访问顺序：每次 get/put 都会把该节点移到链表尾，最久未访问的排在链表头——这正是 LRU 的实现基础。
• 配套钩子 removeEldestEntry(eldest)：默认返回 false；重写为 return size() > capacity; 后，每次插入新节点都会检查链表头（最久未用）是否该淘汰，一行代码就是一个 LRU 缓存（LeetCode 146 的常见解法）。想手写不依赖 LinkedHashMap 的版本，见《03-算法刷题路线》的 LRU 模板。
• 注意区别：accessOrder=false 时淘汰的是最早插入的（FIFO），不是最久未用的——用错了语义就变成 FIFO 缓存。

TreeMap 与 Comparator

• TreeMap 按 key 排序（红黑树实现），支持 firstKey()、ceilingKey() 等导航方法。
• 排序两种方式：元素实现 Comparable（自然序）或构造时传 Comparator（定制序）。

list.sort(Comparator.comparing(User::getAge)
                    .thenComparing(User::getName)     // 多字段
                    .reversed());                      // 降序

Queue / Deque / PriorityQueue

• Queue：offer 入队、poll 出队、peek 看队头（抛异常版本为 add/remove/element）。
• Deque 双端队列：addFirst/addLast/pollFirst/pollLast；用 ArrayDeque 代替 Stack 和 LinkedList 做栈/队列。
• PriorityQueue 小顶堆：poll 总是取最小元素（可传 Comparator 改大顶堆 Comparator.reverseOrder()），TopN 场景常用。

Iterator 与 fail-fast

面试官想听：能解释 ConcurrentModificationException 的检测原理（modCount），并给出至少两种安全删除方案。

• 遍历统一入口：Iterator it = list.iterator(); while (it.hasNext()) { it.next(); }。
• fail-fast（快速失败）：集合内部维护 modCount 修改计数，迭代器创建时记录快照，每次 next() 校验 modCount 是否被改变，被改则抛 ConcurrentModificationException——这是「提前暴露 bug」的设计，不保证并发安全。

遍历时删除的正确姿势

面试官想听：一开口就给出正确答案而不是 list.remove()。

// 方式 1：迭代器的 remove（推荐，唯一会同步 modCount 的删除方式）
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("a")) it.remove();
}
// 方式 2：removeIf（Java 8+，底层也是迭代器删除）
list.removeIf(s -> s.startsWith("a"));
// 方式 3：普通 for 按 i-- 倒序删除（下标法可行但易错）

• foreach 循环里直接 list.remove(x) 必抛 ConcurrentModificationException。
• 并发场景改用 CopyOnWriteArrayList 或并发容器（文件 6）。

Collections / Arrays 工具与不可变集合

• Collections：sort、reverse、shuffle、max/min、unmodifiableList（不可变视图）、synchronizedList（同步包装）。
• Arrays：asList 返回定长列表（底层数组引用，不支持 add/remove，修改元素会影响原数组）。
• Java 9+ List.of/Set.of/Map.of 创建真正不可变集合：不允许 null、任何修改抛 UnsupportedOperationException，适合常量表。

subList 是视图，不是拷贝

• list.subList(1, 3) 返回的是原列表的视图（view），不是新列表：改视图即改原表（sub.set(0, x) 会改到原 list；sub.remove(...) 也会连带删原表元素）。
• 反向也成立：原表结构性修改后，视图立即失效，再访问它抛 ConcurrentModificationException。
• 踩坑高发区：把 subList 结果当独立列表返回或缓存——调用方一改就污染原表。
• 要副本必须显式拷贝：new ArrayList<>(list.subList(1, 3))。
• 同类视图还有：Arrays.asList（定长视图）、keySet/values/entrySet（Map 的视图）、Collections.unmodifiableList（只读视图）——判断标准都是”它是原容器的窗口，还是独立存储”。

泛型

• 泛型把类型检查提前到编译期：List<String> list = new ArrayList<>();（菱形推断）。
• 泛型类 class Box<T>、泛型方法 <T> T pick(T... a)、泛型接口，命名习惯 T/E/K/V/R。

通配符与 PECS

面试官想听：知道 ? extends 与 ? super 各限制什么，并说出 Producer Extends, Consumer Super。

List<? extends Number> producer = List.of(1, 2.0); // 只能读出 Number，不能写入
List<? super Integer> consumer = new ArrayList<Number>(); // 只能写入 Integer，读出为 Object
static void copy(List<? extends T> src, List<? super T> dst) // JDK Collections.copy 原型

• PECS：参数是生产者（只读出来用）用 extends；是消费者（要往里写）用 super。
• List<String> 与 List<Object> 没有任何继承关系，没有通配符就无法互相赋值。

类型擦除

面试官想听：泛型只存在于编译期，运行时全是原始类型；知道后果比背定义重要。

• 编译后 List<String> 与 List<Integer> 都是 List，T 被替换为上边界（无边界则为 Object），调用处由编译器插入强制转换。
• 后果：不能 new T()、不能 T.class、不能 new T[]、不能对泛型类型用 instanceof；运行时获取泛型参数需借助 getGenericSuperclass 等反射手段（框架常用）。
• 验证：new ArrayList<String>().getClass() == new ArrayList<Integer>().getClass() 为 true。

动手实践

任务 1：Map 统计词频

Map<String, Integer> count = new HashMap<>();
for (String w : words) {
    count.merge(w, 1, Integer::sum);   // 等价于 get+判空+put
}
count.entrySet().stream()
     .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
     .limit(3).forEach(e -> System.out.println(e.getKey() + "=" + e.getValue()));

• 验收标准：对一段中文/英文文本输出 Top3 词频；使用 merge 或 getOrDefault 而不是 if-else 嵌套；说出 TreeMap 方案的另一种写法。

任务 2：Comparator 多字段排序

• 要求：定义 Student(id, name, score, age)，实现先按 score 降序、同分按 age 升序、再同按 name 字典序。
• 验收标准：仅用 Comparator.comparing().thenComparing() 链式实现，不写 compare 方法；对构造的同分数据验证次序正确。

任务 3：模拟购物车

• 要求：Cart 内部用 LinkedHashMap<String, CartItem>（key=商品编号），支持添加（数量累加）、修改数量、删除、计算总价（BigDecimal）、按加入顺序打印。
• 验收标准：重复添加同一商品时数量合并而不是重复条目；总价用 BigDecimal 精确到 2 位；演示一次 List.of/Map.of 不可变集合在常量商品目录中的应用。

高频面试题

Q：ArrayList 和 LinkedList 的区别？怎么选？⭐

• ArrayList 动态数组：get/set O(1)；尾部均摊 O(1)；中间插删 O(n)；内存连续、缓存友好。
• LinkedList 双向链表：头尾插删 O(1)；随机访问 O(n)；每个节点多两个引用，内存开销大。
• 结论：绝大多数场景选 ArrayList；做队列/双端队列优先 ArrayDeque。LinkedList 很少是正确答案。

Q：讲一下 HashMap 的 put 流程。⭐

• 计算 hash（高 16 位异或低 16 位），(n-1) & hash 定位桶。
• 空桶直接新建节点；是链表则尾插并 equals 判重替换；是红黑树则按树插入。
• 链表长度达 8 且数组容量 ≥ 64 时树化，≤ 6 退化回链表。
• 插入后 size 超过 容量 × 0.75 触发 2 倍扩容并 rehash（新位置为原下标或原下标+旧容量）。

Q：为什么 HashMap 容量是 2 的幂？⭐

• 使 (n-1) & hash 与 hash % n 等价但只需一次位运算，性能更高。
• n-1 二进制为连续 1，与运算能让 hash 的每一位都参与散列，分布更均匀，减少冲突。
• 指定初始容量为非 2 的幂时，tableSizeFor 会向上取整到最近的 2 的幂。

Q：HashMap 1.7 和 1.8 有什么区别？⭐

• 结构：1.7 数组+链表；1.8 数组+链表+红黑树（长链表查找 O(n)→O(log n)）。
• 插入：1.7 头插，多线程扩容可能形成环形链表死循环；1.8 改尾插。
• 扩容时机与 hash 计算也做了简化优化；1.8 rehash 时只需判断新增高位 bit，不用重新算 hash。

Q：HashSet 是如何保证元素不重复的？⭐

• 底层就是 HashMap，元素作为 key，value 是共享的 PRESENT 占位对象。
• add 时先比较 hashCode 定位，再用 equals 判等，两者都「相同」才认定重复。
• 所以自定义类放入 HashSet 必须重写 equals 和 hashCode，且两个方法逻辑要一致。

Q：什么是 fail-fast？怎么在遍历时安全删除元素？⭐

• fail-fast：迭代时检测到集合结构性被修改（modCount 变化）立即抛 ConcurrentModificationException，防止不确定行为。
• 单线程安全删除：用 iterator.remove() 或 Java 8 的 removeIf。
• foreach 中直接 remove 是错误姿势；多线程环境应使用并发容器或加锁。

Q：什么是 PECS 原则？

• Producer Extends：只读取数据的生产者参数用 ? extends T；Consumer Super：只写入数据的消费者参数用 ? super T。
• Collections.copy(List<? super T> dst, List<? extends T> src) 是标准范例。
• 目的：在保证类型安全的前提下让 API 接受尽可能宽的参数类型。

Q：类型擦除是什么？带来哪些限制？

• 泛型信息只在编译期用于类型检查，编译后擦除为上边界（默认 Object），运行时插入强转。
• 限制：运行时无法 new T()、取 T.class、instanceof 泛型类型。
• 框架通过反射的 getGenericXXX 接口在字节码签名（Signature）里仍能拿到泛型声明。

推荐资料