【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 來解決，