閱讀源碼，從ArrayList開始

2020 年 10 月 9 日
筆記
Java SE, 源碼閱讀

前言

為啥要閱讀源碼？一句話，為了寫出更好的程序。
一方面，只有了解了代碼的執行過程，我們才能更好的使用別人提供的工具和框架，寫出高效的程序。另一方面，一些經典的代碼背後蘊藏的思想和技巧很值得學習，通過閱讀源碼，有助於提升自己的能力。當然，功利的講，面試都喜歡問源碼，閱讀源碼也有助於提升通過面試的概率。

結合今天的主題，一個很簡單的問題，在剛學習集合時，我們都使用過如下代碼，但是下面幾行代碼有區別嗎？

List list1 = new ArrayList();
List list2 = new ArrayList(0);
List list4 = new ArrayList(10);

有人可能會說，沒指定初始值就按默認值，指定了初始值就按指定的值構造一個數組。真的是這樣嗎？如果你對上面這個問題有疑惑，就說明你該看看源碼了。

學習編程的過程千萬不要人云亦云，一定要親自看看。

如何閱讀源碼，每個人的方式不同，這裡僅以自己習慣的方式來說。以今天的主題為例，ArrayList是幹嘛的？怎麼用？這就延伸到一條路線，先看類名及其繼承體系——它是幹嘛的，再看構造函數——如何造一個對象，當然，構造函數會用到一些變量，所以在此之前我們需要先了解下用到的常量值和變量值，最後，我們需要了解常用的方法以及它們是如何實現的。

對於閱讀大多數類基本都是按照：類名——>變量——>構造函數——>常用方法。

本文只會選取有代表性的一些內容，不會講到每一行代碼。

類簽名

好像沒有類簽名這個說法，這裡是對照函數簽名來說的，簡單說就是一個類的類名以及它實現了哪些接口，繼承了哪些類，以及一些泛型要求。

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

從上述代碼可以看出，ArrayList實現了：

Cloneable, Serializable接口，具有克隆（注意深度拷貝和淺拷貝的區別）和序列化的能力，

RandomAccess接口，具有隨機訪問的能力，這裡說的隨機主要是基於數組實現的根據數組索引獲取值，後期結合LinkedList分析更容易理解。

List接口，表明它是一個有序列表（注意，此處的有序指的是存儲時的順序和取出時的順序是一致的，不是說元素本身的排序），可以存儲重複元素。

AbstractList已經實現了List接口，AbstractList中已經實現了一些常見的通用操作，這樣在具體的實現類中通過繼承大大減少重複代碼，需要的時候也可以重寫其中方法。

變量

    //序列化版本號
    private static final long serialVersionUID = 8683452581122892189L;

    //常量，默認容量為10
    private static final int DEFAULT_CAPACITY = 10;

   	//常量，初始化一個空的Object類型數組
    private static final Object[] EMPTY_ELEMENTDATA = {};

	//常量，本質也是一個空的Object類型數組，與EMPTY_ELEMENTDATA用於區別初始化時指定容量0還是默認不指定
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	//變量，真正用來存儲元素的數組名
    transient Object[] elementData; 

	//數組中實際存儲的元素數量，未初始化則默認為0
    private int size;

上述變量中的大部分值都比較好理解，令人疑惑的事EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA，除了變量名，其他都一樣，好在注釋和後續的方法為我們說明了，簡單說，就是針對初始化時，不同的構造函數選用不同的變量名，即

List list1 = new ArrayList(); //此時用DEFAULTCAPACITY_EMPTY_ELEMENTDATA
List list2 = new ArrayList(0); //此時用EMPTY_ELEMENTDATA

為啥搞這麼麻煩，是大神們閑得慌嗎？顯然不是，不信？請繼續往下看。

構造方法


//不指定初始容量的構造函數
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//指定初始容量的構造函數
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
    }
}

//通過已有集合直接構造
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

如上所示，ArrayList有三個構造函數：

不指定容量的情況下，此時直接構造一個空的數組，只有當添加第一個元素時，才會擴容為默認容量10。所以說並不是我們經常理解的直接構造一個容量為10的數組，到此時我們才理解為啥很多時候一些規範建議我們指定初始容量，因為這樣可以減少一次擴容操作。注意，此時使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA 。

指定容量時，小於0拋異常，大於0直接用指定的值構造一個數組，等於0時，也是構造一個空數組，但是此時使用的是EMPTY_ELEMENTDATA。

有啥區別呢？關鍵在與擴容時的操作。繼續往下看。

記住，ArrayList的擴容操作只可能發生在添加元素時。

常用方法

ArrayList的常用方法非常多，這裡先排除一大批私有方法和內部類，看一下外部方法（尷尬，差一點一張圖截不下）：

看起來很多，這裡只選取幾個常用的，其他的可以類比着看。

add(E e)

第一個最常用的方法，添加元素（add）

public boolean add(E e) {
    //檢查數組容量是否充足,不夠則擴容
    ensureCapacityInternal(size + 1);  
    //注意，下方代碼相當於elementData[size] = e; size++;
    elementData[size++] = e;
    return true;
}

可以看出，在添加元素時，第一步先檢查數組容量是否充足，不夠的話進行擴容，add方法的關鍵在於檢查容量

檢查容量：ensureCapacityInternal(int minCapacity)

//檢查容量是否足夠，不夠則擴容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//比較實際存儲元素+1與數組的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	//若構造時不指定容量，則返回默認容量10或者現有實際元素+1中的最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
	//構造時指定了容量，不管是0還是大於0，都返回實際容量+1
    return minCapacity;
}

//如果實際容量+1超過了現有容量（數組裝不下了），則擴容
private void ensureExplicitCapacity(int minCapacity) {
    //記錄修改次數，主要是為了遍曆元素時發生修改則快速失敗，此處不談。
    modCount++;

    // 如果現有元素+1大於數組實際長度，則進行擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

關鍵來了，如何擴容

擴容方法：grow(int minCapacity)

private void grow(int minCapacity) {
    // 舊容量為數組長度
    int oldCapacity = elementData.length;
    //新容量為舊容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //新容量小於實際元素+1，則按實際元素+1擴容
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //新容量大於數組最大長度，根據實際選擇容量為Integer.MAX_VALUE或者MAX_ARRAY_SIZE;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 將舊數組元素複製到新數組
    elementData = Arrays.copyOf(elementData, newCapacity);
}

上述代碼有一個關鍵方法Arrays.copyOf(elementData, newCapacity)用來複制集合中的元素，此處不再深入。

回到開始的問題

在創建ArrayList時，

不指定初始容量，即

List list1 = new ArrayList();
//此時，構造一個空的數組，第一次添加元素時，將數組擴容為10，並添加元素。

指定初始容量為0，即

List list2 = new ArrayList(0);
//此時，也構造一個空數組，但變量名和上面不一樣。第一次添加元素時，將數組擴容為1，並添加元素。

指定初始容量為10，即

List list4 = new ArrayList(10);
//直接構造一個容量為10的數組，第一次添加元素時，不擴容。

所以說，如果我們大概確定將要使用的元素數量，應當在構造函數中指明，這樣可以減少擴容次數，一定程度上提升效率。

小結

到目前為止，只是簡單寫了下ArrayList的構造函數和add方法，大部分內容都還沒有深入。想要把每一個方法都寫到，其實很難，也沒必要。

通過上面的內容，回顧自己閱讀源碼的過程，既要「不求甚解」，更要「觀其大略」，對於一些核心的過程，我們需要仔細分析；但是對沒有經驗的新手來說，弄清楚每個細節很難，有些內容現階段可能還沒法理解，把握整體結構很重要，先搞清楚大概，再對每一個細節深入。如果一開始就對某一細節一直深入，很可能迷失其中自己都走不出來了。

看到這裡，你問我是不是對ArrayList完全了解了，哈哈，顯然沒有。但是，寫到這裡的時候，我的理解又深刻了不少。

心裏覺得大概懂了不一定是真的理解，只有抱着把內容寫出來讓別人看明白的心態，才有可能加深理解。不知，你看明白了沒？

Tags: Java SE 源碼閱讀