【Java 进阶】万字详解集合框架：从原理到源码，彻底搞懂 List、Set、Map

摘要：Java 集合框架（Java Collections Framework）是每一位 Java 开发者必须跨越的门槛。无论是日常业务开发，还是应对大厂面试，对集合的理解深度往往决定了代码的质量和职业的高度。本文将基于 Java 核心体系，从 List、Set 到 Map，深度剖析 ArrayList、LinkedList、HashMap、ConcurrentHashMap 等核心组件的底层实现、扩容机制及线程安全策略，助你构建完整的集合知识体系。

一、 Java 集合框架总览

在 Java 中，集合主要分为两大阵营：

1. Collection 接口：这是单列集合的根接口，定义了存储一组对象的方法。它主要有三个子接口：
   • List：有序，可重复。
   • Set：无序，不可重复。
   • Queue：队列，遵循 FIFO（先进先出）原则（本文暂略，重点聚焦图片内容）。
2. Map 接口：这是双列集合的根接口，存储键值对（Key-Value）。Map 并不是 Collection 的子接口，但它在集合框架中占据半壁江山。

二、 List：有序序列的王者

List 接口是 Collection 的子接口，其最大特点是有序（Ordered）且可重复（Allow Duplicates）。用户可以通过整数索引（Index）精确控制元素的插入位置和访问指定元素。

1. ArrayList：数组的动态演进

ArrayList 是 Java 中最常用的集合类，没有之一。

1.1 底层结构

正如图片中所述，ArrayList 的底层是容量可变的对象数组 (Object[] elementData)。

1.2 核心机制：自动扩容

很多初学者知道 ArrayList 会扩容，但不知道具体细节。

初始容量：当创建一个空的 ArrayList 时，默认的空数组。当添加第一个元素时，容量会初始化为 10。

扩容触发：当当前数组填满时（即 size == capacity），再次添加元素就会触发扩容。

扩容逻辑：

在 JDK 1.8 中，扩容的核心代码在 grow() 方法中。

int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 相当于除以 2。因此，新容量大约是旧容量的 1.5 倍。

数据迁移：扩容不仅仅是改变数值，更重要的是数据拷贝。ArrayList 底层调用 System.arraycopy 或 Arrays.copyOf 将原数组的数据复制到新的大数组中。

⚠ 性能警示：由于数组扩容涉及内存申请和数据复制，如果数据量巨大，频繁扩容会严重影响性能。最佳实践是在创建 ArrayList 时，如果能预估数据量，最好指定初始容量，如 new ArrayList<>(1000)。

1.3 优缺点分析

• 优点：支持随机访问（Random Access）。通过索引访问元素的时间复杂度为 O(1)，因为数组在内存中是连续存储的，可以通过内存地址偏移量直接计算。
• 缺点：插入和删除效率较低。
  • 除了尾部插入，其他位置的插入都需要将插入点之后的元素全部向后移动一位（O(n)）。
  • 删除操作需要将删除点之后的元素全部向前移动一位。
• 线程安全性：ArrayList 是非线程安全的。在多线程环境下并发写入可能导致 ConcurrentModificationException 或数据丢失。

2. LinkedList：链表的灵活舞步

2.1 底层结构

LinkedList 本质上是一个双向链表（Doubly Linked List）。每个节点（Node）包含三个部分：

• item: 存储数据。
• next: 指向下一个节点的指针。
• prev: 指向上一个节点的指针。

2.2 性能特性

• 插入与删除：速度快。
  • 如果在已知节点引用的情况下，插入和删除操作只需要改变前后节点的指针指向，时间复杂度为 O(1)。
  • 注意：如果是根据索引删除（如 remove(5)），它首先需要遍历找到第 5 个节点（O(n/2)），然后再删除。
• 查询：速度慢。
  • 不支持随机访问。要查找第 n 个元素，必须从头（或尾）开始遍历，时间复杂度为 O(n)。LinkedList 做了一点优化，如果索引小于 size 的一半，从头遍历；否则从尾遍历。

2.3 ArrayList vs LinkedList 终极对比

3. Vector 与 Stack（时代的眼泪）

• Vector：ArrayList 的前身，底层也是数组，但它所有的方法都加了 synchronized 关键字。这意味着它是线程安全的，但性能极差。现在几乎不再使用，多线程场景推荐使用 CopyOnWriteArrayList。
• Stack：继承自 Vector，实现了栈（LIFO）结构。由于继承了 Vector 的笨重，现在推荐使用 ArrayDeque 来实现栈的功能。

三、 Set：独一无二的坚持

Set 接口的核心契约是：不允许存在重复的元素。

1. HashSet：披着 Set 外衣的 Map

大多数人不知道，HashSet 的源码极其简单，简单到甚至有点“偷懒”。

1.1 实现原理

HashSet 的底层完全基于 HashMap 实现。

• 当你调用 HashSet.add(E e) 时，实际上是将元素 e 作为 Key 存入了内部的 HashMap 中。
• 那么 Value 是什么？Value 是一个名为 PRESENT 的静态 Object 常量（虚拟值）。

// HashSet 源码示意
private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

1.2 如何保证唯一性？

因为 HashMap 的 Key 是唯一的，所以 HashSet 的元素自然也是唯一的。这依赖于两个方法：

1. hashCode(): 计算哈希值，确定存储位置。
2. equals(): 如果哈希值冲突，比较内容是否相同。

面试考点：如果将自定义对象存入 HashSet，必须重写 hashCode() 和 equals()，否则会出现逻辑上相同的对象被视为不同元素的情况。

2. LinkedHashSet：有序的哈希

HashSet 是无序的，但有时我们需要保持元素的插入顺序。这时 LinkedHashSet 就派上用场了。

• 底层：它继承自 HashSet，但其内部使用的是 LinkedHashMap。
• 机制：在哈希表的基础上，它维护了一个双向链表，记录了所有元素的插入顺序。因此，遍历 LinkedHashSet 时，输出顺序与插入顺序一致。

3. TreeSet：排序的艺术

TreeSet 的底层是 TreeMap。

• 数据结构：红黑树（Red-Black Tree）。
• 特点：元素不仅唯一，而且有序（按值的大小排序，而非插入顺序）。
• 排序规则：
  1. 自然排序：元素类实现 Comparable 接口。
  2. 定制排序：在创建 TreeSet 时传入一个 Comparator 比较器。

四、 Map：键值对的宇宙

Map 是 Java 中最复杂的集合，也是面试中含金量最高的部分。Map 存储 Key-Value 映射，Key 无序且唯一，Value 可重复。

1. HashMap：重中之重

HashMap 是 Java 程序员必须精通的类。

1.1 JDK 1.7 vs JDK 1.8 的巨变

图片中提到了这个关键点，我们来展开讲讲：

• JDK 1.7 结构：数组 + 链表。
  • 采用“拉链法”解决哈希冲突。当发生冲突时，新元素被放到链表中。
  • 头插法：1.7 在扩容迁移数据时使用头插法，这在多线程并发环境下容易导致链表成环（Infinite Loop），导致 CPU 飙升 100%。
• JDK 1.8 结构：数组 + 链表 + 红黑树。
  • 这是一个巨大的优化。当链表过长时，查找效率会从 O(1) 退化为 O(n)。
  • 树化阈值：当链表长度超过 8，且数组长度大于 64 时，链表会转换为红黑树。
  • 红黑树优势：查找时间复杂度优化为 O(log n)。
  • 尾插法：1.8 改用尾插法，解决了并发下的死循环问题（但 HashMap 依然不是线程安全的）。

1.2 关键参数

• Capacity（容量）：数组的长度，默认为 16。必须是 2 的幂次方（为什么？为了利用位运算 (n-1) & hash 高效计算索引）。
• LoadFactor（负载因子）：默认为 0.75。
  • 如果太大（如 1.0），空间利用率高，但哈希冲突概率大，查询慢。
  • 如果太小（如 0.5），冲突少，查询快，但空间浪费大，扩容频繁。
  • 0.75 是一个在时间和空间上的折中选择。

2. LinkedHashMap：LRU 的基石

LinkedHashMap 继承自 HashMap。

• 结构：在 HashMap 的数组+链表/红黑树结构之上，增加了一条双向链表，串联起所有的 Entry。
• 功能：
  1. 保持插入顺序：默认行为。
  2. 保持访问顺序：通过构造函数设置 accessOrder = true。每当读取一个 Key，该 Key 就会被移到链表尾部。这是实现 LRU（Least Recently Used，最近最少使用）缓存算法的核心机制。

3. TreeMap：自平衡的秩序

TreeMap 基于红黑树实现。

• 它保证 Key 是有序的。
• 所有操作（增删改查）的时间复杂度都是 O(log n)。
• 适用于需要按 Key 排序遍历的场景，如一致性哈希环的实现。

4. Hashtable：古老的遗迹

Hashtable（注意 t 是小写）是 JDK 1.0 就存在的类。

• 它是线程安全的（全表锁，使用 synchronized）。
• 不允许 Key 或 Value 为 null（HashMap 允许 Key 为 null）。
• 由于锁的粒度太大，性能低下，已被 ConcurrentHashMap 取代。

5. ConcurrentHashMap：并发编程的利器

这是多线程环境下的首选 Map。

5.1 JDK 1.7 的实现：分段锁 (Segment)

• 思想：锁分离。
• 结构：内部维护了一个 Segment 数组，每个 Segment 本质上是一个小的 HashTable（继承自 ReentrantLock）。
• 并发度：默认为 16。也就是说，理论上支持 16 个线程并发写入而互不干扰，只要它们的 Key 落在不同的 Segment 上。

5.2 JDK 1.8 的实现：CAS + Synchronized

• 抛弃 Segment：1.8 取消了 Segment 分段锁，直接采用 Node 数组。
• 锁粒度更细：
  • 如果该位置（桶）为空，使用 CAS (Compare And Swap) 操作尝试插入，无需加锁。
  • 如果该位置不为空（存在哈希冲突），使用 synchronized 锁住当前桶的头节点（链表头或树根）。
• 优势：锁的粒度细化到了每个数组下标（桶）级别，并发性能得到了极大的提升。

五、 总结与建议

Java 集合框架博大精深，掌握它们不仅仅是背诵 API，更重要的是理解其背后的设计哲学：

1. 权衡（Trade-off）：没有完美的集合。ArrayList 牺牲插入性能换取读取性能；LinkedList 牺牲空间换取插入性能；HashMap 牺牲空间换取极致的查找速度。
2. 扩容的代价：所有的动态集合（ArrayList, HashMap）在扩容时都有巨大的性能损耗。预估容量是优化的第一步。
3. 线程安全：永远不要在多线程环境下直接使用 ArrayList 或 HashMap。请使用 java.util.concurrent 包下的 ConcurrentHashMap、CopyOnWriteArrayList 等并发容器。

希望这篇详解能帮助你从“会用”进阶到“懂原理”，在面试和实战中游刃有余！