ArrayList源碼分析（基于JDK8）

ArrayList簡介

ArrayList 是一個數組隊列，相當于動态數組。與Java中的數組相比，它的容量能動态增長。它繼承于AbstractList，實作了List, RandomAccess, Cloneable, java.io.Serializable這些接口。

ArrayList 繼承了AbstractList，實作了List。它是一個數組隊列，提供了相關的添加、删除、修改、周遊等功能。

ArrayList 實作了RandmoAccess接口，即提供了随機通路功能。RandmoAccess是java中用來被List實作，為List提供快速通路功能的。在ArrayList中，我們即可以通過元素的序号快速擷取元素對象；這就是快速随機通路。稍後，我們會比較List的“快速随機通路”和“通過Iterator疊代器通路”的效率。

ArrayList 實作了Cloneable接口，即覆寫了函數clone()，能被克隆。

ArrayList 實作java.io.Serializable接口，這意味着ArrayList支援序列化，能通過序列化去傳輸。

和Vector不同，ArrayList中的操作不是線程安全的！是以，建議在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList。

下面讓我們翻開ArrayList的源代碼，看看一些常用的方法屬性，以及一些需要注意的地方。

ArrayList屬性

ArrayList屬性主要就是目前數組長度size，以及存放數組的對象elementData數組，除此之外還有一個經常用到的屬性就是從AbstractList繼承過來的modCount屬性，代表ArrayList集合的修改次數。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    // 序列化id
    private static final long serialVersionUID = 8683452581122892189L;
    // 預設初始的容量
    private static final int DEFAULT_CAPACITY = 10;
    // 一個空對象
    private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
    // 一個空對象，如果使用預設構造函數建立，則預設對象内容預設是該值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
    // 目前資料對象存放地方，目前對象不參與序列化
    transient Object[] elementData;
    // 目前數組長度
    private int size;
    // 數組最大長度
    private static final int MAX_ARRAY_SIZE = 2147483639;
 
    // 省略方法。。
}

ArrayList構造函數

無參構造函數

如果不傳入參數，則使用預設無參建構方法建立ArrayList對象，如下：

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

注意：此時我們建立的ArrayList對象中的elementData中的長度是1，size是0,當進行第一次add的時候，elementData将會變成預設的長度：10.

帶int類型的構造函數

如果傳入參數，則代表指定ArrayList的初始數組長度，傳入參數如果是大于等于0，則使用使用者的參數初始化，如果使用者傳入的參數小于0，則抛出異常，構造方法如下：

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

帶Collection對象的構造函數

1）将collection對象轉換成數組，然後将數組的位址的賦給elementData。

2）更新size的值，同時判斷size的大小，如果是size等于0，直接将空對象EMPTY_ELEMENTDATA的位址賦給elementData

3）如果size的值大于0，則執行Arrays.copy方法，把collection對象的内容（可以了解為深拷貝）copy到elementData中。

注意：this.elementData = arg0.toArray(); 這裡執行的簡單指派時淺拷貝，是以要執行Arrays,copy 做深拷貝

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

add方法

add的方法有兩個，一個是帶一個參數的，一個是帶兩個參數的，下面我們一個個講解。

add(E e) 方法

add主要的執行邏輯如下：

1）確定數組已使用長度（size）加1之後足夠存下下一個資料

2）修改次數modCount 辨別自增1，如果目前數組已使用長度（size）加1後的大于目前的數組長度，則調用grow方法，增長數組，grow方法會将目前數組的長度變為原來容量的1.5倍。

3）確定新增的資料有地方存儲之後，則将新元素添加到位于size的位置上。

4）傳回添加成功布爾值。

添加元素方法入口：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

確定添加的元素有地方存儲，當第一次添加元素的時候this.size+1 的值是1，是以第一次添加的時候會将目前elementData數組的長度變為10：

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
 
        ensureExplicitCapacity(minCapacity);
    }

将修改次數（modCount）自增1，判斷是否需要擴充數組長度,判斷條件就是用目前所需的數組最小長度與數組的長度對比，如果大于0，則增長數組長度。

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

如果目前的數組已使用空間（size）加1之後大于數組長度，則增大數組容量，擴大為原來的1.5倍。

private void grow(int arg0) {
        int arg1 = this.elementData.length;
        int arg2 = arg1 + (arg1 >> 1);
        if (arg2 - arg0 < 0) {
            arg2 = arg0;
        }
 
        if (arg2 - 2147483639 > 0) {
            arg2 = hugeCapacity(arg0);
        }
 
        this.elementData = Arrays.copyOf(this.elementData, arg2);
    }

add(int index, E element)方法

這個方法其實和上面的add類似，該方法可以按照元素的位置，指定位置插入元素，具體的執行邏輯如下：

1）確定數插入的位置小于等于目前數組長度，并且不小于0，否則抛出異常

2）確定數組已使用長度（size）加1之後足夠存下下一個資料

3）修改次數（modCount）辨別自增1，如果目前數組已使用長度（size）加1後的大于目前的數組長度，則調用grow方法，增長數組

4）grow方法會将目前數組的長度變為原來容量的1.5倍。

5）確定有足夠的容量之後，使用System.arraycopy 将需要插入的位置（index）後面的元素統統往後移動一位。

6）将新的資料内容存放到數組的指定位置（index）上

public void add(int index, E element) {
        rangeCheckForAdd(index);
 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

注意：使用該方法的話将導緻指定位置後面的數組元素全部重新移動，即往後移動一位。

get方法

傳回指定位置上的元素，

public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
        }

set方法

確定set的位置小于目前數組的長度（size）并且大于0，擷取指定位置（index）元素，然後放到oldValue存放，将需要設定的元素放到指定的位置（index）上，然後将原來位置上的元素oldValue傳回給使用者。

public E set(int index, E element) {
        rangeCheck(index);
 
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

contains方法

調用indexOf方法，周遊數組中的每一個元素作對比，如果找到對于的元素，則傳回true，沒有找到則傳回false。

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

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

remove方法

根據索引remove

1）判斷索引有沒有越界

2）自增修改次數

3）将指定位置（index）上的元素儲存到oldValue

4）将指定位置（index）上的元素都往前移動一位

5）将最後面的一個元素置空，好讓垃圾回收器回收

6）将原來的值oldValue傳回

public E remove(int index) {
        rangeCheck(index);
 
        modCount++;
        E oldValue = elementData(index);
 
        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
 
        return oldValue;
    }

注意：調用這個方法不會縮減數組的長度，隻是将最後一個數組元素置空而已。

根據對象remove

循環周遊所有對象，得到對象所在索引位置，然後調用fastRemove方法，執行remove操作

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

定位到需要remove的元素索引，先将index後面的元素往前面移動一位（調用System.arraycooy實作），然後将最後一個元素置空。

clear方法

添加操作次數（modCount），将數組内的元素都置空，等待垃圾收集器收集，不減小數組容量。

public void clear() {
        modCount++;
 
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
 
        size = 0;
    }

sublist方法

我們看到代碼中是建立了一個ArrayList 類裡面的一個内部類SubList對象，傳入的值中第一個參數時this參數，其實可以了解為傳回目前list的部分視圖，真實指向的存放資料内容的地方還是同一個地方，如果修改了sublist傳回的内容的話，那麼原來的list也會變動。

public List<E> subList(int arg0, int arg1) {
        subListRangeCheck(arg0, arg1, this.size);
        return new ArrayList.SubList(this, 0, arg0, arg1);
    }

trimToSize方法

1）修改次數加1

2）将elementData中空餘的空間（包括null值）去除，例如：數組長度為10，其中隻有前三個元素有值，其他為空，那麼調用該方法之後，數組的長度變為3.

public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

iterator方法

interator方法傳回的是一個内部類，由于内部類的建立預設含有外部的this指針，是以這個内部類可以調用到外部類的屬性。

public Iterator<E> iterator() {
        return new Itr();
    }

一般的話，調用完iterator之後，我們會使用iterator做周遊，這裡使用next做周遊的時候有個需要注意的地方，就是調用next的時候，可能會引發ConcurrentModificationException，當修改次數，與期望的修改次數（調用iterator方法時候的修改次數）不一緻的時候，會發生該異常，詳細我們看一下代碼實作：

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

expectedModCount這個值是在使用者調用ArrayList的iterator方法時候确定的，但是在這之後使用者add，或者remove了ArrayList的元素，那麼modCount就會改變，那麼這個值就會不相等，将會引發ConcurrentModificationException異常，這個是在多線程使用情況下，比較常見的一個異常。

final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

System.arraycopy 方法

參數	說明
src	原數組
srcPos
dest	目标數組
destPos	目标數組的起始位置
length	要複制的數組元素的數目

Arrays.copyOf方法

original - 要複制的數組
newLength - 要傳回的副本的長度
newType - 要傳回的副本的類型

其實Arrays.copyOf底層也是調用System.arraycopy實作的源碼如下：

//基本資料類型（其他類似byte，short···）
public static int[] copyOf(int[] original, int newLength) {
        int[] copy = new int[newLength];
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

小結

ArrayList總體來說比較簡單，不過ArrayList還有以下一些特點：

ArrayList自己實作了序列化和反序列化的方法，因為它自己實作了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法

ArrayList基于數組方式實作，無容量的限制（會擴容）

添加元素時可能要擴容（是以最好預判一下），删除元素時不會減少容量（若希望減少容量，trimToSize()），删除元素時，将删除掉的位置元素置為null，下次gc就會回收這些元素所占的記憶體空間。

線程不安全

add(int index, E element)：添加元素到數組中指定位置的時候，需要将該位置及其後邊所有的元素都整塊向後複制一位

get(int index)：擷取指定位置上的元素時，可以通過索引直接擷取（O(1)）

remove(Object o)需要周遊數組

remove(int index)不需要周遊數組，隻需判斷index是否符合條件即可，效率比remove(Object o)高

contains(E)需要周遊數組

使用iterator周遊可能會引發多線程異常

幾點總結（重要）

關于ArrayList的源碼，給出幾點比較重要的總結：

注意其三個不同的構造方法。無參構造方法構造的ArrayList的容量預設為10，帶有Collection參數的構造方法，将Collection轉化為數組賦給ArrayList的實作數組elementData。
注意擴充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1個，也可能是一組）時，都要調用該方法來確定足夠的容量。當容量不足以容納目前的元素個數時，就設定新的容量為舊的容量的1.5倍加1，如果設定後的新容量還不夠，則直接新容量設定為傳入的參數（也就是所需的容量），而後用Arrays.copyof()方法将元素拷貝到新的數組（詳見下面的第3點）。從中可以看出，當容量不夠時，每次增加元素，都要将原來的元素拷貝到一個新的數組中，非常之耗時，也是以建議在事先能确定元素數量的情況下，才使用ArrayList，否則建議使用LinkedList。
ArrayList的實作中大量地調用了Arrays.copyof()和System.arraycopy()方法。我們有必要對這兩個方法的實作做下深入的了解。

首先來看Arrays.copyof()方法。它有很多個重載的方法，但實作思路都是一樣的，我們來看泛型版本的源碼：

public static <T> T[] copyOf(T[] original, int newLength) {  
    return (T[]) copyOf(original, newLength, original.getClass());  
}

很明顯調用了另一個copyof方法，該方法有三個參數，最後一個參數指明要轉換的資料的類型，其源碼如下：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {  
    T[] copy = ((Object)newType == (Object)Object[].class)  
        ? (T[]) new Object[newLength]  
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);  
    System.arraycopy(original, 0, copy, 0,  
                     Math.min(original.length, newLength));  
    return copy;  
}

這裡可以很明顯地看出，該方法實際上是在其内部又建立了一個長度為newlength的數組，調用System.arraycopy()方法，将原來數組中的元素複制到了新的數組中。

下面來看System.arraycopy()方法。該方法被标記了native，調用了系統的C/C++代碼，在JDK中是看不到的，但在openJDK中可以看到其源碼。該函數實際上最終調用了C語言的memmove()函數，是以它可以保證同一個數組内元素的正确複制和移動，比一般的複制方法的實作效率要高很多，很适合用來批量處理數組。Java強烈推薦在複制大量數組元素時用該方法，以取得更高的效率。

注意ArrayList的兩個轉化為靜态數組的toArray方法。

第一個，Object[] toArray()方法。該方法有可能會抛出java.lang.ClassCastException異常，如果直接用向下轉型的方法，将整個ArrayList集合轉變為指定類型的Array數組，便會抛出該異常，而如果轉化為Array數組時不向下轉型，而是将每個元素向下轉型，則不會抛出該異常，顯然對數組中的元素一個個進行向下轉型，效率不高，且不太友善。

第二個， T[] toArray(T[] a)方法。該方法可以直接将ArrayList轉換得到的Array進行整體向下轉型（轉型其實是在該方法的源碼中實作的），且從該方法的源碼中可以看出，參數a的大小不足時，内部會調用Arrays.copyOf方法，該方法内部建立一個新的數組傳回，是以對該方法的常用形式如下：

public static Integer[] vectorToArray2(ArrayList<Integer> v) {    
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);    
    return newText;    
}

ArrayList基于數組實作，可以通過下标索引直接查找到指定位置的元素，是以查找效率高，但每次插入或删除元素，就要大量地移動元素，插入删除元素的效率低。
在查找給定元素索引值等的方法中，源碼都将該元素的值分為null和不為null兩種情況處理，ArrayList中允許元素為null。

ArrayList源碼分析（基于JDK8）

ArrayList簡介

ArrayList屬性

ArrayList構造函數

remove方法

小結

幾點總結（重要）

繼續閱讀

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

詳解STM32單片機的堆棧

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method