第一篇：JAVA集合之ArrayList源碼剖析

ArrayList簡介

    ArrayList是基于數組實作的，是一個動态數組，其容量能自動增長，類似于C語言中的動态申請記憶體，動态增長記憶體。

    ArrayList不是線程安全的，隻能用在單線程環境下，多線程環境下可以考慮用Collections.synchronizedList(List l)函數傳回一個線程安全的ArrayList類，也可以使用concurrent并發包下的CopyOnWriteArrayList類。

    ArrayList實作了Serializable接口，是以它支援序列化，能夠通過序列化傳輸，實作了RandomAccess接口，支援快速随機通路，實際上就是通過下标序号進行快速通路，實作了Cloneable接口，能被克隆。

ArrayList源碼剖析

    ArrayList的源碼如下（加入了比較詳細的注釋）：

[java]  view plain  copy

1. package java.util;    
2. public class ArrayList<E> extends AbstractList<E>    
3.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable    
4. {    
5.     // 序列版本号    
6.     private static final long serialVersionUID = 8683452581122892189L;    
7.     // ArrayList基于該數組實作，用該數組儲存資料   
8.     private transient Object[] elementData;    
9.     // ArrayList中實際資料的數量    
10.     private int size;    
11.     // ArrayList帶容量大小的構造函數。    
12.     public ArrayList(int initialCapacity) {    
13.         super();    
14.         if (initialCapacity < 0)    
15.             throw new IllegalArgumentException("Illegal Capacity: "+    
16.                                                initialCapacity);    
17.         // 建立一個數組    
18.         this.elementData = new Object[initialCapacity];    
19.     }    
20.     // ArrayList無參構造函數。預設容量是10。    
21.     public ArrayList() {    
22.         this(10);    
23.     }    
24.     // 建立一個包含collection的ArrayList    
25.     public ArrayList(Collection<? extends E> c) {    
26.         elementData = c.toArray();    
27.         size = elementData.length;    
28.         if (elementData.getClass() != Object[].class)    
29.             elementData = Arrays.copyOf(elementData, size, Object[].class);    
30.     }    
31.     // 将目前容量值設為實際元素個數    
32.     public void trimToSize() {    
33.         modCount++;    
34.         int oldCapacity = elementData.length;    
35.         if (size < oldCapacity) {    
36.             elementData = Arrays.copyOf(elementData, size);    
37.         }    
38.     }    
39.     // 确定ArrarList的容量。    
40.     // 若ArrayList的容量不足以容納目前的全部元素，設定 新的容量=“(原始容量x3)/2 + 1”    
41.     public void ensureCapacity(int minCapacity) {    
42.         // 将“修改統計數”+1，該變量主要是用來實作fail-fast機制的    
43.         modCount++;    
44.         int oldCapacity = elementData.length;    
45.         // 若目前容量不足以容納目前的元素個數，設定 新的容量=“(原始容量x3)/2 + 1”    
46.         if (minCapacity > oldCapacity) {    
47.             Object oldData[] = elementData;    
48.             int newCapacity = (oldCapacity * 3)/2 + 1;    
49.             //如果還不夠，則直接将minCapacity設定為目前容量  
50.             if (newCapacity < minCapacity)    
51.                 newCapacity = minCapacity;    
52.             elementData = Arrays.copyOf(elementData, newCapacity);    
53.         }    
54.     }    
55.     // 添加元素e    
56.     public boolean add(E e) {    
57.         // 确定ArrayList的容量大小    
58.         ensureCapacity(size + 1);  // Increments modCount!!    
59.         // 添加e到ArrayList中    
60.         elementData[size++] = e;    
61.         return true;    
62.     }    
63.     // 傳回ArrayList的實際大小    
64.     public int size() {    
65.         return size;    
66.     }    
67.     // ArrayList是否包含Object(o)    
68.     public boolean contains(Object o) {    
69.         return indexOf(o) >= 0;    
70.     }    
71.     //傳回ArrayList是否為空    
72.     public boolean isEmpty() {    
73.         return size == 0;    
74.     }    
75.     // 正向查找，傳回元素的索引值    
76.     public int indexOf(Object o) {    
77.         if (o == null) {    
78.             for (int i = 0; i < size; i++)    
79.             if (elementData[i]==null)    
80.                 return i;    
81.             } else {    
82.                 for (int i = 0; i < size; i++)    
83.                 if (o.equals(elementData[i]))    
84.                     return i;    
85.             }    
86.             return -1;    
87.         }    
88.         // 反向查找，傳回元素的索引值    
89.         public int lastIndexOf(Object o) {    
90.         if (o == null) {    
91.             for (int i = size-1; i >= 0; i--)    
92.             if (elementData[i]==null)    
93.                 return i;    
94.         } else {    
95.             for (int i = size-1; i >= 0; i--)    
96.             if (o.equals(elementData[i]))    
97.                 return i;    
98.         }    
99.         return -1;    
100.     }    
101.     // 反向查找(從數組末尾向開始查找)，傳回元素(o)的索引值    
102.     public int lastIndexOf(Object o) {    
103.         if (o == null) {    
104.             for (int i = size-1; i >= 0; i--)    
105.             if (elementData[i]==null)    
106.                 return i;    
107.         } else {    
108.             for (int i = size-1; i >= 0; i--)    
109.             if (o.equals(elementData[i]))    
110.                 return i;    
111.         }    
112.         return -1;    
113.     }    
114.     // 傳回ArrayList的Object數組    
115.     public Object[] toArray() {    
116.         return Arrays.copyOf(elementData, size);    
117.     }    
118.     // 傳回ArrayList元素組成的數組  
119.     public <T> T[] toArray(T[] a) {    
120.         // 若數組a的大小 < ArrayList的元素個數；    
121.         // 則建立一個T[]數組，數組大小是“ArrayList的元素個數”，并将“ArrayList”全部拷貝到新數組中    
122.         if (a.length < size)    
123.             return (T[]) Arrays.copyOf(elementData, size, a.getClass());    
124.         // 若數組a的大小 >= ArrayList的元素個數；    
125.         // 則将ArrayList的全部元素都拷貝到數組a中。    
126.         System.arraycopy(elementData, 0, a, 0, size);    
127.         if (a.length > size)    
128.             a[size] = null;    
129.         return a;    
130.     }    
131.     // 擷取index位置的元素值    
132.     public E get(int index) {    
133.         RangeCheck(index);    
134.         return (E) elementData[index];    
135.     }    
136.     // 設定index位置的值為element    
137.     public E set(int index, E element) {    
138.         RangeCheck(index);    
139.         E oldValue = (E) elementData[index];    
140.         elementData[index] = element;    
141.         return oldValue;    
142.     }    
143.     // 将e添加到ArrayList中    
144.     public boolean add(E e) {    
145.         ensureCapacity(size + 1);  // Increments modCount!!    
146.         elementData[size++] = e;    
147.         return true;    
148.     }    
149.     // 将e添加到ArrayList的指定位置    
150.     public void add(int index, E element) {    
151.         if (index > size || index < 0)    
152.             throw new IndexOutOfBoundsException(    
153.             "Index: "+index+", Size: "+size);    
154.         ensureCapacity(size+1);  // Increments modCount!!    
155.         System.arraycopy(elementData, index, elementData, index + 1,    
156.              size - index);    
157.         elementData[index] = element;    
158.         size++;    
159.     }    
160.     // 删除ArrayList指定位置的元素    
161.     public E remove(int index) {    
162.         RangeCheck(index);    
163.         modCount++;    
164.         E oldValue = (E) elementData[index];    
165.         int numMoved = size - index - 1;    
166.         if (numMoved > 0)    
167.             System.arraycopy(elementData, index+1, elementData, index,    
168.                  numMoved);    
169.         elementData[--size] = null; // Let gc do its work    
170.         return oldValue;    
171.     }    
172.     // 删除ArrayList的指定元素    
173.     public boolean remove(Object o) {    
174.         if (o == null) {    
175.                 for (int index = 0; index < size; index++)    
176.             if (elementData[index] == null) {    
177.                 fastRemove(index);    
178.                 return true;    
179.             }    
180.         } else {    
181.             for (int index = 0; index < size; index++)    
182.             if (o.equals(elementData[index])) {    
183.                 fastRemove(index);    
184.                 return true;    
185.             }    
186.         }    
187.         return false;    
188.     }    
189.     // 快速删除第index個元素    
190.     private void fastRemove(int index) {    
191.         modCount++;    
192.         int numMoved = size - index - 1;    
193.         // 從"index+1"開始，用後面的元素替換前面的元素。    
194.         if (numMoved > 0)    
195.             System.arraycopy(elementData, index+1, elementData, index,    
196.                              numMoved);    
197.         // 将最後一個元素設為null    
198.         elementData[--size] = null; // Let gc do its work    
199.     }    
200.     // 删除元素    
201.     public boolean remove(Object o) {    
202.         if (o == null) {    
203.             for (int index = 0; index < size; index++)    
204.             if (elementData[index] == null) {    
205.                 fastRemove(index);    
206.             return true;    
207.             }    
208.         } else {    
209.             // 便利ArrayList，找到“元素o”，則删除，并傳回true。    
210.             for (int index = 0; index < size; index++)    
211.             if (o.equals(elementData[index])) {    
212.                 fastRemove(index);    
213.             return true;    
214.             }    
215.         }    
216.         return false;    
217.     }    
218.     // 清空ArrayList，将全部的元素設為null    
219.     public void clear() {    
220.         modCount++;    
221.         for (int i = 0; i < size; i++)    
222.             elementData[i] = null;    
223.         size = 0;    
224.     }    
225.     // 将集合c追加到ArrayList中    
226.     public boolean addAll(Collection<? extends E> c) {    
227.         Object[] a = c.toArray();    
228.         int numNew = a.length;    
229.         ensureCapacity(size + numNew);  // Increments modCount    
230.         System.arraycopy(a, 0, elementData, size, numNew);    
231.         size += numNew;    
232.         return numNew != 0;    
233.     }    
234.     // 從index位置開始，将集合c添加到ArrayList    
235.     public boolean addAll(int index, Collection<? extends E> c) {    
236.         if (index > size || index < 0)    
237.             throw new IndexOutOfBoundsException(    
238.             "Index: " + index + ", Size: " + size);    
239.         Object[] a = c.toArray();    
240.         int numNew = a.length;    
241.         ensureCapacity(size + numNew);  // Increments modCount    
242.         int numMoved = size - index;    
243.         if (numMoved > 0)    
244.             System.arraycopy(elementData, index, elementData, index + numNew,    
245.                  numMoved);    
246.         System.arraycopy(a, 0, elementData, index, numNew);    
247.         size += numNew;    
248.         return numNew != 0;    
249.     }    
250.     // 删除fromIndex到toIndex之間的全部元素。    
251.     protected void removeRange(int fromIndex, int toIndex) {    
252.     modCount++;    
253.     int numMoved = size - toIndex;    
254.         System.arraycopy(elementData, toIndex, elementData, fromIndex,    
255.                          numMoved);    
256.     // Let gc do its work    
257.     int newSize = size - (toIndex-fromIndex);    
258.     while (size != newSize)    
259.         elementData[--size] = null;    
260.     }    
261.     private void RangeCheck(int index) {    
262.     if (index >= size)    
263.         throw new IndexOutOfBoundsException(    
264.         "Index: "+index+", Size: "+size);    
265.     }    
266.     // 克隆函數    
267.     public Object clone() {    
268.         try {    
269.             ArrayList<E> v = (ArrayList<E>) super.clone();    
270.             // 将目前ArrayList的全部元素拷貝到v中    
271.             v.elementData = Arrays.copyOf(elementData, size);    
272.             v.modCount = 0;    
273.             return v;    
274.         } catch (CloneNotSupportedException e) {    
275.             // this shouldn't happen, since we are Cloneable    
276.             throw new InternalError();    
277.         }    
278.     }    
279.     // java.io.Serializable的寫入函數    
280.     // 将ArrayList的“容量，所有的元素值”都寫入到輸出流中    
281.     private void writeObject(java.io.ObjectOutputStream s)    
282.         throws java.io.IOException{    
283.     // Write out element count, and any hidden stuff    
284.     int expectedModCount = modCount;    
285.     s.defaultWriteObject();    
286.         // 寫入“數組的容量”    
287.         s.writeInt(elementData.length);    
288.     // 寫入“數組的每一個元素”    
289.     for (int i=0; i<size; i++)    
290.             s.writeObject(elementData[i]);    
291.     if (modCount != expectedModCount) {    
292.             throw new ConcurrentModificationException();    
293.         }    
294.     }    
295.     // java.io.Serializable的讀取函數：根據寫入方式讀出    
296.     // 先将ArrayList的“容量”讀出，然後将“所有的元素值”讀出    
297.     private void readObject(java.io.ObjectInputStream s)    
298.         throws java.io.IOException, ClassNotFoundException {    
299.         // Read in size, and any hidden stuff    
300.         s.defaultReadObject();    
301.         // 從輸入流中讀取ArrayList的“容量”    
302.         int arrayLength = s.readInt();    
303.         Object[] a = elementData = new Object[arrayLength];    
304.         // 從輸入流中将“所有的元素值”讀出    
305.         for (int i=0; i<size; i++)    
306.             a[i] = s.readObject();    
307.     }    
308. }  

幾點總結

    關于ArrayList的源碼，給出幾點比較重要的總結：

    1、注意其三個不同的構造方法。無參構造方法構造的ArrayList的容量預設為10，帶有Collection參數的構造方法，将Collection轉化為數組賦給ArrayList的實作數組elementData。

    2、注意擴充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1個，也可能是一組）時，都要調用該方法來確定足夠的容量。當容量不足以容納目前的元素個數時，就設定新的容量為舊的容量的1.5倍加1，如果設定後的新容量還不夠，則直接新容量設定為傳入的參數（也就是所需的容量），而後用Arrays.copyof()方法将元素拷貝到新的數組（詳見下面的第3點）。從中可以看出，當容量不夠時，每次增加元素，都要将原來的元素拷貝到一個新的數組中，非常之耗時，也是以建議在事先能确定元素數量的情況下，才使用ArrayList，否則建議使用LinkedList。

    3、ArrayList的實作中大量地調用了Arrays.copyof()和System.arraycopy()方法。我們有必要對這兩個方法的實作做下深入的了解。

    首先來看Arrays.copyof()方法。它有很多個重載的方法，但實作思路都是一樣的，我們來看泛型版本的源碼：

[java]  view plain  copy

1. public static <T> T[] copyOf(T[] original, int newLength) {  
2.     return (T[]) copyOf(original, newLength, original.getClass());  
3. }  

    很明顯調用了另一個copyof方法，該方法有三個參數，最後一個參數指明要轉換的資料的類型，其源碼如下：

[java]  view plain  copy

1. public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {  
2.     T[] copy = ((Object)newType == (Object)Object[].class)  
3.         ? (T[]) new Object[newLength]  
4.         : (T[]) Array.newInstance(newType.getComponentType(), newLength);  
5.     System.arraycopy(original, 0, copy, 0,  
6.                      Math.min(original.length, newLength));  
7.     return copy;  
8. }  

    這裡可以很明顯地看出，該方法實際上是在其内部又建立了一個長度為newlength的數組，調用System.arraycopy()方法，将原來數組中的元素複制到了新的數組中。

    下面來看System.arraycopy()方法。該方法被标記了native，調用了系統的C/C++代碼，在JDK中是看不到的，但在openJDK中可以看到其源碼。該函數實際上最終調用了c語言的memmove()函數，是以它可以保證同一個數組内元素的正确複制和移動，比一般的複制方法的實作效率要高很多，很适合用來批量處理數組。Java強烈推薦在複制大量數組元素時用該方法，以取得更高的效率。

    4、注意ArrayList的兩個轉化為靜态數組的toArray方法。

    第一個，Object[] toArray()方法。該方法有可能會抛出java.lang.ClassCastException異常，如果直接用向下轉型的方法，将整個ArrayList集合轉變為指定類型的Array數組，便會抛出該異常，而如果轉化為Array數組時不向下轉型，而是将每個元素向下轉型，則不會抛出該異常，顯然對數組中的元素一個個進行向下轉型，效率不高，且不太友善。

    第二個，<T> T[] toArray(T[] a)方法。該方法可以直接将ArrayList轉換得到的Array進行整體向下轉型（轉型其實是在該方法的源碼中實作的），且從該方法的源碼中可以看出，參數a的大小不足時，内部會調用Arrays.copyOf方法，該方法内部建立一個新的數組傳回，是以對該方法的常用形式如下：

[java]  view plain  copy

1. public static Integer[] vectorToArray2(ArrayList<Integer> v) {    
2.     Integer[] newText = (Integer[])v.toArray(new Integer[0]);    
3.     return newText;    
4. }    

     5、ArrayList基于數組實作，可以通過下标索引直接查找到指定位置的元素，是以查找效率高，但每次插入或删除元素，就要大量地移動元素，插入删除元素的效率低。

    6、在查找給定元素索引值等的方法中，源碼都将該元素的值分為null和不為null兩種情況處理，ArrayList中允許元素為null。