[TOC]

一、 頂部注釋分析

1.1 首句定義

• Resizable-array implementation of the List interface：List 接口的大小可變數(shù)組的實現(xiàn)

1.2 從注釋中得到的結(jié)論

• 底層：ArrayList 是 List 接口的大小可變數(shù)組的實現(xiàn)，即 implements List<E>
• 是否允許null：ArrayList 允許null 元素
• 時間復雜度：size、isEmpty、get、set、iterator 和listIterator方法都以固定時間運行，時間復雜度為O(1)；而 add 和 remove 方法需要 O(n) 時間
• 容量：ArrayList 的容量可以自動增長
• 是否同步：ArrayList 不是同步的，即線程不安全
• 迭代器：ArrayList 的 iterator 和 listIterator 方法返回的迭代器是 fail-fast 的，若修改會拋出 ConcurrentModificationException 異常

二、源碼分析

2.1 定義

public class ArrayList<E> extends AbstractList<E> 
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

• ArrayList<E>：說明支持泛型
• extends AbstractList<E> ：繼承自 AbstractList
• implements List<E>：實現(xiàn)了List接口
• implements RandomAccess：支持快速（通常是固定時間）隨機訪問。此接口的主要目的是允許一般的算法更改其行為，從而在將其應用到隨機或連續(xù)訪問列表時能提供良好的性能。
• implements Cloneable：可以調(diào)用 clone() 方法來返回實例的 field-for-field 拷貝
• implements java.io.Serializable：具有序列化功能

2.2 字段

// 默認初始化容量10
private static final int DEFAULT_CAPACITY = 10;

// 當指定容量為0時，返回該共享空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};

// 調(diào)用無參構(gòu)造方法時，返回該默認數(shù)組
// 與EMPTY_ELEMENTDATA的區(qū)別：該值是在默認構(gòu)造時返回，而EMPTY_ELEMENTDATA是在用戶指定容量為0時返回
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 保存添加到ArrayList中的元素
 * ArrayList的容量就是該數(shù)組的長度
 * 當?shù)谝淮斡性剡M入ArrayList中時，數(shù)組將擴容為DEFAULT_CAPACITY
 * 被標記為transient，在對象被序列化的時候不會被序列化
 */
transient Object[] elementData; // non-private to simplify nested class access

// ArrayList的實際大?。〝?shù)組包含的元素個數(shù)）
private int size;

/**
 * 分派給arrays的最大容量
 * 減去8是因為某些VM會在數(shù)組中保留一些頭字，嘗試分配這個最大存儲容量，可能會導致array容量大于VM的limit，最終導致OutOfMemoryError
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

2.3 構(gòu)造方法

1. ArrayList(int initialCapacity)：構(gòu)造一個指定容量為capacity的空ArrayList，容量為0則this.elementData = EMPTY_ELEMENTDATA，不為0則新建 new Object[initialCapacity]
2. ArrayList()：構(gòu)造一個空數(shù)組，this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
3. ArrayList(Collection<? extends E> c)：構(gòu)造一個包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。

2.4 添加元素

• 添加元素分兩個步驟：
  1. 空間檢查，如果有需要進行擴容；
  2. 插入元素

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

2.5 容量檢查和擴容

1. 若 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，則取minCapacity為默認容量和傳入容量參數(shù)之間的最大值；
2. 否則執(zhí)行 3 進行明確的容量檢查；
3. 如果所需最小容量比當前數(shù)組長度還要大，則擴容；
4. 第一次擴容為 newCapacity = oldCapacity + (oldCapacity >> 1)，即擴容為1.5倍；
5. 如果一次擴容后還不夠則直接擴充到所需的 minCapacity；
6. 如果容量超過 MAX_ARRAY_SIZE 則擴容至 MAX_ARRAY_SIZE 或拋出溢出的異常；
7. 最后把原有數(shù)組復制到新容量的數(shù)組中

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

    ensureExplicitCapacity(minCapacity);
}

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

    // 所需最小容量比當前數(shù)組長度還要大，需要擴容
    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);
}

2.6 get、set、remove、trimToSize

• 三者首先都需要進行范圍檢查

private void rangeCheck(int index) 
{
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

• 范圍檢查通過后，get 直接返回元素

public E get(int index) 
{
    rangeCheck(index);

    return elementData(index);
}

E elementData(int index) 
{
    return (E) elementData[index];
}

• set 用新值覆蓋舊值，并返回舊值

public E set(int index, E element) 
{
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

• remove 刪除指定元素，并將該元素之后的元素向左移動，并修改 size，最后返回舊值
• 將索引為 size-1 處的元素顯示賦值為null，從而讓GC能發(fā)揮作用。若不手動賦null值，除非對應的位置被其他元素覆蓋，否則原來的對象就一直不會被回收（深入理解 Java 虛擬機中有涉及）

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

• 刪除元素時不會減少容量，若希望減少容量則調(diào)用 trimToSize()

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

2.7 modCount

• modCount 繼承于 AbstractList，它記錄的是集合的修改次數(shù)，例如每次 add 或者 remove 它的值都會加1
• 它的作用是當執(zhí)行一些迭代器操作時，由于ArrayList是非線程安全的，因此每次執(zhí)行時：
  1. 設(shè) expectedModCount = modCount
  2. 執(zhí)行迭代器 next 或 remove 等操作時，先調(diào)用checkForComodification來檢查expectedModCount和modCount是否相等，若不等則拋出異常

final void checkForComodification() 
{
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}