ArrayList源碼中的兩個值得注意的問題

1、“拖泥帶水”的删除

測試代碼：

package com.demo;
import java.util.ArrayList;
public class TestArrayList {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<String> arylist = new ArrayList<String>();
        arylist.add("aa");
        arylist.add("bb");
        arylist.add("bb");
        arylist.add("cc");
//        arylist.add("aa");
//        arylist.add("bb");
//        arylist.add("cc");
//        arylist.add("bb");
        String target = "bb";
        for (int i = 0; i < arylist.size(); i++) {
            if (arylist.get(i).equals(target)) {
                arylist.remove(i);
            }
        }
        for(String value:arylist){
            System.out.println(value);
        }
    }
}      

這段代碼的本意在于删除動态數組arylist中元素等于target的元素，通過周遊數組的每一項，當equals判定相等就删除之。如果數組中的所有元素唯一，不會存在任何問題，對應的元素得到正确的删除；如果數組中元素有重複，那麼你可能理所當然地認為所有重複元素也應該全部被删除，因為似乎周遊到了每項元素。但實際結果有可能不是你想的樣子。運作上述代碼得到輸出：

aa
bb
cc      

有一個元素"bb"應該被删除但是未被删除。

但如果在調整一下動态數組中重複元素“bb”的位置（如注釋的代碼）為：{"aa","bb","cc","bb"}，其結果是兩個“bb”全部被删除。

這裡的重點在于remove()方法的實作。檢視其源碼：

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

從以上删除的處理邏輯可以看出，删除操作主要是調用了System.arraycopy()方法，在System類中該方法的定義為：

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);      

該方法的功能是将源數組src從srcPos位置開始，複制數量為length的元素到目标數組dest中，其中目标數組從destPos位置開始往後填充。

由此可知，remove方法中删除操作的處理辦法是将elementData數組從index+1位置開始其後的numMoved各元素原地複制到index處。簡單點說就是将index+1位置開始的元素依次往前挪動一個位置，因為index位置的元素反正要被删除，就直接覆寫它，最後在處理elementData最末尾無用的元素和更新size。

這樣處理的問題在于，如果arylist中位置為i和i+1的元素重複且剛好是需要删除的元素，那麼由于一輪删除之後，第二個元素占據第一個元素的位置，但是i++自增了，第二個元素被跳過了，未被周遊到，删除實際上是不完整的。實際上隻要待删除元素存在相鄰的情況都會出現這種“拖泥帶水”不完整的删除。

remove(Object o)、fastRemove(int index)都是基于類似的實作方式。

正确的寫法可以在必要的時候手動修正計數器i的值，但是這種實作實際上不是很優雅：

for (int i = 0; i < arylist.size(); i++) {
            if (arylist.get(i).equals(target)) {
                arylist.remove(i);
                i--;
            }
        }      

更好的實作是反向周遊删除：

for (int i = arylist.size()-1; i >= 0; i--) {
            if (arylist.get(i).equals(target)) {
                arylist.remove(i);
            }
        }      

2、不一樣的初始化

ArrayList是基于對象數組實作的。

在版本JDK1.8中

其中幾個常用的成員變量有：

預設的初始化容量：DEFAULT_CAPACITY 

空的對象數組變量兩個：EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA

真正存儲元素的對象數組變量：elementData

大小：size

/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData; // non-private to simplify nested class access

    private int size;      

源碼的實作者特地用兩個空的對象數組來差別有參和無參執行個體化，以滿足不同條件下的使用。

對應的構造器如下：

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

是以，通過如下兩種方式執行個體化後，對象數組實際上都是一個空數組，但是是不同的空數組。

ArrayList<String> list = new ArrayList<String>(0);
        ArrayList<String> list1 = new ArrayList<String>();      

第一種執行個體化得到的空數組是EMPTY_ELEMENTDATA，第二種執行個體化得到的空數組是DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

但是随後的第一次add元素後就會有所差別。

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

add()方法調用ensureCapacityInternal()方法。

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

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

ensureCapacityInternal()方法中特地有差別的對待了兩個同為空的對象數組：

如果對象數組是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那麼第一次add元素時配置設定的容量直接從10起步，随後一直到size為10為止，add元素不會在調用grow()方法。

如果對象數組是EMPTY_ELEMENTDATA，那麼第一次add元素時配置設定的容量是1，并且随後的幾次add都會比較頻繁的調用grow()，這樣的增幅視乎太小了，但是僅限于前面幾次add操作，到後面階段于第一種方式基本保持一直的步調。

為何要在這裡對如此細微的細節給予差别對待？我其實也不是很懂，但是大體上，猜測作者是想傳遞這樣一個實作意圖：

如果程式員用ArrayList<String> list = new ArrayList<String>(0);來執行個體化，那麼他應該是很明确的需要空的動态數組而不需要存儲任何元素，即使需要存儲元素，也是一兩個很少量的元素，不會頻繁的add，是以不應該在第一次add操作時配置設定10的容量，很可能造成浪費。

如果程式員 ArrayList<String> list1 = new ArrayList<String>();來執行個體化，那麼他是需要這個動态數組來存放元素的，是以應該在第一次add是為其配置設定合适的容量10。

完結~~~