Java集合（1）：ArrayList深度決議

一、ArrayList 的概述與特點

ArrayList就是動態陣列，是陣列Array的復雜版本，它具有以下特點：
（1）是一個動態陣列，支持動態擴容
（2）有序存盤，存盤的元素可重復，并支持null元素的存盤
（3）底層為陣列，查找快，增刪慢
（4）不支持同步，執行緒不安全

二、ArrayList 的繼承體系

查看原始碼，發現ArrayList繼承AbstractList抽象父類，實作了List、RandomAccess、Cloneable、Serializable介面，
其中：
（1）List介面：定義了List的一些操作規范，至于為什么繼承了AbstractList還要再實作List介面的問題，網上有兩種說法：一種是代碼規范，方便直接看出是個List集合；二是為了是實作代理時，獲得的介面中有List介面，
（2）RandomAccess介面：是一個空介面，代表可隨機訪問，實作了此介面的集合使用for回圈遍歷速度更快，而沒有實作此介面的集合使用iterator迭代器遍歷速度更快，
（3）Cloneable介面：空介面，實作此介面是為了可以呼叫clone()方法，ArrayList的clone()方法屬于淺克隆，
（4）Serializable介面：空介面，代表可序列化

三、重要屬性

（1）transient Object[] elementData;這是ArrayList的底層，是一個object陣列，由transient修飾，代表此陣列不參與序列化，而是使用另外的序列化方式（使用writeObject方法進行序列化，只序列化有值的位置，其他未賦值的位置不進行序列化，節省空間），
（2）private int size;指集合包含的元素數量，注意與elementData.length（集合容量）的區別，比如當前集合容量為10，只存盤了6個元素，則size為6，elementData.length為10，

四、構造方法

查看ArrayList原始碼所知，ArrayList有三個構造方法，一種為創建指定容量的集合，一種為無參的構造方法，最后一種為構造一個包含指定集合的構造方法，代碼都比較簡單，重點看一下無參的構造方法：

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

DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一個空的集合，注意，雖然在JDK1.8的注釋中所說無參構造器創建的是一個初始容量為10的空集合，但是查看代碼可知，剛開始創建的時候只是一個空集合，而容量變為10體現在后續的操作中（下文有介紹），

五、增刪改查

（1）add 方法

add方法有兩個，分別public boolean add(E e)和public void add(int index, E element)，第一個是在集合元素的最后添加一個元素，第二個方法為在指定位置添加元素，代碼如下：

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

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

由以上代碼，我們可以發現兩種add方法都呼叫了ensureCapacityInternal(size + 1)方法，此方法目的是為了確定是否擴容，第一個add方法比較簡單，先判讀是否擴容，然后再讓最后一個元素的下一個等于需要添加的元素，重點看一下第二個add方法：

a.首先檢查索引是否越界，如果越界則拋例外，呼叫的是rangeCheckForAdd(index);：

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

b.然后檢測是否需要擴容，注意，擴容原理是比較重要的，呼叫的是ensureCapacityInternal(size + 1);注意，這里傳入的引數minCapacity為陣列存盤的元素+1，

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

這里首先呼叫的是calculateCapacity(elementData, minCapacity)，用來計算容量：

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

代碼的流程是如果現在的集合是空的，那么讓它的容量等于DEFAULT_CAPACITY（值為10），否則回傳minCapacity（值為size+1），

然后呼叫的ensureExplicitCapacity(int minCapacity)方法，代碼如下：

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

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

其中modCount代表修改次數，是用在迭代器里保證遍歷程序中集合不被其他執行緒修改，后面的代碼很好理解，如果size+1（已經存盤的元素+要存盤的元素）大于集合容量，則呼叫擴容方法grow(minCapacity)，

擴容方法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);
    }

舊的容量等于elementData.length，新的容量等于oldCapacity + (oldCapacity >> 1)，這個地方新的容量等于舊的容量的1.5倍，從這里可以看出，動態擴容每次擴容1.5倍，

如果新容量小于size+1，回傳size+1，這里適用的情況是第一次添加時elementData.length=0，那么舊容量和計算出的新容量都為0，而minCapacity 為之前得出的10，所以把10賦值給新容量，

然后則是對新容量如果超過陣列最大長度的處理，最后呼叫了Arrays.copyOf(elementData, newCapacity)進行陣列拷貝，跟蹤代碼，發現陣列拷貝最終呼叫的是System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法，是一個native方法，

講完了動態擴容的ensureCapacityInternal(size + 1)代碼，后面的比較簡單了，就是陣列的復制，要添加元素的賦值，還有讓size加一，

（2）remove 方法
由于洗掉不需要涉及擴容，所以代碼比較簡單，自行閱讀即可，ArrayList提供了三種洗掉元素的方法，分別為remove(int index)、remove(Object o)、fastRemove(int index)，即洗掉指定位置的元素、洗掉第一次出現的指定元素、跳過邊界檢查并且不回傳洗掉的值的快速洗掉方法，
（2）set 和get方法
改查方法只需要檢查是否索引越界，然后進行改查操作即可，代碼也非常簡單，不再贅述，

六、其他重要方法

（1）ensureCapacity(int minCapacity)
看這個方法的名字就是一個擴容的方法，我們從上文可知，每次進行擴容時都要進行一次陣列復制，所以頻繁的擴容會導致性能的浪費，所以最好的辦法是在創建陣列后就用此方法設定一個容量以減少擴容的次數，

public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

（2）trimToSize()
陣列在復制完成后，它的size極有可能是小于它的容量的，為了減少空間的浪費，可以呼叫此方法來清空后面沒有賦值的容量，

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

（3）clear()
如果一個ArrayList不再使用，可以呼叫clear()方法，讓每個元素都為null，方便JVM回收，

public void clear() {
        modCount++;

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

        size = 0;
    }

（4）執行緒安全問題
由于ArrayList在多執行緒環境下非安全的，多個執行緒同時操作時會產生并發問題，解決辦法：
a.使用Collections工具類的方法：

 List list = Collections.synchronizedList(new ArrayList(...)); 

b.使用執行緒安全類Vector