通過上一篇文章的內(nèi)容冒晰，我們簡單了解了集合的框架竟块。從本章開始，我們將開始分析集合的具體的實(shí)現(xiàn)類蒋情。我們先從ArrayList開始棵癣。
ArrayList的定義
先看一下ArrayList的定義：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{}
具體分析一下：
1夺衍、繼承了AbstractList，實(shí)現(xiàn)了List接口河劝，即擁有List基本的添加、刪除及修改等等牌里。并且部分方法因?yàn)槔^承了AbstractList务甥，所以也無需重寫。
2态辛、實(shí)現(xiàn)了RandomAccess接口因妙，RandomAccess支持快速（通常是恒定時(shí)間）隨機(jī)訪問票髓。所以铣耘，ArrayList也支持快速的隨機(jī)訪問蜗细。
3、實(shí)現(xiàn)了Cloneable接口踪区，即支持clone吊骤。
4白粉、實(shí)現(xiàn)了Serializable接口，即可以序列化眷细，可以通過序列化去傳輸數(shù)據(jù)鹃祖。
注意，ArrayList是有大小的奔害，隨著列表中元素的增加地熄，它會自動擴(kuò)容。ArrayList不是線程安全的雅潭，如果多個(gè)線程同時(shí)訪問ArrayList的實(shí)例却特，并且至少有一個(gè)線程在結(jié)構(gòu)上修改了列表裂明，則必須在外部同步。
接下來扳碍，我們就通過源碼仙蛉，一步步分析一下ArrayList荠瘪。
ArrayList的源碼簡析
首先，是ArrayList的創(chuàng)建趁餐。它提供了三個(gè)構(gòu)造函數(shù)：
//構(gòu)造具有指定初始容量的空列表,初始容量可以理解為initialCapacity篮绰。
public ArrayList(int initialCapacity) {}
//構(gòu)造一個(gè)初始容量為10的空列表
public ArrayList() {}
//構(gòu)造一個(gè)包含指定集合元素的列表
public ArrayList(Collection<? extends E> c) {}
在這里阶牍，我們從無參的構(gòu)造函數(shù)入手分析。在調(diào)用了無參構(gòu)造函數(shù)后惧辈，會執(zhí)行以下代碼：
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
嗯盒齿？this.elementData是個(gè)啥？DEFAULTCAPACITY_EMPTY_ELEMENTDATA又是什么鬼边翁？趕緊去屬性聲明的地方看一下。
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
哦叨咖，就是初始化了一個(gè)空的數(shù)組甸各。
注意：elementData是存儲ArrayList元素的數(shù)組緩沖區(qū)焰坪。 ArrayList的容量是此數(shù)組緩沖區(qū)的長度某饰。
size屬性是動態(tài)數(shù)組的實(shí)際大小（接下來要用）诫尽。
欸瘟仿？空的數(shù)組比勉？那初始容量10是怎么來的浩聋？嗯。墓捻。坊夫。我們想一下，每次我們實(shí)例化完一個(gè)ArrayList之后梧兼，一般會干什么羽杰？是添加元素對吧。那我們?nèi)dd()方法里看看：
public boolean add(E e) {
//確定數(shù)組大小
ensureCapacityInternal(size + 1); // Increments modCount!!
//將新元素加入數(shù)組
elementData[size++] = e;
return true;
}
我們看到他調(diào)用了一個(gè)ensureCapacityInternal()方法惕澎，并且颜骤，傳遞了一個(gè)參數(shù)"size + 1"。那這個(gè)方法是干嘛用的忍抽，又做了些什么事梯找，我們?nèi)タ纯矗?/p>
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
//判斷當(dāng)前數(shù)組是否為默認(rèn)數(shù)組
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//取10和minCapacity的最大值作為新的數(shù)組的長度，調(diào)用無參構(gòu)造函數(shù)生成ArrayList的話驯鳖，添加第一個(gè)元素時(shí)minCapacity是1
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//根據(jù)minCapacity判斷是否要對數(shù)組擴(kuò)容
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//將修改記錄加1
modCount++
//判斷數(shù)組當(dāng)前容量是否可以容納當(dāng)前元素的個(gè)數(shù)
if (minCapacity - elementData.length > 0)
//當(dāng)前容量無法容納當(dāng)前元素的個(gè)數(shù)久免，對數(shù)組擴(kuò)容
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
//接下來的操作阎姥，就是通過一系列判斷，對數(shù)組擴(kuò)容
int oldCapacity = elementData.length;
//右移一位可以理解為除以2泽腮，所以newCapacity擴(kuò)容了oldCapacity的3/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果minCapacity(新的元素個(gè)數(shù))比newCapacity還大衣赶，則取minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//對數(shù)組擴(kuò)容，拷貝原數(shù)組中的元素碧磅，將其放到一個(gè)新的容量為newCapacity的數(shù)組中鲸郊，并返回新數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
//如果要?jiǎng)?chuàng)建的新的數(shù)組的長度小于0货邓，拋出異常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//確定新建數(shù)組的長度
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
通過分析上面的源碼，相信大家已經(jīng)知道為什么默認(rèn)長度是10了像吻。也知道了ArrayList每次擴(kuò)容都是原基礎(chǔ)的3/2。
添加第一個(gè)元素時(shí)拨匆，任何帶有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都將擴(kuò)展為DEFAULT_CAPACITY（DEFAULT_CAPACITY = 10）惭每。
modCount主要由iterator()和listIterator()方法返回的迭代器和列表迭代器實(shí)現(xiàn)使用，是從AbstractList繼承過來的一個(gè)屬性台腥，具體的后面會講黎侈。
接下來的get()和set()方法就相對容易了，請看：
public E get(int index) {
//判斷是否數(shù)組越界贴汪，數(shù)組越界就拋出異常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//返回指定位置的元素
return (E) elementData[index];
}
//
public E set(int index, E element) {
//判斷是否數(shù)組越界休吠，數(shù)組越界就拋出異常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//先用一個(gè)局部變量接收此位置的舊的元素
E oldValue = (E) elementData[index];
//在指定的位置添加新的元素瘤礁，替換舊值
elementData[index] = element;
//返回修改之前的元素
return oldValue;
}
接下來我們分析一下remove(int index)方法：
public E remove(int index) {
//判斷是否數(shù)組越界，越界則拋出異常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//數(shù)組修改次數(shù)加1
modCount++;
//獲取index位置的當(dāng)前的元素
E oldValue = (E) elementData[index];
//根據(jù)刪除的元素的角標(biāo)及數(shù)組的長度岩调，判斷要拷貝的數(shù)組長度
int numMoved = size - index - 1;
if (numMoved > 0)
//將修改后的數(shù)組拷貝到一個(gè)新的數(shù)組
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//置空方便GC工作
elementData[--size] = null;
//返回移除掉的元素
return oldValue;
}
現(xiàn)在誊辉，我們分析完了一些常用的方法亡脑。接下來霉咨，我們再看一下剛開始說的ArrayList的clone：
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
//復(fù)制數(shù)據(jù)
v.elementData = Arrays.copyOf(elementData, size);
//將操作數(shù)置為0
v.modCount = 0;
//返回克隆好的數(shù)組
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
以及序列化的讀寫：
//將ArrayList實(shí)例的狀態(tài)保存到流中（即序列化它）途戒。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 寫出數(shù)組中數(shù)據(jù)改變的次數(shù)等
int expectedModCount = modCount;
s.defaultWriteObject();
//寫出數(shù)組的容量
s.writeInt(size);
// 按正確的順序?qū)懗鏊性亍? for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
//從流中重構(gòu)ArrayList實(shí)例（即反序列化它）僵驰。
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
//讀入數(shù)組大小等
s.defaultReadObject();
// 讀入容量
s.readInt();
if (size > 0) {
//根據(jù)大小而不是容量來分配數(shù)組
ensureCapacityInternal(size);
Object[] a = elementData;
// 按正確的順序讀入所有元素
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
好了，ArrayList暫時(shí)就分析到這星爪。其他的如果需要顽腾，后續(xù)再寫。現(xiàn)在來總結(jié)一下：
1抄肖、ArrayList是通過elementData數(shù)組(Object類型)去操作數(shù)據(jù)的。這就是我們所說的裙士，ArrayList的底層是數(shù)組管毙，而且是一個(gè)動態(tài)數(shù)組。
2锅风、使用無參的構(gòu)造函數(shù)創(chuàng)建的ArrayList默認(rèn)長度為10皱埠。當(dāng)ArrayList的容量不足以容納全部的元素，ArrayList會自己擴(kuò)容：新的容量=3/2舊的容量边器。當(dāng)然忘巧，容量最大不超過0x7fffffff(是一個(gè)16進(jìn)制的數(shù)，值為：2^31 - 1十酣，是最大的int數(shù)值)际长。
3、克隆虾宇，就是將已有的元素復(fù)制到一個(gè)新的數(shù)組
4嘱朽、序列化的時(shí)候會先寫入數(shù)組改變的次數(shù)以及數(shù)組的容量，然后再寫入元素搪泳；反序列化的時(shí)候，會將數(shù)組大小即數(shù)組容量等全部讀取出來靶端，然后根據(jù)數(shù)組的大小來分配數(shù)組杨名，最后讀入所有的元素猖毫。
5、 ArrayList非線程安全趁蕊。如果有并發(fā)修改仔役，會拋出ConcurrentModificationException異常又兵。這涉及到fail-fast機(jī)制，我們后面會講到宙地。
6逆皮、每次調(diào)用add()、addAll()方法時(shí)秽梅，如果元素個(gè)數(shù)超過了數(shù)組的當(dāng)前容量辰企，ArrayList都會去擴(kuò)容，擴(kuò)容需要將舊的元素拷貝到一個(gè)新的數(shù)組。所以潜索，在可以知道最大容量的情況下臭增，最好給ArrayList一個(gè)初始的容量值誊抛。
7拗窃、ArrayList為什么改泌辫、查快震放？因?yàn)樗讓邮菙?shù)組，通過角標(biāo)就可以改變或者查詢對應(yīng)位置的元素诈铛。為什么增幢竹、刪慢恩静？是因?yàn)樵黾油善蟆h除的操作會導(dǎo)致元素從舊的數(shù)組拷貝到一個(gè)新的數(shù)組。
