本篇文章主要跟大家分析一下ArrayList的源代碼。閱讀本文你首先得對ArrayList有一些基本的了解，至少使用過它。如果你對ArrayList的一些基本使用還不太熟悉或者在閱讀本文的時候感覺有點困難，你可以先閱讀這篇文章ArrayList設計與實作，自己動手寫ArrayList。
ArrayList繼承體系分析
- RandomAccess，這個接口的含義表示可以随機通路ArrayList當中的資料，拿什麼是随機通路呢？随機通路就是表示我們可以在常量時間複雜度内通路資料，也就是時間複雜度是O(1)。因為在ArrayList當中我們使用的最基本的資料類型是數組，而數組是可以随機通路的，比如像下面這樣。
public static void main(String[] args) { int[] data = new int[10]; for (int i = 0; i < 10; i++) data[i] = i; System.out.println("data[5] = " + data[5]); } 而連結清單是不可以随機通路的，比如說我們想通過下标通路連結清單當中的某個資料，需要從頭結點或者尾節點開始周遊，直到周遊到下标對應的資料，比如下圖中的單連結清單找到第3個資料，需要從頭開始周遊，而這個時間複雜度為O(n)。
- Serializable，這個接口主要用于序列化，所謂序列化就是能将對象寫入磁盤，反序列化就是能夠将對象從磁盤當中讀取出來，如果想序列化和反序列化ArrayList的執行個體對象就必須實作這個接口，如果沒有實作這個接口，在執行個體化的時候程式執行會報錯，比如下面就是一個序列化的例子。
import java.io.*;import java.util.Objects; class TestPerson implements Serializable{ String name; Integer age; private static final long serialVersionUID = 9999L; @Override public String toString() { return "TestPerson{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; TestPerson that = (TestPerson) o; return that.age.equals(this.age) && that.name.equals(this.name); } @Override public int hashCode() { return Objects.hash(name, age); } public TestPerson(String name, Integer age) { this.name = name; this.age = age; } } public class SerialTest { public static void main(String[] args) throws IOException, ClassNotFoundException { TestPerson leHung = new TestPerson("LeHung", 18); FileOutputStream os = new FileOutputStream("objtest"); ObjectOutputStream outputStream = new ObjectOutputStream(os); // 序列化資料 outputStream.writeObject(leHung); FileInputStream is = new FileInputStream("objtest"); ObjectInputStream stream = new ObjectInputStream(is); // 反序列化資料 TestPerson object = (TestPerson) stream.readObject(); System.out.println(object); System.out.println(object == leHung); System.out.println(object.equals(leHung)); }} 如果上面程式當中的TestPerson沒有implements Serializable，則上述代碼會報異常java.io.NotSerializableException:。
- Cloneable，實作Cloneable接口那麼實作Cloneable的類就能夠調用clone這個方法，如果沒有實作Cloneable接口就調用方法，則會抛出異常java.lang.CloneNotSupportedException。
- List，這個接口主要定義了一些集合常用的方法讓ArrayList進行實作，比如add，addAll，contains，remove，set，size，indexOf等等方法。
- AbstractList，這個抽象類也實作了List接口裡面的方法，并且為其提供了預設代碼實作，比如說AbstractList中對indexOf的實作如下：
// 這個方法的作用就是傳回對象 o 在容器當中的下标public int indexOf(Object o) { // 通過疊代器去周遊資料 ListIterator<E> it = listIterator(); if (o==null) { while (it.hasNext()) if (it.next()==null) // 傳回資料 o 的下标 return it.previousIndex(); } else { while (it.hasNext()) if (o.equals(it.next())) // 傳回資料 o 的下标 return it.previousIndex(); } return -1;} 集合的addAll方法實作如下：
// 這個函數的作用就是在 index 的位置插入集合 c 當中所有的元素public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); boolean modified = false; for (E e : c) { add(index++, e); modified = true; } return modified;} ArrayList關鍵字段分析
在ArrayList當中主要有以下這些字段：
// ArrayList 當中預設初始化容量，也就是初始化數組的大小private static final int DEFAULT_CAPACITY = 10;// 存放具體資料的數組 ArrayList 底層就是使用數組進行存儲的transient Object[] elementData; // size 表示容器當中資料的個數 注意和容器的長度區分開來private int size;// 當容器當中沒有元素的時候将 elementData 指派為以下資料（不同情況不一樣）private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 下面兩個函數是 ArrayList 的構造函數，從下面兩個函數當中// 我們可以看出 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 使用差別// EMPTY_ELEMENTDATA 是容器當中沒有元素時使用，DEFAULTCAPACITY_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() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;} ArrayList主要方法分析
- add方法，這個方法用于往容器的末尾增加資料，也是ArrayList當中最核心的方法。他的主要工作流程如下圖所示：
他首先調用函數ensureCapacityInternal確定ArrayList當中的數組長度能夠滿足需求，不然數組會報數組下标越界異常，add函數調用過程當中所涉及到的函數如下。
public boolean add(E e) { // 這個函數的主要目的是確定 elementData 的容量有 size + 1 // 否則存儲資料的時候數組就會越界 ensureCapacityInternal(size + 1); // size 表示容器當中資料的個數 注意和容器的長度區分開來 // 加入資料之後 容器當中資料的個數也要 + 1 elementData[size++] = e; return true;} // minCapacity 表示 ArrayList 中的數組最小的長度private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity( // 這個函數計算數組的最小長度 calculateCapacity(elementData, minCapacity) );} private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果是無參構造的話，取預設長度和需求長度 minCapacity 中比較大的值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity;} private void ensureExplicitCapacity(int minCapacity) { // 這個表示容器發生改變的次數，我們在後續分析疊代器的時候進行分析 // 它跟容器擴容沒關系，現在可以不用管他 modCount++; // 如果最小的需求容量 minCapacity 大于現在容器當中數組的長度，則需要進行擴容 if (minCapacity - elementData.length > 0) grow(minCapacity);} private void grow(int minCapacity) { int oldCapacity = elementData.length; // 新數組的長度為原數組的長度的1.5倍，右移一位相當于除以2 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果新數組的長度，小于需要的最小的容量，則更新數組的長度為 minCapacity if (newCapacity - minCapacity < 0) newCapacity = minCapacity; 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);} private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;} 上述代碼的調用流程如下：
- get函數，擷取對應下标的資料。
public E get(int index) { // 進行數組下标的檢查，如果下标超過 ArrayList 中資料的個數，則抛出異常 // 注意這裡是容器當中資料的個數 不是數組的長度 rangeCheck(index); return elementData(index);} private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));} E elementData(int index) { // 傳回對應下标的資料 return (E) elementData[index];} - remove函數，删除ArrayList當中的資料。
// 通過下标删除資料，這個函數的意義是删除下标為 index 的資料public E remove(int index) { // 首先檢查下标是否合法，如果不合法，抛出下标越界異常 rangeCheck(index); modCount++; E oldValue = elementData(index); // 因為删除某個資料，需要将該資料後面的資料往數組前面移動 // 這裡需要計算需要移動的資料的個數 int numMoved = size - index - 1; if (numMoved > 0) // 通過拷貝移動資料 // 這個函數的意義是将 index + 1和其之後的資料整體移動到 index // 的位置 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 因為最後一個資料已經拷貝到前一個位置了，是以可以設定為 null // 可以做垃圾回收了 elementData[--size] = null; return oldValue;} // 這個函數的意義是删除容器當中的第一個等于 o 的資料public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false;} // 這個方法和第一個 remove 方法原理一緻private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work} - set方法，這個方法主要是用于設定指定下标的資料，這個方法比較簡單。
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue;} ArrayList中那些不為人知的方法
ensureCapacity方法
public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }} 這個方法我們在前面已經提到過了，不知道大家有沒有觀察到他的通路修飾符是public，為什麼要設定為public呢？這個意思很明顯，我們可以在使用ArrayList的時候自己調用這個方法，防止當我們在往容器中加入資料的時候頻繁因為數組長度不夠重新申請記憶體，而原來的數組需要從新釋放，這會給垃圾回收器造成壓力。我們在ArrayList設計與實作，自己動手寫ArrayList這篇文章當中寫過一段測試程式去測試這個方法，感興趣的同學可以去看看！！！
toString方法
我們首先來看一下下面代碼的輸出
public class CodeTest { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); for (int i = 0; i < 10; i++) { list.add(i); } System.out.println(list); }}// 輸出結果：// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 執行上面一段代碼我們可以在控制台看見對應的輸出，我們知道最終列印在螢幕上的是一個字元串，那這個字元串怎麼來的呢，我們列印的是一個對象，它是怎麼得到字元串的呢？我們可以檢視System.out.println的源代碼：
public void println(Object x) { String s = String.valueOf(x); synchronized (this) { print(s); newLine(); }} 從上述代碼當中我們可以看見通過String s = String.valueOf(x);這行代碼得到了一個字元串，然後進行列印，我們在進入String.valueOf方法看看是如何得到字元串的：
public static String valueOf(Object obj) { return (obj == null) ? "null" : obj.toString();} 我們可以看到如果對象不為 null 最終是調用對象的toString方法得到的字元串。是以當列印一個對象的時候，最終會列印這個對象的toString方法傳回的字元串。
toString方法沒有直接在ArrayList當中實作，而是在它繼承的類AbstractList當中實作的，toString的源代碼如下所示：
public String toString() { // 得到 ArrayList 的疊代器 這個疊代器我們稍後細說 Iterator<E> it = iterator(); // 如果容器當中沒有資料則傳回空 if (! it.hasNext()) return "[]"; // 額，寫這個代碼的工程師應該不懂中文 哈哈哈 StringBuilder sb = new StringBuilder(); sb.append('['); for (;;) { E e = it.next(); // 将對象加入到 StringBuilder 當中，這裡加入的也是一個對象 // 但是在 append 源代碼當中會同樣會使用 String.ValueOf // 得到對象的 toString 方法的結果 sb.append(e == this ? "(this Collection)" : e); if (! it.hasNext()) return sb.append(']').toString(); sb.append(',').append(' '); }} 上述代碼的整個過程還是比較清晰的，大緻過程如下：
- 如果容器當中沒有資料，直接傳回[]。
- 如果容器當中有資料的話，那麼通過疊代每個資料，調用StringBuilder的append方法，将資料加入到輸出的StringBuilder對象當中，下面是append的源代碼。
// StringBuilder 的 append 方法@Overridepublic StringBuilder append(Object obj) { return append(String.valueOf(obj));} // StringBuilder 的 append 方法的重載方法@Overridepublic StringBuilder append(String str) { super.append(str); return this;} // String 類中的 valueOf方法public static String valueOf(Object obj) { return (obj == null) ? "null" : obj.toString();} 我們可以發現最終append到StringBuilder當中的字元串仍然是ArrayList當中資料對象的toString方法傳回的資料。
equals方法
在ArrayList當中的equals方法和toString方法一樣，equlas方法也是在類AbstractCollection當中實作的，其源代碼如下：
public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof List)) return false; ListIterator<E> e1 = listIterator(); ListIterator<?> e2 = ((List<?>) o).listIterator(); while (e1.hasNext() && e2.hasNext()) { E o1 = e1.next(); Object o2 = e2.next(); if (!(o1==null ? o2==null : o1.equals(o2))) return false; } return !(e1.hasNext() || e2.hasNext());} 上面代碼的主要流程：
- 首先判斷o和this是否是同一個對象，如果是則傳回true，比如下面這種情況：
ArrayList<Object> list = new ArrayList<>();list.equals(ArrayList); - 如果對象沒有實作List接口傳回false。
- 逐個判斷連結清單裡面的對象是否相等（調用連結清單當中存儲的對象的equals方法），如果兩個連結清單當中節點數目一樣而且都相等則傳回true否則傳回false。
通過上面的分析我們可以發現ArrayList方法并沒有讓比較的對象是ArrayList對象，隻需要實作List接口并且資料數目和内容都相同，這樣equals方法傳回的結果就是true，比如下面代碼就驗證的這個結果：
LinkedList<Integer> list = new LinkedList<>();ArrayList<Integer> arrayList = new ArrayList<>();for (int i = 0; i < 10; i++) { list.add(i); arrayList.add(i);}System.out.println(arrayList.equals(list)); // 結果為 true clone方法
ArrayList的方法比較簡單，就是拷貝了原ArrayList當中的數組中的資料。
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); }} 整個拷貝過程如下如所示：
雖然發生了數組的拷貝，但是拷貝之後的數組中資料的指向并沒有發生變化，也就是說兩個數組指向的内容是一樣的，如果一個數組改變了所指向的資料，另外一個數組當中的資料也會發生變化。比如下面的代碼：
package makeyourowncontainer.test; import java.util.ArrayList; class Person { String name; public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + '}'; }} public class ArrayListTest { public static void main(String[] args) { ArrayList<Person> o1 = new ArrayList<>(); Person person = new Person(); person.setName("一無是處的研究僧"); o1.add(person); Object o2 = o1.clone(); System.out.println("o1 = " + o1); System.out.println("o2 = " + o2); ((ArrayList<Person>) o2).get(0).setName("LeHung"); System.out.println("改變資料之後"); System.out.println("o1 = " + o1); System.out.println("o2 = " + o2); }}// 輸出結果o1 = [Person{name='一無是處的研究僧'}]o2 = [Person{name='一無是處的研究僧'}]改變資料之後o1 = [Person{name='LeHung'}]o2 = [Person{name='LeHung'}] 神秘的疊代器Iterator
Iterator介紹
我們在分析toString方法的時候，有下面這樣一行代碼：
Iterator<E> it = iterator(); 然後不斷通過疊代器的hasNext和next方法對資料進行疊代，比如下面這個例子：
public void testArrayList() { ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < 10; i++) list.add(i); Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); }} // iterator 方法傳回的對象public Iterator<E> iterator() { return new Itr();} Iterator字段分析
Itr類是ArrayList的内部類，接下來我們仔細分析Itr類的實作。
在Itr類當中主要有一下幾個字段：
int cursor; // 下一個元素的下标 當我們 new 這個對象的時候這個值預設初始化為0 // 我們使用的時候也是0這個值，是以不用顯示初始化int lastRet = -1; // 上一個通過 next 方法傳回的元素的下标int expectedModCount = modCount; // modCount 表示數組當中資料改變的次數 modCount 是// ArrayList 當中的類變量 expectedModCount 是 ArrayList// 内部類 Itr 中的類變量 然後将這個變量儲存到 expectedModCount當中// 使用 expectedModCount 主要用于 fast-fail 機制這個我們後面會分析 我們現在來花點時間好好談一下modCount（英文全稱為：modifications count，修改次數）這個字段。當ArrayList當中發生一次結構修改(Structural modifications)時，modCount就++。所謂結構修改就是那些讓ArrayList當中數組的資料個數size發生變化的操作，比如說add、remove方法，因為這兩個方法一個是增加資料，一個是删除資料，都會導緻容器當中資料個數發生變化。而set方法就不會是的modCount發生變化，因為沒有改變容器當中資料的個數。
Iterator的初始化方法：
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; Itr() {}} 在初始化方法當中，沒有任何操作也就印證了我們前面在分析字段的時候說的 cursor的初始化的值為0。
Iterator重要方法
接下來分析疊代器當中比較重要的兩個方法next和hasNext。
public boolean hasNext() { // 這個 size 是外部類 ArrayList 當中的 size 表示的是 ArrayList // 當中資料元素的個數，cursor 的初始值為 0 每調用一個 next cursor // 的值就+1，當等于 size 是容器當中的資料已經周遊完成了 hasNext 就傳回 false 了 return cursor != size;} @SuppressWarnings("unchecked")public E next() { // 這個方法主要是用于檢測在資料疊代的過程當中 ArrayList 是否發生 `結構修改` // 如果發生結構修改就抛出 ConcurrentModificationException 異常 checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); // 更改 cursor 的值 并将其設定為下一個傳回元素的下标 這一點我們在 // 字段分析的時候已經談到過了 cursor = i + 1; // 傳回資料 表達式 lastRet = i 的傳回值為 i // 這個表達式不僅将 lastRet 的值指派為 i 同時傳回 i // 是以可以傳回下标為 i 的資料 return (E) elementData[lastRet = i];} // 這個方法主要是用于檢測在資料疊代的過程當中 ArrayList 是否發生 `結構修改`// 如果發生結構修改就抛出 ConcurrentModificationException 異常final void checkForComodification() { // 如果發生 `結構修改` 那麼 modCount 的值會++ 那麼就和 expectedModCount 不相等了 // expectedModCount 初始化的時候令其等于 expectedModCount if (modCount != expectedModCount) throw new ConcurrentModificationException();} 為什麼要抛出ConcurrentModificationException異常呢，我們先想想是什麼導緻modCount發生變化。肯定疊代器在進行周遊的同時，修改了modCount的值，通常這種現象的發生出現在并發的情況下，是以抛出ConcurrentModificationException異常。像這種通過疊代器周遊過程進行檢查并且當發生不符合條件的情況下抛出異常的現象就稱作Fast-fail。
其實我們也可以在不使用并發的情況讓疊代器抛出這個異常，我們隻需要在疊代器疊代的時候我們對ArrayList進行add和remove操作即可。比如像下面這樣就會抛出ConcurrentModificationException：
public void testArrayList() { ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < 10; i++) list.add(i); Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); list.add(55); }} Iterator中的remove方法
public void remove() { if (lastRet < 0) throw new IllegalStateException(); // 進行合法性檢查，看是否需要抛出異常 checkForComodification(); try { // 調用 ArrayList 的remove方法實作 ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; // 因為 remove 會改變 modCount 的值，是以需要将 expectedModCount 重新指派 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }} ArrayList雜談
時間複雜度分析
- 因為ArrayList是随機存取的，是以我們通過下标查找資料的時間複雜度是O(1)。
- 插入資料的時間複雜度是O(n)。
擴容機制
還記的我們在ArrayList設計與實作，自己動手寫ArrayList當中自己實作ArrayList使用的擴容機制嗎？我們自己的擴容機制為擴容為原來長度的兩倍，而ArrayList當中的擴容機制為擴容為原來的1.5倍。
假設我們在使用ArrayList的時候沒有指定初始化的時候數組的長度，也就是說初始長度為ArrayList的預設長度也就是10。那麼當我們不停地往容器當中增加資料，擴容導緻的數組長度的變化如上圖所示，橫軸表示擴容次數，縱軸表示數組長度，藍色的擴容為原數組長度的1.5倍，另外一條是2倍。我們很清晰的發現擴容為原來的2倍在後期的數組長度将會遠大于擴容1.5倍。這很可能會導緻我們會浪費很大的數組空間，比如說剛好加入最後一個資料的時候導緻ArrayList進行擴容操作，這可能是ArrayList在設計時候的考量。
本篇文章我們仔細分析介紹了ArrayList的源碼，希望大家有所收獲，我是LeHung，我們下期再見！！！