Java数据结构源码拆解：从入门到精通避坑指南

官方文档太长，翻到第三页就头晕？想搞懂 数据结构java 底层逻辑，却总被 ArrayList 的扩容机制绕晕？别慌。

很多开发者卡在 入门到精通 的瓶颈期，就是因为只背 API，没看源码。今天不整虚的，直接扒开 JDK 源码，带你把最核心的数据结构看透。

01 入口定位：为什么是 ArrayList？

在 Java 集合框架中，List 接口有两个主要实现：ArrayList 和 LinkedList。

选谁？看场景。

读多写少：选 ArrayList，数组连续存储，CPU 缓存命中率高。
频繁增删：选 LinkedList，双向链表，节点插入删除 O(1)。

但 90% 的业务场景，ArrayList 是默认首选。它的底层是一个对象数组 Object[]。

很多人有个误区：认为 ArrayList 每次添加元素都要新建数组。错！它有个扩容机制。

初始容量：10（JDK 8+ 默认，JDK 7 是 0，第一次 add 才扩容到 10）。
扩容策略：每次扩容为原来的 1.5 倍。

这个 1.5 倍 不是随便定的。它是在“内存浪费”和“拷贝开销”之间找平衡。

扩 2 倍：内存浪费多，GC 压力大。
扩 1.2 倍：拷贝次数多，CPU 开销大。

1.5 倍是经验值。JDK 源码里写死了 oldCapacity + (oldCapacity >> 1)，也就是 oldCapacity * 1.5。

记住这个点，面试常被问。

02 核心片段：源码逐行拆解

来看 JDK 1.8 中 ArrayList 的 add 方法核心逻辑。

public boolean add(E e) {ensureCapacityInternal(size + 1);  // 1. 确保容量足够elementData[size++] = e;           // 2. 元素放入数组末尾return true;
}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(minCapacity);
}private void ensureExplicitCapacity(int minCapacity) {modCount++;                        // 3. 修改计数器，用于并发检查// 如果当前容量小于所需最小容量，触发扩容if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureCapacityInternal(minCapacity);
}private void ensureCapacityInternal(int minCapacity) {synchronized (this) {// 防止并发扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}
}private void grow(int minCapacity) {int oldCapacity = elementData.length;// 4. 计算新容量：oldCapacity + (oldCapacity >> 1)int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;     // 5. 如果新容量仍不够，直接用最小容量if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity); // 6. 超过最大数组限制// 7. 复制数组：System.arraycopy 是底层 C 代码，比 for 循环快elementData = Arrays.copyOf(elementData, newCapacity);
}

逐行注释重点：

ensureCapacityInternal(size + 1)：每次 add 前，检查容量是否够下一个元素。
modCount++：这是 fail-fast 机制的核心。如果在迭代过程中，其他线程修改了列表，modCount 变了，迭代器会抛出 ConcurrentModificationException。
oldCapacity >> 1：右移一位，等价于除以 2。这是位运算优化，比除法快。
Arrays.copyOf：底层调用 System.arraycopy，是 JVM 层面的内存拷贝，效率远高于 Java 层的 for 循环逐个赋值。

关键设计：

懒加载：JDK 8 中，new ArrayList<>() 不会立刻分配数组，而是指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA（空数组）。第一次 add 时才真正分配 10 个空间。节省内存。
同步块：grow 方法里有 synchronized。注意，这不是线程安全！synchronized 只保护 grow 方法本身，但 add 方法整体不是同步的。并发调用 add，还是可能数据错乱。

03 设计思想：为什么这么写？

1. 空间换时间 数组连续存储，支持 O(1) 随机访问。get(i) 直接 elementData[i]，不需要遍历。这是 ArrayList 的核心优势。

2. 扩容的平衡术 1.5 倍扩容，是工程折中。

如果每次加 1 个：new int[n+1]，拷贝 n 个元素，总拷贝次数 O(n²)，太慢。
如果每次翻倍：内存浪费最多 50%，GC 压力大。
1.5 倍：拷贝总次数 O(n)，内存浪费可控。

3. fail-fast 机制 modCount 是并发安全的“报警器”。

单线程迭代中 remove 元素，modCount 不变，迭代器不报错。
并发场景下，modCount 变了，迭代器发现不一致，立刻抛异常。
目的：快速失败，避免数据不一致导致的隐蔽 Bug。

对比 LinkedList： LinkedList 底层是双向链表。

add(i, e)：找到第 i 个节点，插入新节点，修改前后指针。O(1)（假设已定位）。
get(i)：从头或尾遍历到第 i 个。O(n)。

结论：

需要随机访问：ArrayList。
需要频繁中间插入/删除：LinkedList。
但实际业务中，LinkedList 很少用。因为：
1. 节点分散在堆内存，CPU 缓存命中率低。
2. 每个节点多两个指针（prev, next），内存开销大。
3. ArrayList 的扩容开销，在多数场景下可接受。

04 手写简化版：从 0 到 1 实现

理解源码后，自己写一个 MyArrayList，巩固理解。

import java.util.Arrays;public class MyArrayList<E> {private Object[] elementData;private int size;private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};public MyArrayList() {elementData = EMPTY_ELEMENTDATA;}public MyArrayList(int initialCapacity) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);this.elementData = new Object[initialCapacity];}public boolean add(E e) {ensureCapacity(size + 1);elementData[size++] = e;return true;}public E get(int index) {rangeCheck(index);return (E) elementData[index];}public E remove(int index) {rangeCheck(index);E oldValue = (E) elementData[index];int numMoved = size - index - 1;if (numMoved > 0)// 数组元素前移，覆盖被删除元素System.arraycopy(elementData, index + 1, elementData, index, numMoved);elementData[--size] = null; // 帮助 GCreturn oldValue;}private void ensureCapacity(int minCapacity) {if (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;elementData = Arrays.copyOf(elementData, newCapacity);}private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}public int size() {return size;}
}

关键点：

elementData[--size] = null：删除元素后，将末尾位置置空。否则，被删除的对象仍被数组引用，GC 无法回收，导致内存泄漏。
System.arraycopy：比 for 循环快，底层是 native 方法。
rangeCheck：索引越界检查，必须做。

测试：

public static void main(String[] args) {MyArrayList<String> list = new MyArrayList<>();list.add("A");list.add("B");list.add("C");System.out.println(list.get(1)); // 输出 Blist.remove(0);System.out.println(list.get(0)); // 输出 BSystem.out.println(list.size()); // 输出 2
}

05 应用场景：避坑与实战

坑 1：初始容量估算 如果你知道大概要存 1000 个元素，不要 new ArrayList<>()。

// 错误：默认 10，扩容 10->15->22->33->49->73->109->163->244->366->549->823->1234
List<String> list = new ArrayList<>();
for (int i = 0; i < 1000; i++) {list.add("item" + i);
}// 正确：直接指定容量，避免多次扩容
List<String> list = new ArrayList<>(1000);

原因：每次扩容都要 System.arraycopy，拷贝 1000 个对象，开销巨大。

坑 2：并发修改

// 错误：多线程同时 add
List<String> list = new ArrayList<>();
new Thread(() -> {for (int i = 0; i < 1000; i++) {list.add("A" + i);}
}).start();
new Thread(() -> {for (int i = 0; i < 1000; i++) {list.add("B" + i);}
}).start();

结果：size 可能小于 2000，数据丢失。解决：

用 CopyOnWriteArrayList（读多写少，快照隔离）。
用 Collections.synchronizedList(new ArrayList<>())（全同步，性能差）。
用 ConcurrentLinkedQueue（无锁，线程安全，但不支持随机访问）。

坑 3：迭代器删除

// 错误：for-each 中 remove
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
for (String s : list) {if ("B".equals(s)) {list.remove(s); // 抛出 ConcurrentModificationException}
}// 正确：用迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {if ("B".equals(it.next())) {it.remove();}
}

原因：for-each 底层用迭代器，list.remove 直接改 modCount，迭代器发现不一致，抛异常。

实战建议：

JDK 8+：优先用 ArrayList，初始容量设大点。
高并发：CopyOnWriteArrayList（读多）或 ConcurrentLinkedQueue（队列场景）。
需要排序：TreeSet / TreeMap（红黑树，O(log n) 查找）。
需要去重：HashSet / TreeSet。

性能对比（JMH 基准测试，大致参考）： | 操作 | ArrayList | LinkedList | | :--- | :--- | :--- | | get(i) | 1ns | 10ns (遍历) | | add(i) | 100ns (移动元素) | 10ns (指针操作) | | remove(i) | 100ns | 10ns | | 内存占用 | 低 | 高 (指针开销) |

数据支撑： 在 10 万元素级别，ArrayList 的 get 操作比 LinkedList 快 10 倍以上。因为 CPU 缓存行（64 字节）能容纳多个数组元素，而链表节点分散，缓存命中率低。

RFC 规范参考： 虽然 Java 集合框架没有 RFC 规范，但其设计思想与 RFC 2818（HTTP 安全扩展）中的“最小权限原则”类似——ArrayList 不提供线程安全，避免不必要的同步开销。并发安全交给用户选择（Collections.synchronizedList 或 CopyOnWriteArrayList）。

总结：