說明
本文內(nèi)容為本人平時(shí)學(xué)習(xí)時(shí)的筆記，是參考了網(wǎng)上绽昏、書上以及源碼（基于JDK1.8）等資料結(jié)合自己的學(xué)習(xí)方式的總結(jié)校焦；如若有不對(duì)的地方也歡迎指正。
關(guān)系
大概
ArrayList繼承自AbstractList，實(shí)現(xiàn)了List想虎、RandomAccess卦尊、Cloneable、Serializable
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)舌厨，容量可以進(jìn)行動(dòng)態(tài)的增長(zhǎng)岂却，實(shí)現(xiàn)List接口，具有List的特性
List關(guān)注的是索引裙椭，擁有一系列和索引相關(guān)的方法躏哩，查詢速度快。也正因?yàn)榇巳嗳迹诓迦牖騽h除數(shù)據(jù)時(shí)扫尺，會(huì)伴隨著后面數(shù)據(jù)的移動(dòng)，所以插入刪除數(shù)據(jù)速度慢炊汤。
實(shí)現(xiàn)RandomAccess接口正驻，支持快速隨機(jī)訪問
實(shí)現(xiàn)Cloneable接口弊攘，支持淺克隆
實(shí)現(xiàn)Serializable接口，支持序列化
成員變量
/** 默認(rèn)初始容量 */
private static final int DEFAULT_CAPACITY = 10;
/** 空數(shù)組 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** 默認(rèn)初始容量的空數(shù)組（用于不指定容量創(chuàng)建實(shí)例時(shí)使用拨拓，與EMPTY_ELEMENTDATA做區(qū)分） */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 用于存放ArrayList數(shù)據(jù)的數(shù)組
* 使用transient修飾使得該關(guān)鍵字聲明數(shù)組默認(rèn)不會(huì)被序列化（原因后面單獨(dú)做說明）
*/
transient Object[] elementData;
/** 長(zhǎng)度即實(shí)際數(shù)據(jù)的數(shù)量 */
private int size;
/** 繼承自AbstractList的成員變量肴颊，用于記錄更改次數(shù) */
protected transient int modCount = 0;
構(gòu)造
構(gòu)造方法總有有三個(gè)：無參構(gòu)造氓栈、指定容量大小渣磷、帶Collection形參的構(gòu)造
- 無參構(gòu)造 直接將
DEFAULTCAPACITY_EMPTY_ELEMENTDATA賦值給elementData
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 構(gòu)造一個(gè)指定容量大小的ArrayList，構(gòu)造時(shí)傳入一個(gè)
int類型的容量大小授瘦，在創(chuàng)建時(shí)會(huì)先判斷傳入的值是否為0醋界，不為0則直接將elementData初始化一個(gè)容量為initialCapacity的數(shù)組，為0則直接將EMPTY_ELEMENTDATA賦值給elementData
/** 指定大小初始化提完，通過initialCapacity來指定初始ArrayList容量大小 */
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
- 將Collection類型的集合作為參數(shù)來構(gòu)造
ArrayList形纺，調(diào)用c.toArray()，將集合轉(zhuǎn)換為數(shù)組并賦值給elementData
不過源碼中有這么一句注釋：
// c.toArray might (incorrectly) not return Object[] (see 6260652)
參考Java官方Bug文檔徒欣，大致意思就是：Arrays.asList()是將數(shù)組轉(zhuǎn)換為集合的一種方法逐样，但是其內(nèi)部對(duì)toArray方法的實(shí)現(xiàn)與集合中不一樣，不能保證返回的一定是Object[]類型（例如創(chuàng)建String類型的時(shí)候）打肝，簡(jiǎn)單說就是Arrays內(nèi)部類ArrayList中的toArray實(shí)現(xiàn)與ArrayList中的不一樣脂新，所以就有了對(duì)elementData類型的判斷
不過在1.9中已經(jīng)修復(fù)了這個(gè)問題
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
常用API方法
- 增加 add
在了解add方法之前，我們需要先了解一下ArrayList的擴(kuò)容機(jī)制
- ArrayList的擴(kuò)容機(jī)制
在兩個(gè)add方法中粗梭，首先都會(huì)調(diào)用ensureCapacityInternal(size + 1);這個(gè)方法來確保容量始終滿足當(dāng)前的要求争便。先看下源碼中的內(nèi)容
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
在ensureCapacityInternal方法中，首先會(huì)判斷當(dāng)前elementData是否是無參構(gòu)造是時(shí)賦值的DEFAULTCAPACITY_EMPTY_ELEMENTDATA断医，如果是滞乙，則在DEFAULT_CAPACITY（默認(rèn)大小，也就是10）與minCapacity（size + 1）中取最大值進(jìn)行下一步操作鉴嗤。到這可能會(huì)有一個(gè)疑問斩启，都確定是第一次無參創(chuàng)建時(shí)elementData，為什么還要進(jìn)行最大值的比較而不直接給一個(gè)10醉锅，源碼搜索ensureCapacityInternal時(shí)浇垦，會(huì)發(fā)現(xiàn)調(diào)用這個(gè)方法的不只是add，還有addAll荣挨，當(dāng)調(diào)用addAll的時(shí)候男韧，傳入的是一個(gè)Collection的集合，傳入的minCapacity是Collection的length+ArrayList的size默垄，所以是有minCapacity > DEFAULT_CAPACITY的可能存在的此虑。
接著會(huì)調(diào)用ensureExplicitCapacity方法，比較minCapacity和elementData.length的大小來判斷是否需要進(jìn)行擴(kuò)容口锭。（需要注意的是用于比較的是elementData.length而不是size朦前，elementData.length是底層數(shù)組的容量介杆，而size是ArrayList的容量。）
接下來就是gow方法就是動(dòng)態(tài)擴(kuò)容的核心了韭寸。
首先獲取elementData的長(zhǎng)度所謂原始容量oldCapacity春哨，然后計(jì)算一個(gè)擴(kuò)容后的容量（原始容量 + （原始容量向右位移1位后的容量）），也就是原始容量的1.5倍作為新容量newCapacity恩伺，接著比較新容量與需要容量大小赴背，把兩者中最大者賦值給newCapacity。最后再進(jìn)行newCapacity與MAX_ARRAY_SIZE進(jìn)行比較晶渠，這里有一個(gè)常量MAX_ARRAY_SIZE具體為值：Integer.MAX_VALUE - 8 數(shù)組
- 獲取 get
- 刪除 remove
- 更新 set
- 是否包含 indexof/contains
- 容量判斷 size/isEmpty
并發(fā)修改異常ConcurrentModificationException
ArrayList中有一個(gè)繼承制AbstractList的成員變量modCount凰荚，它的作用主要就是一個(gè)計(jì)數(shù)器，用于記錄集合被修改的次數(shù)褒脯。
在線程不安全的ArrayList使用迭代器（Iterator）的過程中便瑟，如果其他線程修改了ArrayList中的數(shù)據(jù)，就會(huì)報(bào)ConcurrentModificationException（并發(fā)修改異常）番川，這就是所謂的fail-fast機(jī)制到涂；同時(shí)需要注意的是，該異常不會(huì)始終指出對(duì)象已經(jīng)由不同線程并發(fā)修改颁督，如果單線程違反了規(guī)則践啄，同樣也有可能會(huì)拋出該異常。
在使用Iterator進(jìn)行遍歷的過程中适篙，如果使用List的remove方法刪除元素往核，會(huì)報(bào)并發(fā)修改異常也是這個(gè)原因；在ArrayList內(nèi)部實(shí)現(xiàn)的Iterator中的next方法和remove方法中嚷节，首先都需要執(zhí)行checkForComodification方法用于校驗(yàn)迭代器中的modCount值是否與ArrayList中的值相同聂儒，不相同則報(bào)并發(fā)修改異常；而使用迭代器自身的remove方法時(shí)硫痰，會(huì)調(diào)用ArrayList自身的remove方法進(jìn)行刪除操作同時(shí)更新modCount值衩婚，并且同時(shí)更新迭代器的modCount（expectedModCount）值，這就是為什么使用迭代器刪除不會(huì)報(bào)并發(fā)修改異常效斑。
