本篇分析ArrayList的源碼，在分析之前先跟大家談一談數(shù)組。數(shù)組可能是我們最早接觸到的數(shù)據(jù)結(jié)構(gòu)之一，它是在內(nèi)存中劃分出一塊連續(xù)的地址空間用來進行元素的存儲，由于它直接操作內(nèi)存，所以數(shù)組的性能要比集合類更好一些，這是使用數(shù)組的一大優(yōu)勢。但是我們知道數(shù)組存在致命的缺陷，就是在初始化時必須指定數(shù)組大小，并且在后續(xù)操作中不能再更改數(shù)組的大小。在實際情況中我們遇到更多的是一開始并不知道要存放多少元素，而是希望容器能夠自動的擴展它自身的容量以便能夠存放更多的元素。ArrayList就能夠很好的滿足這樣的需求，它能夠自動擴展大小以適應(yīng)存儲元素的不斷增加。它的底層是基于數(shù)組實現(xiàn)的，因此它具有數(shù)組的一些特點，例如查找修改快而插入刪除慢。本篇我們將深入源碼看看它是怎樣對數(shù)組進行封裝的。首先看看它的成員變量和三個主要的構(gòu)造器。
|
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
37
38
39
40
|
//默認初始化容量private static final int DEFAULT_CAPACITY = 10;//空對象數(shù)組private static final Object[] EMPTY_ELEMENTDATA = {};//對象數(shù)組private transient Object[] elementData;//集合元素個數(shù)private int size;//傳入初始容量的構(gòu)造方法public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } //新建指定容量的Object類型數(shù)組 this.elementData = new Object[initialCapacity];}//不帶參數(shù)的構(gòu)造方法public ArrayList() { super(); //將空的數(shù)組實例傳給elementData this.elementData = EMPTY_ELEMENTDATA;}//傳入外部集合的構(gòu)造方法public ArrayList(Collection<? extends E> c) { //持有傳入集合的內(nèi)部數(shù)組的引用 elementData = c.toArray(); //更新集合元素個數(shù)大小 size = elementData.length; //判斷引用的數(shù)組類型, 并將引用轉(zhuǎn)換成Object數(shù)組引用 if (elementData.getClass() != Object[].class) { elementData = Arrays.copyOf(elementData, size, Object[].class); }} |
可以看到ArrayList的內(nèi)部存儲結(jié)構(gòu)就是一個Object類型的數(shù)組，因此它可以存放任意類型的元素。在構(gòu)造ArrayList的時候，如果傳入初始大小那么它將新建一個指定容量的Object數(shù)組，如果不設(shè)置初始大小那么它將不會分配內(nèi)存空間而是使用空的對象數(shù)組，在實際要放入元素時再進行內(nèi)存分配。下面再看看它的增刪改查方法。
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
//增(添加)public boolean add(E e) { //添加前先檢查是否需要拓展數(shù)組, 此時數(shù)組長度最小為size+1 ensureCapacityInternal(size + 1); //將元素添加到數(shù)組末尾 elementData[size++] = e; return true;}//增(插入)public void add(int index, E element) { //插入位置范圍檢查 rangeCheckForAdd(index); //檢查是否需要擴容 ensureCapacityInternal(size + 1); //挪動插入位置后面的元素 System.arraycopy(elementData, index, elementData, index + 1, size - index); //在要插入的位置賦上新值 elementData[index] = element; size++;}//刪public E remove(int index) { //index不能大于size rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) { //將index后面的元素向前挪動一位 System.arraycopy(elementData, index+1, elementData, index, numMoved); } //置空引用 elementData[--size] = null; return oldValue;}//改public E set(int index, E element) { //index不能大于size rangeCheck(index); E oldValue = elementData(index); //替換成新元素 elementData[index] = element; return oldValue;}//查public E get(int index) { //index不能大于size rangeCheck(index); //返回指定位置元素 return elementData(index);} |
每次添加一個元素到集合中都會先檢查容量是否足夠，否則就進行擴容，擴容的細節(jié)下面會講到。我們先看具體增刪改查要注意的地方。
增(添加)：僅是將這個元素添加到末尾。操作快速。
增(插入)：由于需要移動插入位置后面的元素，并且涉及數(shù)組的復(fù)制，所以操作較慢。
刪：由于需要將刪除位置后面的元素向前挪動，也會設(shè)計數(shù)組復(fù)制，所以操作較慢。
改：直接對指定位置元素進行修改，不涉及元素挪動和數(shù)組復(fù)制，操作快速。
查：直接返回指定下標(biāo)的數(shù)組元素，操作快速。
通過源碼看到，由于查找和修改直接定位到數(shù)組下標(biāo)，不涉及元素挪動和數(shù)組復(fù)制所以較快，而插入刪除由于要挪動元素，涉及到數(shù)組復(fù)制，操作較慢。并且每次添加操作還可能進行數(shù)組擴容，也會影響到性能。下面我們看看ArrayList是怎樣動態(tài)擴容的。
|
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
37
38
|
private void ensureCapacityInternal(int minCapacity) { //如果此時還是空數(shù)組 if (elementData == EMPTY_ELEMENTDATA) { //和默認容量比較, 取較大值 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //數(shù)組已經(jīng)初始化過就執(zhí)行這一步 ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) { modCount++; //如果最小容量大于數(shù)組長度就擴增數(shù)組 if (minCapacity - elementData.length > 0) { grow(minCapacity); }}//集合最大容量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//增加數(shù)組長度private void grow(int minCapacity) { //獲取數(shù)組原先的容量 int oldCapacity = elementData.length; //新數(shù)組的容量, 在原來的基礎(chǔ)上增加一半 int newCapacity = oldCapacity + (oldCapacity >> 1); //檢驗新的容量是否小于最小容量 if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } //檢驗新的容量是否超過最大數(shù)組容量 if (newCapacity - MAX_ARRAY_SIZE > 0) { newCapacity = hugeCapacity(minCapacity); } //拷貝原來的數(shù)組到新數(shù)組 elementData = Arrays.copyOf(elementData, newCapacity);} |
每次添加元素前會調(diào)用ensureCapacityInternal這個方法進行集合容量檢查。在這個方法內(nèi)部會檢查當(dāng)前集合的內(nèi)部數(shù)組是否還是個空數(shù)組，如果是就新建默認大小為10的Object數(shù)組。如果不是則證明當(dāng)前集合已經(jīng)被初始化過，那么就調(diào)用ensureExplicitCapacity方法檢查當(dāng)前數(shù)組的容量是否滿足這個最小所需容量，不滿足的話就調(diào)用grow方法進行擴容。在grow方法內(nèi)部可以看到，每次擴容都是增加原來數(shù)組長度的一半，擴容實際上是新建一個容量更大的數(shù)組，將原先數(shù)組的元素全部復(fù)制到新的數(shù)組上，然后再拋棄原先的數(shù)組轉(zhuǎn)而使用新的數(shù)組。至此，我們對ArrayList中比較常用的方法做了分析，其中有些值得注意的要點：
1. ArrayList底層實現(xiàn)是基于數(shù)組的，因此對指定下標(biāo)的查找和修改比較快，但是刪除和插入操作比較慢。
2. 構(gòu)造ArrayList時盡量指定容量，減少擴容時帶來的數(shù)組復(fù)制操作，如果不知道大小可以賦值為默認容量10。
3. 每次添加元素之前會檢查是否需要擴容，每次擴容都是增加原有容量的一半。
4. 每次對下標(biāo)的操作都會進行安全性檢查，如果出現(xiàn)數(shù)組越界就立即拋出異常。
5. ArrayList的所有方法都沒有進行同步，因此它不是線程安全的。
6. 以上分析基于JDK1.7，其他版本會有些出入，因此不能一概而論。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://www.cnblogs.com/liuyun1995/p/8286829.html
