騰訊一面！說說ArrayList的遍歷foreach與iterator時remove的區別，我一臉懵逼
本文基於JDK-8u261源碼分析
1 簡介
ArrayList作為最基礎的集合類，其底層是使用一個動態數組來實現的，這裡「動態」的意思是可以動態擴容（雖然ArrayList可以動態擴容，但卻不會動態縮容）。但是與HashMap不同的是，ArrayList使用的是1.5的擴容策略，而HashMap使用的是2的方式。還有一點與HashMap不同：ArrayList的默認初始容量為10，而HashMap為16。
有意思的一點是：在Java 7之前的版本中，ArrayList的無參構造器是在構造器階段完成的初始化；而從Java 7開始，改為了在add方法中完成初始化，也就是所謂的延遲初始化。在HashMap中也有同樣的設計思路。
另外，同HashMap一樣，如果要存入一個很大的數據量並且事先知道要存入的這個數據量的固定值時，就可以往構造器里傳入這個初始容量，以此來避免以後的頻繁擴容。
2 構造器
/**
* ArrayList:
* 無參構造器
*/
public ArrayList() {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一個空實現「{}」，這裡也就是在做初始化
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 有參構造器
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//initialCapacity>0就按照這個容量來初始化數組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//EMPTY_ELEMENTDATA也是一個空實現「{}」，這裡也是在做初始化
this.elementData = EMPTY_ELEMENTDATA;
} else {
//如果initialCapacity為負數，則拋出異常
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
3 add方法
3.1 add(E e)
添加指定的元素：
/**
* ArrayList:
*/
public boolean add(E e) {
//查看是否需要擴容
ensureCapacityInternal(size + 1);
//size記錄的是當前元素的個數，這裡就直接往數組最後添加新的元素就行了，之後size再+1
elementData[size++] = e;
return true;
}
/**
* 第6行程式碼處：
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
/*
minCapacity = size + 1
之前說過，DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一個空實現「{}」，這裡也就是在判斷是不是調用的無參構造器
並第一次調用到此處
*/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
/*
如果是的話就返回DEFAULT_CAPACITY（10）和size+1之間的較大者。也就是說，數組的最小容量是10
這裡有意思的一點是：調用new ArrayList<>()和new ArrayList<>(0)兩個構造器會有不同的默認容量（在HashMap中
也是如此）。也就是說無參構造器的初始容量為10，而傳進容量為0的初始容量為1。同時這也就是為什麼會有
EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA這兩個常量的存在，雖然它們的值都是「{}」
原因就在於無參構造器和有參構造器完全就是兩種不同的實現策略：如果你想要具體的初始容量，那麼就調用有參構造器吧，
即使傳入的是0也是符合這種情況的；而如果你不在乎初始的容量是多少，那麼就調用無參構造器就行了，這會給你默
認為10的初始容量
*/
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//如果調用的是有參構造器，或者調用無參構造器但不是第一次進來，就直接返回size+1
return minCapacity;
}
/**
* 第16行程式碼處：
*/
private void ensureExplicitCapacity(int minCapacity) {
//修改次數+1（快速失敗機制）
modCount++;
/*
如果+1後期望的容量比實際數組的容量還大，就需要擴容了（如果minCapacity也就是size+1後發生了數據溢出，
那麼minCapacity就變為了一個負數，並且是一個接近int最小值的數。而此時的elementData.length也會是一個接近
int最大值的數，那麼該if條件也有可能滿足，此時會進入到grow方法中的hugeCapacity方法中拋出溢出錯誤）
*/
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
//獲取擴容前的舊數組容量
int oldCapacity = elementData.length;
//這裡擴容後新數組的容量是採用舊數組容量*1.5的方式來實現的
int newCapacity = oldCapacity + (oldCapacity >> 1);
/*
如果新數組容量比+1後期望的容量還要小，此時把新數組容量修正為+1後期望的容量（對應於newCapacity為0或1的情況）
這裡以及後面的判斷使用的都是「if (a - b < 0)」形式，而不是常規的「if (a < b)」形式是有原因的，
原因就在於需要考慮數據溢出的情況：如果執行了*1.5的擴容策略後newCapacity發生了數據溢出，那麼它就一樣
變為了一個負數，並且是一個接近int最小值的數。而minCapacity此時也必定會是一個接近int最大值的數，
那麼此時的「newCapacity - minCapacity」計算出來的結果就可能會是一個大於0的數。於是這個if條件
就不會執行，而是會在下個條件中的hugeCapacity方法中處理這種溢出的問題。這同上面的分析是類似的
而如果這裡用的是「if (newCapacity < minCapacity)」，數據溢出的時候該if條件會返回true，於是
newCapacity會錯誤地賦值為minCapacity，而沒有使用*1.5的擴容策略
*/
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
/*
如果擴容後的新數組容量比設定好的容量最大值（Integer.MAX_VALUE - 8）還要大，就重新設置一下新數組容量的上限
同上面的分析，如果發生數據溢出的話，這裡的if條件也可能是滿足的，那麼也會走進hugeCapacity方法中去處理
*/
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
/*
可以看到這裡是通過Arrays.copyOf（System.arraycopy）的方式來進行數組的拷貝，
容量是擴容後的新容量newCapacity，將拷貝後的新數組賦值給elementData即可
*/
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 第83行程式碼處：
*/
private static int hugeCapacity(int minCapacity) {
//minCapacity對應於size+1，所以如果minCapacity<0就說明發生了數據溢出，就拋出錯誤
if (minCapacity < 0)
throw new OutOfMemoryError();
/*
如果minCapacity大於MAX_ARRAY_SIZE，就返回int的最大值，否則返回MAX_ARRAY_SIZE
不管返回哪個，這都會將newCapacity重新修正為一個大於0的數，也就是處理了數據溢出的情況
其實從這裡可以看出：本方法中並沒有使用*1.5的擴容策略，而只是設置了一個上限而已。但是在Java中
真能申請得到Integer.MAX_VALUE這麼大的數組空間嗎？其實不見得，這只是一個理論值。實際上需要考慮
-Xms和-Xmx等一系列JVM參數所設置的值。所以這也可能就是MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）
其中-8的含義吧。但不管如何，當數組容量達到這麼大的量級時，乘不乘1.5其實已經不太重要了）
*/
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
3.2 add(int index, E element)
在指定的位置處添加指定的元素：
/**
* ArrayList:
*/
public void add(int index, E element) {
//index參數校驗
rangeCheckForAdd(index);
//查看是否需要擴容
ensureCapacityInternal(size + 1);
/*
這裡數組拷貝的意義，就是將index位置處以及後面的數組元素往後移動一位，以此來挪出一個位置
System.arraycopy是直接對記憶體進行複製，在大數據量下，比for循環更快
*/
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//然後將需要插入的元素插入到上面挪出的index位置處就可以了
elementData[index] = element;
//最後size+1，代表添加了一個元素
size++;
}
/**
* 第6行程式碼處：
* 檢查傳入的index索引位是否越界，如果越界就拋異常
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
4 get方法
/**
* ArrayList:
*/
public E get(int index) {
//index參數校驗
rangeCheck(index);
//獲取數據
return elementData(index);
}
/**
* 第6行程式碼處：
* 這裡只檢查了index大於等於size的情況，而index為負數的情況
* 在elementData方法中會直接拋出ArrayIndexOutOfBoundsException
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 第8行程式碼處：
* 可以看到，這裡是直接從elementData數組中獲取指定index位置的數據
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
5 remove方法
5.1 remove(Object o)
刪除指定的元素：
/**
* ArrayList:
*/
public boolean remove(Object o) {
if (o == null) {
//如果要刪除的元素為null
for (int index = 0; index < size; index++)
//遍曆數組中的每一個元素，找到第一個為null的元素
if (elementData[index] == null) {
/*
刪除這個元素，並返回true。這裡也就是在做清理的工作：遇到一個為null的元素就清除掉
注意這裡只會清除一次，並不會全部清除
*/
fastRemove(index);
return true;
}
} else {
//如果要刪除的元素不為null
for (int index = 0; index < size; index++)
//找到和要刪除的元素是一致的數組元素
if (o.equals(elementData[index])) {
/*
找到了一個就進行刪除，並返回true。注意這裡只會找到並刪除一個元素，
如果要刪除所有的元素就調用removeAll方法即可
*/
fastRemove(index);
return true;
}
}
/*
如果要刪除的元素為null並且找不到為null的元素，或者要刪除的元素不為null並且找不到和要刪除元素相等的數組元素，
就說明此時不需要刪除元素，直接返回false就行了
*/
return false;
}
/**
* 第14行和第26行程式碼處：
*/
private void fastRemove(int index) {
//修改次數+1
modCount++;
//numMoved記錄的是移動元素的個數
int numMoved = size - index - 1;
if (numMoved > 0)
/*
這裡數組拷貝的意義，就是將index+1位置處以及後面的數組元素往前移動一位，
這會將index位置處的元素被覆蓋，也就是做了刪除
*/
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
/*
因為上面是左移了一位，所以最後一個位置相當於騰空了，這裡也就是將最後一個位置（--size）置為null
當然如果上面計算出來的numMoved本身就小於等於0，也就是index大於等於size-1的時候（大於不太可能，
是屬於異常的情況），意味著不需要進行左移。此時也將最後一個位置置為null就行了。置為null之後，
原有數據的引用就會被斷開，GC就可以工作了
*/
elementData[--size] = null;
}
5.2 remove(int index)
刪除指定位置處的元素：
/**
* ArrayList:
*/
public E remove(int index) {
//index參數校驗
rangeCheck(index);
//修改次數+1
modCount++;
//獲取指定index位置處的元素
E oldValue = elementData(index);
//numMoved記錄的是移動元素的個數
int numMoved = size - index - 1;
if (numMoved > 0)
/*
同上面fastRemove方法中的解釋，這裡同樣是將index+1位置處以及後面的數組元素往前移動一位，
這會將index位置處的元素被覆蓋，也就是做了刪除（這裡是否可以考慮封裝？）
*/
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
//同上，將最後一個位置（--size）置為null
elementData[--size] = null;
//刪除之後，將舊值返回就行了
return oldValue;
}
6 不要在foreach循環里進行元素的remove/add操作
這是《阿里巴巴編碼規範》中的一條。正例：
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String item = iterator.next();
if ("2".equals(item)) {
iterator.remove();
}
}
反例：
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
for (String item : list) {
if ("2".equals(item)) {
list.remove(item);
}
}
運行上面的程式碼可以看到，使用迭代器的刪除操作是不會有問題、能成功刪除的；而使用foreach循環進行刪除則會拋出ConcurrentModificationException異常，但如果使用foreach循環刪除第一個元素「1」的時候又會發現不會拋出異常。那麼這到底是為什麼呢？
眾所周知，foreach循環是一種語法糖，那麼其背後到底是如何來實現的呢？將上面反例的程式碼反編譯後的結果如下：
public class com.hys.util.Test {
public com.hys.util.Test();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: new #2 // class java/util/ArrayList
3: dup
4: invokespecial #3 // Method java/util/ArrayList."<init>":()V
7: astore_1
8: aload_1
9: ldc #4 // String 1
11: invokeinterface #5, 2 // InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
16: pop
17: aload_1
18: ldc #6 // String 2
20: invokeinterface #5, 2 // InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
25: pop
26: aload_1
27: invokeinterface #7, 1 // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
32: astore_2
33: aload_2
34: invokeinterface #8, 1 // InterfaceMethod java/util/Iterator.hasNext:()Z
39: ifeq 72
42: aload_2
43: invokeinterface #9, 1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
48: checkcast #10 // class java/lang/String
51: astore_3
52: ldc #6 // String 2
54: aload_3
55: invokevirtual #11 // Method java/lang/String.equals:(Ljava/lang/Object;)Z
58: ifeq 69
61: aload_1
62: aload_3
63: invokeinterface #12, 2 // InterfaceMethod java/util/List.remove:(Ljava/lang/Object;)Z
68: pop
69: goto 33
72: return
}
上面的內容不需要完全看懂，只需要看到第23行程式碼處、第26行程式碼處和第29行程式碼處後面的解釋，也就是foreach循環是通過調用List.iterator方法來生成一個迭代器，通過Iterator.hasNext方法和Iterator.next方法來實現的遍歷操作（普通的for循環不是通過這種方式，也就是說普通的for循環不會有這種問題）。
那麼首先來看一下ArrayList中iterator方法的實現：
public Iterator<E> iterator() {
return new Itr();
}
可以看到是返回了一個內部類Itr：
/**
* An optimized version of AbstractList.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];
}
//...
}
而拋出異常是在上面第17行程式碼處的checkForComodification方法裡面拋出的，下面來看一下它的實現：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
可以看到如果modCount和expectedModCount不等就會拋出ConcurrentModificationException異常。而上面說過，在add方法和remove方法中，會對modCount修改標誌位做+1的操作。這裡的modCount是為了做快速失敗用的。快速失敗指的是如果在遇到並發修改時，迭代器會快速地拋出異常，而不是在將來某個不確定的時間點冒著任意而又不確定行為的風險來進行操作，也就是將可能出現的bug點推前。在包括HashMap在內的絕大部分集合類都是有快速失敗機制的。注意：這裡的並發修改指的並不都是發生在並發時的修改，也有可能是在單執行緒中所做的修改導致的，就如同上面的反例一樣。
這裡拿上面的反例來舉例，ArrayList調用了兩次add方法，也就是此時的modCount應該為2。而expectedModCount如上所示，一開始會初始化為modCount的值，也就是也為2。
6.1 remove操作
首先來看一下刪除「2」的情況：
第一次循環：
因為此時的modCount和expectedModCount都為2，所以第一次循環中不會拋出異常，拋出異常都是發生在不是第一次循環的情況中。在next方法走完後，foreach循環方法體中的remove方法的if條件判斷不滿足，就結束了本次循環。
第二次循環：
第二次循環的hasNext和next方法都是能成功走完的，在這之後會進入到foreach循環方法體中的remove方法中，進行刪除元素。而此時的size-1變為了1。上面分析過，在remove方法中的fastRemove方法中，會對modCount+1，也就變為了3。
第三次循環：
然後會走入到第三次循環中的hasNext方法中。按照正常的情況下該方法是會返回false的，但因為此時的size已經變為了1，而此時的cursor為2（cursor代表下一次的索引位置），所以兩者不等，錯誤地返回了true，所以會繼續走入到next方法中的checkForComodification方法中，判斷此時的modCount和expectedModCount是否相等。因為此時的modCount已經變為了3，和expectedModCount的值為2不等，所以在此拋出了ConcurrentModificationException異常。
再來看一下刪除「1」的時候為什麼不會拋出異常：
第一次循環：
同上，此時的modCount和expectedModCount都為2，所以第一次循環中的hasNext和next方法都不會拋異常。在這之後會進入到foreach循環方法體中的remove方法中，進行刪除元素。同上，size-1變為了1，而modCount+1變為了3。
第二次循環：
在第二次循環的hasNext方法中，此時的cursor為1，而size也是1，兩者相等。所以hasNext方法返回false，就跳出了foreach循環，不會走到隨後的next方法中，也就不會拋出異常。
6.2 add操作
然後來看一下add操作的情況，其實在第一次循環中添加元素和不是第一次循環中添加元素、從而拋出異常的原因是類似的，這裡就以第一次循環中添加元素來舉例：
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
for (String item : list) {
if ("1".equals(item)) {
list.add(item);
}
}
第一次循環：
同上，此時的modCount和expectedModCount都為2，所以第一次循環中的hasNext和next方法都不會拋異常。在這之後會進入到foreach循環方法體中的add方法中，進行添加元素。size+1變為了3，而modCount+1也變為了3。
第二次循環：
在第二次循環的hasNext方法中，此時的cursor為1，而size為3，兩者不等，所以hasNext方法返回true，會走到隨後的next方法中。而在next方法中的checkForComodification方法中，此時的modCount已經變為了3，而expectedModCount還是為2。兩者不等，所以在此拋出了ConcurrentModificationException異常。
其實從上面的幾次分析中就可以看出：只要在foreach循環方法體中有進行修改過modCount和size的操作，就都有可能會是拋出異常的。
6.3 迭代器操作
6.3.1 remove操作
既然現在已經知道了foreach循環中使用remove/add操作拋出異常的原因，那麼就可以分析一下為什麼使用迭代器進行相關操作就不會有問題呢？上面正例程式碼中的第5行程式碼處的iterator方法、第6行和第7行程式碼處的hasNext和next方法都是跟foreach循環里的實現是一樣的，而區別在於第9行程式碼處的remove操作。這裡的remove不是ArrayList中的remove操作，而是Itr內部類中的remove操作：
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();
}
}
可以看到第7行程式碼處是調用了ArrayList的remove操作進行刪除的，但同時注意第10行程式碼處會將expectedModCount更新為此時modCount的最新值，這樣在next方法中就不會拋出異常了；在第8行程式碼處會將cursor更新為lastRet（lastRet代表上一次的索引位置），即將cursor-1（因為此時要remove，所以cursor指針需要減一）。這樣在hasNext方法中就會返回正確的值了。
6.3.2 add操作
雖然iterator方法可以提供remove操作來使刪除能正確執行，但其卻沒有提供相關add方法的API。無妨， ArrayList中為我們提供了listIterator方法，其中就有add操作（如果一定要用迭代器方式來實現的話）。相關的示例程式碼如下：
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
String item = iterator.next();
if ("1".equals(item)) {
iterator.add(item);
}
}
同上，首先來看一下第5行程式碼處的listIterator方法：
public ListIterator<E> listIterator() {
return new ListItr(0);
}
listIterator方法返回了一個ListItr內部類。那麼就來看一下ListItr的程式碼實現：
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
//...
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();
}
}
}
可以看到ListItr內部類是繼承了Itr類，包括hasNext和next等方法都是直接復用的。而在add方法中的第14行程式碼處，是調用了ArrayList的add操作進行添加的。另外和Itr的remove方法一樣，第17行程式碼處也是在更新expectedModCount為此時modCount的最新值，第15行程式碼處的cursor更新為+1後的結果（因為此時是在做add操作）。這樣後續的hasNext和next操作就不會有問題了。
題外話
在應用業務里待太久很多底層的東西往往容易忽略掉，今年的年初計劃是把常用的JDK源碼工具做一次總結，眼看年底將近，乘著最近有空，趕緊的給補上。在這行乾的越久真是越覺得：萬丈高樓平地起，這絕B是句真理！
- ArrayList你真懂？說說foreach與iterator時remove的區別
- 你是否想過互聯網公司一面為什麼總愛問集合？聊聊經典數據結構HashMap
- AQS源碼深入分析之獨佔模式-ReentrantLock鎖特性詳解
- AQS源碼深入分析之共享模式-為什麼AQS中要有PROPAGATE這個狀態？
- AQS源碼深入分析之條件隊列-Java中的阻塞隊列是如何實現的？
- AQS源碼深入分析之應用工具CountDownLatch（規劃中）
- AQS源碼深入分析之應用工具CyclicBarrier（規劃中）
- ConcurrentHashMap源碼分析-ConcurrentHashMap在Java 8中的實現還有bug？而且還不止一處！這個坑還比較大，後面會重點總結一下！
- ThreadPoolExecutor源碼分析-問爛了的Java執行緒池執行流程，其實如果問的細，很多人還是一臉懵逼？
- ScheduledThreadPoolExecutor源碼分析-重點屢屢定時執行緒池是如何實現延遲執行和周期執行！
- ThreadLocal源碼分析-重點總結，記憶體泄漏，軟引用弱引用虛引用，面試經常喜歡問，我也喜歡問別個
- 紅黑樹TreeMap、LinkedHashMap（不確定要不要寫，有時間寫，看項目情況）
- 有序並且執行緒的Map容器ConcurrentSkipListMap（跳錶）深入理解
- LinkedList（不確定要不要寫，有時間寫，看項目情況）
- 年底如果項目不趕，有空就在寫一篇常用的排序演算法的文章
每一次總結都是對知識點掌握程度的審視，技術不易，每日精進一點，與大家共勉。
