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

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

擴容機制

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

擴容原理

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

源碼分析

先來看ArrayList類生命的幾個參數(shù)

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

當我們創(chuàng)建ArrayList對象并且指定長度時調(diào)用的構(gòu)造器

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

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

不指定長度時構(gòu)造器

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

需要注意的是，我們不論用上述哪個構(gòu)造器，首先第一步創(chuàng)建出來的都是空數(shù)組，但是會在第一次添加數(shù)據(jù)的時候執(zhí)行不同方法進行擴容

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

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

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

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

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

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

其次還要注意的是，如果在創(chuàng)建ArrayList對象時使用的指定長度的構(gòu)造器那么就會直接返回最小容量，也就是說如果你創(chuàng)建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()方法用于判斷是否需要擴容，經(jīng)過上述方法將最小容量minCapacity傳入ensureExplicitCapacity方法，如果這個所需最小容量大于當前數(shù)組容量（也就是當前數(shù)組存不下這個新數(shù)據(jù)了）則觸發(fā)擴容機制grow()方法，反之不會進行擴容

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

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

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

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;

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

private void grow(int minCapacity) {
        // overflow-conscious code
    // 獲取原數(shù)組容量
        int oldCapacity = elementData.length;
    // 新數(shù)組的容量是原數(shù)組容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判斷新數(shù)組容量是否小于最小容量
        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:
    // 調(diào)用copyOf方法將原數(shù)據(jù)全部復(fù)制到新的空數(shù)組中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
// 超出了ArrayList容量執(zhí)行hugeCapacity
    private static int hugeCapacity(int minCapacity) {
        // 因為Integer溢出則為負數(shù)，此處判斷是否溢出
        if (minCapacity < 0) // overflow
            // 拋出異常  內(nèi)存溢出
            throw new OutOfMemoryError();
        // 沒有溢出則判斷最小容量是否大于了ArrayList允許的最大值
        // 大于--> 返回Integer最大值
        // 小于--> 返回ArrayList允許的最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

值得注意的是，如果當前數(shù)組是無參構(gòu)造器默認生成的空數(shù)組，并且是第一次添加數(shù)據(jù)時，那么數(shù)組的長度將會直接變?yōu)?0

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

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

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