詳解ArrayList的擴容機制

Posted on by

一、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 人如其名，它的底層自然是基於鏈表的，而且還是個雙向鏈表。鏈表的特性和數組正好是反的，由於沒有索引，所以查詢效率低，但是增刪速度快。

二、ArrayList 如何指定底層數組大小的

OK，首先，既然咱真正存儲數據的地方是數組，那我們初始化 ArrayList 的時候自然要給數組分配一個大小，開辟一個內存空間。我們先來看看 ArrayList 的無參構造函數：

可以看到，它為底層的 Object 數組也就是 elementData 賦值瞭一個默認的空數組 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。也就是說，使用無參構造函數初始化 ArrayList 後，它當時的數組容量為 0 。

這給咱初始化一個容量為 0 的數組有啥用？啥也存不瞭啊？別急，如果使用瞭無參構造函數來初始化 ArrayList， 隻有當我們真正對數據進行添加操作 add 時，才會給數組分配一個默認的初始容量 DEFAULT_CAPACITY = 10。看下圖：

說完瞭無參構造，ArrayList 的有參構造函數就是中規中矩瞭，按照用戶傳入的大小開辟數組空間：

三、數組的大小一旦被規定就無法改變

 ArrayList 是怎麼對底層數組進行擴容的？

ArrayList 的底層實現是 Object 數組，我們知道，數組的大小一旦被規定就無法改變。那如果我們不斷的往裡面添加數據的話，ArrayList 是如何進行擴容的呢？或者說 ArrayList 是如何實現存放任意數量對象的呢？

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

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

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

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

四、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 ++ 就好，這個方法應該是我們最常使用的：

五、ArrayList 又是如何刪除數據的呢

Ctrl + F 找到 remove 方法，就這？和添加一個道理，也是復制數組

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

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

六、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 要慢。

七、為什麼線程不安全還要用它呢

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

以上就是詳解ArrayList的擴容機制的詳細內容，更多關於ArrayList 擴容機制的資料請關註WalkonNet其它相關文章！

推薦閱讀：