*本篇文章已授權(quán)微信公眾號(hào) guolin_blog （郭霖）獨(dú)家發(fā)布
欣賞我們常用集合ArrayList的源碼,學(xué)習(xí)API背后的故事.
引言
學(xué)Java很久了,一直處于使用API+查API的狀態(tài),不了解原理,久而久之總是覺得很虛,作為一名合格的程序員這是不允許的,不能一直當(dāng)API Player,我們要去了解分析底層實(shí)現(xiàn),下次在使用時(shí)才能知己知彼.知道在什么時(shí)候該用什么方法和什么類比較合適.
之前寫的第一篇Java源碼閱讀文章從源碼角度徹底搞懂String宝恶、StringBuffer此叠、StringBuilder,感興趣的可以去看看.
一能岩、ArrayList的基本特點(diǎn)
- 快速隨機(jī)訪問
- 允許存放多個(gè)null元素
- 底層是Object數(shù)組
- 增加元素個(gè)數(shù)可能很慢(可能需要擴(kuò)容),刪除元素可能很慢(可能需要移動(dòng)很多元素),改對(duì)應(yīng)索引元素比較快
二、ArrayList的繼承關(guān)系
來看下源碼中的定義
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看到繼承了AbstractList,此類提供 List 接口的骨干實(shí)現(xiàn)，以最大限度地減少實(shí)現(xiàn)"隨機(jī)訪問"數(shù)據(jù)存儲(chǔ)（如數(shù)組）支持的該接口所需的工作.對(duì)于連續(xù)的訪問數(shù)據(jù)（如鏈表）偿乖，應(yīng)優(yōu)先使用 AbstractSequentialList冶伞，而不是此類.
實(shí)現(xiàn)了List接口,意味著ArrayList元素是有序的,可以重復(fù)的,可以有null元素的集合.
實(shí)現(xiàn)了RandomAccess接口標(biāo)識(shí)著其支持隨機(jī)快速訪問,實(shí)際上,我們查看RandomAccess源碼可以看到,其實(shí)里面什么都沒有定義.因?yàn)锳rrayList底層是數(shù)組,那么隨機(jī)快速訪問是理所當(dāng)然的,訪問速度O(1).
實(shí)現(xiàn)了Cloneable接口,標(biāo)識(shí)著可以它可以被復(fù)制.注意,ArrayList里面的clone()復(fù)制其實(shí)是淺復(fù)制(不知道此概念的趕快去查資料,這知識(shí)點(diǎn)非常重要).
實(shí)現(xiàn)了Serializable 標(biāo)識(shí)著集合可被序列化。
三筑凫、ArrayList 的構(gòu)造方法
在說構(gòu)造方法之前我們要先看下與構(gòu)造參數(shù)有關(guān)的幾個(gè)全局變量：
/**
* ArrayList 默認(rèn)的數(shù)組容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空實(shí)例的共享空數(shù)組實(shí)例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 另一個(gè)共享空數(shù)組實(shí)例，用的不多,用于區(qū)別上面的EMPTY_ELEMENTDATA
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList底層的容器
*/
transient Object[] elementData; // non-private to simplify nested class access
//當(dāng)前存放了多少個(gè)元素 并非數(shù)組大小
private int size;
注意到,底層容器數(shù)組的前面有一個(gè)transient關(guān)鍵字,啥意思??
查閱資料后,大概知道:transient標(biāo)識(shí)之后是不被序列化的
但是ArrayList實(shí)際容器就是這個(gè)數(shù)組為什么標(biāo)記為不序列化??那豈不是反序列化時(shí)會(huì)丟失原來的數(shù)據(jù)?
其實(shí)是ArrayList在序列化的時(shí)候會(huì)調(diào)用writeObject()并村，直接將size和element寫入ObjectOutputStream巍实；反序列化時(shí)調(diào)用readObject()，從ObjectInputStream獲取size和element哩牍，再恢復(fù)到elementData棚潦。
原因在于elementData是一個(gè)緩存數(shù)組，它通常會(huì)預(yù)留一些容量膝昆，等容量不足時(shí)再擴(kuò)充容量丸边，那么有些空間可能就沒有實(shí)際存儲(chǔ)元素叠必，采用上訴的方式來實(shí)現(xiàn)序列化時(shí)，就可以保證只序列化實(shí)際存儲(chǔ)的那些元素妹窖，而不是整個(gè)數(shù)組纬朝，從而節(jié)省空間和時(shí)間。
無參構(gòu)造方法
/**
* 構(gòu)造一個(gè)初始容量為10的空列表嘱吗。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
命名里面講elementData指向了一個(gè)空數(shù)組玄组，為什么注釋卻說初始容量為10。這里先賣個(gè)關(guān)子谒麦，稍后分析俄讹。
指定初始容量的構(gòu)造方法
public ArrayList(int initialCapacity) {
//容量>0 -> 構(gòu)建數(shù)組
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//容量==0 指向空數(shù)組
this.elementData = EMPTY_ELEMENTDATA;
} else {
//容量<0 報(bào)錯(cuò)唄
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
如果我們預(yù)先知道一個(gè)集合元素的容納的個(gè)數(shù)的時(shí)候推薦使用這個(gè)構(gòu)造方法，避免使用ArrayList默認(rèn)的擴(kuò)容機(jī)制而帶來額外的開銷.
使用另一個(gè)集合 Collection 的構(gòu)造方法
/**
* 構(gòu)造一個(gè)包含指定集合元素的列表绕德，元素的順序由集合的迭代器返回患膛。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray 可能(錯(cuò)誤地)不返回 Object[]類型的數(shù)組 參見 jdk 的 bug 列表(6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果集合大小為空將賦值為 EMPTY_ELEMENTDATA 空數(shù)組
this.elementData = EMPTY_ELEMENTDATA;
}
}
四、增加元素+擴(kuò)容機(jī)制
1. 添加單個(gè)元素
add(E e)方法作用: 添加指定元素到末尾
/**
* 添加指定元素到末尾
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果是以ArrayList()構(gòu)造方法初始化,那么數(shù)組指向的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA.第一次add()元素會(huì)進(jìn)入if內(nèi)部,
//且minCapacity為1,那么最后minCapacity肯定是10,所以ArrayList()構(gòu)造方法上面有那句很奇怪的注釋.
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//列表結(jié)構(gòu)被修改的次數(shù),用于保證線程安全,如果在迭代的時(shí)候該值意外被修改,那么會(huì)報(bào)ConcurrentModificationException錯(cuò)
modCount++;
// 溢出?
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴(kuò)容
private void grow(int minCapacity) {
// overflow-conscious code
//1. 記錄之前的數(shù)組長(zhǎng)度
int oldCapacity = elementData.length;
//2. 新數(shù)組的大小=老數(shù)組大小+老數(shù)組大小的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
//3. 判斷上面的擴(kuò)容之后的大小newCapacity是否夠裝minCapacity個(gè)元素
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//4.判斷新數(shù)組容量是否大于最大值
//如果新數(shù)組容量比最大值(Integer.MAX_VALUE - 8)還大,那么交給hugeCapacity()去處理,該拋異常則拋異常
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//5. 復(fù)制數(shù)組,注意,這里是淺復(fù)制
elementData = Arrays.copyOf(elementData, newCapacity);
}
//巨大容量,,,666,這個(gè)名字取得好
private static int hugeCapacity(int minCapacity) {
//溢出啦,扔出一個(gè)小錯(cuò)誤
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
大體思路:
-
首先判斷如果新添加一個(gè)元素是否會(huì)導(dǎo)致數(shù)組溢出
判斷是否溢出:如果原數(shù)組是空的,那么第一次添加元素時(shí)會(huì)給數(shù)組一個(gè)默認(rèn)大小10.接著是判斷是否溢出,如果溢出則去擴(kuò)容,擴(kuò)容規(guī)則: 新數(shù)組大小是原來數(shù)組大小的1.5倍,最后通過Arrays.copyOf()去淺復(fù)制.
添加元素到末尾
2. 添加元素到指定位置
add(int index, E element)方法作用:添加元素到指定位置
/**
* 添加元素在index處,對(duì)應(yīng)索引處元素(如果有)和后面的元素往后移一位,騰出坑
*/
public void add(int index, E element) {
//1. 入?yún)⒑戏ㄐ詸z查
rangeCheckForAdd(index);
//2. 是否需要擴(kuò)容
ensureCapacityInternal(size + 1); // Increments modCount!!
//3. 將elementData從index開始的size - index個(gè)元素復(fù)制到elementData的`index + 1`處
//相當(dāng)于index處以及后面的往后移動(dòng)了一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//4. 將元素放到index處 填坑
elementData[index] = element;
//5. 記錄當(dāng)前真實(shí)數(shù)據(jù)個(gè)數(shù)
size++;
}
//index不合法時(shí),拋IndexOutOfBoundsException
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
大體思路:這里理解了上面的擴(kuò)容之后,這里是比較簡(jiǎn)單的.其實(shí)就是在數(shù)組的某一個(gè)位置插入元素,那么我們將該索引處往后移動(dòng)一位,騰出一個(gè)坑,最后將該元素放到此索引處(填坑)就行啦.
3. 添加集合到末尾
addAll(Collection<? extends E> c)方法作用:添加集合到末尾,如果集合是null,那么會(huì)拋出NullPointerException.
public boolean addAll(Collection<? extends E> c) {
//1. 生成一個(gè)包含集合c所有元素的數(shù)組a
Object[] a = c.toArray();
//2. 記錄需要插入的數(shù)組長(zhǎng)度
int numNew = a.length;
//3. 判斷一下是否需要擴(kuò)容
ensureCapacityInternal(size + numNew); // Increments modCount
//4. 將a數(shù)組全部復(fù)制到elementData末尾處
System.arraycopy(a, 0, elementData, size, numNew);
//5. 標(biāo)記當(dāng)前elementData已有元素的個(gè)數(shù)
size += numNew;
//6. 是否插入成功:c集合不為空就行
return numNew != 0;
}
大體思路:代碼思路是非常清晰的,很簡(jiǎn)單,就是將需要插入的集合轉(zhuǎn)成數(shù)組a,再將a數(shù)組插入到當(dāng)前elementData的末尾(其中還判斷了一下是否需要擴(kuò)容).
4. 添加集合到指定位置
addAll(int index, Collection<? extends E> c)方法作用:添加集合到指定位置,可能會(huì)拋出IndexOutOfBoundsException(index不合法)或者NullPointerException(集合為null)
public boolean addAll(int index, Collection<? extends E> c) {
//1. 首先檢查一下下標(biāo)是否越界
rangeCheckForAdd(index);
//2. 生成一個(gè)包含集合c所有元素的數(shù)組a
Object[] a = c.toArray();
//3. 記錄需要插入的數(shù)組長(zhǎng)度
int numNew = a.length;
//4. 判斷是否需要擴(kuò)容
ensureCapacityInternal(size + numNew); // Increments modCount
//5. 需要往后移的元素個(gè)數(shù)
int numMoved = size - index;
if (numMoved > 0) //后面有元素才需要復(fù)制哈,否則相當(dāng)于插入到末尾
//6. 將elementData的從index開始的numMoved個(gè)元素復(fù)制到index + numNew處
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//7. 將a復(fù)制到elementData的index處
System.arraycopy(a, 0, elementData, index, numNew);
//8. 標(biāo)記當(dāng)前elementData已有元素的個(gè)數(shù)
size += numNew;
//9. 是否插入成功:c集合不為空就行
return numNew != 0;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
大體思路:其實(shí)就是一個(gè)先挖坑,再填坑的故事.首先判斷一下添加了集合之后是否需要擴(kuò)容,因?yàn)樾枰獙⒓喜迦氲絠ndex處,所以需要將index后面的元素往后挪動(dòng),需要挪動(dòng)的元素個(gè)數(shù)為:size - index,挪動(dòng)的間隔是index + numNew(因?yàn)樾枰舫鲆粋€(gè)坑,用來存放需要插入的集合).
有了上面的步驟后就可以安全的將集合復(fù)制到elementData的index,也就完成了集合的插入.
其實(shí)我們可以看到,源碼中對(duì)于細(xì)節(jié)的處理很細(xì)致,值得學(xué)習(xí).
五耻蛇、刪除元素
1. 移除指定位置元素
remove(int index)方法作用:移除指定位置元素,可能會(huì)拋出IndexOutOfBoundsException或ArrayIndexOutOfBoundsException
public E remove(int index) {
//1. 檢查參數(shù)是否合法
rangeCheck(index);
modCount++;
//2. 記錄下需要移除的元素
E oldValue = elementData(index);
//3. 需要往前面挪動(dòng)1個(gè)單位的元素個(gè)數(shù)
int numMoved = size - index - 1;
if (numMoved > 0) //后面有元素才挪動(dòng)
//4. 將index后面的元素(不包含index)往前"挪動(dòng)"(復(fù)制)一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//5. 這里處理得很巧妙,首先將size-1,然后將elementData原來的最后那個(gè)元素賦值為null(方便GC回收)
elementData[--size] = null; // clear to let GC do its work
//6. 將舊值返回
return oldValue;
}
//檢查參數(shù)是否合法 參數(shù)>size拋出IndexOutOfBoundsException 參數(shù)小于0則拋出ArrayIndexOutOfBoundsException
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
大體思路:
- 首先將舊值取出來,保存起來
- 然后將數(shù)組的index后面的元素往前挪動(dòng)一位
- 將數(shù)組的末尾元素賦值為null,方便GC回收.因?yàn)橐呀?jīng)將index后面的元素往前挪動(dòng)了一位,所以最后一位是多余的,及時(shí)清理掉.
2. 移除指定元素
remove(Object o)方法作用:移除指定元素,只移除第一個(gè)集合中與指定元素相同(通過equals()判斷)的元素.移除成功了則返回true,未移除任何元素則返回false
- 如果傳入的是null,則移除第一個(gè)null元素
- 如果傳入的是非null元素,則移除第一個(gè)相同的元素,通過equals()進(jìn)行比較.所以,如果是自己寫的類,則需要重寫equals()方法.一般需要用到元素比較的,都需要實(shí)現(xiàn)equals()方法,有時(shí)候還需要重寫hashCode()方法.
public boolean remove(Object o) {
//1. 是否為null
if (o == null) {
//2. 循環(huán)遍歷第一個(gè)為null的元素
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//3. 移除 移除之后就返回true
fastRemove(index);
return true;
}
} else {
//4. 循環(huán)遍歷第一個(gè)與o equals()的元素
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
//5. 移除指定位置元素
fastRemove(index);
return true;
}
}
return false;
}
/*
私有的方法,移除指定位置元素,其實(shí)和remove(int index)是一樣的.不同的是沒有返回值
*/
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
}
大體思路:
- 首先判斷需要移除的元素是否為null
- 如果為null,則循環(huán)遍歷數(shù)組,移除第一個(gè)為null的元素
- 如果非null,則循環(huán)遍歷數(shù)組,移除第一個(gè)與指定元素相同(equals() 返回true)的元素
可以看到最后都是移除指定位置的元素,源碼中為了追求最佳的性能,加了一個(gè)fastRemove(int index)方法,次方法的實(shí)現(xiàn)與remove(int index)是幾乎是一樣的,就是少了返回index索引處元素的值.
3. 從此列表中刪除所有包含在給定集合中的元素
removeAll(Collection<?> c)方法作用:從此列表中刪除所有包含在c中的元素.
public boolean removeAll(Collection<?> c) {
//判空
Objects.requireNonNull(c);
return batchRemove(c, false);
}
//complement是true 則移除elementData中除了c以外的其他元素
//complement是false 則移除c和elementData(當(dāng)前列表的數(shù)組)都含有的元素
private boolean batchRemove(Collection<?> c, boolean complement) {
//1. 引用不可變
final Object[] elementData = this.elementData;
//r 是記錄整個(gè)數(shù)組下標(biāo)的, w是記錄有效元素索引的
int r = 0, w = 0;
boolean modified = false;
try {
//2. 循環(huán)遍歷數(shù)組
for (; r < size; r++)
//3. 如果complement為false 相當(dāng)于是取c在elementData中的補(bǔ)集,c包含則不記錄,c不包含則記錄
//如果complement為true 相當(dāng)于是取c和elementData的交集,c包含則記錄,c不包含則不記錄
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r]; //r是正在遍歷的位置 w是用于記錄有效元素的 在w之前的全是有效元素,w之后的會(huì)被"刪除"
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//4. 如果上面在遍歷的過程中出錯(cuò)了,那么r肯定不等于size,于是源碼就將出錯(cuò)位置r后面的元素全部放到w后面
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//5. 如果w是不等于size,那么說明是需要?jiǎng)h除元素的 否則不需要?jiǎng)h除任何元素
if (w != size) {
// clear to let GC do its work
//6. 將w之后的元素全部置空 因?yàn)檫@些已經(jīng)沒用了,置空方便GC回收
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
//7. 記錄當(dāng)前有效元素
size = w;
//8. 標(biāo)記已修改
modified = true;
}
}
return modified;
}
大體思路:
- 首先我們進(jìn)行c集合檢查,判斷是否為null
- 然后我們調(diào)用batchRemove()方法去移除 c集合與當(dāng)前列表的交集
- 循環(huán)遍歷當(dāng)前數(shù)組,記錄c集合中沒有的元素,放在前面(記錄下標(biāo)為w),w前面的是留下來的元素,w后面的是需要?jiǎng)h除的數(shù)據(jù)
- 第3步可能會(huì)出錯(cuò),出錯(cuò)的情況下,則將出錯(cuò)位置的后面的全部保留下來,不刪除
- 然后就是將w之后的元素全部置空(方便GC回收),然后將size(標(biāo)記當(dāng)前數(shù)組有效元素)的值賦值為w,即完成了刪除工作
再籠統(tǒng)一點(diǎn)說吧,其實(shí)就是將當(dāng)前數(shù)組(elementData)中未包含在c中的元素,全部放在elementData數(shù)組的最前面,假設(shè)為w個(gè),最后再統(tǒng)一置空后面的元素,并且記錄當(dāng)前數(shù)組有效元素個(gè)數(shù)為w.即完成了刪除工作.
4. 清空列表
clear() 方法作用:清空當(dāng)前集合的所有元素
這個(gè)方法非常簡(jiǎn)單,就是將數(shù)組所有元素都置為null,然后GC就有機(jī)會(huì)去把它回收了
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
5. 移除相應(yīng)區(qū)間內(nèi)的所有元素(protected)
removeRange(int fromIndex, int toIndex)方法作用:移除指定區(qū)間內(nèi)的所有元素,注意這是protected方法,既然是移除元素,那么就拿出來欣賞欣賞.
//這是protected方法 移除相應(yīng)區(qū)間內(nèi)的所有元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
//1. toIndex后面的元素需要保留下來,記錄一下toIndex后面的元素個(gè)數(shù)
int numMoved = size - toIndex;
//2. 將toIndex后面的元素復(fù)制到fromIndex處
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
//3. 將有效元素后面的元素置空
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
//4. 記錄當(dāng)前有效元素個(gè)數(shù)為size - (toIndex-fromIndex) ,即減去那個(gè)區(qū)間內(nèi)的元素個(gè)數(shù)
size = newSize;
}
大體思路:
- 假設(shè)需要移除(fromIndex,toIndex)區(qū)間內(nèi)的元素,那么將toIndex后面的元素復(fù)制到fromIndex處
- 將有效元素后面的元素置空
六踪蹬、改動(dòng)元素
1. 替換指定下標(biāo)的元素內(nèi)容
set(int index, E element):替換index索引處的元素為element,可能會(huì)拋出IndexOutOfBoundsException
這里比較簡(jiǎn)單,就是將index處的元素替換成element
public E set(int index, E element) {
//1. 入?yún)z測(cè)
rangeCheck(index);
//2. 記錄原來該index處的值
E oldValue = elementData(index);
//3. 替換
elementData[index] = element;
return oldValue;
}
七、查詢?cè)?/h2>
1. 返回指定位置處元素
這個(gè)非常簡(jiǎn)單,就是將index索引處的數(shù)組的值返回
E elementData(int index) {
return (E) elementData[index];
}
/**
* 返回指定位置處元素
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
2.通過iterator()遍歷
這也是查詢的一種,哈哈
首先我們了解一下fail-fast,fail-fast 機(jī)制是java集合(Collection)中的一種錯(cuò)誤機(jī)制臣咖。
當(dāng)多個(gè)線程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)跃捣，就可能會(huì)產(chǎn)生fail-fast事件。例如：當(dāng)某一個(gè)線程A通過iterator去遍歷某集合的過程中夺蛇，
若該集合的內(nèi)容被其他線程所改變了疚漆；那么線程A訪問集合時(shí)，就會(huì)拋出ConcurrentModificationException異常刁赦，產(chǎn)生fail-fast事件娶聘。
要了解fail-fast機(jī)制，我們首先要對(duì)ConcurrentModificationException 異常有所了解甚脉。當(dāng)方法檢測(cè)到對(duì)象的并發(fā)修改丸升，但不允許這種修改時(shí)就拋出該異常。同時(shí)需要注意的是牺氨，該異常不會(huì)始終指出對(duì)象已經(jīng)由不同線程并發(fā)修改狡耻，如果單線程違反了規(guī)則，同樣也有可能會(huì)拋出該異常波闹。
我們先來看看iterator()方法,它new了一個(gè)Itr(ArrayList的內(nèi)部類)進(jìn)行返回.
/**
* Returns an iterator over the elements in this list in proper sequence.
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
* @return an iterator over the elements in this list in proper sequence
以適當(dāng)?shù)捻樞蚍祷卮肆斜碇性氐牡鳌? fail-fast:快速失敗?
*/
public Iterator<E> iterator() {
return new Itr();
}
接下來我們來看看這個(gè)內(nèi)部類
private class Itr implements Iterator<E> {
int cursor; // index of next element to return 下一個(gè)元素的索引
int lastRet = -1; // index of last element returned; -1 if no such 當(dāng)前訪問的最后一個(gè)元素的索引
int expectedModCount = modCount;
//是否有下一個(gè)元素
public boolean hasNext() {
//就是比一下cursor與size的大小 但是為什么是!=,而不是cursor<=size,這里有點(diǎn)蒙
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//判斷一下該列表是否被其他線程改過(在迭代過程中) 修改過則拋異常
checkForComodification();
//第一次的時(shí)候是等于0 從0開始往后取數(shù)據(jù)
int i = cursor;
//如果越界 則拋異常
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
//不能訪問超出elementData.length的索引 可能是被其他線程改動(dòng)了
if (i >= elementData.length)
throw new ConcurrentModificationException();
//往后挪一位 下一次就能訪問下一位元素
cursor = i + 1;
//將需要訪問的元素返回
return (E) elementData[lastRet = i];
}
//移除當(dāng)前訪問到的最后一位元素
public void remove() {
//入?yún)z測(cè)
if (lastRet < 0)
throw new IllegalStateException();
//判斷一下該列表是否被其他線程改過(在迭代過程中) 修改過則拋異常
checkForComodification();
try {
//移除當(dāng)前訪問到的最后一位元素
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//快速遍歷列表
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
//入?yún)z測(cè)
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
//遍歷完成 不用繼續(xù)了
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
//可能是被其他線程改動(dòng)了
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
//循環(huán)遍歷 不斷回調(diào)consumer.accept() 將elementData每個(gè)元素都回調(diào)一次
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
//判斷一下該列表是否被其他線程改過(在迭代過程中) 修改過則拋異常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
八酝豪、總結(jié)
這是我第二次看源碼,分析,鑒賞,學(xué)到了不少東西,相信各位認(rèn)真看完的同學(xué)也多多少少有些感觸.源碼對(duì)于細(xì)節(jié)方面想的很周到,很謹(jǐn)慎.
下面我們來總結(jié)一下ArrayList的關(guān)鍵點(diǎn)
ArrayList關(guān)鍵點(diǎn)
- 底層是Object數(shù)組存儲(chǔ)數(shù)據(jù)
- 擴(kuò)容機(jī)制:默認(rèn)大小是10,擴(kuò)容是擴(kuò)容到之前的1.5倍的大小,每次擴(kuò)容都是將原數(shù)組的數(shù)據(jù)復(fù)制進(jìn)新數(shù)組中. 我的領(lǐng)悟:如果是已經(jīng)知道了需要?jiǎng)?chuàng)建多少個(gè)元素,那么盡量用
new ArrayList<>(13)這種明確容量的方式創(chuàng)建ArrayList.避免不必要的浪費(fèi). - 添加:如果是添加到數(shù)組的指定位置,那么可能會(huì)挪動(dòng)大量的數(shù)組元素,并且可能會(huì)觸發(fā)擴(kuò)容機(jī)制;如果是添加到末尾的話,那么只可能觸發(fā)擴(kuò)容機(jī)制.
- 刪除:如果是刪除數(shù)組指定位置的元素,那么可能會(huì)挪動(dòng)大量的數(shù)組元素;如果是刪除末尾元素的話,那么代價(jià)是最小的. ArrayList里面的刪除元素,其實(shí)是將該元素置為null.
- 查詢和改某個(gè)位置的元素是非常快的( O(1) ).
