知其然官边，需知其所以然⊥庥觯——古語

知其所以然注簿，需引而伸之，觸類而長之臀规；——蟲草

最近準備研究下JDK源碼滩援，把常用的一些類作個剖析整理，出個系列文章塔嬉。ArrayList應該是在開發(fā)過程中非常高頻使用的一個集合類玩徊，就先拿這個類開刀了。

筆者使用的JDK版本為：1.8.0_102谨究，由于源碼太多恩袱，有些也比較簡單，所以挑一些重點說明下胶哲。

<h3>一畔塔、整體介紹</h3>
ArrayList類如其名，是一個可以動態(tài)擴容的數組列表鸯屿，是List家族中的一員澈吨，支持隨機訪問，而且在JDK8中新支持了Stream API寄摆，使用起來還是非常方便的谅辣。不過該類不是線程安全的，所以在多線程情況下需要小心使用婶恼。

<h3>二桑阶、源碼剖析與實踐</h3>
<h4>2.1 成員變量</h4>
transient Object[] elementData;
private int size;
其中elementData即為ArrayList實現依賴的數組柏副，size為ArrayList實際包含的元素的個數。這里elementData有transient蚣录，為什么要加這個呢割择？看后面的2.5小節(jié)。

<h4>2.2 構造函數</h4>
<code>public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}</code>
這個構造函數可以直接基于collection實現構造成ArrayList萎河，具體過程是先將參數轉化成對應數組荔泳，再調用Arrays.copyOf方法進行元素的復制，而Arrays.copyOf方法實際是基于System.arraycopy這個本地方法執(zhí)行的操作虐杯。這兩個方法在ArrayList被大量用到换可，主要就是用作數組間的元素拷貝。

<b>最佳實踐：在Collection家族的集合類需要轉化成ArrayList時厦幅，不需要遍歷設值沾鳄，可以直接使用構造方法，這樣代碼清晰簡單确憨，而且性能也好些译荞。</b>

<h4>2.3 擴容方法</h4>
<code>
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_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);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
</code>

擴容方法主要看ensureCapacityInternal這個私有方法，該方法在列表添加元素時會被調用休弃，以保證數組容量足夠吞歼。其它擴容相關私有方法都是該方法去調用的。其中比較關鍵的是grow方法塔猾，參數minCapacity為即將達到的元素個數篙骡，newCapacity為舊數組容量的1.5倍，哪個值大以哪個容量為準丈甸。不過這里還需要注意的是ArrayList的最大長度也是有限制的糯俗，最大也只有Integer.MAX_VALUE，而且再設置成最大之前睦擂，還會先設置容量為MAX_ARRAY_SIZE 得湘。

為什么先設置成MAX_ARRAY_SIZE呢？這里源碼給出的注釋是MAX_ARRAY_SIZE是最大分配的數組大小顿仇，因為有些虛擬機還存儲一些頭信息在數組里淘正，數組容量分配過大可能會有OutOfMemoryError。所以其實更安全的最大數組長度是MAX_ARRAY_SIZE臼闻。當然實際情況長度很少可能這么長鸿吆。

另外這里擴容的時候為什么是原來的1.5倍呢齿坷？原因是如果擴容倍數太大绒尊，比如2.5倍，那么占用的內存會太大胆数，浪費的內存也會相應多市埋；而擴容太小黎泣，比如1.1倍，那么后期元素增加時又需要對數組重新分配內存缤谎，消耗性能抒倚。所以1.5倍是個經過測試的折衷值】涝瑁【另可參見《編寫高質量代碼》建議63】

<b>最佳實踐：由于ArrayList動態(tài)擴容的特性托呕，而且大多數情況下是擴容1.5倍，所以在已知列表容量時频敛，最好先為列表指定初始化容量项郊，這樣可以避免內存空間的浪費，以及擴容過程數組復制的性能開銷斟赚。</b>

<h4>2.4 差集與交集</h4>
<code>public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}</code>
這里removeAll方法是將在參數集合中存在的元素中從list中刪除，相當于ArrayList與集合參數c的差集拗军；而retainAll方法是將參數集合中不存在的元素中從list中刪除任洞，相當于ArrayList與集合參數c的交集。

這里兩個方法都調用的是batchRemove方法发侵，只是complement值傳的不同交掏，去判斷到底是留包含的還是不包含的。這里有邏輯很多邏輯是寫在finally的刃鳄，是為了保證contains判斷報錯時也正常執(zhí)行盅弛。另外中間有個elementData[i] = null操作，把所有用不到的元素置為null叔锐，這樣也便于垃圾回收挪鹏。

<b>最佳實踐：（1）集合之間取并集用addAll，取差集用removeAll愉烙，取交集用retainAll狰住；（2） 如果數組元素用不到可以置為空，另外在代碼里面如果用到一些的List對象齿梁，如果不用了催植，最好調用clear方法，特別是大List或循環(huán)創(chuàng)建的勺择。</b>

<h4>2.5 序列化與反序列化</h4>
<code>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 behavioural 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 {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}

}
</code>

前面介紹成員變量的時候elementData是有transient標識的创南，即elementData是不會被序列化的。那ArrayList里面的數據到底會不會序列化呢省核？上面的代碼可以看到ArrayList重寫了writeObject與readObject方法稿辙，即覆蓋了默認的序列化實現。序列化與反序列化的時候都是只序列化了List的數組中實際存在的元素气忠，所以ArrayList加transient標識的目的只是為了避免默認序列化機制把整個數組都序列化了邻储，然后自實現了序列化與反序列化方法赋咽，將真實存在的數據進行了序列化操作。

<h4>2.6 子列表</h4>
<code>public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
}
</code>
ArrayList提供了subList這個方法得到一個指定下標范圍內的子列表視圖吨娜，這里下標范圍檢查就不看了脓匿，所有的List下標相關操作都需要做個是否越界的檢查。關鍵看下SubList 這個內部類宦赠，這里限于篇幅代碼沒有貼全陪毡，重點看下這個內部類的成員變量就可以了，特別注意下parent這個是父列表勾扭，而實際上所有子列表操作中其實都是操作的父列表毡琉。

另外看下SubList 這個內部類的checkForComodification方法，子列表幾乎所有操作都會先調用checkForComodification方法妙色，這個方法主要是檢查modCount這個值是否相等桅滋，就是為了避免父列表修改的。因為父列表有修改時modCount值會增加身辨，而造成不相等虱歪，會拋出異常，所以如果得到了子列表栅表，父列表元素不能有變更操作（增刪操作）笋鄙。

<b>最佳實踐：（1）子列表的所有操作都會改變原列表，所以有些場景下想修改列表的某部分數據怪瓶，可以直接得出子列表進行修改萧落，就會修改原列表了；（2）得到子列表后洗贰，不要再直接修改原列表了找岖，否則會拋異常。</b>

<h4>2.7 Stream API</h4>
<code>public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}</code>

其中forEach方法參數為函數式方法敛滋，這里會遍歷每個數組執(zhí)行對應的操作许布。spliterator方法返回Spliterator對象，實際是一個可以并行遍歷的迭代器绎晃，ArrayList從Collection中繼承的stream方法就會用到這個方法去構造蜜唾。removeIf方法參數也會函數式方法，Predicate是個判斷條件的函數接口庶艾，條件滿足時就會將元素刪除袁余。replaceAll方法的參數也是UnaryOperator函數接口，這個接口可以執(zhí)行操作咱揍，然后將對應的元素做替換颖榜。

這里Stream API與Lamda表達式一般都關聯使用，目前對于這塊原理還不是特別清楚，所以就不展開講掩完。后期理清楚了再補充噪漾。這里附幾個看到的比較好的相關資料，有助于了解：
官方Lamda表達式教程
Stream語法詳解
為什么需要 Stream