前言

Java 集合是面试八股文的必争之地。本文从源码视角出发，串联 ArrayList、LinkedList、HashMap、Set 等核心集合类的设计内幕，帮你理解它们为什么这样设计，而不仅仅是”记住”结论。

一、ArrayList 的底层真相：elementData

1.1 核心结构

1
transient Object[] elementData;

ArrayList 的所有元素都存储在这个 Object[] 数组中。你调用的 add(E e)、get(int index)、remove(int index) 等方法，本质上都是在操作这个数组：

1
2
3
4
public E get(int index) {
    Objects.checkIndex(index, size);
    return (E) elementData[index];  // 直接从数组取，O(1)
}

1.2 为什么用 Object[] 而不是 E[]？

Java 的泛型擦除机制决定了 JVM 层面不存在 E[]。编译后 E 就是 Object，所以底层直接用 Object[] 存储，取出来时强转为 E。

1.3 为什么用 transient 修饰？

transient 表示不参与默认序列化。因为 elementData 的实际长度（容量）通常大于元素个数 size，多余的空位都是 null。如果默认序列化，这些 null 也会被写入，浪费空间。

ArrayList 重写了 writeObject / readObject，只序列化前 size 个有效元素。

1.4 扩容机制：1.5 倍增长

每次 add 前都会检查容量是否够用：

1
add(E e) → 如果 (size + 1) > elementData.length → grow() 扩容

扩容核心逻辑：

1
2
3
4
int newCapacity = oldCapacity + (oldCapacity >> 1);
//                    ↑                  ↑
//                 旧容量         旧容量 ÷ 2（向下取整）
//              新容量 = 旧容量 × 1.5

扩容不是改参数，而是”换一个新数组”——创建更大的新数组，把旧元素拷贝过去，旧数组被 GC 回收。

1.5 为什么是 1.5 倍而不是 2 倍？

这个选择背后是空间利用率与时间效率的权衡：

扩容倍数 优点 缺点
2 倍 扩容次数最少 内存碎片无法复用
1.5 倍 扩容次数适中，内存可复用 —

2 倍的致命问题：每次扩容丢弃的旧数组内存块，加起来永远小于下一次要申请的新数组大小，导致内存分配器无法复用这些碎片。

1.5 倍的数学优势：前面释放的所有旧数组累积大小最终会超过新数组大小，内存分配器有机会合并旧块来容纳新数组，碎片化程度更低。

💡 关键纠正：>> 1 这种位运算是实现手段，不是原因。设计者先选择了约 1.5 倍这个增长因子，然后用位运算高效实现它。如果当初要 2 倍，一样可以写成 oldCapacity << 1。

1.6 trimToSize()：给数组”瘦身”

1
2
3
4
5
6
7
8
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
                ? EMPTY_ELEMENTDATA           // 空列表 → 共享空数组
                : Arrays.copyOf(elementData, size); // 砍掉多余空间
    }
}

使用场景：你已经加载了大量数据，之后只做查询不再 add，调用此方法释放多余内存。

⚠️ 注意：如果之后还要 add 元素，刚缩完容马上又扩容，反而更亏。

二、JDK 11 的 ArrayList 变化

JDK 8 中熟悉的 ensureCapacityInternal() 和 ensureExplicitCapacity() 在 JDK 11 中被移除了。

变化方式：不是”替换”，而是把原有逻辑直接内联（inline）到调用处：

JDK 8 JDK 11
ensureCapacityInternal(minCapacity) 逻辑移到 grow(int minCapacity)
ensureExplicitCapacity(minCapacity) modCount++ 提到 add() 开头，判断条件直接写在 add(e, elementData, s) 里
手动计算 newCapacity 改用 ArraysSupport.newLength(...)

本质上功能完全相同，只是摊平了调用层级，代码更扁平化。扩容倍数仍是 1.5 倍。

三、AbstractSequentialList：LinkedList 的适配器

3.1 继承体系全景

1
2
3
4
5
6
7
8
9
AbstractCollection
    ↑
AbstractList              ← 为"随机访问"列表准备的骨架
    ↑          ↑
    |     AbstractSequentialList  ← 为"顺序访问"列表准备的骨架
    |          ↑
    |     LinkedList              ← 只需实现 listIterator()
    |
  ArrayList   ← 直接继承 AbstractList，按数组下标实现

3.2 为什么需要它？

核心矛盾：AbstractList 已经给 get(i)、set(i)、add(i)、remove(i) 写了默认实现——但全是抛异常：

1
2
3
4
// AbstractList 的默认行为
public E set(int index, E element) {
    throw new UnsupportedOperationException();
}

LinkedList 作为链表，直接继承 AbstractList 就必须自己逐个覆盖这四个方法，否则一调就炸。

AbstractSequentialList 做的事：把这四个抛异常的方法全部覆盖，统一转成迭代器操作：

1
2
3
4
5
// AbstractSequentialList 把抛异常改成正常干活
public E get(int index)      → return listIterator(index).next();
public E set(int index, E e) → listIterator(index).set(e);
public void add(int i, E e)  → listIterator(i).add(e);
public E remove(int i)       → { it.next(); it.remove(); }

LinkedList 只需实现 listIterator(index) 一个核心方法，这四个方法自动可用。

3.3 双重身份

身份 说明
标识/约束 明确”这是一个顺序访问的 List”，是 RandomAccess 接口的反面
代码复用 堵住 AbstractList 抛出的四个异常，转为迭代器实现

四、迭代器 vs 下标访问：两种截然不同的访问哲学

4.1 按下标访问——数组的 O(1) 魔法

数组在内存中是连续空间：

1
2
3
4
内存地址:  0x1000  0x1004  0x1008  0x100C  0x1010
           ┌──────┬──────┬──────┬──────┬──────┐
元素:      │  A   │  B   │  C   │  D   │  E   │
           └──────┴──────┴──────┴──────┴──────┘

取第 3 个元素：目标地址 = 起始地址 + 3 × 元素大小，一步到位。

4.2 迭代器——链表的导航仪

链表在内存中是散落的：

1
2
3
4
┌────┐  ┌────┐  ┌────┐  ┌────┐  ┌────┐
│ A  │  │ B  │  │ C  │  │ D  │  │ E  │
│next│→ │next│→ │next│→ │next│→ │next│→ null
└────┘  └────┘  └────┘  └────┘  └────┘

迭代器就是一个拿着当前节点引用的对象，每次 next() 顺着链表往下走一步。

4.3 核心差异：有状态 vs 无状态

1
2
3
4
5
6
7
8
9
10
// 按索引——每次独立，互不影响
list.get(3);  // 从头跳到第3个
list.get(4);  // 又从头跳到第4个
list.get(5);  // 又又从头跳 → O(n²) 的灾难

// 迭代器——有状态的，接着上次的位置继续
Iterator<String> it = list.iterator();
it.next();  // 第0个
it.next();  // 第1个，接着上一步走一步
it.next();  // 第2个，接着上一步走一步 → O(n) 走完全程
按下标 get(3) 迭代器 it.next()
原理 算内存地址 顺着指针走
状态 无状态 有状态（记住走到哪了）
链表复杂度 O(n) O(1) 单次，O(n) 整体

🧭 形象记忆：按索引 = GPS 直接导航过去；迭代器 = 拿张地图沿路走，走一步记一步。数组有 GPS，链表没有，只能沿路走。

五、Set 为什么大多基于 Map 实现？

5.1 一句话真相

HashMap 的 key 天然不重复，Set 的核心要求就是不重复——直接拿 key 那套机制，零成本复用。

5.2 源码真相

1
2
3
4
5
6
7
8
9
10
11
public class HashSet<E> extends AbstractSet<E> {
    
    private transient HashMap<E, Object> map;    // 内部持有一个 HashMap
    private static final Object PRESENT = new Object(); // 占位假 value
    
    public boolean add(E e)    { return map.put(e, PRESENT) == null; }
    public boolean remove(Object o) { return map.remove(o) == PRESENT; }
    public boolean contains(Object o) { return map.containsKey(o); }
    public int size()          { return map.size(); }
    public Iterator<E> iterator() { return map.keySet().iterator(); }
}

Set 就是”只有 key，不要 value”的阉割版 Map。 那个 PRESENT 只是一个占位符，Set 不 care value 是什么。

5.3 各种 Set 对应的 Map

Set 实现 底层 Map 特性来源
HashSet HashMap 无序，O(1) 增删查
LinkedHashSet LinkedHashMap 维护插入顺序
TreeSet TreeMap（红黑树） 自动排序
ConcurrentSkipListSet ConcurrentSkipListMap 线程安全 + 有序

每个 Set 的特点都是从底下的 Map 继承来的。这就是典型的委托模式——换了一层壳，核心能力全部来自被委托的对象。

唯一例外是 EnumSet，基于位向量实现，速度比 HashMap 还快。

六、HashMap 的拉链法

6.1 什么是拉链法？

HashMap 底层是一个数组，每个位置叫一个桶（bucket）。不同 key 算出同一个桶下标 → 冲突了 → 用链表串起来：

1
2
3
4
5
6
7
8
9
10
HashMap 底层数组
┌─────┐
│  0  │ → null
├─────┤
│  1  │ → [key="A"] → [key="B"] → [key="C"] → null   ← 三个 key 冲突了
├─────┤
│  2  │ → null
├─────┤
│  3  │ → [key="D"] → null
└─────┘

“拉链”二字：数组是锁扣，链表是链条，冲突了就拉一条链子挂上去。

6.2 JDK 8 的红黑树优化

当链表太长了怎么办？JDK 8 的策略：

1
2
3
链表长度 ≥ 8   &&   数组容量 ≥ 64
      ↓
链表 → 红黑树（查找从 O(n) 降到 O(logn)）

6.3 拉链法 vs 开放寻址法

拉链法（HashMap） 开放寻址法（ThreadLocal）
原理 冲突了挂在同一个桶下 冲突了往下一个空位放
形象 一个车位挂一串车 车位被占了，往后找空车位
优点 空间利用率灵活，元素多了也能 hold 住 缓存友好，无指针开销
缺点 指针跳转，缓存不友好 表满了必须扩容，删除麻烦

七、LinkedHashMap：给 HashMap 加一条双向链表

7.1 双线结构

LinkedHashMap 继承 HashMap，在原有数组 + 链表/红黑树的基础上，给每个节点增加 before / after 两个指针，把所有节点串成一条双向链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
HashMap 底层数组：
┌───┐
│ 1 │ → [张三] → [王五]     ← 这两个 key 哈希冲突，在同一个桶里
├───┤
│ 2 │ → [赵六]
├───┤
│ 3 │ → [李四]
└───┘

LinkedHashMap 双向链表（贯穿所有节点，按插入顺序）：
null ←→ [张三] ←→ [李四] ←→ [王五] ←→ [赵六] ←→ null
         ↑        ↑        ↑        ↑
       第1个     第2个     第3个     第4个

数组负责 O(1) 快速查找，链表负责维护顺序。 遍历时直接沿链表走，保证顺序可预测。

7.2 最大杀招：LRU 缓存

设置 accessOrder=true 后，每次访问元素会被移到链表末尾：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
LinkedHashMap<String, Integer> lruCache = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3;   // 超过 3 个就自动删最老的
    }
};

lruCache.put("A", 1);
lruCache.put("B", 2);
lruCache.put("C", 3);
lruCache.put("D", 4);  // A 被自动踢出：剩下 B、C、D

lruCache.get("B");      // B 被移到链表末尾
// 此时顺序：C → D → B

几十行代码，一个标准的 LRU 缓存就出来了。这也是面试手写 LRU 的标准答案。

7.3 对比总结

HashMap LinkedHashMap
查找速度 O(1) O(1)（一样快）
遍历顺序 不可预测（按桶） 可预测（按插入/访问顺序）
额外开销 无 每个节点多存 2 个指针
LRU 缓存 不支持 accessOrder=true 即可

🧬 精髓：LinkedHashMap = HashMap 的查找能力 + LinkedList 的顺序能力，各取所长。

总结

组件 核心设计思想
ArrayList Object[] 数组 + 1.5 倍扩容（空间复用优于 2 倍）
AbstractSequentialList 适配器模式，把抛异常的索引操作转为迭代器操作
迭代器 有状态的顺序访问，链表遍历的生命线
HashSet 委托模式，复用 HashMap 的 key 去重能力
HashMap 拉链法 数组 + 链表 + JDK 8 红黑树优化
LinkedHashMap HashMap + 双向链表 → 顺序可预测 + 天然 LRU

理解了这些”为什么”，面试时才能从背八股的选手中脱颖而出。