ArrayList是Java開發(fā)者使用最多的集合容器之一田晚。本片文章通過源碼的角度講解ArrayList的原理们陆。
ArrayList是List（有序集合）接口的一種 可調(diào)整大小的數(shù)組的 實現(xiàn)汉额，底層數(shù)據(jù)結構是數(shù)組蜡塌，存儲元素是有序的赦肃，且可重復丰榴，可存儲任何類型的元素货邓，包括null。該類的實現(xiàn)大致相當于Vector四濒，不過ArrayList是非線程安全的换况，如果多個線程并發(fā)訪問ArrayList，并且至少有一個線程修改了容器的結構盗蟆，那么必須要有額外的同步操作來保證ArrayList的線程安全問題戈二。雖然Vector是線程安全的，不過由于Vector是JDK的歷史遺留容器喳资，已不推薦使用觉吭，如果想使用線程安全的List，可通過 Collections.synchroizedList 方法對ArrayList進行包裝（該方式也適用于List接口的其他實現(xiàn)類）仆邓，或者使用JUC中的并發(fā)容器 CopyOnWriteArrayList 鲜滩。伴鳖。
基本屬性介紹
了解一個類，從屬性開始
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
默認的初始化容量徙硅，即初始的數(shù)組大小榜聂，當創(chuàng)建ArrayList對象時，沒有指定容量大小嗓蘑，即調(diào)用無參的構造方法峻汉，默認使用的就是這個容量大小。
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
這兩個空數(shù)組是為了區(qū)分該ArrayList對象是用無參構造創(chuàng)建的還是根據(jù)指定容量為0的構造方法創(chuàng)建的脐往。這樣才能知道第一次擴容的時候應該擴容多少。
/**
* The size of the ArrayList (the number of elements it contains).
*/
private int size;
表示ArrayList對象實際所存儲的元素個數(shù)
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
實際存儲數(shù)據(jù)的Object數(shù)組扳埂，該屬性用transient表示业簿，說明這個屬性在序列化與反序列化時，是會被忽略的阳懂，真的是這樣的嗎梅尤？（下面講）
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
可分配的數(shù)組的最大容量值，但實際上從擴容方法（下面講）中可以看出來岩调，ArrayList 的數(shù)組最大容量其實是 Integer.MAX_VALUE巷燥。那么為什么這里的最大值設計成Integer.MAX_VALUE - 8 ？首先号枕，我們先看下這段注釋：數(shù)組可分配的最大容量值缰揪，一些虛擬機在數(shù)組中保留一些head words，如果嘗試分配更大 的內(nèi)存葱淳，可能會造成OOM钝腺。從注釋我們可以知道，減去的這個8是為了保留一些內(nèi)存用來存放head words赞厕，那么為什么是8艳狐？而不是其他的數(shù)字呢？下面這段解釋屬片面看法皿桑，可做參考：
Java中的數(shù)組長度是只能用int來表示的毫目，也就是如果內(nèi)存允許，數(shù)組最大長度只能是Integer.MAX_VALUE诲侮。那么這里為什么要減8呢镀虐，這就要涉及到Java對象在內(nèi)存中的結構，數(shù)組對象和標準Java對象類似浆西，主要區(qū)別在于數(shù)組對象的對象頭中有一個額外的元數(shù)據(jù)粉私，用于表示數(shù)組的長度大小，即 array length 近零，減去的這個8就是為了保留一些內(nèi)存用來存儲數(shù)組長度這個值诺核，至于為什么是8 抄肖？array length 的數(shù)據(jù)長度會隨著JVM架構不同而不同，在32位的JVM下窖杀，array length 就是32位漓摩，64位的JVM下就是 64 位，也就是8個字節(jié)入客，由于目前市面上大部分都是64位的管毙，所以這里預留出了8個字節(jié)用來存儲 array length。
protected transient int modCount = 0;
這個字段是繼承自AbstractList類桌硫，表示的是該容器結構被修改的次數(shù)夭咬，如果該值被意外改變了，那么迭代器在執(zhí)行next铆隘、remove卓舵、previous、set膀钠、add等方法時會拋出異常掏湾，以實現(xiàn)快速失敗。
構造方法
ArrayList提供了三個構造方法
1. 無參構造
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
文檔注釋翻譯過來是肿嘲，構造一個容量為10的空集合融击。但其實這里容量為10沒有體現(xiàn)出來，這里只是構造了一個空的數(shù)組雳窟，這個時候數(shù)組的長度還是0尊浪，在第一次添加元素的時候會進行擴容，這時候才會構造一個容量為10的數(shù)組并添加元素封救。
大部分容器也有這種懶加載的設計思路际长，在構造方法里面不會初始化底層的數(shù)據(jù)結構，只有在第一次使用到的時候才會去初始化兴泥，防止資源浪費工育。
2. 指定容量的構造
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
構造一個指定容量的數(shù)組，如果指定容量是0搓彻，則跟上面的無參構造方法一樣初始化為一個空的數(shù)組如绸，EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 這兩個都是空數(shù)組，他們的區(qū)別就是區(qū)分該ArrayList對象是用無參構造創(chuàng)建的還是根據(jù)指定容量為0的構造方法創(chuàng)建的旭贬。
3. 參數(shù)為集合的構造
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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;
}
}
將傳入的集合copy到當前創(chuàng)建的新集合中怔接，如果傳入的集合的長度為0，則創(chuàng)建一個空集合
注意稀轨，該方法沒有做判空處理扼脐，所以如果傳入的集合是null，會拋出空指針異常 NullPointerException
代碼中有一行注釋 c.toArray might (incorrectly) not return Object[] (see 6260652) ，這是一個JDK的bug瓦侮，編號為 6260652 艰赞，在JDK9中已經(jīng)修復。意思就是 c.toArray 方法返回的不一定是 Object[]肚吏，例如用 Arrays.asList(strs) 方式創(chuàng)建的List方妖，在調(diào)用 toArray() 時返回的數(shù)組類型不一定是 Object[]，會保留原來的類型罚攀，有興趣可查看官方 JDK-6260652
增刪改查
增加一個元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
在ensureCapacityInternal方法中党觅，先判斷elementData是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果是則說明這是無參構造方法創(chuàng)建的容器斋泄，且是第一次添加元素杯瞻，則會將數(shù)組初始化成DEFAULT_CAPACITY大小的數(shù)組，然后增加modCount值炫掐，接下來就是判斷元素個數(shù)是否超過了數(shù)組大小又兵，如果是則擴容。然后在數(shù)組最后一位新增元素卒废，并且增加size。
public void add(int index, E element) {
rangeCheckForAdd(index); // 判斷index是否越界
ensureCapacityInternal(size + 1); // Increments modCount!!
// 將指定下標位置以及之后的元素往后移動一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
在指定位置上添加元素宙地，并將指定位置以及之后的元素往后移動一位
還有addAll方法摔认，原理類似。
修改一個元素
public E set(int index, E element) {
rangeCheck(index); // 判斷下標是否越界
E oldValue = elementData(index);
elementData[index] = element; // 然后修改數(shù)組指定位置的值
return oldValue; // 并返回舊的值
}
刪除一個元素
public E remove(int index) {
rangeCheck(index); // 判斷下標是否越界
modCount++; // 增加modCount值
E oldValue = elementData(index); // 獲取舊值
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
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
}
刪除指定元素宅粥，遍歷的方式参袱，fastRemove 和 remove 類似，只是沒有判斷下標秽梅，和沒有返回值抹蚀。
獲取一個元素
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
rangeCheck(index); // 判斷下標是否越界
return elementData(index);
}
總結：增刪改查這幾個方法源碼都比較簡單，做一些判斷及操作數(shù)組即可企垦。新增一個元素和刪除一個元素都會修改 modCount 值环壤，即表示修改了容器的結構，而set方法不會修改 modCount 值钞诡，也就是set不會修改容器的結構郑现，注意了！ set 方法雖然修改了容器中元素的值荧降，但是它不修改容器結構接箫。
ArrayList的擴容
擴容代碼如下
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
邏輯比較簡單，先是在原來容量的基礎上擴容50%朵诫，為了保證此次擴容一定能達到期望的容量值 minCapacity 辛友，所以當擴容50%之后如果還小于 minCapacity，就直接拿 minCapacity 的值當新的容量值剪返。
然后判斷新的容量是否超過了最大容量值废累，即 MAX_ARRAY_SIZE 邓梅，如果超過了，就使用 MAX_ARRAY_SIZE 的值作為新的容量值九默。
前面講到震放，ArrayList的最大容量值是 MAX_ARRAY_SIZE （Integer.MAX_VALUE - 8），即ArrayList的數(shù)組對象的最大容量值就是這個了驼修，但是依然能夠支持到 Integer.MAX_VALUE 大小的容量殿遂，什么時候支持呢？在期望的最小容量值乙各，也就是 minCapacity 值也超過 MAX_ARRAY_SIZE 的時候墨礁，就使用 Integer.MAX_VALUE 的值作為新的容量值。
注意耳峦！擴容是創(chuàng)建一個新的數(shù)組對象恩静，將舊數(shù)組的元素移動過去，然后再將elementData指向新的數(shù)組對象蹲坷。
ArrayList還提供了一個公開的擴容方法驶乾，用戶可以顯式地調(diào)用該方法來擴容。
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
}
ArrayList的序列化
ArrayList實現(xiàn)了Serializable接口循签，表示這個類的對象是可以被序列化的级乐，這個類的所有屬性和方法都會被序列化。
再看下elementData的定義：
transient Object[] elementData; // non-private to simplify nested class access
該屬性被 transient 修飾县匠，說明在序列化的時候风科，該字段會被忽略
而elementData是主要存儲數(shù)據(jù)的字段，為什么要忽略它呢乞旦？那序列化到文件或傳輸?shù)臅r候贼穆，ArrayList的元素不是都沒了嗎？
再看下ArrayList的這兩個方法：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
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();
}
}
}
當一個類實現(xiàn)了 Serializable接口兰粉，又定義了writeObject和readObject方法故痊，那么在序列化和反序列化對象的時候會調(diào)用該類自己定義的序列化和反序列化方式，關鍵源碼在 ObjectStreamClass 中
writeObjectMethod = getPrivateMethod(cl, "writeObject",
new Class<?>[] { ObjectOutputStream.class },
Void.TYPE);
readObjectMethod = getPrivateMethod(cl, "readObject",
new Class<?>[] { ObjectInputStream.class },
Void.TYPE);
通過反射去獲取對象類中方法名叫 writeObject 和 readObject 的方法玖姑，如果存在就調(diào)用對象類的方法
我們看到ArrayList也寫了這兩個方法崖蜜，那么在序列化和反序列化的時候就會調(diào)用自身的這兩個方法。在writeObject和readObject方法中客峭，去重新序列化和反序列化elementData這個屬性
所以不是忽略掉 elementData 這個屬性豫领，而是自己去自定義序列化規(guī)則了。為什么要這么做呢舔琅？
因為ArrayList中elementData等恐，是一個數(shù)組，擴容之后可能會存在沒有被使用的內(nèi)存，比如elementData目前擴容到數(shù)組長度為30了课蔬，可實際上存儲的數(shù)據(jù)可能只有10個囱稽，如果使用默認的序列化方式，就會將那20個值為null的元素也序列化進去了二跋，就造成了不必要的浪費战惊，所以在自定義的方法中，根據(jù)elementData的實際存儲的元素個數(shù)進行序列化扎即。
所以你測試一下會發(fā)現(xiàn)吞获，原本ArrayList的底層數(shù)組長度是10，然后存儲了3個元素谚鄙，"a","b","c"各拷，后面7個元素都是null，在進行序列化與反序列化之后得到的ArrayList對象的底層數(shù)組長度只有3了闷营。
ArrayList的快速失敗
/**
* The number of times this list has been <i>structurally modified</i>.
* Structural modifications are those that change the size of the
* list, or otherwise perturb it in such a fashion that iterations in
* progress may yield incorrect results.
*
* <p>This field is used by the iterator and list iterator implementation
* returned by the {@code iterator} and {@code listIterator} methods.
* If the value of this field changes unexpectedly, the iterator (or list
* iterator) will throw a {@code ConcurrentModificationException} in
* response to the {@code next}, {@code remove}, {@code previous},
* {@code set} or {@code add} operations. This provides
* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* <p><b>Use of this field by subclasses is optional.</b> If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its {@code add(int, E)} and
* {@code remove(int)} methods (and any other methods that it overrides
* that result in structural modifications to the list). A single call to
* {@code add(int, E)} or {@code remove(int)} must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus {@code ConcurrentModificationExceptions}. If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
*/
protected transient int modCount = 0;
這個字段是繼承至 AbstractList 類的烤黍，是實現(xiàn)快速失敗的關鍵。
快速失敗傻盟，即fail-fast速蕊，它是java集合的一種錯誤檢測機制。當多錢程對集合進行結構上的改變或者集合在迭代元素時直接調(diào)用自身方法改變集合結構而沒有通知迭代器時娘赴，有可能會觸發(fā)fast-fail機制并拋出異常
在ArrayList的所有涉及結構變化的方法中都增加modCount的值规哲，包括：add()、remove()筝闹、addAll()、removeRange()及clear()方法腥光。這些方法每調(diào)用一次关顷，modCount的值就加1。
在ArrayList創(chuàng)建迭代器的時候（iterator()方法或listIterator()方法）武福，會將當前的modCount值賦予迭代器中的 expectedModCount 字段议双。
然后在迭代器中的方法（如next(),remove()）都會去判斷 ArrayList 的 modCount 值和迭代器的 expectedModCount ，如果不相等就會拋出異常捉片。
所以如果修改了modCount值平痰，那么再操作迭代器，就會報錯了伍纫，即如果修改了ArrayList對象的結構宗雇，那么在這之前創(chuàng)建的迭代器都將失效。
SubList是ArrayList的一個內(nèi)部類莹规，它是截取ArrayList對象之后的返回值類赔蒲，也有快速失敗的機制。
RandomAccess接口
ArrayList 實現(xiàn)了RandomAccess接口，表示它是支持隨機訪問的舞虱。
RandomAccess接口是個空的接口欢际，只是一個標識，表示ArrayList擁有隨機訪問的能力矾兜，但是即使不實現(xiàn)這個接口损趋，ArrayList也是擁有隨機訪問能力的。ArrayList的隨機訪問能力源自于它存儲數(shù)據(jù)的底層結構是數(shù)組椅寺，可以通過下標精準訪問浑槽，且性能都是O(1)
通過RandomAccess接口的注釋文檔，可以知道用普通for循環(huán)遍歷的方式比用迭代器的方式循環(huán)要快：
/**
* ...
* ...
* for typical instances of the class, this loop:
* <pre>
* for (int i=0, n=list.size(); i < n; i++)
* list.get(i);
* </pre>
* runs faster than this loop:
* <pre>
* for (Iterator i=list.iterator(); i.hasNext(); )
* i.next();
* </pre>
* @since 1.4
* ...
* ...
*/
public interface RandomAccess {
}
所以如果是ArrayList容器配并，推薦使用 for 循環(huán)的方式遍歷（foreach方式不算括荡，foreach的底層也是使用迭代器遍歷的）
在Colletions工具類二分查找方法中：
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
可以看到如果是 list 是實現(xiàn)了 RandomAccess 接口，則一定使用的是數(shù)組下標的方式查找溉旋，因為實現(xiàn) RandomAccess 接口的 list 具有隨機訪問的能力畸冲，用數(shù)組下標的方式訪問速度更快。
ArrayList的迭代器
ArrayList實現(xiàn)了兩種迭代器观腊，一種是 iterator() 方法邑闲，返回的是 Itr 迭代器，Itr是ArrayList的一個內(nèi)部類：
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // 迭代器下一個要訪問的元素數(shù)組下標（稱為游標）
int lastRet = -1; // 迭代器前一個訪問的元素數(shù)組下標梧油，為-1表示迭代器沒有開始訪問元素或者迭代器前一次不是訪問元素（比如刪除元素）
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size; // 如果游標cursor不等于元素的個數(shù)size苫耸，表示游標還沒走完，即還有下一個元素
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); // 檢測快速失敗
int i = cursor;
if (i >= size) // 判斷游標是否走完
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData; // 拿到外部類的數(shù)組
if (i >= elementData.length) // 數(shù)組越界判斷
throw new ConcurrentModificationException();
cursor = i + 1; // 將游標往后移一位
return (E) elementData[lastRet = i]; // 將lastRet賦值為原來游標的值
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet); // 刪除數(shù)組下標為lastRet的元素儡陨，即迭代器前一個訪問的元素
cursor = lastRet; // 將游標重置為lastRet（即前一次訪問的元素下標）
lastRet = -1; // 將lastRet重置為-1
expectedModCount = modCount; // 調(diào)用外部ArrayList的刪除方法之后褪子，modCount會被修改，這里將 expectedModCount 值重置一下骗村，以免出現(xiàn)快速失敗嫌褪。所以調(diào)用Arraylist的刪除方法會出現(xiàn)快速失敗，而調(diào)用迭代器的刪除方法則是安全的胚股。
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 從游標位置開始往后訪問所有元素笼痛，并全部執(zhí)行指定方法，該方法結束之后琅拌，該迭代器也就結束了生命周期缨伊。
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
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();
}
// 快速失敗檢測，很簡單进宝，將外部類ArrayList的 modCount 和迭代器的 expectedModCount 比較刻坊，如果不相等，則表示外部類ArrayList已經(jīng)修改了容器結構党晋，即該迭代器已經(jīng)失效紧唱，拋出異常活尊。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
AbstractList也有一個內(nèi)部類叫Itr，是List的一個通用的迭代器實現(xiàn)漏益，而ArrayList重寫了Itr類蛹锰，是對 AbstractList.Itr 的一個優(yōu)化版本
另一個迭代器 ListItr 是 ArrayList.Itr 迭代器的一個擴展，功能更強大
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* An optimized version of AbstractList.ListItr
*/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
ArrayList.ListItr 迭代器繼承了 Arraylist.Itr 迭代器绰疤，做了一些擴展铜犬，比如可以往前遍歷，可以指定初始時的游標位置轻庆，也可以修改元素值和新增元素癣猾。
這種迭代器的設計方式，實際上是一種設計模式余爆，叫迭代器（Iterator）模式纷宇，又叫做游標模式，它的含義是蛾方，提供一種方法訪問一個容器對象中各個元素像捶，而又不需暴露該對象的內(nèi)部細節(jié)。從定義上看桩砰，迭代器是為容器而生拓春，它本質(zhì)上就是一種遍歷的算法。因為容器的實現(xiàn)千差萬別亚隅，很多時候會不知道如何去遍歷一個集合對象的元素硼莽，所以Java通過提供 Iterator 和 Iterable 倆個接口來實現(xiàn)容器的可迭代性及迭代器的統(tǒng)一訪問。
而Java中的 foreach 的這種寫法煮纵，底層也是基于迭代器的懂鸵，如果你的容器實現(xiàn)了 Iterable 接口，就能使用 foreach 的寫法了
遍歷刪除ArrayList
如何正確地遍歷刪除ArrayList中的元素行疏，主要有兩種
1匆光、普通for循環(huán)的方式遍歷刪除
List list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
list.add("f");
for (int i = 0; i < list.size(); i++) {
list.remove(i);
}
System.out.println(list);
打印出來的結果是 [b, d, f] ，原因是每次刪除元素隘擎，被刪除元素后面的元素都會往前移動一位殴穴，導致元素的位置發(fā)生了變化凉夯。
正確做法是反向遍歷刪除货葬，這樣就不會受到因為刪除而移動元素所帶來的影響。
2劲够、迭代器方式遍歷刪除
List list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
list.add("f");
Iterator iterator = list.iterator();
while(iterator.hasNext()){
Object obj = iterator.next();
list.remove(obj);
}
System.out.println(list);
這種方式遍歷刪除震桶，會拋出異常。原因是 調(diào)用 list.remove(obj) 的時候征绎，會修改容器的結構蹲姐，也就是修改了 modCount 值磨取，導致 list 的 modCount 值跟迭代器中的 expectedModCount 不一致，造成 fail-fast 柴墩。
正確做法就是刪除方法改成用迭代器提供的刪除方法來刪除 iterator.remove() 忙厌，迭代器的刪除方法實際上也是調(diào)用 ArrayList 的刪除方法，但是會重置 expectedModCount 為新的 modCount 值江咳，所以不會出現(xiàn) fail-fast 錯誤逢净，源碼如下：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount; // 重置 expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
參考：
ArrayList源碼分析超詳細
Java中ArrayList最大容量為什么是Integer.MAX_VALUE-8?
JDK9修復的bug(JDK-6260652)是怎么回事？
