Java集合框架源碼解讀(1)——ArrayList、LinkedList和Vector
java.util.List接口是Java Collections Framework的一個重要組成部分，List接口的架構(gòu)圖如下：
本文將通過剖析List接口的三個實現(xiàn)類——ArrayList、LinkedList和Vector的源碼，帶你走近List的世界。
ArrayList
ArrayList是List接口可調(diào)整數(shù)組大小的實現(xiàn)。實現(xiàn)所有可選列表操作，并允許放入包括空值在內(nèi)的所有元素。每個ArrayList都有一個容量（capacity,區(qū)別于size），表示底層數(shù)組的實際大小，容器內(nèi)存儲元素的個數(shù)不能多于當前容量。
底層實現(xiàn)
java.util.ArrayList類的繼承關系如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
其中需要注意的是RandomAccess接口，這是一個標記接口，沒有定義任何具體的內(nèi)容，該接口的意義是隨機存取數(shù)據(jù)。在該接口的注釋中有這樣一段話：
/** for (int i=0, n=list.size(); i < n; i++) { list.get(i); } runs faster than this loop: for (Iterator i=list.iterator(); i.hasNext(); ) { i.next(); } **/
這說明在數(shù)據(jù)量很大的情況下，采用迭代器遍歷實現(xiàn)了該接口的集合，速度比較慢。
實現(xiàn)了RandomAccess接口的集合有：ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector等。
ArrayList一些重要的字段如下：
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;//底層數(shù)組中實際元素個數(shù)，區(qū)別于capacity
可以看到，默認第一次插入元素時創(chuàng)建數(shù)組的大小為10。當向容器中添加元素時，如果容量不足，容器會自動增加50%的容量。增加容量的函數(shù)grow()源碼如下：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//右移一位代表增加50%
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;
}
值得注意的是，由于集合框架用到了編譯器提供的語法糖——泛型，而Java泛型的內(nèi)在實現(xiàn)是通過類型擦除和類型強制轉(zhuǎn)換來進行的，其實存儲的數(shù)據(jù)類型都是Raw Type，因此集合框架的底層數(shù)組都是Object數(shù)組，可以容納任何對象。
數(shù)組復制
ArrayList的實現(xiàn)中大量地調(diào)用了Arrays.copyof()和System.arraycopy()方法。在此介紹一下這兩個方法。
System.arraycopy()方法是一個native方法，調(diào)用了系統(tǒng)的C/C++代碼，在openJDK中可以看到其源碼。該方法最終調(diào)用了C語言的memmove()函數(shù)，因此它可以保證同一個數(shù)組內(nèi)元素的正確復制和移動，比一般的復制方法的實現(xiàn)效率要高很多，很適合用來批量處理數(shù)組。Java強烈推薦在復制大量數(shù)組元素時使用該方法，以取得更高的效率。
Arrays.copyOf()方法有很多重載版本，但實現(xiàn)思路都是一樣的，其泛型版本源碼如下：
public static <T> T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass());
}
其調(diào)用了copyof()方法：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
該方法實際上是在其內(nèi)部創(chuàng)建了一個類型為newType、長度為newLength的新數(shù)組，調(diào)用System.arraycopy()方法，將原來數(shù)組中的元素復制到新的數(shù)組中。
非線程安全
ArrayList的實現(xiàn)是不同步的，如果多個線程同時訪問ArrayList實例，并且至少有一個線程修改list的結(jié)構(gòu)，那么它就必須在外部進行同步。
如果沒有這些對象， 這個list應該用Collections.synchronizedList()方法進行包裝。 最好在list的創(chuàng)建時就完成包裝，防止意外地非同步地訪問list:
List list = Collections.synchronizedList(new ArrayList(...));
除了未實現(xiàn)同步之外，ArrayList大致相當于Vector。
size(),isEmpty(),get(),set()方法均能在常數(shù)時間內(nèi)完成，add()方法的時間開銷跟插入位置有關(adding n elements requires O(n) time)，addAll()方法的時間開銷跟添加元素的個數(shù)成正比。其余方法大都是線性時間。
常用API
ArrayList常用的size(),isEmpty(),get(),set()方法實現(xiàn)都比較簡單，讀者可自行翻閱源碼，它們均能在常數(shù)時間內(nèi)完成，性能很高，這也是數(shù)組實現(xiàn)的優(yōu)勢所在。
add()方法的時間開銷跟插入位置有關(adding n elements requires O(n) time)，addAll()方法的時間開銷跟添加元素的個數(shù)成正比。其余方法大都是線性時間。
add()方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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++;
}
前者是在ArrayList尾部插入一個元素，后者是在指定位置插入元素。值得注意的是，將元素的索引賦給elementData[size]時可能會出現(xiàn)數(shù)組越界，這里的關鍵就在于ensureCapacity(size+1)的調(diào)用，這個方法的作用是確保數(shù)組的容量，它的源碼如下：
ensureCapacity()和ensureExplicitCapacity()方法：
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
其中有一個重要的實例變量modCount，它是在AbstractList類中定義的，在使用迭代器遍歷的時候，用modCount來檢查列表中的元素是否發(fā)生結(jié)構(gòu)性變化（列表元素數(shù)量發(fā)生改變）了，如果modCount值改變，則代表列表中元素發(fā)生了結(jié)構(gòu)性變化。
前面說過，ArrayList是非線程安全的，modCount主要在多線程環(huán)境下進行安全檢查，防止一個線程正在迭代遍歷，另一個線程修改了這個列表的結(jié)構(gòu)。如果在使用迭代器進行遍歷ArrayList的時候modCount值改變，則會報ConcurrentModificationException異常。
可以看出，直接在數(shù)組后面插入一個元素add(e)效率也很高，但是如果要按下標來插入元素，則需要調(diào)用System.arraycopy()方法來移動部分受影響的元素，這會導致性能低下，這也是使用數(shù)組實現(xiàn)的ArrayList的劣勢。
同理，remove()方法也會改變modCount的值，效率與按下標插入元素相似，在此不加贅述。
addAll()方法
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
addAll方法也分在末尾插入和在指定位置插入，先將入?yún)⒅械募蟘轉(zhuǎn)換成數(shù)組，根據(jù)轉(zhuǎn)換后數(shù)組的程度和ArrayList的size拓展容量，之后調(diào)用System.arraycopy()方法復制元素到相應位置，調(diào)整size。根據(jù)返回的內(nèi)容分析，只要集合c的大小不為空，即轉(zhuǎn)換后的數(shù)組長度不為0則返回true。
容易看出，addAll()方法的時間開銷是跟添加元素的個數(shù)成正比的。
trimToSize()方法
下面來看一個簡單但是很有用的方法trimToSize()。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
由于elementData的長度會被拓展，size標記的是其中包含的元素的個數(shù)。所以會出現(xiàn)size很小但elementData.length很大的情況，將出現(xiàn)空間的浪費。trimToSize()將返回一個新的數(shù)組給elementData，元素內(nèi)容保持不變，length和size相同，節(jié)省空間。
在實際應用中，考慮這樣一種情形，當某個應用需要，一個ArrayList擴容到比如size=10000，之后經(jīng)過一系列remove操作size=15，在后面的很長一段時間內(nèi)這個ArrayList的size一直保持在<100以內(nèi)，那么就造成了很大的空間浪費，這時候建議顯式調(diào)用一下trimToSize()方法，以優(yōu)化一下內(nèi)存空間。
或者在一個ArrayList中的容量已經(jīng)固定，但是由于之前每次擴容都擴充50%，所以有一定的空間浪費，可以調(diào)用trimToSize()消除這些空間上的浪費。
LinkedList
LinkedList與ArrayList一樣也實現(xiàn)了List接口，LinkedList使用雙向鏈表實現(xiàn)，允許存儲元素重復，鏈表與ArrayList的數(shù)組實現(xiàn)相比，在進行插入和刪除操作時效率更高，但查找操作效率更低，因此在實際使用中應根據(jù)自己的程序計算需求來從二者中取舍。
與ArrayList一樣，LinkedList也是非線程安全的。
底層實現(xiàn)
java.util.LinkedList的繼承關系如下：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList繼承自抽象類AbstractSequenceList，其實AbstractSequenceList已經(jīng)實現(xiàn)了List接口，這里標注出List只是更加清晰而已。AbstractSequenceList提供了List接口骨干性的實現(xiàn)以減少從而減少了實現(xiàn)受“連續(xù)訪問”數(shù)據(jù)存儲（如鏈表）支持的此接口所需的工作。對于隨機訪問數(shù)據(jù)（如數(shù)組），則應該優(yōu)先使用抽象類AbstractList。
可以看到，LinkedList除了實現(xiàn)了List接口外，還實現(xiàn)了Deque接口，Deque即“Double Ended Queue”，是可以在兩端插入和移動數(shù)據(jù)的線性數(shù)據(jù)結(jié)構(gòu)，我們熟知的棧和隊列皆可以通過實現(xiàn)Deque接口來實現(xiàn)。
因此在LinkedList的實現(xiàn)中，除了提供了列表相關的方法如add()、remove()等，還提供了棧和隊列的pop()、peek()、poll()、offer()等相關方法。這些方法中有些彼此之間只是名稱的區(qū)別，內(nèi)部實現(xiàn)完全相同，以使得這些名字在特定的上下文中顯得更加的合適。
LinkedList定義的字段如下：
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
Size代表的是鏈表中存儲的元素個數(shù)，而first和last分別代表鏈表的頭節(jié)點和尾節(jié)點。 其中Node是LinkedList定義的靜態(tài)內(nèi)部類：
private static class Node<E> {
E item;
Node<E> next
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node是鏈表的節(jié)點類，其中的三個屬性item、next、prev分別代表了節(jié)點的存儲屬性值、前繼節(jié)點和后繼節(jié)點。
常用API
add(e)方法
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
由上述代碼可見，LinkedList在表尾添加元素，只要直接修改相關節(jié)點的前后繼節(jié)點信息，而無需移動其他元素的位置，因此執(zhí)行添加操作時效率很高。此外，LinkedList也是非線程安全的
remove(o)方法
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
與add方法一樣，remove方法的底層實現(xiàn)也無需移動列表里其他元素的位置，而只需要修改被刪除節(jié)點及其前后節(jié)點的prev與next屬性即可。
get(index)方法
該方法可以返回指定位置的元素，下面來看一看代碼
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
可以看到，LinkedList要想找到index對應位置的元素，必須要遍歷整個列表，在源碼實現(xiàn)中已經(jīng)使用了二分查找（size >> 1即是除以2）的方法來進行優(yōu)化，但查找元素的開銷依然很大，并且與查找的位置有關。相比較ArrayList的常數(shù)級時間的消耗而言，差距很大。
clear()方法
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
該方法并不復雜，作用只是遍歷列表，清空表中的元素和節(jié)點連接而已。之所以單獨拿出來講，是基于GC方面的考慮，源碼注釋中講道，該方法中將所有節(jié)點之間的“連接”都斷開并不是必要的，但是由于鏈表中的不同節(jié)點可能位于分代GC的不同年代中，如果它們互相引用會給GC帶來一些額外的麻煩，因此執(zhí)行此方法斷開節(jié)點間的相互引用，可以幫助分代GC在這種情況下提高性能。
Vector
作為伴隨JDK早期誕生的容器，Vector現(xiàn)在基本已經(jīng)被棄用，不過依然有一些老版本的代碼使用到它，因此也有必要做一些了解。
Vector與ArrayList的實現(xiàn)基本相同，它們底層都是基于Object數(shù)組實現(xiàn)的，兩者最大的區(qū)別在于ArrayList是非線程安全的，而Vector是線程安全的。由于Vector與ArrayList的實現(xiàn)非常相近，前面對于ArrayList已經(jīng)進行過詳細介紹了，這里很多東西就不在贅述，重點介紹Vector與ArrayList的不同之處。
容量擴展
Vector與ArrayList還有一處細節(jié)上的不同，那就是Vector進行添加操作時，如果列表容量不夠需要擴容，每次增加的大小是原來的100%，而前面已經(jīng)講過，ArrayList一次只增加原有容量的50%。具體代碼如下：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
線程安全
Vector類內(nèi)部的大部分方法與ArrayList均相同，區(qū)別僅在于加上了synchronized關鍵字，比如：
public synchronized void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (elementCount < oldCapacity) {
elementData = Arrays.copyOf(elementData, elementCount);
}
}
這也保證了同一時刻只有一個線程能夠?qū)慥ector，避免多線程同時寫而引起的不一致性，但實現(xiàn)同步需要很高的花費，因此，訪問Vector比訪問ArrayList要慢。
前面說過，由于性能和一些設計問題，Vector現(xiàn)在基本已被棄用，當涉及到線程安全時，可以如前文介紹ArrayList時所說的，對ArrayList進行簡單包裝，即可實現(xiàn)同步。
Stack類
Vector還有一個子類叫Stack，其實現(xiàn)了棧的基本操作。這也是在JDK早期出現(xiàn)的容器，很多設計不夠規(guī)范，現(xiàn)在已經(jīng)過時，使用Queue接口的相關實現(xiàn)可以完全取代它。
總結(jié)
- ArrayList是最常用的List實現(xiàn)類，內(nèi)部是通過數(shù)組實現(xiàn)的，它允許對元素進行快速隨機訪問。數(shù)組的缺點是每個元素之間不能有間隔，當數(shù)組大小不滿足時需要增加存儲能力，就要講已經(jīng)有數(shù)組的數(shù)據(jù)復制到新的存儲空間中。當從ArrayList的中間位置插入或者刪除元素時，需要對數(shù)組進行復制、移動、代價比較高。因此，它適合隨機查找和遍歷，不適合插入和刪除。
- LinkedList是用鏈表結(jié)構(gòu)存儲數(shù)據(jù)的，很適合數(shù)據(jù)的動態(tài)插入和刪除，隨機訪問和遍歷速度比較慢。另外，他還提供了List接口中沒有定義的方法，專門用于操作表頭和表尾元素，可以當作堆棧、隊列和雙向隊列使用。
- Vector與ArrayList一樣，也是通過數(shù)組實現(xiàn)的，不同的是它支持線程的同步，即某一時刻只有一個線程能夠?qū)慥ector，避免多線程同時寫而引起的不一致性，但實現(xiàn)同步需要很高的花費，因此，訪問它比訪問ArrayList慢，現(xiàn)在基本已棄用。
