上一篇我們知道了菩掏，ArrayList核心是個(gè)數(shù)組腌巾。那么鲫竞，心中肯定有個(gè)疑問：ArrayList是怎么實(shí)現(xiàn)數(shù)組的擴(kuò)容的辐怕？
先給出結(jié)論。
- 每添加一個(gè)元素从绘，檢查數(shù)組剩余空間是否足夠
- 如果第一次添加元素寄疏，就創(chuàng)建容量為10的數(shù)組
- 如果數(shù)組剩余空間不足，觸發(fā)擴(kuò)容
- 每次擴(kuò)容現(xiàn)有容量的50%
- 把舊數(shù)組內(nèi)容拷貝到新數(shù)組
- 添加新元素
這一篇我們來看看僵井，怎么得出上面這個(gè)結(jié)論的陕截。
先對arrayList添加一個(gè)元素。
arrayList.add(123);
調(diào)用如下方法：
public boolean add(E e) {
// 增加數(shù)組修改的次數(shù)
modCount++;
// 調(diào)用add私有方法進(jìn)行元素添加
add(e, elementData, size);
return true;
}
這里的modCount是啥批什？跳過去看看艘策，原來這個(gè)是繼承自AbstractList中的字段，表示數(shù)組修改的次數(shù)渊季，數(shù)組每修改一次，就要增加modCount罚渐。
還有個(gè)size又是啥却汉？跳過去看看，原來是數(shù)組包含的元素個(gè)數(shù)荷并。
接著調(diào)用了另外一個(gè)add私有方法：
private void add(E e, Object[] elementData, int s) {
// 如果數(shù)組已滿
if (s == elementData.length)
// 當(dāng)然是擴(kuò)容啦
elementData = grow();
// 還有空間或者擴(kuò)容完畢合砂，就添加元素
elementData[s] = e;
// 增加數(shù)組元素個(gè)數(shù)
size = s + 1;
}
終于找到擴(kuò)容的方法，原來叫 grow 源织。趕緊跳過去看看翩伪。
private Object[] grow() {
return grow(size + 1);
}
呃，又封了一層谈息，傳了新增元素后的個(gè)數(shù)當(dāng)參數(shù)進(jìn)去缘屹。
/**
* 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
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
作者的注釋說，這個(gè)擴(kuò)容函數(shù)保證至少擴(kuò)容到傳進(jìn)來的最小容量侠仇。
所以轻姿，minCapacity就是擴(kuò)容要求的最小容量犁珠。那么最大是多少呢？
好像這個(gè)最大容量的計(jì)算挺復(fù)雜互亮，那我們先看這個(gè)if-else犁享。
如果數(shù)組已經(jīng)有元素，那么通過ArraysSupport.newLength計(jì)算需要擴(kuò)容的大小豹休，通過Arrays.copyOf創(chuàng)建一個(gè)新的大數(shù)組炊昆，把舊的小數(shù)組拷貝過去。如果沒有新元素威根，就創(chuàng)建大小為10的數(shù)組凤巨。
噢！原來ArrayList自動(dòng)擴(kuò)容就這么回事医窿！
知道了原理后磅甩，我們就深入想想，如果頻繁的擴(kuò)容姥卢，肯定是不行的卷要。但是，一下子創(chuàng)建很大的數(shù)組独榴，又非常浪費(fèi)僧叉。那么，應(yīng)該怎么擴(kuò)容才合理呢棺榔？
我們看看如何計(jì)算每次擴(kuò)容最大容量的瓶堕。
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
- oldCapacity 是擴(kuò)容前的數(shù)組大小，這里我們假設(shè)是10症歇。
- minCapacity - oldCapacity是最小需要擴(kuò)容的大小郎笆。如果只添加一個(gè)元素，那么就是1忘晤。
- oldCapacity >>1右移一位就是除以2宛蚓，就是原來數(shù)組的50%。假設(shè)例子中10的一半就是5设塔。
那么凄吏，這個(gè)ArraysSupport.newLength是什么函數(shù)呢？跳過去看看闰蛔。
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// assert oldLength >= 0
// assert minGrowth > 0
// 最小容量與預(yù)計(jì)增長容量取較大那個(gè)痕钢，然后加上原來數(shù)組大小
int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) {
return newLength;
}
return hugeLength(oldLength, minGrowth);
}
原來，擴(kuò)容后的大小是原來的1.5倍序六。假設(shè)例子中10的1.5倍就是15任连。
當(dāng)然，代碼中還用hugeLength函數(shù)考慮到擴(kuò)容的上限难咕，是Integer.MAX_VALUE即是0x7fffffff课梳，以及超出上限會(huì)拋異常OutOfMemoryError距辆，如下圖。
到這里暮刃，我們終于知道了ArrayList自動(dòng)擴(kuò)容的邏輯：
- 每添加一個(gè)元素跨算，檢查數(shù)組剩余空間是否足夠
- 如果第一次添加元素，就創(chuàng)建容量為10的數(shù)組
- 如果數(shù)組剩余空間不足椭懊，觸發(fā)擴(kuò)容
- 每次擴(kuò)容現(xiàn)有容量的50%
- 把舊數(shù)組內(nèi)容拷貝到新數(shù)組
- 添加新元素
到這里還沒完诸蚕，我們有一個(gè)額外的問題：怎么創(chuàng)建ArrayList最合理？
- 如果少于10個(gè)氧猬，直接創(chuàng)建個(gè)空的就行背犯。
- 如果確定數(shù)組的大概數(shù)量，創(chuàng)建時(shí)候直接傳入最大的量級盅抚，或者在合適時(shí)機(jī)提前調(diào)用
ensureCapacity擴(kuò)容漠魏。這樣可以減少每次只擴(kuò)容50%多次拷貝問題。 - 當(dāng)確認(rèn)數(shù)據(jù)已經(jīng)添加完畢妄均，如有必要柱锹，可以調(diào)用
trimToSize回收多余的空間，這樣可以節(jié)省內(nèi)存空間丰包。
