ArrayList原始碼與實作原理決議

ArrayList簡介

在初學Java時就會學習ArrayList、LinkedList這兩種JDK中常見的集合類，其中ArrayList本質上是一種動態陣列，具有良好的隨機訪問的性能，即在集合中查找元素的性能比較高，但是其進行元素的插入和洗掉效率卻偏低；而LinkedList則是一種雙向鏈表，其隨機訪問元素的性能較差，但是對其進行插入和洗掉元素的效率卻比ArrayList高，
以上都是初學Java時需要掌握的基礎知識，如果需要知道為什么ArrayList、LinkedList具有這些區別，它們的實作原理又是什么，則需要閱讀一下這兩個集合類的原始碼，

ArrayList原始碼

1、ArrayList的相關屬性

（1）ArrayList內部定義了一個使用transient修飾的Object型別的陣列elementData，用來存盤元素，ArrayList中的元素實際上都是存盤在elementData陣列中，正因如此，ArrayList才被稱為一種動態陣列，因為elementData是Object型別的陣列，所以向ArrayList里添加元素時，其型別都會向上轉型為Object型，

如果在創建ArrayList實體時使用了泛型，則從ArrayList中取出元素時，會進行向下轉型，將取出的元素型別由Object型轉為傳入的泛型實參型別，反之如果不使用泛型，則取出的元素均無Object型，

這里的transient用來關閉變數的serialization（持久化）機制，一旦變數被transient修飾，變數將不再是物件持久化的一部分，該變數內容在序列化后無法獲得訪問，
為什么elementData[]陣列需要用transient來修飾？
ArrayList在序列化的時候會呼叫writeObject，直接將size和element寫入ObjectOutputStream；反序列化時呼叫readObject，從ObjectInputStream獲取size和element，再恢復到elementData，
ArrayList之所以不直接用elementData來序列化，而要使用自定義的序列化機制，原因在于在Java語言中，陣列的長度是不可變的，ArrayList通過陣列的拷貝來實作陣列容量的擴容，即當陣列容量不夠時會創建一個新的長度更大的陣列并且將原陣列的元素全部拷貝到新陣列內，那么如果每次向ArrayList增加元素時，elementData陣列都要擴容一次，則太消耗性能，因此ArrayList實際上每次進行陣列擴容時會擴容至一個比當前元素數量更大的長度，以便預留出一些容量，等容量不足時再擴充容量，以此來減少陣列擴容的次數（ArrayList擴容機制下文會講解），正因如此，實際上elementData陣列的長度一般比ArrayList的元素數量要大，陣列中的有些空間可能就沒有實際存盤元素，則不需要序列化，采用自定義的方式來實作序列化時，就可以保證只序列化實際存盤的那些元素，而不是整個陣列，從而節省空間和時間，

（2）ArrayList在屬性中實體化了兩個空的陣列，以備ArrayList實體的容量為0時使用，
DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA即為ArrayList內定義的兩個空陣列變數，用static和final關鍵字修飾，其中用static修飾表示這兩個空陣列是靜態變數，即被所有該類的物件所共享的類變數，用final修飾表示指向這兩個空陣列的變數不能再指向其他陣列物件，

這里有兩個問題，首先需要理解ArrayList為什么定義這兩個空陣列，在ArrayList的構造方法中，如果使用無參構造創建物件或者使用帶參構造但是傳入的初始容量為零或者collection物件為空時，則此時創建出來的ArrayList的實體不需要存盤元素，即是一個空集合，在JDK1.7中，如果ArrayList物件的容量是0的話，會創建一個空陣列并將其參考賦給elementData，這就造成了如果我們的專案中空的ArrayList集合的數量比較多的話，則會創建很多個空陣列，造成性能與空間的浪費，為了解決這個問題，在JDK1.8中，ArrayList定義了兩個由所有物件共享的靜態屬性指向兩個空陣列，并且該屬性用final修飾所以存盤的陣列地址不能改變，這樣，無論有多少個空的ArrayList物件，只要是在其容量為0時，其elementData屬性都將其指向了這兩個相同的空陣列，很大程度上減少了空陣列的創建與存在，
還有一個問題，就是為什么要定義兩個成員變數指向空陣列，一個不就夠了嗎？想知道答案的話請看下文的ArrayList構造方法與擴容機制，

（3）定義默認的集合容量為10，此初始容量只有當第一次往集合中添加數量小于10的元素時才會生效，此時ArrayList為了減少陣列擴容次數，會直接將陣列長度擴容至10，而不是實際需要的最小容量（例如增加1個元素就擴容到1，再次增加元素時擴容到2……），如果使用無參構造或者傳入數量為0的帶參構造創建ArrayList實體時，elementData會賦予一個空陣列，此時集合的容量為0，并非默認容量10，

（4）用size標記集合的元素個數，size為集合的元素個數，并非集合中用來存盤元素的陣列elementData的長度，實際上用來存盤元素的陣列的長度一般比size更大一些，

2、ArrayList的構造方法
上文中說到的ArrayList中定義了靜態最終成員變數指向兩個空陣列，在ArrayList的構造方法中，可以看到這兩個變數的應用，

（1）如果使用ArrayList的無參構造，則使用成員變數中定義的空陣列DEFAULTCAPACITY_EMPTY_ELEMENTDATA作為存盤元素的陣列，

（2）如果使用帶容量大小的構造函授，會判斷傳入的容量大小，如果容量大于0，則會創建一個與容量大小等長度的陣列；如果容量大小小于0，則會拋出例外；如果容量大小等于0，則會使用成員變數EMPTY_ELEMENTDATA定義的空陣列作為存盤元素的陣列elementData，

（3）如果使用帶有collection集合作為引數的構造方法，也會使用toArray()方法將集合轉化為陣列然后賦給存盤元素的陣列，如果傳入的collection集合為空，則也會使用成員變數EMPTY_ELEMENTDATA定義的空陣列作為存盤元素的陣列elementData，

這里，可以做一下總結，在創建ArrayList物件時：
1.如果使用無參構造創建物件，則將空陣列DEFAULTCAPACITY_EMPTY_ELEMENTDATA賦值給elementData，
2.如果使用帶參構造創建一個元素個數為零的ArrayList物件時，則將空陣列EMPTY_ELEMENTDATA賦值給elementData，
這是在構造方法中兩個空陣列屬性的區別，在ArrayList的擴容機制中，兩者還有最為本質區別，當然，兩者也有共同點，即都是在集合容量為0時將不同ArrayList物件的elementData屬性指向同一個空陣列，避免了空陣列的重復創建與存在，

3、增加元素
（1）、在尾部增加元素
其步驟為：
①、首先呼叫ensureCapacityInternal()方法檢查陣列長度是否不足，不足的話則創建一個新長度的陣列，采用陣列拷貝的方式將舊陣列的元素復制給新陣列，
②、將陣列的最第N+1個元素賦值，
③、以上兩步完成則回傳true，

ArrayList檢查陣列長度的方法是ensureCapacityInternal方法，其中包含了ArrayList的擴容機制，其程序為：
①、確定陣列所需要的最小容量，邏輯為：判斷elementData是否是ArrayList屬性中定義的其中一個空陣列DEFAULTCAPACITY_EMPTY_ELEMENTDATA（注意，此處非EMPTY_ELEMENTDATA），是的話以默認容量10和當前集合元素總數加上1中的最大值作為陣列需要的最小容量，否的話以原集合元素總數加上1作為陣列需要的最小容量，

②、比較陣列需要的最小容量和當前陣列的實際長度兩者的大小，如果陣列需要的最小容量大于陣列的實際長度，則呼叫方法將陣列進行擴容，

③、在進行陣列擴容時，會先計算陣列需要擴容到的新的容量的大小，按照以下邏輯進行處理：
Ⅰ、采用右移位運算將原陣列長度加上50%作為默認的新的陣列長度，
Ⅱ、如果默認的新的陣列長度比先前計算的最小容量小，則以最小容量作為新的陣列長度，
Ⅲ、如果新的陣列長度大于ArrayList配置的最大陣列長度（int型資料的最大值減去8），則開始比較最小容量和配置的最大陣列長度，如果最小容量大于配置的最大陣列長度，則以int型陣列的最大值為新的陣列長度，反之會配置的最大陣列長度作為新的陣列長度，因此，ArrayList集合默認存盤的最大元素數量是nt型資料的最大值減去8，實際能存盤的最大元素數量是int型資料的最大值，即為2147483647，

④、得到新的容量大小后，采用陣列拷貝的方式，將舊的陣列拷貝至一個以新容量為長度的新陣列中，

由此，可以得到以下結論
a、ArrayList的擴容機制并非是將存盤元素的陣列elementData每次擴容至與實際存盤元素數量相同的大小，而是一般采用移位運算將原先陣列長度增加50%作為新的陣列長度，在這種機制下，可以有效的減少陣列的擴容次數，但是也會造成內部封裝的用來存盤元素的陣列的長度一般比ArrayList集合元素數量大，這是在效率和空間方面做出的權衡，
b、當ArrayList使用帶參構造創建實體但是集合中沒有元素時，空陣列DEFAULTCAPACITY_EMPTY_ELEMENTDATA會賦值給elementData，此后第一次向集合里面添加元素時，如果添加的元素個數小于10，則直接將10作為陣列需要的最小容量，
當ArrayList使用無參構造創建實體時，EMPTY_ELEMENTDATA會賦值給elementData，此后此后第一次向集合里面添加元素時，無論添加元素的個數是否小于10，均以元素的個數作為陣列需要的最小容量，
縱觀ArrayList的全部原始碼，DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA的區別就在于此，至于JDK1.8為什么要這樣做，我想是因為既然使用帶參構造創建實體，那么該集合有較大可能在創建后頻繁使用，所以第一次添加小于10個的元素時，直接將用10作為陣列的最小容量進入擴容，能減少陣列擴容次數，如果使用無慘構造創建實體，則該集合在創建后使用的頻繁性相對偏小，那么在第一次添加元素時以實際的元素個數作為陣列需要的最小容量可以避免空間浪費，
以上這段為筆者個人的猜想，有興趣的程式員可以自己研究下，

（2）在指定位置添加元素
①檢查傳入的位置是否合法，如果位置的值小于0或者大于集合的長度，則拋出例外，

②檢查陣列大小是否足夠，不夠則擴容，
③呼叫System類的arraycopy()進行陣列拷貝，拷貝規則為：將原陣列中從傳入的位置開始到陣列的最后一個元素這一段的所有元素，拷貝到以原陣列中，但是以傳入位置加上1為起始位置進行放置，相當于把從傳入的位置開始直到最后的所以元素向后移了一位，然后傳入的位置就空了出來，
④將陣列中傳入位置的元素賦值，

備注：System類的arraycopy()方法的作用是實作陣列復制，其中各個引數含義為：src:原陣列；srcPos:源陣列要復制的起始位置； dest:目的陣列； destPos:目的陣列放置的起始位置； length:復制的長度，

4、獲取元素

獲取元素即是回傳陣列中指定位置的元素，會先檢查位置是否合法，再從陣列中回傳該位置的元素，

這里其實就可以看出為什么在ArrayList中進行查找指定位置的速度很快，因為ArrayList內部封裝了一個陣列進行元素存盤，陣列具有下標索引，只需要回傳陣列中對應下標的元素即可，不用做任何遍歷操作，所以速度快，

5、在指定位置洗掉元素
（1）檢查傳入的位置是否合法，即如果位置的值小于0或者大于集合的長度，則拋出例外，
（2）從陣列中取出該位置的元素，
（3）判斷傳入的位置是否是陣列中最后一個非空元素的位置，
（4）如果傳入的位置非陣列中最后一個非空元素的位置，則呼叫System類的arraycopy()進行陣列拷貝，拷貝的規則為：將原陣列中從傳入的位置+1的位置開始到陣列的最后一個元素這一段的所有元素，拷貝到以原陣列中，但是以傳入的位置為起始位置，相當于將洗掉位置以后的所有元素前進一位，把需要洗掉的元素覆寫掉，
（5）拷貝完成后，該陣列最末尾有兩個相同的元素，則需要將陣列的最后一個非空元素的值設為null，
（6）回傳洗掉的元素，

這里就可以看出為什么在ArrayList中進行插入和洗掉元素的效率比較低，因為陣列本身不能改變長度，只能創建和拷貝，在指定位置進行插入和洗掉都會引發陣列的創建和拷貝，這是很消耗性能的，

6、根據元素物件找到指定元素并洗掉
從0位置開始遍歷陣列中的元素，直到找到與該物件相同的元素為止，然后使用fastRemove(index)方法進行洗掉并回傳true，注：fastRemove(index)和remove(index)方法類似，只是不獲取要洗掉的物件并回傳而已，
因為此種洗掉的邏輯是遍歷陣列找到第一個與物件相同的元素就進行洗掉并回傳true，所以如果ArrayList集合中包含重復的元素，則該方法只能洗掉第一個，不能將重復的元素全部洗掉，

fastRemove(index)和remove(index)方法類似，只是不獲取要洗掉的物件并回傳，

ArrayList的fail-fast（快速失敗機制）

1、快速失敗機制的概述
ArrayList內部定義了一個成員變數，叫做modCount，用來記錄串列被修改的次數，每次對串列進行洗掉元素操作時，modCount便會自增1次，
ArrayList的快速失敗機制，是Java集合中的一種失敗檢測機制，當迭代集合的程序中，該集合卻被修改了一次之后，就有可能會發生fail-fast，即拋出 ConcurrentModificationException例外，
如下為原始碼，在迭代器每次回傳下一個元素之前，都會呼叫checkForComodification()方法，其中expectedModCount變數記錄的是迭代器初始化時串列的modCount值，如果modCount值有變，則拋出例外，

2、快速失敗機制的引發原理
Iterator其實只是一個介面，具體的實作還是要看具體的集合類中的內部類去實作Iterator并實作相關方法，其中ArrayList類中實作Iterator介面的內部類原始碼為：



該內部類定義了3個屬性，分別為cursor，lastRet，expectedModCount，
這3個屬性的含義分別是：
cursor：迭代器即將遍歷的元素的索引，初始值為0，因為陣列的下標從0開始，每遍歷一個元素，其值自增1，
lastRet：迭代器上一次遍歷的元素的索引，值為cursor-1，初始值為-1，
expectedModCount：用來保存迭代器所記錄的ArrayList物件的modCount值，以便迭代時和串列實時的modCount值做對比，初始值為迭代器實體創建時ArrayList物件的modCount值，
在迭代器中，hasNext()是判斷集合是否還有下一個可以元素可以迭代的方法，其實作在ArrayList中的實作為判斷迭代器即將遍歷的元素的索引是否等于集合的長度，

在迭代器中，next()是回傳集合下一個元素的方法，在該方法的內部最開始機會呼叫checkForComodification()方法來檢測迭代器記錄的modCount值和當前串列實時的modCount值是否相同，如果不同則說明串列的modCount值被修改了，即有執行緒對串列進行了洗掉元素等操作，將拋出例外，

3、快速失敗機制的解決方案
快速失敗機制有兩種解決方案
（1）使用迭代器本身的remove()方法來洗掉集合種的元素，因為迭代器自帶的remove()方法中，會在每次洗掉操作后，將迭代器用來記錄串列modCount值的expectedModCount變數進行更新，保證兩者的一致性，

（2）使用java并發包(java.util.concurrent)中的類來代替 ArrayList 和hashMap，
比如使用 CopyOnWriterArrayList代替 ArrayList， CopyOnWriterArrayList在是使用上跟 ArrayList幾乎一樣， CopyOnWriter是寫時復制的容器(COW)，在讀寫時是執行緒安全的，該容器在對add和remove等操作時，并不是在原陣列上進行修改，而是將原陣列拷貝一份，在新陣列上進行修改，待完成后，才將指向舊陣列的參考指向新陣列，所以對于 CopyOnWriterArrayList在迭代程序并不會發生fail-fast現象，但 CopyOnWrite容器只能保證資料的最終一致性，不能保證資料的實時一致性，
對于HashMap，可以使用ConcurrentHashMap， ConcurrentHashMap采用了鎖機制，是執行緒安全的，在迭代方面，ConcurrentHashMap使用了一種不同的迭代方式，在這種迭代方式中，當iterator被創建后集合再發生改變就不再是拋出ConcurrentModificationException，取而代之的是在改變時new新的資料從而不影響原有的資料 ，iterator完成后再將頭指標替換為新的資料 ，這樣iterator執行緒可以使用原來老的資料，而寫執行緒也可以并發的完成改變，即迭代不會發生fail-fast，但不保證獲取的是最新的資料，