原文地址：https://xeblog.cn/articles/19
本文主要介紹的是ArrayList在JDK8中的實(shí)現(xiàn)。
ArrayList簡(jiǎn)介
ArrayList 是一個(gè)數(shù)組隊(duì)列蜘拉，內(nèi)部維護(hù)一個(gè)Java數(shù)組泊交，并且它是動(dòng)態(tài)的祈噪，數(shù)組的容量可以自動(dòng)增長(zhǎng)坟募。它繼承了AbstractList，且實(shí)現(xiàn)了List嗓节、RandomAccess勿锅、Cloneable帕膜、Serializable等接口。
ArrayList的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
- 支持隨機(jī)存取溢十，由于其內(nèi)部是一個(gè)數(shù)組垮刹，隨機(jī)訪問(wèn)元素等于通過(guò)數(shù)組下標(biāo)訪問(wèn)，隨機(jī)獲取元素效率高张弛。
- 元素是有序的（按照添加順序）荒典。
- 支持自動(dòng)擴(kuò)容（既是優(yōu)點(diǎn)也是缺點(diǎn)）酪劫。
缺點(diǎn)
- 線程不安全。
- 自動(dòng)擴(kuò)容效率低寺董，每次擴(kuò)容都需要將所有元素添加到新增數(shù)組中覆糟。
- 添加和刪除操作需要移動(dòng)數(shù)組中的元素。
疑問(wèn)：為何ArrayList繼承AbstractList后又實(shí)現(xiàn)了List接口遮咖？
- 這個(gè)回答本人無(wú)法辨別內(nèi)容真實(shí)性滩字，不過(guò)可以晾出來(lái)曬曬。
stackoverflow上有人回答說(shuō)是Josh Bloch（Java集合框架作者）設(shè)計(jì)失誤御吞，作者原本以為這樣的設(shè)計(jì)是有價(jià)值的麦箍，后來(lái)發(fā)現(xiàn)并不是。
- 方便使用Java反射機(jī)制獲取方法實(shí)現(xiàn)的所有接口陶珠，因?yàn)槿绻伙@式的實(shí)現(xiàn)
List接口挟裂，反射獲取接口的時(shí)候還需要先獲取父類，然后再通過(guò)父類獲取接口揍诽。 - 方便一眼就能看出
ArrayList實(shí)現(xiàn)了List接口（敷衍.gif）诀蓉。 - 其它...
ArrayList的部分字段
/**
* 默認(rèn)容量為10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空數(shù)組
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默認(rèn)大小的空數(shù)組。將此與EMPTY_ELEMENTDATA區(qū)分開(kāi)來(lái)暑脆，以便在添加第一個(gè)元素時(shí)知道要膨脹多少渠啤。
* 使用無(wú)參構(gòu)造初始化ArrayList時(shí)默認(rèn)的數(shù)組
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存儲(chǔ)ArrayList元素的數(shù)組。添加第一個(gè)元素時(shí)饵筑，如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* 則此數(shù)組的長(zhǎng)度是默認(rèn)的10
*/
transient Object[] elementData;
/**
* ArrayList的元素個(gè)數(shù)
*/
private int size;
ArrayList的構(gòu)造方法
帶一個(gè)int類型參數(shù)的構(gòu)造方法埃篓，傳入的是ArrayList的初始長(zhǎng)度
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 默認(rèn)的空數(shù)組 Object[] EMPTY_ELEMENTDATA = {}
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
JDK8的無(wú)參構(gòu)造
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
JDK7的無(wú)參構(gòu)造
public ArrayList() {
this(10);
}
JDK8中使用默認(rèn)的無(wú)參構(gòu)造方法初始化ArrayList時(shí)，做了延遲優(yōu)化根资，在未執(zhí)行add() 方法前ArrayList 數(shù)組中的實(shí)際大小還是0，等到第一次添加元素的時(shí)候才進(jìn)行默認(rèn)長(zhǎng)度為10的數(shù)組初始化同窘。
傳入一個(gè)集合對(duì)象的構(gòu)造方法玄帕，構(gòu)造一個(gè)包含此集合元素的ArrayList
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;
}
}
ArrayList是如何實(shí)現(xiàn)動(dòng)態(tài)增長(zhǎng)的？
首先看add(E e)方法
public boolean add(E e) {
// 判斷添加此元素時(shí)數(shù)組是否會(huì)超出想邦，超出則增長(zhǎng)數(shù)組
ensureCapacityInternal(size + 1);
// 添加元素
elementData[size++] = e;
return true;
}
/**
* 此方法用于判斷當(dāng)添加這個(gè)元素時(shí)數(shù)組容量是否超出裤纹，超出則自動(dòng)增長(zhǎng)
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果數(shù)組是通過(guò)默認(rèn)構(gòu)造方法實(shí)例化的，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 將返回true
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 返回最大的值 丧没，如果minCapacity大于10則返回minCapacity的值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// fail-fast機(jī)制鹰椒，并發(fā)修改會(huì)拋出異常 throw new ConcurrentModificationException()
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// 新增元素后的數(shù)組長(zhǎng)度超過(guò)了當(dāng)前數(shù)組長(zhǎng)度，所以調(diào)用增加數(shù)組長(zhǎng)度的方法
grow(minCapacity);
}
看一看grow(int minCapacity)方法就能知道ArrayList是如何自動(dòng)增長(zhǎng)容量的了
// 分配的最大數(shù)組大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 增長(zhǎng)后的容量等于舊容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// MAX_ARRAY_SIZE為int的最大值減8呕童，如果增長(zhǎng)后的容量超過(guò)該值漆际，則直接返回int的最大值，否則返回該值
if (newCapacity - MAX_ARRAY_SIZE > 0);
newCapacity = hugeCapacity(minCapacity);
// 使用的是Arrays.copyOf()方法將原數(shù)組中的元素拷貝到新增數(shù)組中夺饲，新增數(shù)組的長(zhǎng)度即是newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
這里列出hugeCapacity(int minCapacity)方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
JDK6中 int newCapacity = (oldCapacity * 3)/2 + 1; 增長(zhǎng)容量等于舊容量的1.5倍加1奸汇，JDK8中使用了位運(yùn)算施符，直接增長(zhǎng)為舊容量的1.5倍。
手動(dòng)調(diào)整ArrayList的容量
在添加大量元素前擂找，可以通過(guò)調(diào)用ensureCapacity(int minCapacity)方法來(lái)手動(dòng)增加ArrayList的容量戳吝，以減少遞增式再分配的數(shù)量
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
trimToSize()方法可以將ArrayList的容量調(diào)整為實(shí)際元素的大小
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
fail-fast機(jī)制
由于ArrayList不是線程安全的，所以如果在使用迭代器的過(guò)程中有其它線程修改了ArrayList贯涎，那么將會(huì)拋出 throw new ConcurrentModificationException()的異常听哭，這就是fail-fast機(jī)制（快速失敗）塘雳。
fail-fast機(jī)制是通過(guò)modCount字段來(lái)判斷的欢唾，modCount字段是父類AbstractList的字段，在每次修改ArrayList時(shí)粉捻，modCount字段都會(huì)自動(dòng)加1礁遣，迭代器初始化時(shí)會(huì)將modCount的值賦給迭代器的expectedModCount字段。
ArrayList的迭代器內(nèi)部實(shí)現(xiàn)（部分）
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@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];
}
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();
}
}
}
在執(zhí)行next()肩刃、remove()方法時(shí)都會(huì)調(diào)用checkForComodification()方法祟霍，判斷expectedModCount是否還等于modCount，如果不相等則說(shuō)明已經(jīng)有其它線程修改了ArrayList盈包，這時(shí)就將拋出異常throw new ConcurrentModificationException()沸呐。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
