此源碼分析JDK版本為1.7，只是簡單分析店雅，算是個(gè)人看源碼的一點(diǎn)小總結(jié)政基，隨意性比較強(qiáng)，專業(yè)的還需百度闹啦。
先簡單介紹一下ArrayList沮明，ArrayList為線性數(shù)據(jù)結(jié)構(gòu)，時(shí)間復(fù)雜度為O(1)窍奋，內(nèi)部存儲(chǔ)為數(shù)組荐健。以下所有表達(dá)ArrayList的內(nèi)容統(tǒng)稱為數(shù)組。
ps:ArrayList和Vector的區(qū)別就是ArrayList是線程不安全的琳袄，Vector是線程安全的江场。Vector底層核心方法都為synchronized。
簡介
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
屬性
//默認(rèn)數(shù)組大小
private static final int DEFAULT_CAPACITY = 10;
//默認(rèn)空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//數(shù)組(ArrayList中的數(shù)據(jù)就放在此數(shù)組中)
private transient Object[] elementData;
//數(shù)組真實(shí)數(shù)據(jù)的長度(與數(shù)組的長度不一樣)
private int size;
//數(shù)組最大大小常量(Integer.MAX_VALUE - 8原因是嘗試分配較大的數(shù)組可能會(huì)導(dǎo)致OutOfMemoryError)
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//修改次數(shù)(對(duì)于線程安全至關(guān)重要窖逗，在Iterator中會(huì)解釋)
protected transient int modCount = 0;
構(gòu)造方法
//無初始化長度的構(gòu)造方法
public ArrayList() {
super();
//將屬性中的空數(shù)組賦給elementData
this.elementData = EMPTY_ELEMENTDATA;
}
//初始化長度的構(gòu)造方法
public ArrayList(int initialCapacity) {
super();
//當(dāng)初始化長度小于0則拋出異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//new該長度的Object數(shù)組給與elementData
this.elementData = new Object[initialCapacity];
}
//根據(jù)父類Collection類型的對(duì)象進(jìn)行構(gòu)造的構(gòu)造方法
public ArrayList(Collection<? extends E> c) {
//不同的Collection的實(shí)現(xiàn)類會(huì)有不同的實(shí)現(xiàn)扛稽，但最終結(jié)果都是轉(zhuǎn)為Object數(shù)組
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
//目前未知(屬性定義為Object，判斷不等于因此覺得不太理解滑负，而且debug各種類型都是直接跳過此方法，暫時(shí)覺得此判斷不會(huì)進(jìn)入)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
方法
//返回?cái)?shù)組大小
public int size() {
return size;
}
//是否為空
public boolean isEmpty() {
return size == 0;
}
//獲取該值的下標(biāo)(無返回-1)
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
//可能會(huì)有人說Object默認(rèn)的equals()實(shí)現(xiàn)是==用含，覺得此方法塊沒意義矮慕，但實(shí)際調(diào)用的為真實(shí)類型的equals()方法
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//獲取最后該值的下標(biāo)(無返回-1)
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
//同上
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//是否包含
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//返回?cái)?shù)組(并不是返回Object數(shù)組，而是真實(shí)類型的數(shù)組)
public Object[] toArray() {
//查看copyOf源碼會(huì)發(fā)現(xiàn)返回的是真實(shí)類型數(shù)組
return Arrays.copyOf(elementData, size);
}
//當(dāng)調(diào)用get()時(shí)會(huì)通過此方法返回值 (default啄骇，外部無法調(diào)用)
E elementData(int index) {
return (E) elementData[index];
}
//檢查傳入的下標(biāo)參數(shù)是否越界
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//返回該下標(biāo)所對(duì)應(yīng)的值
public E get(int index) {
//檢查下標(biāo)參數(shù)是否越界
rangeCheck(index);
//根據(jù)下標(biāo)返回值
return elementData(index);
}
//設(shè)置下標(biāo)和值
public E set(int index, E element) {
//檢查下標(biāo)參數(shù)是否越界
rangeCheck(index);
//獲取該下標(biāo)的值
E oldValue = elementData(index);
//為該下標(biāo)賦新值
elementData[index] = element;
//返回舊值
return oldValue;
}
//擴(kuò)容：第一步將傳入的值與默認(rèn)最小值進(jìn)行對(duì)比
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
//最小為默認(rèn)最小值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//擴(kuò)容實(shí)現(xiàn)
ensureExplicitCapacity(minCapacity);
}
//擴(kuò)容：第二步將第一步的值與數(shù)組大小進(jìn)行對(duì)比判斷是否需要擴(kuò)容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//當(dāng)傳入的值大于數(shù)組長度時(shí)痴鳄，進(jìn)行擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴(kuò)容：擴(kuò)容真正實(shí)現(xiàn)(默認(rèn)情況下擴(kuò)容之后的大小為當(dāng)前數(shù)組長度+數(shù)組對(duì)2取余)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//定義變量為當(dāng)前大小加一半取余
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果變量小于傳的參數(shù)，則新的數(shù)組大小為傳入的參數(shù)
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果變量大于數(shù)組默認(rèn)最大值則調(diào)用hugeCapacity()方法返回值
if (newCapacity - MAX_ARRAY_SIZE > 0)
//將新的數(shù)組大小與默認(rèn)最大值進(jìn)行對(duì)比
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//調(diào)用Arrays.copyOf()擴(kuò)容
elementData = Arrays.copyOf(elementData, newCapacity);
}
tag:第一個(gè)判斷:如果傳入的值小于[數(shù)組大小加對(duì)二取余]則新的數(shù)組大小為傳入的值缸夹，定義的新值為傳入的值痪寻；如果不是則無操作。第二個(gè)判斷:第一步運(yùn)算厚的結(jié)果如果大于默認(rèn)數(shù)組最大長度虽惭，則返回hugeCapacity()計(jì)算后的值橡类；如果不是則無操作
//判斷傳的值是否大于默認(rèn)數(shù)組最大長度，如果是則為Integer最大值芽唇；如果不是則為默認(rèn)數(shù)組最大長度顾画，返回可用大小
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
//在數(shù)組中增加值
public boolean add(E e) {
//添加則會(huì)增加modCount
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//為某個(gè)下標(biāo)新增值
public void add(int index, E element) {
//判斷下標(biāo)是否越界
rangeCheckForAdd(index);
//先擴(kuò)容(防止index剛好為當(dāng)前數(shù)組長度)
ensureCapacityInternal(size + 1); // Increments modCount!!
//將源數(shù)組index位置開始的數(shù)組復(fù)制到目標(biāo)數(shù)組index+1后，復(fù)制的數(shù)量為size-index個(gè)
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//刪除某下標(biāo)對(duì)應(yīng)的值
public E remove(int index) {
//判斷下標(biāo)是否越界
rangeCheck(index);
//增加修改次數(shù)
modCount++;
//獲取舊值
E oldValue = elementData(index);
//判斷刪除該下標(biāo)元素需要向前移動(dòng)多少個(gè)位置
int numMoved = size - index - 1;
//如果當(dāng)前下標(biāo)不是最后一個(gè)元素匆笤，則將源數(shù)組index+1位置開始的數(shù)組復(fù)制到目標(biāo)數(shù)組index后研侣，復(fù)制的數(shù)量為numMoved個(gè)
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work //置空原尾部數(shù)據(jù) 不再強(qiáng)引用， 可以GC掉
return oldValue;
}
//根據(jù)下標(biāo)刪除值(不檢查下標(biāo)是否越界)
private void fastRemove(int index) {
//增加修改次數(shù)
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 //置空原尾部數(shù)據(jù) 不再強(qiáng)引用炮捧， 可以GC掉
}
//刪除值(只刪除第一個(gè))
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//調(diào)用不檢查下標(biāo)刪除值
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
//調(diào)用不檢查下標(biāo)刪除值
fastRemove(index);
return true;
}
}
return false;
}
//清空數(shù)組
public void clear() {
//增加修改次數(shù)
modCount++;
// clear to let GC do its work //置空原尾部數(shù)據(jù) 不再強(qiáng)引用庶诡， 可以GC掉
for (int i = 0; i < size; i++)
elementData[i] = null;
//數(shù)組真實(shí)長度歸零
size = 0;
}
//將Collection增加到當(dāng)前數(shù)組之后
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
//擴(kuò)容大小為當(dāng)前數(shù)組長度加參數(shù)數(shù)組長度
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
//設(shè)置真實(shí)數(shù)組大小長度
size += numNew;
return numNew != 0;
}
//判斷增加下標(biāo)是否越界(與判斷是否越界區(qū)別在于少了=size和增加了不小于0)
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//在下標(biāo)后增加Collection
public boolean addAll(int index, Collection<? extends E> c) {
//判斷增加下標(biāo)是否越界
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
//擴(kuò)容大小為當(dāng)前數(shù)組長度加參數(shù)數(shù)組長度
ensureCapacityInternal(size + numNew); // Increments modCount
//位移量
int numMoved = size - index;
if (numMoved > 0)
//將index之后的位移量numNoved空置出來
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//將Collection的數(shù)組放置index之后index + numNew之前
System.arraycopy(a, 0, elementData, index, numNew);
//設(shè)置真實(shí)數(shù)組大小長度
size += numNew;
return numNew != 0;
}
//刪除指定區(qū)間內(nèi)的數(shù)組內(nèi)容(protected修飾，subList方法會(huì)調(diào)用咆课，外部不可訪問)
protected void removeRange(int fromIndex, int toIndex) {
//增加修改次數(shù)
modCount++;
//計(jì)算位移量
int numMoved = size - toIndex;
//將toIndex后的數(shù)組放置fromIndex之后
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
//計(jì)算應(yīng)當(dāng)刪除的起始下標(biāo)
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
//設(shè)置真實(shí)數(shù)組大小長度
size = newSize;
}
//與Collection取交集
public boolean retainAll(Collection<?> c) {
//實(shí)際調(diào)用末誓，true表示取交集
return batchRemove(c, true);
}
//根據(jù)complement決定取交集還是取非交集(注意this.elementDat和elementData )
private boolean batchRemove(Collection<?> c, boolean complement) {
//定義變量
final Object[] elementData = this.elementData;
//為了方便理解可以理解為:r為this.elementData的下標(biāo)扯俱，w為elementData 下標(biāo)
int r = 0, w = 0;
//定義是否修改成功
boolean modified = false;
try {
for (; r < size; r++)
//根據(jù)complement決定是否將此值放入elementData中
if (c.contains(elementData[r]) == complement)
//w++是將值放入下標(biāo)為w之后w再+1
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//如果c.contains()拋出異常是則r一定不等于size，則執(zhí)行下方基显。將this.elementData下標(biāo)r之后的復(fù)制到elementData下標(biāo)w之后
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//如果w!=size則需要將w之后的數(shù)組清楚
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;
//只有進(jìn)入此代碼塊才表明修改成功
modified = true;
}
}
return modified;
}
//返回Itr迭代器
public Iterator<E> iterator() {
return new Itr();
}
//返回ListItr迭代器
public ListIterator<E> listIterator() {
return new ListItr(0);
}
//subList部分放置在ArrayList-SubList文章中
tag:在上段代碼中蘸吓，只有w!=size的情況下才會(huì)表明修改成功。我的理解：首先撩幽，contains()發(fā)生異常只會(huì)是空指針库继。如果相等則可能發(fā)生以下幾種情況1.求交集但兩個(gè)數(shù)組完全一樣2.求非交集兩個(gè)數(shù)組完全不一樣3.從開始就出現(xiàn)異常
總結(jié)
1.ArrayList增刪實(shí)現(xiàn)基本靠System.arraycopy()實(shí)現(xiàn)，修改是通過數(shù)組下標(biāo)(只能在下標(biāo)范圍內(nèi)修改)
2.通過modCount解決線程安全問題(iterator遍歷時(shí)如果修改則會(huì)直接拋出異常)
3.手動(dòng)置null去除強(qiáng)引用使gc下次工作是回收此對(duì)象
4.增窜醉、刪都會(huì)因?yàn)閿?shù)組擴(kuò)容二影響效率宪萄，修改和查詢不會(huì)影響效率
5.增、刪都會(huì)修改modCount榨惰，修改和查詢不會(huì)修改modCount
6.手動(dòng)置null只是將內(nèi)存地址取消引用拜英，因?yàn)間c是通過計(jì)數(shù)法來進(jìn)行回收，當(dāng)內(nèi)存地址沒有被引用就會(huì)被回收
