20220929-ArrayList擴容機制源碼分析

2022 年 9 月 29 日
筆記
JAVA

示例程式碼

public class ArrayListSource {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();  //跳轉至第一步
        for (int i = 0; i < 10; i++) {
            arrayList.add(i);  //需要進行第一次擴容，跳轉至第二步
        }
        for (int i = 11; i <= 15; i++) {
            arrayList.add(i);  //需要進行第二次擴容
        }
        arrayList.add(100);  //需要進行第三次擴容
        arrayList.add(200);
        arrayList.add(300);
    }
}

程式碼分析

第一步：
當使用new ArrayList()創建集合時，會調用ArrayList類的無參構造器，在集合內部存在一個空的elementData數組，程式碼如下

private static final int DEFAULT_CAPACITY = 10;  //默認容量
...
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  //默認空數組
...
transient Object[] elementData;  //存放Object對象的數組
...
private int size;  //集合中所包含的元素，默認為0
...
protected transient int modCount = 0;
...
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  //MAX_ARRAY_SIZE = 2147483639
...
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  //elementData初始化為{}數組，其中size=0 
}

第二步：
程式進入for循環，從i=0開始，執行arrayList.add(i)方法，進入ArrayList類中

public boolean add(E e) {  //此時：e=1
        ensureCapacityInternal(size + 1);  //跳轉至第三步
        elementData[size++] = e;
        return true;
}

第三步：
執行ensureCapacityInternal(size + 1)，其中size=0

private void ensureCapacityInternal(int minCapacity) {  //此時minCapacity=size+1=1，即給集合中添加1個元素，需要的最小容量是1
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));  //跳轉至第四步
}

第四步：
先執行ensureExplicitCapacity()中的嵌套函數calculateCapacity(elementData, minCapacity)

// elementData = {}
// minCapacity = 1
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
// DEFAULT_CAPACITY = 10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  //此if語句成立
            return Math.max(DEFAULT_CAPACITY, minCapacity);  //返回值為10，退出函數，跳轉至第五步，
        }
        return minCapacity;
}

第五步：
執行ensureExplicitCapacity()函數

// minCapacity = 10
// modCount默認為0，然後自加1
// elementData.length = 0
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)  //此時if語句成立
            grow(minCapacity);  //跳轉至第六步
}

第六步：
執行grow(minCapacity)

// minCapacity = 10
// MAX_ARRAY_SIZE = 2147483639
private void grow(int minCapacity) {
        int oldCapacity = elementData.length; //oldCapacity=0
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //newCapacity=0+0/2=0
        if (newCapacity - minCapacity < 0)  //此if語句成立
            newCapacity = minCapacity;  //newCapacity = 10
        if (newCapacity - MAX_ARRAY_SIZE > 0)  //此if語句不成立
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
        //此語句執行後，elementData = {null,null,null,null,null,null,null,null,null,null}
}

第七步：
當程式執行完第六步之後，根據方法調用步驟依次返回，直至第二步的第2條程式語句

public boolean add(E e) {//此時：e=1
        ensureCapacityInternal(size + 1);
        //通過以上方法，確保集合中可以存放e對象
        elementData[size++] = e;//此時size=0，之後自加1；e=1
        //執行之後 elementData = {1,null,null,null,null,null,null,null,null,null}
        return true;
}

第八步：
在for循環中，不斷執行 arrayList.add(i)方法，直到for循環結束，以上步驟介紹了ArrayList第一次默認初始化之後存放元素的步驟和擴容機制，當集合中存放的對象達到容量10時，集合需要再次進行擴容。而接下來的每次擴容的容量=原來容量*1.5，即 0 –> 10 –> 15 –> 22 –> 33…

Tags: JAVA