Java之ArrayList源碼淺析

優點：有序，通路元素速度快.

缺點：插入，删除速度慢。

JDK1.8.131版本。

首先檢視ArrayList執行個體化方法相關代碼。

預設無參構造方法。elementData實際存放資料元素,從這些可以看出，ArrayList底層是用數組來實作，元素是連續的；這也展現了ArrayList有序，讀取快，當然數組維護角标，如果在ArrayList元素裡面随機删除個元素，就比較慢了。因為需要維護角标，是以被删除元素後面元素的角标都需要-1。

我們知道ArrayList底層是使用數組來實作的，但是數組是不可變；ArrayList是怎麼實作，動态改變資料元素的呢？這個通過示例（檢視源碼）來說明問題以及原因。

使用ArrayList的無參構造方法，初始化list集合,并使用add方法添加一個"a"元素。

首先，ArrayList先将内部的 elementData 初始化（elementData = {}），這個時候數組的長度是0，list集合的長度也是0.

然後，add方法添加元素，方法中先執行ensureCapacityInternal(size + 1)方法。

add方法以及其涉及到的方法：

在ArrayList将元素添加到集合中之前，先執行了ensureCapacityInternal方法，執行這個方法的目的是檢查集合中元素（數組）是不是還能再插入一個元素，不能則擴容。

流程如下：

先檢查elementData數組是否是預設初始化的數組，如果是則選擇預設初始化容量和最小容量數值大的那一個，再将數值指派給minCapacity變量；如果elementData.lengh小于minCapacity，則擴容（grow）.每次擴容後的容量為int newCapacity = oldCapacity + (oldCapacity >> 1);（之前容量的1.5倍）。如果newCapacity（擴容後的容量）還小于（minCapacity），則直接将新容量定義為minCapacity；如果newCapacity大于了MAX_ARRAY_SIZE，則比較minCapacity和MAX_ARRAY_SIZE的大小，大于則傳回Integer.MAX_VALUE，否則傳回MAX_ARRAY_SIZE，到此擴容後的數組長度确定了，接着使用Arrays.copyOf方法，将之前元素，放入新的數組中，最後執行add方法中elementData[size++] = e，将元素放到集合中。至此添加元素流程完成。

自頂一個ZArrayList,來模拟ArrayList。

首先定義全局變量int count = 0，在擴容方法grow中，使用count+=1，這樣能大緻得出擴容次數。測試代碼

結果如下：

從這些資料可以得出如果依次添加100個元素，大概會擴容7次，如果将資料依次删除，但是list内部數組的長度不變。

特别注意：ArrayList内部數組Object[] elementData的長度不等于ArrayList的size，通過源碼可以看到在add/addAll/remove/removeAll中都維護了一個size變量，這個才是ArrayList元素的個數。

從上邊的分析中可以得出，如果添加資料量比較大的話，最好是給ArrayList一個預設的初始容量，用以減少擴容的次數。

以此類推ArrayList的其他方法addAll和remove方法，原理是相似的，不再贅述。

本文轉自 墨宇hz 51CTO部落格，原文連結:http://blog.51cto.com/zzhhz/2048333