ArrayList 扩容机制与性能调优

// 从 CSV 读取 100 万条记录，逐条加入 ArrayList
List<Order> orders = new ArrayList<>();  // 默认容量 10（延迟分配）

for (String line : csvLines) {       // csvLines.size() ≈ 1_000_000
    orders.add(parseOrder(line));     // 第 11 次 add 触发第一次扩容
}

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    // 默认初始容量（无参构造首次 add 时的目标容量）
    private static final int DEFAULT_CAPACITY = 10;

    // 两个共享的空数组哨兵（见下文，是面试高频点）
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // 底层存储数组——ArrayList 的全部秘密都在这里
    transient Object[] elementData;

    // 当前元素个数（不是数组长度！）
    private int size;
}

public ArrayList() {                    // 无参：指向默认哨兵，容量 0
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];  // 立即分配
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;           // 显式 0 容量
    } else {
        throw new IllegalArgumentException(
            "Illegal Capacity: " + initialCapacity);  // 负数直接拒绝
    }
}

public ArrayList(Collection<? extends E> c) {  // 复制构造：先 toArray 再判断类型
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray() 可能返回 Object[] 以外的类型，需要重新拷贝
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // ① 扩容检查：需要的最小容量 = size + 1
    elementData[size++] = e;             // ③ 写入元素并自增 size
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// ② 关键：只有无参构造创建的列表（指向默认哨兵）才放大到 10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);  // 首次 add → max(10, 1) = 10
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  // 结构修改计数：迭代器/视图靠它做 fail-fast 校验
    if (minCapacity - elementData.length > 0)  // 容量不足才真正扩容
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code：每一处比较都防溢出
    int oldCapacity = elementData.length;

    // ★ 核心公式：右移 1 位 = 整除 2（向下取整）
    // newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity × 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // 如果 1.5 倍还不够（比如 addAll 一次要加很多），直接用请求的最小容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    // 防止溢出：接近 Integer.MAX_VALUE 时的安全处理
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // Arrays.copyOf 内部调用 System.arraycopy → 真正的开销在这里
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// 数组长度上限：给对象头留 8 个 int 的余量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0)  // 溢出为负：说明请求容量超过了 int 上限
        throw new OutOfMemoryError("Required array size too large");
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

// native 方法，由 JVM 用 C/C++ 实现
public static native void arraycopy(
    Object src,   int srcPos,    // 源数组 + 起始位置
    Object dest,  int destPos,   // 目标数组 + 起始位置
    int length                     // 要拷贝的元素个数
);

// 方式 1：构造时指定初始容量（最推荐）
List<Order> orders = new ArrayList<>(1_000_000);

// 方式 2：对已创建的 ArrayList 调用 ensureCapacity
ArrayList<Order> orders2 = new ArrayList<>();
orders2.ensureCapacity(1_000_000);

// ensureCapacity 源码（JDK 8）：不是恰好扩到 minCapacity，而是走 grow() 的 1.5 倍逻辑
public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length) {
        ensureExplicitCapacity(minCapacity);  // modCount++ 后调用 grow(minCapacity)
    }
}

// 若 minCapacity 远大于 1.5 倍结果，grow() 里的兜底分支会直接用 minCapacity

// addAll 内部：先算好总容量，只扩容一次、只拷贝一次
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);   // ★ 一次性把容量给够
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

// 对比：100 万条逐条 add → 29 次扩容、243 万次拷贝
// 100 万条一次 addAll → 0 次扩容、100 万次拷贝（只 copy 一次）

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        // 删除中间元素：把后面的元素整体前移一格（又是 O(n)）

    elementData[--size] = null;  // 尾部槽位置 null：帮 GC 回收（JDK 8 修复）
    return oldValue;
}

public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;   // 逐槽置 null，size 清零
    size = 0;
}

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA                    // 空列表：回到共享哨兵
            : Arrays.copyOf(elementData, size);  // 缩到恰好 size
    }
}

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    transient int size = 0;
    transient Node<E> first;   // 头节点引用
    transient Node<E> last;    // 尾节点引用

    private static class Node<E> {
        E item;
        Node<E> next;   // 后继
        Node<E> prev;   // 前驱
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element; this.next = next; this.prev = prev;
        }
    }
}

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);              // 尾部：O(1)
    else
        linkBefore(element, node(index));  // 中间：先 O(n) 定位，再 O(1) 挂接
}

// 双向二分定位：从头还是从尾走，取决于 index 离哪头近
Node<E> node(int index) {
    if (index < (size >> 1)) {          // index < size/2：从头走
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                          // 否则从尾走
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

// ① 索引 for：直接数组下标访问，零迭代器对象
for (int i = 0; i < list.size(); i++) {
    String s = list.get(i);      // 编译后就是 elementData[i]（RandomAccess）
}

// ② for-each：编译成 Iterator.hasNext()/next()
for (String s : list) {        // 创建 ArrayList.Itr，每次 next 都校验 modCount
}

// ③ stream().forEach：走 Spliterator + 方法句柄
list.stream().forEach(s -> { ... });  // ArrayListSpliterator 按索引区间批量消费

// ④ 容易被忽略的第 4 种：list.forEach（Iterable 默认方法被 ArrayList 重写）
list.forEach(s -> { ... });           // 索引循环 + lambda，无迭代器对象

// for-each 编译产物用的迭代器：每次 next() 都做 fail-fast 校验
public E next() {
    checkForComodification();        // ① 先校验 modCount == expectedModCount
    int i = cursor;
    if (i >= size) throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length) throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

// list.forEach（JDK 8 重写）：索引循环，每次迭代条件里都带 modCount 校验
public void forEach(Consumer<? super E> action) {
    final int expectedModCount = modCount;
    final int size = this.size;
    for (int i = 0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

// stream().forEach 的 Spliterator：先记录 expectedModCount，整段遍历后统一校验
// （ArrayListSpliterator.forEachRemaining：循环里只做索引推进，结束后才检查 modCount）

// ✓ 从数据库查询结果转换
List<UserVO> voList = new ArrayList<>(entityList.size());
for (UserEntity e : entityList) {
    voList.add(toVO(e));
}

// ⚠ 注意：Collectors.toList() 内部只是 new ArrayList<>()，并没有预分配！
List<String> names = users.stream()
    .map(User::getName)
    .collect(Collectors.toList());   // 数据量大时仍会经历多次扩容

// ✓ 想要预分配，用 toCollection 指定容量
List<String> names2 = users.stream()
    .map(User::getName)
    .collect(Collectors.toCollection(() -> new ArrayList<>(expectedSize)));

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
List<String> sub = list.subList(1, 3);  // [b, c] — 这是视图，不是副本

sub.set(0, "B");
System.out.println(list);  // [a, B, c, d] ← 原列表也被修改了！

list.add("e");
sub.get(0);  // ✗ 抛出 ConcurrentModificationException
// 原因：subList 持有原列表的 modCount，原列表结构变化导致不一致

// ✓ 安全做法：需要独立副本就 new 一份
List<String> copy = new ArrayList<>(list.subList(1, 3));

// Arrays.asList() → 返回 Arrays$ArrayList（固定大小，不能 add/remove）
List<String> fixed = Arrays.asList("a", "b");
fixed.add("c");   // ✗ UnsupportedOperationException
fixed.set(0, "A"); // ✓ 可以修改元素（底层就是原数组的包装）

// List.of() (Java 9+) → 真正的不可变列表
List<String> immutable = List.of("a", "b");
immutable.add("c");   // ✗ UnsupportedOperationException
immutable.set(0, "A"); // ✗ UnsupportedOperationException
// List.of() 还不允许 null 元素！

// new ArrayList<>(Arrays.asList(...)) → 可变副本
List<String> mutable = new ArrayList<>(Arrays.asList("a", "b"));
mutable.add("c");   // ✓ 完全自由

ArrayList<String> buffer = new ArrayList<>(10000);
// ... 添加数据，最终只用了 200 个槽位
buffer.trimToSize();  // capacity 从 10000 缩为 200，释放多余内存

// 典型场景：长期存活的大列表，填充后不再修改

// ✗ 正序按索引删：删除后元素前移，i 自增会跳过下一个 → 漏删/越界
for (int i = 0; i < list.size(); i++) {
    if (matches(list.get(i))) list.remove(i);
}

// ✓ 方案 1：倒序删（元素前移不影响已扫描部分）
for (int i = list.size() - 1; i >= 0; i--) {
    if (matches(list.get(i))) list.remove(i);
}

// ✓ 方案 2：removeIf（JDK 8+，内部用迭代器，最优雅）
list.removeIf(this::matches);

// ✓ 方案 3：迭代器 remove（需要遍历过程中做别的判断时）
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (matches(it.next())) it.remove();
}

// Q1: new ArrayList<>(0) 和 new ArrayList<>() 有区别吗？
// A: 有。前者指向 EMPTY_ELEMENTDATA，首次 add 只扩到 1；
//    后者指向 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，首次 add 扩到 10。

// Q2: ArrayList 最多能装多少元素？
// A: 理论上 Integer.MAX_VALUE，但 MAX_ARRAY_SIZE = MAX_VALUE - 8，
//    实际受堆大小限制，接近上限必然 OOM。

// Q3: remove() 之后内存会变小吗？
// A: 不会，elementData.length 不变；JDK 8 起尾部槽位置 null 帮助 GC。
//    要释放容量必须显式 trimToSize()。

// Q4: for-each 里 list.remove(x) 会怎样？
// A: 抛 ConcurrentModificationException（modCount 不匹配）；
//    iterator.remove() 可以，它会同步 expectedModCount。

// Q5: stream().forEach 和 list.forEach 有什么区别？
// A: 前者走 Spliterator（可并行、fail-fast 延迟暴露、不保序 in parallel），
//    后者是 ArrayList 重写的索引循环（每次迭代校验 modCount）。