ArrayList 是 Java 集合框架中使用頻率最高的動態陣列實現。本文基於 JDK 1.8+ 原始碼，深度剖析其核心屬性、擴容機制、核心方法實現與效能特徵。
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable { // 序列化版本號 private static final long serialVersionUID = 8683452581122892189L; // 預設初始容量 private static final int DEFAULT_CAPACITY = 10; // 空陣列實例（共享，節省記憶體） private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 底層儲存陣列（transient 不序列化，由 writeObject/readObject 自定義） transient Object[] elementData; // 實際元素數量 private int size; // 修改次數（用於 fail-fast 機制） protected transient int modCount = 0; }
// 無參建構子：延遲初始化，首次 add 時才分配 DEFAULT_CAPACITY
public ArrayList() {
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;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
// Collection 建構子
public ArrayList(Collection c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
} else {
elementData = EMPTY_ELEMENTDATA;
}
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 確保容量
elementData[size++] = e; // 新增元素
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0) {
grow(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 int hugeCapacity(int minCapacity) {
if (minCapacity < 0) throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
| 特性 | 說明 |
|---|---|
| 增長因子 | 1.5 倍（oldCapacity + oldCapacity/2） |
| 首次擴容 | 無參建構子首次 add 時從 0 → 10 |
| 複製開銷 | Arrays.copyOf 為 native 方法，效能較好但仍需避免頻繁擴容 |
| 最大容量 | Integer.MAX_VALUE - 8（約 2GB 陣列限制） |
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
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);
elementData[--size] = null; // 釋放引用，協助 GC
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null;
}
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
迭代器建立時記錄 expectedModCount = modCount，遍歷過程中若 modCount 變化則拋出異常。注意：這是檢測邏輯錯誤的輔助機制，非執行緒安全保證。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
大量刪除元素後調用可釋放未使用記憶體。
public void sort(Comparator c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
modCount++;
}
public Object clone() {
try {
ArrayList v = (ArrayList) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
僅複製陣列結構，元素物件共享引用。深複製需自行實作。
| 操作 | 時間複雜度 | 說明 |
|---|---|---|
| get/set | O(1) | 隨機存取極快 |
| add(尾部) | O(1) 攤還 | 偶爾觸發擴容 O(n) |
| add(指定位置) | O(n) | 需移動後續元素 |
| remove(指定位置) | O(n) | 需移動後續元素 |
| contains/indexOf | O(n) | 線性搜尋 |
| 遍歷 | O(n) | for/for-each/iterator 皆可 |
new ArrayList<>(expectedSize) 減少擴容開銷Collections.unmodifiableList(list) 或 Java 10+ List.copyOf(list)ArrayList 以動態陣列為核心，提供優異的隨機存取效能與緊湊記憶體佈局。理解其擴容策略、Fail-Fast 機制與各操作複雜度，能幫助開發者在正確場景下發揮最大效能。
