ArrayList概述
（1）ArrayList 是一種變長(zhǎng)的集合類豺鼻，基于定長(zhǎng)數(shù)組實(shí)現(xiàn)。
（2）ArrayList 允許空值和重復(fù)元素蹲坷，當(dāng)往 ArrayList 中添加的元素?cái)?shù)量大于其底層數(shù)組容量時(shí)礁苗，其會(huì)通過(guò)擴(kuò)容機(jī)制重新生成一個(gè)更大的數(shù)組。
（3）由于 ArrayList 底層基于數(shù)組實(shí)現(xiàn)办绝，所以其可以保證在 O(1) 復(fù)雜度下完成隨機(jī)查找操作。
（4）ArrayList 是非線程安全類姚淆，并發(fā)環(huán)境下孕蝉，多個(gè)線程同時(shí)操作 ArrayList，會(huì)引發(fā)不可預(yù)知的異畴绶辏或錯(cuò)誤降淮。
ArrayList的成員屬性
在介紹關(guān)于ArrayList的各種方法之前先看一下基礎(chǔ)屬性成員。其中DEFAULTCAPACITY_EMPTY_ELEMENTDATA與EMPTY_ELEMENTDATA的區(qū)別是：當(dāng)我們向數(shù)組中添加第一個(gè)元素時(shí)搏讶，DEFAULTCAPACITY_EMPTY_ELEMENTDATA將會(huì)知道數(shù)組該擴(kuò)充多少佳鳖。
//默認(rèn)初始化容量
private static final int DEFAULT_CAPACITY = 10;
//默認(rèn)的空的數(shù)組，這個(gè)主要是在構(gòu)造方法初始化一個(gè)空數(shù)組的時(shí)候使用
private static final Object[] EMPTY_ELEMENTDATA = {};
//使用默認(rèn)size大小的空數(shù)組實(shí)例媒惕，和EMPTY_ELEMENTDATA區(qū)分開(kāi)來(lái)系吩，
//這樣可以知道當(dāng)?shù)谝粋€(gè)元素添加的時(shí)候進(jìn)行擴(kuò)容至多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList底層存儲(chǔ)數(shù)據(jù)就是通過(guò)數(shù)組的形式，ArrayList長(zhǎng)度就是數(shù)組的長(zhǎng)度妒蔚。
//一個(gè)空的實(shí)例elementData為上面的DEFAULTCAPACITY_EMPTY_ELEMENTDATA穿挨，當(dāng)添加第一個(gè)元素的時(shí)候
//會(huì)進(jìn)行擴(kuò)容月弛，擴(kuò)容大小就是上面的默認(rèn)容量DEFAULT_CAPACITY
transient Object[] elementData; // non-private to simplify nested class access
//arrayList的大小
private int size;
static修飾的EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA
ArrayList構(gòu)造方法
（1）帶有初始化容量的構(gòu)造方法
參數(shù)大于0，elementData初始化為initialCapacity大小的數(shù)組
參數(shù)小于0科盛，elementData初始化為空數(shù)組
參數(shù)小于0帽衙，拋出異常
//參數(shù)為初始化容量
public ArrayList(int initialCapacity) {
//判斷容量的合法性
if (initialCapacity > 0) {
//elementData才是實(shí)際存放元素的數(shù)組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果傳遞的長(zhǎng)度為0，就是直接使用自己已經(jīng)定義的成員變量(一個(gè)空數(shù)組)
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
（2）無(wú)參構(gòu)造
構(gòu)造方法中將elementData初始化為空數(shù)組DEFAULTCAPACITY_EMPTY_ELEMENTDATA
當(dāng)調(diào)用add方法添加第一個(gè)元素的時(shí)候贞绵，會(huì)進(jìn)行擴(kuò)容
擴(kuò)容至大小為DEFAULT_CAPACITY=10
//無(wú)參構(gòu)造厉萝，使用默認(rèn)的size為10的空數(shù)組，在構(gòu)造方法中沒(méi)有對(duì)數(shù)組長(zhǎng)度進(jìn)行設(shè)置但壮，會(huì)在后續(xù)調(diào)用add方法的時(shí)候進(jìn)行擴(kuò)容
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
（3）參數(shù)為Collection類型的構(gòu)造器
//將一個(gè)參數(shù)為Collection的集合轉(zhuǎn)變?yōu)锳rrayList（實(shí)際上就是將集合中的元素?fù)Q為了數(shù)組的形式）。如果
//傳入的集合為null會(huì)拋出空指針異常（調(diào)用c.toArray()方法的時(shí)候）
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//c.toArray()可能不會(huì)正確地返回一個(gè) Object[]數(shù)組常侣，那么使用Arrays.copyOf()方法
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果集合轉(zhuǎn)換為數(shù)組之后數(shù)組長(zhǎng)度為0蜡饵，就直接使用自己的空成員變量初始化elementData
this.elementData = EMPTY_ELEMENTDATA;
}
}
上面的這些構(gòu)造方法理解起來(lái)比較簡(jiǎn)單，關(guān)注前兩個(gè)構(gòu)造方法做的事情胳施，目的都是初始化底層數(shù)組 elementData(this.elementData=XXX)溯祸。區(qū)別在于無(wú)參構(gòu)造方法會(huì)將 elementData 初始化一個(gè)空數(shù)組，插入元素時(shí)舞肆，擴(kuò)容將會(huì)按默認(rèn)值重新初始化數(shù)組焦辅。而有參的構(gòu)造方法則會(huì)將 elementData 初始化為參數(shù)值大小（>= 0）的數(shù)組椿胯。一般情況下筷登，我們用默認(rèn)的構(gòu)造方法即可。倘若在可知道將會(huì)向 ArrayList 插入多少元素的情況下哩盲，可以使用有參構(gòu)造方法前方。
上面說(shuō)到了使用無(wú)參構(gòu)造的時(shí)候，在調(diào)用add方法的時(shí)候會(huì)進(jìn)行擴(kuò)容廉油，所以下面我們就看看add方法以及擴(kuò)容的細(xì)節(jié)
ArrayList的add方法
add方法大致流程
//將指定元素添加到list的末尾
public boolean add(E e) {
//因?yàn)橐砑釉鼗菹眨蕴砑又罂赡軐?dǎo)致容量不夠，所以需要在添加之前進(jìn)行判斷（擴(kuò)容）
ensureCapacityInternal(size + 1); // Increments modCount!!（待會(huì)會(huì)介紹到fast-fail）
elementData[size++] = e;
return true;
}
我們看到add方法中在添加元素之前抒线，會(huì)先判斷size的大小班巩，所以我們來(lái)看看ensureCapacityInternal方法的細(xì)節(jié)
ensureCapacityInternal方法分析
private void ensureCapacityInternal(int minCapacity) {
//這里就是判斷elementData數(shù)組是不是為空數(shù)組
//（使用的無(wú)參構(gòu)造的時(shí)候，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA）
//如果是嘶炭，那么比較size+1(第一次調(diào)用add的時(shí)候size+1=1)和DEFAULT_CAPACITY抱慌，
//那么顯然容量為10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
當(dāng) 要 add 進(jìn)第1個(gè)元素時(shí)，minCapacity為(size+1=0+1=)1眨猎，在Math.max()方法比較后遥缕，minCapacity 為10。然后緊接著調(diào)用ensureExplicitCapacity更新modCount的值宵呛，并判斷是否需要擴(kuò)容
ensureExplicitCapacity方法分析
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //這里就是add方法中注釋的Increments modCount
//溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);//這里就是執(zhí)行擴(kuò)容的方法
}
下面來(lái)看一下擴(kuò)容的主要方法grow单匣。
grow方法分析
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// oldCapacity為舊數(shù)組的容量
int oldCapacity = elementData.length;
// newCapacity為新數(shù)組的容量（oldCap+oldCap/2:即更新為舊容量的1.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 檢查新容量的大小是否小于最小需要容量，如果小于那舊將最小容量最為數(shù)組的新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于MAX_ARRAY_SIZE，使用hugeCapacity比較二者
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 將原數(shù)組中的元素拷貝
elementData = Arrays.copyOf(elementData, newCapacity);
}
hugeCapacity方法
這里簡(jiǎn)單看一下hugeCapacity方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//對(duì)minCapacity和MAX_ARRAY_SIZE進(jìn)行比較
//若minCapacity大户秤，將Integer.MAX_VALUE作為新數(shù)組的大小
//若MAX_ARRAY_SIZE大码秉，將MAX_ARRAY_SIZE作為新數(shù)組的大小
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
add方法執(zhí)行流程總結(jié)
我們用一幅圖來(lái)簡(jiǎn)單梳理一下，當(dāng)使用無(wú)參構(gòu)造的時(shí)候鸡号，在第一次調(diào)用add方法之后的執(zhí)行流程
這是第一次調(diào)用add方法的過(guò)程转砖，當(dāng)擴(kuò)容值capacity為10之后，
繼續(xù)添加第2個(gè)元素（先注意調(diào)用ensureCapacityInternal方法傳遞的參數(shù)為size+1=1+1=2）
在ensureCapacityInternal方法中鲸伴，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA不成立府蔗，所以直接執(zhí)行ensureExplicitCapacity方法
ensureExplicitCapacity方法中minCapacity為剛剛傳遞的2，所以第二個(gè)if判斷（2-10=-8）不會(huì)成立汞窗，即newCapacity 不比 MAX_ARRAY_SIZE大姓赤，則不會(huì)進(jìn)入
grow方法。數(shù)組容量為10仲吏，add方法中 return true,size增為1不铆。假設(shè)又添加3、4......10個(gè)元素（其中過(guò)程類似裹唆，但是不會(huì)執(zhí)行g(shù)row擴(kuò)容方法）
當(dāng)add第11個(gè)元素時(shí)候誓斥，會(huì)進(jìn)入grow方法時(shí)，計(jì)算newCapacity為15许帐，比minCapacity（為10+1=11）大劳坑，第一個(gè)if判斷不成立。新容量沒(méi)有大于數(shù)組最大size成畦，不會(huì)進(jìn)入hugeCapacity方法泡垃。數(shù)組容量擴(kuò)為15，add方法中return true,size增為11羡鸥。
add(int index,E element)方法
//在元素序列 index 位置處插入
public void add(int index, E element) {
rangeCheckForAdd(index); //校驗(yàn)傳遞的index參數(shù)是不是合法
// 1. 檢測(cè)是否需要擴(kuò)容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 將 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. 將新元素插入至 index 處
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0) //這里判斷的index>size（保證數(shù)組的連續(xù)性）蔑穴，index小于0
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
add(int index, E element)方法（在元素序列指定位置（假設(shè)該位置合理）插入）的過(guò)程大概是下面這些
檢測(cè)數(shù)組是否有足夠的空間(這里的實(shí)現(xiàn)和上面的)
將 index 及其之后的所有元素向后移一位
將新元素插入至 index 處.
將新元素插入至序列指定位置，需要先將該位置及其之后的元素都向后移動(dòng)一位惧浴，為新元素騰出位置存和。這個(gè)操作的時(shí)間復(fù)雜度為O(N)，頻繁移動(dòng)元素可能會(huì)導(dǎo)致效率問(wèn)題衷旅，特別是集合中元素?cái)?shù)量較多時(shí)捐腿。在日常開(kāi)發(fā)中，若非所需柿顶，我們應(yīng)當(dāng)盡量避免在大集合中調(diào)用第二個(gè)插入方法茄袖。
ArrayList的remove方法
ArrayList支持兩種刪除元素的方式
1、remove(int index) 按照下標(biāo)刪除
public E remove(int index) {
rangeCheck(index); //校驗(yàn)下標(biāo)是否合法（如果index>size嘁锯，舊拋出IndexOutOfBoundsException異常）
modCount++;//修改list結(jié)構(gòu)宪祥，就需要更新這個(gè)值
E oldValue = elementData(index); //直接在數(shù)組中查找這個(gè)值
int numMoved = size - index - 1;//這里計(jì)算所需要移動(dòng)的數(shù)目
//如果這個(gè)值大于0 說(shuō)明后續(xù)有元素需要左移(size=index+1)
//如果是0說(shuō)明被移除的對(duì)象就是最后一位元素(不需要移動(dòng)別的元素)
if (numMoved > 0)
//索引index只有的所有元素左移一位 覆蓋掉index位置上的元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//移動(dòng)之后聂薪，原數(shù)組中size位置null
elementData[--size] = null; // clear to let GC do its work
//返回舊值
return oldValue;
}
//src:源數(shù)組
//srcPos:從源數(shù)組的srcPos位置處開(kāi)始移動(dòng)
//dest:目標(biāo)數(shù)組
//desPos:源數(shù)組的srcPos位置處開(kāi)始移動(dòng)的元素，這些元素從目標(biāo)數(shù)組的desPos處開(kāi)始填充
//length:移動(dòng)源數(shù)組的長(zhǎng)度
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
刪除過(guò)程如下圖所示
2蝗羊、remove(Object o) 按照元素刪除藏澳，會(huì)刪除和參數(shù)匹配的第一個(gè)元素
public boolean remove(Object o) {
//如果元素是null 遍歷數(shù)組移除第一個(gè)null
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//遍歷找到第一個(gè)null元素的下標(biāo) 調(diào)用下標(biāo)移除元素的方法
fastRemove(index);
return true;
}
} else {
//找到元素對(duì)應(yīng)的下標(biāo) 調(diào)用下標(biāo)移除元素的方法
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//按照下標(biāo)移除元素（通過(guò)數(shù)組元素的位置移動(dòng)來(lái)達(dá)到刪除的效果）
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
ArrayList的其他方法
ensureCapacity方法
最好在 add 大量元素之前用 ensureCapacity 方法，以減少增量從新分配的次數(shù)
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
ArrayList總結(jié)
（1）ArrayList 是一種變長(zhǎng)的集合類耀找，基于定長(zhǎng)數(shù)組實(shí)現(xiàn)翔悠，使用默認(rèn)構(gòu)造方法初始化出來(lái)的容量是10（1.7之后都是延遲初始化，即第一次調(diào)用add方法添加元素的時(shí)候才將elementData容量初始化為10）野芒。
（2）ArrayList 允許空值和重復(fù)元素蓄愁，當(dāng)往 ArrayList 中添加的元素?cái)?shù)量大于其底層數(shù)組容量時(shí)，其會(huì)通過(guò)擴(kuò)容機(jī)制重新生成一個(gè)更大的數(shù)組狞悲。ArrayList擴(kuò)容的長(zhǎng)度是原長(zhǎng)度的1.5倍
（3）由于 ArrayList 底層基于數(shù)組實(shí)現(xiàn)撮抓，所以其可以保證在 O(1) 復(fù)雜度下完成隨機(jī)查找操作。
（4）ArrayList 是非線程安全類效诅，并發(fā)環(huán)境下胀滚，多個(gè)線程同時(shí)操作 ArrayList趟济，會(huì)引發(fā)不可預(yù)知的異陈彝叮或錯(cuò)誤。
（5）順序添加很方便
（6）刪除和插入需要復(fù)制數(shù)組顷编，性能差（可以使用LinkindList）
（7）Integer.MAX_VALUE - 8 ：主要是考慮到不同的JVM,有的JVM會(huì)在加入一些數(shù)據(jù)頭,當(dāng)擴(kuò)容后的容量大于MAX_ARRAY_SIZE,我們會(huì)去比較最小需要容量和MAX_ARRAY_SIZE做比較,如果比它大, 只能取Integer.MAX_VALUE,否則是Integer.MAX_VALUE -8戚炫。這個(gè)是從jdk1.7開(kāi)始才有的
fast-fail機(jī)制
fail-fast的解釋：
In systems design, a fail-fast system is one which immediately reports at its interface any condition that is likely to indicate a failure. Fail-fast systems are usually designed to stop normal operation rather than attempt to continue a possibly flawed process. Such designs often check the system’s state at several points in an operation, so any failures can be detected early. The responsibility of a fail-fast module is detecting errors, then letting the next-highest level of the system handle them.
大概意思是：在系統(tǒng)設(shè)計(jì)中，快速失效系統(tǒng)一種可以立即報(bào)告任何可能表明故障的情況的系統(tǒng)媳纬∷簦快速失效系統(tǒng)通常設(shè)計(jì)用于停止正常操作，而不是試圖繼續(xù)可能存在缺陷的過(guò)程钮惠。這種設(shè)計(jì)通常會(huì)在操作中的多個(gè)點(diǎn)檢查系統(tǒng)的狀態(tài)茅糜，因此可以及早檢測(cè)到任何故障∷赝欤快速失敗模塊的職責(zé)是檢測(cè)錯(cuò)誤蔑赘，然后讓系統(tǒng)的下一個(gè)最高級(jí)別處理錯(cuò)誤。
其實(shí)就是在做系統(tǒng)設(shè)計(jì)的時(shí)候先考慮異常情況预明，一旦發(fā)生異常缩赛，直接停止并上報(bào)，比如下面的這個(gè)簡(jiǎn)單的例子
//這里的代碼是一個(gè)對(duì)兩個(gè)整數(shù)做除法的方法撰糠，在fast_fail_method方法中酥馍，我們對(duì)被除數(shù)做了個(gè)簡(jiǎn)單的檢查，如果其值為0阅酪，那么就直接拋出一個(gè)異常旨袒，并明確提示異常原因汁针。這其實(shí)就是fail-fast理念的實(shí)際應(yīng)用。
public int fast_fail_method(int arg1,int arg2){
if(arg2 == 0){
throw new RuntimeException("can't be zero");
}
return arg1/arg2;
}
在Java集合類中很多地方都用到了該機(jī)制進(jìn)行設(shè)計(jì)峦失，一旦使用不當(dāng)扇丛，觸發(fā)fail-fast機(jī)制設(shè)計(jì)的代碼，就會(huì)發(fā)生非預(yù)期情況尉辑。我們通常說(shuō)的Java中的fail-fast機(jī)制帆精，默認(rèn)指的是Java集合的一種錯(cuò)誤檢測(cè)機(jī)制。當(dāng)多個(gè)線程對(duì)部分集合進(jìn)行結(jié)構(gòu)上的改變的操作時(shí)隧魄，有可能會(huì)觸發(fā)該機(jī)制時(shí)卓练，之后就會(huì)拋出并發(fā)修改異常ConcurrentModificationException.當(dāng)然如果不在多線程環(huán)境下，如果在foreach遍歷的時(shí)候使用add/remove方法购啄，也可能會(huì)拋出該異常襟企，這里簡(jiǎn)單做個(gè)總結(jié)。
之所以會(huì)拋出ConcurrentModificationException異常狮含，是因?yàn)槲覀兊拇a中使用了增強(qiáng)for循環(huán)顽悼，而在增強(qiáng)for循環(huán)中，集合遍歷是通過(guò)iterator進(jìn)行的几迄，但是元素的add/remove卻是直接使用的集合類自己的方法蔚龙。這就導(dǎo)致iterator在遍歷的時(shí)候，會(huì)發(fā)現(xiàn)有一個(gè)元素在自己不知不覺(jué)的情況下就被刪除/添加了映胁，就會(huì)拋出一個(gè)異常木羹，用來(lái)提示可能發(fā)生了并發(fā)修改！所以解孙，在使用Java的集合類的時(shí)候坑填，如果發(fā)生ConcurrentModificationException，優(yōu)先考慮fail-fast有關(guān)的情況弛姜，實(shí)際上這可能并沒(méi)有真的發(fā)生并發(fā)脐瑰，只是Iterator使用了fail-fast的保護(hù)機(jī)制，只要他發(fā)現(xiàn)有某一次修改是未經(jīng)過(guò)自己進(jìn)行的廷臼，那么就會(huì)拋出異常苍在。
