注：源碼系列文章主要是對某付費專欄的總結記錄。如有侵權，請聯系刪除。
1 整體架構
ArrayList 整體架構比較簡單，就是一個數組結構，如下圖：
ArrayList 底層數組結構
圖中展示的是長度為 10 的數組，從 1 開始計數，index 表示數組的下標，從 0 開始計數，elementData 表示數組本身，源碼中除了這兩個概念，還有三個基本概念：
- DEFAULT_CAPACITY 表示數組的初始大小，默認是 10；
- size 表示當前數組的大小，類型是 int，沒有使用 volatile 修飾，非線程安全；
- modCount 統(tǒng)計當前數組被修改的版本次數，數組結構有變動，就會加 1。
類注釋
看源碼首先要看注釋，我們看看類注釋上面都說了哪些：
- 允許 put null 值，會自動擴容；
- size、isEmpty、get、set、add 等方法時間復雜度都是 O(1)；
- 是非線程安全的，多線程情況下，推薦使用線程安全類：Collections#synchronizedList；
- 增加 for 循環(huán)，或者使用迭代器迭代過程中，如果數組大小被改變，會快速失敗，拋出異常。
2 源碼解析
2.1 初始化
有三種初始化方法：
- 無參數直接初始化
- 指定大小初始化
- 指定初始數據初始化
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 無參數直接初始化
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] 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) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
除了源碼中的注釋，我們再補充如下：
- ArrayList 無參構造器初始化時，默認大小是空數組，并不是默認的 DEFAULT_CAPACITY 10，10 是在第一次 add 的時候擴容的值 ArrayList.class#224 。
- 指定初始數據初始化時，我們發(fā)現一個這樣子的注釋
see 6260652，這是 Java 的一個 bug，意思是當給定集合內的元素不是 Object 類型時，我們會轉化成 Object 類型（如：ArrayList 源碼中的方法public Object[] toArray() { // ... }）。一般情況下不會觸發(fā)此 bug，只有在下列場景下才會觸發(fā)：ArrayList 初始化之后（元素指定非 Object 類型），再次調用toArray方法得到 Object 數組，并且往 Object 數組賦值時才會觸發(fā)此 bug。演示如下：
// 初始化具體類型(非 Object) 的集合
List<String> list = Arrays.asList("a", "b");
// 調用 toArray 返回 Object 類型數組
Object[] array = list.toArray();
System.out.println(array.getClass().getSimpleName()); // String[]
// 雖然 toArray 返回的是 Object 數組，但是 array 元素的真實類型是 String
// 這里存儲 Object 類型時就會報錯: java.lang.ArrayStoreException: java.lang.Object
array[0] = new Object();
執(zhí)行結果：
String[]
java.lang.ArrayStoreException: java.lang.Object
at com.example.ArrayListExample.toArrayObjectsTest(ArrayListExample.java:26)
官方文檔地址：<a >https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652</a>，發(fā)現該問題已經在 Java 9 中被解決。
2.2 新增和擴容實現
新增主要分為兩步：
- 判斷是否需要擴容，如果需要則執(zhí)行擴容操作；
- 賦值新元素。
源碼如下：
public boolean add(E e) {
// 確保數組大小是否足夠，不夠則執(zhí)行擴容，size 為當前數組的大小
ensureCapacityInternal(size + 1); // Increments modCount!!
// 直接賦值
elementData[size++] = e;
return true;
}
擴容步驟(ensureCapacityInternal)源碼：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 計算 capacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果數組為空，則返回默認容量(10) 和最小容量(比如初始化 List add 一個 element 時 minCapacity 為 1)之間的 max 值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 確保容量足夠
private void ensureExplicitCapacity(int minCapacity) {
// 記錄數組被修改
modCount++;
// 如果我們期望的最小容量大于目前數組的長度，則執(zhí)行擴容操作
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 擴容，并把現有數據拷貝到新的數組中去
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新的容量為舊的容量的 1.5 倍(capacity >> 1 ==> capacity / 2)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新的容量小于我們期望值 minCapacity，則將新的容量值賦值為期望值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新的容量大于 JVM 所能分配的數組的最大值，那么就用 Integer 的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 通過復制進行擴容
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
通過源碼學習我們需要注意以下幾點：
- 擴容的規(guī)則并不是翻倍，而是
原來容量大小 + 原來容量大小的一半，直白來說，擴容后的大小是原來容量的 1.5 倍； - ArrayList 中數組的最大容量是
Integer.MAX_VALUE，超過這個值，JVM 就不會給數組分配內存空間了； - 新增時，并沒有對值進行嚴格的校驗，所以 ArrayList 是允許 null 值的。
在新增和擴容源碼中，下面這點值得我們學習借鑒：
- 源碼在擴容的時候，有數組大小溢出意識，就是說擴容后的數組的大小下界不能小于 0，上界不能大于 Integer.MAX_VALUE，這種意識值得我們學習。（比如：二分查找計算 mid 時，不能使用
(low + high) / 2，而要使用low + (high - low) / 2，因為low + high可能會超過 Integer 的最大值，JDK 之前有這個 bug）
擴容完成之后，賦值是非常簡單的，直接在數組上添加元素即可：elementData[size++] = e。也正是通過這種簡單賦值，沒有任何鎖控制，所以這里的操作是線程不安全的。
2.3 擴容的本質
擴容是通過這行代碼來實現的 Arrays.copyOf(elementData, newCapacity)，這行代碼描述的本質是數組之間的拷貝，擴容會先新建一個符合我們預期容量 newCapacity 的新數組，然后把舊數組的數據拷貝過去，源碼如下：
public static int[] copyOf(int[] original, int newLength) {
int[] copy = new int[newLength];
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
測試如下：
int[] elementData = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
System.out.println("舊的容量：" + oldCapacity);
System.out.println("新的容量：" + newCapacity);
System.out.println("舊的數組：" + JSON.toJSONString(elementData));
// 執(zhí)行擴容操作
elementData = Arrays.copyOf(elementData, newCapacity);
System.out.println("新的數組：" + JSON.toJSONString(elementData));
執(zhí)行結果：
舊的容量：10
新的容量：15
舊的數組：[1,2,3,4,5,6,7,8,9,10]
新的數組：[1,2,3,4,5,6,7,8,9,10,0,0,0,0,0]
2.4 刪除操作
ArrayList 刪除元素有很多種方式，比如根據數組索引刪除、根據值刪除或批量刪除等等，原理和思路都差不多，我們選取根據值刪除方式來進行源碼分析：
public boolean remove(Object o) {
// 如果要刪除的值是 null，找到第一個值是 null 的刪除
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 如果要刪除的不是 null，找到第一個和要刪除的值相等的刪除
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
注意兩點：
- 新增的時候是沒有對 null 進行校驗的，所以刪除的時候也是允許刪除 null 值的；
- 找到值在數組中的索引位置，是通過
equals來判斷的，如果數組元素不是基本類型，需要我們關注 equals 的具體實現。
上面源碼中我們已經找到要刪除元素的索引了，下面根據索引進行元素的刪除：
// 根據索引刪除
private void fastRemove(int index) {
// 記錄數組結構發(fā)生變化
modCount++;
// numMoved 表示刪除 index 位置的元素后，需要從 index 后面移動多少個元素到前面去
// 減 1 是因為 size 是從 1 開始計算的，index 是從 0 開始的，而我們調用 System.arraycopy 時需要的是 length 為數組元素被拷貝的長度值
int numMoved = size - index - 1;
if (numMoved > 0)
// 從數組 index+1 位置開始拷貝，拷貝的起始位置是 index，長度是 numMoved
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 數組size最后一個位置賦值為 null，幫助 GC
elementData[--size] = null; // clear to let GC do its work
}
從源碼中我們可以看出，某一個元素刪除后，為了維護數組結構，我們都會把數組后面的元素往前移動。
測試 demo：
Integer[] elementData = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int size = elementData.length;
System.out.println("原始數據：" + JSON.toJSONString(elementData));
System.out.println("數據長度：" + size);
// 要刪除的值
int key = 5;
// 要刪除的值的索引
int index = Arrays.binarySearch(elementData, key);
System.out.println("要刪除的元素值：" + key);
System.out.println("要刪除的元素索引位置：" + index);
// numMoved: 刪除一個值后，該值后面有多少個值需要往前移動
// 比如這里刪除值 5 之后，后面有 6,7,8,9,10 五個數據值需要移動
// 舊的數組為 [1,2,3,4,5,6,7,8,9,10]，刪除成功后為 [1,2,3,4,6,7,8,9,10,null]，而不是 [1,2,3,4,null,6,7,8,9,10]
int numMoved = size - index - 1;
System.out.println("numMoved:" + numMoved);
if (numMoved > 0) {
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
elementData[--size] = null;
System.out.println("新的數據：" + JSON.toJSONString(elementData));
System.out.println("數據長度：" + size);
執(zhí)行結果：
原始數據：[1,2,3,4,5,6,7,8,9,10]
數據長度：10
要刪除的元素值：5
要刪除的元素索引位置：4
numMoved:5
新的數據：[1,2,3,4,6,7,8,9,10,null]
數據長度：9
疑問：
- 刪除 index 為值的元素時，為何要將 index 后面的元素向前移動，再將最后一位賦值為 null。而不是不移動 index 后面的元素，直接賦值 index 位置為 null 呢？是為了讓數組看起來更連續(xù)嗎？
2.5 迭代器
如果要自己實現迭代器，實現 java.util.Iterator 類即可，ArrayList 也是這樣做的，我們來看看迭代器的幾個重要參數：
// 迭代過程中，下一個元素的位置，默認從 0 開始
int cursor; // index of next element to return
// 表示上一次迭代過程中，索引的位置；刪除場景為 -1
int lastRet = -1; // index of last element returned; -1 if no such
// 表示迭代過程中，期望的版本號，modCount 表示數組實際的版本號
int expectedModCount = modCount;
迭代器的三個方法：
-
hasNext: 還有沒有值可以迭代 -
next: 如果有值可以迭代，返回迭代的值 -
remove: 刪除當前迭代的值
三個方法的源碼：
hasNext
public boolean hasNext() {
// cursor 表示下一個元素的位置，size 表示實際大小，如果兩者相等，說明已經沒有元素可以迭代了，如果不等，說明還可以迭代
// 例如當 size 為 10，cursor 為 0-9時都可以讀取, 而如果 cursor 大于9，也就是數組最大值的下標
return cursor != size;
}
next
@SuppressWarnings("unchecked")
public E next() {
// 迭代過程中，判斷版本號有無修改，有被修改，拋出 ConcurrentModificationException 異常
checkForComodification();
// 本次迭代過程中，元素的索引位置
int i = cursor;
// i 最大值只能是 size-1
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 下一次迭代時，元素的位置，為下一次迭代做準備
cursor = i + 1;
// 返回元素值
return (E) elementData[lastRet = i];
}
// 檢查版本號
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
從源碼可以看到，next 方法做了兩件事，第一是檢驗能不能繼續(xù)迭代，第二是找到迭代的值，并為下一次迭代做準備（cursor+1）。
remove
public void remove() {
// 如果上一次操作時，數組的位置已經小于0了，說明數組已經被刪除完了
if (lastRet < 0)
throw new IllegalStateException();
// 迭代過程中，判斷版本號有無被修改，有被修改，則拋出 ConcurrentModificationException 異常
checkForComodification();
try {
// 刪除當前迭代的元素
// 為何是當前: 因為上面 next 中取當前值時已經為 lastRet 賦值為當前元素下標 `lastRet = i`
ArrayList.this.remove(lastRet);
// 因為刪除了當前元素，而 ArrayList remove 方法刪除元素后會將元素后面的所有元素向前移動，所以這里的下次迭代的位置 cursor 賦值為當前值的下標
cursor = lastRet;
// -1 表示元素已經被刪除，這里也防止重復刪除
lastRet = -1;
// 調用 ArrayList remove 刪除元素時 modCount 已經發(fā)生變化，在此賦值給 expectedModCount
// 這樣下次迭代時，兩者的值是一致的
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
這里我們需要注意：
-
lastRet = -1的操作目的，是防止重復刪除操作； - 刪除元素成功，數組當前的 modCount 就會發(fā)生變化，這里會把
expectedModCount重新賦值，這樣下次迭代時兩者的值就是一致的了。
2.6 時間復雜度
從我們上面新增或刪除方法的源碼解析，發(fā)現，對數組元素的操作，只需要根據數組索引，直接新增和刪除，所以時間復雜度是 O(1)。
2.7 線程安全
我們需要強調的是，只有當 ArrayList 作為共享變量時，才會有線程安全問題，當 ArrayList 是方法內部局部變量時，是沒有線程安全問題的。
ArrayList 有線程安全問題的本質，是因為 ArrayList 自身的 elementData、size、modCount 在進行各種操作時，都沒有加鎖，而且這些變量的類型并非是可見的(volatile)的，所以如果多個線程對這些變量進行操作時，可能會有值被覆蓋的情況。
類注釋中推薦我們使用 Collections#synchronizedList 來保證線程的安全，SynchronizedList 是通過在每個方法上面加上同步鎖 synchronized 來實現的，雖然實現了線程安全，但是性能大大降低，具體實現源碼：
static class SynchronizedList<E> extends SynchronizedCollection<E>
implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;
final List<E> list;
public void add(int index, E element) {
// 使用 synchronized 輕量鎖，mutex 表示當前 SynchronizedList，也就是父類 SynchronizedCollection 中的 mutex
synchronized (mutex) {
list.add(index, element);
}
}
}
總結
從 ArrayList 整理架構觸發(fā)，落地到初始化、新增、擴容、刪除、迭代等核心源碼實現，我們發(fā)現 ArrayList 其實就是圍繞底層數組結構，各個 API 都是對數組的操作進行封裝，讓使用者無需感知底層實現，只需關注如何使用即可。
------------------------------------- END -------------------------------------
