ArrayList源碼分析
java version ： 10.0.1
1. 概覽
在IDEA中雙擊Shift鍵，調(diào)出search everywhere框，搜索ArrayList，點(diǎn)擊進(jìn)去即可閱讀源碼。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList是基于數(shù)組實(shí)現(xiàn)的，因此支持快速訪問(wèn)。繼承自AbstractList類，并實(shí)現(xiàn)了RandomAccess，Cloneable，Serializable接口。
ArrayList的默認(rèn)大小是10。private static final int DEFAULT_CAPACITY = 10
2. ArrayList擴(kuò)容
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
觀察源碼可知，向ArrayList末尾添加元素使用add(E e)函數(shù)，先將modCount加一，再添加元素到末尾，如果容量不夠還要擴(kuò)容。擴(kuò)容使用grow()函數(shù)，擴(kuò)容后容量為原數(shù)組長(zhǎng)度的1.5倍，擴(kuò)容后使用Arrays.copyOf()函數(shù)將原數(shù)組的內(nèi)容復(fù)制到新數(shù)組中。往指定位置添加元素的邏輯同上。不同的是使用arraycopy方法復(fù)制數(shù)組。
Arrays.copyOf()方法有兩個(gè)參數(shù)，第一個(gè)是原數(shù)組，第二個(gè)是新數(shù)組的長(zhǎng)度，若新數(shù)組長(zhǎng)度超過(guò)原數(shù)組，則保留原數(shù)組內(nèi)容。
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
代碼解釋:
Object src : 原數(shù)組
int srcPos : 從元數(shù)據(jù)的起始位置開(kāi)始
Object dest : 目標(biāo)數(shù)組
int destPos : 目標(biāo)數(shù)組的開(kāi)始起始位置
int length : 要copy的數(shù)組的長(zhǎng)度
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
3. ArrayList刪除元素
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
刪除指定位置元素使用arraycopy方法將待刪除元素之后的數(shù)組內(nèi)容往前移動(dòng)一個(gè)位置，此方法復(fù)雜度為O(N)。而刪除指定元素，也是先找出元素的位置，再執(zhí)行上述操作。
4. Fail-Fast機(jī)制
在AbstractList類中有一成員變量modCount，protected transient int modCount = 0。而ArrayList同樣繼承了這個(gè)成員變量。這個(gè)成員變量是用來(lái)記錄ArrayList結(jié)構(gòu)發(fā)生變化的次數(shù)的，比如添加元素或刪除元素，都會(huì)引起結(jié)構(gòu)發(fā)生變化。但是僅僅設(shè)置元素值并不算結(jié)構(gòu)發(fā)生變化。
java常用容器中Collection繼承了Iterable接口，其中的iterator()方法能夠產(chǎn)生一個(gè)Iterator對(duì)象，通過(guò)這個(gè)對(duì)象就可以迭代遍歷Collection中的元素。
從 JDK 1.5 之后可以使用 foreach 方法來(lái)遍歷實(shí)現(xiàn)了 Iterable 接口的聚合對(duì)象。
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
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();
}
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int size = ArrayList.this.size;
int i = cursor;
if (i < size) {
final Object[] es = elementData;
if (i >= es.length)
throw new ConcurrentModificationException();
for (; i < size && modCount == expectedModCount; i++)
action.accept(elementAt(es, i));
// update once at end to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
在ArrayList中，當(dāng)調(diào)用list.iterator()時(shí)，返回了一個(gè)Itr()對(duì)象，Itr是一個(gè)內(nèi)部類，實(shí)現(xiàn)了Iterator接口。其中有三個(gè)成員變量
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
cursor是遍歷集合元素的索引，lastRet是剛被訪問(wèn)的元素的索引，而expectedModCount就是Fail-Fast機(jī)制的關(guān)鍵。觀察源碼中的next方法可以看到，每次在訪問(wèn)元素之前，會(huì)調(diào)用checkForComodification方法，而此方法中會(huì)拋出ConcurrentModificationException異常。
在這段代碼中當(dāng)modCount != expectedModCount時(shí)，就會(huì)拋出異常。而expectedModCount除了在初始化時(shí)等于modCount之后，在整個(gè)遍歷過(guò)程中就沒(méi)有再發(fā)生變化，所以發(fā)生變化的只能是modCount。在前面的分析中，我們知道當(dāng)ArrayList添加或刪除元素時(shí)，集合的結(jié)構(gòu)會(huì)發(fā)生變化，modCount變量就會(huì)改變。這樣在迭代時(shí)就會(huì)拋出異常。
5. 序列化
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioral compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// like clone(), allocate array based upon size not capacity
SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
Object[] elements = new Object[size];
// Read in all elements in the proper order.
for (int i = 0; i < size; i++) {
elements[i] = s.readObject();
}
elementData = elements;
} else if (size == 0) {
elementData = EMPTY_ELEMENTDATA;
} else {
throw new java.io.InvalidObjectException("Invalid size: " + size);
}
}
ArrayList基于數(shù)組實(shí)現(xiàn)，并且具有動(dòng)態(tài)擴(kuò)容特性，因此保存元素的數(shù)組不一定都會(huì)被使用，那么就沒(méi)必要全部進(jìn)行序列化。
保存元素的數(shù)組elementData使用transient修飾，該關(guān)鍵字聲明數(shù)組默認(rèn)不會(huì)被序列化。
transient Object[] elementData; // non-private to simplify nested class access
ArrayList 實(shí)現(xiàn)了 writeObject() 和 readObject() 來(lái)控制只序列化數(shù)組中有元素填充那部分內(nèi)容。
序列化時(shí)需要使用 ObjectOutputStream 的 writeObject() 將對(duì)象轉(zhuǎn)換為字節(jié)流并輸出。而 writeObject() 方法在傳入的對(duì)象存在 writeObject() 的時(shí)候會(huì)去反射調(diào)用該對(duì)象的 writeObject() 來(lái)實(shí)現(xiàn)序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理類似。
ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);
