⭐ 题目日期：

字节 - 2024/12/10

📝 题解：

一、底层数据结构与扩容触发条件

1. 底层结构
   ArrayList内部维护一个Object[] elementData数组，存储实际元素。
   • 默认初始容量：10（通过无参构造器创建时）。
   • 当前元素数量：通过size变量记录，size与实际数组长度（elementData.length）可能不同。

2. 扩容触发条件
   当向ArrayList添加元素时（如add(E e)方法），会先检查是否需要扩容：

   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // 检查是否需要扩容
       elementData[size++] = e;
       return true;
   }

   • 触发条件：当size + 1 > elementData.length（即当前数组已满时）。

---

二、扩容流程与容量计算

1. 扩容步骤

• 步骤1：计算新容量。
默认扩容为原容量的1.5倍（通过位运算优化计算）。
java int newCapacity = oldCapacity + (oldCapacity >> 1); // oldCapacity >> 1 = oldCapacity / 2 • 步骤2：处理极端情况（如初始容量为1）。
若新容量仍不足（例如从1扩容到1.5后仍为1），则直接设置新容量为所需的最小容量（minCapacity = size + 1）。
• 步骤3：若新容量超过最大数组限制（Integer.MAX_VALUE - 8），调用hugeCapacity()处理（可能抛出OutOfMemoryError）。
• 步骤4：创建新数组并复制元素。
使用Arrays.copyOf(elementData, newCapacity)将旧数组数据复制到新数组。

2. 容量计算示例

原容量（oldCapacity）	新容量（newCapacity）
10	10 + 5 = 15
15	15 + 7 = 22
1	1 + 0 = 1 → 扩容到2

---

三、性能分析与优化建议

1. 时间复杂度

• 单次扩容：时间复杂度为O(n)（需复制整个旧数组）。
• 均摊时间复杂度：连续插入n个元素时，扩容的均摊时间复杂度为O(1)（类似动态数组的均摊分析）。

2. 优化建议

• 预先指定初始容量：
若已知元素数量，使用ArrayList(int initialCapacity)构造器避免多次扩容。
java List<Integer> list = new ArrayList<>(1000); // 直接初始化容量为1000 • 手动扩容：
使用ensureCapacity(int minCapacity)提前扩容，减少后续添加元素的扩容次数。
java list.ensureCapacity(1000); // 提前扩容至至少1000

---

四、源码关键方法解析

1. ensureCapacityInternal(int minCapacity)
   • 确定最小容量（默认初始容量为10）。
   • 调用grow(int minCapacity)执行扩容。
2. grow(int minCapacity)
   • 计算新容量（1.5倍旧容量），处理边界情况。
   • 复制旧数组到新数组。

---

五、面试扩展点

1. 与Vector的扩容对比

• Vector：默认扩容为原容量的2倍，且方法同步（线程安全但性能差）。
• ArrayList：扩容1.5倍，非线程安全但性能更高。

2. 高频插入场景的替代方案

• 频繁头部插入：使用LinkedList（基于链表，插入时间复杂度O(1)）。
• 线程安全需求：使用CopyOnWriteArrayList（写时复制）或Collections.synchronizedList()。

3. 内存与性能权衡

• 空间浪费：ArrayList可能预留未使用的容量（如扩容后未填满）。
• 时间效率：扩容牺牲单次插入性能，但均摊后整体高效。

---

六、示例代码

// 默认初始容量为10
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 20; i++) {
    list.add(i); 
    // 第11次插入时触发扩容：10 → 15
    // 第16次插入时再次扩容：15 → 22
}