一、ArrayList底层数据结构

📦 核心结构

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    // 底层存储数组（transient表示不参与序列化）
    transient Object[] elementData;
    
    // 实际元素个数
    private int size;
    
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    
    // 空数组常量
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    private static final Object[] EMPTY_ELEMENTDATA = {};
}

关键点：

• elementData：真正存储元素的数组
• size：当前数组中元素的实际数量
• DEFAULT_CAPACITY：默认初始容量为10

完整扩容流程时序图

📊 场景：添加第11个元素（触发扩容）

二、分步详解（附源码）

🔍 步骤1：客户端调用add()方法

// 客户端代码
ArrayList<String> list = new ArrayList<>();
list.add("Hello");  // 触发扩容流程

时序说明：

• 客户端调用list.add("Hello")
• 进入ArrayList的add(E e)方法

---

🔍 步骤2：调用ensureCapacityInternal()

// ArrayList源码
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保容量足够
    elementData[size++] = e;           // 添加元素
    return true;
}

时序说明：

• add()方法首先调用ensureCapacityInternal(size + 1)
• 参数minCapacity = size + 1（所需最小容量）

---

🔍 步骤3：计算所需容量（calculateCapacity）

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果是空数组，返回默认容量10和minCapacity的较大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

时序说明：

• 判断当前数组是否为空数组
• 首次添加：返回max(10, minCapacity) → 10
• 后续添加：直接返回minCapacity

---

🔍 步骤4：确保显式容量（ensureExplicitCapacity）

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  // 修改次数+1（用于fail-fast机制）
    
    // 如果所需容量超过当前数组长度，触发扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

时序说明：

• modCount++：记录修改次数（用于迭代器的fail-fast检查）
• 判断是否需要扩容：minCapacity > elementData.length

---

🔍 步骤5：扩容核心逻辑（grow方法）

private void grow(int minCapacity) {
    // 1. 获取旧容量
    int oldCapacity = elementData.length;
    
    // 2. 计算新容量 = 旧容量 + 旧容量/2（即1.5倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 3. 如果1.5倍仍不够，直接使用所需容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 4. 处理最大容量限制
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // 5. 复制数组到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

时序说明：

1. 获取当前数组长度oldCapacity
2. 计算新容量：oldCapacity + (oldCapacity >> 1)（位运算相当于除以2）
3. 检查新容量是否满足需求，不足则用minCapacity
4. 检查是否超过最大限制Integer.MAX_VALUE - 8
5. 调用Arrays.copyOf()创建新数组并复制元素

---

🔍 步骤6：数组复制（Arrays.copyOf）

// Arrays.copyOf底层调用System.arraycopy（native方法）
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

时序说明：

• 创建新数组（长度为newCapacity）
• 调用System.arraycopy()（native方法，高效复制）
• 返回新数组，替换原elementData

---

🔍 步骤7：添加元素并返回

// 回到add()方法
elementData[size++] = e;  // 将元素放入数组
return true;              // 返回成功

时序说明：

• 扩容完成后，将元素放入elementData[size]位置
• size++：元素计数+1
• 返回true，流程结束

三、不同场景的扩容时序图

📊 场景1：首次添加元素（从空数组到容量10）

关键点：

• 初始数组为空{}
• calculateCapacity返回10（默认容量）
• grow中1.5倍计算为0，不足则直接用10

📊 场景2：第11个元素添加（1.5倍扩容）

关键点：

• 旧容量10 → 新容量15（10 + 5）
• System.arraycopy复制10个元素到新数组
• 剩余5个位置为null

---

📊 场景3：批量添加触发扩容（addAll）

关键点：

• addAll一次性添加多个元素
• 1.5倍扩容后仍不足，直接使用所需容量20

总结：扩容流程关键点

步骤	方法	关键操作	时间复杂度
1	add()	调用扩容检查	O(1)
2	ensureCapacityInternal()	计算所需容量	O(1)
3	calculateCapacity()	首次返回10，后续返回minCapacity	O(1)
4	ensureExplicitCapacity()	判断是否需要扩容	O(1)
5	grow()	计算新容量（1.5倍）	O(1)
6	Arrays.copyOf()	数组复制	O(n)
7	add()	添加元素	O(1)

🎯 核心要点

1. 扩容触发条件：size + 1 > elementData.length
2. 扩容倍数：1.5倍（old + old/2）
3. 首次扩容：空数组 → 容量10
4. 扩容成本：数组复制是**O(n)**操作
5. 性能优化：预估容量可避免多次扩容