ArrayList 可以完全替代數組嗎？

本文已收錄到  GitHub · AndroidFamily，有 Android 進階知識體系，歡迎 Star。技術和職場問題，請關注公眾號 [彭旭銳] 加入 Android 交流群。

前言

大家好，我是小彭。

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

在後續的文章里，我們將以 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) 時間複雜度（如果考慮查詢被刪除節點的時間，複雜度分析上依然是 O(n)，在工程分析上還是比數組快）；

    • 額外記憶體消耗上： ArrayList 在數組的尾部增加了閑置位置，而 LinkedList 在節點上增加了前驅和後繼指針。

2. ArrayList 源碼分析

這一節，我們來分析 ArrayList 中主要流程的源碼。

2.1 ArrayList 的屬性

ArrayList 的屬性很好理解，底層是一個 Object 數組，我要舉手提問：

  • 🙋🏻‍♀️疑問 1： 為什麼 elementData 欄位不聲明 private 關鍵字？
  • 🙋🏻‍♀️疑問 2： 為什麼 elementData 欄位聲明 transient 關鍵字？
  • 🙋🏻‍♀️疑問 3： 為什麼elementData 欄位不聲明為泛型類型 E？
  • 🙋🏻‍♀️疑問 4： 為什麼 ArrayList 的最大容量是 Integer.MAX_VALUE，Long.MAX_VALUE 不行嗎？
  • 🙋🏻‍♀️疑問 5： 為什麼 ArrayList 的最大容量是 MAX_VALUE - 8，一定會減 8 嗎？

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

public class ArrayList<E> extends AbstractList<E> implements List<E>, 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 的情況？
// 帶初始容量的構造方法
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 可以在數組末尾或數組中間添加元素：

  • 如果是在數組末尾添加，均攤時間只需要 O(1) 時間複雜度；
  • 如果在數組中間添加，由於需要搬運數據，所以需要 O(n) 時間複雜度。

添加前會先檢查數據容量，不足會先擴容：

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

不管是擴容到 10 還是擴容到 1.5 倍，都是為了防止頻繁擴容，避免每次 add 添加數據都要擴容一次。

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

  • 🙋🏻‍♀️疑問 4：為什麼 ArrayList 的最大容量是 Integer.MAX_VALUE，Long.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 。這有點擺爛的意思，會不會溢出運行時再說。

數組長度溢出

OutOfMemoryError: Requested array size exceeds VM limit
  • 🙋🏻‍♀️疑問 8：不應該是 elementData.length – minCapacity > 0 嗎？ 這是考慮到整型溢出的情況，minCapacity 溢出就變成負數了。
// 在數組末尾添加元素
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 還支援縮容，將底層數組的容量縮小到實際元素的數量：

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

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

2.4 ArrayList 的迭代器

Java 的 foreach 是語法糖，本質上也是採用 iterator 的方式。ArrayList 提供了 2 個迭代器：

  • iterator():Iterator()： 單向迭代器
  • ListIterator listIterator()： 雙向迭代器

在迭代器遍曆數組的過程中，有可能出現多個執行緒並發修改數組的情況，造成數據不一致甚至數組越界，所以 Java 很多容器類的迭代器中都有 fail-fast 機制。

如果在迭代的過程中發現 expectedModCount 變化，說明數據被修改，此時就會提前拋出 ConcurrentModificationException 異常（當然也不一定是被其他執行緒修改）。

private class Itr implements Iterator<E> {
    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，並通過方法調用，而 non-private 欄位就可以直接訪問欄位。

2.5 ArrayList 的序列化過程

  • 🙋🏻‍♀️疑問 2：為什麼 elementData 欄位聲明 transient 關鍵字？

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

// 序列化和反序列化只考慮有效元素
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 ArrayList 的 clone() 過程

ArrayList 中的 elementData 數組是引用類型，因此在 clone() 中需要實現深拷貝，否則原對象與克隆對象會相互影響：

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 拷貝數組對象
        v.elementData = Arrays.copyOf(elementData, size);
        // 修改計數歸零
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

2.7 為什麼阿里巴巴要求謹慎使用 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

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

private class SubList extends AbstractList<E> implements RandomAccess {
    // 原 ArrayList
    private final AbstractList<E> 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.8 ArrayList 如何實現執行緒安全？

有 4 種方式：

  • 方法 1 – 使用 Vector 容器： Vector 是執行緒安全版本的數組容器，它會在所有方法上增加 synchronized 關鍵字；
  • 方法 2 – 使用 Collections.synchronizedList 包裝類： 原理也是在所有方法上增加 synchronized 關鍵字；
  • 方法 3 – 使用 CopyOnWriteArrayList 容器： 基於加鎖的 「讀寫分離」 和 「寫時複製」 實現的動態數組，適合於讀多寫少，數據量不大的場景。
  • 方法 4 – 使用 ArrayBlockingQueue 容器： 基於加鎖的阻塞隊列，適合於帶阻塞操作的生產者消費者模型。

提示： 關於 CopyOnWriteArrayList 的更多內容，去看看專欄文章 《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 對象，就出現異常了：

示例程式碼

// 假設沒有特殊處理
List<String> 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

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

private static class ArrayList<E> extends AbstractList<E> 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

public class ArrayList<E> extends AbstractList<E> implements List<E>, 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 的 ArrayBlockingQueue 和 ArrayDeque 就是基於數組的隊列。

5. 總結

  • 1、ArrayList 是基於數組封裝的動態數組，封裝了操作數組時的搬運和擴容等邏輯；

  • 2、在構造 ArrayList 時，除了指定大於 0 的初始容量外，ArrayList 在構造時不會創建數組，而是指向全局空數組，這是懶初始化的策略；

  • 3、在添加數據時會先檢查數據容量，不足會先擴容。首次添加默認會擴容到 10 容量，後續會擴容到舊容量的 1.5 倍，這是為了避免反覆擴容；

  • 4、因為擴容涉及到數據搬運操作，所以如果能事先知道數據的容量，最好在創建 ArrayList 時就顯式指定數據量大小；

  • 5、ArrayList 重寫了序列化過程，只處理數組中有效的元素；

  • 6、ArrayList 的 subList API 只是提供視圖窗口，並不是創建新列表；

  • 7、ArrayList 在大多數場景中可以代替數組，但在高性能和二次封裝的場景中，ArrayList 無法替代數組。

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

參考資料

Tags:

VirMach 便宜 VPS

QNews

QNews