上次說(shuō)到HashMap的源碼素跺，這次來(lái)聊聊ArrayList的源碼。
歡迎大家關(guān)注我的公眾號(hào) javawebkf誉券，目前正在慢慢地將簡(jiǎn)書(shū)文章搬到公眾號(hào)指厌，以后簡(jiǎn)書(shū)和公眾號(hào)文章將同步更新，且簡(jiǎn)書(shū)上的付費(fèi)文章在公眾號(hào)上將免費(fèi)踊跟。
ArrayList踩验，顧名思義，底層是用Array即數(shù)組實(shí)現(xiàn)的商玫。下面來(lái)看看實(shí)現(xiàn)細(xì)節(jié)箕憾。
1、ArrayList中的一些屬性：
private static final int DEFAULT_CAPACITY = 10;// 默認(rèn)初始化的容量
private static final Object[] EMPTY_ELEMENTDATA = {};// 空數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 空數(shù)組
transient Object[] elementData; // 存放元素的數(shù)組
private int size;// 數(shù)組中元素的個(gè)數(shù)
2拳昌、ArrayList的初始化：
- 無(wú)參構(gòu)造器：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
沒(méi)傳 initialCapacity 的時(shí)候袭异，elementData 就是一個(gè)空數(shù)組。
- 帶參構(gòu)造器：
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);
}
}
首先判斷傳入的 initialCapacity 是否大于0炬藤，大于0就new一個(gè)長(zhǎng)度為 initialCapacity 的數(shù)組御铃；如果等于0，那么 elementData 還是空數(shù)組沈矿；如果小于0上真，直接拋異常。
那么問(wèn)題來(lái)了羹膳，空數(shù)組如何存元素谷羞？接下來(lái)看看 add 方法。
3溜徙、ArrayList的add方法：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
調(diào)用add方法的時(shí)候湃缎，首先是調(diào)用了 ensureCapacityInternal 方法。這個(gè)方法接收一個(gè)int類(lèi)型的參數(shù)蠢壹，表示的是當(dāng)前數(shù)組中的元素個(gè)數(shù)加1∩のィ現(xiàn)在是空數(shù)組，所以size就是0图贸，也就說(shuō)傳入的是1蹂季。那么接下來(lái)看看 ensureCapacityInternal里面做了什么事。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
這個(gè)方法里面又調(diào)用了兩個(gè)方法疏日，一個(gè)calculateCapacity方法偿洁，然后將calculateCapacity方法的返回值作為參數(shù)再調(diào)用ensureExplicitCapacity方法。那么我們把她的衣服一件件的脫開(kāi)沟优，先看看calculateCapacity方法做了什么涕滋。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
它首先看看當(dāng)前數(shù)組是否為空挠阁，如果為空宾肺，那么就返回DEFAULT_CAPACITY和minCapacity當(dāng)中較大的一個(gè)。DEFAULT_CAPACITY就是10侵俗，minCapacity就是剛才傳入的size + 1，也就是1增拥，所以就返回10掌栅。然后將10作為參數(shù)傳給ensureExplicitCapacity，看看里面發(fā)生了什么忘衍。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
這里有個(gè)變量自增了，這個(gè)先不管卿城，看看下面的判斷∶兜觯現(xiàn)在這個(gè)minCapacity是剛才傳入的10，數(shù)組的length是0瑟押，所以調(diào)用了grow方法搀捷。再去看看grow方法。
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);
}
這里oldCapacity 是0，newCapacity的初始值是1.5倍的oldCapacity嫩舟，所以也是0氢烘。接下來(lái)因?yàn)閚ewCapacity減minCapacity是0減10，所以小于0家厌，那么newCapacity就是10播玖。最后調(diào)用Arrays.copyOf方法，初始化數(shù)組饭于。Arrays.copyOf方法底層調(diào)用的System.arraycopy蜀踏，這是一個(gè)本地方法。它會(huì)將一個(gè)舊數(shù)組中的數(shù)據(jù)拷貝到新數(shù)組中。
這既是初始化的過(guò)程，其實(shí)也是擴(kuò)容的過(guò)程颓芭。add的時(shí)候，先將數(shù)組中的元素個(gè)數(shù)size 加 1傳給ensureCapacityInternal方法局待，如果當(dāng)前elementData為空，就是初始化吗讶，返回10燎猛，初始化一個(gè)大小為10的數(shù)組。如果elementData 不為空照皆，就返回 size + 1 的值重绷，將其傳入ensureExplicitCapacity方法，判斷size + 1的值減去當(dāng)前數(shù)組的長(zhǎng)度是否大于0膜毁。比如我現(xiàn)在elementData 的length為10昭卓，現(xiàn)在已經(jīng)存了9個(gè)元素，即size + 1等于10瘟滨，此時(shí)10減10是不大于的0候醒，不執(zhí)行g(shù)row方法。當(dāng)存了10個(gè)元素的時(shí)候杂瘸，10加1等于11倒淫，才會(huì)執(zhí)行g(shù)row方法。也就是說(shuō)败玉，當(dāng)數(shù)組滿了才會(huì)執(zhí)行擴(kuò)容操作敌土。擴(kuò)容的時(shí)候，是擴(kuò)容為當(dāng)前數(shù)組容量的1.5倍运翼，然后底層調(diào)用一個(gè)本地方法將舊數(shù)組數(shù)據(jù)轉(zhuǎn)移到新數(shù)組返干。
總結(jié)：
- 初始化：調(diào)用無(wú)參構(gòu)造初始化時(shí)只是創(chuàng)建了一個(gè)空數(shù)組，等調(diào)用add方法的時(shí)候才會(huì)調(diào)用擴(kuò)容方法血淌，初始化一個(gè)長(zhǎng)度為10的數(shù)組矩欠。
- 擴(kuò)容：當(dāng)數(shù)組中存滿了元素時(shí)，創(chuàng)建一個(gè)容量為原先的1.5倍的新數(shù)組，將元素copy到新數(shù)組的方法底層調(diào)用的是System類(lèi)的一個(gè)本地方法癌淮。
