【Java集合原始碼】關於ArrayList的幾個問題

1.說說對 ArrayList 的理解？

ArrayList 內容很多，可以先從總體架構入手，然後再以某個細節作為突破口，比如這樣：ArrayList 底層資料結構是個陣列，其 API 都做了一層對陣列底層存取的封裝，比如說 add 方法的過程是……（這裡具體可以參考 ArrayList 原始碼分析中 add 的過程）。

另外，對 LinkedList 的理解也是同樣套路。

2.擴容相關問題

2.1 ArrayList 無引數構造器構造，現在 add 一個值進去，此時陣列的大小是多少，下一次擴容前最大可用大小是多少？

答：此處陣列的大小是 1，下一次擴容前最大可用大小是 10，因為 ArrayList 第一次擴容時，是有預設值的，預設值是 10，在第一次 add 一個值進去時，陣列的可用大小被擴容到 10 了。

2.2 如果連續往 list 裡面新增值，增加到第 11 個的時候，陣列的大小是多少？

答：這裡實際問的是擴容的公式，當增加到 11 的時候，此時我們希望陣列的大小為 11，但實際上陣列的最大容量只有 10，不夠了就需要擴容，擴容的公式是：oldCapacity + (oldCapacity>> 1)，oldCapacity 表示陣列現有大小，目前場景計算公式是：10 + 10 ／2 = 15，然後我們發現 15 已經夠用了，所以陣列的大小會被擴容到 15。

2.3 陣列初始化，被加入一個值後，如果使用 addAll 方法，一下子加入 15 個值，那麼最終陣列的大小是多少？

答：在上一題中已經計算出來陣列在加入一個值後，實際大小是 1，最大可用大小是 10 ，現在需要一下子加入 15 個值，那我們期望陣列的大小值就是 16，此時陣列最大可用大小隻有 10，明顯不夠，需要擴容，擴容後的大小是：10 + 10 ／2 = 15，這時候發現擴容後的大小仍然不到我們期望的值 16，這時候原始碼中有一種策略如下：

// newCapacity 本次擴容的大小，minCapacity 我們期望的陣列最小大小
// 如果擴容後的值 < 我們的期望值，我們的期望值就等於本次擴容的大小
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

所以最終陣列擴容後的大小為 16。具體原始碼請參考ArrayList 原始碼分析的grow方法。

2.4 現在有一個很大的陣列需要拷貝，原陣列大小是 5k，請問如何快速拷貝？

答：因為原陣列比較大，如果新建新陣列的時候，不指定陣列大小的話，就會頻繁擴容，頻繁擴容就會有大量拷貝的工作，造成拷貝的效能低下，所以在新建陣列時，指定新陣列的大小為 5k 即可。

2.5 為什麼說擴容會消耗效能？

答：擴容底層使用的是 System.arraycopy 方法，會把原陣列的資料全部拷貝到新陣列上，所以效能消耗比較嚴重。

2.6 原始碼擴容過程有什麼值得借鑑的地方？

答：有兩點：

擴容的思想值得學習，通過自動擴容的方式，讓使用者不用關心底層資料結構的變化，封裝得很好，1.5 倍的擴容速度，可以讓擴容速度在前期緩慢上升，在後期增速較快，大部分工作中要求陣列的值並不是很大，所以前期增長緩慢有利於節省資源，在後期增速較快時，也可快速擴容。
擴容過程中，有陣列大小溢位的意識，比如要求擴容後的陣列大小，不能小於 0，不能大於 Integer 的最大值。

3. 刪除相關問題

3.1 有一個 ArrayList，資料是 2、3、3、3、4，中間有三個 3，現在通過 for (int i=0;i<list.size ();i++) 的方式，想把值是 3 的元素刪除，請問可以刪除乾淨麼？最終刪除的結果是什麼，為什麼？刪除程式碼如下：

List<String> list = new ArrayList<String>() {{
  add("2");
  add("3");
  add("3");
  add("3");
  add("4");
}};
for (int i = 0; i < list.size(); i++) {
  if (list.get(i).equals("3")) {
    list.remove(i);
  }
}

答：不能刪除乾淨，最終刪除的結果是 2、3、4，有一個 3 刪除不掉，原因我們看下圖：
圖片描述從圖中我們可以看到，每次刪除一個元素後，該元素後面的元素就會往前移動，而此時迴圈的 i 在不斷地增長，最終會使每次刪除 3 的後一個 3 被遺漏，導致刪除不掉。

3.2 還是上面的 ArrayList 陣列，我們通過增強 for 迴圈進行刪除，可以麼？

答：不可以，會報錯。因為增強 for 迴圈過程其實呼叫的就是迭代器的 next () 方法，當你呼叫 list.remove () 方法進行刪除時，modCount 的值會 +1，而這時候迭代器中的 expectedModCount 的值卻沒有變，導致在迭代器下次執行 next () 方法時，expectedModCount != modCount 就會報 ConcurrentModificationException 的錯誤。

3.3 還是上面的陣列，如果刪除時使用 Iterator.remove () 方法可以刪除麼，為什麼？

答：可以的，因為 Iterator.remove () 方法在執行的過程中，會把最新的 modCount 賦值給 expectedModCount，這樣在下次迴圈過程中，modCount 和 expectedModCount 兩者就會相等。

3.4 以上三個問題對於 LinkedList 也是同樣的結果麼？

答：是的，雖然 LinkedList 底層結構是雙向連結串列，但對於上述三個問題，結果和 ArrayList 是一致的。

4.與LinkedList對比的問題

4.1 ArrayList 和 LinkedList 有何不同？

答：可以先從底層資料結構開始說起，然後以某一個方法為突破口深入，比如：

最大的不同是兩者底層的資料結構不同，ArrayList 底層是陣列，LinkedList 底層是雙向連結串列
兩者的資料結構不同也導致了操作的 API 實現有所差異，拿新增實現來說，ArrayList 會先計算並決定是否擴容，然後把新增的資料直接賦值到陣列上，而 LinkedList 僅僅只需要改變插入節點和其前後節點的指向位置關係即可。

4.2 ArrayList 和 LinkedList 應用場景有何不同？

答：

ArrayList 更適合於快速的查詢匹配，不適合頻繁新增刪除，像工作中經常會對元素進行匹配查詢的場景比較合適
LinkedList 更適合於經常新增和刪除，對查詢反而很少的場景。

4.3 ArrayList 和 LinkedList 兩者有沒有最大容量？

答：

ArrayList 有最大容量的，為 Integer 的最大值，大於這個值 JVM 是不會為陣列分配記憶體空間的
LinkedList 底層是雙向連結串列，理論上可以無限大。但原始碼中，LinkedList 實際大小（size）用的是 int 型別，這也說明了 LinkedList 不能超過 Integer 的最大值，不然會溢位。

4.4 ArrayList 和 LinkedList 是如何對 null 值進行處理的？

答：

ArrayList 允許 null 值新增，也允許 null 值刪除。刪除 null 值時，是從頭開始，找到第一值是 null 的元素刪除
LinkedList 新增刪除時對 null 值沒有特殊校驗，是允許新增和刪除的。

5.執行緒安全問題

5.1 ArrayList 和 LinedList 是執行緒安全的麼，為什麼？

答：

當兩者作為非共用變數時，比如說僅僅是在方法裡面的區域性變數時，是沒有執行緒安全問題的，只有當兩者是共用變數時，才會有執行緒安全問題。
主要的問題點在於多執行緒環境下，所有執行緒任何時刻都可對陣列和連結串列進行操作，這會導致值被覆蓋，甚至混亂的情況。就像ArrayList 自身的 elementData、size、modConut 在進行各種操作時，都沒有加鎖，而且這些變數的型別並非是可見（volatile）的，所以如果多個執行緒對這些變數進行操作時，可能會有值被覆蓋的情況。

如果有執行緒安全問題，在迭代的過程中，會頻繁報 ConcurrentModificationException 的錯誤，意思是在我當前迴圈的過程中，陣列或連結串列的結構被其它執行緒修改了

5.2 如何解決執行緒安全問題？

答：Java 原始碼中推薦使用 Collections#synchronizedList 進行解決，Collections#synchronizedList 的返回值是 List 的每個方法都加了 synchronized 鎖，保證了在同一時刻，陣列和連結串列只會被一個執行緒所修改，但是效能大大降低，具體實現原始碼：

public boolean add(E e) {
    synchronized (mutex) {// synchronized 是一種輕量鎖，mutex 表示一個當前 SynchronizedList
        return c.add(e);
    }
}

另外，還可以採用 JUC 的 CopyOnWriteArrayList 並行 List 來解決。