## 05 ArrayList 源碼解析和設計思路 > 耐心和恒心總會得到報酬的。 > ——愛因斯坦 ## 引導語 ArrayList 我們幾乎每天都會使用到，但真正面試的時候，發現還是有不少人對源碼細節說不清楚，給面試官留下比較差的印象，本小節就和大家一起看看面試中和 ArrayList 相關的源碼。 ## 1 整體架構 ArrayList 整體架構比較簡單，就是一個數組結構，比較簡單，如下圖： 圖中展示是長度為 10 的數組，從 1 開始計數，index 表示數組的下標，從 0 開始計數，elementData 表示數組本身，源碼中除了這兩個概念，還有以下三個基本概念： * DEFAULT\_CAPACITY 表示數組的初始大小，默認是 10，這個數字要記住； * size 表示當前數組的大小，類型 int，沒有使用 volatile 修飾，非線程安全的； * modCount 統計當前數組被修改的版本次數，數組結構有變動，就會 +1。 **類注釋** 看源碼，首先要看類注釋，我們看看類注釋上面都說了什么，如下： * 允許 put null 值，會自動擴容； * size、isEmpty、get、set、add 等方法時間復雜度都是 O (1)； * 是非線程安全的，多線程情況下，推薦使用線程安全類：Collections#synchronizedList； * 增強 for 循環，或者使用迭代器迭代過程中，如果數組大小被改變，會快速失敗，拋出異常。 除了上述注釋中提到的 4 點，初始化、擴容的本質、迭代器等問題也經常被問，接下來我們從源碼出發，一一解析。 ## 2 源碼解析 ### 2.1 初始化 我們有三種初始化辦法：無參數直接初始化、指定大小初始化、指定初始數據初始化，源碼如下： ~~~java private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //無參數直接初始化，數組大小為空 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //指定初始數據初始化 public ArrayList(Collection<? extends E> c) { //elementData 是保存數組的容器，默認為 null elementData = c.toArray(); //如果給定的集合（c）數據有值 if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) //如果集合元素類型不是 Object 類型，我們會轉成 Object if (elementData.getClass() != Object[].class) { elementData = Arrays.copyOf(elementData, size, Object[].class); } } else { // 給定集合（c）無值，則默認空數組 this.elementData = EMPTY_ELEMENTDATA; } } ~~~ 除了源碼的中文注釋，我們補充兩點： 1：ArrayList 無參構造器初始化時，默認大小是空數組，并不是大家常說的 10，10 是在第一次 add 的時候擴容的數組值。 2：指定初始數據初始化時，我們發現一個這樣子的注釋 see 6260652，這是 Java 的一個 bug，意思是當給定集合內的元素不是 Object 類型時，我們會轉化成 Object 的類型。一般情況下都不會觸發此 bug，只有在下列場景下才會觸發：ArrayList 初始化之后（ArrayList 元素非 Object 類型），再次調用 toArray 方法，得到 Object 數組，并且往 Object 數組賦值時，才會觸發此 bug，代碼和原因如圖： 官方查看文檔地址：[https://bugs.java.com/bugdatabase/view\_bug.do?bug\_id=6260652](https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652)，問題在 Java 9 中被解決。 ### 2.2 新增和擴容實現 新增就是往數組中添加元素，主要分成兩步： * 判斷是否需要擴容，如果需要執行擴容操作； * 直接賦值。 兩步源碼體現如下： ~~~java public boolean add(E e) { //確保數組大小是否足夠，不夠執行擴容，size 為當前數組的大小 ensureCapacityInternal(size + 1); // Increments modCount!! //直接賦值，線程不安全的 elementData[size++] = e; return true; } ~~~ 我們先看下擴容（ensureCapacityInternal）的源碼： ~~~java private void ensureCapacityInternal(int minCapacity) { //如果初始化數組大小時，有給定初始值，以給定的大小為準，不走 if 邏輯 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; // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果擴容后的值 < 我們的期望值，擴容后的值就等于我們的期望值 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果擴容后的值 > jvm 所能分配的數組的最大值，那么就用 Integer 的最大值 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 通過復制進行擴容 elementData = Arrays.copyOf(elementData, newCapacity); } ~~~ 注解應該比較詳細，我們需要注意的四點是： * 擴容的規則并不是翻倍，是原來容量大小 + 容量大小的一半，直白來說，擴容后的大小是原來容量的 1.5 倍； * ArrayList 中的數組的最大值是 Integer.MAX\_VALUE，超過這個值，JVM 就不會給數組分配內存空間了。 * 新增時，并沒有對值進行嚴格的校驗，所以 ArrayList 是允許 null 值的。 從新增和擴容源碼中，下面這點值得我們借鑒： * 源碼在擴容的時候，有數組大小溢出意識，就是說擴容后數組的大小下界不能小于 0，上界不能大于 Integer 的最大值，這種意識我們可以學習。 擴容完成之后，賦值是非常簡單的，直接往數組上添加元素即可：elementData \[size++\] = e。也正是通過這種簡單賦值，沒有任何鎖控制，所以這里的操作是線程不安全的，對于新增和擴容的實現，畫了一個動圖，如下：  ### 2.3 擴容的本質 擴容是通過這行代碼來實現的：`Arrays.copyOf(elementData, newCapacity);`，這行代碼描述的本質是數組之間的拷貝，擴容是會先新建一個符合我們預期容量的新數組，然后把老數組的數據拷貝過去，我們通過 System.arraycopy 方法進行拷貝，此方法是 native 的方法，源碼如下： ~~~java /** * @param src 被拷貝的數組 * @param srcPos 從數組那里開始 * @param dest 目標數組 * @param destPos 從目標數組那個索引位置開始拷貝 * @param length 拷貝的長度 * 此方法是沒有返回值的，通過 dest 的引用進行傳值 */ public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); ~~~ 我們可以通過下面這行代碼進行調用，newElementData 表示新的數組： ~~~java System.arraycopy(elementData, 0, newElementData, 0,Math.min(elementData.length,newCapacity)) ~~~ ### 2.4 刪除 ArrayList 刪除元素有很多種方式，比如根據數組索引刪除、根據值刪除或批量刪除等等，原理和思路都差不多，我們選取根據值刪除方式來進行源碼說明： ~~~java 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++) // 這里是根據 equals 來判斷值相等的，相等后再根據索引位置進行刪除 if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } ~~~ 我們需要注意的兩點是： * 新增的時候是沒有對 null 進行校驗的，所以刪除的時候也是允許刪除 null 值的； * 找到值在數組中的索引位置，是通過 equals 來判斷的，如果數組元素不是基本類型，需要我們關注 equals 的具體實現。 上面代碼已經找到要刪除元素的索引位置了，下面代碼是根據索引位置進行元素的刪除： ~~~java private void fastRemove(int index) { // 記錄數組的結構要發生變動了 modCount++; // numMoved 表示刪除 index 位置的元素后，需要從 index 后移動多少個元素到前面去 // 減 1 的原因，是因為 size 從 1 開始算起，index 從 0開始算起 int numMoved = size - index - 1; if (numMoved > 0) // 從 index +1 位置開始被拷貝，拷貝的起始位置是 index，長度是 numMoved System.arraycopy(elementData, index+1, elementData, index, numMoved); //數組最后一個位置賦值 null，幫助 GC elementData[--size] = null; } ~~~ 從源碼中，我們可以看出，某一個元素被刪除后，為了維護數組結構，我們都會把數組后面的元素往前移動，下面動圖也演示了其過程：  ### 2.5 迭代器 如果要自己實現迭代器，實現 java.util.Iterator 類就好了，ArrayList 也是這樣做的，我們來看下迭代器的幾個總要的參數： ~~~java int cursor;// 迭代過程中，下一個元素的位置，默認從 0 開始。 int lastRet = -1; // 新增場景：表示上一次迭代過程中，索引的位置；刪除場景：為 -1。 int expectedModCount = modCount;// expectedModCount 表示迭代過程中，期望的版本號；modCount 表示數組實際的版本號。 ~~~ 迭代器一般來說有三個方法： * hasNext 還有沒有值可以迭代 * next 如果有值可以迭代，迭代的值是多少 * remove 刪除當前迭代的值 我們來分別看下三個方法的源碼： **hasNext** ~~~java public boolean hasNext() { return cursor != size;//cursor 表示下一個元素的位置，size 表示實際大小，如果兩者相等，說明已經沒有元素可以迭代了，如果不等，說明還可以迭代 } ~~~ **next** ~~~java public E next() { //迭代過程中，判斷版本號有無被修改，有被修改，拋 ConcurrentModificationException 異常 checkForComodification(); //本次迭代過程中，元素的索引位置 int i = cursor; 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 方法就干了兩件事情，第一是檢驗能不能繼續迭代，第二是找到迭代的值，并為下一次迭代做準備（cursor+1）。 **remove** ~~~java public void remove() { // 如果上一次操作時，數組的位置已經小于 0 了，說明數組已經被刪除完了 if (lastRet < 0) throw new IllegalStateException(); //迭代過程中，判斷版本號有無被修改，有被修改，拋 ConcurrentModificationException 異常 checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; // -1 表示元素已經被刪除，這里也防止重復刪除 lastRet = -1; // 刪除元素時 modCount 的值已經發生變化，在此賦值給 expectedModCount // 這樣下次迭代時，兩者的值是一致的了 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } ~~~ 這里我們需要注意的兩點是： * lastRet = -1 的操作目的，是防止重復刪除操作 * 刪除元素成功，數組當前 modCount 就會發生變化，這里會把 expectedModCount 重新賦值，下次迭代時兩者的值就會一致了 ### 2.6 時間復雜度 從我們上面新增或刪除方法的源碼解析，對數組元素的操作，只需要根據數組索引，直接新增和刪除，所以時間復雜度是 O (1)。 ### 2.7 線程安全 我們需要強調的是，只有當 ArrayList 作為共享變量時，才會有線程安全問題，當 ArrayList 是方法內的局部變量時，是沒有線程安全的問題的。 ArrayList 有線程安全問題的本質，是因為 ArrayList 自身的 elementData、size、modConut 在進行各種操作時，都沒有加鎖，而且這些變量的類型并非是可見（volatile）的，所以如果多個線程對這些變量進行操作時，可能會有值被覆蓋的情況。 類注釋中推薦我們使用 Collections#synchronizedList 來保證線程安全，SynchronizedList 是通過在每個方法上面加上鎖來實現，雖然實現了線程安全，但是性能大大降低，具體實現源碼： ~~~java public boolean add(E e) { synchronized (mutex) {// synchronized 是一種輕量鎖，mutex 表示一個當前 SynchronizedList return c.add(e); } } ~~~ ## 總結 本文從 ArrayList 整體架構出發，落地到初始化、新增、擴容、刪除、迭代等核心源碼實現，我們發現 ArrayList 其實就是圍繞底層數組結構，各個 API 都是對數組的操作進行封裝，讓使用者無需感知底層實現，只需關注如何使用即可。