Java中ArrayList容量及擴(kuò)容方式的示例分析

小編給大家分享一下Java中ArrayList容量及擴(kuò)容方式的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

查看JDK1.8 ArrayList的源代碼

1、默認(rèn)初始容量為10

   /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

2、最大容量為 Integer.MAX_VALUE - 8

/**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

原因：之前參考別人的，有待求證：

數(shù)組對(duì)象有一個(gè)額外的元數(shù)據(jù)，用于表示數(shù)組的大?。?/p>

數(shù)組長(zhǎng)度size為int類(lèi)型，共32位，有一位符號(hào)位，所以最大長(zhǎng)度為Integer.MAX_VALUE=2^31= 2,147,483,648；

8bytes用來(lái)存儲(chǔ)size；

3、擴(kuò)容方式：

（1）首先傳遞進(jìn)來(lái)一個(gè)希望的最小容量minCapacity；

（2）新容量newCapacity = oldCapacity + (oldCapacity >> 1)，即新容量等于原容量的1.5倍；

（3）如果minCapacity > newCapacity ，newCapacity = minCapacity ;

（4）如果 newCapacity > 最大容量 MAX_ARRAY_SIZE ，newCapacity = hugeCapacity(minCapacity);

（5）以新容量拷貝原數(shù)據(jù)

   /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
 
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

Java ArrayList() 擴(kuò)容原理

平常都是直接使用 ArrayList()，今天特地看一下 ArrayList() 的擴(kuò)容原理。

先看下 ArrayList 的屬性以及構(gòu)造方法，這個(gè)比較重要

先看下屬性

// ArrayList 默認(rèn)容量大小
private static final int DEFAULT_CAPACITY = 10;
// 一個(gè)共享的空數(shù)組, 在空實(shí)例時(shí)使用
private static final Object[] EMPTY_ELEMENTDATA = {};
// 一個(gè)共享的空數(shù)組, 在使用默認(rèn) size 的空實(shí)例時(shí)使用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/*
存儲(chǔ) ArrayList 元素的數(shù)組緩沖區(qū)
重點(diǎn)1: ArrayList 的容量是數(shù)組緩沖區(qū)的長(zhǎng)度
重點(diǎn)2: 從這個(gè)元素也可以看的出來(lái) ArrayList() 的底層就是一個(gè) Object[]  
add 第一個(gè)元素時(shí), 任何帶有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都將被擴(kuò)展為 DEFAULT_CAPACITY
*/
transient Object[] elementData;
// ArrayList 的大小, 我們平常使用的 list.size() 底層就是記錄的這個(gè) size
private int size;
// ArrayList 最大
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

再看構(gòu)造器，帶參構(gòu)造器

/*
帶參構(gòu)造器, 參數(shù)為容量大小, 例如: 初始化一個(gè)容器為 20 類(lèi)型為 Integer 的 ArrayList
ArrayList<Integer> list = new ArrayList<>(20);
*/
public ArrayList(int initialCapacity) {
 /*
 初始化容量 > 0, elementData 初始化為初始化容量大小的數(shù)組
 初始化容量 = 0, elementData = EMPTY_ELEMENTDATA (空數(shù)組)
 初始化容量 < 0, 直接拋出異常
 */
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

參數(shù)為 Collection 的構(gòu)造器

/*
將一個(gè)參數(shù)為 Collection 的集合轉(zhuǎn)換為 ArrayList
*/
public ArrayList(Collection<? extends E> c) {
    // Collection 轉(zhuǎn)換為數(shù)組 Object[] 類(lèi)型 
    elementData = c.toArray();
    // 判斷當(dāng)前對(duì)象大小是否和 Collection 長(zhǎng)度相等并且不等于 0, false 的話 elementData 等于空數(shù)組了
    if ((size = elementData.length) != 0) {
     // c.toArray() 可能不會(huì)正確地返回一個(gè) Object[] 數(shù)組，所以使用 Arrays.copyOf()
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

不帶參構(gòu)造器

/*
不帶參構(gòu)造器就像我們平時(shí)使用一樣, 直接 new 一個(gè) ArrayList 不需要傳遞任何參數(shù)
構(gòu)造方法中直接將 elementData 初始化為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA (空數(shù)組)
*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

看到這里就發(fā)現(xiàn)，帶參的構(gòu)造器我們可以直接傳遞參數(shù)，而默認(rèn)的構(gòu)造器怎么怎么樣初始化容量大小的呢？

add() 方法可以直接得到答案。

public boolean add(E e) {
 // 這一行是關(guān)鍵, 看下面
    ensureCapacityInternal(size + 1);
    // 將元素追加到集合的末尾 假如當(dāng)前 size = 10 size++ 追加到第 11 位
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal() 方法調(diào)用

private void ensureCapacityInternal(int minCapacity) {
 /*
 calculateCapacity() 方法, 剛初始化時(shí)會(huì)返回 10, 其他情況返回當(dāng)前 size + 1
 ensureExplicitCapacity() 方法, 調(diào)用擴(kuò)容
 */
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) { 
 /*
 使用無(wú)參構(gòu)造器創(chuàng)建創(chuàng)建 ArrayList 的集合, 此時(shí)一定是相等的
 */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
     /*
     兩數(shù)相比返回最大值, 此時(shí) Math.max(10, 1); 
     默認(rèn)容量, 由此而來(lái)
     */
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 不相等的話只有返回當(dāng)前的 size + 1
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    // 增量, 記錄修改/更新次數(shù)
    modCount++;  
    
     // 初始化: 10 - 0 > 0
     // 其他: size + 1 > 0
    if (minCapacity - elementData.length > 0)
     // 擴(kuò)容操作
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // 老的長(zhǎng)度, 初始化時(shí)為 0, 
    int oldCapacity = elementData.length;
    // 新的長(zhǎng)度此時(shí) 0 + (0 >> 1), newCapacity = 0
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 初始化場(chǎng)景: 0 - 10 < 0 ? true newCapacity = 10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 初始化場(chǎng)景: 10 - 2147483639 > 0 返回 false
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     // 超大長(zhǎng)度才可以執(zhí)行這個(gè)方法, 必須大于 MAX_ARRAY_SIZE 一般不會(huì)
        newCapacity = hugeCapacity(minCapacity);
    // 復(fù)制原數(shù)組中的元素, 并擴(kuò)容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

上看說(shuō)的是初始化場(chǎng)景，下面看一下其他場(chǎng)景，也是相當(dāng)簡(jiǎn)單

private void ensureCapacityInternal(int minCapacity) {
 /*
 calculateCapacity() 方法, 正常擴(kuò)容返回 size + 1, 比如 10 + 1, 因?yàn)槟J(rèn)長(zhǎng)度為 10 當(dāng)再次新增數(shù)據(jù)時(shí)就會(huì)出發(fā)擴(kuò)容
 ensureExplicitCapacity() 方法, 調(diào)用擴(kuò)容
 */
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    /*
 elementData 不等于空數(shù)組
 返回當(dāng)前的 size + 1, 即 10 + 1 返回 11
 */
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    // 增量, 記錄修改/更新次數(shù)
    modCount++;  
    
    // 其他: 11 - 10 > 0 true, 觸發(fā)擴(kuò)容, 如果當(dāng)前下表是 5 的話 5 + 1 =6, 6 < 10 是, 此時(shí)不會(huì)出發(fā)擴(kuò)容
    if (minCapacity - elementData.length > 0)
     // 擴(kuò)容操作
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // 老的長(zhǎng)度 10
    int oldCapacity = elementData.length;
    // 新的長(zhǎng)度此時(shí) 10 + (10 >> 1), newCapacity = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 15 - 11 < 0 ? false
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 15 - 2147483639 > 0 返回 false
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     // 超大長(zhǎng)度才可以執(zhí)行這個(gè)方法, 必須大于 MAX_ARRAY_SIZE 一般不會(huì)
        newCapacity = hugeCapacity(minCapacity);
    // 復(fù)制原數(shù)組中的元素, 并擴(kuò)容 newCapacity = 15
    elementData = Arrays.copyOf(elementData, newCapacity);
}

結(jié)論

1、 觸發(fā)擴(kuò)容的關(guān)鍵是

當(dāng)前 size + 1 是否大于當(dāng)前容量，如果大于容量則證明，集合不夠用了，需要擴(kuò)容。如果小與當(dāng)前容量則證明集合還有容量不需要擴(kuò)容！

2、 每次擴(kuò)容的大小是

oldCapacity + (oldCapacity >> 1) 即: 10 + (10 >> 1)

即：當(dāng)前容量的 1.5 倍！

以上是“Java中ArrayList容量及擴(kuò)容方式的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！