20220929-ArrayList擴容機制原始碼分析

示例代碼

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 = https://www.cnblogs.com/zhanghuaze/p/{};  //默認空陣列
...
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 = https://www.cnblogs.com/zhanghuaze/p/{}
// 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 = https://www.cnblogs.com/zhanghuaze/p/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 = https://www.cnblogs.com/zhanghuaze/p/{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...

標籤：Java

上一篇：day44-反射03

下一篇：java- 介面筆記