ArrayList源碼解讀（基于JDK1.8）

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源碼解讀（基于JDK1.8）

下面讓我們翻開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;
    }

方法執行流程

ArrayList源碼解讀（基于JDK1.8）

確定添加的元素有地方存儲，當第一次添加元素的時候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++;
    }

方法執行流程

ArrayList源碼解讀（基于JDK1.8）

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

get方法

傳回指定位置上的元素，

public E get(int index) {
        //越界檢查
        rangeCheck(index);
        return elementData(index);
    }

方法執行流程

ArrayList源碼解讀（基于JDK1.8）

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

方法執行流程

ArrayList源碼解讀（基于JDK1.8）

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

方法執行流程

ArrayList源碼解讀（基于JDK1.8）

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

根據對象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;
    }

方法執行流程

ArrayList源碼解讀（基于JDK1.8）

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

    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
    }

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源碼解讀（基于JDK1.8）

資料結構

繼續閱讀

Openstack liberty 雲主機遷移源碼分析之靜态遷移1

Android源碼探索-View體系(一)

自定義View原理篇（2）- layout過程1. 簡介2. layout的始點3.layout過程分析4. 自定義View5. 其他

spring源碼解讀：@Async的原理——預設配置前言一、如何使用@Async二、源碼解讀總結

Spring IOC 源碼分析-bean标簽解析概述重點關系圖代碼流程分析

spring源碼分析-預設标簽解析預設标簽解析

Spring源碼(IOC子產品)分析

深入淺出異步I/O模型

詳細分析MyBatis的工作原理以及核心流程詳解

線程池ThreadPoolExecutor底層原理源碼分析

深入淺出Mybatis源碼系列（一）---Mybatis入門

spring源碼：spring生命周期中重要的接口類

spring核心包類圖關系-spring源碼學習（1）

EventBus分析EventBus源碼分析源碼分析

重新認識HashMap

基于jdk1.8的Vector源碼分析