相信大家對 ArrayList 這個類都不陌生吧，ArrayList 底層是基于數(shù)組實現(xiàn)的，作為可變長度的數(shù)組用于存儲任意類型的對象，那么是否有了解過 ArrayList 是如何實現(xiàn)可變長的呢，它的擴容機制是什么呢？

這篇文章將從源碼的角度來講講 ArrayList 的擴容機制，有興趣的讀者們可以接著往下了解。

ArrayList 的構造函數(shù)

在了解 ArrayList 的擴容機制之前，讓我們先看看它的構造函數(shù)有哪些？

ArrayList 的字段

// 默認初始容量大小
private static final int DEFAULT_CAPACITY = 10;
// 空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默認空數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存儲數(shù)據(jù)的數(shù)組
transient Object[] elementData;
// 元素個數(shù)
private int size;
// 最大數(shù)組長度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

相信大家對這里的 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 為何需要有兩個空數(shù)組感到疑惑，這兩個空數(shù)組之間的區(qū)別在什么地方呢？對于這個問題等看完后面的源碼后就會有答案了。

ArrayList 的構造函數(shù)

// 有參構造函數(shù)（initialCapacity：指定的初始化集合大?。?
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 創(chuàng)建長度為initialCapacity的數(shù)組
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 使用空數(shù)組（長度為0）
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
// 無參構造器
public ArrayList() {
    // 使用默認空數(shù)組（一開始長度為0，等集合被使用后初始化為10）
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 有參構造器（根據(jù)指定的集合構造列表）
public ArrayList(Collection<? extends E> c) {
    // 通過toArray()方法轉(zhuǎn)換為數(shù)組
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 數(shù)組長度不為0且數(shù)組不是Object類型數(shù)據(jù)則更換類型為Object的新數(shù)組
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 數(shù)組長度為0則使用空數(shù)組
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

通過上面源碼中的三種 ArrayList 的構造函數(shù)可以看到根據(jù)不同的參數(shù)構造列表，同時根據(jù)不同的參數(shù)導致的列表的數(shù)組 elementData 被賦予的值也是不同的。

到這里應該可以看出 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的區(qū)別：

• EMPTY_ELEMENTDATA：當構造函數(shù)使用指定 initialCapacity 為 0 或指定集合且集合元素為 0 時，會使得 elementData 被賦值為 EMPTY_ELEMENTDATA。這里的空數(shù)組表示初始化后的數(shù)組長度就是 0 。
• DEFAULTCAPACITY_EMPTY_ELEMENTDATA：當構造函數(shù)使用無參構造函數(shù)時，elementData 被賦值為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。這里的空數(shù)組表示開始長度為 0，當列表被使用時，初始化后的數(shù)組長度為 10（DEFAULT_CAPACITY），也就是默認數(shù)組大小。（通過后面的 add() 源碼能夠更好理解）

到這里就可以理解為什么 ArrayList 有兩個空數(shù)組字段，主要是為了設置默認的數(shù)組長度，也就是為了區(qū)分當前數(shù)組是默認數(shù)組（也就是還不確定大小，先設置為空數(shù)組，等使用后在設置為默認長度），還是已經(jīng)確認長度為 0 的空數(shù)組。

ArrayList 的擴容機制

ArrayList 的擴容機制核心方法是 grow() 方法，這里從 add() 方法進入詳細看看 ArrayList 的擴容過程。

擴容過程源碼分析

添加元素方法：add()

public boolean add(E e) {
    // size + 1 確保添加后長度足夠，進入方法判斷是否需要擴容
    ensureCapacityInternal(size + 1);
    // 添加元素
    elementData[size++] = e;
    return true;
}

判斷是否是默認長度方法：ensureCapacityInternal()

private void ensureCapacityInternal(int minCapacity) {
    // 數(shù)組為默認數(shù)組時，minCapacity只會在10之上。
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 進入方法判斷是否需要擴容
    ensureExplicitCapacity(minCapacity);
}

判斷是否需要擴容方法：ensureExplicitCapacity()

private void ensureExplicitCapacity(int minCapacity) {
    // 用于記錄修改次數(shù)的計數(shù)器，保證多線程下拋出ConcurrentModificationException異常
    modCount++;
    // minCapacity最小需求容量小于當前數(shù)組長度時則需要擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

擴容方法：grow()

private void grow(int minCapacity) {
    // 舊容量等于數(shù)組長度
    int oldCapacity = elementData.length;
    // 新容量等于數(shù)組長度 + 0.5 * 數(shù)組長度 也就是 1.5 數(shù)組長度
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新容量還是小于最小需求容量時，直接將新容量賦值為最小需求容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 新容量大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）調(diào)用hugeCapacity()擴容到Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 數(shù)組拷貝，將數(shù)據(jù)遷移到新數(shù)組
    elementData = Arrays.copyOf(elementData, newCapacity);
}

擴容過程梳理

下面以使用無參構造函數(shù)的列表為例，分別講講第1個元素插入和第11個元素插入的擴容過程：

添加第1個元素的過程：

• 調(diào)用 add(e) 方法添加元素，此時的 size=0。
• 調(diào)用 ensureCapacityInternal(1) 方法判斷是否是默認長度數(shù)組，此時該方法的傳參是 size + 1 代表目前列表需要的最小容量。進入該方法后，因為使用的是無參構造器，故這里的數(shù)組是默認長度數(shù)組，所以 minCapacity 最小容量被置為 10，也就是列表默認長度 DEFAULT_CAPACITY。
• 調(diào)用 ensureExplicitCapacity(10) 方法判斷是否需要擴容，此時由于 minCapacity=10 大于 數(shù)組長度 elementData.length=0 所以需要擴容。
• 調(diào)用 grow(10) 方法進行擴容，此時舊數(shù)組容量為 oldCapacity=0，新數(shù)組容量為 newCapacity=0，而最小容量 minCapacity=10，因為新數(shù)組容量小于最小容量，故將新數(shù)組容量重新賦值為 newCapacity=minCapacity=10，然后進行數(shù)組拷貝，到此完成擴容操作。

添加第11個元素的過程：

• 調(diào)用 add(e10) 方法添加元素，此時的 size=10。
• 調(diào)用 ensureCapacityInternal(11) 方法判斷是否是默認長度數(shù)組，此時該方法的傳參是 size + 1 代表目前列表需要的最小容量。進入該方法后，由于已經(jīng)超出了默認長度 10，所以這里 minCapacity 設置為 11。
• 調(diào)用 ensureExplicitCapacity(11) 方法判斷是否需要擴容，此時由于 minCapacity=11 大于 數(shù)組長度 elementData.length=10 所以需要擴容。
• 調(diào)用 grow(11) 方法進行擴容，此時舊數(shù)組容量為 oldCapacity=10，新數(shù)組容量為 newCapacity=15，而最小容量 minCapacity=11，因為新數(shù)組容量大于最小容量，故將新數(shù)組容量依舊為15，然后進行數(shù)組拷貝，到此完成擴容操作，新數(shù)組的長度擴容到了 15，并將舊數(shù)組的元素遷移到新數(shù)組中。

以上就是擴容的全過程，擴容公式為 newCapacity=oldCapacity+(oldCapacity>>1)newCapacity = oldCapacity + (oldCapacity >> 1)newCapacity=oldCapacity+(oldCapacity>>1)，也就是新容量取值為舊容量的 1.5 倍。

補充：數(shù)組拷貝 System.arraycopy() 方法

擴容后的數(shù)據(jù)遷移調(diào)用的是 Arrays.copyOf() 方法底層調(diào)用的是 System.arraycopy()，這里簡單介紹一下這個常用的方法。

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

該方法的參數(shù)如下：

• src：源數(shù)組
• srcPos：源數(shù)組拷貝的起始位置
• dest：目標數(shù)組
• destPos：目標數(shù)組拷貝的起始位置
• length：需要拷貝的數(shù)組元素的數(shù)量

這里作為補充知識簡單了解一下即可。

總要有總結

以上就是 ArrayList 的擴容機制的內(nèi)容了，主要總結如下：

• ArrayList 是基于動態(tài)數(shù)組實現(xiàn)的，可以擴容或縮短（縮短可以手動調(diào)用 trimToSize() 方法，ArrayList在元素小于一半長度時會自動縮短長度，這里不作過多說明）數(shù)組的大小從而實現(xiàn)可變長的數(shù)組。
• ArrayList 中聲明了 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 兩個字段，雖然都是空數(shù)組，但是兩者之間有著不同的作用。
• ArrayList 的擴容機制采用的是新數(shù)組容量擴容為舊數(shù)組容量的 1.5 倍。

補充： ArrayList 提供了 ensureCapacity(int minCapacity) 用于實現(xiàn)手動擴容到指定的容量，這樣在需要添加大量數(shù)據(jù)時可以不必重復進行擴容操作，提高性能。

到這里就是本篇的所有內(nèi)容了，ArrayList 類中還有許多有意思的方法，有興趣的讀者們可以自行去查看它們的源碼。

到此這篇關于淺談Java中ArrayList的擴容機制的文章就介紹到這了,更多相關Java中 ArrayList擴容內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論