深入學習Java集合之ArrayList的實作原理

ArrayList 是List 接口的可變數組的實作,底層就是一個數組, 是以按序查找快, 亂序插入、删除因為涉及到後面元素移位是以性能慢。實作了所有可選清單操作，并允許包括 null 在内的所有元素。除了實作 List 接口外，此類還提供一些方法來操作内部用來存儲清單的數組的大小。

每個ArrayList 執行個體都有一個容量，該容量是指用來存儲清單元素的數組的大小。它總是至少等于清單的大小。随着向ArrayList 中不斷添加元素，其容量也自動增長。

自動增長會帶來資料向新數組

的重新拷貝，是以，如果可預知資料量的多少，可在構造ArrayList 時指定其容量。在添加大量元素前，應用程式也可以使用

ensureCapacity

操作來增加ArrayList執行個體的容量，這可以減少遞增式再配置設定的數量。

注意，此實作不是同步的。如果多個線程同時通路一個ArrayList 執行個體，而其中至少一個線程從結構上修改了清單，那麼它必須保持外部同步。

【1】ArrayList 的實作

對于ArrayList 而言，它實作List 接口、

底層使用數組

儲存所有元素。其操作基本上是對數組的操作，下面我們來分析ArrayList 的源代碼。

① 底層使用數組實作

//預設初始化容量，每次擴容1.5倍--new=1.5*old
private static final int DEFAULT_CAPACITY = 10;

//用于空執行個體的共享空數組執行個體
private static final Object[] EMPTY_ELEMENTDATA = {};

//共享空數組執行個體，用于預設大小的空執行個體。
//與EMPTY_ELEMENTDATA 區分開，以便了解添加第一個元素時需要擴容多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//存儲ArrayList的elements
transient Object[] elementData;

//ArrayList的size--包含的元素個數
private int size;

//數組配置設定最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

② 構造方法

ArrayList 提供了三種方式的構造器，可以構造一個預設初始容量為10 的空清單、構造一個指定初始容量的空清單以及構造一個包含指定collection 的元素的清單，這些元素按照該collection 的疊代器傳回它們的順序排列的。

//構造一個預設初始容量10的空清單
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
//構造一個指定初始容量的空清單
    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 的元素的清單，這些元素按照該collection 的疊代器傳回它們的順序排列
    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 提供了

set(int index, E element)、add(E e)、add(int index, E element)、 addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)

這些添加元素的方法。

3.1 set(int index, E element)：

用指定的元素替代此清單中指定位置上的元素，并傳回以前位于該位置上的元素。

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

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

rangeCheck(index)：

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

檢查給定索引是否在範圍内。如果不是，則抛出适當的運作時異常。此方法不檢查索引是否為負：它總是在數組通路之前立即使用，如果索引為負，則會抛出ArrayIndexOutOfBoundsException。

3.2 add(E e)

将指定的元素添加到此清單的尾部，其中add方法内部的ensureCapacityInternal(size + 1)方法會使modCount++，這與failFast機制有關。

public boolean add(E e) {
     // Increments modCount!!
    ensureCapacityInternal(size + 1); 
    //這裡的size指的是清單中包含的元素個數
     elementData[size++] = e;
     return true;
 }

ensureCapacityInternal(size + 1)：

private void ensureCapacityInternal(int minCapacity) {
   //如果底層資料為DEFAULTCAPACITY_EMPTY_ELEMENTDATA
   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
   //将minCapacity 指派為DEFAULT_CAPACITY和minCapacity中的大數
         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
     }
     ensureExplicitCapacity(minCapacity);
 }

ensureExplicitCapacity(minCapacity)：

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

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

将modCount++，并判斷底層資料的length與minCapacity大小，若

elementData.length<minCapacity

,需要擴容。

grow(int minCapacity)：

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;

        //newCapacity =1.5*oldCapacity 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        //newCapacity 與minCapacity 比較
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            //newCapacity 與MAX_ARRAY_SIZE 比較
        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);
        //Arrays.copyOf(elementData, newCapacity);将會使用newCapacity作為length建立一個
        //新數組，将elementData中元素拷貝過去，并将新數組指派給elementData 
    }

hugeCapacity(int minCapacity) ：

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
            //如果minCapacity大于MAX_ARRAY_SIZE，則取  Integer.MAX_VALUE；
            //否則取MAX_ARRAY_SIZE
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :MAX_ARRAY_SIZE;

3.3 add(int index, E element)

将指定的元素插入此清單中的指定位置。如果目前位置有元素，則向右移動目前位于該位置的元素以及所有後續元素（将其索引加1）

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

        // Increments modCount!! 這個與上面一緻
        ensureCapacityInternal(size + 1);  
        //數組拷貝，移動index及後續索引位置--index都+1
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
          //在原index位置處放上将要添加的元素
        elementData[index] = element;
        //将元素個數+1
        size++;
    }

rangeCheckForAdd(int index)-檢查索引：

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

3.4 addAll(Collection<? extends E> c)

按照指定collection 的疊代器所傳回的元素順序，将該collection 中的所有元素添加到此清單的尾部。

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        //如果數組length不夠，則将會擴容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //數組拷貝
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

3.5 addAll(int index, Collection<? extends E> c)

從指定的位置開始，将指定collection 中的所有元素插入到此清單中。

public boolean addAll(int index, Collection<? extends E> c) {
//索引檢查
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        //需要拷貝元素的個數
        int numNew = a.length;
        //數組容量檢查，如果數組length不夠，則擴容
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        //判斷是否插入中間，如果是則“先騰空間--将元素往後移動numNew個機關”
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        //将a中的元素從index=0開始拷貝到elementData中 index開始的位置
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

④ 讀取

傳回此清單中指定位置上的元素

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

        return elementData(index);
    }

⑤ 删除

ArrayList 提供了根據下标或者指定對象等幾種方式的删除功能。

5.1 remove(int index)

移除此清單中指定位置上的元素

public E remove(int index) {
//檢查索引
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
 //判斷是移除中間還是末尾及以外的元素，如果是中間則進行數組拷貝--往前移動一個index機關
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
          //将原先清單末尾處元素指派為null
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

5.2 remove(Object o)

移除此清單中首次出現的指定元素（如果存在）。這是因為ArrayList 中允許存放重複的元素。remove(Object o)是基于 fastRemove(index)進行元素移除的。

public boolean remove(Object o) {
 //首先判斷是否為null
        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;
    }

fastRemove(index)：

私有移除方法，與remove(int index)方法的差別是fastRemove(index)跳過邊界檢查且不傳回移除的值。

private void fastRemove(int index) {
    //修改 modCount
        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
    }

5.3 removeAll(Collection<?> c)

從清單中移除指定集合裡面的元素，基于batchRemove(c, false)方法實作。

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

batchRemove(Collection<?> c, boolean complement)

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++)
            //判斷Collection是否包含elementData[r]，如果包含則進行下一輪判斷；
            //否則将 r 位置元素 指派給 w ，并将w+1;這個過程中w <= 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
                //将w及以後的位置指派為null
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

注意：從數組中移除元素的操作，也會導緻被移除的元素以後的所有元素的向左移動一個位置。

⑥ trimToSize

ArrayList 還給我們提供了将底層數組的容量調整為目前清單儲存的實際元素的大小的功能。它可以通過trimToSize 方法來實作。代碼如下：

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

注意：從數組中移除元素的操作，也會導緻被移除的元素以後的所有元素的向左移動一個位置。

【2】Fail-Fast 機制

ArrayList 也采用了快速失敗的機制，通過記錄modCount 參數來實作。在面對并發的修改時，疊代器很快就會完全失敗，而不是冒着在将來某個不确定時間發生任意不确定行為的風險。

深入學習Java集合之ArrayList的實作原理

【1】ArrayList 的實作

【2】Fail-Fast 機制

繼續閱讀

資料結構之數組資料結構之數組

ACdream 1162 胖子教你線段樹

POJ 3139 Balancing the Scale

五（五）、構造器 & JavaBean &this

iOS開發Tips3:循環的性能

1275.找出井字棋的獲勝者Java

CodeForces 343D Water Tree

5、繼承與派生3-類型相容規則

【React】1020- React useEffect 使用指南

CodeChef PRIMEDST Prime Distance On Tree

力扣每日一練之數組下篇Day3

python3-基礎篇-01-變量

HDU 5719 Arrange

HDU 4609 3-idiots

HDU 1402 A * B Problem Plus

數組和類數組