List的繼承結(jié)構(gòu)：
如圖可知List掠抬，有三個(gè)子實(shí)現(xiàn)類：ArrayList吼野，Vector，LinkedList两波。下面我們會(huì)依次對(duì)源碼進(jìn)行分析
ArrayList源碼分析
ArrayList一個(gè)動(dòng)態(tài)數(shù)組,其本質(zhì)也是用數(shù)組實(shí)現(xiàn)的瞳步，它具有：隨機(jī)訪問速度快，插入和移除性能較差(數(shù)組的特點(diǎn))腰奋；【支持null元素】谚攒；【有序】；元素【可重復(fù)】氛堕；【線程不安全】馏臭；
ArrayList實(shí)現(xiàn)了List接口以及l(fā)ist相關(guān)的所有方法，它允許所有元素的插入讼稚，包括null括儒。另外，ArrayList和Vector除了線程不同步之外锐想，大致相等帮寻。
繼承實(shí)現(xiàn)
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList繼承AbstractList并實(shí)現(xiàn)了List接口，RandomAccess接口（http://www.reibang.com/p/89aaaee1077e）
Cloneable接口赠摇，Serializable接口固逗，因此它支持快速訪問，可復(fù)制藕帜，可序列化烫罩。
屬性
/**
* 初始容量大小為10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 常量EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是為了初始化elementData的。
如果為無參構(gòu)造函數(shù)洽故，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA贝攒；
如果為含參構(gòu)造函數(shù)，使用EMPTY_ELEMENTDATA：
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*元素存放的地方时甚，由此可看出ArrayList內(nèi)部是用數(shù)組實(shí)現(xiàn)的
*/
transient Object[] elementData; //非私有便于內(nèi)部類訪問
/**
int類型的size表示數(shù)組中元素的個(gè)數(shù)
*/
private int size;
ArrayList底層是使用一個(gè)Object類型的數(shù)組來存放數(shù)據(jù)的隘弊，size變量代表List實(shí)際存放元素的數(shù)量
使用transient修飾哈踱，使用writeObject 和 readObject 方法是為了序列化、反序列化時(shí)節(jié)省空間和時(shí)間（http://blog.csdn.net/zero__007/article/details/52166306）
（http://www.importnew.com/12611.html）
為了對(duì)應(yīng)不同的構(gòu)造函數(shù)梨熙，ArrayList使用了不同的數(shù)組
代碼中有個(gè)常量开镣，表示數(shù)組的默認(rèn)容量，大小為10
構(gòu)造函數(shù)
/**
* 用指定的初始化容量構(gòu)造一個(gè)空的List
*
* @param initialCapacity 初始容量
* @throws IllegalArgumentException 如果初始容量為負(fù)數(shù)拋出異常
*
*/
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);
}
}
/**
* 無參構(gòu)造咽扇，默認(rèn)我空的數(shù)組邪财，當(dāng)添加第一個(gè)元素時(shí)，創(chuàng)建一個(gè)初始容量為10的數(shù)組
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
常量EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是為了初始化elementData的肌割。如果為無參構(gòu)造函數(shù)，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA帐要；如果為含參構(gòu)造函數(shù)把敞，使用EMPTY_ELEMENTDATA，使用上述構(gòu)造函數(shù)榨惠，elementData中沒有元素奋早，size為0，不過elementData的長(zhǎng)度有可能不同赠橙。
ArrayList還提供了使用集合構(gòu)造的構(gòu)造函數(shù)：
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;
}
}
函數(shù)首先將集合c轉(zhuǎn)化為數(shù)組耽装，然后檢查轉(zhuǎn)化的類型，如果不是Object[]類型期揪，使用Arrays類中的copyOf方法進(jìn)行復(fù)制掉奄；同時(shí)，如果c中沒有元素凤薛，使用EMPTY_ELEMENTDATA初始化姓建。
增刪改查操作
get和set方法，都是通過數(shù)組下標(biāo)缤苫，直接操作數(shù)據(jù)的速兔，時(shí)間復(fù)雜度為O(1)
查詢
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
// 遍歷所有元素找到相同的元素，返回元素的下標(biāo)活玲，
// 如果是元素為null涣狗，則直接比較地址，否則使用equals的方法比較
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
增加
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 擴(kuò)容檢測(cè)
elementData[size++] = e;//新增元素添加到末尾
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);//添加容量檢測(cè)
ensureCapacityInternal(size + 1); // 擴(kuò)容檢測(cè)
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 使用System.arraycopy的方法舒憾，將index后面元素往后移動(dòng)1位
elementData[index] = element;// 存放元素到index位置
size++;
}
//添加一個(gè)集合的元素到末端镀钓，若要添加的集合為空返回false
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
//從指定位置添加一個(gè)集合的元素，若要添加的集合為空返回false
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
//添加方式為：先將指定位置后的元素后移镀迂，再復(fù)制參數(shù)集合的元素到指定位置后
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
刪除
public E remove(int index) {
rangeCheck(index);//越界檢測(cè)
modCount++;
E oldValue = elementData(index);//舊值
int numMoved = size - index - 1; // 需要移動(dòng)元素的數(shù)量
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //方便JVM進(jìn)行GC操作掸宛，避免出現(xiàn)泄露
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
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
}
removeRange
//刪除指定范圍內(nèi)元素
protected void removeRange(int fromIndex, int toIndex) {
//數(shù)組改變，modCount++
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex - fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
removeAll 和 retainAll
//刪除指定集合的元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c); //檢查集合是否為空
return batchRemove(c, false); //調(diào)用batchRemove招拙，complement為false
}
//與removeAll相反唧瘾，僅保留指定集合的元素
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c); //檢查集合是否為空
return batchRemove(c, true); //調(diào)用batchRemove措译，complement為true
}
//complement true時(shí)從數(shù)組保留指定集合中元素的值，為false時(shí)從數(shù)組刪除指定集合中元素的值饰序。
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0; //w為數(shù)組更新后的大小
boolean modified = false;
try {
//遍歷數(shù)組领虹，并檢查元素是否在指定集合中，根據(jù)complement的值保留特定值到數(shù)組
//若complement為true即保留求豫，則將相同元素移動(dòng)到數(shù)組前端
//若complement為false即刪除塌衰，則將不同元素移動(dòng)到數(shù)組前端
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
//如果r!=size則說明c.contains(elementData[r])拋出異常
if (r != size) {
//將數(shù)組未遍歷的部分添加
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//如果w!=size說明進(jìn)行了刪除操作，故需將刪除的值賦為null
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w; //更新數(shù)組容量
modified = true;
}
}
return modified;
}
clear
//清空數(shù)組蝠嘉，全部賦值為null最疆，方便垃圾回收
public void clear() {
//數(shù)組改變，modCount++
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
其他重要方法
擴(kuò)容
在添加一個(gè)元素之前蚤告，先調(diào)用一下ensureCapacityInternal方法努酸，這個(gè)方法如下
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
它首先判斷Array的底層數(shù)組elementData與默認(rèn)的空數(shù)組是不是相同，如果相同杜恰，就需要取默認(rèn)容量（java8中默認(rèn)是10）與你傳進(jìn)來參數(shù)的最大值获诈，這個(gè)判斷的目的是為了List中的addAll()方法，它會(huì)增加一個(gè)collection到這個(gè)數(shù)組里來心褐，這個(gè)collection容量大于10舔涎，那么就要拓展這個(gè)數(shù)組的大小。就是通過ensureExplicitCapacity來實(shí)現(xiàn)逗爹。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount是父類AbstractList里的一個(gè)成員變量亡嫌，用來記錄List的修改次數(shù)的，這里不再討論掘而。 下面if判斷就是指如果添加完元素后的容量大于當(dāng)前數(shù)組長(zhǎng)度昼伴，就要對(duì)數(shù)組擴(kuò)容。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
}
oldCapacity>>1 指向右移一位镣屹，實(shí)際為oldCapacity/2 取整圃郊，這樣直接位運(yùn)算速度較快，這跟jdk之前的版本不一樣女蜈，以前是容量*1.5倍然后加1持舆，新的jdk減少了步驟。
最后一句就是擴(kuò)容的最終實(shí)現(xiàn)
Arrays.copyOf Jdk8也與以前的版本不同伪窖，之前直接使用System.arraycopy()實(shí)現(xiàn)這一功能逸寓，最新版將這一步又重新封裝了一層，這兒不再詳貼覆山，有意的可以自己翻看一下竹伸。
//檢查參數(shù)是否溢出
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // // 溢出
throw new OutOfMemoryError();
//如果參數(shù)比默認(rèn)的最大值大，則取最大整數(shù)值，否則取容量默認(rèn)最大值
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
保存和讀取
//保存數(shù)組實(shí)例的狀態(tài)到一個(gè)流（即它序列化）勋篓。寫入過程數(shù)組被更改（利用modCount的值）會(huì)拋出異常
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount; //寫入前modCount的值吧享，將依據(jù)此檢查寫入過程數(shù)組是否被更改
s.defaultWriteObject();
// 寫入容量大小
s.writeInt(size);
// 按順序?qū)懭霐?shù)組元素
for (int i = 0; i < size; i++) {
s.writeObject(elementData[i]);
}
// 若寫入前后modCount值不同，說明寫入過程數(shù)組被更改譬嚣，則拋出異常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
//讀操作钢颂，跟上述寫操作類似
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i = 0; i < size; i++) {
a[i] = s.readObject();
}
}
}
總結(jié)
fail-fast機(jī)制的實(shí)現(xiàn)
fail-fast機(jī)制也叫作”快速失敗”機(jī)制，是Java集合中的一種錯(cuò)誤檢測(cè)機(jī)制拜银。
在對(duì)集合進(jìn)行迭代過程中殊鞭，除了迭代器可以對(duì)集合進(jìn)行數(shù)據(jù)結(jié)構(gòu)上進(jìn)行修改，其他的對(duì)集合的數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改尼桶，都會(huì)拋出ConcurrentModificationException錯(cuò)誤操灿。
這里，所謂的進(jìn)行數(shù)據(jù)結(jié)構(gòu)上進(jìn)行修改,是指對(duì)存儲(chǔ)的對(duì)象泵督，進(jìn)行add,set,remove操作趾盐，進(jìn)而對(duì)數(shù)據(jù)發(fā)生改變。
ArrayList中幌蚊，有個(gè)modCount的變量谤碳，每次進(jìn)行add溃卡，set溢豆，remove等操作，都會(huì)執(zhí)行modCount++瘸羡。
在獲取ArrayList的迭代器時(shí)漩仙，會(huì)將ArrayList中的modCount保存在迭代中，
每次執(zhí)行add,set,remove等操作犹赖，都會(huì)執(zhí)行一次檢查队他，調(diào)用checkForComodification方法，對(duì)modCount進(jìn)行比較峻村。
如果迭代器中的modCount和List中的modCount不同麸折，則拋出ConcurrentModificationException
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
使用場(chǎng)景
ArrayList的使用場(chǎng)景主要從其優(yōu)缺點(diǎn)來考慮的：
優(yōu)點(diǎn)：
get，set粘昨，時(shí)間復(fù)雜度為O(1)
add（一般都是在末尾插入）垢啼，時(shí)間復(fù)雜度為O(1)，最差情況下（往頭部插入數(shù)據(jù)）张肾，時(shí)間復(fù)雜度O(n)
數(shù)據(jù)存儲(chǔ)是順序的
缺點(diǎn)：
remove芭析，時(shí)間復(fù)雜度為O(n)，最優(yōu)情況下（移除末尾元素）吞瞪，時(shí)間復(fù)雜度為O(1)
ArrayList底層使用數(shù)組存儲(chǔ)數(shù)據(jù)馁启，數(shù)組是不能自動(dòng)擴(kuò)容的，因此在發(fā)生擴(kuò)容的情況下芍秆，需要移動(dòng)大量的元素惯疙。
ArrayList大小很大的時(shí)候翠勉，會(huì)存在空間浪費(fèi)（可以通過trimToSize方法，清除空閑空間）
數(shù)組大小是由限制的螟碎，受jvm和機(jī)器的影響眉菱，當(dāng)擴(kuò)容超出上限時(shí)，ArrayList會(huì)拋出異常
插入操作多掉分，數(shù)據(jù)量不大俭缓，順序存儲(chǔ)時(shí)，可以考慮使用ArrayList
多線程情況下：
ArrayList所有的操作酥郭，都不是同步的华坦，因此ArrayList不是線程安全的。
如果考慮到線程安全的話不从，可以使用CopyOnWriteArrayList或者外部同步ArrayList（List list = Collections.synchronizedList(new ArrayList(…));）
思考
1.remove方法中惜姐，為什么會(huì)將數(shù)組對(duì)應(yīng)的元素置為null？
ArrayList內(nèi)部使用數(shù)組實(shí)現(xiàn)一套管理對(duì)象的機(jī)制椿息，remove操作中歹袁，已經(jīng)將元素的數(shù)量-1了，ArrayList認(rèn)為該對(duì)象已經(jīng)被移除了寝优，應(yīng)該被jvm回收条舔。
但是，對(duì)于jvm來說乏矾，該值仍然保存在數(shù)組中孟抗，ArrayList持有這個(gè)對(duì)象的引用，在jvm發(fā)生GC時(shí)钻心，這個(gè)對(duì)象是不對(duì)被jvm回收凄硼，這樣就會(huì)造成內(nèi)存泄露了。
2.查找元素的方法中（比如indexOf）捷沸，為什么需要對(duì)元素進(jìn)行null值判斷摊沉？
判斷對(duì)象是否相等，有兩個(gè)方面痒给，1.對(duì)象存儲(chǔ)的地址说墨；2.對(duì)象的內(nèi)容。
==侈玄，是用來比較兩個(gè)對(duì)象的地址是否相等婉刀，一般來說，兩個(gè)對(duì)象的地址相同序仙，那么這兩個(gè)對(duì)象可以認(rèn)為是相同的對(duì)象
equals方法突颊，是用來比較對(duì)象內(nèi)容的，當(dāng)然，也可以重載該方法律秃，直接比較對(duì)象地址爬橡；Object對(duì)象的equals方法，是比較地址的棒动。
一般來說糙申，重載equals方法的同時(shí)，也要重載hashCode方法的船惨，重載hashCode方法柜裸，必須得遵守6個(gè)原則：
自反性：對(duì)于任何非null的引用值x，x.equals(x),必須返回true
傳遞性：對(duì)于任何非null的引用值x,y,z粱锐，如果x.equals(y) 為true疙挺，且y.equals(z)為true，那么x.equals(z)必須為true
對(duì)稱性：對(duì)于任何非null的引用值x,y怜浅，如果x.equals(y)為true铐然，那么y.equals(x)必須為true
非空性：對(duì)于任何非null的引用值x,x.equals(null)必須為false
一致性：對(duì)于任何非null的引用值x，y恶座，如果多次調(diào)用equals方法搀暑，如果x和y比較的值沒有改變，那么x.equals(y)就會(huì)一致性返回true或者false
為什么重載equals方法跨琳，一般要重載hashCode方法自点？
重載equals方法，可以不重載hashCode方法湾宙，但是一般情況樟氢，不建議這么做冈绊。
hashCode方法侠鳄，使用來求出對(duì)象的Hash值，
重載hashCode方法主要是為了提高一些容器（比如HashMap死宣，Hashtable）進(jìn)行hash運(yùn)算的效率伟恶，而且也可以避免出現(xiàn)一些錯(cuò)誤（比如HashSet容器的操作）
對(duì)于元素進(jìn)行null值判斷，我認(rèn)為主要是為了效率考慮毅该，如果是null值的話博秫，可以直接比較地址，而非空值眶掌，則需要通過equals方法來比較挡育，由于ArrayList是泛型的，
所以其添加的元素朴爬，可能重載equals方法即寒，自定義了判斷的原則。
3.grow方法中，對(duì)新容量大小進(jìn)行判斷母赵，為什么會(huì)定義MAX_ARRAY_SIZE的逸爵？
ArrayList底層存儲(chǔ)是使用數(shù)組來實(shí)現(xiàn)的，所以ArrayList存儲(chǔ)文件的大小必定受數(shù)組大小的限制凹嘲，所以在擴(kuò)容中师倔，可以看到ArrayList對(duì)新容量大小進(jìn)行邏輯判斷。
影響數(shù)組最大值：
理論上最大值為Integer.MAX_VALUE(2^32 - 1)
對(duì)象頭限制周蹭，不同類型的元素趋艘，可創(chuàng)建數(shù)組的最大值是不同的，byte是1字節(jié)凶朗，int是4字節(jié)
比如jvm可用內(nèi)存為1M致稀，32位機(jī)器下，
int[] bytes = new int[1024 * 1024 / 4];
byte[] bytes = new byte[1024 * 1024];
jvm可用內(nèi)存大小限制
比如jvm可用內(nèi)存為1M俱尼，32位機(jī)器下抖单，
byte[] bytes = byte[1024 * 1024]
至于為什么MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
某些機(jī)器上需要存儲(chǔ)Headerwords
避免一些機(jī)器內(nèi)存溢出，減少出錯(cuò)幾率遇八，所以少分配
最大還是能支持到 Integer.MAX_VALUE
