從JDK源碼學習Arraylist

2020 年 4 月 10 日
筆記

從今天開始從源碼去學習一些Java的常用數據結構，打好基礎:)

Arraylist源碼閱讀：

jdk版本：1.8.0

首先看其構造方法：

構造方法一：

第一種支援初始化容量大小，其中聲明一個對象數組，賦值給this.elementdata

構造方法二：

第二種無參構造函數，即不指定初始容量大小，則默認賦值this.elementdata為一個空的對象數組，但是由注釋可以看到其無參構造實際上初始容量為10

在elementData的注釋中也說了該變數是實際存儲Arrylist數據的存儲結構，任何空的arraylist，當第一次被調用add放進元素時，將會擴充容量為default_capacity也就是10

看看其add方法，因為arraylist也是有序的，因此加入的元素在列表尾部，在添加元素之前，調用ensureCapacityInternal，確保內部容量大小

在ensureCapacityInternal中將判斷當前的elementdata的值是否為空數組，若為空則賦值minCapacity為默認容量和入口參數minCapacity的較大值，然後進一步調用ensureExplicitCapacity明確容量大小

在ensureExplicitCapacity中，modCount自增，判斷當前最小容量和arraylist的實際元素個數差值若大於零，則調用grow函數來進行實際的容量擴充

擴容函數grow先取到當前arraylist的實際長度，然後將其擴大1.5倍，然後判斷該值和最小容量的大小，若擴充1.5倍小於所需要的最小容量，則賦值新的容量為需要的最小容量，此時並判斷是否產生溢出情況，也就是注釋裡面的overflow conscious mode的含義，所以arraylist不是無限擴容，看下其max_array_size的值

數組最大值為integer.max_value-8，也就是2的31次-1-8

至於為什麼要-8，這裡有些vm要存儲其最大值的大小需要八個位元組，如下圖所示

如果擴充的新容量比max還大，則調用hugeCapacity，判斷最小的容量和2的31次-1的大小，若大於則賦值max_value,否則說明此時最小容量介於max_value-8和max_value之間，則賦值為max_value-8

然後調用Array.copyof將舊的arraylist中的值拷貝到新的擴充後的arraylist中，所以默認空數組的add操作後容量即為10

構造方法三：

可以傳遞任何實現了Collection介面的類，其調用collection的toarray方法返回一個對象數組，也就是將集合中的元素以對象數組形式返回，toarray的注釋里也說明了這個方法是array和collection的橋樑

為了防止重寫toArray方法返回的並不是對象數組，因此這裡判斷一下elementData的類是否是對象數組，如果不是的話，則將element中的數組copy到對象數組中

比如有MySubClass是MyClass的子類。  Collection<MyClass> myCollection;  //myCollection里有很多元素。  Collection<MySubClass> mySubCollection;  //mySubCollection里有很多元素。  ArrayList<MyClass> myList = new ArrayList<MyClass>(myCollection);  也可以：  ArrayList<MyClass> myList = new ArrayList<MyClass>(mySubCollection);

意思就是這裡用extends e，來指定定義一個父類的arraylist，則其所有子類的集合都能放進該父類的arraylist，從而編譯器才能夠知道放入的元素都是滿足？也就是，初始定義arraylist的類型聲明

關於執行緒安全：

上面遺留了一個modcount++的自增操作的解釋，看一下jdk對modcount的解釋

該參數是對arraylist容量大小修改的次數，也就是刪減元素改變大小時可能會使正常的迭代過程出現錯誤，那麼針對單執行緒而言，不存在又讀又寫，但在多執行緒情況下，可能存在讀寫同時進行的操作，參考知乎一個很精簡明確的答案，看完真的是一目了然，如果結構發生變化則拋出ConcurrentModificationException