重識 ArrayList

2019 年 10 月 3 日
筆記

前言

ArrayList 作為 Java 集合框架中最常用的類，在一般情況下，用它存儲集合數據最適合不過。知其然知其所以然，為了能更好地認識和使用 ArrayList，本文將從下面幾方面深入理解 ArrayList：

為什麼不用數組，用 ArrayList
ArrayList 特性的源碼分析
Java 8 後的 ArrayList
正確的 ArrayList 使用姿勢

為什麼不用數組，用 ArrayList。

在 Java 語言中，由於普通數組受到長度限制，初始化時就需要限定數組長度，無法根據元素個數動態擴容，並且 Java 數組供開發者調用方法有限，只有取元素，獲取數組長度和添加元素一些簡單操作。後台在 Java 1.2 引入了強大豐富的 Collection 框架，其中用 ArrayList 來作為可動態擴容數組的列表實現來代替 Array 在日常開發的使用，ArrayList 實現所有列表的操作方法，方便開發者操作列表集合。這裡我們先列舉下 ArrayList 的主要特點，在後文進行一一闡述：

有序存儲元素
允許元素重複，允許存儲 null 值
支援動態擴容
非執行緒安全

為了更好地認識 ArrayList，我們首先來看下從 ArrayList 的UML類圖：

從上圖可以看出 ArrayList 繼承了 AbstractList, 直接實現了 Cloneable, Serializable，RandomAccess 類型標誌介面。

AbstractList 作為列表的抽象實現，將元素的增刪改查都交給了具體的子類去實現，在元素的迭代遍歷的操作上提供了默認實現。
Cloneable 介面的實現，表示了 ArrayList 支援調用 Object 的 clone 方法，實現 ArrayList 的拷貝。
Serializable 介面實現，說明了 ArrayList 還支援序列化和反序列操作，具有固定的 serialVersionUID 屬性值。
RandomAccess 介面實現，表示 ArrayList 里的元素可以被高效效率的隨機訪問，以下標數字的方式獲取元素。實現 RandomAccess 介面的列表上在遍歷時可直接使用普通的for循環方式，並且執行效率上給迭代器方式更高。

ArrayList 源碼分析

進入 ArrayList 源程式碼，從類的結構里很快就能看到 ArrayList 的兩個重要成員變數：elementData 和 size。

elementData 是一個 Object 數組，存放的元素，正是外部需要存放到 ArrayList 的元素，即 ArrayList 對象維護著這個對象數組 Object[]，對外提供的增刪改查以及遍歷都是與這個數組有關，也因此添加到 ArrayList 的元素都是有序地存儲在數組對象 elementData 中。
size 欄位表示著當前添加到 ArrayList 的元素個數，需要注意的是它必定小於等於數組對象 elementData 的長度。一旦當 size 與 elementData 長度相同，並且還在往列表裡添加元素時，ArrayList 就會執行擴容操作，用一個更長的數組對象存儲先前的元素。

由於底層維護的是一個對象數組，所以向 ArrayList 集合添加的元素自然是可以重複的，允許為 null 的，並且它們的索引位置各不一樣。

如何擴容

了解完 ArrayList 為何有序存儲元素和元素可以重複，我們再來看下作為動態數組列表，底層擴容是如何實現的。

首先，要確定下擴容的時機會是在哪裡，就如上面描述 size 欄位時提到的，當 size 與 elementData 長度相同，此刻再添加一個元素到集合就會出現容量不夠的情況，需要進行擴容，也就是說 ArrayList 的擴容操作發生在添加方法中，並且滿足一定條件時才會發生。

現在我們再來看下 ArrayList 類的程式碼結構，可以看到有四個添加元素的方法，分為兩類：添加單個元素和添加另一個集合內的所有元素。

先從簡單的方法下手分析，查看 add(E):boolean 方法實現：

public boolean add(E e) {      ensureCapacityInternal(size + 1);      elementData[size++] = e;      return true;  }

從上面可以看出第三行程式碼是簡單地添加單個元素，並讓 size 遞增加 1；那麼擴容實現就在 ensureCapacityInternal 方法中，這裡傳入參數為 size+1，就是要在真正添加元素前判斷添加後的元素個數，也就是集合所需要的最小容量是否會超過原數組的長度。再看下這個 ensureCapacityInternal 方法實現

private void ensureCapacityInternal(int minCapacity) {      ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));  }

其內部仍有兩個方法調用，首先看下比較簡單的 calculateCapacity 方法：

private static int calculateCapacity(Object[] elementData, int minCapacity) {      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {          return Math.max(DEFAULT_CAPACITY, minCapacity);      }      return minCapacity;  }

當 elementData 與 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 相等，也就是空數組時，返回一個可添加元素的默認最小容量值 DEFAULT_CAPACITY 對應的10 ，否則按照傳入的 size +1 為最小容量值；執行完之後接著看 ensureExplicitCapacity 方法：

private void ensureExplicitCapacity(int minCapacity) {      modCount++;        if (minCapacity - elementData.length > 0)          grow(minCapacity);  }

從程式碼中可以看到擴容實現在 grow 方法之中，並且只有當數組長度小於所需要的最小容量時執行：當數組存儲元素已滿，無法再存儲將新加入的元素。

private void grow(int minCapacity) {      int oldCapacity = elementData.length;      int newCapacity = oldCapacity + (oldCapacity >> 1);      if (newCapacity - minCapacity < 0)          newCapacity = minCapacity;      if (newCapacity - MAX_ARRAY_SIZE > 0)          newCapacity = hugeCapacity(minCapacity);      elementData = Arrays.copyOf(elementData, newCapacity);  }

進一步跳轉到 grow 方法的實現，可以看到第8行利用工具類方法 java.util.Arrays#copyOf(T[], int) ,對原有數組進行拷貝，將內部所有的元素存放到長度為 newCapacity 的新數組中，並將對應新數組的引用賦值給 elementData。此刻 ArrayList 內部引用的對象就是更新長度了的新數組，實現效果就如下圖一樣：

現在我們再來關注下代表數組新容量的 newCapacity 被調整為多少。首先 newCapacity 通過 oldCapacity + (oldCapacity >> 1) 計算獲得，使用位運算將原容量值 oldCapacity 通過右移一位，獲得其一半的值（向下取整）, 然後加上原來的容量值，那麼就是原容量值 oldCapacity 的1.5倍。

>> 右位運算符，會將左操作數進行右移，相當於除以2，並且向下取整，比如表達式 (7 >> 1) == 3 結果為真。

當計算得到的 newCapacity 仍然小於傳入最小容量值時，說明當前數組個數為空，採用默認的 DEFAULT_CAPACITY作為容量值分配數組。

額外需要注意的是還有最大數組個數的判斷，MAX_ARRAY_SIZE 在文件對應的程式碼定義如下：

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList 存儲元素個數有最大限制，如果超過限制就會導致 JVM 拋出 OutOfMemoryError 異常。

到這裡 java.util.ArrayList#add(E) 方法的擴容邏輯就分析結束了。類似的，在其他添加元素的方法里實現內我們都可以看到 ensureCapacityInternal 方法的調用，在真正操作底層數組前都會進行容量的確認，容量不夠則進行動態擴容。

序列化與反序列化

transient Object[] elementData;

在 ArrayList 源碼看到的 elementData 帶有關鍵字 transient，而通常 transient 關鍵字修飾了欄位則表示該欄位不會被序列化，但是 ArrayList 實現了序列化介面，並且提供的序列化方法 writeObject 與反序列化方法 readObject 的實現, 這是如何做到的呢？

我們首先來看下 ArrayList 進行序列化的程式碼：

private void writeObject(java.io.ObjectOutputStream s)          throws java.io.IOException {      int expectedModCount = modCount;      s.defaultWriteObject();        s.writeInt(size);        for (int i = 0; i < size; i++) {          s.writeObject(elementData[i]);      }        if (modCount != expectedModCount) {          throw new ConcurrentModificationException();      }  }

第4行程式碼首先將當前對象的非 static 修飾，非 transient 修飾的欄位寫出到流中；第6行將寫出元素的個數作為容量。

接下來就是通過循環將包含的所有元素寫出到流，在這一步可以看出 ArrayList 在自己實現的序列化方法中沒有將無存儲數據的記憶體空間進行序列化，節省了空間和時間。

同樣地，在反序列化中根據讀進來的流數據中獲取 size 屬性，然後進行數組的擴容，最後將流數據中讀到的所有元素數據存放到持有的對象數組中。

private void readObject(java.io.ObjectInputStream s)          throws java.io.IOException, ClassNotFoundException {      elementData = EMPTY_ELEMENTDATA;        s.defaultReadObject();        s.readInt(); // ignored        if (size > 0) {          int capacity = calculateCapacity(elementData, size);          SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);          ensureCapacityInternal(size);            Object[] a = elementData;          for (int i = 0; i < size; i++) {              a[i] = s.readObject();          }      }  }

關於拷貝

針對列表元素的拷貝，ArrayList 提供自定義的 clone 實現如下：

public Object clone() {    try {      ArrayList<?> v = (ArrayList<?>) super.clone();      v.elementData = Arrays.copyOf(elementData, size);      v.modCount = 0;      return v;    } catch (CloneNotSupportedException e) {      // this shouldn't happen, since we are Cloneable      throw new InternalError(e);    }  }

從上述程式碼可以清楚看出執行的 copyOf 操作是一次淺拷貝操作，原 ArrayList 對象的元素不會被拷貝一份存到新的 ArrayList 對象然後返回，它們各自的欄位 elementData 里各位置存放的都是一樣元素的引用，一旦哪個列表修改了數組中的某個元素，另一個列表也將受到影響。

JDK 1.8 後的 ArrayList

從源碼角度分析完 ArrayList 的特性之後，我們再來看下 JDK 1.8 之後在 ArrayList 類上有什麼新的變化。

新增 removeIf 方法

removeIf 是 Collection 介面新增的介面方法，ArrayList 由於父類實現該介面，所以也有這個方法。removeIf 方法用於進行指定條件的從數組中刪除元素。

public boolean removeIf(Predicate<? super E> filter){...}

傳入一個代表條件的函數式介面參數 Predicate，也就是Lambda 表達式進行條件匹配，如果條件為 true，則將該元素從數組中刪除，例如下方程式碼示例：

List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));  numbers.removeIf(i -> i % 2 == 0);  System.out.println(numbers); // [1, 3, 5, 7, 9]

新增 spliterator 方法

這個方法也是來自於 Collection 介面，ArrayList 對此方法進行了重寫。該方法會返回 ListSpliterator 實例，該實例用於遍歷和分離容器所存儲的元素。

@Override  public Spliterator<E> spliterator() {      return new ArrayListSpliterator<>(this, 0, -1, 0);  }

在 ArrayList 的實現中，該方法返回一個內部靜態類對象 ArrayListSpliterator，通過它可以就可以集合元素進行操作。

它的主要操作方法有下面三種：

tryAdvance 迭代單個元素，類似於 iterator.next()
forEachRemaining 迭代剩餘元素
trySplit 將元素切分成兩部分並行處理,但需要注意的 Spliterator 並不是執行緒安全的。

雖然這個三個方法不常用，還是有必要了解，可以簡單看下方法的使用方式

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(1,2,3,4,5,6));  Spliterator<Integer> numbers = numbers.spliterator();    numbers.tryAdvance( e -> System.out.println( e ) ); // 1    numbers.forEachRemaining( e -> System.out.println( e ) ); // 2 3 4 5 6    Spliterator<Integer> numbers2 = numbers.trySplit();    numbers.forEachRemaining( e -> System.out.println( 3 ) );      //4 5 6  numbers2.forEachRemaining( e -> System.out.println( 3 ) );      //1 2 3

必會的使用姿勢

接觸了 ArrayList 源碼和新API 之後，我們最後學習如何在平常開發中高效地使用 ArrayList。

高效的初始化

ArrayList 實現了三個構造函數, 默認創建時會分配到空數組對象 EMPTY_ELEMENTDATA；第二個是傳入一個集合類型數據進行初始化；第三個允許傳入集合長度的初始化值，也就是數組長度。由於每次數組長度不夠會導致擴容，重新申請更長的記憶體空間，並進行複製。而讓我們初始化 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);      }  }    public ArrayList() {      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  }    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;      }  }

元素遍歷

JDK 1.8前，ArrayList 只支援3種遍歷方式：迭代器遍歷，普通 for 循環，for-each 增強，在 JDK1.8 引入了 Stream API 之後，同屬於 Collection 集合的 ArrayList，可以使用 stream.foreach() 方法一個個地獲取元素：

ArrayList<String> names = new ArrayList<String>(Arrays.asList( "alex", "brian", "charles"));  names.forEach(name -> System.out.println(name)); // alex brian charles

轉換 Array

ArrayList 提供兩個方法用於列表向數組的轉換

public Object[] toArray();  public <T> T[] toArray(T[] a);

第一個方法直接返回 Object 類型數組
在第二個方法中，返回數組的類型為所傳入的指定數組的類型。並且如果列表的長度符合傳入的數組，將元素拷貝後數組後，則在其中返回數組。否則，將根據傳入數組的類型和列表的大小重新分配一個新數組，拷貝完成後再返回。

從上述描述可以看出使用第二個方法更加合適，能保留原先類型：

ArrayList<String> list = new ArrayList<>(4);  list.add("A");  list.add("B");  list.add("C");  list.add("D");    String[] array = list.toArray(new String[list.size()]);  System.out.println(Arrays.toString(array)); // [A, B, C, D]

應對多執行緒

在這裡需要說明的是 ArrayList 本身是非執行緒安全的，如果需要使用執行緒安全的列表通常採用的方式是 java.util.Collections#synchronizedList(java.util.List<T>) 或者使用 Vector 類代替。還有一種方式是使用並發容器類 CopyOnWriteArrayList 在多執行緒中使用，它底層通過創建原數組的副本來實現更新，添加等原本需同步的操作，不僅執行緒安全，減少了對執行緒的同步操作。

應對頭部結點的增刪

ArrayList是數組實現的，使用的是連續的記憶體空間，當有在數組頭部將元素添加或者刪除的時候，需要對頭部以後的數據進行複製並重新排序，效率很低。針對有大量類似操作的場景，出於性能考慮，我們應該使用 LinkedList 代替。由於LinkedList 是基於鏈表實現，當需要操作的元素位置位於List 前半段時，就從頭開始遍歷，馬上找到後將把元素在相應的位置進行插入或者刪除操作。

結語

到這裡我們學習總結 ArrayList 的實現和常見使用，作為基礎容器集合，越是多些了解，對我們日常使用越順手。由於上文提到了另一個列表集合 LinkedList，它與 ArrayList 實現方式不同，使用場景也不同，將作為下一篇文章分析的集合登場，感興趣的小夥伴歡迎關注我的微信公眾號，期待更新。

參考

https://www.cnblogs.com/skywang12345/p/3308556.html
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
https://yuqirong.me/2018/01/21/ArrayList%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%86%E8%A7%A3%E6%9E%90/
https://juejin.im/post/5a58aa62f265da3e4d72a51b
https://howtodoinjava.com/java-arraylist/
http://cmsblogs.com/?p=4727