Java 面試題:ArrayList 可以完全替代陣列嗎?

語言: CN / TW / HK

theme: jzman

本文已收錄到  GitHub · AndroidFamily,有 Android 進階知識體系,歡迎 Star。技術和職場問題,請關注公眾號 [彭旭銳] 私信我提問。

前言

大家好,我是小彭。

在前面的文章裡,我們學習了很多資料結構與演算法思想。在實際的業務開發中,往往不需要我們手寫資料結構,而是直接使用標準庫的資料結構 / 容器類。

在後續的文章裡,我們將以 Java 語言為例,分析從 ArrayList 到 LinkedHashMap 等一系列標準庫容器類,最後再有一篇總結回顧,請關注。


學習路線圖:


1. 說一下 ArrayList 和 LinkedList 的區別?

  • 1、資料結構: 在資料結構上,ArrayList 和 LinkedList 都是 “線性表”,都繼承於 Java 的 List 介面。另外 LinkedList 還實現了 Java 的 Deque 介面,是基於連結串列的棧或佇列,與之對應的是 ArrayDeque 基於陣列的棧或佇列;

  • 2、執行緒安全: ArrayList 和 LinkedList 都不考慮執行緒同步,不保證執行緒安全;

  • 3、底層實現: 在底層實現上,ArrayList 是基於陣列的,而 LinkedList 是基於連結串列的。事實上,它們很多特性的區別都是因為底層實現不同引起的。比如說:

    • 在遍歷速度上: 陣列是一塊連續記憶體空間,基於區域性性原理能夠更好地命中 CPU 快取行,而連結串列是離散的記憶體空間對快取行不友好;
    • 在訪問速度上: 陣列是一塊連續記憶體空間,支援 O(1) 時間複雜度隨機訪問,而連結串列需要 O(n) 時間複雜度查詢元素;
    • 在新增和刪除操作上: 如果是在陣列的末尾操作只需要 O(1) 時間複雜度,但在陣列中間操作需要搬運元素,所以需要 O(n)時間複雜度,而連結串列操作只是修改引用指向,只需要 O(1) 時間複雜度。

2. ArrayList 原始碼分析

這一節,我們來分析 ArrayList 中主要流程的原始碼。

2.1 ArrayList 的屬性

ArrayList 的屬性很好理解,底層是一個 Object 陣列,我要舉手提問 🙋🏻‍♀️:

  • 疑問 1: 為什麼 elementData 欄位不宣告 private 關鍵字?
  • 疑問 2: 為什麼 elementData 欄位宣告 transient 關鍵字?
  • 疑問 3: 為什麼elementData 欄位不宣告為泛型型別 E
  • 疑問 4: 為什麼 ArrayList 的最大容量是 Integer.MAX_VALUELong.MAX_VALUE 不行嗎?
  • 疑問 5: 為什麼 ArrayList 的最大容量是 MAX_VALUE - 8,一定會減 8 嗎?

這些問題我們在分析原始碼的過程中回答。疑問這麼多,ArrayList 瞬間不香了。

```java public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { // new ArrayList() 預設初始容量 private static final int DEFAULT_CAPACITY = 10;

// new ArrayList(0) 的全域性空陣列
private static final Object[] EMPTY_ELEMENTDATA = {};

// new ArrayList() 的全域性空陣列
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 修改次數記錄
protected transient int modCount = 0;

// 陣列的最大長度
// 疑問 4:為什麼 ArrayList 的最大容量是 Integer.MAX_VALUE,Long.MAX_VALUE 不行嗎?
// 疑問 5:為什麼 ArrayList 的最大容量是 MAX_VALUE - 8,一定會減 8 嗎?
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8

// 疑問 1:為什麼不宣告 private(後文回答)
// 疑問 2:為什麼宣告 transient(後文回答)
// 疑問 3:為什麼不宣告為泛型型別 E
// 底層陣列
transient Object[] elementData;

// 陣列的有效長度(不是 elementData.length)
private int size;

// size() 返回的是陣列的有效長度(合理,底層陣列我們不關心)
public int size() {
    return size;
}

} ```

2.2 ArrayList 的構造方法

ArrayList 有三個建構函式:

  • 1、帶初始容量的構造方法: 如果初始容量大於 0,則建立指定長度的陣列。如果初始容量是 0,則指向第 1 個全域性空陣列 ;EMPTY_ELEMENTDATA
  • 2、無參構造方法: 指向第 2 個全域性空陣列 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  • 3、帶集合的構造方法: 將集合轉為陣列,如果陣列為空,則指向第 1 個全域性空陣列 EMPTY_ELEMENTDATA

可以看到,除了指定大於 0 的初始容量外,ArrayList 在構造時不會建立陣列,而是指向全域性空陣列,這是懶初始化的策略。

構造器的原始碼不難,但小朋友總有太多的問號,舉手提問 🙋🏻‍♀️:

  • 疑問 6:既然都是容量為 0 ,為什麼 ArrayList 要區分出 2 個空陣列?

這個問題直接回答吧:ArrayList 認為無參建構函式應該使用預設行為,在首次新增資料時會建立長度為 10(DEFAULT_CAPACITY) 的預設初始陣列;而顯示設定初始容量為 0 是開發者的顯式意圖,所以不使用預設初始陣列,在首次新增資料時只會建立長度為 1 (size + 1)的陣列(可以結合後文原始碼理解下)。

  • 疑問 7: 在帶集合的構造方法中,為什麼會存在集合轉化後的陣列型別不是 Object[].class 的情況?

```java // 帶初始容量的構造方法 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // 建立 initialCapacity 長度的陣列 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { // 指向第 1 個全域性空陣列 this.elementData = EMPTY_ELEMENTDATA; } else { // 不合法的初始容量 throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); } }

// 無參構造方法 public ArrayList() { // 指向第 1 個全域性空陣列 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

// 帶集合的構造方法 public ArrayList(Collection<? extends E> c) { // 將集合轉為陣列 elementData = c.toArray(); if ((size = elementData.length) != 0) { // 疑問 7:這一個條件語句好奇怪,toArray() 的返回值型別就是 Object[] 啊? if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = EMPTY_ELEMENTDATA; } }

public Object[] toArray() { return Arrays.copyOf(elementData, size); } ```

2.3 ArrayList 的新增與擴容方法

ArrayList 有 4 個新增方法,可以在陣列末尾或陣列中間新增元素。如果是在陣列末尾新增,均攤時間只需要 O(1) 時間複雜度;如果在陣列中間新增,由於需要搬運資料,所以需要 O(n) 時間複雜度。

新增前會先檢查資料容量,不足會先擴容:

  • 在使用無參構造器初始化時,首次新增元素時會直接擴容到 10 的容量;
  • 在其他情況,會直接擴容到舊容量的 1.5 倍,而不是擴容到最小容量要求。

不管是擴容到 10 還是擴容到 1.5 倍,都是為了防止頻繁擴容,避免每次 add 新增資料都要擴容一次。

現在,我們可以回到一些小朋友的疑問:

  • 疑問 4:為什麼 ArrayList 的最大容量是 Integer.MAX_VALUELong.MAX_VALUE 不行嗎?

本質上看,應該說是陣列長度的限制,而不是 ArrayList 長度的限制。在 《物件的記憶體分為哪幾個部分?》 這篇文章裡,我們討論過物件的記憶體佈局。陣列物件的長度是記錄在物件頭中的 “陣列長度” 欄位中,這個欄位是 4 位元組,正好就是 Integer 也是 4 個位元組,所以限制為 Integer.MAX_VALUE,而不能使用 Long.MAX_VALUE

不對啊,Java Integer 是有符號整數,所以 Integer.MAX_VALUE 只有 31 位有效位,還少了 1 位呢。沒錯,是少了一位。如果要榨乾這 1 位容量,當然可以用 long 型別並且限制到 32 位能夠表示的最大正整數上,並且在原始碼中到處加上陣列越界判斷,想想就不穩定的。相比之下,限制陣列長度為 int 型別且最大長度為 Integer.MAX_VALUE,如果有超過 Integer.MAX_VALUE 儲存容量的需求,那就建立兩個陣列呀:)你覺得哪種更好。

Java 物件記憶體佈局

  • 疑問 5:為什麼 ArrayList 的最大容量是 MAX_VALUE - 8,一定會減 8 嗎?

依然與物件的記憶體佈局有關。在 Java 虛擬機器垃圾回收演算法中,需要計算物件的記憶體大小,計算結果是儲存在 jint 型別變數(Java int 型別在 JNI 中的對映)中的。如果陣列的長度是 MAX_VALUE,那麼加上物件頭之後就整型溢位了,所以 ArrayList 會預先減掉物件頭可能佔用的 8 個位元組。物件頭的具體大小取決於虛擬機器實現,減 8 是相對保守的。

其實,ArrayList 的最大容量也不一定會減 8,如果最小容量要求是超過 MAX_ARRAY_SIZE 的,那麼還是會擴容到 MAX_VALUE 。這有點擺爛的意思,會不會溢位執行時再說。

陣列長度溢位

java OutOfMemoryError: Requested array size exceeds VM limit

  • 疑問 8:不應該是 elementData.length - minCapacity > 0 嗎? 這是考慮到整型溢位的情況,minCapacity 溢位就變成負數了。

```java // 在陣列末尾新增元素 public boolean add(E e) { // 先確保底層陣列容量足夠容納 size + 1,不足會擴容 ensureCapacityInternal(size + 1); // Increments modCount!! // 在 size + 1 的位置賦值 elementData[size++] = e; return true; }

// 在陣列中間插入元素 public void add(int index, E element) { // 範圍檢查 rangeCheckForAdd(index); // 先確保容量足夠容納 size + 1,不足會擴容 ensureCapacityInternal(size + 1); // Increments modCount!! // 先搬運資料騰出空位 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 在 index 的位置賦值 elementData[index] = element; // 長度加一 size++; }

// 在陣列末尾新增集合 public boolean addAll(Collection<? extends E> c) { // 集合轉陣列 Object[] a = c.toArray(); // 先確保底層陣列容量足夠容納 size + numNew,不足會擴容 int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount // 搬運原資料 System.arraycopy(a, 0, elementData, size, numNew); // 長度加 numNew size += numNew; return numNew != 0; }

// 在陣列中間插入集合 public boolean addAll(int index, Collection<? extends E> c) { // 略,原理類似 }

// 嘗試擴容 // (提示:原始碼呼叫了 calculateCapacity() 函式,這裡做內聯簡化) private void ensureCapacityInternal(int minCapacity) { // 使用無參構造器初始化時,指定擴容為 10 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }

private void ensureExplicitCapacity(int minCapacity) { modCount++; // 疑問 8:不應該是 elementData.length - minCapacity > 0 嗎? // 如果底層陣列長度不夠 minCapacity 最小容量要求,則需要擴容 if (minCapacity - elementData.length > 0) grow(minCapacity); }

private void grow(int minCapacity) { // 舊容量 int oldCapacity = elementData.length; // 新容量 = 舊容量 * 1.5 倍(有可能整型溢位) int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果新容量小於最小容量要求,則使用最小容量(addAll 大集合的情況) if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } // (提示:上一個 if 的 newCapacity 有可能是溢位的) // 如果新容量超出最大陣列長度限制,說明無法擴容 1.5 倍,迴歸到 minCapacity 上 // (提示:原始碼呼叫了 hugeCapacity() 函式,這裡做內聯簡化) if (newCapacity - MAX_ARRAY_SIZE > 0) { // 最小容量要求發生整型溢位,無法滿足要求,只能直接丟擲 OOM if (minCapacity < 0) throw new OutOfMemoryError(); // 如果最小容量要求超出最大陣列長度限制,則擴容到 MAX_VALUE(說明不一定會減 8) // 否則,擴容到最大陣列長度限制(MAX_VALUE - 8) newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } // 擴容到 newCapacity 長度 elementData = Arrays.copyOf(elementData, newCapacity); }

private static int hugeCapacity(int minCapacity) { // 已經內聯簡化到 grow 方法中 } ```

除了擴容之外,ArrayList 還支援縮容,將底層陣列的容量縮小到實際元素的數量:

java // 縮容 public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }

另外,因為擴容涉及到資料搬運操作,所以如果能事先知道資料的容量,最好在建立 ArrayList 時就顯式指定資料量大小。

2.4 ArrayList 的迭代器

Java 的 foreach 是語法糖,本質上也是採用 iterator 的方式。

在迭代器遍歷陣列的過程中,有可能出現多個執行緒併發修改陣列的情況,造成資料不一致甚至陣列越界,所以 Java 很多容器類的迭代器中都有 fail-fast 機制。

如果在迭代的過程中發現 expectedModCount 變化,說明資料被修改,此時就會提前丟擲 ConcurrentModificationException 異常(當然也不一定是被其他執行緒修改)。

```java private class Itr implements Iterator { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such // 建立迭代器是會記錄外部類的 modCount int expectedModCount = modCount; ...

Itr() {}

public boolean hasNext() {
    return cursor != size;
}

@SuppressWarnings("unchecked")
public E next() {
    // 檢查
    checkForComodification();
    ...
}

public void remove() {
    ...
    // 更新
    expectedModCount = modCount;
}

} ```

  • 疑問 1:為什麼 elementData 欄位不宣告 private 關鍵字?

在註釋中的解釋是:“non-private to simplify nested class access”。但我們知道在 Java 中,內部類是可以訪問外部類的 private 變數的,所以這就說不通的。我的理解是:因為內部類在編譯後會生成獨立的 Class 檔案,如果外部類的 elementData 欄位是 private 型別,那麼編譯器就需要在 ArrayList 中插入 getter / setter。

2.5 ArrayList 的序列化過程

  • 疑問 2:為什麼 elementData 欄位宣告 transient 關鍵字?

ArrayList 重寫了 JDK 序列化的邏輯,只把 elementData 陣列中有效元素的部分序列化,而不會序列化整個陣列。

```java // 序列化和反序列化只考慮有效元素 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject();

// 寫入陣列長度
s.writeInt(size);

// 寫入有效元素
for (int i=0; i<size; i++) {
    s.writeObject(elementData[i]);
}

if (modCount != expectedModCount) {
    throw new ConcurrentModificationException();
}

} ```

2.6 為什麼阿里巴巴要求謹慎使用 subList API?

在 《阿里巴巴 Java 開發手冊》中,有關於 ArrayList#subList API 的規定。為什麼阿里巴巴要做這樣的限制呢?

  • 【強制】ArrayList 的 subList 結果不可強轉成 ArrayList,否則會丟擲 ClassCastException 異常;
  • 【強制】在 subList 場景中,高度注意對原集合元素的增加或刪除,均會導致子列表的遍歷、增加、刪除產生 ConcurrentModificationException 異常。

這是因為 subList API 只是提供通過起始索引 fromIndex 和終止索引 toIndex 包裝了一個原 ArrayList 的 “檢視視窗” ,並不是真的擷取並建立了一個新的 ArrayList,所以強制型別轉換就會丟擲 ClassCastException 異常。

此時,在 ArrayList 或 SubList 上做修改,要注意相互之間的影響:

  • 在 ArrayList 或 SubList 上修改元素,都會同步更新到對方(因為底層都是 ArrayList 本身);
  • 在 SubList 上增加或刪除元素,會影響到 ArrayList;
  • 在 ArrayList 上增加或刪除元素,會導致 SubList 丟擲 ConcurrentModificationException 異常。

ArrayList.java

```java public List subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); }

private class SubList extends AbstractList implements RandomAccess { // 原 ArrayList private final AbstractList parent; private final int parentOffset; private final int offset; int size;

SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
    this.parent = parent;
    this.parentOffset = fromIndex;
    this.offset = offset + fromIndex;
    this.size = toIndex - fromIndex;
    // modCount 記錄
    this.modCount = ArrayList.this.modCount;
}

public E set(int index, E e) {
    rangeCheck(index);
    // 在 ArrayList 上增加或刪除元素,會導致 SubList 丟擲 ConcurrentModificationException 異常
    checkForComodification();
    // 在 SubList 上增加或刪除元素,會影響到 ArrayList;
    E oldValue = ArrayList.this.elementData(offset + index);
    ArrayList.this.elementData[offset + index] = e;
    return oldValue;
}

} ```

2.7 ArrayList 如何實現執行緒安全?

有 3 種方式:

  • 方法 1 - 使用 Vector 容器: Vector 是執行緒安全版本的陣列容器,它會在所有方法上增加 synchronized 關鍵字;
  • 方法 2 - 使用 Collections.synchronizedList 包裝類: 原理也是在所有方法上增加 synchronized 關鍵字;
  • 方法 3 - 使用 CopyOnWriteArrayList 容器: 等到發生修改時才分配資源,避免複製大量資源帶來的瞬時延時,原理與作業系統的 fork 或檔案系統的 cow 相同。CopyOnWriteArrayList 我們後面會討論,請關注專欄文章。

3. Arrays#ArrayList:世界上的另一個我

事實上,在 Java 環境中有兩個 ArrayList,這或許是一個隱藏的彩蛋(坑):

  • ArrayList: 一般認為的 ArrayList,是一個頂級類;
  • Arrays#ArrayList: Arrays 的靜態內部類,和上面這個 ArrayList 沒有任何關係。

其實,Arrays#ArrayList 的定位就是在陣列和和 List 直接切換而已。Arrays 提供了陣列轉 List 的 API,而 Arrays#ArrayList 也提供了 List 轉陣列的 API(這些 API 第一個 ArrayList 中也都有…)

回過頭看剩下的 2 個問題:

  • 疑問 3:為什麼 elementData 欄位不宣告為泛型型別 E

泛型擦除後等於 Object[] elementData,沒有區別。

  • 疑問 7:在帶集合的構造方法中,為什麼會存在集合轉化後的陣列型別不是 Object[].class 的情況?

這是因為有些 List 集合的底層陣列不是 Object[] 型別,有可能是 String[] 型別。而在 ArrayList#toArray() 方法中,返回值的型別是 Object[] 型別,有型別錯誤風險。

例如:在這段程式碼中,ArrayList 接收一個由 String 陣列轉化的 List,最後在 ArrayList#toArray() 返回的 Object 陣列中新增一個 Object 物件,就出現異常了:

示例程式碼

```java // 假設沒有特殊處理 List list = new ArrayList<>(Arrays.asList("list")); // class java.util.ArrayList System.out.println(list.getClass());

Object[] listArray = list.toArray(); // 如果過沒有特殊處理,實際型別是 [Ljava.lang System.out.println(listArray.getClass()); // 如果過沒有特殊處理,將丟擲 ArrayStoreException 異常 listArray[0] = new Object(); ```

原始碼摘要:

Arrays.java

```java public static List asList(T... a) { return new ArrayList<>(a); }

private static class ArrayList extends AbstractList implements RandomAccess, java.io.Serializable { // 泛型擦除後:Object[] a; private final E[] a;

// 泛型擦除後:Object[] array;
// Java 陣列是協變的,能夠接收 String[] 型別的陣列
ArrayList(E[] array) {
    // 賦值
    a = Objects.requireNonNull(array);
}

// 實際返回的陣列可能是 Object[] 型別,也可能是 String[] 型別
@Override
public Object[] toArray() {
    return a.clone();
}

} ```

ArrayList.java

```java public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable transient Object[] elementData;

// 帶集合的構造方法
public ArrayList(Collection<? extends E> c) {
    // 將集合轉為陣列
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 疑問 7:這一個條件語句好奇怪,toArray() 的返回值型別就是 Object[] 啊?
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

} ```


4. ArrayList 這麼好用,可以完全替代陣列嗎?

大多數場景可以,但不能完全替代。

ArrayList 是基於 Object 陣列封裝的動態陣列,我們不需要關心底層陣列的資料搬運和擴容等邏輯,因此在大多數業務開發場景中,除非是為了最求極致的效能,否則直接使用 ArrayList 代替陣列是更好的選擇。

那麼,ArrayList 有哪些地方上比陣列差呢?

  • 舉例 1 - ArrayList 等容器類不支援 int 等基本資料型別,所以必然存在裝箱拆箱操作;
  • 舉例 2 - ArrayList 預設的擴容邏輯是會擴大到原容量的 1.5 倍,在大資料量的場景中,這樣的擴容邏輯是否多餘,需要打上問題;
  • 舉例 3 - ArrayList 的靈活性不夠。ArrayList 不允許底層資料有空洞,所有的有效資料都會 “壓縮” 到底層陣列的首部。因此,當需要基於陣列二次開發容器時,ArrayList 並不是一個好選擇。
    • 例如,使用 ArrayList 開發棧的結構或許合適,可以在陣列的尾部操作資料。但使用 ArrayList 開發佇列就不合適,因為在陣列的首部入隊或出隊需要搬運資料。
    • 而陣列沒有這些約束,我們可以將陣列設計為 “環形陣列”,就可以避免入隊和出隊時搬運資料。例如 Java 的 ArrayBlockingQueueArrayDeque 就是基於陣列的佇列。

5. 總結

  • 1、ArrayList 是基於陣列封裝的動態陣列,封裝了運算元組時的搬運和擴容等邏輯;

  • 2、在構造 ArrayList 時,除了指定大於 0 的初始容量外,ArrayList 在構造時不會建立陣列,而是指向全域性空陣列,這是懶初始化的策略;

  • 3、在新增資料時會先檢查資料容量,不足會先擴容。首次新增預設會擴容到 10 容量,後續會擴容到舊容量的 1.5 倍,這是為了避免反覆擴容;

  • 4、因為擴容涉及到資料搬運操作,所以如果能事先知道資料的容量,最好在建立 ArrayList 時就顯式指定資料量大小;

  • 5、ArrayList 重寫了序列化過程,只處理陣列中有效的元素;

  • 6、ArrayList 的 subList API 只是提供檢視視窗,並不是建立新列表;

  • 7、ArrayList 在大多數場景中可以代替陣列,但在高效能和二次封裝的場景中,ArrayList 無法替代陣列。

在下一篇文章裡,我們來討論 ArrayList 的孿生兄弟 —— LinkedList。請關注。


本文為稀土掘金技術社群首發簽約文章,14天內禁止轉載,14天后未獲授權禁止轉載,侵權必究!

參考資料