本篇內容包括：ArrayList 概述、ArrayList 的擴容機制（包含源碼部分）、如何在遍歷 ArrayList 時正確的移除一個元素、ArrayList 的構造方法及常用方法、關于 Array 與 ArrayList 的區別、關于 CopyOnWriteArrayList、關于 Fail Fast 與 Fail Safe 機制！

---

---

一、ArrayList 概述

ArrayList 是最常用的 List 實現類，內部是通過數組實現的，它允許對元素進行快速隨機訪問。數組的缺點是每個元素之間不能有間隔，當數組大小不滿足時需要增加存儲能力，就要將已經有數組的數據復制到新的存儲空間中。當從 ArrayList 的中間位置插入或者刪除元素時，需要對數組進行復制、移動、代價比較高。因此，它適合隨機查找和遍歷，不適合插入和刪除。

ArrayList 是基于數組實現的，相當于動態數組，相當于動態數組，其容量能動態增長，類似于 C 語言中的動態申請內存，動態增長內存。

ArrayList 的每個實例都有一個容量，該容量是指用來存儲列表元素的數組的大小。它總是大于等于列表的大小。隨著向 ArrayList 中不斷添加元素，其容量也自動增長。自動增長會帶來數據向新數組的重新拷貝，因此，如果可預知數據量的多少，可在構造 ArrayList 時指定其容量。

ArrayList 在被添加大量元素前，應用程序可以使用 ensureCapacity() 操作來指定 ArrayList 實例的容量，這可以減少遞增式再分配的數量。

ArrayList 是非線程安全的，只能在單線程環境下使用，多線程環境下可以考慮用 Collections.synchronizedList(List l) 函數返回一個線程安全的 ArrayList 類，也可以使用 java.util.concurrent 并發包下的 CopyOnWriteArrayList 類。

---

二、ArrayList 的擴容

1、ArrayList 的擴容機制（源碼）

ArrayList 底層是一個 Object 數組 elementData，用于存放插入的數據：

private transient Object[] elementData;		// 存儲ArrayList中的元素
/*** 定義元素個數*/
private int size();

我們知道，數組需要使用著一塊連續的內存空間，因此數組的大小一旦被規定就無法改變。那如果我們不斷的往里面添加數據的話，ArrayList 是如何進行擴容的呢 ？

public boolean add(E e) {// 確認elementData容量是否足夠ensureCapacityInternal(size + 1);  // 第一次調用add()方法時，size=0elementData[size++] = e;return true;}

ArrayList 添加元素時會先調用 ensureCapacityInternal(int minCapacity) 方法，對數組容量進行檢查，判斷剩余空間是否足夠，不夠時則進行擴容

private void ensureCapacityInternal(int minCapacity) {// 如果elementData為"{}"即第一次調用add(E e)，重新定義minCapacity的值，賦值為DEFAULT_CAPACITY=10// 即第一次調用add(E e)方法時，定義底層數組elementData的長度為10if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}// 判斷是否需要擴容ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {modCount++;// 第一次進入時，minCapacity=10,elementData.length=0,對數組進行擴容// 之后再進入時，minCapacity=size+1，elementData.length=10(每次擴容后會改變)，// 需要minCapacity>elementData.length成立，才能擴容if (minCapacity - elementData.length > 0){grow(minCapacity);}
}

ArrayList 通過 grow(minCapacity) 方法對數組進行擴容

private void grow(int minCapacity) {// 將數組長度賦值給oldCapacityint oldCapacity = elementData.length;// 將oldCapacity右移一位再加上oldCapacity，即相當于newCapacity=1.5oldCapacity(不考慮精度損失)int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果newCapacity還是小于minCapacity，直接將minCapacity賦值給newCapacityif (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 特殊情況：newCapacity的值過大，直接將整型最大值賦給newCapacity，// 即newCapacity=Integer.MAX_VALUEif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 將elementData的數據拷貝到擴容后的數組elementData = Arrays.copyOf(elementData, newCapacity);
}// 如果大于臨界值，進行整型最大值的分配
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) {// overflowthrow new OutOfMemoryError();}return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

總結：ArrayList 在添加元素時，會進行一個判斷，當「元素個數+1> 當前數組長度（size + 1 > elementData.length）」時，進行擴容，擴容后的數組大小是原大小的 1.5 倍（oldCapacity + (oldCapacity >> 1)）。最后將舊數組進行復制（調用 Arrays.copyof()，再調用 System.arraycopy() ），達到擴容的目的，此時新舊列表的 size 大小相同，但 elementData 的長度即容量不同。

2、在遍歷 ArrayList 時移除一個元素

在遍歷 ArrayList 時移除一個元素，這是一個比較經典的面試題，這里最常用的有 2 種方式：

方式一：在 for 循環中使用倒序遍歷 remove 刪除元素.

假設按照從 0 到 size-1 下標來刪有相鄰且相同的兩個元素，刪除第一個，數組長度會 -1 并且所有元素往前移動一位，那么第二個就到第一個元素的位置，此時控值 for 循環的下標 i 已經 +1 ，相當于直接就跳過了第二個重復元素，而倒敘可以避免此類情況。

方式二：使用迭代器遍歷 ArrayList 并刪除元素（推薦）。

Eg：

List<String> strs = new ArrayList<>();
strs.add("1")
strs.add("2")
strs.add("3")
strs.add("4")
strs.add("5")
strs.add("6")Iterator<String> iter = strs.iterator();
while(iter.hasNext()) {if (iter.next().toString().equals("1")) {iter.remove();}
}
System.out.println(strs);

---

三、ArrayList 的使用

1、構造方法

方法名	方法說明
public ArrayList()	無參構造函數，此構造函數用于創建一個空列表，其初始容量足以容納10個元素
public ArrayList(int initialCapacity)	此構造函數用于創建具有初始容量的空列表
public ArrayList(Collection<? extends E> c)	此構造函數用于創建包含指定集合的元素的列表

2、常用方法

方法名	方法說明
boolean add(E e)	此方法將指定的元素追加到此列表末尾
void add(int index, E element)	此方法將指定的元素插入此列表中的指定位置
boolean addAll(Collection<? extends E> c)	此方法按指定集合迭代器的返回順序將指定集合中所有元素加到列表末尾
boolean addAll(int index, Collection<? extends E> c)	此方法從指定位置開始將指定集合中的所有元素插入此列表
E get(int index)	此方法返回此列表中指定位置的元素
E set(int index, E element)	此方法返回此列表中指定位置的元素，并使用參數中的元素進行替換
E remove(int index)	此方法返回此列表中指定位置的元素，并刪除此指定位置的元素
boolean remove(Object o)	此方法從該列表中刪除指定元素的第一個匹配項（如果存在）
void clear()	此方法將從此列表中刪除所有元素
Object clone()	此方法返回此ArrayList實例的淺表副本
boolean contains(Object o)	如果此列表包含指定的元素，則此方法返回true
boolean isEmpty()	如果此列表為空，則此方法返回true
void ensureCapacity(int minCapacity)	此方法增加了此列表的容量
int size()	此方法返回此列表中的元素數
Object[] toArray()	此方法以適當的順序（從第一個元素到最后一個元素）返回包含此列表中所有元素的數組
<T> T[] toArray(T[] a)	此方法以適當的順序（從第一個元素到最后一個元素）返回包含此列表中所有元素的數組; 返回數組的運行時類型是指定數組的運行時類型
void trimToSize()	此方法將此ArrayList實例的容量修剪為列表的當前大小
void sort(Comparator<? super E> c)	此方法對列表內對象，以指定方式進行排序
List<E> subList(int fromIndex, int toIndex)	此方法將截取集合的一部分并返回一個List集合

---

四、相關知識點

1、關于 Array 與 ArrayList 的區別

• （包含類型）Array 既可以包含基本類型，也可以包含對象類型；而 ArrayList 只能包含對象類型。
• （實例聲明）Array 作為變量在聲明的時必須進行實例化（至少得初始化數組的大小），而 ArrayList 可以只是先聲明。
• （初始大小）Array 對象創建后的數組大小是固定的，而 ArrayList 的大小可以動態指定，也就是說該對象的空間可以任意增加。
• （方法特性）Arraylist 提供了更多的方法和特性，比如添加全部addAll()，刪除全部removeAll()，返回迭代器iterator()等等。

2、關于 CopyOnWriteArrayList

Java 并發包中的并發 List 只有 CopyOnWriteArrayList。CopyOnWriteArrayList 是一個線程安全的 ArrayList，對其進行的修改操作都是在底層的一個復制數組（快照）上進行的，也就是使用了寫時復制策略。

寫時復制（CopyOnWrite，簡稱 COW）思想是計算機程序涉及領域中的一種優化策略。其核心思想是，如果多個調用者（Callers）同時要求相同的資源（如內存或者磁盤上的數據存儲），他們會共同獲取相同的指針指向相同的資源，直到某個調用者視圖修改資源內容時，系統才會真正復制一份專用的副本給調用者，而其他調用者所見到的最初的資源仍然保持不變。這個過程對其他調用者都是透明的。樣做的好處就是可以對 CopyOnWrite 容器進行并發的讀而不需要加鎖，因為當前容器不會被修改。

從 Jdk1.5 開始 Java 并發包里提供了兩個使用 CopyOnWrite 機制實現的并發容器，它們是 CopyOnWriteArrayList 和 CopyOnWriteArraySet。

CopyOnWriteArrayList 中 add 方法添加的時候是需要加鎖的，保證同步，避免了多線程寫的時候復制出多個副本。讀的時候不需要加鎖，如果讀的時候有其他線程正在向 CopyOnWriteArrayList 添加數據，還是可以讀到舊的數據。

寫時復制的缺點：

• 內存占用問題。由于 CopyOnWrite 的寫時復制機制，在進行寫操作的時候，內存里會同時駐扎兩個對象的內存。
• CopyOnWrite 容器不能保證數據的實時一致性，可能讀取到舊數據。

3、關于 Fail Fast

Fail Fast 是 Java 集合的一種錯誤機制。當多個線程對同一個集合進行操作時，就有可能會產生 fast-fail 事件。例如：當線程 A 正通過 iterator 遍歷集合，另一個線程 B 修改了集合的內容，此時 modCount（記錄集合操作過程的修改次數）會加 1，不等于 expectedModCount，那么線程 A 訪問集合的時候，就會拋出 Concurrent Modification Exception，產生 fast-fail 事件。邊遍歷邊修改集合也會產生 fast-fail 事件。

解決方法：

• 使用 Colletions.synchronizedList 方法或在修改集合內容的地方加上 synchronized。這樣的話，增刪集合內容的同步鎖會阻塞遍歷操作，缺點是會影響性能。
• 使用 CopyOnWriteArrayList 來替換 ArrayList。在對 CopyOnWriteArrayList 進行修改操作的時候，會拷貝一個新的數組，對新的數組進行操作，操作完成后再把引用移到新的數組。

4、關于 Fail Safe

Fail Safe 也是 Java 集合的一種機制，采用安全失敗機制的集合容器（Eg：CopyOnWriteArrayList）在遍歷時不是直接在集合內容上訪問的，而是先復制原有集合內容，在拷貝的集合上進行遍歷。

• 原理：由于迭代時是對原集合的拷貝進行遍歷，所以在遍歷過程中對原集合所作的修改并不能被迭代器檢測到，所以不會觸發 Concurrent Modification Exception。
• 缺點：基于拷貝內容的優點是避免了 Concurrent Modification Exception，但同樣地，迭代器并不能訪問到修改后的內容，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發生的修改迭代器是不知道的。

Ps：java.util.concurrent 包下的容器都是 Fail Safe 的，可以在多線程下并發使用，并發修改。