注：本文的java環(huán)境為：max os x 10 ，jdk8
1、前言
說(shuō)到ArrayList，就不得不說(shuō)Array。光看名字，還以為這2個(gè)是同一個(gè)東西。其實(shí)不然。
Array:指容量為固定的數(shù)組，常見(jiàn)的初始化方法如下：

String[] names = {"david","tom","kate"};

在聲明的時(shí)候直接聲明了內(nèi)部元素，這樣jvm就可以快速的分配給指定大小的空間。同時(shí)，看Array源碼可知，Array的方法基本上都是native方法，其底層實(shí)現(xiàn)均為c/c++實(shí)現(xiàn)。

ArrayList:動(dòng)態(tài)數(shù)組，允許新增、刪除等操作，常見(jiàn)的初始化方法：

List<String> nameList = new ArrayList<>();

看完概念，我們開(kāi)始正題，開(kāi)始源碼的解讀。

2、與其他容器對(duì)比

與hashmap不同，ArrayList為集合的一種，來(lái)源自數(shù)據(jù)結(jié)構(gòu)中的數(shù)組概念，與hashmap源自數(shù)據(jù)結(jié)構(gòu)中的圖概念不同。

我們先看ArrayList的uml圖。

類(lèi)圖

可以看出，ArrayList不僅實(shí)現(xiàn)了Cloneable、Serializable接口，還 實(shí)現(xiàn)了RandomAccess接口、List接口。

3、簡(jiǎn)述RandomAccess接口
在后續(xù)代碼中，還可以看到RandomAccess這個(gè)接口。若實(shí)現(xiàn)了該接口，則表明該類(lèi)可以進(jìn)行下標(biāo)式訪問(wèn)，類(lèi)似于這樣：

List<String> nameList = new ArrayList<>();
String david  = names[0];

（這個(gè)會(huì)提示越界了）

4、成員變量分析
ArrayList的成員變量分析如下：

//默認(rèn)容量
private static final int DEFAULT_CAPACITY = 10;
//空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//也是空數(shù)組，作用是在新增元素的時(shí)候用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//數(shù)組
transient Object[] elementData;
//數(shù)組大小
private int size;
//數(shù)組最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//繼承自AbstractList，用于fail-fast機(jī)制
protected transient int modCount = 0;

從成員變量來(lái)看，數(shù)組用transient修飾符修飾，作用應(yīng)該是類(lèi)似于hashmap的Node[]。

5、核心方法分析

5.1 容量擴(kuò)增

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新空間分配直接擴(kuò)大50%
        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:
        //元素復(fù)制
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
private static int hugeCapacity(int minCapacity) {
        //這一點(diǎn)比較特殊,見(jiàn)下面分析
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

關(guān)于hugeCapacity的判斷小于0則為溢出，由于在jvm內(nèi)部是以反碼存儲(chǔ)的數(shù)據(jù)，首位為符號(hào)位，當(dāng)容量擴(kuò)增后，若溢出，首位則變?yōu)?，此時(shí)變?yōu)樨?fù)數(shù)，則可以快速判斷出是否溢出。

5.2 trimToSize 壓縮空間

去掉多余的空對(duì)象，精簡(jiǎn)存儲(chǔ)空間

public void trimToSize() {
        modCount++;
        //代碼也寫(xiě)的很簡(jiǎn)潔，經(jīng)常使用三元表達(dá)式
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

由上面的擴(kuò)增容量可知，如果原始容量是100，在擴(kuò)增容量后，那么分配的容量為150.但是實(shí)際上可能只存110個(gè)對(duì)象實(shí)例，那么此時(shí)調(diào)用這個(gè)方法，就可以節(jié)約一定的存儲(chǔ)空間。不過(guò)若數(shù)組較大，那么操作可能會(huì)耗費(fèi)一點(diǎn)時(shí)間。

5.3 fail-fast機(jī)制
這個(gè)其實(shí)在hashmap中也采取了類(lèi)似機(jī)制，就是額外有一個(gè)成員變量，用于快速判斷該實(shí)例是否有變化，若在進(jìn)行迭代的時(shí)候有變更，那么就拋出一個(gè)并發(fā)修改異常(ConcurrentModificationException)。

5.4 indexOf 求 下標(biāo)

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
}

這段代碼略過(guò)，用的比較多，沒(méi)什么亮點(diǎn)。

5.5 新增一個(gè)元素

既然是數(shù)組，那么就有兩種 新增的方式：指定特定的位置、向后插入。

向指定位置寫(xiě)入元素：

public void add(int index, E element) {
        //下標(biāo)檢查，是否越界了
        rangeCheckForAdd(index);
        //擴(kuò)增容量，同時(shí)改變modcount
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //index后面的元素后移
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        //指定位置放置元素
        elementData[index] = element;
        //元素?cái)?shù)量大小自增
        size++;
    }

向后插入一個(gè)元素:

public boolean add(E e) {
        //擴(kuò)大容量,修改modcount
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //注意
        //數(shù)組是從0開(kāi)始的存元素的，而數(shù)組個(gè)數(shù)是從1開(kāi)始計(jì)數(shù)的
        //這個(gè)地方是往第size個(gè)位置上存元素
        //再將元素個(gè)數(shù)加1
        elementData[size++] = e;
        return true;
    }

從以上源碼可以看出，向后插入一個(gè)元素不用進(jìn)行元素的復(fù)制，自然效率要大于指定位置插入一個(gè)元素。

5.6 移除一個(gè)元素
同新增，也是分2種。
移除指定位置的元素：

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);
        //這個(gè)與新增類(lèi)似，但是是左自減運(yùn)算，自己體會(huì)吧
        //特地表明將該位置的置空，讓gc回收空間
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

刪除指定元素：

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

//類(lèi)似指定位置刪除元素
private void fastRemove(int index) {
    modCount++;
    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
}

看到這個(gè)指定刪除某個(gè)元素的代碼，那么有人就會(huì)有疑問(wèn)了，如果我里面有多個(gè)一樣的元素，那這不是刪不完嗎？這個(gè)時(shí)候你得使用removeAll：

public boolean removeAll(Collection<?> c) {
    //參數(shù)校驗(yàn)，僅判斷c != null，感覺(jué)不太嚴(yán)謹(jǐn)
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    //常量數(shù)組，不允許再賦值,但是數(shù)組內(nèi)部的元素允許自由移動(dòng)、被重新賦值
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //不包含該元素,則存到新數(shù)組,其實(shí)是位置前移
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //上面if內(nèi)類(lèi)型不匹配拋異常時(shí)，r與size不等
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            //由于將已包含的元素前移了，那么不包含的元素都在后面，直接將后面的元素刪掉
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

5.7 序列化
這個(gè)源碼類(lèi)似于hashmap，就不重復(fù)分析了。

5.8 其他
set、get方法比較簡(jiǎn)單， 就不分析了。
需要注意的是，arraylist繼承的AbstractList覆寫(xiě)了hashcode和equals方法。

6 小結(jié)
總的來(lái)說(shuō)，arraylist的源碼比較簡(jiǎn)單，可供分析的內(nèi)容不多。