摘要：源碼分析構造方法有兩個構造方法，一個是無參，另一個需傳入初始容量值。所以我們可以把上面的代碼轉(zhuǎn)換一下，等價于下面形式這個時候，我們再去分析一下的迭代器源碼就能找出原因。原因是刪除元素后，元素計數(shù)器，而迭代器中的也等于，從而導致返回。

ArrayList 是一種變長的集合類，基于定長數(shù)組實現(xiàn)。ArrayList 允許空值和重復元素，當往 ArrayList 中添加的元素數(shù)量大于其底層數(shù)組容量時，其會通過擴容機制重新生成一個更大的數(shù)組。另外，由于 ArrayList 底層基于數(shù)組實現(xiàn)，所以其可以保證在 O(1) 復雜度下完成隨機查找操作。其他方面，ArrayList 是非線程安全類，并發(fā)環(huán)境下，多個線程同時操作 ArrayList，會引發(fā)不可預知的錯誤。

ArrayList 是大家最為常用的集合類，作為一個變長集合類，其核心是擴容機制。所以只要知道它是怎么擴容的，以及基本的操作是怎樣實現(xiàn)就夠了。本文后續(xù)內(nèi)容也將圍繞這些點展開敘述。

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;
}

上面的代碼比較簡單，兩個構造方法做的事情并不復雜，目的都是初始化底層數(shù)組 elementData。區(qū)別在于無參構造方法會將 elementData 初始化一個空數(shù)組，插入元素時，擴容將會按默認值重新初始化數(shù)組。而有參的構造方法則會將 elementData 初始化為參數(shù)值大?。?= 0）的數(shù)組。一般情況下，我們用默認的構造方法即可。倘若在可知道將會向 ArrayList 插入多少元素的情況下，應該使用有參構造方法。按需分配，避免浪費。

對于數(shù)組（線性表）結(jié)構，插入操作分為兩種情況。一種是在元素序列尾部插入，另一種是在元素序列其他位置插入。ArrayList 的源碼里也體現(xiàn)了這兩種插入情況，如下：

/** 在元素序列尾部插入 */
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++;
}

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

檢測數(shù)組是否有足夠的空間插入

將新元素插入至序列尾部

如下圖：

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

檢測數(shù)組是否有足夠的空間

將 index 及其之后的所有元素向后移一位

將新元素插入至 index 處

如下圖：

從上圖可以看出，將新元素插入至序列指定位置，需要先將該位置及其之后的元素都向后移動一位，為新元素騰出位置。這個操作的時間復雜度為O(N)，頻繁移動元素可能會導致效率問題，特別是集合中元素數(shù)量較多時。在日常開發(fā)中，若非所需，我們應當盡量避免在大集合中調(diào)用第二個插入方法。

以上是 ArrayList 插入相關的分析，上面的分析以及配圖均未體現(xiàn)擴容機制。那么下面就來簡單分析一下 ArrayList 的擴容機制。對于變長數(shù)據(jù)結(jié)構，當結(jié)構中沒有空余空間可供使用時，就需要進行擴容。在 ArrayList 中，當空間用完，其會按照原數(shù)組空間的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，則將數(shù)組容量擴容至 Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

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

不同于插入操作，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 {
        // 遍歷數(shù)組，查找要刪除元素的位置
        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
}

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

獲取指定位置 index 處的元素值

將 index + 1 及之后的元素向前移動一位

將最后一個元素置空，并將 size 值減 1

返回被刪除值，完成刪除操作

如下圖：

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

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

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

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

ArrayList 實現(xiàn)了 RandomAccess 接口（該接口是個標志性接口），表明它具有隨機訪問的能力。ArrayList 底層基于數(shù)組實現(xiàn)，所以它可在常數(shù)階的時間內(nèi)完成隨機訪問，效率很高。對 ArrayList 進行遍歷時，一般情況下，我們喜歡使用 foreach 循環(huán)遍歷，但這并不是推薦的遍歷方式。ArrayList 具有隨機訪問的能力，如果在一些效率要求比較高的場景下，更推薦下面這種方式：

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

至于原因也不難理解，foreach 最終會被轉(zhuǎn)換成迭代器遍歷的形式，效率不如上面的遍歷方式。

在 Java 集合框架中，很多類都實現(xiàn)了快速失敗機制。該機制被觸發(fā)時，會拋出并發(fā)修改異常ConcurrentModificationException，這個異常大家在平時開發(fā)中多多少少應該都碰到過。關于快速失敗機制，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 迭代器中的方法都是均具有快速失敗的特性，當遇到并發(fā)修改的情況時，迭代器會快速失敗，以避免程序在將來不確定的時間里出現(xiàn)不確定的行為。

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

遍歷時刪除是一個不正確的操作，即使有時候代碼不出現(xiàn)異常，但執(zhí)行邏輯也會出現(xiàn)問題。關于這個問題，阿里巴巴 Java 開發(fā)手冊里也有所提及。這里引用一下：

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

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

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

相信有些朋友應該看過這個，并且也執(zhí)行過上面的程序。上面的程序執(zhí)行起來不會雖不會出現(xiàn)異常，但代碼執(zhí)行邏輯上卻有問題，只不過這個問題隱藏的比較深。我們把 temp 變量打印出來，會發(fā)現(xiàn)只打印了數(shù)字1，2沒打印出來。初看這個執(zhí)行結(jié)果確實很讓人詫異，不明原因。如果死摳上面的代碼，我們很難找出原因，此時需要稍微轉(zhuǎn)換一下思路。我們都知道 Java 中的 foreach 是個語法糖，編譯成字節(jié)碼后會被轉(zhuǎn)成用迭代器遍歷的方式。所以我們可以把上面的代碼轉(zhuǎn)換一下，等價于下面形式：

List a = new ArrayList<>();
a.add("1");
a.add("2");
Iterator 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 {
    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() {
        // 并發(fā)修改檢測，檢測不通過則拋出異常
        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();
    }
    
    // 省略不相關的代碼
}

我們一步一步執(zhí)行一下上面的代碼，第一次進入 while 循環(huán)時，一切正常，元素 1 也被刪除了。但刪除元素 1 后，就無法再進入 while 循環(huán)，此時 it.hasNext() 為 false。原因是刪除元素 1 后，元素計數(shù)器 size = 1，而迭代器中的 cursor 也等于 1，從而導致 it.hasNext() 返回false。歸根結(jié)底，上面的代碼段沒拋異常的原因是，循環(huán)提前結(jié)束，導致 next 方法沒有機會拋異常。不信的話，大家可以把代碼稍微修改一下，即可發(fā)現(xiàn)問題：

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

以上是關于遍歷時刪除的分析，在日常開發(fā)中，我們要避免上面的做法。正確的做法使用迭代器提供的刪除方法，而不是直接刪除。

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

本文在知識共享許可協(xié)議 4.0 下發(fā)布，轉(zhuǎn)載需在明顯位置處注明出處
作者：coolblog
本文同步發(fā)布在我的個人博客：http://www.coolblog.xyz

本作品采用知識共享署名-非商業(yè)性使用-禁止演繹 4.0 國際許可協(xié)議進行許可。