Java?ArrayList擴容機制原理是什么

本文小編為大家詳細介紹“Java ArrayList擴容機制原理是什么”，內容詳細，步驟清晰，細節處理妥當，希望這篇“Java ArrayList擴容機制原理是什么”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

擴容機制

ArrayList是一個底層基于數組實現的集合容器。當我們在創建ArrayList對象時，默認數組長度為10，當然也可以在創建時指定長度。之后在程序執行過程中，不斷地向ArrayList中添加數據。當數據存儲達到底層數組最大容量時則會觸發擴容機制

擴容原理

首先創建一個新的數組，新數組的長度時原數組的1.5倍。然后調用Arrays.copyOf()方法將原數組的所有數據copy到新數組中，再將當前新添加的數據添加至新數組并返回

源碼分析

先來看ArrayList類生命的幾個參數

// 默認ArrayList底層數組長度為10
private static final int DEFAULT_CAPACITY = 10;
// 空數組  其他地方調用
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默認長度的空數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// elementData 真正存儲數據的數組  ArrayList的容量就是該數組的長度 
// 默認創建空的ArrayList將在第一次調用add方法時將該數組擴容成為DEFAULT_CAPACITY = 10的容量
transient Object[] elementData;
// size代表的是當前elementData數組中存儲的元素個數  并不是數組的容量！ 
private int size;

當我們創建ArrayList對象并且指定長度時調用的構造器

ArrayList<> list = new ArrayList<>(12);

public ArrayList(int initialCapacity) {
    // initialCapacity就是你指定的長度
    // 邏輯判斷
        if (initialCapacity > 0) {
// initialCapacity符合要求就創建新數組 長度為你指定的長度
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
// 如果initialCapacity為0則得到一個空數組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }

不指定長度時構造器

public ArrayList() {
    // 使用默認長度大小的數組
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

需要注意的是，我們不論用上述哪個構造器，首先第一步創建出來的都是空數組，但是會在第一次添加數據的時候執行不同方法進行擴容

下面我們從調用add()方法開始分析：

每次添加數據都會將size+1去進行判斷，保證數組擁有至少存儲這個新數據的空間

public boolean add(E e) {
    // 就此處開始一系列的擴容判斷和操作
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;// 添加數據
        return true;
    }
// 下面是add方法中第一行執行的方法  此處minCapacity就是數組的最小容量  也就是當前存儲的元素個數+1
private void ensureCapacityInternal(int minCapacity) {
 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

CalculateCapacity()方法用于判斷當前數組是否是默認容量的數組，如果是默認容量的數組那么此時就要確定是否是第一次添加數據

如果是第一次添加數據，那么就將返回DEFAULT_CAPACITY=10也就是minCapacity=10

如果不是第一次添加數據，就將添加新數據之后的最小容量返回

其次還要注意的是，如果在創建ArrayList對象時使用的指定長度的構造器那么就會直接返回最小容量，也就是說如果你創建ArrayList指定長度為0，那么此時就會返回minCapacity=1，指定長度為0這個清空后面給到具體分析

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

ensureExplicitCapacity()方法用于判斷是否需要擴容，經過上述方法將最小容量minCapacity傳入ensureExplicitCapacity方法，如果這個所需最小容量大于當前數組容量（也就是當前數組存不下這個新數據了）則觸發擴容機制grow()方法，反之不會進行擴容

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;// modCount++是做什么的？ 我也不知道
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

在分析grow()方法之前我們先明確兩個概念：

ArrayList定義了允許存儲的最大容量也就是Integer允許的范圍-8，如果溢出則是負數

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Integer類型的范圍是： -2的31次方~2的31次方減1

@Native public static final int MAX_VALUE = 0x7fffffff;

下面我們來看真正實現擴容的grow()方法

private void grow(int minCapacity) {
        // overflow-conscious code
    // 獲取原數組容量
        int oldCapacity = elementData.length;
    // 新數組的容量是原數組容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判斷新數組容量是否小于最小容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    // 判斷新容量是否超過了ArrayList允許的最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
    // 調用copyOf方法將原數據全部復制到新的空數組中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
// 超出了ArrayList容量執行hugeCapacity
    private static int hugeCapacity(int minCapacity) {
        // 因為Integer溢出則為負數，此處判斷是否溢出
        if (minCapacity < 0) // overflow
            // 拋出異常  內存溢出
            throw new OutOfMemoryError();
        // 沒有溢出則判斷最小容量是否大于了ArrayList允許的最大值
        // 大于--> 返回Integer最大值
        // 小于--> 返回ArrayList允許的最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

值得注意的是，如果當前數組是無參構造器默認生成的空數組，并且是第一次添加數據時，那么數組的長度將會直接變為10

如果當前的數組是有參構造器（指定長度）生成并且指定初始容量為0，那么在前四次調用add方法添加數據時每次擴容都是+1,只有在第五次才會執行1.5倍擴容。

因為第一次添加則是minCapacity=1，oldCapacity=0 執行int newCapacity = oldCapacity + (oldCapacity >> 1);之后newCapacity 還是0，則執行if (newCapacity - minCapacity < 0) -->newCapacity = minCapacity;也就是1，那么newCapacity 就為1，后面的三次以此類推差不多，那么至此，ArrayList就完成了擴容。

讀到這里，這篇“Java ArrayList擴容機制原理是什么”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。