原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處

Java程序的核心就是那些在啟動(dòng)時(shí)和運(yùn)行中所創(chuàng)建的對(duì)象，如何管理這些對(duì)象是一項(xiàng)非常重要的工作。既要方便存儲(chǔ)，又要方便讀取，有時(shí)候還需要對(duì)對(duì)象進(jìn)行排序，根據(jù)不同的場(chǎng)合，需要將同一類的對(duì)象存放在一起，就形成了容器的概念。

Java 集合框架.gif

Java類庫(kù)為我們提供了一套相當(dāng)完整的容器來解決程序運(yùn)行中對(duì)象的存儲(chǔ)問題，其中最常用的有 List、Set、Queue以及 Map。上面是一張完整的 Java 框架類庫(kù)圖，其中有許多接口和抽象類，他們定義了不同種類基礎(chǔ)容器的行為，這個(gè)系列的文章將從源碼的角度解釋圖中常用的集合類的實(shí)現(xiàn)以及使用。

線性的存儲(chǔ)

ArrayList 其實(shí)是一個(gè)典型的線性表，從名字也不難看出它與數(shù)組有莫大的關(guān)聯(lián)，其實(shí) ArrayList 內(nèi)部本身就是維護(hù)了一個(gè)數(shù)組，所有的插入、刪除等操作都是基于這個(gè)數(shù)組實(shí)現(xiàn)的。

首先看一下 ArrayList 中的變量定義:

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

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    transient Object[] elementData;

    private int size;
}   

除了一些預(yù)定義的常量，ArrayList 中一共就兩個(gè)變量：用于存放對(duì)象引用的數(shù)組elementData和標(biāo)識(shí)個(gè)數(shù)的size。值得區(qū)分一下的概念是 size 和 capacity，size 表示的是當(dāng)前 ArrayList 中所存放有效對(duì)象的個(gè)數(shù)，而 capacity 表示的是當(dāng)前 elementData 數(shù)組的容量（即數(shù)組大?。?。眾所周知數(shù)組的長(zhǎng)度一旦被指定就無(wú)法更改，既然 ArrayList 底層使用數(shù)組來實(shí)現(xiàn)，那它又是如何做到在被調(diào)用add()方法時(shí)看上去沒有容量限制的呢？答案就是不斷的比較 size 和 capacity，然后創(chuàng)建新的數(shù)組，再將原數(shù)組的內(nèi)容復(fù)制過去，這在ArrayList內(nèi)部稱為擴(kuò)容操作。

對(duì)象的存放

ArrayList共有三個(gè)構(gòu)造器，他們的作用都是初始化elementData數(shù)組：

    // NO.1
    public ArrayList() {
        this(10);
    }

    // NO.2
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    // NO.3
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
           elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

前兩個(gè)構(gòu)造器通過指定的capacity來初始化一個(gè)空的數(shù)組：this.elementData = new Object[initialCapacity]，如果沒有initialCapacity參數(shù)則默認(rèn)為10。

tips: 在新建一個(gè)ArrayList時(shí)可以預(yù)估需要的大小，以new ArrayList(20)這種形式調(diào)用，可以避免在使用ArrayList時(shí)多次擴(kuò)容。

第三個(gè)構(gòu)造器接收一個(gè)Collection參數(shù)，如果你有仔細(xì)看過文章開頭的集合框架圖不難發(fā)現(xiàn)ArrayList是Collection的一種實(shí)現(xiàn)，這個(gè)構(gòu)造器表示可以接收Collection接口的所有實(shí)現(xiàn)類型，并將其轉(zhuǎn)換為自身類型（ArrayList）進(jìn)行存儲(chǔ)。

擴(kuò)容與移位

要想將對(duì)象放入 ArrayList 中需要調(diào)用add(E)或者add(int, E)方法，前者將對(duì)象按順序放到末尾，后者可以指定放置的位置。

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

//...
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

在調(diào)用兩種 add 方法時(shí)都需要先調(diào)用ensureCapacityInternal，這個(gè)方法的做用是將數(shù)組進(jìn)行擴(kuò)容。由于在真正擴(kuò)容之前 JDK 會(huì)進(jìn)行一些邏輯檢查和判斷，最終調(diào)用到grow()函數(shù)，出于篇幅考慮將一些函數(shù)的調(diào)用關(guān)系省略掉，有興趣的朋友可以自行查閱源碼。先看看grow()函數(shù)中關(guān)鍵的部分：

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

可以看到參數(shù) minCapacity 只是一個(gè)“建議”值，ArrayList 默認(rèn)每次擴(kuò)容為當(dāng)前容量的1.5倍：

int newCapacity = oldCapacity + (oldCapacity >> 1);

在擴(kuò)充到1.5倍之后如果還沒有達(dá)到 minCapacity 時(shí)，便會(huì)采用 minCapacity 的值，最后調(diào)用 Arrays.copyOf(elementData, newCapacity);將整個(gè)數(shù)組進(jìn)行拷貝。
回到add(int, E)方法，數(shù)組擴(kuò)容完后，需要在指定的位置插入元素，接著便調(diào)用了System.arraycopy，根據(jù)參數(shù)可以看出這一步將 elementData 數(shù)組第index之后的元素全部向后移了一位，再在 index 位置插入新元素。
至此，對(duì)象的存放完成，通過對(duì)擴(kuò)容和移位的分析，可以看出基于數(shù)組實(shí)現(xiàn)的 ArrayList 在對(duì)象的插入操作上效率并不高，但是數(shù)組的優(yōu)點(diǎn)是快速的隨機(jī)訪問，在接下來的對(duì)象獲取方法中將可以看到 ArrayList 很好的繼承了數(shù)組的這一特性。

對(duì)象的獲取

ArrayList 最常用的get(int index)方法一共只有兩行：

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

        return elementData(index);
    }

    //...
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

在檢查完參數(shù) index 的范圍之后，直接就返回 index 位置上的元素，非?？焖?。

另一個(gè)獲取對(duì)象有關(guān)的常用函數(shù)是indexOf(Object o)，到這里讀者應(yīng)該可以想到基于數(shù)組的 ArrayList 是怎樣查找元素在數(shù)組中的下標(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;
    }

通過源碼可以觀察到比較有趣的一點(diǎn)，indexOf的參數(shù)允許為 null，并且如果數(shù)組中有值為 null的元素（在 size 范圍以內(nèi)）時(shí)將返回下標(biāo)。

調(diào)用remove(int index)函數(shù)同樣會(huì)使數(shù)組中多個(gè)元素位置變動(dòng)：

    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)用 arraycopy方法，只不過拷貝的位置與 add 時(shí)相反。同時(shí)注意到elementData[--size] = null;是非常關(guān)鍵的，正如注釋所說，進(jìn)行remove操作以后，數(shù)組最后一個(gè)位置上引用的對(duì)象邏輯上已經(jīng)被“移除”，但是實(shí)際數(shù)組還保持著對(duì)象的引用，這會(huì)導(dǎo)致 GC 無(wú)法將其回收，造成內(nèi)存泄露。

功能性函數(shù)

介紹完了主要操作函數(shù)，ArrayList 封裝的一些功能函數(shù)也非常有意思。

• trimToSize：
  這個(gè)函數(shù)的作用是將數(shù)組容量（capacity）修整到 size 的大小。譬如ArrayList在大量讀入對(duì)象之后又進(jìn)行了許多移除操作，并且預(yù)計(jì)在今后很長(zhǎng)一段時(shí)間容量都將保持在較小范圍內(nèi)，這時(shí)可以手動(dòng)都用trimToSize()來節(jié)約內(nèi)存空間。

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

• addAll:
  addAll 方法接收一個(gè)實(shí)現(xiàn)了 Collection 接口的類型，并將其添加到當(dāng)前 ArrayList 末尾：

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

其實(shí)質(zhì)最終還是調(diào)用了 arraycopy 方法，ArrayList.addAll()方法很容易讓人聯(lián)想到定義在 Collections 中的 addAll 方法，在沒有特殊要求的時(shí)候兩者可以互換，個(gè)別情況下由于其實(shí)現(xiàn)邏輯不同兩者的性能會(huì)有一些差異，這里不做過多討論，開發(fā)者可以根據(jù)編程風(fēng)格和規(guī)范自行選擇，Collections.addAll()的定義如下：

    public static <T> boolean addAll(Collection<? super T> c, T... elements) {
        boolean result = false;
        for (T element : elements)
            result |= c.add(element);
        return result;
    }

小結(jié)

ArrayList 正如其名字，是實(shí)現(xiàn)了 List接口規(guī)范，底層采用數(shù)組的一個(gè)集合類。ArrayList 繼承了數(shù)組的所有優(yōu)缺點(diǎn)，并且在使用上針對(duì) List 接口進(jìn)行了封裝，例如在指定位置插入、刪除元素等。開發(fā)人員在使用時(shí)可以完全按照 List 接口定義的規(guī)范進(jìn)行調(diào)用，但是知道其底層實(shí)現(xiàn)細(xì)節(jié)對(duì)程序調(diào)優(yōu)、不同集合類之間的選擇有很大的幫助。