Java集合框架源码核心解析与实战对比

Java 集合框架源码核心解析（面试进阶必备）

直接切入正题——这里提炼的是最核心、最高频、最实用的集合源码解析，不浪费一行文字，全部聚焦于实际工作和面试中的关键点。按照这个路线学习，足以深入理解集合底层机制。

一、先理清：集合框架整体结构

Collection（根接口）
├─ List 有序、可重复
│  ├─ ArrayList（动态数组）
│  ├─ LinkedList（双向链表）
│  └─ Vector（线程安全，已废弃）
├─ Set 无序、不可重复
│  ├─ HashSet（基于 HashMap）
│  ├─ LinkedHashSet（链表+哈希）
│  └─ 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)，远慢于 ArrayList
• remove()：调整节点指针，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 倍
• 重新计算所有元素的存储位置
• 高并发下可能引发死循环（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
• 锁粒度：数组头节点，细分锁竞争，并发性能更高
• 底层：数组 + 链表 + 红黑树
• 禁止 key/value 为 null

3. 为何线程安全？

• 读操作无锁（volatile 保证可见性）
• 写操作：CAS 失败 → synchronized 锁头节点再操作

六、高频面试题（直接背诵）

1. ArrayList vs LinkedList

• ArrayList：基于数组，随机查询快，插入删除慢
• LinkedList：基于双向链表，随机查询慢，插入删除快

2. HashMap 1.7 vs 1.8

• 1.7：数组+链表，头插法，扩容存在死链问题
• 1.8：数组+链表+红黑树，尾插法，哈希算法优化

3. HashMap 线程不安全的根源

• 多线程 put 导致数据覆盖
• JDK1.7 扩容时产生循环链表

4. ConcurrentHashMap 的安全保障

1.8：CAS + synchronized 锁定数组头节点 + volatile 保证可见性

5. 为何 HashMap 加载因子默认 0.75？

• 空间利用率与查询效率的折衷
• 基于泊松分布，哈希碰撞概率最低

6. 链表为何要转红黑树？

• 链表过长时查询退化为 O(n)
• 红黑树查询 O(logn)，性能显著提升

七、学习建议

• 优先深耕：HashMap、ArrayList（面试出现率最高）
• 阅读源码只聚焦核心：put/get/扩容/树化 流程
• 不必逐行通读，抓住设计思想和主干逻辑
• 配合画图理解（数组+链表+红黑树结构）

总结

• ArrayList：动态数组，1.5 倍扩容，随机读性能强
• LinkedList：双向链表，增删操作快
• HashMap：1.8 数组+链表+红黑树，非线程安全
• ConcurrentHashMap：1.8 CAS + synchronized 保证线程安全