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