Jdk1.6 Collections Framework源碼解析(1)-ArrayList

工作中經常會用到Java的集合類，最近不忙了，把相關知識總結一下，便于了解記憶。

打開java.util.ArrayList的源代碼，首先映入眼簾的是@author Josh Bloch(相對于源碼，本人更喜歡看故事 :D ，每次看到一份源碼，先看看作者是誰。然後搜尋一下作者的百科以及一些八卦。。。以及與作者相關的人的百科和一些八卦。。。以及。。。一上午就過去了。。。

言歸正傳，看一個類的時候首先要看看這個類能幹什麼，有什麼特性。這些都可以在這個類實作的接口上展現了(廢話。。。)。好，直接從最頂級的接口看吧。首先是接口java.lang.Iterable:

由于篇幅的關系，去掉了注釋。注釋上說明，實作了這個接口的類，可以使用"foreach"文法。

接下來是接口java.util.Collection:

裡面的注釋很詳細，反正大概意思是說(英語不太好)，這是集合層次的頂級接口，代表了一組對象blablablabla，所有通用的實作應該提供兩個"标準"的構造方法:無參的構造方法和擁有一個集合類型參數的構造方法blablablabla，總之這個接口對集合進行了高度滴、抽象滴定義：）

接下來就是java.util.List接口了。

list代表了一個有序的集合，可以通過index來通路和查找集合内的元素，集合内元素是可重複的，因為index(集合中的位置)不同。

還有一個ArrayList實作的接口是java.util.RandomAccess:

一看沒有方法的接口，就知道這大概是個标記接口喽。實作這個接口的集合類會在随機通路元素上提供很好的性能。比如說，ArrayList實作了RandomAccess而LinkedList沒有，那麼當我們拿到一個集合時(假設這個集合不是ArrayList就是LinkedList)，如果這個集合時ArrayList，那麼我們周遊集合元素可以使用下标周遊，如果是LinkedList，就使用疊代器周遊。比如集合工具類Collections中提供的對集合中元素進行二分查找的方法，代碼片段如下：

還有java.lang.Cloneable和java.io.Serializable兩個标記接口，表示ArrayList是[url=http://brokendreams.iteye.com/blog/1940038][color=orange]可克隆的[/color][/url]、可序列化的。

還要看一下AbstractCollection和AbstractList，這兩個抽象類裡實作了一部分公共的功能，代碼都還比較容易看懂。

需要注意的地方是AbstractList中的一個屬性modCount。這個屬性主要由集合的疊代器來使用，對于List來說，可以調用iterator()和listIterator()等方法來生成一個疊代器，這個疊代器在生成時會将List的modCount儲存起來(疊代器實作為List的内部類)，在疊代過程中會去檢查目前list的modCount是否發生了變化(和自己儲存的進行比較)，如果發生變化，那麼馬上抛出java.util.ConcurrentModificationException異常，這種行為就是fail-fast。

好了，終于可以看ArrayList了，在看之前可以先思考一下，如果我們自己來實作ArrayList，要怎麼實作。我們都會把ArrayList簡單的看作動态數組，說明我們使用它的時候大都是當做數組來使用的，隻不過它的長度是可改變的。那我們的問題就變成了一個實作長度可變化的數組的問題了。那麼首先，我們會用一個數組來做底層資料存儲的結構，建立的時候會提供一個預設的數組長度。當我們添加或删除元素的時候，會改變資料的長度(當預設長度不夠或者其他情況下)，這裡涉及到資料的拷貝，我們可以使用系統提供的System.arraycopy來進行數組拷貝。如果我們每次添加或者删除元素時都會因為改變數組長度而拷貝數組，那也太2了，可以在當數組長度不夠的時候，擴充一定的空間，比如可以擴充到原來的2倍，這樣會提高一點性能(如果不是在數組末尾添加或删除元素的話，還是會進行數組拷貝)，但同時浪費了一點空間。再看看上面的接口，比如我們要實作size方法，那麼就不能直接傳回數組的長度了(由于上面的原因)，也沒辦法去周遊數組得到長度(因為可能存在null元素)，我們會想到利用一個私有變量來儲存長度，在添加删除等方法裡面去相應修改這個變量(這裡不考慮線程安全問題，因為ArrayList本身就不是線程安全的)。

帶着這些問題，來看一下ArrayList的代碼。

首先，真正存儲元素的是一個數組。

那麼這個數組該怎麼初始化呢？數組的長度該怎麼确定呢？看一下構造方法。

可以看到，我們可以選擇使用一個參數作為ArrayList内部數組的容量來構造一個ArrayList；或者使用無參的構造方法，這樣會預設使用10作為數組容量。我們在實際應用中可以根據具體情況來選擇使用哪個構造方法，例如在某種特定邏輯下，我們需要存儲200個元素(固定值)到一個ArrayList裡，那我們就可以使用帶一個int型參數的構造方法，這樣就避免了在數組長度不夠，進行擴容時，内部數組的拷貝。

當然，根據接口java.util.Collection的規範(非強制)，ArrayList也提供用一個集合做為參數的構造方法。

上面說到說考慮用一個私有變量來存儲size(集合中實際原始的個數)。在ArrayList也有這樣一個變量。

有了這個變量，一些方法實作起來就非常簡單了。

由于内部數組的存在，一些基于下标的方法實作起來也非常簡單。

有幾個要注意的地方，首先是RangeCheck方法，顧名思義是做邊界檢查的，看看方法實作。

異常資訊是不是很眼熟，呵呵。

還有就是在"添加"方法中的ensureCapacity方法，上面也考慮到擴容的問題，這個方法其實就幹了這件事情。

注意當數組長度不夠的時候，會進行數組的擴充，擴充到原來長度的1.5倍(注意整型的除法)加1，比如原來是2，會擴充到4，原來是30，會擴充到46。當數組的長度大到算出的新容量超出了整型最大範圍，那麼新容量就等于傳入的"最小容量"。

最後再看一下另一個删除方法。

可以看到，像size、isEmpty、get、set這樣的方法時間複雜度為O(1)，而像indexOf、add、remove等方法，最壞的情況下(如添加元素到第一個位置，删除第一個位置的元素，找最後一個元素的下标等)時間複雜度為O(n)。

一般情況下内部數組的長度總是大于集合中元素總個數的，ArrayList也提供了一個釋放多餘空間的方法，我們可以适時調用此方法來減少記憶體占用。

基本上ArrayList的内容總結的差不多啦。最後，别忘了它是線程不安全的。