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

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

從對(duì)ArrayList的簡(jiǎn)單描述中我們可以得出幾點(diǎn)

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

ArrayList 內(nèi)部實(shí)現(xiàn)是通過(guò)一個(gè)對(duì)象數(shù)組
transient Object[] elementData

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

因?yàn)楸举|(zhì)上是對(duì)數(shù)組進(jìn)行操作，當(dāng)在數(shù)組中插入、刪除數(shù)據(jù)時(shí)，需要先對(duì)數(shù)組進(jìn)行移位操作，插入時(shí)需要將插入點(diǎn)以后的數(shù)據(jù)全部后移，而刪除操作則需要將刪除節(jié)點(diǎn)后的數(shù)據(jù)全部前移,操作時(shí)間復(fù)雜度為O(n)。

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

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

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

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

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



實(shí)際擴(kuò)充容量的片段
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 將上面方法返回的大小和當(dāng)前 elementData 大小進(jìn)行比較，判斷是否需要擴(kuò)容
    if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}
private void grow(int minCapacity) { // 具體擴(kuò)容代碼
    int oldCapacity = elementData.length;
    // 擴(kuò)容后容量總是擴(kuò)容前的大約1.5倍左右增量0.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
    // 如果擴(kuò)容后超出了最大個(gè)數(shù)限制 則由hugeCapacity()來(lái)處理
    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.手動(dòng)擴(kuò)容或者指定初始容量
ArrayList 手動(dòng)擴(kuò)容主要是調(diào)用ensureCapacity(int minCapacity)方法，除此之外還能在創(chuàng)建ArrayList時(shí)指定初始容量
創(chuàng)建時(shí)直接指定容量new ArrayList<>(initialCapacity)及其實(shí)現(xiàn)
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 創(chuàng)建指定容量的一個(gè)數(shù)組
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
通過(guò)ensureCapacity(int minCapacity)方法在處理過(guò)程中擴(kuò)容，這種情況一般發(fā)生在處理過(guò)程中發(fā)現(xiàn)初始容量不能滿(mǎn)足當(dāng)前數(shù)據(jù)需求，而又為了避免自動(dòng)擴(kuò)容時(shí)的資源浪費(fèi)，因?yàn)槊看巫詣?dòng)擴(kuò)容時(shí)都會(huì)進(jìn)行數(shù)組復(fù)制。
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0: DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}
3.最后看看擴(kuò)容時(shí)的數(shù)組復(fù)制,數(shù)組復(fù)制是通過(guò)Arrays.copyOf(origin,newLenght)方法來(lái)實(shí)現(xiàn)的
public static  T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
// 具體復(fù)制代碼
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ù)復(fù)制到新數(shù)組
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

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

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

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

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

RandomAccess接口是一個(gè)標(biāo)記接口并沒(méi)有定義任何方法，ArrayList 實(shí)現(xiàn)它是標(biāo)記ArrayList支持快速隨機(jī)訪問(wèn)這一特性！

并發(fā)修改異常ConcurrentModificationException通常出現(xiàn)在對(duì)一個(gè)List進(jìn)行遍歷時(shí)，對(duì)正在遍歷的數(shù)組進(jìn)行了修改性操作（修改性操作：改變大?。╯ize=數(shù)量）的操作，而不是指具體值）(add,remove,clear等)時(shí)便會(huì)拋出這個(gè)異常，在ArrayList內(nèi)部有一個(gè)protected transient int modCount = 0的變量用于記錄對(duì)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);
}
可以看到在調(diào)用add方法時(shí)會(huì)執(zhí)行modCount++操作以此標(biāo)記最新修改的數(shù)量modCount
而在遍歷時(shí)比如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)中一個(gè)明確的條件是modCount == expectedModCount 每次遍歷都會(huì)檢測(cè)該條件是否成立，而在進(jìn)入該段代碼之前先用final int expectedModCount = modCount;來(lái)保存代碼執(zhí)行之前的修改數(shù)量，當(dāng)進(jìn)入遍歷后，有了更改操作，就會(huì)使得expectedModCount 和modCount不相等此時(shí)便會(huì)拋出ConcurrentModificationException異常，對(duì)于其他的修改操作，原理都是類(lèi)似的。