## ArrayList [TOC] ### 1. 概覽 實現了 RandomAccess 接口，因此支持隨機訪問，這是理所當然的，因為 ArrayList 是基于數組實現的。 ```java public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable ``` 數組的默認大小為 10。 ```java private static final int DEFAULT_CAPACITY = 10; ```  ### 2. 序列化 基于數組實現，保存元素的數組使用 transient 修飾，該關鍵字聲明數組默認不會被序列化。ArrayList 具有動態擴容特性，因此保存元素的數組不一定都會被使用，那么就沒必要全部進行序列化。ArrayList 重寫了 writeObject() 和 readObject() 來控制只序列化數組中有元素填充那部分內容。 ```java transient Object[] elementData; // non-private to simplify nested class access ``` ### 3. 擴容 添加元素時使用 ensureCapacityInternal() 方法來保證容量足夠，如果不夠時，需要使用 grow() 方法進行擴容，新容量的大小為 `oldCapacity + (oldCapacity >> 1)`，也就是舊容量的 1.5 倍。 擴容操作需要調用 `Arrays.copyOf()` 把原數組整個復制到新數組中，這個操作代價很高，因此最好在創建 ArrayList 對象時就指定大概的容量大小，減少擴容操作的次數。 ```java // JDK 1.8 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } // 判斷數組是否越界 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); // 1.5倍 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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } ``` ### 4. 刪除元素  需要調用 System.arraycopy() 將 index+1 后面的元素都復制到 index 位置上。 ```java public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); //復制的個數 int numMoved = size - index - 1;//刪除23，則后面的元素的位置index 7 8 9，所以需要3個 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved);//numMoved代表需要復制幾個！ elementData[--size] = null; // clear to let GC do its work return oldValue; } ``` ### 5. Fail-Fast **開始之前我們想講講，什么是 fail-fast 機制?** fail-fast 機制在遍歷一個集合時，當集合結構被修改，會拋出 Concurrent Modification Exception。 fail-fast 會在以下兩種情況下拋出 Concurrent Modification Exception （1）單線程環境 - 集合被創建后，在遍歷它的過程中修改了結構。 - 注意 remove() 方法會讓 expectModcount 和 modcount 相等，所以是不會拋出這個異常。 （2）多線程環境 - 當一個線程在遍歷這個集合，而另一個線程對這個集合的結構進行了修改。 modCount 用來記錄 ArrayList 結構發生變化的次數。結構發生變化是指**添加**或者**刪除**至少一個元素的所有操作，或者是調整內部數組的大小，僅僅只是設置元素的值不算結構發生變化。 在進行序列化或者迭代等操作時，需要比較操作前后 modCount 是否改變，如果改變了需要拋出 Concurrent Modification Exception。 ```java 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(); } } ```