Java集合源碼分析之List（二）：ArrayList

Java集合源碼分析之List（二）：ArrayListJava集合源碼分析之List（二）：ArrayListArrayList繼承結構構造方法與初始化重要方法其他實作方法總結

大大紙飛機關注 2018.04.17 16:02* 字數 1952 閱讀 427 評論 5 喜歡 2

做了這麼多準備，終于到了

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

因為種種原因不推薦使用了，這裡我們就不對其進行分析了。

ArrayList

是一個可以動态調整大小的

List

實作，其資料的順序與插入順序始終一緻，其餘特性與

List

中定義的一緻。

ArrayList繼承結構

Java集合源碼分析之List（二）：ArrayListJava集合源碼分析之List（二）：ArrayListArrayList繼承結構構造方法與初始化重要方法其他實作方法總結

ArrayList結構圖

可以看到，

ArrayList

是

AbstractList

的子類，同時實作了

List

接口。除此之外，它還實作了三個辨別型接口，這幾個接口都沒有任何方法，僅作為辨別表示實作類具備某項功能。

RandomAccess

表示實作類支援快速随機通路，

Cloneable

表示實作類支援克隆，具體表現為重寫了

clone

方法，

java.io.Serializable

則表示支援序列化，如果需要對此過程自定義，可以重寫

writeObject

與

readObject

方法。

一般面試問到與

ArrayList

相關的問題時，可能會問

ArrayList

的初始大小是多少？很多人在初始化

ArrayList

時，可能都是直接調用無參構造函數，從未關注過此問題。例如，這樣擷取一個對象：

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

我們都知道，

ArrayList

是基于數組的，而數組是定長的。那

ArrayList

為何不需要指定長度，就能使我們既可以插入一條資料，也可以插入一萬條資料？回想剛剛文檔的第一句話：

Resizable-array implementation of the List interface.

ArrayList

可以動态調整大小，是以我們才可以無感覺的插入多條資料，這也說明其必然有一個預設的大小。而要想擴充數組的大小，隻能通過複制。這樣一來，預設大小以及如何動态調整大小會對使用性能産生非常大的影響。我們舉個例子來說明此情形：

比如預設大小為5，我們向

ArrayList

中插入5條資料，并不會涉及到擴容。如果想插入100條資料，就需要将

ArrayList

大小調整到100再進行插入，這就涉及一次數組的複制。如果此時，還想再插入50條資料呢？那就得把大小再調整到150，把原有的100條資料複制過來，再插入新的50條資料。自此之後，我們每向其中插入一條資料，都要涉及一次資料拷貝，且資料量越大，需要拷貝的資料越多，性能也會迅速下降。

其實，

ArrayList

僅僅是對數組操作的封裝，裡面采取了一定的措施來避免以上的問題，如果我們不利用這些措施，就和直接使用數組沒有太大的差別。那我們就看看

ArrayList

用了哪些措施，并且如何使用它們吧。我們先從初始化說起。

構造方法與初始化

ArrayList

一共有三個構造方法，用到了兩個成員變量。

//這是一個用來标記存儲容量的數組，也是存放實際資料的數組。
//當ArrayList擴容時，其capacity就是這個數組應有的長度。
//預設時為空，添加進第一個元素後，就會直接擴充到DEFAULT_CAPACITY，也就是10
//這裡和size差別在于，ArrayList擴容并不是需要多少就擴充多少的
transient Object[] elementData;

//這裡就是實際存儲的資料個數了
private int size;

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

protected transient int modCount = ;

這個變量主要作用是防止在進行一些操作時，改變了

ArrayList

的大小，那将使得結果不可預測。

下面我們看看構造函數：

//預設構造方法。文檔說明其預設大小為10，但正如elementData定義所言，
//隻有插入一條資料後才會擴充為10，而實際上預設是空的
 public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//帶初始大小的構造方法，一旦指定了大小，elementData就不再是原來的機制了。
public ArrayList(int initialCapacity) {
    if (initialCapacity > ) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == ) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    }
}

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

重要方法

ArrayList

已經是一個具體的實作類了，是以在

List

接口中定義的所有方法在此都做了實作。其中有些在

AbstractList

中實作過的方法，在這裡再次被重寫，我們稍後就可以看到它們的差別。

先看一些簡單的方法：

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

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

//一樣的道理，已經有了所有元素，不需要再利用Iterator來擷取元素了
//注意這裡傳回時把elementData截斷為size大小
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

//帶類型的轉換，看到這裡a[size] = null;這個用處真不大，除非你确定所有元素都不為空，
//才可以通過null來判斷擷取了多少有用資料。
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // 給定的資料長度不夠，複制出一個新的并傳回
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, , a, , size);
    if (a.length > size)
        a[size] = null;
    return a;
}

資料操作最重要的就是增删改查，改查都不涉及長度的變化，而增删就涉及到動态調整大小的問題，我們先看看改和查是如何實作的：

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

//隻要擷取的資料位置在0-size之間即可
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

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

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

增和删是

ArrayList

最重要的部分，這部分代碼需要我們細細研究，我們看看它是如何處理我們例子中的問題的：

//在最後添加一個元素
public boolean add(E e) {
    //先確定elementData數組的長度足夠
    ensureCapacityInternal(size + );  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

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

    //先確定elementData數組的長度足夠
    ensureCapacityInternal(size + );  // Increments modCount!!
    //将資料向後移動一位，空出位置之後再插入
    System.arraycopy(elementData, index, elementData, index + ,
                         size - index);
    elementData[index] = element;
    size++;
}

以上兩種添加資料的方式都調用到了

ensureCapacityInternal

這個方法，我們看看它是如何完成工作的：

//在定義elementData時就提過，插入第一個資料就直接将其擴充至10
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    
    //這裡把工作又交了出去
    ensureExplicitCapacity(minCapacity);
}

//如果elementData的長度不能滿足需求，就需要擴充了
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

//擴充
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //可以看到這裡是1.5倍擴充的
    int newCapacity = oldCapacity + (oldCapacity >> );
    
    //擴充完之後，還是沒滿足，這時候就直接擴充到minCapacity
    if (newCapacity - minCapacity < )
        newCapacity = minCapacity;
    //防止溢出
    if (newCapacity - MAX_ARRAY_SIZE > )
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

至此，我們徹底明白了

ArrayList

的擴容機制了。首先建立一個空數組elementData，第一次插入資料時直接擴充至10，然後如果elementData的長度不足，就擴充1.5倍，如果擴充完還不夠，就使用需要的長度作為elementData的長度。

這樣的方式顯然比我們例子中好一些，但是在遇到大量資料時還是會頻繁的拷貝資料。那麼如何緩解這種問題呢，

ArrayList

為我們提供了兩種可行的方案：

使用 ArrayList(int initialCapacity) 這個有參構造，在建立時就聲明一個較大的大小，這樣解決了頻繁拷貝問題，但是需要我們提前預知資料的數量級，也會一直占有較大的記憶體。
除了添加資料時可以自動擴容外，我們還可以在插入前先進行一次擴容。隻要提前預知資料的數量級，就可以在需要時直接一次擴充到位，與 ArrayList(int initialCapacity) 相比的好處在于不必一直占有較大記憶體，同時資料拷貝的次數也大大減少了。這個方法就是ensureCapacity(int minCapacity)，其内部就是調用了 ensureCapacityInternal(int minCapacity) 。

其他還有一些比較重要的函數，其實作的原理也大同小異，這裡我們不一一分析了，但還是把它們列舉出來，以便使用。

//将elementData的大小設定為和size一樣大，釋放所有無用記憶體
public void trimToSize() {
    //...
}

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

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

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

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

//删除指定範圍内的元素
protected void removeRange(int fromIndex, int toIndex){
    //...
}

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

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

ArrayList

還對父級實作的

ListIterator

以及

SubList

進行了優化，主要是使用位置通路元素，我們就不再研究了。

其他實作方法

ArrayList

不僅實作了

List

中定義的所有功能，還實作了

equals

、

hashCode

、

clone

、

writeObject

與

readObject

等方法。這些方法都需要與存儲的資料配合，否則結果将是錯誤的或者克隆得到的資料隻是淺拷貝，或者資料本身不支援序列化等，這些我們定義資料時注意到即可。我們主要看下其在序列化時自定義了哪些東西。

//這裡就能解開我們的迷惑了，elementData被transient修飾，也就是不會參與序列化
//這裡我們看到資料是一個個寫入的，并且将size也寫入了進去
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=; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    //modCount的作用在此展現，如果序列化時進行了修改操作，就會抛出異常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

readObject

是一個相反的過程，就是把資料正确的恢複回來，并将

elementData

設定好即可，感興趣可以自行閱讀源碼。

總結

總體而言，

ArrayList

還是和數組一樣，更适合于資料随機通路，而不太适合于大量的插入與删除，如果一定要進行插入操作，要使用以下三種方式：

使用 ArrayList(int initialCapacity) 這個有參構造，在建立時就聲明一個較大的大小。
使用ensureCapacity(int minCapacity)，在插入前先擴容。
使用LinkedList，這個無可厚非哈，我們很快就會介紹這個适合于增删的集合類。

轉載： https://www.jianshu.com/p/15e8e72ad0c8

Java集合源碼分析之List（二）：ArrayListJava集合源碼分析之List（二）：ArrayListArrayList繼承結構構造方法與初始化重要方法其他實作方法總結

Java集合源碼分析之List（二）：ArrayList

ArrayList繼承結構

構造方法與初始化

重要方法

其他實作方法

總結

繼續閱讀

Java中Map與Set的關系

Java 集合（五）| 集合面試彙總一、HashMap面試彙總二、List面試彙總三、補充

java 集合源碼探究之 treemap 如何保證有序，put過程， get過程。TreeMap

Java集合之LinkedList1. 簡介2. 繼承體系3. 深入源碼4. 總結

Java集合-ArrayList2. 簡介2. List 實作類 - ArrayList

RandomAccess接口了解根據javadoc上面的的解釋是：

HashMap、LinkedHashMap、ConcurrentHashMap、ArrayList、LinkedList的底層實作

Java 集合fail-fast總結(通過ArrayList來說明fail-fast的原理、解決辦法)1 fail-fast簡介2 fail-fast示例3 fail-fast解決辦法4 fail-fast原理5 解決fail-fast的原理

Java 集合系列（8）： Map接口源碼

Java集合源碼探究之周遊方式，Set List Map

java 集合架構-LinkedHashMap

拆行解碼 Java 集合源碼之總覽

拆行解碼 Java 集合源碼之 ArrayDeque

拆行解碼 Java 集合源碼之 Hashtable

JAVA 集合之 LinkedListLinkedList