ArrayList 源碼詳細分析

1.概述

ArrayList

是一種變長的集合類，基于定長數組實作。ArrayList 允許空值和重複元素，當往 ArrayList 中添加的元素數量大于其底層數組容量時，其會通過擴容機制重新生成一個更大的數組。另外，由于 ArrayList 底層基于數組實作，是以其可以保證在

O(1)

複雜度下完成随機查找操作。其他方面，ArrayList 是非線程安全類，并發環境下，多個線程同時操作 ArrayList，會引發不可預知的錯誤。

ArrayList 是大家最為常用的集合類，作為一個變長集合類，其核心是擴容機制。是以隻要知道它是怎麼擴容的，以及基本的操作是怎樣實作就夠了。本文後續内容也将圍繞這些點展開叙述。

2.源碼分析

2.1 構造方法

ArrayList 有兩個構造方法，一個是無參，另一個需傳入初始容量值。大家平時最常用的是無參構造方法，相關代碼如下：

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;
    
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}           

上面的代碼比較簡單，兩個構造方法做的事情并不複雜，目的都是初始化底層數組 elementData。差別在于無參構造方法會将 elementData 初始化一個空數組，插入元素時，擴容将會按預設值重新初始化數組。而有參的構造方法則會将 elementData 初始化為參數值大小（>= 0）的數組。一般情況下，我們用預設的構造方法即可。倘若在可知道将會向 ArrayList 插入多少元素的情況下，應該使用有參構造方法。按需配置設定，避免浪費。

2.2 插入

對于數組（線性表）結構，插入操作分為兩種情況。一種是在元素序列尾部插入，另一種是在元素序列其他位置插入。ArrayList 的源碼裡也展現了這兩種插入情況，如下：

/** 在元素序列尾部插入 */
public boolean add(E e) {
    // 1. 檢測是否需要擴容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将新元素插入序列尾部
    elementData[size++] = e;
    return true;
}

/** 在元素序列 index 位置處插入 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // 1. 檢測是否需要擴容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将 index 及其之後的所有元素都向後移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 3. 将新元素插入至 index 處
    elementData[index] = element;
    size++;
}           

對于在元素序列尾部插入，這種情況比較簡單，隻需兩個步驟即可：

1. 檢測數組是否有足夠的空間插入
2. 将新元素插入至序列尾部

如下圖：

如果是在元素序列指定位置（假設該位置合理）插入，則情況稍微複雜一點，需要三個步驟：

1. 檢測數組是否有足夠的空間
2. 将 index 及其之後的所有元素向後移一位
3. 将新元素插入至 index 處

從上圖可以看出，将新元素插入至序列指定位置，需要先将該位置及其之後的元素都向後移動一位，為新元素騰出位置。這個操作的時間複雜度為

O(N)

，頻繁移動元素可能會導緻效率問題，特别是集合中元素數量較多時。在日常開發中，若非所需，我們應當盡量避免在大集合中調用第二個插入方法。

以上是 ArrayList 插入相關的分析，上面的分析以及配圖均未展現擴容機制。那麼下面就來簡單分析一下 ArrayList 的擴容機制。對于變長資料結構，當結構中沒有空餘空間可供使用時，就需要進行擴容。在 ArrayList 中，當空間用完，其會按照原數組空間的1.5倍進行擴容。相關源碼如下：

/** 計算最小容量 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/** 擴容的入口方法 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/** 擴容的核心方法 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 擴容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果最小容量超過 MAX_ARRAY_SIZE，則将數組容量擴容至 Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}           

上面就是擴容的邏輯，代碼雖多，但很多都是邊界檢查，這裡就不詳細分析了。

2.3 删除

不同于插入操作，ArrayList 沒有無參删除方法。是以其隻能删除指定位置的元素或删除指定元素，這樣就無法避免移動元素（除非從元素序列的尾部删除）。相關代碼如下：

/** 删除指定位置的元素 */
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    // 傳回被删除的元素值
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将 index + 1 及之後的元素向前移動一位，覆寫被删除值
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将最後一個元素置空，并将 size 值減1                
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

E elementData(int index) {
    return (E) elementData[index];
}

/** 删除指定元素，若元素重複，則隻删除下标最小的元素 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        // 周遊數組，查找要删除元素的位置
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/** 快速删除，不做邊界檢查，也不傳回删除的元素值 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}           

上面的删除方法并不複雜，這裡以第一個删除方法為例，删除一個元素步驟如下：

1. 擷取指定位置 index 處的元素值
2. 将 index + 1 及之後的元素向前移動一位
3. 将最後一個元素置空，并将 size 值減 1
4. 傳回被删除值，完成删除操作

上面就是删除指定位置元素的分析，并不是很複雜。

現在，考慮這樣一種情況。我們往 ArrayList 插入大量元素後，又删除很多元素，此時底層數組會空閑處大量的空間。因為 ArrayList 沒有自動縮容機制，導緻底層數組大量的空閑空間不能被釋放，造成浪費。對于這種情況，ArrayList 也提供了相應的處理方法，如下：

/** 将數組容量縮小至元素數量 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}           

通過上面的方法，我們可以手動觸發 ArrayList 的縮容機制。這樣就可以釋放多餘的空間，提高空間使用率。

2.4 周遊

ArrayList 實作了 RandomAccess 接口（該接口是個标志性接口），表明它具有随機通路的能力。ArrayList 底層基于數組實作，是以它可在常數階的時間内完成随機通路，效率很高。對 ArrayList 進行周遊時，一般情況下，我們喜歡使用 foreach 循環周遊，但這并不是推薦的周遊方式。ArrayList 具有随機通路的能力，如果在一些效率要求比較高的場景下，更推薦下面這種方式：

for (int i = 0; i < list.size(); i++) {
    list.get(i);
}           

至于原因也不難了解，foreach 最終會被轉換成疊代器周遊的形式，效率不如上面的周遊方式。

3.其他細節

3.1 快速失敗機制

在 Java 集合架構中，很多類都實作了快速失敗機制。該機制被觸發時，會抛出并發修改異常

ConcurrentModificationException

，這個異常大家在平時開發中多多少少應該都碰到過。關于快速失敗機制，ArrayList 的注釋裡對此做了解釋，這裡引用一下：

The iterators returned by this class's iterator() and

listIterator(int) methods are fail-fast

if the list is structurally modified at any time after the iterator is

created, in any way except through the iterator's own

ListIterator remove() or ListIterator add(Object) methods,

the iterator will throw a ConcurrentModificationException. Thus, in the face of

concurrent modification, the iterator fails quickly and cleanly, rather

than risking arbitrary, non-deterministic behavior at an undetermined

time in the future.

上面注釋大緻意思是，ArrayList 疊代器中的方法都是均具有快速失敗的特性，當遇到并發修改的情況時，疊代器會快速失敗，以避免程式在将來不确定的時間裡出現不确定的行為。

以上就是 Java 集合架構中引入快速失敗機制的原因，并不難了解，這裡不多說了。

3.2 關于周遊時删除

周遊時删除是一個不正确的操作，即使有時候代碼不出現異常，但執行邏輯也會出現問題。關于這個問題，阿裡巴巴 Java 開發手冊裡也有所提及。這裡引用一下：

【強制】不要在 foreach 循環裡進行元素的 remove/add 操作。remove 元素請使用 Iterator 方式，如果并發操作，需要對 Iterator 對象加鎖。

相關代碼（稍作修改）如下：

List<String> a = new ArrayList<String>();
    a.add("1");
    a.add("2");
    for (String temp : a) {
        System.out.println(temp);
        if("1".equals(temp)){
            a.remove(temp);
        }
    }
}           

相信有些朋友應該看過這個，并且也執行過上面的程式。上面的程式執行起來不會雖不會出現異常，但代碼執行邏輯上卻有問題，隻不過這個問題隐藏的比較深。我們把 temp 變量列印出來，會發現隻列印了數字

1

，

2

沒列印出來。初看這個執行結果确實很讓人詫異，不明原因。如果死摳上面的代碼，我們很難找出原因，此時需要稍微轉換一下思路。我們都知道 Java 中的 foreach 是個文法糖，編譯成位元組碼後會被轉成用疊代器周遊的方式。是以我們可以把上面的代碼轉換一下，等價于下面形式：

List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
    String temp = it.next();
    System.out.println("temp: " + temp);
    if("1".equals(temp)){
        a.remove(temp);
    }
}           

這個時候，我們再去分析一下 ArrayList 的疊代器源碼就能找出原因。

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
    int expectedModCount = modCount;

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

    @SuppressWarnings("unchecked")
    public E next() {
        // 并發修改檢測，檢測不通過則抛出異常
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    
    // 省略不相關的代碼
}           

我們一步一步執行一下上面的代碼，第一次進入 while 循環時，一切正常，元素 1 也被删除了。但删除元素 1 後，就無法再進入 while 循環，此時 it.hasNext() 為 false。原因是删除元素 1 後，元素計數器 size = 1，而疊代器中的 cursor 也等于 1，進而導緻 it.hasNext() 傳回false。歸根結底，上面的代碼段沒抛異常的原因是，循環提前結束，導緻 next 方法沒有機會抛異常。不信的話，大家可以把代碼稍微修改一下，即可發現問題：

List<String> a = new ArrayList<>();
a.add("1");
a.add("2");
a.add("3");
Iterator<String> it = a.iterator();
while (it.hasNext()) {
    String temp = it.next();
    System.out.println("temp: " + temp);
    if("1".equals(temp)){
        a.remove(temp);
    }
}           

以上是關于周遊時删除的分析，在日常開發中，我們要避免上面的做法。正确的做法使用疊代器提供的删除方法，而不是直接删除。

4.總結

看到這裡，大家對 ArrayList 應該又有了些新的認識。ArrayList 是一個比較基礎的集合類，用的很多。它的結構簡單（本質上就是一個變長的數組），實作上也不複雜。盡管如此，本文還是啰裡啰嗦講了很多，大家見諒。好了，本文到這裡就結束了，感謝閱讀。

本文在知識共享許可協定 4.0 下釋出，轉載需在明顯位置處注明出處

作者：coolblog

本文同步釋出在我的個人部落格：

http://www.coolblog.xyz

本作品采用

知識共享署名-非商業性使用-禁止演繹 4.0 國際許可協定

進行許可。