前幾天自我學習了arraylist的源碼，寫了篇雲筆記，現将其釋出到部落格，供大家學習交流，本人并非大神，如有任何問題，歡迎批評指正。
<a target="_blank" href="http://download.csdn.net/detail/u010887744/9224715">arraylist源碼jdk1.8下載下傳</a>
接口
特性
實作類
實作類特性
成員要求
list
線性、有序的存儲容器，可通過索引通路元素
arraylist
數組實作，非同步。
vector
類似arraylist，同步。
linkedlist
雙向連結清單，非同步。
arraylist就是動态數組，是array的複雜版本，動态的增加和減少元素，實作了icollection和ilist接口，靈活的設定數組的大小。實作了所有可選清單操作，并允許包括 null 在内的所有元素。除了實作 list 接口外，此類還提供一些方法來操作内部用來存儲清單的數組的大小。
1、arraylist的定義
1）所屬包：package java.util;
2）導入包：
import java.util.function.consumer;
import java.util.function.predicate;
import java.util.function.unaryoperator;
3）定義：
public class arraylist<e> extends abstractlist<e>
implements list<e>, randomaccess, cloneable, java.io.serializable
由arraylist<e>可知其支援泛型
abstractlist提供了list接口的預設實作（個别方法為抽象方法）。
list接口（extends collection）定義了清單必須實作的方法。
randomaccess是一個标記接口，接口内沒有定義任何内容。
實作了cloneable接口的類，可以調用object.clone方法傳回該對象的淺拷貝。
通過實作 java.io.serializable 接口以啟用其序列化功能。未實作此接口的類将無法使其任何狀态序列化或反序列化。序列化接口沒有方法或字段，僅用于辨別可序列化的語義。
2、 arraylist的屬性
private static final long serialversionuid =
8683452581122892189l;
private static final int default_capacity =
10; // 容納能力
private static final object[] empty_elementdata =
{};
private static final object[] defaultcapacity_empty_elementdata =
transient object[] elementdata; //non-private
to simplify nested class access
private int size; //實際包含元素的個數
private static final int max_array_size =
integer.max_value -
8;
private static final int max_array_size = 2147483639; //反編譯的源碼是這個，why？？
預設容量為10；
empty_elementdata[] 建構空集合；
elementdata存儲arraylist内的元素；
size表示包含的元素的數量。
最大容量2147483639，注2147483647=2^31-1
= 2^0+2^1+……+2^30=interger.max_value，相差8是個什麼鬼？
3、關鍵字transient
java的serialization提供了一種持久化對象執行個體的機制。當持久化對象時，可能有一個特殊的對象資料成員，我們不想用serialization機制來儲存它。為了在一個特定對象的一個域上關閉serialization，可以在這個域前加上關鍵字transient。
transient是java語言的關鍵字，用來表示一個域不是該對象串行化的一部分。當一個對象被串行化的時候，transient型變量的值不包括在串行化的表示中，然而非transient型的變量是被包括進去的。
被标記為transient的屬性在對象被序列化的時候不會被儲存,這個字段的生命周期僅存于調用者的記憶體中而不會寫到磁盤裡持久化。
詳見另一篇筆記《java transient關鍵字使用小記》
transient 例子：
a = 25,b = 張三
a = 25,b = null
4、arraylist的構造方法
共有3個構造方法
第三個構造方法則将提供的集合轉成數組傳回給elementdata，傳回的若不是object[]将調用arrays.copyof方法将其轉為object[]
arrays的copyof方法：
5、arraylist方法實作
方法清單：
1
boolean add(e e)
2
void ensurecapacity(int mincapacity)
3
void add(int index,
e element)
4
boolean addall(collection<? extends e> c)
5
boolean addall(int index,
collection<? extends e> c)
6
e get(int index)
7
class<?> getclass()
8
void clear()
9
void trimtosize()
10
boolean contains(object o)
11
int indexof(object o)
12
int lastindexof(object o)
13
boolean containsall(collection
collection)
abstractcollection
14
int hashcode()
java.util.abstractlist
15
object clone()
16
boolean equals(object o)
17
boolean remove(object o)
18
e remove(int index)
19
protected void removerange(int fromindex, int toindex)
20
boolean removeall(collection <?> c)
21
boolean retainall (collection<?> c)
22
e set (int index , e element)
23
object[] toarray()
24
<t> t[] toarray(t[] a)
25
void sort(comparator<? super e> c)
26
int size()
27
list<e> sublist(int fromindex , int toindex)
1）、add(e e)方法：
調用ensurecapacityinternal至少将elementdata的容量增加了1，是以elementdata[size]不會出現越界的情況。
add(e e)都知道是在尾部添加一個元素，如何實作的呢？
arraylist基于數組實作的，屬性中也看到了數組，具體是怎麼實作的呢？比如就這個添加元素的方法，如果數組大，則在将某個位置的值設定為指定元素即可，如果數組容量不夠了呢？具體實作如下：
注：ensurecapacityinternal在arraylist中多次使用，着重了解。
由以上源碼可知：
add方法先調用ensurecapacityinternal方法增加自身容量，
如果擴容後的容量比預設的10小，那麼list的容量将強制更改為預設的10，也就是說隻要調用了add方法，list的容量至少為10。
if擴容後的容量超出了數組可容納的長度則執行grow操作，新的容量為舊的容量的1.5倍，右移操作即除以2（為什麼用右移，而不直接除以2
，這是給電腦運算的，運算的應該是二進制效率才最快，而不是給人類運算的，人類運算的才是十進制）。
grow：如果arraylist的容量超過預設最大值，允許其增加為integer.max_value，即再次增加8。
modcount：
從類 java.util.abstractlist 繼承的字段，protected transient
int modcount，表示已從結構上修改此清單的次數。從結構上修改是指更改清單的大小，或者打亂清單，進而使正在進行的疊代産生錯誤的結果。
在使用疊代器周遊的時候，用來檢查清單中的元素是否發生結構性變化（清單元素數量發生改變）了，主要在多線程環境下需要使用，防止一個線程正在疊代周遊，另一個線程修改了這個清單的結構。使用arraylist中的remove(int
index) remove(object o) remove(int fromindex ,int toindex) add等方法的時候都會修改modcount，在疊代的時候需要保持單線程的唯一操作，如果期間進行了插入或者删除，就會被疊代器檢查獲知，進而出現運作時異常。具體why？？？
arraylist是非線程安全的。
2）void ensurecapacity(int mincapacity)
順帶一起看一下這個方法，這個方法可供外部調用，而ensurecapacityinternal僅供内部方法（如add）調用。
elementdata的length要麼為0，要麼>=10。
minexpand ：elementdata不為空則傳回0，否則傳回10；
1) elementdata為空時，minexpand =10,如果mincapacity>10,則擴容（則length>=10），否則不進行擴容。
2) elementdata非空（并假設其length=20）那麼minexpand=0，
如果我傳入的mincapacity=5>minexpand，那麼将調用ensureexplicitcapacity動态擴容，但mincapacity<elementdata.length，grow便不會執行了，擴容失敗；
如果我傳入的mincapacity=25>minexpand，調用ensureexplicitcapacity，此時又有mincapacity>elementdata.length，執行grow，擴容成功。
在大緻了解list大小時，可用此方法一次性增加mincapacity，這可以減少重配置設定次數，進而提高性能。
3）add(int index,
在指定位置插入指定元素。将目前處于該位置的元素（如果有的話）和所有後續元素向後移動（其索引加 1）。
①先調用rangecheckforadd檢查索引是否合法；
②合法再調用上面講過的ensurecapacityinternal執行擴容；
③調用系統的arraycopy函數将索引處及其後的元素後移一位；
④在index處插入該元素。
add(int index, e element)方法太耗時，主要展現在arraycopy上，一般别用。
4）addall(collection<? extends e> c)
插入集合c（以下函數上面已經細講了，這裡隻講流程了）
①将c轉換為數組a；
②調用ensurecapacityinternal動态擴容；
③調用系統函數arraycopy；
④增加elementdata的size
⑤有意思的小細節，numnew != 0，則傳回true。//
為什麼不從一開始就判斷numnew的值呢，如果等于0，直接傳回，後面的函數也就不用執行了？
5）addall(int index,
在指定位置插入集合c
①和add(int index, e element)一樣，先調用rangecheckforadd檢查做引合法性；
②将c轉換為數組a；
③調用ensurecapacityinternal擴容；
④如果插入位置不是arraylist的末尾，則調用arraycopy将索引及其後的元素後移；
⑤将a的元素arraycopy到elementdata中；
⑥增加size；
⑦numnew != 0，則傳回true
6）e get(int index)
public e
get(int index)
{
rangecheck(index);
return elementdata(index);
}
private void rangecheck(int index)
if (index >= size)
thrownew indexoutofboundsexception(outofboundsmsg(index));
傳回指定位置的元素
①檢查索引合法性；
②傳回指定資料。
7）getclass()
//
調用java.lang.object的getclass
/*
*@return the {@code class} object that represents the runtime
* class of this object.
*/
public final native class<?>
getclass();
傳回目前運作的arraylist。
8）clear()
清空arraylist
①從結構上修改 此清單的次數加1；
②for循環将每個元素置空；
③size置為0，elementdata的長度并沒有修改，如果确定不再修改list内容之後最好調用trimtosize來釋放掉一些空間）。
9）trimtosize()
去掉預留元素的位置。
傳回一個新數組，新數組不含null，數組的size和elementdata.length相等，以節省空間。此函數可避免size很小但elementdata.length很大的情況。
arraylist會每次增長會預申請多一點空間，1.5倍，這樣就會出現當size() = 10的時候，arraylist已經申請了15空間， trimtosize就是删除多餘的5，隻留10。
或許有人會有疑問：
調用arrays.copyof複制size長度的元素到elementdata，而且由源碼看應該是從0複制到size處，那麼如果我之前調用過add(int index, e element)呢？比如，list={1，2，3，null，null，4，null，null}，如果調用trimtosize傳回的應該是list={1，2，3，null}（因為size=4）。（我剛看這個時就這麼考慮的）
其實上面這種情況不會發生的，因為調用add(int index, e element)時，會檢查index的合法性，是以list的元素肯定是相鄰的，而不會出現上述這種中間出現null的情況。
10）boolean contains(object o)
判斷對象o是否包含在arraylist中。
注：不建議使用contains(object o)方法，看源碼就知道了，調用其内置的indexof方法，for循環一個個equals，這效率隻能呵呵哒了，建議使用hashcode。
11）int indexof(object o)
12）int lastindexof(object o)
indexof方法：
if (o == null)什麼鬼？難道arraylist包含了null，趕緊敲代碼來壓壓驚。
原來arraylist不僅可以添加null，而且可以“随意”加！
另外，還允許存在相同的元素哦。
13）boolean containsall(collection
判斷集合a是否全部包含于集合b。
14）int hashcode()
繼承java.util.abstractlist的hashcode。
15）object clone()
傳回arraylist執行個體的淺拷貝，
【淺克隆就是我們所看到的arrays.copyof， system.arraycopy，數組是新的，但是裡面n個元素全是引用的舊的。】
==輸出為false，修改list2但list1未修改，這貌似是deepcopy啊？？？？
其實不然，上述程式僅僅包含基本類型，沒有module，
淺拷貝(影子克隆):隻複制基本類型。
深拷貝(深度克隆):基本類+對象。
16）boolean equals(object o)
先看一下instanceof ，這是java的一個關鍵字，一個二進制操作符。作用是測試它左邊的對象是否是它右邊的類的執行個體，傳回boolean類型的資料。詳細見java目錄另一篇筆記《java中的instanceof關鍵字》。
(o1==null ? o2==null : o1.equals(o2))
如果o1==null，傳回o2==null的值，如果o2恰好為null，那麼傳回結果為true;
如果o1!=null，傳回 o1.equals(o2)的值，如果o2、o2相等，那麼傳回結果為tru。
注意前面還有個非“ ! ”噢。
17）boolean remove(object o)
首先判斷要remove的元素是null還是非null，然後for循環查找，核心是fastremove(index)方法。
fastremove并不傳回被移除的元素。
elementdata[--size] = null;因為arraycopy方法是将elementdata的index+1處開始的元素往前複制，也就是說最後一個數本該消除，但還在那裡，是以需要置空。如原數組{1,2,3,4}，删除index=1時，首先調用arraycopy，結果為{1,3,4,4}，最後一個4并沒有删除。
至于源碼說的将最後一位指派為null以便垃圾回收，個人不太了解？
18）e remove(int index)
删除指定位置的元素，調用的arraycopy方法前面已經講過了。
19）void removerange(int fromindex, int toindex)
20）boolean removeall(collection<?> c)
21）boolean retainall(collection<?> c)
removeall、retainall：删除或保留arraylist中包含collection
c中的的元素。
首先判斷集合是否為空；
核心方法batchremove：（batch批處理）,boolean complement相當精妙，代碼重用！！
以removeall為例，batchremove(c,
false)，
①周遊elementdata，
如果集合c中包含elementdata的元素e，則c.contains(elementdata[r])為true，if不成立，if結束；
如果c不包含elementdata的元素e，則if成立，将此元素e指派給elementdata[w++]【即elementdata保留了c中沒有的元素，也就是删除了c中存在的所有元素】。
②執行finally，finally是不管try中結果如何都會執行的哦。
if (r != size)，則将elementdata未參加比較的元素arraycopy到elementdata後面；新索引w加上剛arraycopy的數目；
if (w != size)，此時w還不等于size，則将w後的元素移除，為什麼移除（調用了arraycopy，詳見fastremove）。
隻有執行了if (w != size)（事實上隻要c中含有elementdata的元素，w肯定不等于size），才令modified = true，才說明remove成功，傳回true，否則傳回false。
小例子：
remove中還有一個removeif，用的不多，這裡就暫時不去分析源碼了。
22）e set(int index,
在指定位置插入新的value，并傳回oldvalue。
23）object[] toarray()
public object[]
toarray() {
return arrays.copyof(elementdata, size);
@suppresswarnings("unchecked")
publicstatic <t>
t[] copyof(t[] original, intnewlength)
return (t[]) copyof(original, newlength, original.getclass());
// copyof方法詳見arraylist的第三個構造方法
此方法即将size大小的list轉為數組。
24）<t> t[] toarray(t[] a)
①如果傳入數組的長度length小于size，傳回一個新的數組，大小為size，類型與傳入數組相同；
②否則将elementdata的元素全部複制到傳入的數組a中，并傳回a；
③若length大于size，除了複制elementdata外，還将把傳回數組的第size個元素置為空。《隻是第size個哦，其他空位不管》
25）void sort(comparator<? super e> c)
expectedmodcount 初始設定為modcount，用于記錄arraylist發生結構性改變的次數，執行完sort後去檢查expectedmodcount值是否和現在的modcount相等，進而保證執行sort時資料結構沒有被其他程序修改，保證資料準确性。
26）int size()
傳回實際大小size。
27）list<e> sublist(int fromindex, int toindex)
這個方法有陷阱，詳情及破解方法見另一篇筆記《java.util.list.sublist陷阱及解決方法》。
ps:寫太多，有道雲就崩潰了，不能繼續寫了，幸好還可以複制出來。
再寫就沒有撤銷功能了。。。。
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)