ArrayList是Java程序員最常用的數(shù)據(jù)結(jié)構(gòu)這句話說的一點(diǎn)都不過分，平日開發(fā)中拿來接受參數(shù)，包裝數(shù)據(jù)使用非常頻繁，但我們，因?yàn)樗褂锰唵?，以至于我們好像并不是很在意ArrayList的底層實(shí)現(xiàn)，今天我們就來看看ArrayList的源碼，以常見的面試套路來剖析它的底層原理。
面試官：你平時(shí)用ArrayList會(huì)是在那些場景，為什么用它？
我：我們一般開發(fā)時(shí)一般在接受集合類型的數(shù)據(jù)時(shí)用到，比如前端的參數(shù)，Dao層的返回值，以及業(yè)務(wù)處理集合類型的數(shù)據(jù)時(shí)用它來承載數(shù)據(jù)。因?yàn)樗奶攸c(diǎn)是有序而且查詢速度快，所以用它的頻率很高。
- 那你知道為什么它的查詢效率為什么這么快嗎？
我：因?yàn)锳rrayList底層采用的是動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，我們可以通過數(shù)組索引下標(biāo)定位元素所在的位置
- 恩，那你說說JDK1.8中ArrayList的數(shù)據(jù)結(jié)構(gòu)，以及它的添加元素的過程吧
我：JDK1.8中ArrayList提供了三個(gè)構(gòu)造函數(shù)，無參構(gòu)造默認(rèn)是指向空數(shù)組，帶參構(gòu)造可以設(shè)置指定容量的數(shù)組，初始化時(shí)就新建一個(gè)指定容量的數(shù)組。添加元素時(shí)先檢查element數(shù)組容量，如果容量不足就會(huì)擴(kuò)容，如果容量充足就在數(shù)組末尾添加元素，然后集合size++。
- 如果我創(chuàng)建ArrayList時(shí)，給定容量是20，那初始化以后它的容量是20嗎？
我：額，是的，如果構(gòu)造時(shí)指定了初始容量那么初始化時(shí)它的數(shù)組長度就是20，只不過它的size為0
// 帶參構(gòu)造，自定義容量
public ArrayList(int initialCapacity) {
// 如果指定容量大于0，那么就初始化數(shù)組，數(shù)組長度就是指定的容量大小
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果指定容量為0，那么數(shù)組默認(rèn)引用空數(shù)組對(duì)象，否則拋出異常
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
// 無參構(gòu)造,默認(rèn)引用空數(shù)組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
當(dāng)然還有一個(gè)帶參構(gòu)造：
//構(gòu)造傳入集合
public ArrayList(Collection<? extends E> c) {
// 將集合迭代為數(shù)組輸出
elementData = c.toArray();
// 如果容量為空則引用空數(shù)組對(duì)象
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 數(shù)組類型不匹配的情況發(fā)生在toArray()中，實(shí)際元素量大于預(yù)期量時(shí)，迭代產(chǎn)生新的數(shù)組
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
- 那你講講ArrayList是怎么擴(kuò)容的吧
首先它會(huì)計(jì)算出數(shù)組需要的最小容量，然后調(diào)用grow(int minCapacity)方法進(jìn)行擴(kuò)容
// 計(jì)算出最小需要的容量大小
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果當(dāng)前數(shù)組還處于空數(shù)組階段，那么判斷size+1的值也就是minCapacity和默認(rèn)初始容量10的大小，取最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 添加元素的時(shí)候會(huì)調(diào)用此方法進(jìn)行最小容量的計(jì)算
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
// 集合的變動(dòng)次數(shù)
modCount++;
//如果當(dāng)前數(shù)組的長度不足以容納最小容量的元素，那么就擴(kuò)容
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
我們進(jìn)入grow(int minCapacity)方法看看，原來此方法就是ArrayList擴(kuò)容的核心
// 擴(kuò)容機(jī)制，傳入當(dāng)前需要的最小容量大小
private void grow(int minCapacity) {
// overflow-conscious code
// 擴(kuò)容前，數(shù)組的長度
int oldCapacity = elementData.length;
// 新的數(shù)組長度 = 舊的數(shù)組長度 + 舊數(shù)組長度/2 = oldCapacity*1.5 (新數(shù)組長度為舊數(shù)組長度1.5倍) 賦值為int時(shí)向下取整
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新數(shù)組長度小于最小容量大小，則新數(shù)組長度=最小容量大小
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新數(shù)組長度大于int范圍，則返回int最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 復(fù)制一個(gè)新數(shù)組，指向原數(shù)組，完成擴(kuò)容
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 不光是ArrayList，其它集合也一樣，為什么在add或者remove方法中有一個(gè)modCount，它是拿來干什么的
我：modCount是ArrayList的抽象父類AbstractList中的一個(gè)變量，用來記錄集合機(jī)構(gòu)被修改的次數(shù)。源碼文檔中的解釋是它用來在迭代遍歷集合的時(shí)候判斷集合的修改狀態(tài)，如果在遍歷過程中發(fā)現(xiàn)modCount發(fā)生了改變，就會(huì)拋出ConcurrentModificationExceptions
- 恩，不錯(cuò)。那你再講講ArrayList的刪除元素吧
// 刪除指定位置的元素
public E remove(int index) {
// 檢查index是否越界
rangeCheck(index);
// 集合的變更次數(shù)
modCount++;
// 獲取并返回此位置的老數(shù)據(jù)
E oldValue = elementData(index);
// 元素要移動(dòng)的距離，如果numMoved>0標(biāo)識(shí)刪除的是集合內(nèi)部的元素，numMoved=0標(biāo)識(shí)刪除的是集合末尾元素，就不用移動(dòng)
int numMoved = size - index - 1;
if (numMoved > 0)
// 將index后續(xù)的元素復(fù)制到數(shù)組對(duì)象上
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 將數(shù)組末尾置為null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
其實(shí)和add(int,E)方法原理類似，根據(jù)復(fù)制一個(gè)新數(shù)組，add是將新數(shù)組追加到index后面，然后指向原數(shù)組完成添加。remove是新數(shù)組追加到index之前，然后將數(shù)組末尾置為null。
- 好，那你知道為什么集合類實(shí)現(xiàn)了Serializable接口，自己卻還要重新定義序列化方法？
我：完了，回去等通知吧，當(dāng)場領(lǐng)盒飯。
不單單是ArrayList是將容納數(shù)據(jù)的element數(shù)組用transient關(guān)鍵字修飾，其它很多集合都一樣。transient修飾的變量語義為序列化時(shí)忽略，那么集合類為什么要這樣做呢？網(wǎng)上有很多說法，有說虛擬機(jī)版本和平臺(tái)的問題，也有說容量浪費(fèi)的問題。因?yàn)榧项惗加袛U(kuò)容機(jī)制，而且每次擴(kuò)容以后容量相比以前要大很多，而一般情況下容量是撐不滿的，也意味著有大量的內(nèi)存空間被浪費(fèi)，而序列化手段是將程序?qū)ο筠D(zhuǎn)換為可轉(zhuǎn)移的二進(jìn)制文件或數(shù)據(jù)，讓然體積越小越好。
補(bǔ)充：ArrayList的克隆是淺克隆，是復(fù)制了原來的數(shù)組
clear()方法并不是將element數(shù)組置為null，而是將數(shù)組中的元素依次置為null
// 清空元素，并沒有將數(shù)組置為null，而是將數(shù)組內(nèi)每個(gè)元素置為null
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
