基于ArrayList源碼分析

本篇內容主要講解“基于ArrayList源碼分析”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“基于ArrayList源碼分析”吧!

ArrrayList是Java中經常被用到的集合，弄清楚它的底層實現，有利于我們更好地使用它。

下圖是ArrayList的UML圖

從圖中我們可以看出

1： 實現了RandomAccess接口：表面ArrayList支持快速（通常是常量時間）的隨機訪問。官方源碼也給出了解釋：（因為底層實現是一個數組，所以get()方法要比迭代器快，后面還會更有更加詳細的源碼解析）

2：實現了Cloneable接口，表明它支持克隆。可以調用clone（）進行淺拷貝。

3：實現了Serializable接口，表明它支持序列化。

4：它還實現了List接口，并且繼承自AbstractList抽象類。

代碼分析部分太多了，我直接把總結弄到最上面了，可以方便查看。

總結：

• ① ArrayList在我們日常開發中隨處可見，所以建議大家可以自己手動實現一個ArrayList，實在寫不出來可以模仿一下ArrayList么。

• ② 由于ArryList隨機存儲，底層是用的一個數組作為存放元素的，所以在遍歷ArrayList的時候，使用get（）方法的效率要比使用迭代器的效率高。

• ③在ArrayList中經常使用的一個變量modCount，它是在ArrayList的父類AbstractList中定義的一個protected變量，該變量主要在多線程的環境下，如果使用迭代器進行刪除或其他操作的時候，需要保證此刻只有該迭代器進行修改操作，一旦出現其他線程調用了修改modCount的值的方法，迭代器的方法中就會拋出異常。究其原因還是因為ArrayList是線程不安全的。

• ④ 在ArrayList底層實現中，很多數組中元素的移動，都是通過本地方法System.arraycopy實現的，該方法是由native修飾的。

• ⑤ 在學習源碼的過程中，如果有看不懂的方法，可以自己寫一個小例子調用一下這個方法，然后通過debug的方式輔助理解代碼的含義。當然啦，有能力的最好自己實現一下。（不過有些方法確實設計的超級精巧，直接讀代碼還看不懂，只能通過debug輔助學習源代碼，更別提寫這些方法了。。。。）

• ⑥ 不過我們在操作集合的過程中，盡量使用使用基于Stream的操作，這樣能夠不僅寫起來爽，看起來更爽！真的是誰用誰知道。簡直不要太爽！

下面是源碼解析的部分

①首先我們先看一下JDK中ArrayList的屬性有哪些：

   private static final long serialVersionUID = 8683452581122892189L;
	
	//默認的容量
	private static final int DEFAULT_CAPACITY = 10;
    
    //定義了一個空的數組，用于在用戶初始化代碼的時候傳入的容量為0時使用。
    private static final Object[] EMPTY_ELEMENTDATA = {};
	
	//同樣是一個空的數組，用于默認構造器中，賦值給頂層數組elementData。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
	
	//底層數組，ArrayList中真正存儲元素的地方。
    transient Object[] elementData;
     
    //用來表示集合中含有元素的個數
    private int size;

②看看我們的JDK中提供的構造器：（提供了三種構造器，分別是：需要提供一個初始容量、默認構造器、需要提供一個Collection集合。）

//  如果我們給定的容量等于零，它就會調用上面的空數組EMPTY_ELEMENTDATA。
//	如果大于零的話，就把底層的elementData進行初始化為指定容量的數組。
//	當然啦，如果小于零的話，就拋出了違法參數異常（IllegalArgumentException）。
 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);
        }
    }


    /**
     * 默認的情況下，底層的elementData使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA數組。
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     *
     * 傳入一個集合，首先把集合轉化為數組，然后把集合的底層數組elementData指向該數組，
     * 此時，底層數組有元素了，而size屬性表示ArrayList內部元素的個數，所以需要把底層數組
     * element的大小賦值給size屬性，然后在它不等于0 的情況
     * 下（也就是傳進來的集合不為空），再通過判斷保證此刻底層數組elementData數組的類型
     * 和Object[]類型相同，如果不同，則拷貝一個Object[]類型的數組給elementData數組。
     * 如果參數collection為null的話，將會報空指針異常。
     *
     * @param 一個Collection集合。
     * @throws 如果參數collection為null的話，將會報異常（NullPointerException）
     */
    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;
        }
    }

③縮至“最簡潔”的容量：把ArrayList的底層elementData數組大小調整為size（size是ArrayList集合中存儲的元素的個數）

那為什么會有這個方法呢？

因為我們在ArrayList中添加元素的時候，當ArrayList容量不足的時候，ArrayList會自動擴容，（調用的是ensureCapacityInternal()方法，這個方法后續會講解。），一般擴充為原來容量的1.5倍，我們可能用不了那么多的空間，所以，有時需要這個來節省空間。

//modCount這個變量從字面意思看，它代表了修改的次數。實際上它就是這個意思。
//它是AbstractList中的 protected修飾的字段。
//我們首先解釋一下它的含義：顧名思義，修改的次數（好像有點廢話了）
//追根溯源還是由于ArrayList是一個線程不安全的類。這個變量主要是用來保證在多線程環境下使用
//迭代器的時候，同時在對集合做修改操作時，同一時刻只能有一個線程修改集合，如果多于一個
//線程進行對集合改變的操作時，就會拋出ConcurrentModificationException。
//所以，這是為線程不安全的ArrayList設計的。
//
//接著判斷一下，如果ArrayList中元素的個數小于底層數組的長度，說明此時需要縮容。
//最后通過一個三位運算符判斷，如果ArrayList中沒有元素，則把底層數組設置為空數組。
//否則的話，就使用數組拷貝把底層數組的空間大小縮為size（元素個數）的大小。
//
  public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

④增加ArrayList實例的容量，如果有需要的話，以確保它至少能容納元素的數量由傳入的參數決定。

//官方的JDK中首先：需要確定一個最小的預期容量（minCapacity）：
//它通過判斷底層數組是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA（也就是說是不是使用了
//默認的構造器，)，如果沒有使用默認的構造器的話，它的最小預期容量是0，如果使用了默認
//構造器，最小預期容量（minCapacity）為默認容量（DEFAULT_CAPACITY：10），
//最后判斷一下，如果參數大于最小預期的話，則需要調用ensureExplicitCapacity()方法
//擴容。該方法講解，請看下面。
   public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    //因為需要進行擴容，也就是ArrayList發生了變化，所以需要modCount++.
    //接著判斷一下，如果我們傳進來的參數（需要擴充的容量）大于底層數組的長度elemntData
    //的時候，就需要擴容了。 擴容見下面的grow（）方法。
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //首先是新建一個變量oldCapacity，把底層數組的長度保存起來，然后通過oldCapacity做
	//移位運算，向右移移位，就變成了oldCapacity的1.5倍了（可能小于1.5倍，后面就當做1.5倍
    //對移位運算不懂的童鞋們可以上網查查移位運算的資料)。
    //接著判斷一下，如果newCapacity（它是底層數組容量的1.5倍）的大小仍然小于我們
    //自定義傳進來的參數minCapacity的大小，就把minCapacity的值賦值給newCapacity。
    //接著再判斷一下如果newCapacity的大小超過了最大數組容量（MAX_ARRAY_SIZE），
    //MAX_ARRAY_SIZE代表了要分配數組的最大大小，如果試圖分配更大的長度時，超出了虛擬機的限制。可能會導致OutOfMemoryError。
    //該值是一個常量，源碼中是：private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //就調用hugeCapacity進行擴容。最后把底層數組的容量擴充進行擴容為newCapacity的容量。
    private void grow(int minCapacity) {
   
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //如果超出MAX_ARRAY_SIZE,會調用該方法分配Integer.MAX_VALUE的空間。
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

⑤求ArrayList的大小。（一目了然的代碼就不解釋了。）

直接返回size即可，因為屬性size代表了ArrayList的大小。

    public int size() {
        return size;
    }

⑥判斷ArrayList是否為空：

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

⑦判斷某一元素在ArrayList中的位置（從前向后遍歷）：

源碼通過兩次for循環遍歷ArrayList，第一次用于判斷當參數是空的時候，判斷其位置，第二次用于不為空的時候，判斷其位置，這兩次循環中，如果找到了就返回元素在集合中的位置，如果沒有找到則返回-1。可以看出，都是判斷位置時都是通過底層數組elementData的遍歷進行判斷。

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（）方法，如果該方法返回大于0，則存在該元素。

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

⑨判斷某一元素在ArrayList中的位置（從后向前遍歷）：

和indexOf（）方法差不多，就不解釋了。（只不過這次是從后向前遍歷）

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

⑩克隆方法。（實現了Cloneable接口）

直接調用超類Object的clone方法，然后強制轉化一下類型，然后把底層數組拷貝一下，切記要將modCount設置為0，最后返回即可。（當拋出不支持克隆的異常的時候，將派出一個系你的內部錯誤的異常。）

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

11：轉化為數組。（無參的方法）

這里調用了Arrays中的方法，不屬于ArrayList的范疇，所以不細剖析內部的實現。后續的Arrays將會講解。

（其實最頂層是調用的本地方法（本地方法是指用native修飾的方法，即是用其他語言實現的邏輯），這里數組拷貝使用的是System.arraycopy（）方法。）

（其實，你看ArrayList的源碼實現的時候，會發現很多涉及數組移動、數組復制的操作都是用System.arraycopy（）處理的。）

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

12:轉化為數組（傳入一個和該方法返回值類型相同的數組）

前半段代碼含義很清晰：首先判斷一下傳進來的數組a的大小是否小于需要轉化為數組的ArrayList的數組元素的個數，如果小于的話，返回原來ArrayList底層存儲元素的數組elementData，并且它的大小設置為ArrayList中元素的個數，且類型為傳進來的類型參數a。（傳進來的參數和返回值類型必須一致）

如果傳進來數組a的帶下不小于ArrayList中元素的個數的話，則先把底層數組elementData中的元素全部復制到a中。

接下來比較奇怪的一點是：如果a的長度大于size的話，則把a[size]設置為空。

我通過代碼測試和查看官方解釋得出如下結論：

• 如果數組a的length大于ArrayList中元素的個數size，則把a[size]置為空，從結果目的是為了區分ArrayList和轉化后的數組的大小以及內容有哪些區別。

• 如果是等于的話，它和小于的結果顯示一樣。都是輸出了轉化后的數組，且元素和元素的個數與ArrayList中元素和元素個數完全一致。

 public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

13：查看底層elementData數組的某個元素：（直接通過數組訪問）

 E elementData(int index) {
        return (E) elementData[index];
    }

14：檢查底層數組是否越界：

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

15：獲取某個位置上的元素：（直接通過數組操作）

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

        return elementData(index);
    }

16：設置某一位置上的元素，并且返回該位置的舊值：（都是很簡單，一目了然，不解釋了）

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

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

17：添加一個元素：（這里和擴容用的是同樣的輔助方法（輔助方法就是指private修飾的方法）。最后一次分析這些輔助方法。）

首先調用ensureCapacityInternal()方法，傳入當前ArrayList中元素的個數+1；

進入該方法后，調用 ensureExplicitCapacity();在該方法的參數中調用calculateCapacity(elementData, minCapacity)進行容量的計算，如果我們的ArrayList是通過默認的構造器創建的話（就是代碼中的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA），則把minCapacity（也就是我們的size+1）和DEFAULT_CAPACITY（默認容量是10）比較，取較大者返回，否則的話，就返回minCapacity，接著調用ensureExplicitCapacity(int minCapacity）方法，如果minCapacity大于底層數組的長度，則需要調用grow(minCapacity)進行擴容，否則的話，add（）方法中的ensureCapacityInternal(size + 1)什么也不做。（其實ensureCapacityInternal(size + 1)方法就是為了判斷數組用不用擴容。）

如果需要擴容的話，則調用grow（）方法：

下面解釋一下grow（）方法：

此時先定義一個變量oldCapacity，先把elementData數組的長度存儲起來，然后定義一個新的變量newCapacity，用來存儲擴容后的容量，即oldCapacity + (oldCapacity >> 1)（大概是oldCapacity）的1.5倍。接著判斷一下，如果新容量小于我們設置的minCapacity的話，就把minCapacity賦值給newCapacity，

接著繼續判斷一下newCapacity是否大于MAX_ARRAY_SIZE，（這個MAX_ARRAY_SIZE代表了所能設置的數組的最大容量，如果超過這個值，可能導致內存溢出的錯誤（OutOfMemoryError），當然啦，如果超過的話，會將數組的容量設置為INTEGER.MAX_VALUE）。

總結：

添加一個元素之前，需要先判斷一下容量（底層elementData數組的大小是否滿足條件），如果容量不足， 足需要擴容，然后擴大后的容量取決于size+1，最后給elementData[size++]賦值就可以了，最后返回true。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
    }
    
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(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);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        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);
    }

18：為進行增加操作的方法添加范圍檢查。

如果index大于size或者小于0，則拋出IndexOutOfBoundsException。

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

19：在指定位置的地方添加新的元素：

先檢查一下參數是否符合要求。

然后和上面通過ensureCapacityInternal(size + 1)判斷是否需要增加容量，如果需要則擴容，如果不需要則什么也不做。

然后進行數組拷貝（其實就是移動底層數組elementData的元素），最后把要添加的元素添加到指定的位置，然后size++（size代表了ArrayList中元素的個數）。

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

20：移出指定位置上的元素：

老規矩，但凡是改變添加或者刪除元素，都需要先檢查參數是否合法，因為此方法需要返回就的值，所以需要先定義一個oldValue來存儲舊的值。

重要的學習點：

在移動元素的時候，仍然選擇進行數組的拷貝。但是，這里涉及到一個數組邊界的問題：我們在計算出要移動的元素的個數后（這里可能有的童鞋看不懂為什么移動的個數是size-index-1，你可以畫個圖一下子就出來了，其實就是因為我們的index指代的是數組的下標，所以index位置處的元素以及它前面的元素的和是index+1，所以剩下的元素就是size-index-1，而剩下的元素，也就是index位置后的所有元素都需要向前移動，所以numMoved=size-index-1），移動的元素的個數大于0，我們下面數組拷貝（其實就是起到了移動元素的功能）才有意義，否則的話直接在elementData[–size]處設置為空就可以了。記住最后需要返回移除了的值。

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; 

        return oldValue;
    }

21：移除具體的元素：

提供兩種方法，一種是應對參數為空的情況，另一種是應對參數不為空的情況。

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

22：快速刪除指定位置上的元素：（這是一個輔助方法）（不提供給用戶使用。）

這個是JDK提供的刪除指定位置上元素的更快的方法。（從它的名字就看出來了。）

它直接跳過范圍檢查，并且不返回值。

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
    }

23：清空ArrayList：

從代碼中看，非常簡單，通過for循環把底層數組中的元素全部置為null，然后把size設置為0就可以了。

  public void clear() {
        modCount++;

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

        size = 0;
    }

24：把一個集合中的所有元素添加到ArrayList中：

首先把Collection參數轉化為一個數組，該toArray（）方法調用了Arrays類的copyOf（）方法，最底層調用的System.arraycopy（）方法。

然后把它的容量加上ArrayList的大小，然后和上面添加元素的方式一樣，繼續判斷一下容量夠不夠。最后進行數組的拷貝，把參數中的所有元素添加到底層數組elementData中，然后把代表ArrayList中元素個數的size重新設置一下。最后如果參數的元素不為空，則返回true，表明把元素添加了進去，如果為空的話，說明沒有添加元素，則返回false。

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

25：在ArrayList的指定位置上添加一個新的集合：

上面的一個方法同樣是添加一個集合到ArrayList中，為什么不需要進行邊界檢查？這里就需要呢？

因為這個方法多傳了一個參數index，它用來指代插入ArrayList中的位置，如果index是一個負值或其他不合法的值時，就無法進行后面的操作，而上面那個方法，默認直接插入ArrayLisr底層數組的后面，所以不需要檢查。

numMoved=size-index;表示除了index位置前面的元素，Index位置上的元素以及index后面的元素都需要移動，如果size-index小于或等于0，則說明添加的位置在ArrayList中所有元素的后面，所以就無需第一個數組拷貝了（System.arraycopy(elementData, index, elementData, index + numNew,numMoved);）只需要進行第二個數組拷貝，通過System.arraycopy(a, 0, elementData, index, numNew);數組拷貝即可，最后返回numNew!=0，和上面的套路一樣，不解釋了。

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

26：移除某一個范圍的元素：

進行修改操作還是得考慮為迭代器服務的modCount。

這個方法是protected修飾的，所以只有它的子類或者同一個包下才可以使用，所以，一般我們也用不到，但還是分析一下吧：

先給個結論吧：它刪除下標從fromIndez到toIndex的元素，但是不刪除下標為toIndex的元素。

首先求出要移動的元素，也就是說，toIndex位置的元素以及它后面的元素都要移動，然后通過System.arraycopy（）把toIndex位置的元素以及它后面的元素移動到了fromIndex的位置上。最后把新的底層數組elementData的對應的原來的底層數組的最后一個位置的元素的后面所有元素都設置為null，然后調整數組的大小。

protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

27：移除集合中包含的所有元素：

首先需要調用Objects類保證參數不為空，然后調用battchRemove（）方法。

在battchRemove方法中，首先把底層數組elementData賦值給一個Object數組。接著通過遍歷底層數組elementData和傳進來的參數c，判斷一下如果集合中不包含依次遍歷的底層數組的元素，首先通過遍歷底層數組elementData，判斷參數集合c是否包含遍歷過程中的每個元素，如果集合c不包含遍歷的元素時，就把底層數組的該元素賦值給底層數組的前面的一個，如果包含，則什么也不做，最后底層數組變成了前面不包

含集合c中含有的元素。后面就是用來通過判斷進行修改底層數組，最后返回即可。

這里的代碼比較細，童鞋們可以自行debug一下， 學習起來就容易很多了，下面給的邏輯超清晰。

public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

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

28：只保留參數中的元素和底層數組elementData中相同的元素，剩下的全部刪除。

這個實現和上面的removeAll（）差不多，調用的是同一個輔助方法。

 public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

29：把ArrayList的狀態保存為流。（序列化）writeObject(java.io.ObjectOutputStream s)。

30：從流中重新構建為ArrayList。（反序列化）readObject(java.io.ObjectInputStream s)。

31：返回List的專有迭代器（這個方法有個參數：用來表示從哪個位置迭代）：

其中ListItr是ArrayList中的內部類。

ArrayList共有4個內部類，分別是：Itr、ListItr、SubList、ArrayListSpliterator。

public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

32：返回List的專有迭代器（這個方法沒有參數，直接從開始位置進行迭代。）

public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

33：普通迭代器：

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

34：Itr內部類的分析：（代碼中解釋）

• cursor：代表了返回的下一個元素的下標。

• lastRet：代表了返回最后一個元素的下標，如果沒有最后一個元素，則返回-1。

• expectedModCount：期望的ArrayList修改的次數。

private class Itr implements Iterator<E> {
        int cursor;       
        int lastRet = -1; 
        int expectedModCount = modCount;

        Itr() {}
// 如果下一個元素的下標和底層數組elementData的數組大小不相等，則返回true。
        public boolean hasNext() {
            return cursor != size;
        }
//首先調用checkForComodification()方法，檢查一下modCount是否等于內部類定義的expectedModCount，如果不等于，則拋出ConcurrentModificationException。
//那個方法的作用是什么呢？
//由于ArrayList自身是線程不安全的，如果當前線程使用迭代器迭代ArrayList的時候，其他線程如果調用改變ArrayList的方法時候，而這些方法中都會修改modCount這個值，而這個值是在AbstractList中定義的protected變量，所以這里驗證如果expectedModCount不等于modeCount的時候，說明有其他線程在修改ArrayList，所以該方法是用來保證帶迭代的時候其他線程不能修改modeCount的值。
然后定義一個變量i保存下一個元素的下標，如果i>size，則拋出NoSuchElementException異常。
接著定義一個Object數組的引用指向底層數組，接著判斷一下如果i>size就拋出異常，接著把讓cursor自增，并通過elementData返回當前元素。

        @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];
        }
//在remove方法中，首先判斷lasrRest是否小于0，如果小于0，表面它沒有進行next操作，就
//會拋出IllegalStateException。因此我們在迭代的時候，必須保證每次都要先進行next（）
//方法，然后進行刪除remove（）操作。
//接著繼續檢查一下是否有其他線程修改了ArrayList。
//接著再try語句中刪除lastRet位置上的元素。接著把lastRet賦值給cursor，以便下一個next()方法使用，然后expectedModCount = modCount。
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } 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();
        }
    }

35：對ArrayList中的元素進行排序。

需要傳入一個比較器，以實現自定義排序規則。

因為ArrayList底層是用數組實現的，所以ArrayList就直接使用了Arrays.sort（）方法進行了ArrayList的排序。

@Override
    @SuppressWarnings("unchecked")
    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++;
    }

到此，相信大家對“基于ArrayList源碼分析”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！