技術文章 » 送分題，ArrayList 的擴容機制瞭解嗎？

送分題，ArrayList 的擴容機制瞭解嗎？

2022-06-21 12:01:04

1. ArrayList 瞭解過嗎？它是啥？有啥用?

眾所周知，Java 集合框架擁有兩大介面 Collection 和 Map，其中，Collection 麾下三生子 List、Set 和 Queue。ArrayList 就實現了 List 介面，其實就是一個陣列列表，不過作為 Java 的集合框架，它只能儲存物件參照型別，也就是說當我們需要裝載的資料是諸如 int、float 等基本資料型別的時候，必須把它們轉換成對應的包裝類。

ArrayList 的底層實現是一個 Object 陣列：

既然它是基於陣列實現的，陣列在記憶體空間中是連續分配的，那必然查詢速率非常快，不過當然也肯定逃不過增刪效率低的缺陷。

另外，和 ArrayList 一樣同樣實現了 List 介面的、我們比較常用的還有 LinkedList。LinkedList 比較特殊，它不僅實現了 List 介面，還實現了 Queue 介面，所以你可以看見 LinkedList 經常被當作佇列使用：

Queue<Integer> queue = new LinkedList<>();

LinkedList 人如其名，它的底層自然是基於連結串列的，而且還是個雙向連結串列。連結串列的特性和陣列正好是反的，由於沒有索引，所以查詢效率低，但是增刪速度快。

2. ArrayList 如何指定底層陣列大小的？

OK，首先，既然咱真正儲存資料的地方是陣列，那我們初始化 ArrayList 的時候自然要給陣列分配一個大小，開闢一個記憶體空間。我們先來看看 ArrayList 的無參建構函式：

可以看到，它為底層的 Object 陣列也就是 elementData 賦值了一個預設的空陣列 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。也就是說，使用無參建構函式初始化 ArrayList 後，它當時的陣列容量為 0 。

這給咱初始化一個容量為 0 的陣列有啥用？啥也存不了啊？別急，如果使用了無參建構函式來初始化 ArrayList， 只有當我們真正對資料進行新增操作 add 時，才會給陣列分配一個預設的初始容量 DEFAULT_CAPACITY = 10。看下圖：

說完了無參構造，ArrayList 的有參建構函式就是中規中矩了，按照使用者傳入的大小開闢陣列空間：

3. 陣列的大小一旦被規定就無法改變，那 ArrayList 是怎麼對底層陣列進行擴容的？

ArrayList 的底層實現是 Object 陣列，我們知道，陣列的大小一旦被規定就無法改變。那如果我們不斷的往裡面新增資料的話，ArrayList 是如何進行擴容的呢？或者說 ArrayList 是如何實現存放任意數量物件的呢？

OK，擴容發生在啥時候？那肯定是我們往陣列中新加入一個元素但是發現陣列滿了的時候。沒錯，我們去 add 方法中看看 ArrayList 是怎麼做擴容的：

ensureExplicitCapacity 判斷是否需要進行擴容，很顯然，grow 方法是擴容的關鍵：

說實話，別的都不用看了，看上面圖中的黃色框框就知道 ArrayList 是怎麼擴容的了：擴容後的陣列長度 = 當前陣列長度 + 當前陣列長度 / 2。最後使用 Arrays.copyOf 方法直接把原陣列中的陣列 copy 過來，需要注意的是，Arrays.copyOf 方法會建立一個新陣列然後再進行拷貝。

舉個例子畫個圖來演示一下：

4. 既然擴容發生在新增資料的時候，講講 ArrayList 具體是怎麼新增資料的

OK，add 方法我們剛剛講了一半，新增資料前會先判斷一下是否需要擴容，真正的新增資料的操作在下半部分：

先講下 add(int index, E element) 這個方法的含義，就是在指定索引 index 處插入元素 element。比如說 ArrayList.add(0, 3)，意思就是在頭部插入元素 3。

再來看看 add 方法的核心 System.arraycopy，這個方法有 5 個引數：

  • elementData：源陣列
  • index：從源陣列中的哪個位置開始複製
  • elementData：目標陣列
  • index + 1：複製到目標陣列中的哪個位置
  • size - index：要複製的源陣列中陣列元素的數量

解釋一下上面程式碼中 arraycopy 的意思，舉個例子，我們想要在 index = 5 的位置插入元素，首先，我們會複製一遍源陣列 elementData（這裡我們稱複製的陣列為新陣列吧），然後把源陣列中從 index = 5 的位置開始到陣列末尾的元素，放到新陣列的 index + 1 = 6 的位置上：

於是，這就給我們要新增的元素騰出了位置，然後在新陣列 index = 5 的位置放入元素 element 就完成了新增的操作：

顯然，不用多說，ArrayList 的將資料插入到指定位置的操作效能非常低下，因為要開闢新陣列複製元素啊，要是涉及到擴容那就更慢了。

另外，ArrayList 還內建了一個直接在末尾新增元素的 add 方法，不用複製陣列，直接 size ++ 就好，這個方法應該是我們最常使用的：

5. ArrayList 又是如何刪除資料的呢？

Ctrl + F 找到 remove 方法，就這？和新增一個道理，也是複製陣列

舉個例子，假設我們要刪除陣列的 index = 5 的元素，首先，我們會複製一遍源陣列，然後把源陣列中從 index + 1 = 6 的位置開始到陣列末尾的元素，放到新陣列的 index = 5 的位置上：

也就是說 index = 5 的元素直接被覆蓋掉了，給了你被刪除的感覺。同樣的，它的效率自然也是十分低下的

6. ArrayList 是執行緒安全的嗎？不安全的表現

ArrayList 和 LinkedList 都不是執行緒安全的，我們以在末尾新增元素的 add 方法為例，來看看 ArrayList 執行緒不安全的表現是啥：

黃色框裡的並不是一個原子操作，它由兩步操作構成：

elementData[size] = e;
size = size + 1;

在單執行緒執行這兩條程式碼時，那當然沒有任何問題，但是當多執行緒環境下執行時，可能就會發生一個執行緒新增的值覆蓋另一個執行緒新增的值。舉個例子：

  • 假設 size = 0，我們要往這個陣列的末尾新增元素
  • 執行緒 A 開始新增一個元素，值為 A。此時它執行第一條操作，將 A 放在了陣列 elementData 下標為 0 的位置上
  • 接著執行緒 B 剛好也要開始新增一個值為 B 的元素，且走到了第一步操作。此時執行緒 B 獲取到的 size 值依然為 0，於是它將 B 也放在了 elementData 下標為 0 的位置上
  • 執行緒 A 開始增加 size 的值，size = 1
  • 執行緒 B 開始增加 size 的值，size = 2

這樣，執行緒 A、B 都執行完畢後，理想的情況應該是 size = 2，elementData[0] = A，elementData[1] = B。而實際情況變成了 size = 2，elementData[0] = B（執行緒 B 覆蓋了執行緒 A 的操作），下標 1 的位置上什麼都沒有。並且後續除非我們使用 set 方法修改下標為 1 的值，否則這個位置上將一直為 null，因為在末尾新增元素時將會從 size = 2 的位置上開始。

上段程式碼驗證下：

結果和我們分析的一樣：

ArrayList 的執行緒安全版本是 Vector，它的實現很簡單，就是把所有的方法統統加上 synchronized ：

既然它需要額外的開銷來維持同步鎖，所以理論上來說它要比 ArrayList 要慢。

7. 為什麼執行緒不安全還要用它呢？

因為在大多數場景中，查詢的情況居多，不會涉及太頻繁的增刪。那如果真的涉及頻繁的增刪，可以使用LinkedList，底層連結串列實現，為增刪而生。而如果你非得保證執行緒安全那就使用 Vector。當然實際開發中使用最多的還是 ArrayList，雖然執行緒不安全、增刪效率低，但是查詢效率高啊。

小夥伴們大家好呀，我是小牛肉，公眾號【飛天小牛肉】定期推播大廠面試題，提供背誦版 + 詳細版，知其然而知其所以然，讓八股文變得有價值！）