Java小白集合源碼的學習系列：ArrayList
目錄
- ArrayList源碼學習
- ArrayList的繼承體系
- ArrayList核心源碼
- ArrayList擴容機制
- 最後的總結
ArrayList源碼學習
本文基于JDK1.8版本，對集合中的巨頭ArrayList做一定的源碼學習，将會參考大量資料，在文章後面都将會給出參考文章連結，本文用以鞏固學習知識。
ArrayList的繼承體系
ArrayList繼承了AbstracList這個抽象類，還實作了List接口，提供了添加、删除、修改、周遊等功能。至于其他接口，以後再做總結。
ArrayList核心源碼
底層基于數組實作，我們可以檢視源碼，了解其擁有的一些屬性：
複制 private static final long serialVersionUID = 8683452581122892189L;
//預設的初始容量為10
private static final int DEFAULT_CAPACITY = 10;
//如果指定數組容量為0，傳回該數組，相當于new ArrayList<>(0);
private static final Object[] EMPTY_ELEMENTDATA = {};
//沒有指定容量時，傳回該數組，與上面不同的是：new ArrayList<>();
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//該數組儲存着ArrayList存儲的元素，任何沒有指定容量的ArrayList在添加第一個元素後，将會擴容至初始容量10
transient Object[] elementData; // non-private to simplify nested class access
//代表了目前存儲元素的數量
private int size; 再次強調将
EMPTY_ELEMENTDATA
和
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
區分開來是為了明确添加第一個元素時，應該擴容的大小，具體擴容的機制，後面會分析。
我們再來瞧瞧它的構造器：
複制 //該構造器用以建立一個可以指定容量的清單
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//建立一個指定容量大小的數組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//指定容量為0，對應EMPTY_ELEMENTDATA數組
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//預設無參構造器，指派空數組，但是在第一次添加之後，容量變為預設容量10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//傳入一個集合，根據該集合疊代器傳回順序，構造一個指定集合裡元素的清單
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
//傳入集合不為空長
if ((size = elementData.length) != 0) {
//傳入集合轉化為的數組可能不是Object[]需要判斷
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//傳入集合為元素數量為0，用空數組代替即可
this.elementData = EMPTY_ELEMENTDATA;
}
}
//指定集合為null的話（并不是說集合為空長），調用ArrayList的toArray方法，可能會抛出空指針異常 ArrayList擴容機制
了解完ArrayList基本的屬性和構造器之後，我們将對裡面包含的方法進行學習：
- 上面說到，使用預設構造器時，初始化指派其實是個空數組，在添加了一個元素之後，容量才會變成10，是不是會覺得有點好奇呢，我們先來瞧一瞧它的add系列方法：
複制 //沒有指定索引，預設在尾部添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//擴容之後，下一位指派為e，size加1
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//判斷是否為預設構造器生成的數組，并将minCapacity置為0；如果不是，minCapacity還是傳入的size+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//使用預設構造器，那麼才會傳回所需要的最小容量為預設容量10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//minCapacity = size+1
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//定義在AbstractList中，用于存儲結構修改次數
modCount++;
//如果最小容量比數組總長度還大，就擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴容操作
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//将舊容量右移一位在加上本身，像當于新容量為就容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//1.新數組的容量還是不能滿足需要的最小容量，如初始指定容量為0時的情況
//2.新數組越過了整數邊界，newCapacity将會小于0
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新數組的容量比數組最大的容量Integer.MAX_VALUE - 8還大，
//調用hugeCapacity方法
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
//比較最小容量和MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//三目表達式：如果真的需要擴這麼大容量的情況下：
//1.最小容量大于MAX_ARRAY_SIZE，新容量等于Integer.MAX_VALUE，否則新容量為Integer.MAX_VALUE-8
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
} - 根據擴容操作，如果我們一開始使用的是預設構造器生成的數組，在第一次增加之後容量就會變成預設容量10，之後才會以1.5倍進行擴容。
- 但是如果我們指定的是以0為容量的話，會通過grow方法，前四次擴容每次都隻是增加1，頻繁地調用copyOf就非常難受了，是以在知道目标大概多大時，可以通過
public void ensureCapacity(int minCapacity)
- 關于
newCapacity - minCapacity < 0
- 當原容量為0或1時，擴容就會滿足該條件。
- 當原容量足夠大時，它的1.5倍會越過整數邊界，變為負值，同樣滿足。
- 注意：移位運算效率會比整除運算更高一些。
- modCount代表的是已對清單進行結構更改的次數，可以看到，每次執行添加操作時，一定都會讓該次數加1。設計到的fail-fast機制，我們之後将會繼續學習，暫不贅述。
- 其實擴容的方式就是我們看到的，建立一個以新容量為長度的新數組，并将原來數組的值全部拷貝到新數組上，最後讓elementData指向這個新數組。
文章寫到這裡，我大舒一口長氣，層層嵌套的調用終于結束了，不知道你們的内心是否也和我一樣哈。我們趁熱打鐵，趕緊看看另一個重載的add方法。
複制 //在索引為index處插入E
public void add(int index, E element) {
//索引越界判斷
rangeCheckForAdd(index);
//同上，確定有足夠容量添加元素
ensureCapacityInternal(size + 1); // Increments modCount!!
//實際上Arrays.copyOf的底層調用的就是這個方法，意思是在原數組上從索引的位置到最後整體向後複制一位，相當于移動的長度為 (size-1) - index +1 = size -index
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在将index處填上元素E
elementData[index] = element;
//元素數量+1
size++;
} 有了前面的鋪墊，相對來說就比較輕松了。我們不妨看看判斷數組越界的方法，媽呀，這就更加清晰了，但是需要注意的是index==size在添加操作裡，相當于從尾部插入，并不會構成越界：
複制 private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} 看完了“增”的兩個方法，該輪到同是四胞胎兄弟的“删”了。再談“删”之前，我們要明确，ArrayList底層基于數組實作，可依靠連續索引值存取擷取資料就變得理所當然了：
複制 E elementData(int index) {
return (E) elementData[index];
} 下面是“删”操作，需要注意的是，remove操作并不能夠将容量減少，隻是将其中的元素數量變少，自始至終隻是size在變化，不信你看：
複制 //移除指定位置的元素，并将其傳回
public E remove(int index) {
//範圍判斷
rangeCheck(index);
//操作清單，計數加1
modCount++;
//取出舊值
E oldValue = elementData(index);
//相當于把index+1位置向後的所有元素集體向前複制一位，複制的長度就是
//(size-1)-(index+1)+1 = numMoved
int numMoved = size - index - 1;
if (numMoved > 0)
//執行集體拷貝動作
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//并讓最後一個空出來的位置指向null，點名讓GC清理
elementData[--size] = null;
//傳回舊值
return oldValue;
} 可以稍微看一下rangeCheck的代碼，與add操作裡判定略有不同，省去了index<0的判斷，我一開始很疑惑，後來發現後面有對數組的索引值取值，還是會發生異常：
複制 private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} 我覺得有必要總結一下System.arraycopy這個方法，public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
native修飾符，底層并不是Java實作，而是c和c++。
這個方法的作用呢：就是從指定的源數組（src）從指定位置（srcPos）開始複制數組到目标數組（dest）的指定位置（destPos），複制的個數正好是length。
而Arrays.copyOf這個方法雖然底層調用了System.arraycopy，但是使用上是不太一樣的，它不需要目标數組，系統會自動在内部建立一個數組，并傳回。
哇，感覺add部分講完，真的思路及其清晰，簡直豁然開朗呢。咱們繼續來remove！
複制 //移除指定元素，找到并删除傳回true，沒找到傳回false
public boolean remove(Object o) {
//判斷指定的元素是否本身就是null值
if (o == null) {
for (int index = 0; index < size; index++)
//找到同為null值的那個“它”
if (elementData[index] == null) {
//快速删除，删除操作和之前類似，隻是省略了範圍判斷，就不贅述了
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
//不是空值的話，就找值相等的，注意不要elementData[index].equals(o),時刻避免空指針
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
} 還有一個範圍性的removeRange就不贅述了，總結一下：ArrayList中的remove操作基于數組的拷貝，并将remove的長度置空，元素數量相應減少（隻是元素數量減少，數組容量并不會改變）。
對了，清理的話，clear方法會清理的相對幹淨一些，但是依舊隻是size變化：
複制 public void clear() {
modCount++;
//将所有元素置空，等待GC寵幸
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
} 當然，如果你希望數組容量也發生變化的話。你可以試試下面的這個方法：
複制 //将ArrayList容量調整為目前size的大小
public void trimToSize() {
modCount++;
//基于三目運算
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
} 接下來，講一講相當簡單的set與get這對基佬操作：
複制 //用指定值替換隻當索引位置上的值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//擷取指定索引位置上的值
public E get(int index) {
rangeCheck(index);
return elementData(index);
} 然後是姐妹花操作：indexOf和lastIndexOf。(ps:尋找元素的過程可以參考remove指定元素的過程），以indexOf為例，lastIndexOf從尾部向前周遊即可。
複制 //判斷o在ArrayList中第一次出現的位置
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
} 通過indexOf方法的傳回值，我們還可以判斷某個元素是否存在：
複制 public boolean contains(Object o) {
return indexOf(o) >= 0;
} 除了單個元素增之外，ArrayList中還提供了可以将整個集合增加到本身尾部的方法：
複制 //把傳入集合中的所有元素全部加到本身集合的後面，如果發生改變就傳回true
public boolean addAll(Collection<? extends E> c) {
//将傳入集合轉化為清單，如果傳入集合為null，會發生空指針異常
Object[] a = c.toArray();
int numNew = a.length;
//确定新長度是否需要擴容
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
//傳入為空集合就為false，因為不會發生改變
return numNew != 0;
} 它的重載方法是在指定位置插入另一個集合中地所有元素，并且以疊代的順序排列：
複制 //在指定位置插入另一集合中的所有元素
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
//還是會引發空指針
Object[] a = c.toArray();
//傳入新集合c的元素個數
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
//要移動的個數：(size-1)-index+1 = numMoved
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//size<index的情況，前面就會抛異常，是以這裡隻能index==size，相當于從尾部添加
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
} 最後的總結
- ArrayList基于數組實作，查詢便利，通過擴容機制實作動态增長。
- 預設構造器生成的ArrayList初始化指派其實是空數組，增加第一個元素之後變為10.
- 擴容機制讓每次的新容量都是原容量的1.5倍，且基于右移運算。
- 增加和删除的操作底層基于數組拷貝，底層都調用了arraycopy的方法。
- 由于複制拷貝，導緻增删的操作大多數情況下的效率會降低，但是并不是絕對的，如果一直在尾部插，尾部删的話，還是挺快的。
- 對了，它是線程不安全的，這個以後學習的時候在做總結吧。
對了如果不出意外的話，之後會帶來LinkedList的源碼學習，如果覺得我有叙述錯誤的地方，或者我沒有說明白點地方，還望評論區批評指正，一起學習交流，加油加油！
參考連結：
淺談ArrayList動态擴容
List集合就這麼簡單【源碼剖析】
https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList.md