Java集合---ArrayList的實現原(yuan)理
目錄：
5) 元素刪除
6) 調整數組容量
7)轉為靜態數組toArray
ArrayList是基(ji)于數組實現的，是一(yi)個動態(tai)數組，其容量能自(zi)動增長(chang)，類似于C語言中(zhong)的動態(tai)申請內存(cun)，動態(tai)增長(chang)內存(cun)。
ArrayList不(bu)是線(xian)程安全(quan)的(de)，只能用(yong)在單線(xian)程環境下，多線(xian)程環境下可以考慮用(yong)Collections.synchronizedList(List l)函數返(fan)回一個線(xian)程安全(quan)的(de)ArrayList類，也可以使用(yong)concurrent并(bing)發包下的(de)CopyOnWriteArrayList類。
ArrayList實現了(le)(le)Serializable接口(kou)，因此它支持序列化(hua)，能(neng)夠通過(guo)序列化(hua)傳輸(shu)，實現了(le)(le)RandomAccess接口(kou)，支持快速隨機訪問(wen)，實際(ji)上就是(shi)通過(guo)下標序號進(jin)行快速訪問(wen)，實現了(le)(le)Cloneable接口(kou)，能(neng)被克隆。
每個(ge)ArrayList實例都有一個(ge)容(rong)量(liang)(liang)，該容(rong)量(liang)(liang)是(shi)(shi)指用來(lai)(lai)存儲列表(biao)(biao)元(yuan)(yuan)素的(de)(de)數(shu)組的(de)(de)大(da)小。它總是(shi)(shi)至(zhi)少等于列表(biao)(biao)的(de)(de)大(da)小。隨(sui)著向ArrayList中不斷添(tian)加元(yuan)(yuan)素，其容(rong)量(liang)(liang)也自動(dong)增(zeng)(zeng)長。自動(dong)增(zeng)(zeng)長會(hui)帶(dai)來(lai)(lai)數(shu)據(ju)向新(xin)數(shu)組的(de)(de)重新(xin)拷貝，因此，如果可(ke)預知(zhi)數(shu)據(ju)量(liang)(liang)的(de)(de)多少，可(ke)在(zai)構(gou)造(zao)ArrayList時指定其容(rong)量(liang)(liang)。在(zai)添(tian)加大(da)量(liang)(liang)元(yuan)(yuan)素前，應用程序也可(ke)以(yi)使用ensureCapacity操(cao)作來(lai)(lai)增(zeng)(zeng)加ArrayList實例的(de)(de)容(rong)量(liang)(liang)，這(zhe)可(ke)以(yi)減少遞增(zeng)(zeng)式再分配的(de)(de)數(shu)量(liang)(liang)。
注意(yi)，此實現不(bu)是同(tong)步(bu)的。如果多個線程(cheng)同(tong)時訪(fang)問一(yi)個ArrayList實例(li)，而其中至少一(yi)個線程(cheng)從結構上修改了列(lie)表，那(nei)么(me)它必(bi)須保(bao)持外(wai)部同(tong)步(bu)。
對(dui)于ArrayList而言(yan)，它實現List接口、底層(ceng)使用數組保存所有元素。其操作基本上是對(dui)數組的操作。下面(mian)我(wo)們來分析(xi)ArrayList的源(yuan)代碼：
ArrayList定義只定義類(lei)兩個(ge)私(si)有屬性：
/**
* 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內(nei)的(de)元素，size表示它包含的(de)元素的(de)數量。
有個關鍵字需要解釋：transient。
Java的serialization提供了一種持久化對象實例的機制。當持久化對象時，可能有一個特殊的對象數據成員，我們不想用serialization機制來保存它。為了在一個特定對象的一個域上關閉serialization，可以在這個域前加上關鍵字transient。
有點抽象，看個例(li)子應該能明白。
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("張(zhang)三", "123456");
System.out.println(userInfo);
try {
// 序列(lie)化，被設置為(wei)transient的屬性沒有(you)被序列(lie)化
ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(
"UserInfo.out"));
o.writeObject(userInfo);
o.close();
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
try {
// 重新讀取(qu)內容(rong)
ObjectInputStream in = new ObjectInputStream(new FileInputStream(
"UserInfo.out"));
UserInfo readUserInfo = (UserInfo) in.readObject();
//讀取(qu)后psw的內容為null
System.out.println(readUserInfo.toString());
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
}
}
被(bei)標記(ji)為(wei)transient的屬(shu)性在對象被(bei)序(xu)列化的時候不(bu)會被(bei)保存。
接著回到ArrayList的(de)分析中......
2) 構造方法：
ArrayList提供了三種方式的(de)(de)構(gou)(gou)造器，可以(yi)構(gou)(gou)造一(yi)個默認初始容量(liang)為10的(de)(de)空列(lie)表(biao)、構(gou)(gou)造一(yi)個指定(ding)初始容量(liang)的(de)(de)空列(lie)表(biao)以(yi)及構(gou)(gou)造一(yi)個包(bao)含(han)指定(ding)collection的(de)(de)元素的(de)(de)列(lie)表(biao)，這些元素按照該collection的(de)(de)迭代(dai)器返回它們的(de)(de)順序排列(lie)的(de)(de)。
// ArrayList帶容量大小的(de)構(gou)造函(han)數(shu)。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 新建(jian)一個數組
this.elementData = new Object[initialCapacity];
}
// ArrayList無參構造(zao)函數。默(mo)認容量是10。
public ArrayList() {
this(10);
}
// 創建一個包含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);
}
ArrayList提(ti)供(gong)了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)這些添加元素的方法。下面我們一(yi)一(yi)講解：
20 // 用(yong)指(zhi)定的元素(su)替(ti)代此列表中指(zhi)定位(wei)置上(shang)(shang)的元素(su)，并返(fan)回以前位(wei)于該位(wei)置上(shang)(shang)的元素(su)。
21 public E set(int index, E element) {
22 RangeCheck(index);
23
24 E oldValue = (E) elementData[index];
25 elementData[index] = element;
26 return oldValue;
27 }
28 // 將(jiang)指定的元(yuan)素(su)添加到(dao)此列表(biao)的尾部。
29 public boolean add(E e) {
30 ensureCapacity(size + 1);
31 elementData[size++] = e;
32 return true;
33 }
34 // 將指(zhi)(zhi)定的(de)元素插入(ru)此列(lie)表中的(de)指(zhi)(zhi)定位置(zhi)。
35 // 如果當(dang)前位置(zhi)有(you)元(yuan)(yuan)素(su)，則向(xiang)右移動當(dang)前位于該位置(zhi)的元(yuan)(yuan)素(su)以及所有(you)后續元(yuan)(yuan)素(su)（將其索引加1）。
36 public void add(int index, E element) {
37 if (index > size || index < 0)
38 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
39 // 如果數組長度不足，將進行擴容。
40 ensureCapacity(size+1); // Increments modCount!!
41 // 將(jiang) elementData中從Index位置(zhi)開始(shi)、長度(du)為size-index的(de)元素，
42 // 拷(kao)貝到從下標為index+1位置開始的(de)新(xin)的(de)elementData數組中(zhong)。
43 // 即將(jiang)當前位于該位置的元素(su)以及所有后續元素(su)右移一個位置。
44 System.arraycopy(elementData, index, elementData, index + 1, size - index);
45 elementData[index] = element;
46 size++;
47 }
48 // 按照(zhao)指(zhi)定collection的迭(die)代(dai)器(qi)所返回(hui)的元素(su)順序(xu)，將該collection中的所有元素(su)添加到此(ci)列表的尾部。
49 public boolean addAll(Collection<? extends E> c) {
50 Object[] a = c.toArray();
51 int numNew = a.length;
52 ensureCapacity(size + numNew); // Increments modCount
53 System.arraycopy(a, 0, elementData, size, numNew);
54 size += numNew;
55 return numNew != 0;
56 }
57 // 從指定(ding)的(de)位置開始，將指定(ding)collection中的(de)所有元素插入到(dao)此列(lie)表中。
58 public boolean addAll(int index, Collection<? extends E> c) {
59 if (index > size || index < 0)
60 throw new IndexOutOfBoundsException(
61 "Index: " + index + ", Size: " + size);
62
63 Object[] a = c.toArray();
64 int numNew = a.length;
65 ensureCapacity(size + numNew); // Increments modCount
66
67 int numMoved = size - index;
68 if (numMoved > 0)
69 System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
70
71 System.arraycopy(a, 0, elementData, index, numNew);
72 size += numNew;
73 return numNew != 0;
}
書上(shang)都說ArrayList是(shi)基于數組實現(xian)的(de)，屬(shu)性中也看(kan)到(dao)了(le)數組，具(ju)體是(shi)怎么實現(xian)的(de)呢？比如(ru)就這(zhe)個添加(jia)元素(su)的(de)方法，如(ru)果數組大，則在將某個位置(zhi)的(de)值設(she)置(zhi)為指定元素(su)即(ji)可，如(ru)果數組容(rong)量不夠了(le)呢？
看到add(E e)中先(xian)調用了ensureCapacity(size+1)方法，之后將元素的(de)索(suo)引賦給(gei)(gei)elementData[size]，而后size自增(zeng)。例如初次添加時，size為0，add將elementData[0]賦值為e，然后size設置(zhi)為1（類似執行以下兩條語句elementData[0]=e;size=1）。將元素的(de)索(suo)引賦給(gei)(gei)elementData[size]不是會出現數組越界的(de)情況嗎？這里關鍵就在ensureCapacity(size+1)中了。
// 返回此列(lie)表(biao)中指定位置上的元素(su)。
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
ArrayList提供了(le)根據下標(biao)或(huo)者指定對象兩種方式的刪除功能。如下：
romove(int index):
1 // 移(yi)除此列表中指定位置(zhi)上的元素。
2 public E remove(int index) {
3 RangeCheck(index);
4
5 modCount++;
6 E oldValue = (E) elementData[index];
7
8 int numMoved = size - index - 1;
9 if (numMoved > 0)
10 System.arraycopy(elementData, index+1, elementData, index, numMoved);
11 elementData[--size] = null; // Let gc do its work
12
13 return oldValue;
14 }
首先是檢查(cha)范圍，修(xiu)改modCount，保留將要被移(yi)(yi)除的(de)元素，將移(yi)(yi)除位置之后(hou)的(de)元素向前挪動一(yi)個(ge)位置，將list末(mo)尾(wei)元素置空（null），返回被移(yi)(yi)除的(de)元素。
remove(Object o)
1 // 移除(chu)此列表(biao)中(zhong)首次出現的指定元素（如果(guo)存(cun)在）。這是應為ArrayList中(zhong)允許(xu)存(cun)放重(zhong)復的元素。
2 public boolean remove(Object o) {
3 // 由(you)于ArrayList中允許(xu)存(cun)放(fang)null，因此下面通過兩(liang)種情況來分別處(chu)理。
4 if (o == null) {
5 for (int index = 0; index < size; index++)
6 if (elementData[index] == null) {
7 // 類(lei)似remove(int index)，移除列表中指(zhi)定位置上的元素。
8 fastRemove(index);
9 return true;
10 }
11 } else {
12 for (int index = 0; index < size; index++)
13 if (o.equals(elementData[index])) {
14 fastRemove(index);
15 return true;
16 }
17 }
18 return false;
19 }
20 }
首先通過代(dai)(dai)碼可以看(kan)到(dao)(dao)，當移(yi)除成功后返(fan)回(hui)true，否(fou)則(ze)返(fan)回(hui)false。remove(Object o)中通過遍歷(li)element尋找(zhao)(zhao)是否(fou)存在傳入對(dui)象，一旦找(zhao)(zhao)到(dao)(dao)就(jiu)調用fastRemove移(yi)除對(dui)象。為什么找(zhao)(zhao)到(dao)(dao)了元素(su)(su)就(jiu)知道了index，不(bu)通過remove(index)來移(yi)除元素(su)(su)呢？因(yin)為fastRemove跳過了判斷邊界的(de)處理(li)，因(yin)為找(zhao)(zhao)到(dao)(dao)元素(su)(su)就(jiu)相當于確定了index不(bu)會超過邊界，而且fastRemove并(bing)不(bu)返(fan)回(hui)被(bei)移(yi)除的(de)元素(su)(su)。下(xia)面(mian)是fastRemove的(de)代(dai)(dai)碼，基本和remove(index)一致。
1 private void fastRemove(int index) {
2 modCount++;
3 int numMoved = size - index - 1;
4 if (numMoved > 0)
5 System.arraycopy(elementData, index+1, elementData, index,
6 numMoved);
7 elementData[--size] = null; // Let gc do its work
8 }
removeRange(int fromIndex,int toIndex)
1 protected void removeRange(int fromIndex, int toIndex) {
2 modCount++;
3 int numMoved = size - toIndex;
4 System.arraycopy(elementData, toIndex, elementData, fromIndex,
5 numMoved);
6
7 // Let gc do its work
8 int newSize = size - (toIndex-fromIndex);
9 while (size != newSize)
10 elementData[--size] = null;
11 }
執行過(guo)程是將(jiang)elementData從toIndex位置(zhi)開(kai)始(shi)的元(yuan)素向前(qian)移動到fromIndex，然后(hou)將(jiang)toIndex位置(zhi)之后(hou)的元(yuan)素全部置(zhi)空順便修(xiu)改size。
;這(zhe)個(ge)方(fang)法(fa)是protected，及受保護的方(fang)法(fa)，為什(shen)么這(zhe)個(ge)方(fang)法(fa)被定義為protected呢？
這是一個解(jie)釋，但是可能不容易看明白。//stackoverflow.com/questions/2289183/why-is-javas-abstractlists-removerange-method-protected
先看下面(mian)這個(ge)例子
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);
輸出結果(guo)是(shi)(shi)(shi)[0, 1, 4, 5, 6]，結果(guo)是(shi)(shi)(shi)不(bu)是(shi)(shi)(shi)像調(diao)用了removeRange(int fromIndex,int toIndex)！哈哈哈，就(jiu)是(shi)(shi)(shi)這樣(yang)的。但(dan)是(shi)(shi)(shi)為什么(me)效果(guo)相同呢？是(shi)(shi)(shi)不(bu)是(shi)(shi)(shi)調(diao)用了removeRange(int fromIndex,int toIndex)呢？
從上面介紹的(de)(de)向ArrayList中存儲(chu)元(yuan)素的(de)(de)代(dai)碼中，我們(men)看到，每當(dang)向數(shu)組(zu)中添(tian)加元(yuan)素時(shi)，都(dou)要去檢查添(tian)加后元(yuan)素的(de)(de)個數(shu)是否會超出(chu)當(dang)前數(shu)組(zu)的(de)(de)長度，如果超出(chu)，數(shu)組(zu)將會進行擴容(rong)，以滿足添(tian)加數(shu)據的(de)(de)需求。數(shu)組(zu)擴容(rong)通過(guo)一個公(gong)開的(de)(de)方法ensureCapacity(int minCapacity)來(lai)實(shi)(shi)現。在實(shi)(shi)際添(tian)加大量元(yuan)素前，我也可以使用(yong)ensureCapacity來(lai)手動增加ArrayList實(shi)(shi)例(li)的(de)(de)容(rong)量，以減(jian)少遞(di)增式再分(fen)配的(de)(de)數(shu)量。
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);
}
}
從上(shang)述代(dai)碼中(zhong)(zhong)可以(yi)看出，數(shu)組(zu)進行擴容(rong)時(shi)，會將老數(shu)組(zu)中(zhong)(zhong)的(de)(de)(de)(de)元素(su)重新拷(kao)貝(bei)一份(fen)到新的(de)(de)(de)(de)數(shu)組(zu)中(zhong)(zhong)，每次數(shu)組(zu)容(rong)量(liang)(liang)的(de)(de)(de)(de)增(zeng)長大約是其原容(rong)量(liang)(liang)的(de)(de)(de)(de)1.5倍。這種操作的(de)(de)(de)(de)代(dai)價是很(hen)高的(de)(de)(de)(de)，因此在實際使用時(shi)，我(wo)們(men)應該盡(jin)量(liang)(liang)避免數(shu)組(zu)容(rong)量(liang)(liang)的(de)(de)(de)(de)擴張。當我(wo)們(men)可預(yu)知要保存的(de)(de)(de)(de)元素(su)的(de)(de)(de)(de)多少時(shi)，要在構造ArrayList實例(li)時(shi)，就指(zhi)定其容(rong)量(liang)(liang)，以(yi)避免數(shu)組(zu)擴容(rong)的(de)(de)(de)(de)發生。或者根(gen)據實際需求，通(tong)過調用ensureCapacity方法來(lai)手(shou)動增(zeng)加ArrayList實例(li)的(de)(de)(de)(de)容(rong)量(liang)(liang)。
Object oldData[] = elementData;//為什么要用到oldData[]
乍一看來后(hou)面并沒有用(yong)(yong)(yong)到關于oldData， 這(zhe)句(ju)(ju)話(hua)(hua)顯得多此(ci)一舉(ju)！但(dan)是(shi)(shi)(shi)這(zhe)是(shi)(shi)(shi)一個(ge)(ge)牽(qian)涉到內(nei)(nei)(nei)(nei)存(cun)管理的(de)(de)(de)(de)類(lei)， 所以要了(le)(le)解內(nei)(nei)(nei)(nei)部的(de)(de)(de)(de)問題(ti)。 而且為(wei)什么這(zhe)一句(ju)(ju)還在if的(de)(de)(de)(de)內(nei)(nei)(nei)(nei)部，這(zhe)跟elementData = Arrays.copyOf(elementData, newCapacity); 這(zhe)句(ju)(ju)是(shi)(shi)(shi)有關系的(de)(de)(de)(de)，下(xia)面這(zhe)句(ju)(ju)Arrays.copyOf的(de)(de)(de)(de)實(shi)現(xian)時新創建(jian)了(le)(le)newCapacity大(da)小的(de)(de)(de)(de)內(nei)(nei)(nei)(nei)存(cun)，然后(hou)把老(lao)的(de)(de)(de)(de)elementData放入。好像也沒有用(yong)(yong)(yong)到oldData，有什么問題(ti)呢(ni)。問題(ti)就在于舊的(de)(de)(de)(de)內(nei)(nei)(nei)(nei)存(cun)的(de)(de)(de)(de)引(yin)用(yong)(yong)(yong)是(shi)(shi)(shi)elementData， elementData指向(xiang)了(le)(le)新的(de)(de)(de)(de)內(nei)(nei)(nei)(nei)存(cun)塊，如果(guo)有一個(ge)(ge)局部變(bian)(bian)量oldData變(bian)(bian)量引(yin)用(yong)(yong)(yong)舊的(de)(de)(de)(de)內(nei)(nei)(nei)(nei)存(cun)塊的(de)(de)(de)(de)話(hua)(hua)，在copy的(de)(de)(de)(de)過(guo)(guo)程中就會(hui)(hui)比較安(an)全(quan)，因為(wei)這(zhe)樣證(zheng)明這(zhe)塊老(lao)的(de)(de)(de)(de)內(nei)(nei)(nei)(nei)存(cun)依(yi)然有引(yin)用(yong)(yong)(yong)，分配內(nei)(nei)(nei)(nei)存(cun)的(de)(de)(de)(de)時候就不(bu)會(hui)(hui)被侵占掉，然后(hou)copy完成后(hou)這(zhe)個(ge)(ge)局部變(bian)(bian)量的(de)(de)(de)(de)生(sheng)命期也過(guo)(guo)去了(le)(le)，然后(hou)釋放才是(shi)(shi)(shi)安(an)全(quan)的(de)(de)(de)(de)。不(bu)然在copy的(de)(de)(de)(de)的(de)(de)(de)(de)時候萬一新的(de)(de)(de)(de)內(nei)(nei)(nei)(nei)存(cun)或其他線程的(de)(de)(de)(de)分配內(nei)(nei)(nei)(nei)存(cun)侵占了(le)(le)這(zhe)塊老(lao)的(de)(de)(de)(de)內(nei)(nei)(nei)(nei)存(cun)，而copy還沒有結束(shu)，這(zhe)將是(shi)(shi)(shi)個(ge)(ge)嚴重的(de)(de)(de)(de)事情。
關于ArrayList和Vector區(qu)別如下：
- ArrayList在內(nei)存不夠(gou)時默認是擴展(zhan)50% + 1個，Vector是默認擴展(zhan)1倍。
- Vector提供indexOf(obj, start)接口，ArrayList沒(mei)有。
- Vector屬于線(xian)程(cheng)安全級(ji)別的，但是大多數情況下(xia)不使用Vector，因為線(xian)程(cheng)安全需要更大的系統開銷(xiao)。
ArrayList還給我們提供了將底層(ceng)數組的容量(liang)調整為當前(qian)列表(biao)保存的實際元素的大小的功能(neng)。它(ta)可以通過(guo)trimToSize方法(fa)來實現。代碼如下：
127 public void trimToSize() {
128 modCount++;
129 int oldCapacity = elementData.length;
130 if (size < oldCapacity) {
131 elementData = Arrays.copyOf(elementData, size);
132 }
}
由于elementData的長度會(hui)被拓展，size標記的是其中(zhong)包含(han)的元(yuan)素(su)的個數。所以會(hui)出現(xian)size很小但elementData.length很大的情況(kuang)，將出現(xian)空間的浪(lang)費。trimToSize將返回一個新的數組(zu)給elementData，元(yuan)素(su)內容保持不變，length和size相(xiang)同，節省空間。
4、注意(yi)ArrayList的兩(liang)個轉化(hua)為靜態數(shu)組(zu)的toArray方法。
第一(yi)個(ge)， 調(diao)用Arrays.copyOf將返回一(yi)個(ge)數(shu)組，數(shu)組內容(rong)是(shi)size個(ge)elementData的元素，即拷貝elementData從0至size-1位置的元素到(dao)新(xin)數(shu)組并返回。
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
第(di)二個(ge)，如果傳入(ru)數(shu)組(zu)的(de)長(chang)度(du)小于size，返(fan)回(hui)一(yi)個(ge)新的(de)數(shu)組(zu)，大小為(wei)size，類(lei)型與傳入(ru)數(shu)組(zu)相同。所傳入(ru)數(shu)組(zu)長(chang)度(du)與size相等，則將(jiang)elementData復制(zhi)到傳入(ru)數(shu)組(zu)中并返(fan)回(hui)傳入(ru)的(de)數(shu)組(zu)。若傳入(ru)數(shu)組(zu)長(chang)度(du)大于size，除了復制(zhi)elementData外，還(huan)將(jiang)把返(fan)回(hui)數(shu)組(zu)的(de)第(di)size個(ge)元素置為(wei)空。
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也采用了快速失敗的(de)(de)機制(zhi)，通過記錄modCount參數(shu)來(lai)實現(xian)。在面對并發(fa)的(de)(de)修改時(shi)，迭代器很快就會完(wan)全失敗，而(er)不是冒著在將來(lai)某個不確定(ding)時(shi)間發(fa)生(sheng)任意不確定(ding)行為(wei)的(de)(de)風險。具體介紹請(qing)參考(kao)這篇文章 中(zhong)的(de)(de)Fail-Fast機制(zhi)。
關于ArrayList的(de)源碼，給出幾點比(bi)較(jiao)重要(yao)的(de)總(zong)結(jie)：
1、注意其三個不同的構(gou)(gou)造(zao)方法。無參(can)構(gou)(gou)造(zao)方法構(gou)(gou)造(zao)的ArrayList的容量默認(ren)為10，帶有(you)Collection參(can)數(shu)的構(gou)(gou)造(zao)方法，將(jiang)Collection轉化為數(shu)組賦給ArrayList的實現數(shu)組elementData。
2、注(zhu)意擴充容量的(de)(de)(de)(de)(de)方(fang)法(fa)ensureCapacity。ArrayList在每次增(zeng)加元(yuan)(yuan)素(su)(su)（可能(neng)是(shi)1個(ge)(ge)，也(ye)可能(neng)是(shi)一組(zu)）時(shi)，都要(yao)調用(yong)該方(fang)法(fa)來(lai)確保足(zu)夠(gou)(gou)的(de)(de)(de)(de)(de)容量。當(dang)容量不足(zu)以容納當(dang)前的(de)(de)(de)(de)(de)元(yuan)(yuan)素(su)(su)個(ge)(ge)數(shu)時(shi)，就(jiu)設置(zhi)(zhi)新的(de)(de)(de)(de)(de)容量為舊的(de)(de)(de)(de)(de)容量的(de)(de)(de)(de)(de)1.5倍加1，如(ru)果設置(zhi)(zhi)后的(de)(de)(de)(de)(de)新容量還(huan)不夠(gou)(gou)，則直接新容量設置(zhi)(zhi)為傳入的(de)(de)(de)(de)(de)參數(shu)（也(ye)就(jiu)是(shi)所需的(de)(de)(de)(de)(de)容量），而后用(yong)Arrays.copyof()方(fang)法(fa)將元(yuan)(yuan)素(su)(su)拷貝(bei)到新的(de)(de)(de)(de)(de)數(shu)組(zu)（詳見(jian)下面的(de)(de)(de)(de)(de)第(di)3點(dian)）。從中(zhong)可以看出(chu)，當(dang)容量不夠(gou)(gou)時(shi)，每次增(zeng)加元(yuan)(yuan)素(su)(su)，都要(yao)將原來(lai)的(de)(de)(de)(de)(de)元(yuan)(yuan)素(su)(su)拷貝(bei)到一個(ge)(ge)新的(de)(de)(de)(de)(de)數(shu)組(zu)中(zhong)，非常(chang)之耗時(shi)，也(ye)因(yin)此建議在事(shi)先能(neng)確定元(yuan)(yuan)素(su)(su)數(shu)量的(de)(de)(de)(de)(de)情況下，才使用(yong)ArrayList，否(fou)則建議使用(yong)LinkedList。
3、ArrayList的(de)實現(xian)中大量地調用了Arrays.copyof()和System.arraycopy()方法。我們有(you)必要對(dui)這(zhe)兩個方法的(de)實現(xian)做(zuo)下(xia)深(shen)入的(de)了解。
首先來(lai)看(kan)Arrays.copyof()方法(fa)。它有很多個重(zhong)載的方法(fa)，但實現思路(lu)都(dou)是一樣的，我們來(lai)看(kan)泛型版(ban)本的源碼(ma)：
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
很明顯調用了(le)另一(yi)個(ge)copyof方法，該方法有三個(ge)參數(shu)，最后一(yi)個(ge)參數(shu)指明要轉換的(de)數(shu)據的(de)類型，其(qi)源碼(ma)如下：
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;
}
這里可以(yi)很明顯地(di)看出(chu)，該(gai)方法實際上是在其內部又創(chuang)建了(le)一個長度(du)為(wei)newlength的數組，調用System.arraycopy()方法，將原來數組中的元素復(fu)制到了(le)新(xin)的數組中。
下面來看(kan)System.arraycopy()方法。該方法被標(biao)記了(le)native，調(diao)(diao)用了(le)系統的(de)(de)C/C++代碼(ma)，在JDK中是(shi)看(kan)不到的(de)(de)，但在openJDK中可(ke)以(yi)看(kan)到其源碼(ma)。該函數(shu)(shu)實際上最(zui)終調(diao)(diao)用了(le)C語言的(de)(de)memmove()函數(shu)(shu)，因此它(ta)可(ke)以(yi)保證同一(yi)個(ge)數(shu)(shu)組(zu)內元素的(de)(de)正(zheng)確復(fu)制和移動，比(bi)一(yi)般的(de)(de)復(fu)制方法的(de)(de)實現效率要(yao)高很(hen)多，很(hen)適合(he)用來批量(liang)處理數(shu)(shu)組(zu)。Java強烈推薦在復(fu)制大量(liang)數(shu)(shu)組(zu)元素時用該方法，以(yi)取(qu)得更高的(de)(de)效率。
4、ArrayList基于(yu)數組實現(xian)，可以通過下標索(suo)引直接查找(zhao)到指定位(wei)置(zhi)的(de)元(yuan)(yuan)素(su)，因(yin)此查找(zhao)效率高，但每次插(cha)入或刪(shan)除(chu)元(yuan)(yuan)素(su)，就(jiu)要大量地移動(dong)元(yuan)(yuan)素(su)，插(cha)入刪(shan)除(chu)元(yuan)(yuan)素(su)的(de)效率低(di)。
5、在查找給定元素(su)(su)索引值等(deng)的方法(fa)中，源(yuan)碼(ma)都將該元素(su)(su)的值分(fen)為(wei)(wei)null和不為(wei)(wei)null兩種情況處理(li)，ArrayList中允(yun)許元素(su)(su)為(wei)(wei)null。
注：參(can)考