ArrayList的實現細節

ArrayList是我們經常用到的一個類，下面總結一下它內部的實現細節和使用時要注意的地方。

ArrayList在數據結構的層面上講，是一個用數組實現的list，從應用層面上講，就是一個容量會自己改變的數組，具有一系列方便的add、set、get、remove等方法，線程不安全。先上張類圖吧。

ArrayList的容量

ArrayList有兩個數據域與之相關。

1 transient Object elementData; // non-private to simplify nested class access
2
3 private int size;

很明顯，size表示ArrayList中包含的元素數量，也就是size方法的返回值，而elementData.length則是ArrayList的容量，表示在不擴容的情況下能存儲多少個元素。By the way，JDK1.8的ArrayList的初始容量是0，之前的版本貌似10。 ArrayList還有一些關於擴大容量和縮小容量的方法

1 /**
2 * 當ArrayList中有空閑的空間時，縮減ArrayList的容量。應用程序可以使用這個方法最小化ArrayList實例
3 */
4 public void trimToSize
5
6 /**
7 * public修飾，供應用程序調用的擴容方法，內部調用ensureExplicitCapacity方法
8 */
9 public void ensureCapacity(int minCapacity)
10
11 /**
12 * private修飾，供ArrayList內部使用的擴容方法，內部同樣是調用ensureExplicitCapacity方法
13 */
14 private void ensureCapacityInternal(int minCapacity)
15
16 /**
17 * 內部調用grow方法
18 */
19 private void ensureExplicitCapacity(int minCapacity)
20
21 /**
22 * grow方法內部會做一個判斷，如果ArrayList擴大1.5倍還不夠的話，才會增加到minCapacity
23 * 這是為了防止擴容太小而導致多次擴容多次改變數組大小，從而影響性能。
24 * 比如說，我有一個裝滿了的ArrayList，現在我往其中加入10個元素，自然是要擴容的，
25 * 那麼我是一次性擴容增加10個容量，還是每次add前擴容增加一個容量呢，答案可想而知。
26 */
27 private void grow(int minCapacity)
28
29 /**
30 * 對ArrayList擴容的一個限制，擴得太大會拋出OutOfMemoryError
31 */
32 private static int hugeCapacity(int minCapacity)

雖說的容量會隨著數據量的增大而增大，使用時不用費心於容量的維護，不過在可以預估數據量的情況下，務必使用public ArrayList(int initialCapacity)來指定初始容量，這樣的話，一來減少擴容方法的調用避免數組頻繁更改，二來在一定程度上減少了內存的消耗（比如我就存5000個元素，當數組達到4000時擴容擴大1.5倍變成6000，白白耗費了1000個單位的內存）。經過測試，這是可以大大提高運行效率的。

ArrayList的clone方法是淺複製，在這裡直接上段demo。

1 public class Main {
2 public static void main(String[] args) {
3 User u1 = new User;
4 u1.setUsername("qwe");
5 u1.setPassword("qwePASSWORD");
6 User u2 = new User;
7 u2.setUsername("asd");
8 u2.setPassword("asdPassword");
9 ArrayList<User> list1 = new ArrayList<>;
10 list1.add(u1);
11 list1.add(u2);
12 ArrayList<User> list2 = (ArrayList<User>) list1.clone;
13 list2.get(0).setUsername("zxc"); //修改u1的username
14 list2.get(0).setPassword("zxcPassword"); ////修改u1的password
15 System.out.println(list1); //[User [username=zxc, password=zxcPassword], User //[username=asd, password=asdPassword]]
16 }
17 /**
18 * 實現深複製
19 */
20 private static List<User> deepClone(List<User> from) throws CloneNotSupportedException {
21 List<User> list = new ArrayList<>;
22 for(User item : from) {
23 list.add((User)item.clone);
24 }
25 return list;
26 }
27 }
28
29 class User {
30 private String username;
31 private String password;
32 public User {
33 }
34 public String getUsername {
35 return username;
36 }
37 public void setUsername(String username) {
38 this.username = username;
39 }
40 public String getPassword {
41 return password;
42 }
43 public void setPassword(String password) {
44 this.password = password;
45 }
46 @Override
47 public String toString {
48 return "User [username=" + username + ", password=" + password + "]";
49 }
50 }

有輸出可知，list2中的u1就是list1中的u1，二者的引用指向了同一個User對象，具體見示意圖。所以要想實現ArrayList的深複製得根據場景自己寫。

1 /**
2 * 獲得一個Object數組，這個方法會分配一個新數組（並不是單純的return elementData;），所以調用者可以安全的修改數組而不影響ArrayList
3 */
4 public Object toArray
5
6 /**
7 * 獲得一個泛型數組
8 */
9 public <T> T toArray(T[] a) {
10 if (a.length < size) //數組a長度不足，則重新new一個數組
11 // Make a new array of a"s runtime type, but my contents:
12 return (T[]) Arrays.copyOf(elementData, size, a.getClass);
13 System.arraycopy(elementData, 0, a, 0, size); //數組a長度足夠，就將元素複製到a數組中，而後返回a
14 if (a.length > size)
15 a[size] = null;
16 return a;
17 }

This method acts as bridge between array-based and collection-based APIs.這是文檔注釋中的一句話，大意是這個方法是數組和集合之間的橋樑。通過函數簽名，我們可以得知toArray返回一個Object數組，toArray(T[] a)返回一個泛型數組。我們往往使用的是toArray(T[] a),常見的使用方式如下

1 List<Integer> list = new ArrayList<>;
2 Collections.addAll(list,1,2,3,4,5,6);
3 // 方式1 //
4 list.toArray(new Integer[0]); //涉及到反射，效率較低
5 // 方式2 //
6 list.toArray(new Integer[list.size()])

構造函數：public ArrayList(Collection c)

1 public ArrayList(Collection<? extends E> c) {
2 elementData = c.toArray;
3 if ((size = elementData.length) != 0) {
4 // c.toArray might (incorrectly) not return Object (see 6260652)
5 if (elementData.getClass != Object.class)
6 elementData = Arrays.copyOf(elementData, size, Object[].class);
7 } else {
8 // replace with empty array.
9 this.elementData = EMPTY_ELEMENTDATA;
10 }
11 }

利用這個構造方法，我們可以方便的使用其他容器來構造一個ArrayList。這裡有一個要點，通過源碼我們得知，當elementData不是Object數組時，它會使用Arrays.copyOf方法構造一個Object數組替換elementData，為什麼要這麼做呢，Object objArr = new String[5];之類的代碼完全不會報錯啊。我們先看一段代碼，理解Java數組的一個特性，Java數組要求其存儲的元素必須是new數組時的實際類型的實例。

1 Object objArr = new String[5];
2 objArr[0] = "qwe";
3 objArr[1] = new Object; //java.lang.ArrayStoreException
4 System.out.println(Arrays.toString(objArr));

數組objArr的實際類型是String數組，所以它只能存儲Stirng類型的對象實例（String沒有子類），不然就拋出異常。

理解了ArrayStoreException，我們再回到ArrayList。假設在使用上面那個構造函數時，不轉換成Object數組類型，當我們使用toArray方法時就會出問題了，正如注釋所說：c.toArray might (incorrectly) not return Object。使用toArray方法獲得一個Object數組，直觀意思就是可以往裡面加任何類型的實例啊，但是如果不在上面那個構造函數中特殊處理，是會拋java.lang.ArrayStoreException。這就是為什麼ArrayList要對非Object數組特殊處理：為了toArray返回的Object數組能夠正常使用。

1 List<String> list = new ArrayList<String>;
2 list.add("one");
3 list.add("two");
4 Object arr = list.toArray; //這個arr數組可以正常使用，真是nice啊
5 // class [Ljava.lang.Object;返回的是Object數組
6 System.out.println(arr.getClass);
7 arr[0] = "";
8 arr[0] = 123;
9 arr[0] = new Object;

fail-fast：快速失敗

fail-fast是指在多線程環境下，比如一個線程在讀（這裡僅考慮迭代器迭代），一個線程在寫的情況下容易出現匪夷所思的bug，為了更好的調試，採用了快速失敗機制，一旦發現非同步修改，馬上拋異常而不是繼續迭代下去。當然，ArrayListd的實現更加嚴格，在單線程環境下作死的話也會拋出異常。

1 List<Integer> list = new ArrayList<Integer>;
2 Collections.addAll(list, 1, 2, 3, 4, 5, 6, 7);
3 Iterator<Integer> iterator = list.iterator;
4 list.add(8); //修改了ArrayList
5 while(iterator.hasNext) {
6 System.out.println(iterator.next); //java.util.ConcurrentModificationException
7 }

下面再簡單講幾句ArrayList實現快速失敗的機制。ArrayList的快速失敗是圍繞著迭代器的，所以定位到迭代器的源碼。獲得一個迭代器後， expectedModCount值就確定了，可是modCount可能會改變（trimToSize()、ensureExplicitCapacity()、remove()、clear()等等都會修改modCount）。往後使用迭代器的過程中，一旦expectedModCount不等於modCount，就認為迭代的結果有問題，不管三七二十一就拋出ConcurrentModificationException。

1 private class Itr implements Iterator<E> {
2 /**
3 * 每構造一個迭代器都會記錄當前的modCount，modCount之後有可能會改變
4 */
5 int expectedModCount = modCount;
6 /**
7 * 當modCount不等於expectedModCount就拋出ConcurrentModificationException
8 */
9 final void checkForComodification {
10 if (modCount != expectedModCount)
11 throw new ConcurrentModificationException;
12 }
13 }

務必理解文檔注釋中的一段話。

1 he iterators returned by this class"s iterator and listIterator methods are fail-fast:
2 if the list is structurally modified at any time after the iterator is created, in any way except through the iterator"s own remove or add methods, the iterator will throw a ConcurrentModificationException.
3 Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
4
5 快速失敗是指：迭代器被創建後，list發生了結構型的變化（除了使用迭代器自己的add或者remove操作），迭代器使用時會拋出ConcurrentModificationException。
6 該類的iterator和listIterator都是快速失敗的。
7 因此，面對並發修改，迭代器將快速的拋出異常終止迭代，而不是冒著風險在非確定的未來進行非確定性行為。

ArrayList的序列化機制

通過UML圖，我們知道ArrayList實現了Serializable介面，通過源碼，我們又知道ArrayList的序列化機制、反序列化機制是自定義的。

/**
* 自定義序列化機制
*/
private void writeObject(java.io.ObjectOutputStream s)

/**
* 自定義反序列化機制
*/
private void readObject(java.io.ObjectInputStream s)

那麼為什麼要自定義序列化、反序列化機制呢？是由於ArrayList實質上是一個動態數組，往往數組中會有空餘的空間，如果採用默認的序列化機制，那些空餘的空間會作為null寫入本地文件或者在網路中傳輸，耗費了不必要的資源。所以，ArrayList使用自定義序列化機制，僅寫入索引為【0，size）的有效元素以節省資源。

ArrayList的遍歷方式有三種：foreach語法糖、普通for循環，迭代器。其中foreach相當於使用迭代器遍歷，而是用迭代器時會有個迭代器對象的開銷，所以一般情況下普通的for循環遍歷效率更高。

1 ArrayList<Integer> list = new ArrayList<>;
2 Collections.addAll(list,1,2,3,4,5,6,7);
3 int len = list.size; //避免重複調用list.size方法
4 for(int i=0;i<len;i++) {
5 System.out.print(list.get(i)); //隨機訪問
6 }

RandomAccess介面

RandomAccess是一個標記介面，用於標記當前類是可以隨機訪問的，有什麼用？我們先看看JDK中一個典型的應用場景。

1 /**
2 * Collections.fill
3 */
4 public static <T> void fill(List<? super T> list, T obj) {
5 int size = list.size;
6 if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
7 for (int i=0; i<size; i++)
8 list.set(i, obj);
9 } else {
10 ListIterator<? super T> itr = list.listIterator;
11 for (int i=0; i<size; i++) {
12 itr.next;
13 itr.set(obj);
14 }
15 }
16 }

上面這段代碼，大概的業務邏輯是指當list是RandomAccess的實例時，便用普通的for循環遍歷，如果不是RandomAccess實例時，則用迭代器遍歷。

前面一點已經講了，對於ArrayList，普通的for循環遍歷效率比用迭代器遍歷效率高。現在拓展這一點：當一個類標記了RandomAccess介面，那麼表明該類使用for循環遍歷效率更高，如果沒用RandomAccess標記，則使用迭代器遍歷效率更高。平時我們可以模仿Collections.fill,使用這個特性寫出更美好的代碼。

另外，如果使用普通的for循環遍歷非RandomAccess的實例，效率是很低的，比如LinkedList（實質是一個雙向鏈表），每次get一個元素都要遍歷半個鏈表，所以要格外注意。

記得剛學數據結構時，刪除一個元素，添加一個元素是這麼寫的。

/**
* 在第索引{@param i}處插入元素{@param item}
*/
@Override
public void add(int i, T item) {
// 參數校驗 //
if (i < 0 || i > size) {
throw new IllegalArgumentException(String.format("i=%d，無效索引值", i));
}
// 插入元素 //
for (int p = size; p > i; p--) { // 移動數組
arr[p] = arr[p - 1];
}
arr[i] = item;
size++;
}

/**
* 刪除索引{@param i}處的元素
*/
@Override
public T remove(int i) {
// 參數校驗 //
if (i < 0 || i >= size) {
throw new IllegalArgumentException(String.format("i=%d，無效索引值", i));
}
// 移除節點 //
T item = arr[i];
for (int p = i; p < size - 1; p++) { // 移動數組
arr[p] = arr[p + 1];
}
arr[--size] = null;
return item;
}

不論添加、刪除，因為移動數組，所以得用for循環來移動，而且循環的邊界條件很難掌握很容易寫錯，而ArrayList使用了System.arraycopy來簡化的這一切。掌握了這個，平時我們也可以使用System.arraycopy來編寫代碼了！

1 public void add(int index, E element) {
2 rangeCheckForAdd(index); //檢查index有沒有越界
3 ensureCapacityInternal(size + 1); // Increments modCount!!
4 System.arraycopy(elementData, index, elementData, index + 1,
5 size - index); //將elementData位於index之後的元素全部向後移一位
6 elementData[index] = element;
7 size++;
8 }
9
10 public E remove(int index) {
11 rangeCheck(index);//檢查index有沒有越界
12 modCount++;
13 E oldValue = elementData(index);
14 int numMoved = size - index - 1;
15 if (numMoved > 0)
16 System.arraycopy(elementData, index+1, elementData, index,
17 numMoved);//將elementData位於index+1之後的元素全部向前移一位
18 elementData[--size] = null; // clear to let GC do its work
19 return oldValue;
20 }

總結

ArrayList是一個線程不安全的動態數組，使用ensureCapacity擴容，trimToSize縮減容量。

toArray的使用

System.arraycopy的使用

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！