List的繼承結(jié)構(gòu)：
如圖可知List，有三個子實(shí)現(xiàn)類：ArrayList，Vector，LinkedList。下面我們會依次對源碼進(jìn)行分析
ArrayList源碼分析
ArrayList一個動態(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.itdecent.cn/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ù)組中元素的個數(shù)
*/
private int size;
ArrayList底層是使用一個Object類型的數(shù)組來存放數(shù)據(jù)的，size變量代表List實(shí)際存放元素的數(shù)量
使用transient修飾，使用writeObject 和 readObject 方法是為了序列化、反序列化時節(jié)省空間和時間（http://blog.csdn.net/zero__007/article/details/52166306）
（http://www.importnew.com/12611.html）
為了對應(yīng)不同的構(gòu)造函數(shù)，ArrayList使用了不同的數(shù)組
代碼中有個常量，表示數(shù)組的默認(rèn)容量，大小為10
構(gòu)造函數(shù)
/**
* 用指定的初始化容量構(gòu)造一個空的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)添加第一個元素時，創(chuàng)建一個初始容量為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的長度有可能不同。
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ù)制；同時，如果c中沒有元素，使用EMPTY_ELEMENTDATA初始化。
增刪改查操作
get和set方法，都是通過數(shù)組下標(biāo)，直接操作數(shù)據(jù)的，時間復(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ò)容檢測
elementData[size++] = e;//新增元素添加到末尾
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);//添加容量檢測
ensureCapacityInternal(size + 1); // 擴(kuò)容檢測
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 使用System.arraycopy的方法，將index后面元素往后移動1位
elementData[index] = element;// 存放元素到index位置
size++;
}
//添加一個集合的元素到末端，若要添加的集合為空返回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;
}
//從指定位置添加一個集合的元素，若要添加的集合為空返回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);//越界檢測
modCount++;
E oldValue = elementData(index);//舊值
int numMoved = size - index - 1; // 需要移動元素的數(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ù)組保留指定集合中元素的值，為false時從數(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即保留，則將相同元素移動到數(shù)組前端
//若complement為false即刪除，則將不同元素移動到數(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ò)容
在添加一個元素之前，先調(diào)用一下ensureCapacityInternal方法，這個方法如下
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ù)的最大值，這個判斷的目的是為了List中的addAll()方法，它會增加一個collection到這個數(shù)組里來，這個collection容量大于10，那么就要拓展這個數(shù)組的大小。就是通過ensureExplicitCapacity來實(shí)現(xiàn)。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount是父類AbstractList里的一個成員變量，用來記錄List的修改次數(shù)的，這里不再討論。 下面if判斷就是指如果添加完元素后的容量大于當(dāng)前數(shù)組長度，就要對數(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)到一個流（即它序列化）。寫入過程數(shù)組被更改（利用modCount的值）會拋出異常
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集合中的一種錯誤檢測機(jī)制。
在對集合進(jìn)行迭代過程中，除了迭代器可以對集合進(jìn)行數(shù)據(jù)結(jié)構(gòu)上進(jìn)行修改，其他的對集合的數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改，都會拋出ConcurrentModificationException錯誤。
這里，所謂的進(jìn)行數(shù)據(jù)結(jié)構(gòu)上進(jìn)行修改,是指對存儲的對象，進(jìn)行add,set,remove操作，進(jìn)而對數(shù)據(jù)發(fā)生改變。
ArrayList中，有個modCount的變量，每次進(jìn)行add，set，remove等操作，都會執(zhí)行modCount++。
在獲取ArrayList的迭代器時，會將ArrayList中的modCount保存在迭代中，
每次執(zhí)行add,set,remove等操作，都會執(zhí)行一次檢查，調(diào)用checkForComodification方法，對modCount進(jìn)行比較。
如果迭代器中的modCount和List中的modCount不同，則拋出ConcurrentModificationException
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
使用場景
ArrayList的使用場景主要從其優(yōu)缺點(diǎn)來考慮的：
優(yōu)點(diǎn)：
get，set，時間復(fù)雜度為O(1)
add（一般都是在末尾插入），時間復(fù)雜度為O(1)，最差情況下（往頭部插入數(shù)據(jù)），時間復(fù)雜度O(n)
數(shù)據(jù)存儲是順序的
缺點(diǎn)：
remove，時間復(fù)雜度為O(n)，最優(yōu)情況下（移除末尾元素），時間復(fù)雜度為O(1)
ArrayList底層使用數(shù)組存儲數(shù)據(jù)，數(shù)組是不能自動擴(kuò)容的，因此在發(fā)生擴(kuò)容的情況下，需要移動大量的元素。
ArrayList大小很大的時候，會存在空間浪費(fèi)（可以通過trimToSize方法，清除空閑空間）
數(shù)組大小是由限制的，受jvm和機(jī)器的影響，當(dāng)擴(kuò)容超出上限時，ArrayList會拋出異常
插入操作多，數(shù)據(jù)量不大，順序存儲時，可以考慮使用ArrayList
多線程情況下：
ArrayList所有的操作，都不是同步的，因此ArrayList不是線程安全的。
如果考慮到線程安全的話，可以使用CopyOnWriteArrayList或者外部同步ArrayList（List list = Collections.synchronizedList(new ArrayList(…));）
思考
1.remove方法中，為什么會將數(shù)組對應(yīng)的元素置為null？
ArrayList內(nèi)部使用數(shù)組實(shí)現(xiàn)一套管理對象的機(jī)制，remove操作中，已經(jīng)將元素的數(shù)量-1了，ArrayList認(rèn)為該對象已經(jīng)被移除了，應(yīng)該被jvm回收。
但是，對于jvm來說，該值仍然保存在數(shù)組中，ArrayList持有這個對象的引用，在jvm發(fā)生GC時，這個對象是不對被jvm回收，這樣就會造成內(nèi)存泄露了。
2.查找元素的方法中（比如indexOf），為什么需要對元素進(jìn)行null值判斷？
判斷對象是否相等，有兩個方面，1.對象存儲的地址；2.對象的內(nèi)容。
==，是用來比較兩個對象的地址是否相等，一般來說，兩個對象的地址相同，那么這兩個對象可以認(rèn)為是相同的對象
equals方法，是用來比較對象內(nèi)容的，當(dāng)然，也可以重載該方法，直接比較對象地址；Object對象的equals方法，是比較地址的。
一般來說，重載equals方法的同時，也要重載hashCode方法的，重載hashCode方法，必須得遵守6個原則：
自反性：對于任何非null的引用值x，x.equals(x),必須返回true
傳遞性：對于任何非null的引用值x,y,z，如果x.equals(y) 為true，且y.equals(z)為true，那么x.equals(z)必須為true
對稱性：對于任何非null的引用值x,y，如果x.equals(y)為true，那么y.equals(x)必須為true
非空性：對于任何非null的引用值x,x.equals(null)必須為false
一致性：對于任何非null的引用值x，y，如果多次調(diào)用equals方法，如果x和y比較的值沒有改變，那么x.equals(y)就會一致性返回true或者false
為什么重載equals方法，一般要重載hashCode方法？
重載equals方法，可以不重載hashCode方法，但是一般情況，不建議這么做。
hashCode方法，使用來求出對象的Hash值，
重載hashCode方法主要是為了提高一些容器（比如HashMap，Hashtable）進(jìn)行hash運(yùn)算的效率，而且也可以避免出現(xiàn)一些錯誤（比如HashSet容器的操作）
對于元素進(jìn)行null值判斷，我認(rèn)為主要是為了效率考慮，如果是null值的話，可以直接比較地址，而非空值，則需要通過equals方法來比較，由于ArrayList是泛型的，
所以其添加的元素，可能重載equals方法，自定義了判斷的原則。
3.grow方法中，對新容量大小進(jìn)行判斷，為什么會定義MAX_ARRAY_SIZE的？
ArrayList底層存儲是使用數(shù)組來實(shí)現(xiàn)的，所以ArrayList存儲文件的大小必定受數(shù)組大小的限制，所以在擴(kuò)容中，可以看到ArrayList對新容量大小進(jìn)行邏輯判斷。
影響數(shù)組最大值：
理論上最大值為Integer.MAX_VALUE(2^32 - 1)
對象頭限制，不同類型的元素，可創(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ī)器上需要存儲Headerwords
避免一些機(jī)器內(nèi)存溢出，減少出錯幾率，所以少分配
最大還是能支持到 Integer.MAX_VALUE
