一、ArrayList 簡介

ArrayList 是 Java 集合框架中基于數組實現的可變長度列表，其核心特性是：

• 支持隨機訪問（通過索引）
• 支持動態擴容
• 插入/刪除效率較低（非尾部操作）

---

二、底層數據結構

// JDK 11+
transient Object[] elementData; // 實際存儲元素的數組

---

三、容量與初始狀態

默認構造函數

public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

默認初始值為一個空數組，不分配空間，首次添加元素時分配容量。

---

指定初始容量

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];}
}

開發中建議：盡量提前估算容量，減少擴容次數

---

四、擴容機制核心原理

觸發條件：

當新增元素導致 size > elementData.length 時觸發擴容。

---

擴容策略：

新容量 = 原容量 + (原容量 >> 1) = 原容量 * 1.5

例如：

• 當前容量 10 → 擴容后為 15
• 當前容量 15 → 擴容后為 22

---

五、源碼詳解（以 JDK 8 為例）

添加元素核心方法：

public boolean add(E e) {ensureCapacityInternal(size + 1); // 確保有容量elementData[size++] = e;return true;
}

---

ensureCapacityInternal(int minCapacity)

private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);
}

---

ensureExplicitCapacity(int minCapacity)

private void ensureExplicitCapacity(int minCapacity) {modCount++; // fail-fast 標識if (minCapacity - elementData.length > 0)grow(minCapacity); // 核心：擴容方法
}

---

grow(int minCapacity)

private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 擴容1.5倍if (newCapacity - minCapacity < 0)newCapacity = minCapacity; // 不夠就按最小需求擴if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity); // 復制數組
}

---

六、最大容量限制

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

超過該限制會拋出 OutOfMemoryError。

---

七、擴容操作的成本

• 使用 Arrays.copyOf() 進行數組復制，時間復雜度為 O(n)
• 多次擴容會引起頻繁復制，影響性能

---

八、如何避免頻繁擴容？

方式一：指定初始容量

List<String> list = new ArrayList<>(1000); // 預估大小

方式二：批量添加前調用 ensureCapacity

list.ensureCapacity(10000); // 批量操作前手動擴容

---

九、總結對比：不同初始化方式

構造方式	初始容量	首次添加觸發擴容	是否推薦
new ArrayList()	0	是（容量為10）	?? 慎用
new ArrayList(20)	20	否	? 推薦
new ArrayList(list)	原容量	否	? 推薦

---

十、擴容流程圖

graph TD
A[add(e)] --> B[ensureCapacityInternal]
B --> C[ensureExplicitCapacity]
C --> D{容量夠嗎？}
D -- 是 --> E[添加成功]
D -- 否 --> F[grow 擴容]
F --> G[復制新數組]
G --> E

---

十一、常見面試題

Q1：ArrayList 每次擴容增長多少？

• 默認是 1.5 倍（即 old + old/2）

Q2：頻繁 add 元素時怎么優化？

• 預估大小，構造時指定初始容量
• 或調用 ensureCapacity

Q3：ArrayList 最大能容納多少元素？

• Integer.MAX_VALUE - 8 ≈ 2^31 - 9

---

十二、總結

點位	描述
數據結構	動態數組 Object[]
擴容觸發	新增元素導致數組容量不夠
擴容增長率	1.5倍
拷貝機制	Arrays.copyOf() 整體復制
最大容量	Integer.MAX_VALUE - 8
性能建議	盡量設定初始容量，避免頻繁擴容