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

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

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

ArrayList 有兩個(gè)構(gòu)造方法，一個(gè)是無參，另一個(gè)需傳入初始容量值。大家平時(shí)最常用的是無參構(gòu)造方法，相關(guān)代碼如下：

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

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

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

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

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

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

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

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

將新元素插入至序列尾部

如下圖：

如果是在元素序列指定位置（假設(shè)該位置合理）插入，則情況稍微復(fù)雜一點(diǎn)，需要三個(gè)步驟：

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

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

將新元素插入至 index 處

如下圖：

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

以上是 ArrayList 插入相關(guān)的分析，上面的分析以及配圖均未體現(xiàn)擴(kuò)容機(jī)制。那么下面就來簡單分析一下 ArrayList 的擴(kuò)容機(jī)制。對于變長數(shù)據(jù)結(jié)構(gòu)，當(dāng)結(jié)構(gòu)中沒有空余空間可供使用時(shí)，就需要進(jìn)行擴(kuò)容。在 ArrayList 中，當(dāng)空間用完，其會(huì)按照原數(shù)組空間的1.5倍進(jìn)行擴(kuò)容。相關(guān)源碼如下：

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

/** 擴(kuò)容的入口方法 */
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);
}

/** 擴(kuò)容的核心方法 */
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);
    // 擴(kuò)容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

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

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

不同于插入操作，ArrayList 沒有無參刪除方法。所以其只能刪除指定位置的元素或刪除指定元素，這樣就無法避免移動(dòng)元素（除非從元素序列的尾部刪除）。相關(guān)代碼如下：

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

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

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

    return oldValue;
}

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

/** 刪除指定元素，若元素重復(fù)，則只刪除下標(biāo)最小的元素 */
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ù)組，查找要?jiǎng)h除元素的位置
        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
}

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

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

將 index + 1 及之后的元素向前移動(dòng)一位

將最后一個(gè)元素置空，并將 size 值減 1

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

如下圖：

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

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

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

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

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

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

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

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

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

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

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

相關(guān)代碼（稍作修改）如下：

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

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

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

這個(gè)時(shí)候，我們再去分析一下 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();
    }
    
    // 省略不相關(guān)的代碼
}

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

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

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

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

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