做了這么多準(zhǔn)備，終于到了ArrayList了，ArrayList是我們使用最為頻繁的集合類了，我們先看看文檔是如何介紹它的：

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

可見，ArrayList是Vector的翻版，只是去除了線程安全。Vector因?yàn)榉N種原因不推薦使用了，這里我們就不對(duì)其進(jìn)行分析了。ArrayList是一個(gè)可以動(dòng)態(tài)調(diào)整大小的List實(shí)現(xiàn)，其數(shù)據(jù)的順序與插入順序始終一致，其余特性與List中定義的一致。

ArrayList繼承結(jié)構(gòu)

ArrayList結(jié)構(gòu)圖

可以看到，ArrayList是AbstractList的子類，同時(shí)實(shí)現(xiàn)了List接口。除此之外，它還實(shí)現(xiàn)了三個(gè)標(biāo)識(shí)型接口，這幾個(gè)接口都沒有任何方法，僅作為標(biāo)識(shí)表示實(shí)現(xiàn)類具備某項(xiàng)功能。RandomAccess表示實(shí)現(xiàn)類支持快速隨機(jī)訪問，Cloneable表示實(shí)現(xiàn)類支持克隆，具體表現(xiàn)為重寫了clone方法，java.io.Serializable則表示支持序列化，如果需要對(duì)此過程自定義，可以重寫writeObject與readObject方法。

一般面試問到與ArrayList相關(guān)的問題時(shí)，可能會(huì)問ArrayList的初始大小是多少？很多人在初始化ArrayList時(shí)，可能都是直接調(diào)用無(wú)參構(gòu)造函數(shù)，從未關(guān)注過此問題。例如，這樣獲取一個(gè)對(duì)象：

ArrayList<String> strings = new ArrayList<>();

我們都知道，ArrayList是基于數(shù)組的，而數(shù)組是定長(zhǎng)的。那ArrayList為何不需要指定長(zhǎng)度，就能使我們既可以插入一條數(shù)據(jù)，也可以插入一萬(wàn)條數(shù)據(jù)？回想剛剛文檔的第一句話：

Resizable-array implementation of the List interface.

ArrayList可以動(dòng)態(tài)調(diào)整大小，所以我們才可以無(wú)感知的插入多條數(shù)據(jù)，這也說(shuō)明其必然有一個(gè)默認(rèn)的大小。而要想擴(kuò)充數(shù)組的大小，只能通過復(fù)制。這樣一來(lái)，默認(rèn)大小以及如何動(dòng)態(tài)調(diào)整大小會(huì)對(duì)使用性能產(chǎn)生非常大的影響。我們舉個(gè)例子來(lái)說(shuō)明此情形：

比如默認(rèn)大小為5，我們向ArrayList中插入5條數(shù)據(jù)，并不會(huì)涉及到擴(kuò)容。如果想插入100條數(shù)據(jù)，就需要將ArrayList大小調(diào)整到100再進(jìn)行插入，這就涉及一次數(shù)組的復(fù)制。如果此時(shí)，還想再插入50條數(shù)據(jù)呢？那就得把大小再調(diào)整到150，把原有的100條數(shù)據(jù)復(fù)制過來(lái)，再插入新的50條數(shù)據(jù)。自此之后，我們每向其中插入一條數(shù)據(jù)，都要涉及一次數(shù)據(jù)拷貝，且數(shù)據(jù)量越大，需要拷貝的數(shù)據(jù)越多，性能也會(huì)迅速下降。

其實(shí)，ArrayList僅僅是對(duì)數(shù)組操作的封裝，里面采取了一定的措施來(lái)避免以上的問題，如果我們不利用這些措施，就和直接使用數(shù)組沒有太大的區(qū)別。那我們就看看ArrayList用了哪些措施，并且如何使用它們吧。我們先從初始化說(shuō)起。

構(gòu)造方法與初始化

ArrayList一共有三個(gè)構(gòu)造方法，用到了兩個(gè)成員變量。

//這是一個(gè)用來(lái)標(biāo)記存儲(chǔ)容量的數(shù)組，也是存放實(shí)際數(shù)據(jù)的數(shù)組。
//當(dāng)ArrayList擴(kuò)容時(shí)，其capacity就是這個(gè)數(shù)組應(yīng)有的長(zhǎng)度。
//默認(rèn)時(shí)為空，添加進(jìn)第一個(gè)元素后，就會(huì)直接擴(kuò)展到DEFAULT_CAPACITY，也就是10
//這里和size區(qū)別在于，ArrayList擴(kuò)容并不是需要多少就擴(kuò)展多少的
transient Object[] elementData;

//這里就是實(shí)際存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)了
private int size;

除了以上兩個(gè)成員變量，我們還需要掌握一個(gè)變量，它是

protected transient int modCount = 0;

這個(gè)變量主要作用是防止在進(jìn)行一些操作時(shí)，改變了ArrayList的大小，那將使得結(jié)果不可預(yù)測(cè)。

下面我們看看構(gòu)造函數(shù)：

//默認(rèn)構(gòu)造方法。文檔說(shuō)明其默認(rèn)大小為10，但正如elementData定義所言，
//只有插入一條數(shù)據(jù)后才會(huì)擴(kuò)展為10，而實(shí)際上默認(rèn)是空的
 public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//帶初始大小的構(gòu)造方法，一旦指定了大小，elementData就不再是原來(lái)的機(jī)制了。
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);
    }
}

//從一個(gè)其他的Collection中構(gòu)造一個(gè)具有初始化數(shù)據(jù)的ArrayList。
//這里可以看到size是表示存儲(chǔ)數(shù)據(jù)的數(shù)量
//這也展示了Collection這種抽象的魅力，可以在不同的結(jié)構(gòu)間轉(zhuǎn)換
public ArrayList(Collection<? extends E> c) {
    //轉(zhuǎn)換最主要的是toArray()，這在Collection中就定義了
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

重要方法

ArrayList已經(jīng)是一個(gè)具體的實(shí)現(xiàn)類了，所以在List接口中定義的所有方法在此都做了實(shí)現(xiàn)。其中有些在AbstractList中實(shí)現(xiàn)過的方法，在這里再次被重寫，我們稍后就可以看到它們的區(qū)別。

先看一些簡(jiǎn)單的方法：

//還記得在AbstractList中的實(shí)現(xiàn)嗎？那是基于Iterator完成的。
//在這里完全沒必要先轉(zhuǎn)成Iterator再進(jìn)行操作
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

//和indexOf是相同的道理
 public int lastIndexOf(Object o) {
    //...
}

//一樣的道理，已經(jīng)有了所有元素，不需要再利用Iterator來(lái)獲取元素了
//注意這里返回時(shí)把elementData截?cái)酁閟ize大小
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

//帶類型的轉(zhuǎn)換，看到這里a[size] = null;這個(gè)用處真不大，除非你確定所有元素都不為空，
//才可以通過null來(lái)判斷獲取了多少有用數(shù)據(jù)。
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // 給定的數(shù)據(jù)長(zhǎng)度不夠，復(fù)制出一個(gè)新的并返回
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

數(shù)據(jù)操作最重要的就是增刪改查，改查都不涉及長(zhǎng)度的變化，而增刪就涉及到動(dòng)態(tài)調(diào)整大小的問題，我們先看看改和查是如何實(shí)現(xiàn)的：

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

//只要獲取的數(shù)據(jù)位置在0-size之間即可
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

//改變下對(duì)應(yīng)位置的值
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

增和刪是ArrayList最重要的部分，這部分代碼需要我們細(xì)細(xì)研究，我們看看它是如何處理我們例子中的問題的：

//在最后添加一個(gè)元素
public boolean add(E e) {
    //先確保elementData數(shù)組的長(zhǎng)度足夠
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);

    //先確保elementData數(shù)組的長(zhǎng)度足夠
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //將數(shù)據(jù)向后移動(dòng)一位，空出位置之后再插入
    System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
    elementData[index] = element;
    size++;
}

以上兩種添加數(shù)據(jù)的方式都調(diào)用到了ensureCapacityInternal這個(gè)方法，我們看看它是如何完成工作的：

//在定義elementData時(shí)就提過，插入第一個(gè)數(shù)據(jù)就直接將其擴(kuò)充至10
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    
    //這里把工作又交了出去
    ensureExplicitCapacity(minCapacity);
}

//如果elementData的長(zhǎng)度不能滿足需求，就需要擴(kuò)充了
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;
    //可以看到這里是1.5倍擴(kuò)充的
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    //擴(kuò)充完之后，還是沒滿足，這時(shí)候就直接擴(kuò)充到minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //防止溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

至此，我們徹底明白了ArrayList的擴(kuò)容機(jī)制了。首先創(chuàng)建一個(gè)空數(shù)組elementData，第一次插入數(shù)據(jù)時(shí)直接擴(kuò)充至10，然后如果elementData的長(zhǎng)度不足，就擴(kuò)充1.5倍，如果擴(kuò)充完還不夠，就使用需要的長(zhǎng)度作為elementData的長(zhǎng)度。

這樣的方式顯然比我們例子中好一些，但是在遇到大量數(shù)據(jù)時(shí)還是會(huì)頻繁的拷貝數(shù)據(jù)。那么如何緩解這種問題呢，ArrayList為我們提供了兩種可行的方案：

• 使用ArrayList(int initialCapacity)這個(gè)有參構(gòu)造，在創(chuàng)建時(shí)就聲明一個(gè)較大的大小，這樣解決了頻繁拷貝問題，但是需要我們提前預(yù)知數(shù)據(jù)的數(shù)量級(jí)，也會(huì)一直占有較大的內(nèi)存。

• 除了添加數(shù)據(jù)時(shí)可以自動(dòng)擴(kuò)容外，我們還可以在插入前先進(jìn)行一次擴(kuò)容。只要提前預(yù)知數(shù)據(jù)的數(shù)量級(jí)，就可以在需要時(shí)直接一次擴(kuò)充到位，與ArrayList(int initialCapacity)相比的好處在于不必一直占有較大內(nèi)存，同時(shí)數(shù)據(jù)拷貝的次數(shù)也大大減少了。這個(gè)方法就是ensureCapacity(int minCapacity)，其內(nèi)部就是調(diào)用了ensureCapacityInternal(int minCapacity)。

其他還有一些比較重要的函數(shù)，其實(shí)現(xiàn)的原理也大同小異，這里我們不一一分析了，但還是把它們列舉出來(lái)，以便使用。

//將elementData的大小設(shè)置為和size一樣大，釋放所有無(wú)用內(nèi)存
public void trimToSize() {
    //...
}

//刪除指定位置的元素
public E remove(int index) {
    //...
}

//根據(jù)元素本身刪除
public boolean remove(Object o) {
    //...
}

//在末尾添加一些元素
public boolean addAll(Collection<? extends E> c) {
    //...
}

//從指定位置起，添加一些元素
public boolean addAll(int index, Collection<? extends E> c){
    //...
}

//刪除指定范圍內(nèi)的元素
protected void removeRange(int fromIndex, int toIndex){
    //...
}

//刪除所有包含在c中的元素
public boolean removeAll(Collection<?> c) {
    //...
}

//僅保留所有包含在c中的元素
public boolean retainAll(Collection<?> c) {
    //...
}

ArrayList還對(duì)父級(jí)實(shí)現(xiàn)的ListIterator以及SubList進(jìn)行了優(yōu)化，主要是使用位置訪問元素，我們就不再研究了。

其他實(shí)現(xiàn)方法

ArrayList不僅實(shí)現(xiàn)了List中定義的所有功能，還實(shí)現(xiàn)了equals、hashCode、clone、writeObject與readObject等方法。這些方法都需要與存儲(chǔ)的數(shù)據(jù)配合，否則結(jié)果將是錯(cuò)誤的或者克隆得到的數(shù)據(jù)只是淺拷貝，或者數(shù)據(jù)本身不支持序列化等，這些我們定義數(shù)據(jù)時(shí)注意到即可。我們主要看下其在序列化時(shí)自定義了哪些東西。

//這里就能解開我們的迷惑了，elementData被transient修飾，也就是不會(huì)參與序列化
//這里我們看到數(shù)據(jù)是一個(gè)個(gè)寫入的，并且將size也寫入了進(jìn)去
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

        // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    //modCount的作用在此體現(xiàn)，如果序列化時(shí)進(jìn)行了修改操作，就會(huì)拋出異常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

readObject是一個(gè)相反的過程，就是把數(shù)據(jù)正確的恢復(fù)回來(lái)，并將elementData設(shè)置好即可，感興趣可以自行閱讀源碼。

總結(jié)

總體而言，ArrayList還是和數(shù)組一樣，更適合于數(shù)據(jù)隨機(jī)訪問，而不太適合于大量的插入與刪除，如果一定要進(jìn)行插入操作，要使用以下三種方式：

• 使用ArrayList(int initialCapacity)這個(gè)有參構(gòu)造，在創(chuàng)建時(shí)就聲明一個(gè)較大的大小。

• 使用ensureCapacity(int minCapacity)，在插入前先擴(kuò)容。

• 使用LinkedList，這個(gè)無(wú)可厚非哈，我們很快就會(huì)介紹這個(gè)適合于增刪的集合類。

上一篇：Java集合源碼分析之List（一）：超級(jí)接口List

下一篇：Java集合源碼分析之Queue（一）：超級(jí)接口Queue

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長(zhǎng)。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。