首先看一下集合體系繼承樹
Collection接口
Collection是最基本的集合接口，一個Collection代表一組Object，即Collection的元素（Elements）。Java SDK不提供直接繼承自Collection的類，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。
如何遍歷Collection中的每一個元素？不論Collection的實際類型如何，它都支持一個iterator()的方法，該方法返回一個迭代子，使用該迭代子即可逐一訪問Collection中每一個元素。典型的用法如下：
Iterator it = collection.iterator(); // 獲得一個迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一個元素
}
讓我們轉(zhuǎn)到對框架實現(xiàn)的研究，具體的集合類遵循命名約定，并將基本數(shù)據(jù)結(jié)構(gòu)和框架接口相結(jié)合。除了四個歷史集合類外，Java 2 框架還引入了六個集合實現(xiàn)，如下表所示。關(guān)于歷史集合類如何轉(zhuǎn)換、比如說，如何修改Hashtable 并結(jié)合到框架中，請參閱歷史集合類
接口 實現(xiàn) 歷史集合類
| 接口 | 實現(xiàn) | 歷史集合 |
|---|---|---|
| List | ArrayList | Vector |
| LinkedList | Stack | |
| Set | HashSet | |
| TreeSe | ||
| Map | HashMap | Hashtable |
| TreeMap | Properties |
ArrayList的實現(xiàn)原理
一、 ArrayList概述：
1、ArrayList是基于數(shù)組實現(xiàn)的，是一個動態(tài)數(shù)組，其容量能自動增長，類似于C語言中的動態(tài)申請內(nèi)存，動態(tài)增長內(nèi)存。
2、ArrayList不是線程安全的，只能用在單線程環(huán)境下，多線程環(huán)境下可以考慮用Collections.synchronizedList(List l)函數(shù)返回一個線程安全的ArrayList類，也可以使用concurrent并發(fā)包下的CopyOnWriteArrayList類。
3、ArrayList實現(xiàn)了Serializable接口，因此它支持序列化，能夠通過序列化傳輸，實現(xiàn)了RandomAccess接口，支持快速隨機訪問，實際上就是通過下標(biāo)序號進(jìn)行快速訪問，實現(xiàn)了Cloneable接口，能被克隆。
4、每個ArrayList實例都有一個容量，該容量是指用來存儲列表元素的數(shù)組的大小。它總是至少等于列表的大小。隨著向ArrayList中不斷添加元素，其容量也自動增長。自動增長會帶來數(shù)據(jù)向新數(shù)組的重新拷貝，因此，如果可預(yù)知數(shù)據(jù)量的多少，可在構(gòu)造ArrayList時指定其容量。在添加大量元素前，應(yīng)用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量，這可以減少遞增式再分配的數(shù)量。
注意在第4項中，此實現(xiàn)不是同步的。如果多個線程同時訪問一個ArrayList實例，而其中至少一個線程從結(jié)構(gòu)上修改了列表，那么它必須保持外部同步。
二、 ArrayList的實現(xiàn)：
對于ArrayList而言，它實現(xiàn)List接口、底層使用數(shù)組保存所有元素。其操作基本上是對數(shù)組的操作。下面我們來分析ArrayList的源代碼：
1) 私有屬性：
ArrayList定義只定義類兩個私有屬性：
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
很容易理解，elementData存儲ArrayList內(nèi)的元素，size表示它包含的元素的數(shù)量。
有個關(guān)鍵字需要解釋：transient。
Java的serialization提供了一種持久化對象實例的機制。當(dāng)持久化對象時，可能有一個特殊的對象數(shù)據(jù)成員，我們不想用serialization機制來保存它。為了在一個特定對象的一個域上關(guān)閉serialization，可以在這個域前加上關(guān)鍵字transient。
有點抽象，看個例子應(yīng)該能明白。
public class UserInfo implements Serializable {
private static final long serialVersionUID = 996890129747019948L;
private String name;
private transient String psw;
public UserInfo(String name, String psw) {
this.name = name;
this.psw = psw;
}
public String toString() {
return "name=" + name + ", psw=" + psw;
}
}
public class TestTransient {
public static void main(String[] args) {
UserInfo userInfo = new UserInfo("張三", "123456");
System.out.println(userInfo);
try {
// 序列化，被設(shè)置為transient的屬性沒有被序列化
ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(
"UserInfo.out"));
o.writeObject(userInfo);
o.close();
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
try {
// 重新讀取內(nèi)容
ObjectInputStream in = new ObjectInputStream(new FileInputStream(
"UserInfo.out"));
UserInfo readUserInfo = (UserInfo) in.readObject();
//讀取后psw的內(nèi)容為null
System.out.println(readUserInfo.toString());
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
}
}
被標(biāo)記為transient的屬性在對象被序列化的時候不會被保存。
接著回到ArrayList的分析中......
2) 構(gòu)造方法：
ArrayList提供了三種方式的構(gòu)造器，可以構(gòu)造一個默認(rèn)初始容量為10的空列表、構(gòu)造一個指定初始容量的空列表以及構(gòu)造一個包含指定collection的元素的列表，這些元素按照該collection的迭代器返回它們的順序排列的。
// ArrayList帶容量大小的構(gòu)造函數(shù)。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 新建一個數(shù)組
this.elementData = new Object[initialCapacity];
}
// ArrayList無參構(gòu)造函數(shù)。默認(rèn)容量是10。
public ArrayList() {
this(10);
}
// 創(chuàng)建一個包含collection的ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
3) 元素存儲：
ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)這些添加元素的方法。下面我們一一講解：
// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于該位置上的元素。
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
// 將指定的元素添加到此列表的尾部。
public boolean add(E e) {
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
// 將指定的元素插入此列表中的指定位置。
// 如果當(dāng)前位置有元素，則向右移動當(dāng)前位于該位置的元素以及所有后續(xù)元素（將其索引加1）。
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
// 如果數(shù)組長度不足，將進(jìn)行擴容。
ensureCapacity(size+1); // Increments modCount!!
// 將 elementData中從Index位置開始、長度為size-index的元素，
// 拷貝到從下標(biāo)為index+1位置開始的新的elementData數(shù)組中。
// 即將當(dāng)前位于該位置的元素以及所有后續(xù)元素右移一個位置。
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 按照指定collection的迭代器所返回的元素順序，將該collection中的所有元素添加到此列表的尾部。
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
// 從指定的位置開始，將指定collection中的所有元素插入到此列表中。
public boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: " + index + ", Size: " + size);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(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;
}
書上都說ArrayList是基于數(shù)組實現(xiàn)的，屬性中也看到了數(shù)組，具體是怎么實現(xiàn)的呢？比如就這個添加元素的方法，如果數(shù)組大，則在將某個位置的值設(shè)置為指定元素即可，如果數(shù)組容量不夠了呢？
看到add(E e)中先調(diào)用了ensureCapacity(size+1)方法，之后將元素的索引賦給elementData[size]，而后size自增。例如初次添加時，size為0，add將elementData[0]賦值為e，然后size設(shè)置為1（類似執(zhí)行以下兩條語句elementData[0]=e;size=1）。將元素的索引賦給elementData[size]不是會出現(xiàn)數(shù)組越界的情況嗎？這里關(guān)鍵就在ensureCapacity(size+1)中了。
4) 元素讀?。?/h3>
// 返回此列表中指定位置上的元素。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
- 元素刪除：
// 返回此列表中指定位置上的元素。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
ArrayList提供了根據(jù)下標(biāo)或者指定對象兩種方式的刪除功能。如下：
romove(int index):
// 移除此列表中首次出現(xiàn)的指定元素（如果存在）。這是應(yīng)為ArrayList中允許存放重復(fù)的元素。
public boolean remove(Object o) {
// 由于ArrayList中允許存放null，因此下面通過兩種情況來分別處理。
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 類似remove(int index)，移除列表中指定位置上的元素。
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
}
首先通過代碼可以看到，當(dāng)移除成功后返回true，否則返回false。remove(Object o)中通過遍歷element尋找是否存在傳入對象，一旦找到就調(diào)用fastRemove移除對象。為什么找到了元素就知道了index，不通過remove(index)來移除元素呢？因為fastRemove跳過了判斷邊界的處理，因為找到元素就相當(dāng)于確定了index不會超過邊界，而且fastRemove并不返回被移除的元素。下面是fastRemove的代碼，基本和remove(index)一致。
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; // Let gc do its work
}
removeRange(int fromIndex,int toIndex)
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
}
執(zhí)行過程是將elementData從toIndex位置開始的元素向前移動到fromIndex，然后將toIndex位置之后的元素全部置空順便修改size。
這個方法是protected，及受保護(hù)的方法，為什么這個方法被定義為protected呢？
這是一個解釋，但是可能不容易看明白。http://stackoverflow.com/questions/2289183/why-is-javas-abstractlists-removerange-method-protected
先看下面這個例子
ArrayList<Integer> ints = new ArrayList<Integer>(Arrays.asList(0, 1, 2,
3, 4, 5, 6));
// fromIndex low endpoint (inclusive) of the subList
// toIndex high endpoint (exclusive) of the subList
ints.subList(2, 4).clear();
System.out.println(ints);
輸出結(jié)果是[0, 1, 4, 5, 6]，結(jié)果是不是像調(diào)用了removeRange(int fromIndex,int toIndex)！哈哈哈，就是這樣的。但是為什么效果相同呢？是不是調(diào)用了removeRange(int fromIndex,int toIndex)呢？
6) 調(diào)整數(shù)組容量ensureCapacity：
從上面介紹的向ArrayList中存儲元素的代碼中，我們看到，每當(dāng)向數(shù)組中添加元素時，都要去檢查添加后元素的個數(shù)是否會超出當(dāng)前數(shù)組的長度，如果超出，數(shù)組將會進(jìn)行擴容，以滿足添加數(shù)據(jù)的需求。數(shù)組擴容通過一個公開的方法ensureCapacity(int minCapacity)來實現(xiàn)。在實際添加大量元素前，我也可以使用ensureCapacity來手動增加ArrayList實例的容量，以減少遞增式再分配的數(shù)量。
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1; //增加50%+1
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
從上述代碼中可以看出，數(shù)組進(jìn)行擴容時，會將老數(shù)組中的元素重新拷貝一份到新的數(shù)組中，每次數(shù)組容量的增長大約是其原容量的1.5倍。這種操作的代價是很高的，因此在實際使用時，我們應(yīng)該盡量避免數(shù)組容量的擴張。當(dāng)我們可預(yù)知要保存的元素的多少時，要在構(gòu)造ArrayList實例時，就指定其容量，以避免數(shù)組擴容的發(fā)生。或者根據(jù)實際需求，通過調(diào)用ensureCapacity方法來手動增加ArrayList實例的容量。
Object oldData[] = elementData;//為什么要用到oldData[]
乍一看來后面并沒有用到關(guān)于oldData， 這句話顯得多此一舉！但是這是一個牽涉到內(nèi)存管理的類， 所以要了解內(nèi)部的問題。 而且為什么這一句還在if的內(nèi)部，這跟elementData = Arrays.copyOf(elementData, newCapacity); 這句是有關(guān)系的，下面這句Arrays.copyOf的實現(xiàn)時新創(chuàng)建了newCapacity大小的內(nèi)存，然后把老的elementData放入。好像也沒有用到oldData，有什么問題呢。問題就在于舊的內(nèi)存的引用是elementData， elementData指向了新的內(nèi)存塊，如果有一個局部變量oldData變量引用舊的內(nèi)存塊的話，在copy的過程中就會比較安全，因為這樣證明這塊老的內(nèi)存依然有引用，分配內(nèi)存的時候就不會被侵占掉，然后copy完成后這個局部變量的生命期也過去了，然后釋放才是安全的。不然在copy的的時候萬一新的內(nèi)存或其他線程的分配內(nèi)存侵占了這塊老的內(nèi)存，而copy還沒有結(jié)束，這將是個嚴(yán)重的事情。
關(guān)于ArrayList和Vector區(qū)別如下：
- ArrayList在內(nèi)存不夠時默認(rèn)是擴展50% + 1個，Vector是默認(rèn)擴展1倍。
- Vector提供indexOf(obj, start)接口，ArrayList沒有。
- Vector屬于線程安全級別的，但是大多數(shù)情況下不使用Vector，因為線程安全需要更大的系統(tǒng)開銷。
ArrayList還給我們提供了將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實際元素的大小的功能。它可以通過trimToSize方法來實現(xiàn)。代碼如下：
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
由于elementData的長度會被拓展，size標(biāo)記的是其中包含的元素的個數(shù)。所以會出現(xiàn)size很小但elementData.length很大的情況，將出現(xiàn)空間的浪費。trimToSize將返回一個新的數(shù)組給elementData，元素內(nèi)容保持不變，length和size相同，節(jié)省空間。
7)轉(zhuǎn)為靜態(tài)數(shù)組toArray
注意ArrayList的兩個轉(zhuǎn)化為靜態(tài)數(shù)組的toArray方法。
第一個， 調(diào)用Arrays.copyOf將返回一個數(shù)組，數(shù)組內(nèi)容是size個elementData的元素，即拷貝elementData從0至size-1位置的元素到新數(shù)組并返回。
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
第二個，如果傳入數(shù)組的長度小于size，返回一個新的數(shù)組，大小為size，類型與傳入數(shù)組相同。所傳入數(shù)組長度與size相等，則將elementData復(fù)制到傳入數(shù)組中并返回傳入的數(shù)組。若傳入數(shù)組長度大于size，除了復(fù)制elementData外，還將把返回數(shù)組的第size個元素置為空。
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
Fail-Fast機制：
ArrayList也采用了快速失敗的機制，通過記錄modCount參數(shù)來實現(xiàn)。在面對并發(fā)的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發(fā)生任意不確定行為的風(fēng)險。具體介紹請參考這篇文章深入Java集合學(xué)習(xí)系列：HashMap的實現(xiàn)原理 中的Fail-Fast機制。
總結(jié):
關(guān)于ArrayList的源碼，給出幾點比較重要的總結(jié)：
1、注意其三個不同的構(gòu)造方法。無參構(gòu)造方法構(gòu)造的ArrayList的容量默認(rèn)為10，帶有Collection參數(shù)的構(gòu)造方法，將Collection轉(zhuǎn)化為數(shù)組賦給ArrayList的實現(xiàn)數(shù)組elementData。
2、注意擴充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1個，也可能是一組）時，都要調(diào)用該方法來確保足夠的容量。當(dāng)容量不足以容納當(dāng)前的元素個數(shù)時，就設(shè)置新的容量為舊的容量的1.5倍加1，如果設(shè)置后的新容量還不夠，則直接新容量設(shè)置為傳入的參數(shù)（也就是所需的容量），而后用Arrays.copyof()方法將元素拷貝到新的數(shù)組（詳見下面的第3點）。從中可以看出，當(dāng)容量不夠時，每次增加元素，都要將原來的元素拷貝到一個新的數(shù)組中，非常之耗時，也因此建議在事先能確定元素數(shù)量的情況下，才使用ArrayList，否則建議使用LinkedList。
3、ArrayList的實現(xiàn)中大量地調(diào)用了Arrays.copyof()和System.arraycopy()方法。我們有必要對這兩個方法的實現(xiàn)做下深入的了解。
首先來看Arrays.copyof()方法。它有很多個重載的方法，但實現(xiàn)思路都是一樣的，我們來看泛型版本的源碼：
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
很明顯調(diào)用了另一個copyof方法，該方法有三個參數(shù)，最后一個參數(shù)指明要轉(zhuǎn)換的數(shù)據(jù)的類型，其源碼如下：
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)建了一個長度為newlength的數(shù)組，調(diào)用System.arraycopy()方法，將原來數(shù)組中的元素復(fù)制到了新的數(shù)組中。
下面來看System.arraycopy()方法。該方法被標(biāo)記了native，調(diào)用了系統(tǒng)的C/C++代碼，在JDK中是看不到的，但在openJDK中可以看到其源碼。該函數(shù)實際上最終調(diào)用了C語言的memmove()函數(shù)，因此它可以保證同一個數(shù)組內(nèi)元素的正確復(fù)制和移動，比一般的復(fù)制方法的實現(xiàn)效率要高很多，很適合用來批量處理數(shù)組。Java強烈推薦在復(fù)制大量數(shù)組元素時用該方法，以取得更高的效率。
4、ArrayList基于數(shù)組實現(xiàn)，可以通過下標(biāo)索引直接查找到指定位置的元素，因此查找效率高，但每次插入或刪除元素，就要大量地移動元素，插入刪除元素的效率低。
5、在查找給定元素索引值等的方法中，源碼都將該元素的值分為null和不為null兩種情況處理，ArrayList中允許元素為null。
Java集合類（二）LinkedList源碼分析
參考文章
