ArrayList 從源碼角度剖析底層原理
對于 ArrayList 來說，我們平常用的最多的方法應該就是 add 和 remove 了，本文就主要通過這兩個基礎的方法入手，通過源碼來看看 ArrayList 的底層原理。
add
默認添加元素
這個應該是平常用的最多的方法了，其用法如下。
接下來我們就來看看 add 方法的底層源碼。
ensureCapacityInternal 作用為：保證在不停的往 ArrayList 插入數據時，數組不會越界，并且實現自動擴容。
這里的 minCapacaity 的值，實際上就是在調用完當前這次 add 操作之后，數組中元素的數量
注意，這里說當前這次 add 操作完成。舉個例子，調用 add 之前，ArrayList 中有3個元素，那么此時這個 minCapacity 的值就為 4
此外，可以看到將函數 calculateCapacity 的返回值作為了 ensureExplicitCapacity 的輸入。
calculateCapacity 做了什么，用大白話來說是，如果當前數組是空的，則直接返回 數組默認長度(10) 和 minCapacity 的最大值，否則就直接返回 minCapacity 。
接下里是 ensureExplicitCapacity ，源碼如下：
modCount 表示該 ArrayList 被更改過多少次，這里的更改不只是新增，刪除也是一種更改。通過上面的了解我們知道，如果當前數組內的元素個數是小于數組長度的，則 minCapacity 的值一定是小于 elementData.length 的。
相反，如果數組內的元素個數已經和數組長度相等了，則 0>0 一定是 false ，此時就會調用 grow 函數來進行數組擴容。
核心邏輯很簡單，新的數組長度 = 舊數組長度 + 舊數組長度/2。
這里的右移，就相當于直接除以2
所以通過這里的源碼我們驗證，ArrayList 的擴容是每次擴容 1.5 倍。但是這里會有一個疑問，因為上文提到擴容時 minCapacity 的值和數組長度應該是相等的，所以 新數組長度 - minCapacity 應該永遠大于0才對，為什么會有小于0的情況?
答案是 addAll 。
可以看到，add 和 addAll 底層都會調用 ensureCapacityInternal 。add 是往數組中添單個元素，而 addAll 則是往數組中添加整個數組。假設 addAll 我們傳進了一個很大的值，舉個例子，ArrayList 的默認數組長度為 10 ，擴容一次之后長度為 15 ，假設我們傳入的數組元素有 10 個，那么即使擴容一次還是不足以放下所有的元素，因為 15 < 20。
所以才會出現 newCapacity(擴容之后的數組長度) < minCapacity(執行完當前操作之后的數組內元素數量) 的情況，所以當這種情況出現之后，就會直接將 minCapacity 的值賦給 newCapacity 。
除此之外，還會有個極端的情況，假設 addAll 往里面塞入了 Integer.MAX_VALUE 個元素呢?這就是 hugeCapacity 函數要處理的邏輯了。首先如果溢出了就直接拋出 OOM 異常，其次會保證其容量不會超過 Integer.MAX_VALUE。
最后是真正執行擴容的操作，調用了 java.util 包里的 Arrays.copyOf 方法。從上圖可以看出，這個方法中傳入了兩個參數，分別是存放元素的數組、新的數組長度，舉個例子：
- int[] elementData = {1, 2, 3, 4, 5};
- int[] newElementData = Arrays.copyOf(elementData, 10);
- System.out.println(newElementData); // [1 2 3 4 5 0 0 0 0 0]
數組擴容完成之后，就會將本次 add 的元素寫入 elementData 的末尾了，elementData[size++] = e 。
接下來我們用流程圖來總結一下 add 操作的整個核心流程。
指定添加元素的位置
了解完了 add 和 addAll，我們趁熱打鐵，來看看可以指定元素位置的 add ，其接受兩個參數，分別是：
- 新元素在數組中的下標
- 新元素本身
這里和最開始的 add 就有些不同了，之前的 add 方法會將元素放在數組的末尾，而 add(int index, E element) 則會將元素插入到數組中指定的位置，接下來從源碼層面看看。
首先，由于這個方法允許用戶傳入數組下標，所以首先要做的事情就是檢查傳入的數組下標是否合法，如果不合法則會直接拋出 IndexOutOfBoundsException 異常。
很簡單的判斷，下標 index 不能小于0，并且不能超過數組中的元素個數，舉個例子：
像上圖這種情況，調用 add(int index, E element) 之前，數組內有3個元素，即使底層數組的長度為10 ，但是數組下標如果傳入5，是會拋出 IndexOutOfBoundsException 異常的。在上圖這種情況，index 的值最大只能為3才不會報錯，因為 index(下標為3) > size(3個元素) 肯定不為 true 。
完成了校驗之后，還是會調用上面聊到過的 ensureCapacityInternal 方法，根據需要，來對底層的數組進行擴容。然后調用 System.arraycopy 方法，這個方法比較關鍵，也比較難理解，所以我就簡單一句話把它的作用概括了——將制定下標后的元素全部往后移動一位。
System.arraycopy 接收 4 個參數，分別是：
- 原數組
- 原數組中的起始下標
- 目標數組
- 目標數組中的起始下標
光看參數，不結合例子，其實很難理解，我這里舉個簡單的例子。
假設現在數組里有元素 [1 2 3] ，然后此時我調用方法 add(1, 4) ，表明我想要將元素 4 插入到數組下標為 1 的位置，那么此時 index 的值為1，size 的值為 3。
System.arraycopy 的方法就會變成 System.arraycopy(elementData, 1, elementData, 2, 2)，也就是將 elementData 從下標 1 開始的兩個元素(也就是 2 和 3)，拷貝到 elementData 的從下標 2 開始的地方。
可能還是有點繞，說人話就是執行完后，elementData 就變成了 [1 2 2 3]，然后再對 elementData 進行賦值，將下標為 1 的元素改為本次需要 add 的元素。再說句人話就變成了 [1 4 2 3]。
所以綜上來看，沒有什么黑魔法，主要需要了解的就是兩個關鍵的函數，分別是 Arrays.copy 和 System.arraycopy 。我們需要把這兩個封裝好的函數的作用給記住。
- Arrays.copy 數組擴容
- System.arraycopy 將數組中某個下標之后元素全部往后移動一位
所以從這里就可以看到，看源碼的好處，主要有兩個方面。第一，我相信你在刷題的時候一定也遇到過需要將數組的元素整個后移的 case，但是你可能并不知道可以使用 System.arraycopy ，就算你知道有這么個函數可能就連參數都看不懂;第二，知道了 System.arraycopy ，但是覺得這些函數完全沒有應用場景。
remove
了解數據怎么來，接下來我們來看一下數據是怎么被移除的。首先我們來看最常用的兩種：
- 按照下標移除
- 根據元素移除
根據下標移除
首先是根據下標移除
這里也會先檢查傳入的 index 是否合法，但是這里的 index 和 add 中調用的 rangeCheck 還有點區別。add 中的 rangeCheckForAdd 會判斷 index 是否為負數，而 remove 中的 rangeCheck 則只會判斷 index 是否 >= 數組中的元素個數。
其實從函數的名稱就能看出，rangeCheckForAdd 是專門給 add 方法用的
那如果此時傳入的 index 真的是負數怎么辦?其實是會拋出 ArrayIndexOutOfBoundsException ，因為remove 方法上加了 Range 注解。
完成后，還是會更新 modCount 的值，這也驗證了我們上面提到的 modCount 代表的更改中也包含了刪除。
接下來會計算一個 numMoved ，代表需要被移動的元素數量。add 一個元素，對應的下標的元素都需要往后順移一位，remove 同理，刪除了某個位置的元素后，其后面對應的所有的元素都需要往前順移一位，就像這樣：
知道了需要移動多少個元素之后，我們的 System.arraycopy 就又可以登場了。完成了元素的移動之后，數組的末尾必然會空出來一個元素，直接將其設置為 null 然后交給 GC 回收即可，最后把被移除的值返回。
根據值移除
舉個例子，根據值移除就長下面這樣這樣。
廢話不多說，直接看核心源碼
完了，第二行就給整懵了，移除一個 null 是什么鬼?還要循環去移除?
實際上，ArrayList 允許我們傳 null 值進去，再舉個例子。
看完這個例子，應該就能夠明白為什么要做 o == null 的判斷了。如果傳入的是 null ，ArrayList 會對底層的數組進行遍歷，并移除匹配到的第一個值為 null 的元素。
如果值不為 null 也是同理，如果數組中有多個一樣的值，ArrayList 也會對其進行遍歷，并且移除匹配到的第一個值。通過源碼可以看到，無論值是否為 null ，其都會調用真正的刪除元素方法 fastRemove ，干的事情就跟 remove 做的幾乎一樣。
他們的唯一的區別在于，按照下標移除，會返回被移除的元素;按照值移除只會返回是否移除成功。
總結
所以，看完 ArrayList 的部分源碼之后，我們就可以知道，ArrayList 的底層數據結構是數組。雖然對于用戶來說 ArrayList 是個動態的數組，但是實際上底層是個定長數組，只是在必要的時候，對底層的數組進行擴容，每次擴容 1.5 倍。但是從源碼也看出來了，擴容、刪除都是有代價的，特別是在極端的情況，會需要將大量的元素進行移位。
所以我們得出結論，ArrayList 如果有頻繁的隨機插入、頻繁的刪除操作是會對其性能造成很大影響的， 總結來說，ArrayList 適合用于讀多寫少的場景。
另一個很重要很重要的點，這里提一下，ArrayList 不是線程安全的。多線程的情況下會出現數據不一致或者會拋出 ConcurrentModificationException 異常，關于這塊后面有機會再聊吧
了解完如何向一個數據結構中存取、移除數據，其實就已經能夠順理成章的理解跟其相關的很多事情了。
舉個例子，indexOf 方法用于返回指定元素在數組中的下標，了解完 remove 中的遍歷匹配，或者說你甚至可以直接靠直覺就應該想到，indexOf 不就是個 for 循環匹配嗎?lastIndexOf 不就是個反向的 for 循環匹配嗎?所以在這里再貼出源碼除了讓文章篇幅更長之外，沒有任何意義。這個感興趣的話可以找源碼看一看。
