關於ArrayList的動態擴容機制解讀

Posted on by

1. 前言

對於 ArrayList 的動態擴容機制想必大傢都聽說過，之前的文章中也談到過，不過由於時間久遠，早已忘卻。

所以利用這篇文章做做筆記，加深理解記憶

2. ArrayList 的動態擴容機制

要瞭解其動態擴容機制就必須先看它的源碼，源碼是基於 jdk 1.8 的

2.1. ArrayList 的主要屬性

// 如果不指定容量（空構造器）,則在添加數據時的空構造器默認初始容量最小為 10
private static final int DEFAULT_CAPACITY = 10;
// 出現在需要用到空數組的地方，其中一處是使用自定義初始容量構造方法時候如果你指定初始容量為0的時候，那麼elementData指向該數組
// 另一處是使用包含指定collection集合元素的列表的構造方法時，如果被包含的列表中沒有數據，那麼elementData指向該數組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 如果使用默認構造方法，那麼elementData指向該數組
// 在添加元素時會判斷是否是使用默認構造器第一次添加，如果是數組就會擴容至10個容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默認未初始化的儲存 ArrayList集合元素的底層數組,其長度就是 ArrayList的容量
transient Object[] elementData;
// 私有的elementData數組中具體的元素對象的數量,可通過size方法獲得。默認初始值為0，在add、remove等方法時size會改變
private int size;

可以看到 ArrayList 底層核心是一個 Object[] elementData 的數組

2.2. ArrayList 的構造器

// 默認的構造器
public ArrayList() {
	// Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} 空數組
	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);
	}
}

從上面的構造器中，可以得出以下結論

  • 如果使用 ArrayList 的默認構造器時，它的初始容量就是 0
  • 如果使用 ArrayList 的有參構造器時，它的初始容量就是你傳入的參數 initialCapacity的值

2.3. ArrayList 的動態擴容

根據上面的兩個結論，不管是使用默認或有參構造器時，我們可以使其初始容量為 0，那麼它的動態擴容發生在哪裡？

可以肯定就發生在 add() 方法中，那麼查看 add() 方法源碼如下

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

按照我們第一次 add， size 肯定是 0 瞭，所以 ensureCapacityInternal 這個函數傳入的是 1

// 第一次 add 時，參數 minCapacity = 1
private void ensureCapacityInternal(int minCapacity) {
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// calculateCapacity() 方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {	
	// 如果是第一次 add 元素
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		// minCapacity 設置為 DEFAULT_CAPACITY 與 minCapacity 的最大值
		return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
    return minCapacity;
}
// ensureExplicitCapacity() 方法
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

elementData.length 是數組長度，它是隨著數組擴容而動態變化的

  • 如果是第一次 add 元素時，它為 0
  • 之後它是隨著 oldCapacity + (oldCapacity >> 1) 而動態變化的

首先看 calculateCapacity() 方法

  • 如果是第一次 add 元素，那麼 minCapacity 設置為 DEFAULT_CAPACITY 與 minCapacity 的最大值，即 10 與 1 取最大值，這裡返回最大值 10
  • 否則，直接返回 minCapacity

再看 ensureExplicitCapacity() 方法

  • 如果是第一次 add 元素，由上面方法可知 minCapacity = 10，即 10 – 0 > 0 返回 true，再調用 grow() 方法
  • 隻要 minCapacity – elementData.length > 0 為 true，就會再調用 grow() 方法
private void grow(int minCapacity) {
    // 原容量
    int oldCapacity = elementData.length;
    // 擴容後的容量，擴大到原容量的 1.5 倍左右，右移一位相當於原數值除以 2 的商
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量減去最小容量的值小於 0
    if (newCapacity - minCapacity < 0)
        // 新容量等於最小容量
        newCapacity = minCapacity;
    // 如果新容量減去建議最大容量的值大於 0
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 調整新容量上限或者拋出 OutOfMemoryError
        newCapacity = hugeCapacity(minCapacity);
        
     // 最終進行新數組的構建和重新賦值，此後原數組被摒棄
     // elementData:原數組; newCapacity:新數組容量
    elementData = Arrays.copyOf(elementData, newCapacity);
}

elementData.length 是數組長度，它是隨著數組拷貝而動態變化的

  • 如果是第一次 add 元素時，它為 0
  • 之後它是隨著 oldCapacity + (oldCapacity >> 1) 而動態變化的

如果是第一次 add 元素，由上面的方法可知參數 minCapacity = 10，第一次 add 元素 oldCapacity = 0，可得知 newCapacity = 0 + 0，由於 newCapacity – minCapacity < 0，所以 newCapacity = minCapacity = 10 重新賦值，最終進行新數組的構建和拷貝賦值

3. 小結

3.1. 初始容量

如果使用 ArrayList 的默認無參構造器時，它的初始容量就是 0

如果使用 ArrayList 的有參構造器時，它的初始容量就是你傳入的參數 initialCapacity的值

3.2. 動態擴容大小

ArrayList 的初始容量為 0，當第一次 add 元素時，才會發生擴容操作，它的擴容大小是 10

當第一次 add 元素完成後，此時的 elementData.length = 10，後面要想發生擴容操作，必須 minCapacity – elementData.length > 0 為 true，即 minCapacity 最小為 11，也就是說當 ArrayList 第十一次 add 時，才會接著發生擴容操作，且擴容大小為 15 = 10 + 5

3.3. 動態擴容大小測試

public class TestArrayList {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        list.add(9);
        list.add(10);
        list.add(11);// 打上斷點
    }
}

add() 方法打上斷點

ensureCapacityInternal() 方法打上斷點

ensureExplicitCapacity() 方法打上斷點

grow() 方法打上斷點

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。

推薦閱讀：