1 ArrayList
1.1 底層結(jié)構(gòu)
底層的數(shù)據(jù)結(jié)構(gòu)是數(shù)組铺敌，數(shù)組元素類型為Object類型踢涌，即可以存放所有類型數(shù)據(jù)黔龟。
1.2 優(yōu)缺點(diǎn)
動(dòng)態(tài)數(shù)組實(shí)現(xiàn)历等，查找快讨惩，增刪慢
2 四個(gè)關(guān)注點(diǎn)
| 關(guān)注點(diǎn) | 結(jié)論 |
|---|---|
| ArrayList是否允許空 | 允許 |
| ArrayList是否允許重復(fù)數(shù)據(jù) | 允許 |
| ArrayList是否有序 | 有序 |
| ArrayList是否線程安全 | 非線程安全 |
3 ArrayList源碼解析
3.1 類的繼承關(guān)系
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
說(shuō)明：ArrayList繼承AbstractList抽象父類，實(shí)現(xiàn)了List接口（規(guī)定了List的操作規(guī)范）募闲、RandomAccess（可隨機(jī)訪問(wèn)）步脓、Cloneable（可拷貝）、Serializable（可序列化）浩螺。
3.2 類的屬性
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 版本號(hào)
private static final long serialVersionUID = 8683452581122892189L;
// 缺省容量
private static final int DEFAULT_CAPACITY = 10;
// 空對(duì)象數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
// 缺省空對(duì)象數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素?cái)?shù)組
transient Object[] elementData;
// 實(shí)際元素大小靴患，默認(rèn)為0
private int size;
// 最大數(shù)組容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
說(shuō)明：類的屬性中核心的屬性為elementData，類型為Object[]要出，用于存放實(shí)際元素鸳君，并且被標(biāo)記為transient，也就意味著在序列化的時(shí)候患蹂，此字段是不會(huì)被序列化的或颊。
擴(kuò)展：為什么ArrayList的elementData是用transient修飾的？
看到ArrayList實(shí)現(xiàn)了Serializable接口传于，這意味著ArrayList是可以被序列化的囱挑，用transient修飾elementData意味著不希望elementData數(shù)組被序列化。這是為什么沼溜？因?yàn)樾蛄谢疉rrayList的時(shí)候平挑，ArrayList里面的elementData未必是滿的，比方說(shuō)elementData有10的大小系草，但是我只用了其中的3個(gè)通熄，那么是否有必要序列化整個(gè)elementData呢？顯然沒(méi)有這個(gè)必要找都，因此ArrayList中重寫了writeObject方法唇辨。每次序列化的時(shí)候調(diào)用這個(gè)方法，先調(diào)用defaultWriteObject()方法序列化ArrayList中的非transient元素能耻，elementData不去序列化它赏枚，然后遍歷elementData亡驰，只序列化那些有的元素，這樣：
1嗡贺、加快了序列化的速度
2隐解、減小了序列化之后的文件大小
不失為一種聰明的做法，如果以后開發(fā)過(guò)程中有遇到這種情況诫睬，也是值得學(xué)習(xí)煞茫、借鑒的一種思路。
3.3 類的構(gòu)造函數(shù)
1. ArrayList(int)型構(gòu)造函數(shù)
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) { // 初始容量大于0
this.elementData = new Object[initialCapacity]; // 根據(jù)初始容量初始化元素?cái)?shù)組
} else if (initialCapacity == 0) { // 初始容量為0
this.elementData = EMPTY_ELEMENTDATA; // 為空對(duì)象數(shù)組
} else { // 初始容量小于0摄凡，拋出異常
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
說(shuō)明：指定elementData數(shù)組的大小续徽，不允許初始化容量小于0，否則拋出異常亲澡。
2. ArrayList()型構(gòu)造函數(shù)
public ArrayList() {
// 無(wú)參構(gòu)造函數(shù)钦扭，設(shè)置元素?cái)?shù)組為空
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
說(shuō)明：當(dāng)未指定初始化容量時(shí)，會(huì)給elementData賦值為空集合床绪。
3. ArrayList(Collection<? extends E>)型構(gòu)造函數(shù)
public ArrayList(Collection<? extends E> c) { // 集合參數(shù)構(gòu)造函數(shù)
elementData = c.toArray(); // 將集合轉(zhuǎn)化為數(shù)組
if ((size = elementData.length) != 0) { // 集合非空
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;
}
}
說(shuō)明：當(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;
}
說(shuō)明：在add函數(shù)我們發(fā)現(xiàn)還有其他的函數(shù)ensureCapacityInternal，此函數(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); // 比較初始容量（10）和最小容量仰担，取較大值
}
ensureExplicitCapacity(minCapacity);
}
說(shuō)明：在ensureCapacityInternal函數(shù)中我們又發(fā)現(xiàn)了ensureExplicitCapacity函數(shù)，這個(gè)函數(shù)也是為了確保elemenData數(shù)組有合適的大小绩社。ensureExplicitCapacity的具體函數(shù)如下
private void ensureExplicitCapacity(int minCapacity) {
// 結(jié)構(gòu)性修改加1
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
說(shuō)明：在ensureExplicitCapacity函數(shù)我們又發(fā)現(xiàn)了grow函數(shù)摔蓝，grow函數(shù)才會(huì)對(duì)數(shù)組進(jìn)行擴(kuò)容，ensureCapacityInternal愉耙、ensureExplicitCapacity都只是過(guò)程贮尉，最后完成實(shí)際擴(kuò)容操作還是得看grow函數(shù)，grow函數(shù)的具體函數(shù)如下
private void grow(int minCapacity) {
int oldCapacity = elementData.length; // 舊容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量為舊容量的1.5倍
if (newCapacity - minCapacity < 0) // 新容量小于參數(shù)指定容量朴沿，修改新容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量大于最大容量
newCapacity = hugeCapacity(minCapacity); // 指定新容量
// 拷貝擴(kuò)容
elementData = Arrays.copyOf(elementData, newCapacity);
}
說(shuō)明：正常情況下會(huì)擴(kuò)容1.5倍猜谚，特殊情況下（新擴(kuò)展數(shù)組大小已經(jīng)達(dá)到了最大值）則只取最大值。
當(dāng)我們調(diào)用add方法時(shí)悯仙，實(shí)際上的函數(shù)調(diào)用如下
示例一（調(diào)用無(wú)參構(gòu)造函數(shù)）
List<Integer> lists = new ArrayList<Integer>();
lists.add(8);
說(shuō)明：初始化lists大小為0龄毡，調(diào)用的ArrayList()型構(gòu)造函數(shù)吠卷，那么在調(diào)用lists.add(8)方法時(shí)锡垄，會(huì)經(jīng)過(guò)怎樣的步驟呢？下圖給出了該程序執(zhí)行過(guò)程和最初與最后的elementData的大小
說(shuō)明：我們可以看到祭隔，在add方法之前開始elementData = {}货岭；調(diào)用add方法時(shí)會(huì)繼續(xù)調(diào)用路操，直至grow，最后elementData的大小變?yōu)?0千贯，之后再返回到add函數(shù)屯仗，把8放在elementData[0]中。
示例二（調(diào)用有參構(gòu)造函數(shù)：指定初始容量）
List<Integer> lists = new ArrayList<Integer>(6);
lists.add(8);
說(shuō)明：調(diào)用的ArrayList(int)型構(gòu)造函數(shù)搔谴，那么elementData被初始化為大小為6的Object數(shù)組魁袜，在調(diào)用add(8)方法時(shí)，具體的步驟如下：
說(shuō)明：相比上一個(gè)敦第，缺少一步grow()峰弹。因?yàn)檫M(jìn)行 if (minCapacity - elementData.length > 0) 判斷時(shí)，minCapacity為1芜果， elementData.length為6鞠呈，條件為false，因此不會(huì)調(diào)用grow(),不會(huì)進(jìn)行擴(kuò)容處理右钾。
2.set函數(shù)
public E set(int index, E element) {
// 檢驗(yàn)索引是否合法
rangeCheck(index);
// 舊值
E oldValue = elementData(index);
// 賦新值
elementData[index] = element;
// 返回舊值
return oldValue;
}
3.indexOf函數(shù)
// 從首開始查找數(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; i++) // 遍歷數(shù)組舀射，找到第一個(gè)和指定元素相等的元素窘茁，返回下標(biāo)
if (o.equals(elementData[i]))
return i;
}
// 沒(méi)有找到，返回空
return -1;
}
說(shuō)明：從頭開始查找與指定元素相等的元素后控，注意庙曙，是可以查找null元素的，意味著ArrayList中可以存放null元素的浩淘。與此函數(shù)對(duì)應(yīng)的lastIndexOf捌朴，表示從尾部開始查找。
4.get函數(shù)
public E get(int index) {
// 檢驗(yàn)索引是否合法
rangeCheck(index);
return elementData(index);
}
5.remove函數(shù)
public E remove(int index) {
// 檢查索引是否合法
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 需要移動(dòng)的元素的個(gè)數(shù)
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 賦值為空张抄，有利于進(jìn)行GC
elementData[--size] = null;
// 返回舊值
return oldValue;
}
說(shuō)明：remove函數(shù)用戶移除指定下標(biāo)的元素砂蔽，此時(shí)會(huì)把指定下標(biāo)到數(shù)組末尾的元素向前移動(dòng)一個(gè)單位，并且會(huì)把數(shù)組最后一個(gè)元素設(shè)置為null署惯，這樣是為了方便之后將整個(gè)數(shù)組不被使用時(shí)左驾，會(huì)被GC，可以作為小的技巧使用极谊。
