ArrayList源碼閱讀

前言

數組是我們最常用最簡單的資料結構，Java裡對數組做了一個簡單的包裝，就是ArrayList，提供自動擴容的功能。

最常用法

list在我們日常代碼中最為常用的做法是建立一個list，放入資料，取出資料。如下：

@Test
public void testList(){
    final List<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("a");

    final String one = list.get(0);
    final int size = list.size();

    Assert.assertEquals("a", one);
    Assert.assertEquals(4, size);
}           

下面，将從構造函數開始讀取源碼。

構造器

第一步，構造一個list對象

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}           

注釋寫的很清楚，構造一個空list，初始化容量為10. 我們來看看這個初始值。

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};           

預設大小的共享的空array執行個體。可以注意到這是一個static變量，也就是說所有的ArrayList對象共享這個變量。由此可以猜測，這是一個臨時值。

然後看我們的資料存儲對象elementData.

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access           

ArrayList的容量(capacity)就是這個數組的長度。

另外，注意修飾關鍵字

transient

， 這個不常用，用來表示這個字段不可以被序列化。我們知道，ArrayList實作了

Serializable

接口，為什麼不允許序列化data呢？具體原因參加 http://www.cnblogs.com/woshimrf/p/java-serialize.html

add

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

先保證容量，然後插入資料，size數量+1.

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

    ensureExplicitCapacity(minCapacity);
}           

針對空list第一次add，判斷elementData是不是預設的空對象，若是空對象，計算容量。容量的計算也很有意思。

private static final int DEFAULT_CAPACITY = 10;           

第一次添加後容量就是10了，當超過10之後就肯定要擴容了。

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

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}           

再一次看到modCount這個變量名，和HashMap一樣，記載容量發生變化的次數。而擴容的門檻值也相當簡單，隻要保證目前數量+1能夠容納就好。當數組長度不夠的時候，擴容。

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

擴容也同HashMap一樣，擴大為2倍。然後建立數組，長度為新的容量，複制舊資料。由于過程中沒有加鎖，ArrayList也不是線程安全的。

Get

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

    return elementData(index);
}           

實作相當簡單，就是通過數組下标讀取元素。但值得學習的是程式設計結構。比如，這個的範圍檢測，通過一個有意義的方法名封裝了一段代碼。清晰易懂。

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

如何使用線程安全的List

自己對變化過程加鎖，或者使用

List list = Collection.synchronizedList(new ArrayList());           

CopyOnWriteArrayList是一個有趣的例子，它規避了隻讀操作（如get/contains）并發的瓶頸，但是它為了做到這點，在修改操作中做了很多工作和修改可見性規則。 此外，修改操作還會鎖住整個List，是以這也是一個并發瓶頸。是以從理論上來說，CopyOnWriteArrayList并不算是一個通用的并發List。(并發程式設計網)

參考

    關注我的公衆号

唯有不斷學習方能改變！

--

Ryan Miao