1.3　List集合實現——ArrayList

ArrayList集合是JCF中非常重要的集合之一，也是實際工作中最常使用的集合之一。ArrayList集合擁有與Vector集合類似的接口和操作邏輯（從JDK 1.2開始提供），但它不支持線程安全操作（Vector集合支持線程安全操作，但是基于線程安全的多線程操作性能不高）。ArrayList集合也支持隨機訪問，也就是說，ArrayList集合在單線程下對指定索引位上的數據讀取操作的時間復雜度為O(1)。ArrayList集合的主要繼承體系如圖1-13所示。

1.3.1　ArrayList集合概述

ArrayList集合是程序員在單線程操作場景中最常使用的List集合之一。該集合的內部結構是一個數組，并且這個數組在需要的時候可以進行擴容操作，所以理論上ArrayList集合能存儲任意數量的數據對象（但實際上受各種客觀因素限制而無法實現）。ArrayList集合允許將數據對象添加到數組的任意有效索引位上，并且允許從數組的任意有效索引位上獲取數據對象。描述ArrayList集合中重要全局變量和常量的源碼如下。

關于transient修飾符的作用，本書默認各位讀者已經知曉，這里不再贅述。從全局變量的定義方式來看，ArrayList集合和Vector集合的工作思路類似：都支持隨機訪問，都繼承了AbstractList抽象類，都使用數組存儲數據對象，但這兩種集合在細節處理上存在較大差異。

1.3.2　ArrayList集合的初始化操作和擴容操作

本節主要講解ArrayList集合的初始化操作和擴容操作，并且與前面已經介紹的Vector集合進行對比。首先講解ArrayList集合的初始化方法，相關源碼片段如下。

根據上述源碼片段可知，如果在進行初始化時不指定ArrayList集合的容量，那么ArrayList集合會被初始化成一個容量為0的集合。對于上述源碼片段中的默認構造方法，官方給出的初始化意義是“Constructs an empty list with an initial capacity of ten”。這是因為當ArrayList集合處于這種狀態時，后續在向ArrayList集合添加新數據對象時，無論是使用add(E)方法，還是使用add(int, E)方法（或其他方法），ArrayList集合都會使用grow(int)方法將elementData數組擴容成一個新的容量為10的數組。

grow(int)方法是ArrayList集合實際進行擴容操作的方法。由于一個數組在完成初始化后，其容量不能改變。因此ArrayList集合實際的擴容機制是通過某種規則創建一個容量更大的數組，并且按照一定的邏輯將原數組中的數據對象依次復制（引用）到新的數組中。grow(int)方法的完整源碼如下。

根據上述源碼可知，ArrayList集合的擴容操作主要分為兩種情況：在進行擴容操作前，ArrayList集合的容量值為0的情況和不為0的情況。

? 在進行擴容操作前，ArrayList集合容量值不為0。

這種情況就是以上源碼片段中判定條件“ oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA”為true的情況。處理邏輯為，以傳入的minCapacity參數值和原始容量默認的50%增量值的比較結果為依據進行擴容操作。一般會按照原始容量默認的50%增量值進行擴容操作。

? 在進行擴容操作前，ArrayList集合的容量值為0。

這種情況實際上就是ArrayList集合使用默認的構造方法剛完成初始化操作的情況——只要之前發生了一次添加操作，ArrayList集合就不會是這樣的狀態。

擴容操作中的兩種邏輯場景如圖1-14所示。

ArrayList集合內部的數組在長度為0的情況下進行數組引用的替換，嚴格來說都不能稱為擴容操作，因為沒有最關鍵的數據復制過程。但為了統一考慮處理邏輯，我們將其視為擴容操作的一種特殊場景。

1.3.3　ArrayList集合中的add(E)方法

ArrayList集合中的add(E)方法和Vector集合中的add(E)方法功能類似，其處理過程都可以概括如下。

如果集合中還有多余索引位可以存儲數據對象，那么直接在數組最后一個有效索引位的下一個索引位上添加新數據對象；如果集合中沒有多余的索引位可以存儲數據對象，那么先進行擴容操作，再進行新數據對象的添加操作。

兩種集合中的add(E)方法在一些處理細節上有所不同，具體如下。

兩個add(E)方法都是在當前集合中的有效索引位（尾部）的下一個索引位上進行數據對象的添加操作，但兩種集合定義記錄尾部的屬性不一樣。ArrayList集合使用size屬性記錄尾部，Vector集合使用elementCount屬性記錄尾部。注意，這里的“尾部”并不是用elementData數組的length屬性表示的。ArrayList集合中的add(E)方法的相關源碼片段如下。

ArrayList集合中的add(E)方法并不是線程安全的，Vector集合中的add(E)方法，雖然加入了保證線程安全性的機制，但仍然不適合用于高并發場景中。兩種集合在進行擴容操作時，它們的擴容邏輯也不相同。

ArrayList集合還為使用者提供了add(int, E)方法。使用add(int, E)方法，調用者可以在指定的有效索引位上插入一個新的數據對象，在插入新數據對象前，這個索引位上的數據對象會向后移動，源碼如下。

add(int, E)方法和add(E)方法的工作差異在arraycopy()方法處才顯現出來，具體來說，add(int, E)方法可以使用arraycopy()方法將數據對象的添加操作和指定索引位上數據對象的移位操作一次性處理完，如圖1-15所示。

圖1-15中的操作過程是在調用add(int, E)方法時集合容量充足的情況。如果集合容量不充足，那么首先進行擴容操作，然后使用arraycopy()方法將elementData數組中的指定索引位及后續索引位上的數據對象依次向后移動一位，最后將新的數據對象添加（引用）到指定的索引位上。

1.3.4　Vector集合與ArrayList集合對比

本節在介紹ArrayList集合的工作邏輯時，會刻意和Vector集合進行對比，因為這兩種集合的結構、處理邏輯、應用場景都非常相似。

1. 對集合的內部結構進行對比

Vector集合和ArrayList集合的內部結構都是數組，甚至代表數組的變量名都一樣（elementData）。Vector集合中數組的初始化容量值默認為10，并且使用者可以指定Vector集合的初始化容量值。

ArrayList集合中數組的默認初始化容量值也為10，也可以指定集合中數組的初始化容量值，但如果使用者沒有指定初始化容量值，那么ArrayList集合中的elementData數組會被初始化為一個容量值為0的空數組。

2. 對擴容邏輯進行對比

Vector集合和ArrayList集合的擴容邏輯不同，因為兩種集合對擴容平衡性的處理思路不一樣。Vector集合默認采用當前容量的1倍大小進行擴容操作，而且Vector集合可以指定一個固定的擴容增量（capacityIncrement），但除非使用者很明確Vector集合即將承載的數據量規模，否則不推薦使用這種方法，因為固定的擴容增量要么導致頻繁擴容，要么比必要擴容浪費更多的存儲空間。

ArrayList集合在進行擴容操作時會將當前容量增大50%，并且擴容邏輯不能干預，除非擴容前容量值小于10（如果發生這樣的情況，則首先擴容到10）。ArrayList集合的擴容邏輯相對動態，這保證了在擴容操作頻率和擴容大小之間更好的平衡性。

3. 對線程安全性保證進行對比

Vector集合的線程安全性體現在該集合提供給外部調用者使用的讀/寫方法中都會使用synchronized修飾符進行修飾（Object Monitor模式），示例代碼如下。

這種線程安全保證方式的鎖粒度太過粗放，并且已經被本書后續要介紹的各種在高并發場景中使用的集合代替，所以不推薦為了保證線程安全性而使用Vector集合。

ArrayList集合并不是線程安全的，官方也不推薦在多線程場景中使用ArrayList集合。如果使用者強行這么做，那么ArrayList集合很可能出現“臟數據”問題（實際上ArrayList集合會在迭代器中通過modCount全局變量標記的操作數進行一些避免“臟讀”問題的限制，這是一種CAS思想的借鑒）。

4. 對序列化過程進行對比

Vector集合并沒有對集合的序列化過程和反序列化過程進行特殊優化處理（雖然重寫了readObject()方法和writeObject()方法）。在序列化過程中，當前elementData數組中多余的索引位會一起被序列化，這很明顯產生了不必要的性能消耗。

ArrayList集合會對集合的序列化過程和反序列化過程進行針對性的優化處理，在對ArrayList集合進行序列化時，只會對elementData數組中已使用的索引位進行序列化，未使用的索引位不會被序列化；相對地，在原ArrayList集合中已被序列化的各個數據對象被反序列化成新的ArrayList集合中的數據對象時，新的elementData數組不會產生多余的容量，只有在下一次被要求向該集合中添加數據對象時，才會開始新一輪的擴容操作。