整體介紹
ArrayList實(shí)現(xiàn)了List接口，是一個(gè)常見的集合類,它有一下特點(diǎn)：
- 是順序容器，即元素存放的數(shù)據(jù)與放進(jìn)去的順序相同，
- 允許放入null元素温数，
- 底層通過(guò)數(shù)組實(shí)現(xiàn)。
- 添加元素而容量不足時(shí)蜻势，可自動(dòng)擴(kuò)充底層數(shù)組的容量撑刺。
- 除該類未實(shí)現(xiàn)同步外，其余跟Vector大致相同握玛。
- 操作時(shí)間復(fù)雜度分別為：
- size,isEmpty,get,set,iterator,listIterator方法運(yùn)行時(shí)間為常量時(shí)間
- add方法運(yùn)行為攤還常量時(shí)間够傍，也即增加n個(gè)元素的時(shí)間為O(n)
- 其他的操作運(yùn)行時(shí)間大致為線性時(shí)間，常數(shù)因子相較于LinkedList更小挠铲。
攤還時(shí)間是一個(gè)操作的平均代價(jià)冕屯，可能某次操作代價(jià)很高，但總體的來(lái)看也并非那么糟糕拂苹；add方法是攤還常量時(shí)間與底層數(shù)組容量自動(dòng)擴(kuò)充有關(guān)
image.png
源碼分析
成員變量
/**
* 初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 當(dāng)ArrayList的空實(shí)例,用于無(wú)參數(shù)初始化
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* ArrayList的底層數(shù)組
* 泛型只是編譯器提供的語(yǔ)法糖所以這里的數(shù)組是一個(gè)Object數(shù)組
* ArrayList的容量就是elementData.length
* 當(dāng)ArrayList為空時(shí),elementData == EMPTY_ELEMENTDATA
* 當(dāng)?shù)谝粋€(gè)元素加入時(shí)elementData.length == DEFAULT_CAPACITY
* transient 說(shuō)明這個(gè)數(shù)組無(wú)法序列化安聘。
*/
private transient Object[] elementData;
/**
* ArrayList包含的元素?cái)?shù)量,與容量不同.
*/
private int size;
/**
* 數(shù)組最大容量
* 一些虛擬器需要在數(shù)組前加個(gè)頭標(biāo)簽，所以減去8 瓢棒。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 這個(gè)變量并不是ArrayList里面定義的,而是繼承自父類AbstractList
* ArrayList在使用Iterator時(shí)發(fā)生不同步會(huì)拋出錯(cuò)誤就是依靠了這個(gè)變量
(雖然不可靠,想要可靠的同步保證用
List list = Collections.synchronizedList(new ArrayList(...))
或
concurrent包下的CopyOnWriteArrayList
或
用synchronized進(jìn)行一層代理)
* add和remove方法都是有modCount++.
* 下面再具體說(shuō)說(shuō)modCount的作用
*/
protected transient int modCount = 0;
get()
get()方法本身很簡(jiǎn)單,不涉及數(shù)組的容量擴(kuò)充,除了檢查下標(biāo)范圍以及類型轉(zhuǎn)換,與一般的數(shù)組get()操作沒(méi)區(qū)別
public E get(int index) {
//檢查是否越界,
//由于java數(shù)組本身就會(huì)檢查是否越界,所以這里只是檢查是否超過(guò)了size,
//要知道數(shù)組的大小大于size,index大于size并不會(huì)觸發(fā)數(shù)組越界.
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
//對(duì)元素進(jìn)行類型轉(zhuǎn)換,底層儲(chǔ)存是Object,但返回是E.
return (E) elementData[index];
}
set()
set()方法也很簡(jiǎn)單,不涉及數(shù)組的容量擴(kuò)充,除了檢查下標(biāo)范圍,與一般的數(shù)組set()操作沒(méi)區(qū)別
public E set(int index, E element) {
//在get()中提到的,檢查越界問(wèn)題.
rangeCheck(index);
//直接用element替換elementData[index]
//賦值到指定位置浴韭，復(fù)制的僅僅是引用
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
add()
如果不算入容量擴(kuò)充的耗費(fèi),
add()方法運(yùn)行時(shí)間為常量時(shí)間.但是可能某次add()觸發(fā)了容量擴(kuò)充,那么那次操作的運(yùn)行時(shí)間為線性時(shí)間.所以add()的運(yùn)行時(shí)間為攤還常量時(shí)間,即n次操作的時(shí)間為O(n).add()會(huì)觸發(fā)modCount++
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
*從這個(gè)方法可知第一次add元素,初始容量為DEFAULT_CAPACITY,即10
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
*add()的modCount++來(lái)源于這里
*當(dāng)新容量大于當(dāng)前容量時(shí),觸發(fā)容量擴(kuò)充,即調(diào)用grow方法.
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
*ArrayList實(shí)現(xiàn)容量自動(dòng)擴(kuò)充是依靠了這個(gè)方法.
*新容量為原容量的1.5倍
*耗費(fèi)時(shí)間為O(n),因?yàn)樾枰獜?fù)制原來(lái)的元素到擴(kuò)充后的數(shù)組.
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//每次擴(kuò)充,新容量為原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// //擴(kuò)展空間并復(fù)制
elementData = Arrays.copyOf(elementData, newCapacity);
}
remove
-
remove運(yùn)行時(shí)間為O(n),因?yàn)锳rrayList底層實(shí)現(xiàn)為數(shù)組,所以刪除元素后,需要移動(dòng)之后的元素. - 除了越界檢查,與一般數(shù)組的
remove沒(méi)有區(qū)別 - 在
remove后并不會(huì)影響數(shù)組容量 -
remove會(huì)觸發(fā)modCount++
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//這里清除了elementData[size]的引用,
//因?yàn)榧偃绮磺宄?那么ArrayList就會(huì)一致保留那個(gè)對(duì)象
//GC不能清除仍被持有引用的對(duì)象
elementData[--size] = null;
return oldValue;
}
序列化
- 在上面成員變量那里提到了Object[] elementData用了transient關(guān)鍵字,無(wú)法序列化,這里ArrayList復(fù)寫了readObject和writeObject方法,實(shí)現(xiàn)底層數(shù)組的序列化.
- 復(fù)寫的writeObject用modCount保證了當(dāng)發(fā)生不同步問(wèn)題時(shí)拋出錯(cuò)誤(雖然不可靠)
- 關(guān)于序列化的知識(shí)可以看我轉(zhuǎn)載的<<深入理解Java對(duì)象序列化>>
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 記下方法開始時(shí)的modCount
int expectedModCount = modCount;
//將沒(méi)有transient關(guān)鍵字的成員變量寫入
s.defaultWriteObject();
//這里寫入數(shù)組的容量,但是把數(shù)組元素的數(shù)量size視為容量,
//而不用原來(lái)的容量elementData.length
s.writeInt(size);
// 將底層數(shù)組的元素依次寫入
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
//與之前記下的modCount對(duì)比,看是否有其他線程操作了ArrayList,有則拋出錯(cuò)誤.
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// 將沒(méi)有transient關(guān)鍵字的成員變量讀入
s.defaultReadObject();
// 將數(shù)組容量讀入,
//但是如上面writeObject所寫把size視為了數(shù)組容量,所以這里沒(méi)有實(shí)質(zhì)的作用
s.readInt(); // ignored
if (size > 0) {
// 擴(kuò)充數(shù)組大小
ensureCapacityInternal(size);
Object[] a = elementData;
// 把數(shù)組元素一次寫入
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
迭代器
ArrayList用iterator()可以返回迭代器.
- 實(shí)現(xiàn)了Iterator<E>接口;
private class Itr implements Iterator<E> - 當(dāng)有多個(gè)線程同時(shí)操作ArrayList,使用迭代器可以拋出錯(cuò)誤,避免發(fā)生不同步(這里就是用了
modCount,用法與writeObject()的差不多) - 迭代器使得對(duì)容器的遍歷操作完全與其底層相隔離，可以到達(dá)極好的解耦效果脯宿。
iterator()
public Iterator<E> iterator() {
//使用構(gòu)造函數(shù),返回一個(gè)新的迭代器
return new Itr();
}
迭代器成員變量
int cursor; // 下一個(gè)返回的元素的下標(biāo)
int lastRet = -1; // 上一次返回的元素的下標(biāo),初始為-1
//記下創(chuàng)建迭代器時(shí)的modCount,用于之后的同步檢查
int expectedModCount = modCount;
hasNext()
hasNext()用于檢測(cè)是否有下一個(gè)元素返回,實(shí)現(xiàn)很簡(jiǎn)單.
public boolean hasNext() {
return cursor != size;
}
checkForComodification()
- 這個(gè)方法是迭代器可以在多個(gè)線程操作時(shí)拋出錯(cuò)誤(fail-fast機(jī)制)的關(guān)鍵方法
- 下面的
remove和next都調(diào)用了這個(gè)方法 - 實(shí)現(xiàn)很簡(jiǎn)單,對(duì)比modCount,如果不一致,則說(shuō)明有其他線程也在用ArrayList,拋出錯(cuò)誤.
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
next()
-
next()方法的實(shí)現(xiàn)很簡(jiǎn)單,代碼寫的很清楚 -
next()在內(nèi)部做了很多安全檢查,保證了使用迭代器的安全性 -
next()調(diào)用了checkForComodification(),使用了fail-fast機(jī)制
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
remove()
- 迭代器的
remove()方法內(nèi)部是調(diào)用了ArrayList的remove()方法 -
remove()調(diào)用了checkForComodification(),使用了fail-fast機(jī)制
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
后記
- ArrayList的源代碼寫的很好,注釋也很清晰,我在這篇分析里面有很多內(nèi)容其實(shí)都是從注釋里翻譯,或者加了點(diǎn)自己的理解.
- 這里只是挑了幾個(gè)我覺(jué)得重要的地方做了分析,其余的推薦直接看源代碼
