Appearance
集合框架
程序员的第一道坎：数组不够用了怎么办？ 🚀
🎯 场景：为什么需要集合？
┌─────────────────────────────────────────────────────────────────┐
│ 数组的局限性 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ // 数组长度固定，不能动态增长 │
│ String[] users = new String[3]; │
│ users[0] = "张三"; │
│ users[1] = "李四"; │
│ users[2] = "王五"; │
│ // users[3] = "赵六"; // 报错！数组越界 │
│ │
│ // 数组不知道有多少元素 │
│ for (int i = 0; i < ???; i++) { ... } │
│ │
│ 数组：不支持动态增删，不知道有多少元素，操作麻烦 │
│ │
└─────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────┐
│ 集合来了！ │
├─────────────────────────────────────────────────────────────────┤
│ │
│ // ArrayList - 动态数组，想加多少加多少 │
│ List<String> users = new ArrayList<>(); │
│ users.add("张三"); │
│ users.add("李四"); │
│ users.add("王五"); │
│ users.add("赵六"); // 没问题！自动扩容 │
│ │
│ // size() 知道有多少元素 │
│ for (int i = 0; i < users.size(); i++) { ... } │
│ │
│ 集合：动态扩容、自动管理长度、API 丰富 │
│ │
└─────────────────────────────────────────────────────────────────┘💡 实战场景：
- 用户的购物车商品列表 → ArrayList
- 用户的订单不能重复 → HashSet
- 用户 ID 和订单 ID 映射 → HashMap
- 消息队列、任务队列 → Queue
集合框架全览
┌─────────────────────────────────────────────────────────────────────────┐
│ Collection │
│ （集合的根接口） │
│ ┌─────────────────┴─────────────────┐ │
│ │ │ │
│ List Set │
│ （有序、可重复） （无序、不可重复） │
│ │ │ │
│ ┌─────┼─────┐ ┌──────┼──────┐ │
│ │ │ │ │ │ │ │
│ ArrayList LinkedList Vector HashSet TreeSet LinkedHashSet │
│ │
│ ┌─────────────────────────┐ │
│ │ Queue │ │
│ │ （队列，先进先出） │ │
│ └────────────┬────────────┘ │
│ │ │
│ LinkedList │
│ PriorityQueue │
└─────────────────┼───────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────────────┐
│ Map │
│ （键值对） │
│ ┌─────────────────┴─────────────────┐ │
│ │ │ │
│ HashMap TreeMap │
│ │ │ │
│ LinkedHashMap （有序的Map） │
│ │
│ Hashtable（已过时） │
└─────────────────────────────────────────────────────────────────────────┘List 集合
ArrayList vs LinkedList vs Vector
💡 实战场景：选哪个？
┌─────────────────────────────────────────────────────────────────┐
│ List 实现类选择指南 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 📦 ArrayList：大多数场景的首选 │
│ 场景：遍历商品列表、查询用户订单、展示帖子列表 │
│ 理由：随机访问 O(1)，日常开发 90% 场景都是查询多 │
│ │
│ 🔗 LinkedList：头尾操作频繁时 │
│ 场景：实现队列、栈、任务调度系统 │
│ 理由：头尾插入/删除 O(1)，但随机访问慢 │
│ │
│ 🛡️ Vector：遗留代码或需要线程安全 │
│ 场景：老项目维护、或者 ConcurrentLinkedQueue 也不够用时 │
│ 理由：所有方法 synchronized，现在很少用了 │
│ │
└─────────────────────────────────────────────────────────────────┘| 特性 | ArrayList | LinkedList | Vector |
|---|---|---|---|
| 底层实现 | 动态数组 | 双向链表 | 动态数组 |
| 随机访问 | O(1) ⭐ | O(n) | O(1) |
| 头部插入/删除 | O(n) | O(1) ⭐ | O(n) |
| 尾部插入/删除 | O(1) 均摊 | O(1) | O(1) |
| 线程安全 | 否 | 否 | 是（同步） |
| 适用场景 | 随机访问多 | 插入/删除多 | 需要线程安全 |
ArrayList 核心原理
java
// ArrayList 底层是 Object[]数组
transient Object[] elementData;
// 创建时默认容量
private static final int DEFAULT_CAPACITY = 10;
// 添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 扩容检查
elementData[size++] = e;
return true;
}
// 扩容机制 - 发现代JDK会自动计算
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新容量 = 旧容量 + 旧容量/2 (1.5倍)
int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity);
}💡 面试高频点：ArrayList 扩容机制？
初始容量 0 → 第一次 add → 容量 10
容量不够时 → 扩容 1.5 倍 → 拷贝原数组Vector vs ArrayList（历史面试题）
java
// Vector 所有方法都 synchronized，线程安全但性能差
// 不推荐使用，推荐 CopyOnWriteArrayList
// Java 5+ 推荐替代方案
List<String> list = new CopyOnWriteArrayList<>(); // 读多写少
List<String> list = Collections.synchronizedList(new ArrayList<>()); // 写多Set 集合
HashSet vs TreeSet vs LinkedHashSet
💡 实战场景：去重选哪个？
┌─────────────────────────────────────────────────────────────────┐
│ Set 实现类选择指南 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 🗑️ HashSet：最常用的去重方案 │
│ 场景：用户标签、商品分类、已读消息标记 │
│ 理由：O(1) 查找最快，不在乎顺序 │
│ │
│ 📊 TreeSet：需要排序时 │
│ 场景：排行榜、优先级任务调度、历史记录排序 │
│ 理由：O(log n) 查找，自动排序 │
│ │
│ 📝 LinkedHashSet：需要保持插入顺序 │
│ 场景：用户浏览历史、最近浏览记录 │
│ 理由：保持 FIFO，查找也是 O(1) │
│ │
└─────────────────────────────────────────────────────────────────┘| 特性 | HashSet | TreeSet | LinkedHashSet |
|---|---|---|---|
| 底层实现 | HashMap | TreeMap | LinkedHashMap |
| 元素顺序 | 无序 | 有序（自然/比较器） | 插入顺序 |
| 时间复杂度 | O(1) | O(log n) | O(1) |
| null 元素 | 允许一个 | 不允许 | 允许一个 |
| 适用场景 | 去重、无顺序要求 | 排序、去重 | 去重、保持插入顺序 |
HashSet 核心原理
java
// HashSet 底层是 HashMap，value 用同一个 Object 填充
private transient HashMap<E, Object> map;
// 添加元素
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
// 内部用 PRESENT（一个固定对象）作为所有 value
private static final Object PRESENT = new Object();HashSet 去重原理：
┌──────────────────────────────────────────────────────┐
│ HashSet 去重流程 │
├──────────────────────────────────────────────────────┤
│ │
│ 1. 计算元素的 hashCode() │
│ ↓ │
│ 2. 根据 hashCode() 确定 bucket 位置 │
│ ↓ │
│ 3. 用 equals() 比较是否已存在 │
│ ↓ │
│ 4. 若已存在 → 替换；若不存在 → 添加 │
│ │
└──────────────────────────────────────────────────────┘TreeSet 排序规则
java
// 方式1：元素实现 Comparable 接口
public class Person implements Comparable<Person> {
private String name;
private int age;
@Override
public int compareTo(Person o) {
// 按年龄升序
return this.age - o.age;
}
}
// 方式2：创建 TreeSet 时传入 Comparator
TreeSet<Person> set = new TreeSet<>(new Comparator<Person>() {
@Override
public int compare(Person p1, Person p2) {
return p1.getName().compareTo(p2.getName());
}
});
// Java 8+ 简化
TreeSet<Person> set = new TreeSet<>((p1, p2) ->
p1.getName().compareTo(p2.getName())
);Map 集合
HashMap vs Hashtable vs ConcurrentHashMap
| 特性 | HashMap | Hashtable | ConcurrentHashMap |
|---|---|---|---|
| 线程安全 | 否 | 是（全表锁） | 是（分段锁） |
| 性能 | 高 | 低 | 较高 |
| null key/value | 都允许 | 都不允许 | key 不允许，value 允许 |
| 迭代安全性 | 否 | 否 | 是（快照） |
| 适用场景 | 单线程 | 不推荐 | 多线程并发 |
HashMap 核心原理（JDK 8+）
java
// Node 数组 + 链表 + 红黑树
transient Node<K, V>[] table;
// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 添加元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 数组为空则扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 计算 index，插入链表或红黑树
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = new Node<>(hash, key, value, null);
else {
// 3. 处理哈希冲突（链表/红黑树）
// ...
}
return null;
}💡 面试高频点：HashMap 的哈希冲突如何解决？
┌────────────────────────────────────────────────────────┐
│ 哈希冲突解决方法 │
├────────────────────────────────────────────────────────┤
│ │
│ 1. 开放地址法（线性探测/二次探测） │
│ │
│ 2. 再哈希法（多个哈希函数） │
│ │
│ 3. 链地址法（HashMap 采用）⭐ │
│ • 链表长度 < 8 → 链表 │
│ • 链表长度 >= 8 → 红黑树（查询 O(log n)） │
│ │
└────────────────────────────────────────────────────────┘ConcurrentHashMap 核心原理
java
// JDK 7：Segment 分段锁
// JDK 8+：CAS + synchronized
// JDK 8+ put 逻辑
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 1. 数组为空则初始化（CAS）
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 2. 当前位置为空，用 CAS 插入
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break;
}
// 3. 当前位置有值，用 synchronized 加锁处理
else {
synchronized (f) {
// 处理链表或红黑树...
}
}
}
return null;
}迭代器与增强for循环
Iterator 的正确使用
java
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
// ❌ 错误：ConcurrentModificationException
for (String item : list) {
if ("b".equals(item)) {
list.remove(item); // 迭代过程中修改集合
}
}
// ✅ 正确方式1：使用迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String item = it.next();
if ("b".equals(item)) {
it.remove(); // 迭代器删除，安全
}
}
// ✅ 正确方式2：removeIf (Java 8+)
list.removeIf("b"::equals);
// ✅ 正确方式3：倒序遍历删除
for (int i = list.size() - 1; i >= 0; i--) {
if ("b".equals(list.get(i))) {
list.remove(i);
}
}💡 面试高频点：为什么会发生 ConcurrentModificationException？
┌─────────────────────────────────────────────────────────┐
│ fail-fast 机制说明 │
├─────────────────────────────────────────────────────────┤
│ │
│ ArrayList 内部维护了一个 modCount（修改次数） │
│ │
│ 迭代器创建时记录 expectedModCount = modCount │
│ │
│ 迭代过程中检测到 modCount != expectedModCount │
│ ↓ │
│ 抛出 ConcurrentModificationException │
│ │
│ 这是 fail-fast 机制，尽快发现并发问题 │
│ │
└─────────────────────────────────────────────────────────┘Collections 工具类
常用方法
java
List<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
// 排序
Collections.sort(list); // [1, 2, 5, 8, 9]
// 反转
Collections.reverse(list); // [9, 8, 5, 2, 1]
// 随机排序（洗牌）
Collections.shuffle(list);
// 二分查找（必须先排序）
int index = Collections.binarySearch(list, 5);
// 最大最小值
int max = Collections.max(list);
int min = Collections.min(list);
// 填充
Collections.fill(list, 0); // 所有元素设为 0
// 交换
Collections.swap(list, 0, 4); // 交换索引 0 和 4
// 统计出现次数
int count = Collections.frequency(list, 5);
// 不可变集合
List<Integer> immutable = Collections.unmodifiableList(list);线程安全集合
┌────────────────────────────────────────────────────────────────┐
│ 线程安全集合一览 │
├────────────────────────────────────────────────────────────────┤
│ │
│ 非线程安全 → 线程安全替代 │
│ ───────────── ───────────────────── │
│ ArrayList → CopyOnWriteArrayList │
│ LinkedList → ConcurrentLinkedQueue │
│ HashSet → CopyOnWriteArraySet │
│ TreeSet → ConcurrentSkipListSet │
│ HashMap → ConcurrentHashMap │
│ TreeMap → ConcurrentSkipListMap │
│ │
└────────────────────────────────────────────────────────────────┘各种并发集合对比
| 集合 | 适用场景 | 特点 |
|---|---|---|
| ConcurrentHashMap | 高并发读写 | 分段锁/CAS，O(1) 查询 |
| CopyOnWriteArrayList | 读多写少 | 写时复制，写入需复制整个数组 |
| ConcurrentLinkedQueue | 高并发入队出队 | 无锁链表，适合消息队列 |
| BlockingQueue | 生产者-消费者 | 支持阻塞操作 |
java
// ConcurrentHashMap 常用操作
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.putIfAbsent("a", 1); // 不存在才插入
map.computeIfAbsent("b", k -> 1); // 不存在才计算插入
map.merge("a", 1, Integer::sum); // 合并操作
map.getOrDefault("c", 0); // 获取默认值
// CopyOnWriteArrayList 示例
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("a"); // 每次都复制整个数组，不适合写多场景总结
集合核心知识点：
| 知识点 | 面试频率 | 实战重要性 |
|---|---|---|
| ArrayList vs LinkedList | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| HashMap 底层结构 | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| HashMap vs Hashtable | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ |
| ConcurrentHashMap | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| HashSet 去重原理 | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ |
| fail-fast 机制 | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ |
⚠️ 易错点提醒：
- HashMap 可以存一个 null key、多个 null value
- TreeSet/TreeMap 元素必须可比较或提供 Comparator
- 遍历时删除元素必须用迭代器
- ArrayList 扩容是 1.5 倍，不是 2 倍
- HashMap 链表转红黑树的阈值是 8，红黑树转链表是 6