基于ArrayList初始化長度的作用及影響

更新時間：2023年03月13日 17:17:56 作者：不負(fù)好時光?

這篇文章主要介紹了基于ArrayList初始化長度的作用及影響，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

一、有無初始容量的區(qū)別

?? ?/**
? ? ?* 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;
? ??
?? ?/**
? ? ?* Default initial capacity.
? ? ?*/
? ? private static final int DEFAULT_CAPACITY = 10;

?? ?/**
? ? ?* The array buffer into which the elements of the ArrayList are stored.
? ? ?* The capacity of the ArrayList is the length of this array buffer. Any
? ? ?* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
? ? ?* will be expanded to DEFAULT_CAPACITY when the first element is added.
? ? ?*/
? ? transient Object[] elementData; // non-private to simplify nested class access

?? ?/**
? ? ?* Shared empty array instance used for empty instances.
? ? ?*/
? ? private static final Object[] EMPTY_ELEMENTDATA = {};?? ?

?? ?/**
? ? ?* Constructs an empty list with the specified initial capacity.
? ? ?*
? ? ?* @param ?initialCapacity ?the initial capacity of the list
? ? ?* @throws IllegalArgumentException if the specified initial capacity
? ? ?* ? ? ? ? is negative
? ? ?*/
? ? 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);
? ? ? ? }
? ? }

?? ?/**
? ? ?* 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);
? ? }

以上是JDK1.8的ArrayList源碼，可以看出，

沒有初始容量的話，在做數(shù)據(jù)操作的時候ArrayList會自己創(chuàng)建容量，JDK1.8默認(rèn)為10
每次擴(kuò)容后容量為oldCapacity + (oldCapacity >> 1)
容量最大值Integer.MAX_VALUE - 8

由此可以想到，如果存在上千上萬數(shù)據(jù)量的操作，不初始容量和初始化了合適的容量，處理時間肯定不同，因為初始化和擴(kuò)容是需要時間的。

測試代碼如下：

public static void main(String[] args) {
? ? final int count = 200 * 10000;
? ? List<Integer> list = new ArrayList<>();
? ? long begin = System.currentTimeMillis();
? ? for(int i = 0; i < count ; i++) {
? ? ? ? list.add(i);
? ? }
? ? System.out.println("沒有設(shè)置ArrayList初始容量： " + (System.currentTimeMillis() - begin) + " ms");

? ? List<Integer> list2 = new ArrayList<>(10);
? ? long begin2 = System.currentTimeMillis();
? ? for(int i = 0; i < count ; i++) {
? ? ? ? list2.add(i);
? ? }
? ? System.out.println("設(shè)置了ArrayList初始容量： " + (System.currentTimeMillis() - begin2) + " ms");
}

輸出：

沒有設(shè)置ArrayList初始容量： 96 ms
設(shè)置了ArrayList初始容量： 26 ms

分析：

在list.add()方法執(zhí)行時，先調(diào)用ArrayList的：

/**
?* Appends the specified element to the end of this list.
?*
?* @param e element to be appended to this list
?* @return <tt>true</tt> (as specified by {@link Collection#add})
?*/
public boolean add(E e) {
? ? ensureCapacityInternal(size + 1); ?// Increments modCount!!
? ? elementData[size++] = e;
? ? return true;
}

進(jìn)入方法：

private void ensureCapacityInternal(int minCapacity) {
? ? ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

再往下：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
? ? if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// 第一次add的時候，都會走這一步
? ? ? ? return Math.max(DEFAULT_CAPACITY, minCapacity);//初始化容量小于默認(rèn)值10都會取10，反之取自定義的容量
? ? }
? ? return minCapacity;
}

擴(kuò)容方法：

private void ensureExplicitCapacity(int minCapacity) {
? ? modCount++;

? ? // overflow-conscious code
? ? if (minCapacity - elementData.length > 0)
? ? ? ? grow(minCapacity);
}

grow():

/**
?* 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) {//minCapacity是當(dāng)前容量，比如，默認(rèn)容量下，add一次后就是10+1
? ? // 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);
}

總結(jié)：

建議初始化容量，減少系統(tǒng)初始化容量的耗時；
初始化容量不是越大越好，跟系統(tǒng)配置相關(guān)，因為要開辟內(nèi)存。如果能確定add的總數(shù)，以總數(shù)作為初始容量效率最高，但這種場景太少了。最佳的設(shè)置要兼顧內(nèi)存空間和擴(kuò)容次數(shù)，我也沒有找到最優(yōu)解，歡迎大佬補(bǔ)充。
盡管不知道初始化多少最快，但是初始化比未初始化快，并且有限的數(shù)據(jù)量下，設(shè)置不同initialCapacity的差距不大。最終，我建議大家初始化容量，并且就寫10（<=10都一樣，看自己喜好）。

上例不同大小初始容量的耗時：

initialCapacity	time
未初始化	96
<=10	26
100	26
1000	23
10000	648
100000	24
1000000	18
10000000	609

二、initialCapacity != list.size()

public static void main(String[] args) {
? ? List<Integer> list = new ArrayList<>(10);
? ? list.set(0, 666);
}

console:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
   at java.util.ArrayList.rangeCheck(ArrayList.java:657)
   at java.util.ArrayList.set(ArrayList.java:448)
   at top.chengsw.demo.test.ListTest.main(ListTest.java:25)

此時，list.size() = 0。

也就是說，該構(gòu)造方法并不是將ArrayList()初始化為指定長度，而是指定了其內(nèi)部的Object數(shù)組的長度，也就是其容量。

當(dāng)我們調(diào)用size()時，返回的是其實際長度，而非容量大小。

對超出ArrayList長度的部分進(jìn)行訪問或賦值操作時也會造成訪問越界，盡管它的容量大小足夠。