Java 集合框架源码核心解析（面试进阶必背）
直接切入正题——这里梳理的是最核心、最高频、最实用的集合源码解析，没有一句废话，全部是工作和面试中的重难点。按照这个路线学习，基本就能把集合底层原理彻底吃透。
一、先搞懂：集合框架整体架构
Collection（根接口）
├─ List 有序、可重复
│ ├─ ArrayList（数组）
│ ├─ LinkedList（双向链表）
│ └─ Vector（线程安全，弃用）
├─ Set 无序、不可重复
│ ├─ HashSet（HashMap 实现）
│ ├─ LinkedHashSet（链表 + Hash）
│ └─ TreeSet（红黑树）
└─ Queue 队列
Map（键值对，根接口）
├─ HashMap（数组 + 链表 + 红黑树）
├─ ConcurrentHashMap（线程安全）
├─ LinkedHashMap（记录插入顺序）
└─ TreeMap（红黑树排序）
二、ArrayList 源码核心（高频考察点）
1. 底层数据结构
底层依赖 Object 数组：transient Object[] elementData
2. 初始化时机
- 无参构造：初始为空数组
{}，第一次调用 add 才扩容为 10 - 有参构造：直接指定数组长度，避免频繁扩容
3. 扩容机制（重中之重）
- 扩容公式：新容量 = 旧容量 * 1.5（右移一位加原值）
- 扩容方法：
Arrays.copyOf()（底层调用 System.arraycopy 进行内存拷贝） - 扩容本质：创建新数组 → 复制所有元素 → 丢弃旧数组对象
4. 常用方法源码逻辑
add()：先检查容量是否足够，不足则扩容，再在末尾赋值元素get()：直接通过数组下标访问，时间复杂度 O(1)，性能极快remove()：将后续元素整体向前移动，时间复杂度 O(n)，效率较低
5. 特点总结
- 优点：随机查询、快速读取性能突出
- 缺点：插入和删除需要移动元素、线程不安全
- 适用场景：读多写少、频繁随机访问的业务
三、LinkedList 源码核心
1. 底层结构
双向链表实现，节点内部结构：
private static class Node {
E item;
Node next; // 后继指针
Node prev; // 前驱指针
}
2. 核心逻辑
add()：只需修改节点之间的引用关系，无需扩容，时间复杂度 O(1)get(int index)：需要遍历链表到指定位置，时间复杂度 O(n)，远慢于 ArrayListremove()：修改前后节点的引用即可，时间复杂度 O(1)
3. 特点总结
- 优点：任意位置的插入和删除效率高
- 缺点：随机访问性能很差
- 线程不安全，需外部加锁
四、HashMap 源码（重中之重！面试几乎必问）
1. 底层数据结构
JDK 1.8 采用：数组 + 链表 + 红黑树
2. 关键参数
- 初始容量：16
- 负载因子：0.75
- 扩容阈值：当前容量 * 负载因子
- 树化阈值：链表长度 ≥ 8
- 反树化阈值：红黑树节点 ≤ 6
3. 哈希计算（源码设计精髓）
static final int hash(Object key) {
int h;
// 高16位异或低16位，充分扰动，减少哈希冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
数组下标计算公式：(数组长度 - 1) & hash
4. put 方法执行流程（建议熟记）
- 数组为空，第一次 put 时才会初始化容量为 16
- 计算 hash 值，得到数组下标
- 下标处无元素 → 直接新建节点插入
- 下标有元素 → 遍历链表或红黑树
- 链表长度 ≥8 且数组总长度 ≥64 → 链表转为红黑树
- 元素个数超过扩容阈值 → 容量扩大为原容量的 2 倍
- 覆盖旧值或新增成功
5. 扩容机制详解
- 容量扩大为原来的 2 倍
- 重新计算所有元素的桶下标（rehash）
- 高并发下旧版本（JDK1.7）可能产生死循环，1.8 已修复但仍非线程安全
6. 特点总结
- 线程不安全
- 允许 key 和 value 为 null
- 查询效率极高，平均 O(1)
- 链表过长时自动转换为红黑树，查询效率提升至 O(logn)
五、ConcurrentHashMap 源码（线程安全方案）
1. JDK 1.7 版本
- 分段锁（Segment），默认分为 16 段
- 锁粒度：段级别，并发度为 16
2. JDK 1.8 版本（重点）
- 取消分段锁，改用 CAS + synchronized
- 锁粒度：细化到数组头节点，并发性能进一步提升
- 底层结构：数组 + 链表 + 红黑树（与 HashMap 相同）
- 不允许 key 或 value 为 null
3. 如何保证线程安全？
- 读操作：通过 volatile 变量保证可见性，无锁
- 写操作：先尝试 CAS，失败后加 synchronized 锁住头节点
六、高频面试题（直接背答案）
1. ArrayList 与 LinkedList 如何选择？
- ArrayList：数组结构，查询快（O(1)）、增删慢（O(n)）
- LinkedList：双向链表结构，查询慢（O(n)）、增删快（O(1)）
2. HashMap 1.7 与 1.8 的核心差异
- 1.7：数组 + 链表，头插法，扩容时可能形成死循环
- 1.8：数组 + 链表 + 红黑树，尾插法，哈希算法优化
3. 为什么 HashMap 是线程不安全的？
- 多线程同时 put 可能导致数据被覆盖
- JDK1.7 扩容时多线程并发操作会引发死循环（CPU 100%）
4. ConcurrentHashMap 如何保证并发安全？
1.8 采用 CAS + synchronized 锁头节点 + volatile 读，实现高并发下数据一致性
5. 为什么 HashMap 默认负载因子是 0.75？
- 在空间利用率与查询效率之间取得最佳平衡
- 根据泊松分布，0.75 时哈希冲突概率最低
6. 链表过长为什么要转红黑树？
- 链表查询时间复杂度为 O(n)，性能随长度急剧下降
- 红黑树查询时间复杂度为 O(logn)，可显著提升效率
七、学习建议
- 优先掌握：HashMap、ArrayList（面试出现频率最高）
- 阅读源码时聚焦核心方法：
put/get/扩容/树化流程 - 不必死磕每一行代码，重在理解整体思想和关键步骤
- 结合示意图理解（数组 → 链表 → 红黑树 的演进过程）
总结
- ArrayList：动态数组，1.5 倍扩容，随机访问快
- LinkedList：双向链表，增删操作高效
- HashMap：1.8 采用数组 + 链表 + 红黑树，非线程安全
- ConcurrentHashMap：1.8 使用 CAS + synchronized 实现线程安全
