我相信幾乎所有的同學在大大小小的筆試、面試過程中都會被問及ArrayList與LinkedList之間的異同點。稍有準備的人這些問題早已爛熟于心，前者基于數(shù)組實現(xiàn)，后者基于鏈表實現(xiàn)；前者隨機方法速度快刪除和插入指定位置速度慢，后者隨機訪問速度慢刪除和插入指定位置速度快；兩者都是線程不安全的；列表與數(shù)組之間的區(qū)別等等。
列表與數(shù)組之間很大的一個區(qū)別就是：數(shù)組在其初始化就需要給它確定大小不能動態(tài)擴容，而列表則可以動態(tài)擴容。ArrayList是基于數(shù)組實現(xiàn)的，那么它是如何實現(xiàn)的動態(tài)擴容呢？
對于ArrayList的初始化有三種方式：
對于第一種默認的構造方法，ArrayList并沒有初始化容量大小，而是將列表的元素數(shù)據(jù)引用指向了一個空數(shù)組。
|
1
2
|
private transient Object[] elementData;private static final Object[] EMPTY_ELEMENTDATA = {}; |
|
1
2
3
4
5
|
//1.ArrayList默認構造方法public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA;} |
與JDK1.6不同的是，JDK1.6即時是在調(diào)用默認的構造方法時，也會初始化容量大小，JDK1.7當然會帶來一定的好處，如果初始化而不使用就白白浪費了存儲空間，等到添加的時候再初始化容量大小即可。
與JDK1.6不同的是，JDK1.6即時是在調(diào)用默認的構造方法時，也會初始化容量大小，JDK1.7當然會帶來一定的好處，如果初始化而不使用就白白浪費了存儲空間，等到添加的時候再初始化容量大小即可。
|
1
2
3
4
|
//JDK1.6 ArrayListpublic ArrayList() { this(10);} |
對于第二種構造方法，則直接創(chuàng)建一個指定大小的數(shù)組，將列表的元素數(shù)組引用指向它。
|
1
2
3
4
5
6
7
8
|
//2.ArrayList帶有初始化大小的構造方法public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity];} |
第三種構造方法，能將一個集合作為參數(shù)傳遞，但集合中的元素必須繼承自ArrayList中的元素。
|
1
2
3
4
5
6
7
8
|
//3.可將一個集合作為ArrayList的參數(shù)構造成ArrayListpublic ArrayList(Collection<? extends E> c) { elementData = c.toArray(); //將集合轉(zhuǎn)換為數(shù)組 size = elementData.length; //集合中的元素大小 // c.toArray might (incorrectly) not return Object[] (see 6260652) 這里是個bug，參考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class);} |
上面提到了一個bug，也就是說將一個集合轉(zhuǎn)換為數(shù)組的時候可能錯誤地不會返回Object[]，舉例說明。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
package com.algorithm.sort;import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * bug編號:6260652。toArray有可能不會返回Object[] * Created by yulinfeng on 2017/6/26. */public class Test { public static void main(String[] args) { correctly(); incorrectly(); } /** * 返回Object[] */ private static void correctly() { List<String> list = new ArrayList<String>(); list.add("test"); System.out.println(list.getClass()); Object[] objArray = list.toArray(); System.out.println(objArray.getClass()); } /** * 不返回Object[] */ private static void incorrectly() { List<String> list = Arrays.asList("test"); System.out.println(list.getClass()); Object[] objArray = list.toArray(); System.out.println(objArray.getClass()); }} |
運行結果：
上面的這個例子就說明了toArray并不一定總是返回Object[]，返回的Object[]時，Object元素就不能插入，故JDK在“6260652”中修復了這個bug。
接下來看元素插入以及刪除等其它方法。
|
1
2
3
4
5
6
|
//ArrayList#addpublic boolean add(E e) { ensureCapacityInternal(size + 1); //確保容量是否充足 elementData[size++] = e; //將元素添加至數(shù)組 return true;} |
|
1
2
3
4
5
6
7
|
//ArrayList#ensureCapacityInternalprivate void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //如果此時還沒有初始化列表容量大小，則對其初始化，默認容量為10 } ensureExplicitCapacity(minCapacity); //檢查容量是否充足} |
|
1
2
3
4
5
6
|
//ArrayList#ensureEcplicitCapacityprivate void ensureExplicitCapacity(int minCapacity) { modCount++; //注意此變量 if (minCapacity - elementData.length > 0) grow(minCapacity); //容量不夠則進行擴容} |
在ensureEcplicitCapacity方法中有一個modCount（modify count）變量進行了自增。
|
1
|
protected transient int modCount = 0; |
這個變量不僅在add方法中會自增，只要是在增加或者刪除等對ArrayList結構產(chǎn)生了變化都會記錄加1，這樣做的原因和多線程下Iterator迭代器遍歷有關。在AbstractList$Itr中也有一個變量與之對應。
|
1
2
|
//AbstractList$Itrint expectedModCount = modCount; |
在AbstractList$Itr#next中調(diào)用了checkForComodification方法。
|
1
2
3
4
5
|
//AbstractList$Itr#checkForComodificationfinal void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException();} |
如果當前運行環(huán)境是單線程，不論對列表進行何種操作何時增加、修改、刪除等，excpectedModCount總是會等于modCount，但是如果當前運行環(huán)境是多線程，很有可能一個線程在迭代遍歷，而另一個線程在對其進行新增或者修改等，JDK則不允許這么做，此時則會拋出ConcurrentModificationException異常，這就是modCount變量在此起的作用。
回到ArrayList#add方法，當列表容量不足時，此時會調(diào)用grow方法進行擴容。
|
1
2
3
4
5
6
7
8
9
10
11
|
//ArrayList#growprivate void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //擴容策略為，每次新增容量的大小為舊容量的一半。也就是說如果默認容量為10，則第一次擴容大小為10 / 2 = 5，第二次擴容大小為15 / 2 = 7。 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //擴容策略擴得太小 if (newCapacity - MAX_ARRAY_SIZE > 0) //擴容策略擴得太大，大于最大數(shù)組大小時，最多等于Integer.MAX_VALUE newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity);} |
ArrayList獲取指定索引位置的元素get方法。
|
1
2
3
4
|
public E get(int index) { rangeCheck(index); //檢查索引是否越界 return elementData(index);} |
由于ArrayList是由基于數(shù)組實現(xiàn)，故此方法較為簡單，判斷是否越界，沒有則根據(jù)數(shù)組下標來索引返回元素即可。remove方法刪除指定位置的元素。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
//ArrayList#removepublic E remove(int index) { rangeCheck(index); //檢查索引是否越界 modCount++; //記錄modCount，上面已提及 E oldValue = elementData(index); //取出指定索引元素 int numMoved = size - index - 1; //移動的元素個數(shù) if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; //將最后一個數(shù)組元素置為null，方便GC return oldValue;} |
代碼比較簡單，同樣也體現(xiàn)了基于數(shù)組實習的ArrayList在刪除指定元素時的效率問題。
以上這篇基于ArrayList常用方法的源碼全面解析就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
