1.ArrayList的基本介紹

官方API：java.util.ArrayList

官方解釋永遠(yuǎn)是最權(quán)威的解釋

List接口的大小可變數(shù)組的實(shí)現(xiàn)。實(shí)現(xiàn)了所有可選列表操作，并允許包括 null 在內(nèi)的所有元素。除了實(shí)現(xiàn) List 接口外，此類還提供一些方法來(lái)操作內(nèi)部用來(lái)存儲(chǔ)列表的數(shù)組的大小。（此類大致上等同于 Vector 類，除了此類是不同步的。）
size、isEmpty、get、set、iterator 和 listIterator 操作都以固定時(shí)間運(yùn)行。add 操作以分?jǐn)偟墓潭〞r(shí)間 運(yùn)行，也就是說(shuō)，添加 n 個(gè)元素需要 O(n) 時(shí)間。其他所有操作都以線性時(shí)間運(yùn)行（大體上講）。與用于 LinkedList 實(shí)現(xiàn)的常數(shù)因子相比，此實(shí)現(xiàn)的常數(shù)因子較低。
每個(gè) ArrayList 實(shí)例都有一個(gè)容量。該容量是指用來(lái)存儲(chǔ)列表元素的數(shù)組的大小。它總是至少等于列表的大小。隨著向 ArrayList 中不斷添加元素，其容量也自動(dòng)增長(zhǎng)。并未指定增長(zhǎng)策略的細(xì)節(jié)，因?yàn)檫@不只是添加元素會(huì)帶來(lái)分?jǐn)偣潭〞r(shí)間開(kāi)銷那樣簡(jiǎn)單。
在添加大量元素前，應(yīng)用程序可以使用 ensureCapacity 操作來(lái)增加 ArrayList 實(shí)例的容量。這可以減少遞增式再分配的數(shù)量。
注意，此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問(wèn)一個(gè) ArrayList 實(shí)例，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了列表，那么它必須 保持外部同步。（結(jié)構(gòu)上的修改是指任何添加或刪除一個(gè)或多個(gè)元素的操作，或者顯式調(diào)整底層數(shù)組的大小；僅僅設(shè)置元素的值不是結(jié)構(gòu)上的修改。）這一般通過(guò)對(duì)自然封裝該列表的對(duì)象進(jìn)行同步操作來(lái)完成。
此類的 iterator 和 listIterator 方法返回的迭代器會(huì) fail-fast ：在創(chuàng)建迭代器之后，除非通過(guò)迭代器自身的 remove 或 add 方法從結(jié)構(gòu)上對(duì)列表進(jìn)行修改，否則在任何時(shí)間以任何方式對(duì)列表進(jìn)行修改，迭代器都會(huì)拋出 ConcurrentModificationException。因此，面對(duì)并發(fā)的修改，迭代器很快就會(huì)完全失敗，而不是冒著在將來(lái)某個(gè)不確定時(shí)間發(fā)生任意不確定行為的風(fēng)險(xiǎn)。
注意，迭代器的fail-fast行為無(wú)法得到保證，因?yàn)橐话銇?lái)說(shuō)，不可能對(duì)是否出現(xiàn)不同步并發(fā)修改做出任何硬性保證?？焖偈〉鲿?huì)盡最大努力拋出 ConcurrentModificationException。因此，為提高這類迭代器的正確性而編寫(xiě)一個(gè)依賴于此異常的程序是錯(cuò)誤的做法：迭代器的fail-fast行為應(yīng)該僅用于檢測(cè) bug。

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

image.png

ArrayList的底層是使用數(shù)組實(shí)現(xiàn)的：

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

ArrayList的默認(rèn)容量為10：

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

ArrayList特點(diǎn)

• 隨機(jī)訪問(wèn)：訪問(wèn)快（隨機(jī)訪問(wèn)）、增刪慢（會(huì)移動(dòng)數(shù)組元素）
• 排列有序，可重復(fù)
• 線程不安全
• 容量不夠時(shí)，增長(zhǎng)率為0.5
• contain()與remove()方法底層依賴的是equals()方法；若要比較引用類型數(shù)據(jù)，則需要重寫(xiě)equals方法；
• ArrayList遍歷（以及是否支持刪除元素）：
  • 普通for循環(huán)，刪除后需要將索引減一；效率最高
  • 迭代器，使用迭代器的刪除方法
  • 增強(qiáng)for循環(huán)（foreach）：不能刪除元素

2.ArrayList的構(gòu)造方法

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    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;
        }
    }

3 ArrayList的容量

與容量有關(guān)的屬性
注：常量代表static final

ArrayList的容量就是elementData.length，是這個(gè)ArrayList能夠存放多少個(gè)元素，這個(gè)elementData相當(dāng)于容器。而size指的是這個(gè)容器中已經(jīng)存放的元素?cái)?shù)量。一般對(duì)于使用者來(lái)說(shuō)，關(guān)心的是ArrayList中存放的元素?cái)?shù)量，即size，因?yàn)锳rrayList可以自動(dòng)擴(kuò)容；但是要了解ArrayList的實(shí)現(xiàn)原理，就需要了解容量的相關(guān)知識(shí)。

通過(guò)上面的構(gòu)造方法可以知道，構(gòu)造ArrayList時(shí)可以不指定大小，使用默認(rèn)大?。?0） ；也可以指定ArrayList的容量大??；甚至可以傳入一個(gè)集合來(lái)構(gòu)造ArrayList，集合的大小就是ArrayList的容量。

Tips:

• EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的區(qū)別：前者表示的是一個(gè)空數(shù)組，后者表示的也是一個(gè)空數(shù)組，但是不同在于后者是可以擴(kuò)容的，當(dāng)往進(jìn)添加首個(gè)元素的時(shí)候就會(huì)觸發(fā)擴(kuò)容機(jī)制，容量會(huì)擴(kuò)容到10個(gè)長(zhǎng)度。
• elementData字段是保存元素的緩沖數(shù)組，被transient修飾表示它不會(huì)被序列化，這意味著集合對(duì)象保存的元素不會(huì)被自動(dòng)序列化，所以后面添加了writeObject和readObject方法，用來(lái)序列化和反序列化數(shù)組中的元素。

3.1 使用默認(rèn)容量（空參構(gòu)造）

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

通過(guò)代碼可以看見(jiàn)，空參構(gòu)造方法給elementData初始化為DEFAULTCAPACITY_EMPTY_ELEMENTDATA;而DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一個(gè)空數(shù)組。怎么會(huì)說(shuō)把它初始化為10呢？
為了驗(yàn)證他的容量是0還是10，我們寫(xiě)段代碼驗(yàn)證一下：

        ArrayList list = new ArrayList();
        System.out.println(getArrayListCapacity(list));    // 反射獲取elementData.length，輸出 0

   /**
    * 通過(guò)反射機(jī)制獲取ArrayList 的容量
    * @param arrayList
    * @return
    */
   public static int getArrayListCapacity(ArrayList<?> arrayList) {
       Class<ArrayList> arrayListClass = ArrayList.class;
       try {
           Field field = arrayListClass.getDeclaredField("elementData");
           field.setAccessible(true);
           Object[] objects = (Object[])field.get(arrayList);
           return objects.length;
       } catch (NoSuchFieldException e) {
           e.printStackTrace();
           return -1;
       } catch (IllegalAccessException e) {
           e.printStackTrace();
           return -1;
       }
   }

這里輸出的確實(shí)是0，那為什么我們又說(shuō)默認(rèn)容量為10呢？
初始化ArrayList之后，肯定會(huì)添加元素，所以，我們先來(lái)粗略的看一下add()方法：

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

ArrayList的add()有很多重載方法，我們先不細(xì)究，但是每個(gè)add()都有一行類似下面的代碼

    ensureCapacityInternal(size + 1);  // Increments modCount!!

所以我們看一下這個(gè)ensureCapacityInternal(int)

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

發(fā)現(xiàn)他又調(diào)用了一個(gè)ensureExplicitCapacity(int)方法，傳入的參數(shù)是calculateCapacity(elementData, minCapacity):

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

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

下面我們來(lái)簡(jiǎn)要分析一下這幾個(gè)方法：
顧名思義（這就是命名規(guī)范的好處之一），

tips：
calculateCapacity()其實(shí)就是為了默認(rèn)構(gòu)造方法中給elementData賦值為DEFAULTCAPACITY_EMPTY_ELEMENTDATA后設(shè)計(jì)的擴(kuò)容機(jī)制：初始化默認(rèn)容量為ArrayList提供的默認(rèn)容量 或 添加元素的個(gè)數(shù)（add添加一個(gè)，addAll可以添加多個(gè)）；這里需要說(shuō)明一下，默認(rèn)容量相當(dāng)于一個(gè)閾值，是為了避免添加一個(gè)元素后，容量不至于太小，再次添加元素需要重新擴(kuò)容（并且擴(kuò)容的空間也很?。?，調(diào)用grow()中的Arrays.copyOf()創(chuàng)建新數(shù)組，效率低；但是如果使用addAll()添加的元素個(gè)數(shù)大于默認(rèn)容量了，ArrayList提供的默認(rèn)容量就不夠使用，滿足需求的最小容量就應(yīng)該是添加的元素個(gè)數(shù)。

這屬于ArrayList的擴(kuò)容機(jī)制，先不深究，但是眼睛毒辣的朋友肯定發(fā)現(xiàn)了一句解答上面問(wèn)題的關(guān)鍵代碼：

image.png

DEFAULTCAPACITY_EMPTY_ELEMENTDATA不就是空參構(gòu)造方法里給elementData賦值的常量嗎？如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，空參構(gòu)造后就滿足這個(gè)條件，之后返回DEFAULT_CAPACITY與minCapacity（這里傳入的是size+1，size為0）的最大值，就是DEFAULT_CAPACITY（上面提到的默認(rèn)容量：10）。
是不是已經(jīng)接近答案了？我們繼續(xù)深入：當(dāng)添加一個(gè)元素時(shí)，將這個(gè)DEFAULT_CAPACITY傳入ensureExplicitCapacity()，通過(guò)判斷這個(gè)容量與elementData.length（當(dāng)前容量）的大小，當(dāng)前容量不足則擴(kuò)容，調(diào)用grow()方法：

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//這里是向下取整，比如15擴(kuò)容后是22
        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ī)制：

剛初始化時(shí)容量為0,擴(kuò)容后還是0，小于傳入的minCapacity,如果傳入的是DEFAULT_CAPACITY，則擴(kuò)容為DEFAULT_CAPACITY。
由于add()添加一個(gè)的使用頻率比較高，所以傳入的size+1為1，需要給grow傳入DEFAULT_CAPACITY，所以我們通常說(shuō)ArrayList的默認(rèn)容量為10.

3.2 使用指定容量(參數(shù)為int型的容量)

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

這段代碼也比較簡(jiǎn)單，就是判斷一下容量與0的大小

• 如果大于0，直接構(gòu)造一個(gè)此容量的數(shù)組
• 如果等于0，將ArrayList的共享空實(shí)例常量EMPTY_ELEMENTDATA賦值給elementData（這里就是EMPTY_ELEMENTDATA與DEFAULTCAPACITY_EMPTY_ELEMENTDATA區(qū)分的地方，傳入0作為初始化容量，ArrayList不會(huì)把默認(rèn)容量拿來(lái)初始化，后面有代碼驗(yàn)證）
• 如果小于0，拋出IllegalArgumentException異常提示參數(shù)非法

3.3 使用集合

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

使用集合構(gòu)造一個(gè)ArrayList與上面的區(qū)別不是很大，做了集合元素是否為空的判斷：先讓elementData初始化為集合轉(zhuǎn)換的數(shù)組：

• 如果數(shù)組長(zhǎng)度不為空，就判斷elementData記錄的數(shù)組類型是否為Object [] ，如果不是，就需要將其轉(zhuǎn)換為Object []類型
• 如果數(shù)組長(zhǎng)度為空，就將elementData初始化為共享的空實(shí)例EMPTY_ELEMENTDATA

3.4 代碼驗(yàn)證擴(kuò)容機(jī)制

由于elementData外部無(wú)法訪問(wèn)，所以寫(xiě)了一段代碼用反射機(jī)制獲取集合的容量elementData.length:

    /**
     * 通過(guò)反射機(jī)制獲取ArrayList 的容量
     * @param arrayList
     * @return
     */
    public static int getArrayListCapacity(ArrayList<?> arrayList) {
        Class<ArrayList> arrayListClass = ArrayList.class;
        try {
            Field field = arrayListClass.getDeclaredField("elementData");
            field.setAccessible(true);
            Object[] objects = (Object[])field.get(arrayList);
            return objects.length;
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
            return -1;
        } catch (IllegalAccessException e) {
            e.printStackTrace();
            return -1;
        }
    }

然后基于這個(gè)動(dòng)態(tài)獲取容量的方法，編寫(xiě)了一段代碼驗(yàn)證以上理論：

/**
 * ClassName: MyCollectionCapacityTest
 * Description:
 * date: 2019/11/23 22:48
 *
 * @author seaxll
 * @since JDK 1.8
 */
public class MyCollectionCapacityTest {
    public static void main(String[] args) {
        // 分別用不同參數(shù)初始化ArrayList:空參（默認(rèn)容量）、0、5
        ArrayList<Integer> listWithDefaultCapacity = new ArrayList<>();
        ArrayList<Integer> listWithInitCapacityZero = new ArrayList<>(0);
        ArrayList<Integer> listWithInitCapacity = new ArrayList<>(5);

        // 打印初始化信息：初始容量、初始size
        System.out.println("create a ArrayList with no parameter default capacity:");
        System.out.println( "init:  elementData.length:\t" + getArrayListCapacity(listWithDefaultCapacity) +
                "\tsize:\t" + listWithDefaultCapacity.size());
        System.out.println("----------------------------------------I am is a Dividing line --------------------------------");
        System.out.println("create a ArrayList used capacity 0:");
        System.out.println( "init:  elementData.length:\t" + getArrayListCapacity(listWithInitCapacityZero) +
                "\tsize:\t" + listWithInitCapacityZero.size());
        System.out.println("----------------------------------------I am is a Dividing line --------------------------------");
        System.out.println("create a ArrayList used capacity 5:");
        System.out.println( "init:  elementData.length:\t" + getArrayListCapacity(listWithInitCapacity) +
                "\tsize:\t" + listWithInitCapacity.size());
        System.out.println("----------------------------------------I am is a Dividing line --------------------------------");

        // 擴(kuò)容并打印信息
        System.out.println("\t\t\t" + "no parameter" + "\tinitCapacity = 0"  + "\tinitCapacity = 5");
        System.out.println("init :\t\t" + getArrayListCapacity(listWithDefaultCapacity) +
                "\t\t\t\t" + getArrayListCapacity(listWithInitCapacityZero) +
                "\t\t\t\t\t" + getArrayListCapacity(listWithInitCapacity));
        // 添加50個(gè)驗(yàn)證擴(kuò)容機(jī)制，這里擴(kuò)容1.5倍，向下取整，下面代碼可以驗(yàn)證。
        for (int i = 0; i < 50; ) {
            listWithDefaultCapacity.add(i);
            listWithInitCapacityZero.add(i);
            listWithInitCapacity.add(i);
            System.out.println("size = " + (++i) +
                    "\t" + getArrayListCapacity(listWithDefaultCapacity) +
                    "\t\t\t\t" + getArrayListCapacity(listWithInitCapacityZero) +
                    "\t\t\t\t\t" + getArrayListCapacity(listWithInitCapacity));
        }

        // arrayListCapacityTest();
        // test();
    }

輸出：

create a ArrayList with no parameter default capacity:
init:  elementData.length:  0   size:   0
----------------------------------------I am is a Dividing line --------------------------------
create a ArrayList used capacity 0:
init:  elementData.length:  0   size:   0
----------------------------------------I am is a Dividing line --------------------------------
create a ArrayList used capacity 5:
init:  elementData.length:  5   size:   0
----------------------------------------I am is a Dividing line --------------------------------
            no parameter    initCapacity = 0    initCapacity = 5
init :      0               0                   5
size = 1    10              1                   5
size = 2    10              2                   5
size = 3    10              3                   5
size = 4    10              4                   5
size = 5    10              6                   5
size = 6    10              6                   7
size = 7    10              9                   7
size = 8    10              9                   10
size = 9    10              9                   10
size = 10   10              13                  10
size = 11   15              13                  15
size = 12   15              13                  15
size = 13   15              13                  15
size = 14   15              19                  15
size = 15   15              19                  15
size = 16   22              19                  22
size = 17   22              19                  22
size = 18   22              19                  22
size = 19   22              19                  22
size = 20   22              28                  22
size = 21   22              28                  22
size = 22   22              28                  22
size = 23   33              28                  33
size = 24   33              28                  33
size = 25   33              28                  33
size = 26   33              28                  33
size = 27   33              28                  33
size = 28   33              28                  33
size = 29   33              42                  33
size = 30   33              42                  33
size = 31   33              42                  33
size = 32   33              42                  33
size = 33   33              42                  33
size = 34   49              42                  49
size = 35   49              42                  49
size = 36   49              42                  49
size = 37   49              42                  49
size = 38   49              42                  49
size = 39   49              42                  49
size = 40   49              42                  49
size = 41   49              42                  49
size = 42   49              42                  49
size = 43   49              63                  49
size = 44   49              63                  49
size = 45   49              63                  49
size = 46   49              63                  49
size = 47   49              63                  49
size = 48   49              63                  49
size = 49   49              63                  49
size = 50   73              63                  73

Process finished with exit code 0

4 ArrayList中的一些方法(部分API源代碼，邏輯比較簡(jiǎn)單，可以忽略此內(nèi)容)

4.1添加

4.1.1 添加指定元素

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

ensureCapacityInternal方法主要用于校驗(yàn)當(dāng)前List的容量是否已經(jīng)達(dá)到極限，如果達(dá)到極限需要進(jìn)行擴(kuò)容。具體參照上面擴(kuò)容解析。

剩下的就是添加新元素的邏輯，簡(jiǎn)單至極，直接將新元素到添加到底層數(shù)組elementData的下一下標(biāo)位size++即可。

4.1.2 添加指定元素到指定位置

除了在末尾添加元素之外，在指定位置添加元素的時(shí)候，都依賴于 System.arraycopy()方法將指定位置的元素后的元素后移。

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

首先校驗(yàn)給定的添加位置index，index必須小于size的值，并大于等于0。

然后同樣校驗(yàn)容量是否達(dá)到極限，達(dá)到極限需要擴(kuò)容。

之后執(zhí)行一個(gè)本地方法，System.arraycopy方法用于將指定位置及其后面的所有元素整個(gè)通過(guò)復(fù)制遷移到從index+1開(kāi)始的位置，即整體后移一位，將index位空出來(lái)用于保存新元素。

最后將新元素添加到空出的index位置。

4.1.3 將指定集合中的元素添加到List末尾

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

首先將給定的集合轉(zhuǎn)換為數(shù)組Object[]。

然后以目標(biāo)List的size+給定集合轉(zhuǎn)化的數(shù)組的容量為總?cè)萘窟M(jìn)行容量校驗(yàn)，若容量不足，執(zhí)行擴(kuò)容操作。

再然后通過(guò)本地方法執(zhí)行數(shù)組復(fù)制操作將給定集合轉(zhuǎn)換數(shù)組的元素復(fù)制到目標(biāo)List的底層數(shù)組的尾部。

最后不要忘記將size增加。

4.1.4 將指定集合中的元素添加到List指定位置

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

首先校驗(yàn)下標(biāo)index，index必須小于size，大于等于0。

然后將給定集合轉(zhuǎn)換為數(shù)組Object[]，再執(zhí)行容量校驗(yàn)，擴(kuò)容操作。

通過(guò)本地方法數(shù)組復(fù)制操作將給定位置開(kāi)始的所有元素整體后移一定的距離，具體的距離為給定集合轉(zhuǎn)換后數(shù)組的容量大小，這樣就能空出容量大小的空位來(lái)存放給定的集合元素。

最后再次通過(guò)本地?cái)?shù)組復(fù)制方法將給定的集合轉(zhuǎn)換的數(shù)組元素整體復(fù)制到上一步空出來(lái)的位置上。

4.2 修改

    public E set(int index, E element) {
        rangeCheck(index);

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

修改指定位置的元素為新元素，首先需要校驗(yàn)給定index的值，index必須大于等于0，小于size，然后將新元素保存到index位置，并將舊元素返回。

4.3 獲取

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

獲取指定下標(biāo)位置的元素值，首先需要校驗(yàn)給定的下標(biāo)index，index必須大于等于0，小于size。

4.4 根據(jù)元素查詢索引

    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;
    }
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

indexOf是通過(guò)正序遍歷的方式搜索給定的元素的下標(biāo)，lastIndexOf是通過(guò)逆序遍歷的方式搜索給定元素的下標(biāo)，這兩個(gè)方法找到的下標(biāo)都是正序或者逆序該元素首次出現(xiàn)的位置下標(biāo)。如果o為null，那么將會(huì)搜索第一個(gè)null值元素的下標(biāo)。

4.5 移除

4.5.1 移除指定下標(biāo)的元素

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

首先校驗(yàn)給定的下標(biāo)值index,index必須小于size，這里的校驗(yàn)和添加元素的下標(biāo)校驗(yàn)有點(diǎn)不同：

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

前者是此處的index校驗(yàn)，后者是添加元素的index校驗(yàn)。

那為何后者比前者要多一個(gè)index<0的校驗(yàn)?zāi)?，那是因?yàn)樵赼dd(int,E)方法中，校驗(yàn)完成后緊接著就是調(diào)用本地方法進(jìn)行數(shù)組復(fù)制操作，如果index小于0，那么出錯(cuò)位置在C代碼中，無(wú)法在Java代碼中得以體現(xiàn)，所以提前進(jìn)行校驗(yàn)，保證調(diào)用本地C代碼之前參數(shù)的準(zhǔn)確性。前者校驗(yàn)完成之后，緊接著的是Java代碼獲取指定下標(biāo)的元素，如果下標(biāo)小于0，也會(huì)出錯(cuò)但是JVM會(huì)拋出異常，不會(huì)無(wú)聲無(wú)息，所以沒(méi)有必要校驗(yàn)是否小于0。

index校驗(yàn)完成后，通過(guò)本地方法數(shù)組復(fù)制將index+1及其之后的元素整體復(fù)制到index位置。

最后將原來(lái)的最后一個(gè)位置元素置空。

4.5.2 移除指定元素

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

首先通過(guò)循環(huán)操作找到首個(gè)指定的元素，然后將針對(duì)找到的元素執(zhí)行刪除操作。

刪除操作還是依靠本地的數(shù)組復(fù)制操作完成的。

4.5.3 清空元素

    public void clear() {
        modCount++;

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

        size = 0;
    }

至于清空元素，就是通過(guò)循環(huán)將List中的每個(gè)元素都刪除，將整個(gè)List置空。

4.5.4 移除當(dāng)前List中所有(不)包含在給定集合中的元素

    // 刪除當(dāng)前List中所有包含在給定集合中的元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
    // 刪除當(dāng)前List中所有不包含在給定集合中的元素
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

4.6 遍歷

ArrayList的遍歷方式有很多：

4.6.1 ListIterator

ListIterator是繼承自Iterator的，在其基礎(chǔ)上添加了反向遍歷的功能方法。

    // 截取從執(zhí)行下標(biāo)開(kāi)始的元素組成迭代器實(shí)例，進(jìn)行遍歷
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
    // 將集合中所有元素組成迭代器實(shí)例，進(jìn)行遍歷
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

源碼中的ListItr是ListIterator的實(shí)現(xiàn)類。

4.6.2 Iterator

Iterator擁有正向遍歷的功能。

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

4.6.3 Spliterator

Spliterator是分割迭代器，是JDK1.8的新功能。幾乎每個(gè)集合都實(shí)現(xiàn)了它，它是實(shí)現(xiàn)并行遍歷的基礎(chǔ)。使用這個(gè)迭代器，可以實(shí)現(xiàn)多線程遍歷集合的功能，其中每個(gè)線程遍歷集合中的一段，因此沒(méi)有線程安全問(wèn)題。

    public Spliterator<E> spliterator() {
        return new ArrayListSpliterator<>(this, 0, -1, 0);
    }

public interface Spliterator<T> {
    // 針對(duì)單個(gè)元素執(zhí)行某個(gè)行為
    // 接收一個(gè)行為（Lambda表達(dá)式或方法引用）
    boolean tryAdvance(Consumer<? super T> action);
    // 針對(duì)所有元素執(zhí)行某個(gè)行為，通過(guò)tryAdvance實(shí)現(xiàn)
    // 接收一個(gè)行為（Lambda表達(dá)式或方法引用）
    default void forEachRemaining(Consumer<? super T> action) {
        do { } while (tryAdvance(action));
    }
    // 分割集合，返回一個(gè)新的Spliterator迭代器，
    // 一旦元素被返回的迭代器攜帶，則從當(dāng)前迭代器消失
    // 一般分割是截取一半
    Spliterator<T> trySplit();
    // 獲取剩余遍歷元素的數(shù)量的估計(jì)值
    long estimateSize();
    // 當(dāng)前迭代器擁有SIZED特征值時(shí)，返回剩余元素個(gè)數(shù)，否則返回-1
    default long getExactSizeIfKnown() {
        return (characteristics() & SIZED) == 0 ? -1L : estimateSize();
    }
    // 返回當(dāng)前迭代器的特征值
    int characteristics();
    // 校驗(yàn)當(dāng)前迭代器是否擁有指定的特征值
    default boolean hasCharacteristics(int characteristics) {
        return (characteristics() & characteristics) == characteristics;
    }
    // 返回比較器
    default Comparator<? super T> getComparator() {
        throw new IllegalStateException();
    }
}

4.6.4 forEach

forEach方式是java 1.8中新增的方式，接受一個(gè)行為作為參數(shù)，即接收一個(gè)方法引用或者Lambda表達(dá)式。

    // action代表接受的行為，是一個(gè)函數(shù)式接口類型Consumer，表示消費(fèi)之意，消費(fèi)就是將資源處理掉，所以有一個(gè)入?yún)?，無(wú)返回值。
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);// 執(zhí)行函數(shù)式接口行為
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

實(shí)例：

public class ArrayListTest {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.addAll(Arrays.asList("123","444444","2123"));
        ListIterator<String> listIterator = list.listIterator();// 第一種
        listIterator.forEachRemaining(System.out::println);
        System.out.println("-------------");
        ListIterator<String> listIterator1 = list.listIterator(1);// 第二種
        listIterator1.forEachRemaining(System.out::println);
        System.out.println("-------------");
        Iterator<String> iterator = list.iterator();// 第三種
        iterator.forEachRemaining(System.out::println);
        System.out.println("-------------");
        Spliterator<String> spliterator = list.spliterator();// 第四種
        spliterator.forEachRemaining(System.out::println);
        System.out.println("-------------");
        list.forEach(System.out::println);// 第五種
    }
}

4.7 校驗(yàn)

4.7.1 是否為空

    public boolean isEmpty() {
        return size == 0;
    }

size表示的就是List中包含的元素的個(gè)數(shù)。

4.7.2 是否包含某元素

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

該校驗(yàn)通過(guò)indexOf()方法來(lái)實(shí)現(xiàn)，如果能找到元素的下標(biāo)，則存在，否則不存在。

4.8 排序

Java中排序可以通過(guò)兩種方式實(shí)現(xiàn)：

• 實(shí)現(xiàn)Comparable接口
• 使用Comparator比較器

這里很明顯ArrayList的繼承體系中并無(wú)Comparable接口，那么只能通過(guò)Comparator來(lái)實(shí)現(xiàn)，這就涉及到了ArrayList中的sort方法：

    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

使用這種方式來(lái)排序需要傳遞一個(gè)Comparator比較器作為參數(shù)，最簡(jiǎn)單的方式就是匿名內(nèi)部類方式，在Java 1.8之后直接使用Lambda來(lái)實(shí)現(xiàn)。

public class ComparatorTest {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.addAll(Arrays.asList("123","45612","7839"));
        list.sort((o1, o2) -> o1.length()-o2.length());
        list.forEach(System.out::println);
    }
}

執(zhí)行結(jié)果為：

123
7839
45612

4.9 克隆

因?yàn)锳rrayList實(shí)現(xiàn)了Cloneable接口，重寫(xiě)了clone方法，便擁有了對(duì)象克隆的功能。

    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

這是一個(gè)淺拷貝的實(shí)現(xiàn)。

4.10 序列化/反序列化

由于ArrayList中使用transient修飾了elementData，它代表的是底層的元素?cái)?shù)組，序列化的主要內(nèi)容就是它，或者說(shuō)是它里面的內(nèi)容，而它又無(wú)法被序列化，因此我們只能通過(guò)自定義writeObject方法來(lái)手動(dòng)序列化，定義readObject方法來(lái)手動(dòng)反序列化。

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

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }    

4.11 其他方法

4.11.1 trimToSize()方法：

    /**
     * 將此ArrayList實(shí)例的容量修剪為列表的當(dāng)前大小。
     * 程序可以使用此操作最小化ArrayList實(shí)例的存儲(chǔ)。
     *
     * 注意：這里只是根據(jù)size的大小去除elementData中的空元素，而不是通過(guò)判斷 == null 去掉null的元素：
     *  1) 通過(guò)remove(int index)方法(刪除index位置，并將index后的元素前移)，在后面移動(dòng)空出的位置會(huì)被 剪切 掉
     *  2) 如果通過(guò)set()方法將某個(gè)索引的位置（不論是在中間還是末尾）為null，其size不變，并不會(huì)被移出
     *  3) 此外，trimToSize還會(huì)剪切擴(kuò)容后（或初始化ArrayList容量時(shí)）多出的空余位置。
     */
    public void trimToSize() {
        // modCount:繼承自 AbstractList 中的屬性，記錄著 ArrayList 被修改的次數(shù)
        // modCount 與 fail-fast 機(jī)制有關(guān) （concurrentModficationException）
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
                    ? EMPTY_ELEMENTDATA
                    : Arrays.copyOf(elementData, size);
        }
    }

驗(yàn)證代碼：

    public void testTrimToSize(){
        ArrayList<String> arrayList = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            arrayList.add(String.valueOf(i));
        }
        // arrayList.remove(4); // 9    [0, 1, 2, 3, 5, 6, 7, 8, 9]
        arrayList.set(4,null);  // 10   [0, 1, 2, 3, null, 5, 6, 7, 8, 9]
        arrayList.trimToSize();
        System.out.println(arrayList.size() + " \t" + arrayList);
    }

5 其他

5.1 modCount

該字段表示list結(jié)構(gòu)上被修改的次數(shù)。結(jié)構(gòu)上的修改指的是那些改變了list的長(zhǎng)度大小或者使得遍歷過(guò)程中產(chǎn)生不正確的結(jié)果的其它方式。
該字段被Iterator以及ListIterator的實(shí)現(xiàn)類所使用，如果該值被意外更改，Iterator或者ListIterator 將拋出ConcurrentModificationException異常。
這是jdk在面對(duì)迭代遍歷的時(shí)候?yàn)榱吮苊獠淮_定性而采取的fast-fail原則。
子類對(duì)此字段的使用是可選的，如果子類希望支持快速失敗，只需要覆蓋該字段相關(guān)的所有方法即可。單線程調(diào)用不能添加刪除terator正在遍歷的對(duì)象，否則將可能拋出ConcurrentModificationException異常，如果子類不希望支持fast-fail，該字段可以直接忽略。

/**
 * ClassName: ArrayListTest
 * Description:
 * date: 2019/11/24 10:24
 *
 * @author seaxll
 * @since JDK 1.8
 */
public class ArrayListTest {
    public static void main(String[] args) {
        removeTest();
    }
    public static void removeTest(){
        List<Integer> list = new ArrayList();
        for (int i = 0; i < 5; i++) {
            list.add(i);
        }

        Iterator it = list.iterator();
        int i = 0;
        while(it.hasNext()){
            if(i==2){
                it.remove();// 如果用list.remove(it.next());會(huì)報(bào)異常
            }
            System.out.println("第"+i+"個(gè)元素"+it.next());
            i++ ;
        }
        System.out.println("----------------");
        Iterator it2 = list.iterator();
        while(it2.hasNext()){
            System.out.println(it2.next());
        }
    }
}

另：注意it.remove()刪除的是最近的一次it.next()獲取的元素，而不是當(dāng)前iterator中游標(biāo)指向的元素?。?br> 因此，本例中i==2時(shí)，刪除的其實(shí)是1，而不是2，這很容易被忽視或者誤解。如果想刪掉2,正確操作是先調(diào)用it.next()獲取到具體元素，再判斷；而且由于調(diào)用了it.next(),此時(shí)游標(biāo)已經(jīng)指向我們期望刪除的值了。想直接數(shù)數(shù)字進(jìn)行刪除，在這里會(huì)容易出錯(cuò)誤。可以理解為此處的下標(biāo)從1開(kāi)始。

其實(shí)我們可以查看Iterator的源碼來(lái)驗(yàn)證：

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

返回的是一個(gè)Itr對(duì)象，這個(gè)Itr是ArrayList的內(nèi)部類

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return   //下一個(gè)元素的游標(biāo)
    int lastRet = -1; // index of last element returned; -1 if no such  //上一個(gè)元素的
    int expectedModCount = modCount;  //修改計(jì)數(shù)器期望值
 
    public boolean hasNext() {
        return cursor != size;
    }
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor; //此時(shí)的游標(biāo)，指向的是本次要遍歷的對(duì)象，因?yàn)樯弦淮我呀?jīng)++了，初始值為0，沒(méi)有++的情況下是第一個(gè)元素
        if (i >= size)   //越界了
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;  //游標(biāo)指向了下一個(gè)元素, 但 i 的值沒(méi)有變
        return (E) elementData[lastRet = i];   //將 i 賦值給lastRet，取的值是方法開(kāi)始時(shí)int i=cursor；中的cursor指向的值，而且最終這個(gè)游標(biāo)的數(shù)值賦值給了lastRet
    }
    public void remove() {
        if (lastRet < 0)  // 如果沒(méi)有next()操作就直接remove的話，lastRet=-1，會(huì)拋異常
            throw new IllegalStateException();
        checkForComodification();
        try {
            ArrayList.this.remove(lastRet); // remove之前，cursor、lastRet的值沒(méi)有修改，都是上次next之后的值，因此此處的lastRet指向上次next獲取的元素
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;  // 手動(dòng)將ArrayList.remove()后modCount的值賦給expectedModCount，避免引起不一致
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

以上代碼告訴我們，iterator.remove(）實(shí)際是remove了上次next返回的元素，并且為了防止ConcurrentModificationException異常，手動(dòng)修復(fù)了修改計(jì)數(shù)的期望值，而且如果沒(méi)有經(jīng)過(guò)next操作就直接remove的話，會(huì)因?yàn)槌跏嫉膌astRet=-1而拋出IllegalStateException異常。

6.總結(jié)

• ArrayList底層采用數(shù)組實(shí)現(xiàn)，擁有快速隨機(jī)訪問(wèn)能力，但是非線程安全的集合。
• ArrayList默認(rèn)容量為10，擴(kuò)容規(guī)則為當(dāng)要保存的新元素所需的容量不足時(shí)觸發(fā)，基本規(guī)則為擴(kuò)容1.5倍。
• 如果在遍歷的時(shí)候發(fā)生結(jié)構(gòu)性變化，會(huì)觸發(fā)ConcurrentModificationException異常。
• ArrayList支持序列化功能，支持克?。\拷貝）功能，排序功能等。

以上只是我——一個(gè)java新手學(xué)習(xí)時(shí)的一點(diǎn)思考與筆記，如果有朋友刷到這篇筆記，并且賞臉看了這篇筆記，如果發(fā)現(xiàn)了有不對(duì)的地方，還請(qǐng)不吝賜教。