摘要：實現(xiàn)了接口，所以包含的基本方法新增，刪除，插入等都實現(xiàn)了。線程安全問題在多線程情況下有線程進行修改時，是線程不安全的。線程安全性問題，取決于如何應用。反映的是當前數(shù)組中存了多少數(shù)據(jù)，而則反映的是內部數(shù)組的容量。

ArrayList 是一個可擴容數(shù)組Resizable-array,它實現(xiàn)了List接口的所有方法。

從對ArrayList的簡單描述中我們可以得出幾點

ArrayList 是數(shù)組，但不同于一般數(shù)組，可擴容，而一般數(shù)組容量固定。
ArrayList 實現(xiàn)了List接口，所以List包含的基本方法（新增，刪除，插入等）ArrayList都實現(xiàn)了。

ArrayList 內部實現(xiàn)是通過一個對象數(shù)組
transient Object[] elementData

ArrayList add() 方法實質上是實現(xiàn)了在數(shù)組的末尾添加一個元素 elementData[size++] = el 所以執(zhí)行的時間復雜度是固定的O(1)，添加n個元素為O(n)

因為本質上是對數(shù)組進行操作，當在數(shù)組中插入、刪除數(shù)據(jù)時，需要先對數(shù)組進行移位操作，插入時需要將插入點以后的數(shù)據(jù)全部后移，而刪除操作則需要將刪除節(jié)點后的數(shù)據(jù)全部前移,操作時間復雜度為O(n)。

ArrayList 在多線程情況下有線程進行修改時，是線程不安全的。線程安全性問題，取決于如何應用。List list = Collections.synchronizedList(new ArrayList(...))可以獲取線程安全的ArrayList

ArrayList 有其自動擴容機制也可以在預知要處理數(shù)據(jù)大小時手動擴容

1.自動擴容
ArrayList 在新增元素時（add ,addAll操作）會先檢測當前內部數(shù)組elementData[]的容量是否足夠添加新元素，如果不足則擴容，ArrayList最大容量為Integer.MAX_VALUE，自動擴容調用的流程如下
public boolean add(E e) {
    // 自動擴容，并記錄元素修改數(shù)量 ，元素修改數(shù)量主要是用于并發(fā)修改錯誤
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}

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

// 返回一個數(shù)組大小的值 minCapacity 和默認的 DEFAULT_CAPACITY 中較大的那個
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果是空數(shù)組 通過new ArrayList()創(chuàng)建
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      // 默認大小是DEFAULT_CAPACITY =  10
      return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}



實際擴充容量的片段
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 將上面方法返回的大小和當前 elementData 大小進行比較，判斷是否需要擴容
    if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}
private void grow(int minCapacity) { // 具體擴容代碼
    int oldCapacity = elementData.length;
    // 擴容后容量總是擴容前的大約1.5倍左右增量0.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
    // 如果擴容后超出了最大個數(shù)限制 則由hugeCapacity()來處理
    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;
}

2.手動擴容或者指定初始容量
ArrayList 手動擴容主要是調用ensureCapacity(int minCapacity)方法，除此之外還能在創(chuàng)建ArrayList時指定初始容量
創(chuàng)建時直接指定容量new ArrayList<>(initialCapacity)及其實現(xiàn)
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 創(chuàng)建指定容量的一個數(shù)組
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
通過ensureCapacity(int minCapacity)方法在處理過程中擴容，這種情況一般發(fā)生在處理過程中發(fā)現(xiàn)初始容量不能滿足當前數(shù)據(jù)需求，而又為了避免自動擴容時的資源浪費，因為每次自動擴容時都會進行數(shù)組復制。
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0: DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}
3.最后看看擴容時的數(shù)組復制,數(shù)組復制是通過Arrays.copyOf(origin,newLenght)方法來實現(xiàn)的
public static  T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
// 具體復制代碼
public static  T[] copyOf(U[] original, int newLength, Class newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    // 將舊數(shù)組中的數(shù)據(jù)復制到新數(shù)組
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

ArrayList在方法中傳遞時，傳遞的是對象的引用，當某一個方法修改了ArrayList時，該修改會反映到引用該ArrayList的所有地方，不管傳遞多少次，都引用的時同一個內存區(qū)域的數(shù)據(jù)，所以如果要實現(xiàn)在傳遞時確保內容不變，應該克隆(用ArrayList的clone())方法一份進行傳遞(需要注意深淺克隆問題深克隆可以使用Collections.copy(dest,src)方法)，具體該怎么弄，還是要視需求而定。

如果要找他們之間的關系可能就是size=元素數(shù)量 <= capacity = 容量大小吧。size 反映的是當前數(shù)組中存了多少數(shù)據(jù)，而capacity則反映的是ArrayList內部數(shù)組的容量。不能習慣性認為capacity 既是 size

ArrayList和LinkedList為什么會存在選擇性問題，因為他們在get、add、remove時性能是不一樣的。
ArrayList是內部實現(xiàn)是數(shù)組，在隨機存取時時間復雜度是O(1)知道索引就能立馬取值，而其插入和刪除操作就相對比較麻煩，需要進行移位操作線性的時間復雜度。
LinkedList 是雙向連表Doubly-linked ，在插入和刪除時時間復雜度都是O(1)，但索引（取索引位上的值）時需要從表頭或者表尾進行遍歷操作。
所以選用哪一個，完全取決于你要進行的操作是以隨機存取為主還是增刪元素較多為主。

transient關鍵字的作用是阻止對象序列化，那么為什么要防止elementData序列化呢?那是因為elementData是一個數(shù)組，并且并不是數(shù)組中每一個位置上都保存有值，容量10000的數(shù)組中可能只保存了10個對象。所以不能對其進行序列化，在ArrayList中重寫了writeObject 、readObject 方法來對ArrayList進行序列化控制。

RandomAccess接口是一個標記接口并沒有定義任何方法，ArrayList 實現(xiàn)它是標記ArrayList支持快速隨機訪問這一特性！

并發(fā)修改異常ConcurrentModificationException通常出現(xiàn)在對一個List進行遍歷時，對正在遍歷的數(shù)組進行了修改性操作（修改性操作：改變大小（size=數(shù)量）的操作，而不是指具體值）(add,remove,clear等)時便會拋出這個異常，在ArrayList內部有一個protected transient int modCount = 0的變量用于記錄對ArrayList的修改，比如add方法代碼
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
可以看到在調用add方法時會執(zhí)行modCount++操作以此標記最新修改的數(shù)量modCount
而在遍歷時比如forEach先看代碼
public void forEach(Consumer action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}
可以看到for循環(huán)中一個明確的條件是modCount == expectedModCount 每次遍歷都會檢測該條件是否成立，而在進入該段代碼之前先用final int expectedModCount = modCount;來保存代碼執(zhí)行之前的修改數(shù)量，當進入遍歷后，有了更改操作，就會使得expectedModCount 和modCount不相等此時便會拋出ConcurrentModificationException異常，對于其他的修改操作，原理都是類似的。