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. 扩容公式：新容量 = 旧容量 * 1.5
2. 扩容方法：Arrays.copyOf()（底层调用 System.arraycopy）
3. 扩容本质：创建新数组 → 复制元素 → 丢弃旧数组

4. 常用方法源码逻辑

• add()
  1. 检查容量是否足够
  2. 不够就扩容
  3. 赋值元素
• get()
  直接数组下标访问，O(1)，极快
• remove()
  后面元素向前移动，O(n)，效率低

5. 特点总结

• 优点：查询快、随机访问快
• 缺点：插入/删除慢、线程不安全
• 适用：读多写少

三、LinkedList 源码核心

1. 底层结构

双向链表，节点结构：

private static class Node<E> {
   
    E item;
    Node<E> next; // 后继
    Node<E> prev; // 前驱
}

2. 核心逻辑

• add()：只需修改节点引用，不用扩容，O(1)
• get(int index)：
  会遍历链表，O(n)，比 ArrayList 慢很多
• remove()：修改节点引用，O(1)

3. 特点

• 优点：增删快
• 缺点：查询慢
• 线程不安全

四、HashMap 源码（重中之重！面试 100% 问）

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 方法流程（背下来）

1. 数组为空，第一次 put 才初始化容量 16
2. 计算 hash，得到数组下标
3. 下标无元素 → 直接插入
4. 下标有元素 → 遍历链表
5. 链表长度 ≥8 且数组长度≥64 → 转为红黑树
6. 元素个数超过阈值 → 扩容 2 倍
7. 覆盖旧值或新增成功

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)，提升效率

七、学习建议

1. 优先掌握：HashMap、ArrayList（最常考）
2. 看源码只看核心：put/get/扩容/树化
3. 不用死磕全部代码，抓流程和思想
4. 结合画图理解（数组+链表+红黑树）

总结

• ArrayList：动态数组，1.5 倍扩容，查询快
• LinkedList：双向链表，增删快
• HashMap：1.8 数组+链表+红黑树，CAS 不安全
• ConcurrentHashMap：1.8 CAS + synchronized 线程安全