源碼閱讀是基于JDK7肾筐，本篇主要涉及ArrayList常用方法源碼分析哆料。
1.概述
ArrayList是List接口的可調(diào)整大小的數(shù)組實(shí)現(xiàn)，可以包含任何類型的元素吗铐，包括null东亦。除了實(shí)現(xiàn)List接口中的方法，它還提供了調(diào)整元素?cái)?shù)組大小的方法抓歼。這個類除了非同步的特性讥此，大體上和Vector是相同的。它的size谣妻、isEmpty、get卒稳、set方法運(yùn)行時間為常數(shù)蹋半，而add方法運(yùn)行開銷為分?jǐn)偟某?shù)，添加n個元素的時間復(fù)雜度是O(n)充坑。每個ArrayList的實(shí)例都有自己的容量减江，這個容量即用于存儲List元素的數(shù)組大小，它的大小要大于等于數(shù)組實(shí)際存儲的元素?cái)?shù)捻爷，當(dāng)元素被添加到ArrayList時辈灼，它的容量會自動擴(kuò)容。當(dāng)需要添加大量的元素到ArrayList中也榄，最好提前給ArrayList設(shè)置合適的初始容量巡莹，這樣可以減少增量式的內(nèi)存再分配次數(shù)司志。ArrayList的實(shí)現(xiàn)方式是非同步的(非線程安全的)，所以當(dāng)多線程同時訪問的時候降宅，如果有線程從結(jié)構(gòu)上做了修改(指任何添加或刪除一個或多個元素的操作骂远，或者顯式調(diào)整底層數(shù)組的大小，僅僅設(shè)置元素的值不是結(jié)構(gòu)上的修改)腰根，需要在使用它的地方做同步控制激才，源碼里提供了使用List list = Collections.synchronizedList(new ArrayList(...))方式做同步，這個不推薦额嘿，這種方式只是在原有方法上加了同步控制瘸恼，對于有些使用場景沒有針對性，如果真的需要線程安全的操作册养，推薦使用Vector或concurrent并發(fā)包下的CopyOnWriteArrayList东帅。
2.數(shù)據(jù)結(jié)構(gòu)
ArrayList類的聲明代碼如下，
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
由上面的代碼段可以得出如下所示的類圖捕儒，
ArrayList中聲明了如下一些屬性冰啃，
private static final int DEFAULT_CAPACITY = 10;
private transient Object[] elementData;
private int size;
protected transient int modCount = 0;
private static final Object[] EMPTY_ELEMENTDATA = {};
(1)DEFAULT_CAPACITY為默認(rèn)的初始容量，即數(shù)組的默認(rèn)大辛跤ā阎毅；
(2)elementData數(shù)組用于存儲元素；
(3)size為ArrayList中實(shí)際元素個數(shù)点弯；
(4)modCount從AbstractList繼承而來扇调，用于記錄從結(jié)構(gòu)上修改此ArrayList的次數(shù)。
(5)EMPTY_ELEMENTDATA空數(shù)組抢肛；
3.構(gòu)造方法
提供了三個構(gòu)造函數(shù)可供使用狼钮。
//initialCapacity指定初始容量大小
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
//無參構(gòu)造方法，elementData指向EMPTY_ELEMENTDATA
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
//構(gòu)造一個包含指定元素的list捡絮，這些元素的是按照Collection的迭代器返回的順序排列的
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
4.擴(kuò)容
當(dāng)添加元素的時候熬芜，檢查數(shù)組容量是否需要擴(kuò)容。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//可分配的最大數(shù)組大小(一些虛擬機(jī)保留一些字節(jié)頭福稳，所以減8)
//試圖分配較大容量的數(shù)組可能會導(dǎo)致OutOfMemoryError
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//擴(kuò)展容量的時候要確保能容納minCapacity參數(shù)指定的元素的數(shù)量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//準(zhǔn)備新擴(kuò)容的數(shù)組長度為舊容量的1.5倍
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
5.size方法
public int size() {
return size;
}
返回ArrayList中元素的個數(shù)涎拉。
6.isEmpty方法
public boolean isEmpty() {
return size == 0;
}
判斷ArrayList中元素的個數(shù)是否為0。
7.contains方法
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
從前向后遍歷elementData數(shù)組的圆，匹配第一個和o相等的元素鼓拧，如果存在返回對應(yīng)元素的下標(biāo)序號，否則返回-1越妈。這里需要注意的是o.equals(elementData[i])季俩，這里是Objetc的equals方法，比較的是引用梅掠。
8.toArray方法
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
該方法返回一個新的數(shù)組酌住，數(shù)組中的元素按照ArrayList中的第一個到最后一個順序排列店归，修改返回的數(shù)組不會影響原ArrayList中的數(shù)據(jù)。
9.get方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
10.set方法
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set方法就是給數(shù)組的指定下標(biāo)成員重新賦值赂韵。
11.add方法
//首先進(jìn)行擴(kuò)容(是否擴(kuò)容由ensureCapacityInternal方法決定)
//給數(shù)組的size++位置賦值為e
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//檢查給定的index是否正確
//進(jìn)行擴(kuò)容(是否擴(kuò)容由ensureCapacityInternal方法決定)
//index位置后面的元素向后移動(數(shù)組復(fù)制實(shí)現(xiàn))
//給index下標(biāo)成員重新賦值
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
12.remove方法
//刪除指定位置的元素
//原理：將index+1位置開始到末尾的元素向前移動一位娱节，最后一位賦值為null，GC進(jìn)行回收
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
//刪除指定內(nèi)容的元素祭示，刪除匹配的第一個元素
//原理：將匹配的第一個元素的位置下標(biāo)加1開始到末尾的元素向前移動一位肄满，最后一位賦值為null，GC進(jìn)行回收
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//將index+1位置開始到末尾的元素向前移動一位质涛，最后一位賦值為null稠歉，GC進(jìn)行回收
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
13.clear方法
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
將數(shù)組所有元素引用設(shè)置了null，ArrayList的元素個數(shù)置為0汇陆；
14.iterator方法和listIterator方法
//返回Iterator用于遍歷ArrayList
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // 下一個元素的索引下標(biāo)
int lastRet = -1; // 最后一個元素的下標(biāo)怒炸，如果不存在則返回-1
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
//從index下標(biāo)開始返回一個ListIterator
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
在執(zhí)行iterator或listIterator方法時，如果有線程從結(jié)構(gòu)上做了修改(指任何添加或刪除一個或多個元素的操作毡代，或者顯式調(diào)整底層數(shù)組的大小阅羹，僅僅設(shè)置元素的值不是結(jié)構(gòu)上的修改)，這兩個方法會fail-fast教寂，將會拋出ConcurrentModificationException捏鱼。迭代器的快速失敗行為無法得到保證，因?yàn)橐话銇碚f酪耕，不可能對是否出現(xiàn)不同步并發(fā)修改做出任何硬性保證导梆。快速失敗操作會盡最大努力拋出ConcurrentModificationException迂烁。因此看尼，為提高此類操作的正確性而編寫一個依賴于此異常的程序是錯誤的做法，正確做法是：ConcurrentModificationException應(yīng)該僅用于檢測bug盟步。拋異常就是為了避免數(shù)據(jù)問題而存在的藏斩，其實(shí)就是檢查modCount是否是期望值，如果不是却盘，則說明ArrayList數(shù)組被從結(jié)構(gòu)上修改了灾茁。這里是經(jīng)常會遇到的問題，使用Java的For Each方式遍歷元素時刪除匹配的元素谷炸，會拋出ConcurrentModificationException。Java中的For Each實(shí)際上使用的是iterator進(jìn)行處理的禀挫，而iterator是不允許集合在iterator使用期間刪除的旬陡。
小結(jié)：
1.ArrayList是實(shí)現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)。
2.ArrayList在每次增加元素時语婴，都要進(jìn)行擴(kuò)容判斷描孟，擴(kuò)容時都要確保足夠的容量驶睦。當(dāng)容量不足以容納當(dāng)前的元素個數(shù)時，就設(shè)置新的容量為舊的容量的1.5倍匿醒，如果新容量還不夠场航，則新容量設(shè)置為傳入的參數(shù)，如果新容量還不夠廉羔，則新容量為最大容量溉痢。從中可以看出，當(dāng)容量不夠時憋他，都要將原來的元素拷貝到一個新的數(shù)組中孩饼，耗時而且還需要重新分配內(nèi)存，因此建議在事先能確定元素?cái)?shù)量的情況下竹挡，明確指明容量大小镀娶。
3.ArrayList基于數(shù)組實(shí)現(xiàn)，可以通過下標(biāo)索引直接查找到指定位置的元素揪罕，因此查找效率高梯码，但每次插入或刪除元素，就要大量地移動元素好啰，效率低轩娶。
