本文基于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 = https://www.cnblogs.com/tomakemyself/p/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 =https://www.cnblogs.com/tomakemyself/p/= 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 = https://www.cnblogs.com/tomakemyself/p/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 = https://www.cnblogs.com/tomakemyself/p/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（不確定要不要寫，有時間寫，看專案情況）
- 年底如果專案不趕，有空就在寫一篇常用的排序演算法的文章
每一次總結都是對知識點掌握程度的審視，技術不易，每日精進一點，與大家共勉，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/139677.html
標籤：Java
上一篇：買不到的數目[藍橋杯]