在理解了ArrayList的父類AbstractList的實現(xiàn)之后，我們就要開始動手理解ArrayList.
ArrayList實現(xiàn)了List接口，其中定義了列表應該有的操作，還實現(xiàn)了RandomAccess, Cloneable, Serializable接口，分別讓List具有能夠隨機讀取，可復制，可以序列化的能力．
RandomAccess這個接口，是一個空接口，它其中沒有任何方法的聲明．實現(xiàn)這個接口，只是讓我們知道ArrayList是可以進行隨機讀取的．實際上，由于ArrayList的內部數(shù)據(jù)結構是數(shù)組，所以它天生就具備隨機讀取的能力．
ArrayList中，有一個DEFAULT_CAPACITY屬性，定義了ArrayList起始的默認長度，為10.
但是，這并不意味著，你在創(chuàng)建一個ArrayList時，沒有為其指定容量的話，它會自動為你創(chuàng)建一個長度為10的數(shù)組，作為內部數(shù)據(jù)容器.實際上，如果你在創(chuàng)建ArrayList時，不為其傳遞初始容量這個參數(shù)，其內部維護全部數(shù)據(jù)的數(shù)組，其容量還是為0.
那么DEFAULT_CAPACITY這個屬性到底有什么用呢?
ArrayList還給我們提供了一個叫做ensureCapacity的方法，這個方法能夠讓我們確保手動確保數(shù)組的容量:
結合上面的這三個方法，DEFAULT_CAPACITY的作用就很顯然了．
在ensureCapacity這個方法中，如果elementData這個數(shù)據(jù)容器的數(shù)組，此時其中并沒有任何元素，并且你傳入的minCapacity大于10,就會將elementData擴容到10.反之，如果此時elementData中有元素，那么就會根據(jù)minCapacity和此刻elementData的長度來進行判斷是否進行擴容．
在ensureCapacityInternal方法中，如果elementData此時沒有任何元素，那么就將elementData擴容到DEFAULT_CAPACITY和minCapacity中較大的那個．
需要注意的是，數(shù)組的長度，和數(shù)組中元素的個數(shù)并不是一回事．數(shù)組的長度，是在數(shù)組剛開始被創(chuàng)建時就確定下來的，這樣JVM才能為其分配空間并初始化．而數(shù)組中元素的個數(shù)，則如其名字所示．
比方說，我們這樣創(chuàng)建一個數(shù)組:
int[] arr = new int[10];int[0] = 0;int[1] = 1;
此時，數(shù)組的長度為10，但是其中元素的個數(shù)僅為2.
那么，一個ArrayList的最大長度是多少呢?從源文件中，我們可以看到為Integer.MAX_VALUE - 8．那么為什么要減8呢?
從StackOverflow上面得知，由于數(shù)組的索引采用int表示，所以理論上說，數(shù)組的最大值應該是Integer.MAX_VALUE或者Integer.MAX_VALUE - 1或者Integer.MAX_VALUE - 2．具體多大取決于JVM.
而可能會有一些JVM會將某些ArrayList的信息寫入到其內部的數(shù)組中，所以，為了安全起見，就讓其最大容量為Integer.MAX_VALUE - 8.這只是我的個人猜測，不保證正確．我們從源文件中看到的解釋為:
ArrayList還有兩個類似的屬性，一個為EMPTY_ELEMENTDATA，另一個為DEFAULTCAPACITY_EMPTY_ELEMENTDATA.我們從源文件看到對它們的解釋如下:
那么這兩個屬性有什么區(qū)別呢?
其實它們有啥區(qū)別我也不清楚，反正兩個都是一個空的數(shù)組，而且這兩個空的數(shù)組在使用的過程中也都沒有改變，有啥不一樣的!
ArrayList有三種初始化方式，一種是傳入初始長度，然后ArrayList將其內部的elementData初始化為指定長度的數(shù)組，另一種是什么參數(shù)也不傳，這樣的話，ArrayList就會將其內部的elementData初始化為一個空數(shù)組，最后一種初始化方式，是傳入一個Collection對象，ArrayList會先將這個Collection對象轉換為一個數(shù)組，然后將其賦給elementData.
我們再來看一下ArrayList的擴容函數(shù)，grow.
從這個函數(shù)中，我們可以看到，ArrayList每次進行擴容時，都會先計算我們想要的最小容量是否小于原數(shù)組的長度的3/2倍，如果不是，則擴容到minCapacity大?。绻?，則擴容到原數(shù)組的長度的3/2倍．所以說，我們在使用ensureCapacity這個函數(shù)確保數(shù)組的長度時，數(shù)組擴容后的長度并不一定是我們指定的minCapacity,而更可能是原數(shù)組長度的3/2倍．
另外，這個方法中，很細節(jié)的地方是，在計算3/2倍時，它采用的是oldCapacity + (oldCapacity >> 1)的方式，各位都知道這是什么意思．對于3/2這么一個不快的增長速度來說，如果需要頻繁進行擴容，這就是一個不錯的優(yōu)化點．如果每次增大為原來的兩倍，那么，在第10次擴容后，elementData的長度將為10240.而每次僅擴容為原來的3/2倍，第十次擴容后，elementData的長度將為570.很顯然，遠比每次擴大為兩倍小得多．
我想這里，是開發(fā)者為了協(xié)調空間浪費和時間而做的折中．如果我們開發(fā)應用時，ArrayList需要很快的進行擴容，這里我們可以調整一下擴容的速率．
我們上面提到過，數(shù)組的長度，只能在使用前指定，然后JVM才能進行內存分配以及初始化，也就是說，在初始化完數(shù)組之后，實際上，它的長度就是不可變的了．而每次擴容，就會創(chuàng)建一個新數(shù)組，對于急速增長的ArrayList，效率上是否有點問題,如果我們指定的minCapacity一直都小于oldCapacity * (3 / 2)的話?
接下來，我們看一下indexOf方法的實現(xiàn):
我們可以看到，indexOf方法的實現(xiàn)，跟AbstractList中的實現(xiàn)一樣，時間復雜度都是O(n).所以，如果我們做應用時，用ArrayList來存儲數(shù)據(jù)，并且ArrayList還不小，還有熱點數(shù)據(jù)的需求．那么最好寫一個Map來記錄熱點數(shù)據(jù)和其在ArrayList中對應的位置關系．這樣，如果我們需要查詢該熱點數(shù)據(jù)m次，則使用平攤分析可得時間復雜度為O(n/m)．
但是，這樣也有一個問題，就是，我們知道，ArrayList中一旦刪除了數(shù)據(jù)之后，那么在elementData中，位于該特定數(shù)據(jù)之后的數(shù)據(jù)，都會向左移動．這樣就會有映射失效的問題．
所以，這不是一個好的緩存方案．
我想各位此時心里一萬個草泥馬飄過...
我也是邊寫邊分析的...
起碼現(xiàn)在我們知道了為什么這樣做緩存不好了，對吧?
其實我們還是可以這樣做的，但是在刪除ArrayList中的數(shù)據(jù)的時候，我們需要同時檢查Map中，是否有需要移動的元素，然后Map中存儲的它們在ArrayList中的索引 - 需要移動的值．這些還需要放在同一個事務中來做．
你現(xiàn)在心里可能會想，這不是脫了褲子放屁嘛．我直接用一個HashMap來緩存不就好了，干嘛還要整個ArrayList.
好像確實是這樣...
所以，上面跟緩存相關的這部分，似乎都是一本正經(jīng)的扯淡...
回歸正題!
另外，每次刪除一個元素，都需要移動此元素后面的元素，這樣效率是否有問題呢,對于那種頻繁刪除ArrayList中的元素的應用來說?
我并不知道它具體在移動時是采用什么算法的，System的arraycopy這個方法是native的．
另外，ArrayList的Iterator是Fail-Fast的．也就是說，只要我們調用了那種會改變數(shù)組的長度的方法，那么Iterator就不會正常工作了，而會拋出異常了．
還有ArrayList的subList方法，需要注意的是，它返回的并不是一個新的List,而是一個原來的ArrayList的包裝類．所以，如果你對這個返回的SubList進行修改的話，實際上就是在修改原來的ArrayList.
其他的方法就基本上跟AbstractList差不多了．
ArrayList還提供了一個叫做ArrayListSpliterator的類，這個類用于對ArrayList中的元素，來實現(xiàn)并行計算．具體的實現(xiàn)我也沒有深入了解過．
總體來說，ArrayList的查找,修改，增加的效率還是蠻高的，特別是對于查找和修改，是O(1)的時間復雜度，增加的話，對于數(shù)據(jù)增長不是特別迅速的場景，也是O(1)，但是一旦要進行擴容的話，就是O(n)了，刪除元素的話，就是O(n)了．
所以，如果是那種讀多寫少，并且確定數(shù)據(jù)的數(shù)量不會超過Integer.MAX_VALUE - 8的場景的話，ArrayList還是蠻不錯的．
