ArrayList 是 Java 集合框架中最常用的數據結構之一，它基于動態數組實現，提供了高效的隨機訪問和動態擴容能力。本文將深入分析 ArrayList 的動態擴容機制，探討其源碼實現、擴容策略、性能影響以及相關的優化策略。
ArrayList 的內部結構主要由以下幾個部分組成：
elementData: 一個 Object[] 數組，用于存儲實際的數據元素。size: 一個 int 類型的變量，表示當前 ArrayList 中實際存儲的元素數量。modCount: 一個 int 類型的變量，用于記錄 ArrayList 結構修改的次數，主要用于迭代器的快速失敗機制。transient Object[] elementData; // 存儲元素的數組
private int size; // 當前元素數量
protected transient int modCount = 0; // 結構修改次數
ArrayList 提供了多個構造函數，允許用戶指定初始容量或使用默認容量。
// 默認構造函數，初始容量為10
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);
}
}
// 使用集合初始化的構造函數
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList 的添加操作主要通過 add(E e) 方法實現。該方法首先檢查當前數組是否已滿，如果已滿則觸發擴容操作，然后將新元素添加到數組的末尾。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 確保容量足夠
elementData[size++] = e; // 添加元素
return true;
}
ArrayList 的擴容操作在以下情況下觸發：
add(E e) 方法時，如果當前數組已滿（即 size == elementData.length），則需要擴容。addAll(Collection<? extends E> c) 方法時，如果當前數組容量不足以容納新添加的所有元素，則需要擴容。ArrayList 的擴容過程主要通過 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); // 復制元素到新數組
}
在擴容過程中，Arrays.copyOf() 方法用于將原數組中的元素復制到新數組中。該方法內部調用了 System.arraycopy()，這是一個本地方法，具有較高的性能。
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;
}
ArrayList 的默認擴容策略是將容量擴大為原來的 1.5 倍。這種策略在大多數情況下能夠平衡內存使用和性能。
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量為原容量的1.5倍
用戶可以通過構造函數指定 ArrayList 的初始容量，從而避免頻繁擴容。
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);
}
}
在某些場景下，用戶可以通過手動調整 ArrayList 的容量來優化性能。例如，在已知需要添加大量元素時，可以提前調用 ensureCapacity(int minCapacity) 方法，避免頻繁擴容。
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length) {
grow(minCapacity);
}
}
ArrayList 的擴容操作的時間復雜度為 O(n)，其中 n 是當前數組的長度。這是因為在擴容過程中需要將原數組中的元素復制到新數組中。
ArrayList 的擴容操作的空間復雜度為 O(n)，其中 n 是新數組的長度。這是因為在擴容過程中需要創建一個新的數組來存儲元素。
頻繁的擴容操作會導致性能下降，因為每次擴容都需要復制大量元素。因此，在實際使用中，應盡量避免頻繁擴容，可以通過提前設置合適的初始容量或手動調整容量來優化性能。
ArrayList 并沒有提供自動縮容的機制，但用戶可以通過調用 trimToSize() 方法手動將 ArrayList 的容量調整為當前元素數量，從而減少內存占用。
public void trimToSize() {
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
ArrayList 不是線程安全的，如果在多線程環境下使用 ArrayList，可能會導致數據不一致或其他并發問題。為了在多線程環境下使用 ArrayList，可以使用 Collections.synchronizedList() 方法將其包裝為線程安全的列表。
List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());
ArrayList 的動態擴容機制是其高效性能的關鍵之一。通過分析其源碼，我們了解了 ArrayList 的擴容觸發條件、擴容過程、擴容策略以及性能影響。在實際使用中，合理設置初始容量、避免頻繁擴容以及手動調整容量是優化 ArrayList 性能的重要手段。同時，ArrayList 的線程安全性問題也需要在使用時特別注意。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
