《JDK1.8源碼分析之ArrayList》由會(huì)員分享，可在線閱讀，更多相關(guān)《JDK1.8源碼分析之ArrayList（9頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、文檔供參考，可復(fù)制、編制，期待您的好評與關(guān)注！
JDK1.8源碼分析之ArrayList
一、前言
分析了Map中主要的類之后，下面我們來分析Collection下面幾種常見的類，如ArrayList、LinkedList、HashSet、TreeSet等。下面通過JDK源碼來一起分析ArrayList底層是如何實(shí)現(xiàn)的。（PS：把JVM看完了之后終于可以有成片的時(shí)間來閱讀源碼了，感覺簡直不能更爽）。
二、ArrayList數(shù)據(jù)結(jié)構(gòu)
分析一個(gè)類的時(shí)候，數(shù)據(jù)結(jié)構(gòu)往往是它的靈魂所在，理解底層的數(shù)據(jù)結(jié)構(gòu)其實(shí)就理解了該類的實(shí)現(xiàn)思路，具體的實(shí)現(xiàn)細(xì)節(jié)再具體分析。
ArrayLis
2、t的數(shù)據(jù)結(jié)構(gòu)如下：
說明：底層的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，數(shù)組元素類型為Object類型，即可以存放所有類型數(shù)據(jù)。我們對ArrayList類的實(shí)例的所有的操作底層都是基于數(shù)組的。下面我們來分析通過數(shù)組是如何保證庫函數(shù)的正確實(shí)現(xiàn)的。
三、ArrayList源碼分析
3.1 類的繼承關(guān)系
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
說明：ArrayList繼承AbstractList抽象父類
3、，實(shí)現(xiàn)了List接口（規(guī)定了List的操作規(guī)范）、RandomAccess（可隨機(jī)訪問）、Cloneable（可拷貝）、Serializable（可序列化）。
3.2 類的屬性
?
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
{
// 版本號
private static final long serialVersionUID = 868345258112
4、2892189L;
// 缺省容量
private static final int DEFAULT_CAPACITY = 10;
// 空對象數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 缺省空對象數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素?cái)?shù)組
transient Object[] elementData;
// 實(shí)際
5、元素大小，默認(rèn)為0
private int size;
// 最大數(shù)組容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
View Code
說明：類的屬性中核心的屬性為elementData，類型為Object[]，用于存放實(shí)際元素，并且被標(biāo)記為transient，也就意味著在序列化的時(shí)候，此字段是不會(huì)被序列化的。
3.3 類的構(gòu)造函數(shù)
1. ArrayList(int)型構(gòu)造函數(shù)
?
public ArrayList(int initi
6、alCapacity) {
if (initialCapacity > 0) { // 初始容量大于0
this.elementData = new Object[initialCapacity]; // 初始化元素?cái)?shù)組
} else if (initialCapacity == 0) { // 初始容量為0
this.elementData = EMPTY_ELEMENTDATA; // 為空對象數(shù)組
} else { // 初始容量小于0，拋出異常
throw
7、 new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
View Code
說明：指定elementData數(shù)組的大小，不允許初始化大小小于0，否則拋出異常。
2. ArrayList()型構(gòu)造函數(shù)
?
public ArrayList() {
// 無參構(gòu)造函數(shù)，設(shè)置元素?cái)?shù)組為空
this.elementData
8、= DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
View Code
說明：當(dāng)未指定初始化大小時(shí)，會(huì)給elementData賦值為空集合。
3. ArrayList(Collection)型構(gòu)造函數(shù)
?
public ArrayList(Collection c) { // 集合參數(shù)構(gòu)造函數(shù)
elementData = c.toArray(); // 轉(zhuǎn)化為數(shù)組
if ((size = elementData.length) != 0) {
9、 // 參數(shù)為非空集合
if (elementData.getClass() != Object[].class) // 是否成功轉(zhuǎn)化為Object類型數(shù)組
elementData = Arrays.copyOf(elementData, size, Object[].class); // 不為Object數(shù)組的話就進(jìn)行復(fù)制
} else { // 集合大小為空，則設(shè)置元素?cái)?shù)組為空
this.elementData = EMPTY_ELEMENTDATA;
}
}
10、
View Code
說明：當(dāng)傳遞的參數(shù)為集合類型時(shí)，會(huì)把集合類型轉(zhuǎn)化為數(shù)組類型，并賦值給elementData。
3.4 核心函數(shù)分析
1. add函數(shù)
?
public boolean add(E e) { // 添加元素
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
View Code
說明：在add函數(shù)我們發(fā)現(xiàn)還有其他的函數(shù)ensu
11、reCapacityInternal，此函數(shù)可以理解為確保elementData數(shù)組有合適的大小。ensureCapacityInternal的具體函數(shù)如下
?
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 判斷元素?cái)?shù)組是否為空數(shù)組
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 取較大值
12、 }
ensureExplicitCapacity(minCapacity);
}
View Code
說明：在ensureCapacityInternal函數(shù)中我們又發(fā)現(xiàn)了ensureExplicitCapacity函數(shù)，這個(gè)函數(shù)也是為了確保elemenData數(shù)組有合適的大小。ensureExplicitCapacity的具體函數(shù)如下
?
private void ensureExplicitCapacity(int minCapacity) {
// 結(jié)構(gòu)性修改加1
modCount+
13、+;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
View Code
說明：在ensureExplicitCapacity函數(shù)我們又發(fā)現(xiàn)了grow函數(shù)，grow函數(shù)才會(huì)對數(shù)組進(jìn)行擴(kuò)容，ensureCapacityInternal、ensureExplicitCapacity都只是過程，最后完成實(shí)際擴(kuò)容操作還是得看grow函數(shù)，grow函數(shù)的具體函數(shù)如下
?
private void grow(int minCapacity) {
14、 int oldCapacity = elementData.length; // 舊容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量為舊容量的1.5倍
if (newCapacity - minCapacity < 0) // 新容量小于參數(shù)指定容量，修改新容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量大于最大容量
15、 newCapacity = hugeCapacity(minCapacity); // 指定新容量
// 拷貝擴(kuò)容
elementData = Arrays.copyOf(elementData, newCapacity);
}
View Code
說明：正常情況下會(huì)擴(kuò)容1.5倍，特殊情況下（新擴(kuò)展數(shù)組大小已經(jīng)達(dá)到了最大值）則只取最大值。
當(dāng)我們調(diào)用add方法時(shí)，實(shí)際上的函數(shù)調(diào)用如下
說明：程序調(diào)用add，實(shí)際上還會(huì)進(jìn)行一系列調(diào)用，可能會(huì)調(diào)用到grow，grow可能會(huì)調(diào)用hugeCapacity。
下面通過
16、兩種方式給出調(diào)用add的例子，并分析最后的elementData數(shù)組的大小。
示例一（只給出了會(huì)影響到最終結(jié)果的核心代碼）
List lists = new ArrayList();
lists.add(8);
說明：初始化lists大小為0，調(diào)用的ArrayList()型構(gòu)造函數(shù)，那么在調(diào)用lists.add(8)方法時(shí)，會(huì)經(jīng)過怎樣的步驟呢？下圖給出了該程序執(zhí)行過程和最初與最后的elementData的大小
說明：我們可以看到，在add方法之前開始elementData = {}；調(diào)用add方法時(shí)會(huì)繼續(xù)調(diào)用，直至grow，最后e
17、lementData的大小變?yōu)?0，之后再返回到add函數(shù)，把8放在elementData[0]中。
示例二核心代碼如下
List lists = new ArrayList(6);
lists.add(8);
說明：調(diào)用的ArrayList(int)型構(gòu)造函數(shù)，那么elementData被初始化為大小為6的Object數(shù)組，在調(diào)用add(8)方法時(shí)，具體的步驟如下：
說明：我們可以知道，在調(diào)用add方法之前，elementData的大小已經(jīng)為6，之后再進(jìn)行傳遞，不會(huì)進(jìn)行擴(kuò)容處理。
2. set函數(shù)
?
public
18、 E set(int index, E element) {
// 檢驗(yàn)索引是否合法
rangeCheck(index);
// 舊值
E oldValue = elementData(index);
// 賦新值
elementData[index] = element;
// 返回舊值
return oldValue;
}
View Code
說明：設(shè)定指定下標(biāo)索引的元素值。
3. indexOf函數(shù)
?
// 從首
19、開始查找數(shù)組里面是否存在指定元素
public int indexOf(Object o) {
if (o == null) { // 查找的元素為空
for (int i = 0; i < size; i++) // 遍歷數(shù)組，找到第一個(gè)為空的元素，返回下標(biāo)
if (elementData[i]==null)
return i;
} else { // 查找的元素不為空
for (int i = 0; i < size;
20、 i++) // 遍歷數(shù)組，找到第一個(gè)和指定元素相等的元素，返回下標(biāo)
if (o.equals(elementData[i]))
return i;
}
// 沒有找到，返回空
return -1;
}
View Code
說明：從頭開始查找與指定元素相等的元素，注意，是可以查找null元素的，意味著ArrayList中可以存放null元素的。與此函數(shù)對應(yīng)的lastIndexOf，表示從尾部開始查找。
4. get函數(shù)
?
pu
21、blic E get(int index) {
// 檢驗(yàn)索引是否合法
rangeCheck(index);
return elementData(index);
}
View Code
說明：get函數(shù)會(huì)檢查索引值是否合法（只檢查是否大于size，而沒有檢查是否小于0），值得注意的是，在get函數(shù)中存在element函數(shù)，element函數(shù)用于返回具體的元素，具體函數(shù)如下
?
E elementData(int index) {
return (E) elementData[index
22、];
}
View Code
說明：返回的值都經(jīng)過了向下轉(zhuǎn)型（Object -> E），這些是對我們應(yīng)用程序屏蔽的小細(xì)節(jié)。
5. remove函數(shù)
?
public E remove(int index) {
// 檢查索引是否合法
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 需要移動(dòng)的元素的個(gè)數(shù)
int numMoved = size -
23、 index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 賦值為空，有利于進(jìn)行GC
elementData[--size] = null;
// 返回舊值
return oldValue;
}
View Code
說明：remove函數(shù)用戶移除指定下標(biāo)的元素，此時(shí)會(huì)把指定下標(biāo)到數(shù)組末尾的元素向前移動(dòng)一個(gè)單位，并且會(huì)把數(shù)組最后一個(gè)元素設(shè)置為null，這樣是為了方便之后將整個(gè)數(shù)組不被使用時(shí)，會(huì)被GC，可以作為小的技巧使用。
四、總結(jié)
ArrayList有其特殊的應(yīng)用場景，與LinkedList相對應(yīng)。其優(yōu)點(diǎn)是隨機(jī)讀取，缺點(diǎn)是插入元素時(shí)需要移動(dòng)大量元素，效率不太高。至此，ArrayList的源碼分析就到這里，
9 / 9
JDK1.8源碼分析之ArrayList
