這一篇開始說arraylist
參考代碼為jdk1.6_45 jdk1.7_80 jdk1.8_111中的源碼，對比閱讀，發(fā)現(xiàn)修改的問題以及改進(jìn)點(diǎn)。
public class arraylist<e> extends abstractlist<e> implements list<e>, randomaccess, cloneable, java.io.serializable
一、基本性質(zhì)
1、底層使用原生數(shù)組實(shí)現(xiàn)，實(shí)現(xiàn)randomaccess接口，可以隨機(jī)訪問，隨機(jī)訪問指的是下標(biāo)索引操作index(i)的時間復(fù)雜度是o(1)。
size、isempty、get、set、iterator和listiterator操作在o(1)內(nèi)完成，add(e)操作平均在o(1)內(nèi)完成，即添加n個元素需要o(n)時間（這個是collection.add，是在尾部添加注意區(qū)分下list.add(index, e)）。其他操作基本都是o(n)內(nèi)完成。arraylist與linkedlist實(shí)現(xiàn)相比，o(n)的各個方法的時間復(fù)雜度的常數(shù)因子更小。
2、因?yàn)榈讓訑?shù)組 elementdata 的容量是不能改變的，所以容量不夠時，需要把 elementdata 換成一個更大的數(shù)組，這個過程叫作擴(kuò)容。實(shí)際的元素的數(shù)量size，總是不會超過底層數(shù)組的容量 elementdata.length，因?yàn)閿U(kuò)容需要申請更大的內(nèi)存，并且需要原來數(shù)組的進(jìn)行一次復(fù)制，所以擴(kuò)容是個耗時的操作。在添加大量元素之前，使用者最好是預(yù)估一個大致的數(shù)量，手動調(diào)用ensurecapacity進(jìn)行一次擴(kuò)容操作，避免一個個添加導(dǎo)致頻繁擴(kuò)容影響性能。
3、arraylist是未同步的，多線程并發(fā)讀寫時需要外部同步，如果不外部同步，那么可以使用collections.synchronizedlist方法對arraylist的實(shí)例進(jìn)行一次封裝，或者使用vector。
4、對存儲的元素?zé)o限制，允許null元素。
5、arraylist的iterator和listiterator方法返回的迭代器是快速失敗的，也就是如果在創(chuàng)建迭代器之后的任何時間被結(jié)構(gòu)性修改，除了通過迭代器自己的remove或add方法之外，迭代器將直接拋出一個concurrentmodificationexception，從而達(dá)到快速失敗fail-fast的目的，盡量避免不確定的行為。
arraylist的迭代器的快速失敗行為不能被嚴(yán)格保證，并發(fā)修改時它會盡量但不100%保證拋出concurrentmodificationexception。因此，依賴于此異常的代碼的正確性是沒有保障的，迭代器的快速失敗行為應(yīng)該僅用于檢測bug。
6、實(shí)現(xiàn)clone接口，可以調(diào)用其clone方法（雖然clone()是object中的方法，但是它是protected，使用子類的clone()必須在子類中覆蓋此方法）。clone方法復(fù)制一個arraylist，底層數(shù)組elementdata不共享，但是實(shí)際的元素還是共享的。
不過clone是arraylist中覆蓋的，不屬于list中的方法，因此常見的聲明形式
list<string> strs = new arraylist<>()；
聲明出來的變量不能直接使用clone方法，本身也用得極少。
7、實(shí)現(xiàn)serializable接口，可以被序列化。arraylist"實(shí)現(xiàn)"了自定義序列化方法，這么做主要是為了節(jié)省空間 。對于占用空間的大頭——元素list，僅僅序列化實(shí)際size大小的元素，同時不序列化對于新對象無用屬性的——來自父類abstractlist的modcount。arraylist的實(shí)際size不會超過底層數(shù)組的length，大多數(shù)情況下比底層數(shù)組length小，使用默認(rèn)序列化的話，會直接序列化整個底層數(shù)組，序列化后字節(jié)流會變大，浪費(fèi)空間。
二、構(gòu)造方法
1、默認(rèn)構(gòu)造方法，arraylist()
關(guān)于默認(rèn)構(gòu)造方法，你可能在別的地方看見過這種話：無參構(gòu)造方法（默認(rèn)構(gòu)造方法）構(gòu)造的arraylist的底層數(shù)組elementdata大小（容量）默認(rèn)為10。這里告訴你，這不一定是對的。這句話在1.6版本中是對的（更之前的版本我沒看），從1.7開始這句話就有問題了。下面我貼出了三個版本的代碼：
jdk1.6的，初始化成10個容量。
|
1
2
3
4
5
|
// jdk1.6的 /** constructs an empty list with an initial capacity of ten. */ public arraylist() { this(10); } |
jdk1.7的，相對1.6版本，引入了一個新的常量empty_elementdata，它是一個空數(shù)組，因此容量為0。
|
1
2
3
4
5
6
7
8
9
10
11
|
// jdk1.7的 /** shared empty array instance used for empty instances. */private static final object[] empty_elementdata = {}; ... /** constructs an empty list with an initial capacity of ten. */public arraylist() { super(); this.elementdata = empty_elementdata; } |
jdk1.8的，相對1.7版本，又引入了一個新的常量defaultcapacity_empty_elementdata ，它也是一個空數(shù)組，因此容量也為0。至于兩個空數(shù)組有什么區(qū)別，看下面一點(diǎn)說的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/** shared empty array instance used for empty instances. */private static final object[] empty_elementdata = {}; /** * shared empty array instance used for default sized empty instances. we * distinguish this from empty_elementdata to know how much to inflate when * first element is added. */private static final object[] defaultcapacity_empty_elementdata = {}; ... /** constructs an empty list with an initial capacity of ten. */public arraylist() { this.elementdata = defaultcapacity_empty_elementdata; } |
對比下可以看出：jdk1.6的無參構(gòu)造方法（默認(rèn)構(gòu)造方法）構(gòu)造的arraylist的底層數(shù)組elementdata大小（容量）默認(rèn)為10；從1.7開始，無參構(gòu)造方法構(gòu)造的arraylist的底層數(shù)組elementdata大小默認(rèn)為0。
java集合類在jdk1.7版本基本上都有一種改動：懶初始化。懶初始化指的是默認(rèn)構(gòu)造方法構(gòu)造的集合類，占據(jù)盡可能少的內(nèi)存空間（對于arraylist來說，使用空數(shù)組來占據(jù)盡量少的空間，不使用null是為了避免null判斷），在第一次進(jìn)行包含有添加語義的操作時，才進(jìn)行真正的初始化工作。
1.7開始的arraylist，默認(rèn)構(gòu)造方法構(gòu)造的實(shí)例，底層數(shù)組是空數(shù)組，容量為0，在進(jìn)行第一次add/addall等操作時才會真正給底層數(shù)組賦非empty的值。如果add/addall添加的元素小于10，則把elementdata數(shù)組擴(kuò)容為10個元素大小，否則使用剛好合適的大小（例如，第一次addall添加6個，那么擴(kuò)容為10個，第一次添加大于10個的，比如24個，擴(kuò)容為24個，剛好合適）；1.8版本，默認(rèn)構(gòu)造的實(shí)例這個行為沒有改變，只是用的數(shù)組名字變了。
順便吐槽下：jdk這個類維護(hù)者，你能不能改下默認(rèn)構(gòu)造方法上的注釋啊，默認(rèn)構(gòu)造方法的行為都改變了，你注釋還是用之前的！！！
2、帶初始容量的構(gòu)造方法，public arraylist(int initialcapacity)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
// 1.6 public arraylist(int initialcapacity) { super(); if (initialcapacity < 0) throw new illegalargumentexception("illegal capacity: "+ initialcapacity); this.elementdata = new object[initialcapacity]; } // 1.7 跟1.6的一樣 public arraylist(int initialcapacity) { super(); if (initialcapacity < 0) throw new illegalargumentexception("illegal capacity: "+ initialcapacity); this.elementdata = new object[initialcapacity]; } // 1.8 public arraylist(int initialcapacity) { if (initialcapacity > 0) { this.elementdata = new object[initialcapacity]; } else if (initialcapacity == 0) { this.elementdata = empty_elementdata; // 重用空數(shù)組，一個小小的優(yōu)化 } else { throw new illegalargumentexception("illegal capacity: "+ initialcapacity); } } |
678三個版本的這個構(gòu)造方法的實(shí)際行為基本一致：如果initialcapacity >= 0，把底層數(shù)組elementdata賦值為一個大小為initialcapacity的數(shù)組，數(shù)組的所有元素都是默認(rèn)值null。1.8稍微進(jìn)行了一點(diǎn)優(yōu)化，也是賦值為空數(shù)組，但是重用了常量對象。
下面寫個簡單的例子看一個細(xì)微的區(qū)別。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
// jdk1.6，兩個構(gòu)造的區(qū)別很明顯 public class testarraylist { public static void main(string[] args) { list<string> la = new arraylist<string>(0); // la.elementdata = new object[0], la.elementdata.length = 0 la.add("111"); // la.elementdate.length = 1，這里一次性擴(kuò)容了1個，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 list<string> lb = new arraylist<string>(); // lb.elementdata = new object[10], lb.elementdata.length = 10 lb.add("111"); // lb.elementdate.length = 10，這里沒有進(jìn)行擴(kuò)容，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 } } // jdk1.7，兩個構(gòu)造在第一次進(jìn)行添加時才看得出區(qū)別 public class testarraylist { public static void main(string[] args) { list<string> la = new arraylist<>(0); // la.elementdata = new object[0], la.elementdata.length = 0 la.add("111"); // la.elementdate.length = 1，這里一次性擴(kuò)容了1個，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 list<string> lb = new arraylist<>(); // lb.elementdata = empty_elementdata, lb.elementdata.length = 0 lb.add("111"); // lb.elementdate.length = 10，這里一次性擴(kuò)容了10個，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 } } // jdk1.8，同1.7 public class testarraylist { public static void main(string[] args) { list<string> la = new arraylist<>(0); // la.elementdata = empty_elementdata, la.elementdata.length = 0 la.add("111"); // la.elementdate.length = 1，這里一次性擴(kuò)容了1個，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 list<string> lb = new arraylist<>(); // lb.elementdata = defaultcapacity_empty_elementdata, lb.elementdata.length = 0 lb.add("111"); // lb.elementdate.length = 10，這里一次性擴(kuò)容了10個，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 } } |
jdk1.6中new arraylist<?>()跟new arraylist<?>(10)的行為是一模一樣的，所以跟new arraylist<?>(0)有很明顯區(qū)別，這個好理解 。從1.7版本開始，new arraylist<>()和new arraylist<>(0)，雖然創(chuàng)建后底層內(nèi)容和容量都一樣，但是實(shí)際的行為有些細(xì)小的差別，那就是這兩個在第一次自動擴(kuò)容時策略不一樣。不過這一點(diǎn)影響比較小，基本不影響使用。
1.8中使用兩個空數(shù)組，正如注釋所說的，是在優(yōu)化（避免創(chuàng)建無用的空數(shù)組）的同時，保留其擴(kuò)容初始策略區(qū)別。只用一個空數(shù)組就不能再優(yōu)化的同時，繼續(xù)保持這個小區(qū)別了。
3、collection拷貝構(gòu)造方法，public arraylist(collection<? extends e> c)
678三個版本的關(guān)系和第2點(diǎn)一樣。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// jdk 1.6 public arraylist(collection<? extends e> c) { elementdata = c.toarray(); size = elementdata.length; // c.toarray might (incorrectly) not return object[] (see 6260652) if (elementdata.getclass() != object[].class) elementdata = arrays.copyof(elementdata, size, object[].class); } // jdk 1.7 public arraylist(collection<? extends e> c) { elementdata = c.toarray(); size = elementdata.length; // c.toarray might (incorrectly) not return object[] (see 6260652) if (elementdata.getclass() != object[].class) elementdata = arrays.copyof(elementdata, size, object[].class); } // jdk 1.8 public arraylist(collection<? extends e> c) { elementdata = c.toarray(); if ((size = elementdata.length) != 0) { // c.toarray might (incorrectly) not return object[] (see 6260652) if (elementdata.getclass() != object[].class) elementdata = arrays.copyof(elementdata, size, object[].class); } else { // replace with empty array. this.elementdata = empty_elementdata; } } |
關(guān)于中間這行注釋，可以看下這篇
此構(gòu)造方法會有和array.copyof/system.arraycopy一樣的問題，那就是它只是新建一個elementdata數(shù)組，數(shù)組的內(nèi)容對應(yīng)相等，但是不拷貝實(shí)際的元素，實(shí)際的元素占據(jù)的內(nèi)存空間還是共享的。
三、確保容量方法（擴(kuò)容方法）：ensurecapacity/ensurecapacityinternal
提前聲明下：這兩個方法只是確保容量，不一定會擴(kuò)容，但是為了好理解，下面的文字中所說的"擴(kuò)容"指的就是這兩個方法。
因?yàn)樵臄?shù)組的容量不能改變，要改變數(shù)組的容量，只能是新建一個數(shù)組，并把原來數(shù)組的內(nèi)容復(fù)制到新數(shù)組對應(yīng)位置上去。數(shù)組拷貝使用的是arrays.copyof，底層用的是system.arraycopy，比循環(huán)賦值效率高。擴(kuò)容示意圖如下。
擴(kuò)容方法四個位置用到：兩個add方法，兩個addall方法，一個反序列化方法，還有就是手動擴(kuò)容方法ensurecapacity（稱之為手動，是因?yàn)榇朔椒ㄊ莗ublic的，可以外部手動調(diào)用）。在1.6版本是只有這個手動的方法，內(nèi)部自動操作也是調(diào)用這個方法，1.7開始進(jìn)行了區(qū)分，并且進(jìn)一步改進(jìn)了擴(kuò)容操作。
下面的是jdk1.8的代碼，1.7的和1.8的基本相同，唯一的一點(diǎn)區(qū)別就是1.8用兩個空數(shù)組，導(dǎo)致這里的空數(shù)組的名字不一樣，兩個版本的代碼可以看作是一樣的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
// 手動擴(kuò)容方法（可以外部調(diào)用，不過大多數(shù)情況都是list<?> = new arraylist<>()，這樣是調(diào)用不到這個方法的） // 這個方法只是簡單區(qū)別下list是不是通過 new arraylist() 來創(chuàng)建的，這一點(diǎn)前面說了 // 如果是，則嘗試最小擴(kuò)容10個，不是則嘗試擴(kuò)容指定個，具體也是通過內(nèi)部擴(kuò)容方法完成容量確保 public void ensurecapacity(int mincapacity) { int minexpand = (elementdata != defaultcapacity_empty_elementdata) // any size if not default element table ? 0 // larger than default for default empty table. it's already // supposed to be at default size. : default_capacity; if (mincapacity > minexpand) { ensureexplicitcapacity(mincapacity); } } // 下面是內(nèi)部擴(kuò)容相關(guān)的幾個方法的代碼 private void ensurecapacityinternal(int mincapacity) { if (elementdata == defaultcapacity_empty_elementdata) { mincapacity = math.max(default_capacity, mincapacity); } ensureexplicitcapacity(mincapacity); } private void ensureexplicitcapacity(int mincapacity) { modcount++; // overflow-conscious code 考慮int型溢出 if (mincapacity - elementdata.length > 0) grow(mincapacity); } private void grow(int mincapacity) { // overflow-conscious code 考慮int型溢出 int oldcapacity = elementdata.length; int newcapacity = oldcapacity + (oldcapacity >> 1); if (newcapacity - mincapacity < 0) newcapacity = mincapacity; if (newcapacity - max_array_size > 0) newcapacity = hugecapacity(mincapacity); // mincapacity is usually close to size, so this is a win: elementdata = arrays.copyof(elementdata, newcapacity); } private static int hugecapacity(int mincapacity) { if (mincapacity < 0) // overflow int型溢出，直接報錯 throw new outofmemoryerror(); return (mincapacity > max_array_size) ? integer.max_value : max_array_size; } |
下面這是1.6的相關(guān)代碼，可以對比看下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public void ensurecapacity(int mincapacity) { modcount++; int oldcapacity = elementdata.length; if (mincapacity > oldcapacity) { object olddata[] = elementdata; int newcapacity = (oldcapacity * 3)/2 + 1; if (newcapacity < mincapacity) newcapacity = mincapacity; // mincapacity is usually close to size, so this is a win: elementdata = arrays.copyof(elementdata, newcapacity); } } |
區(qū)別就是：1.6的方法只是簡單進(jìn)行了邏輯上的操作，沒有過多考慮int型溢出的問題，從1.7（上面貼的是1.8的）開始對這個進(jìn)行了完善。
先仔細(xì)看看1.6的問題，整體來說都是int型溢出的問題。
1、沒考慮入?yún)incapacity可能因?yàn)閕nt溢出變?yōu)樨?fù)數(shù)。這個方法可以外部手動調(diào)用，手動擴(kuò)容傳入負(fù)數(shù)這個肯定是應(yīng)該攔截掉的。但是自動擴(kuò)容會因?yàn)閕nt溢出產(chǎn)生負(fù)數(shù)，碰到這種情況時應(yīng)該特殊處理，而不是什么都不做，等著后面拋出一個arrayindexoutofboundsexception。
2、就是這句代碼不太好，過早溢出
int newcapacity = (oldcapacity * 3)/2 + 1;
雖然上面這行代碼和1.7開始的oldcapacity + (oldcapacity >> 1) 看上去一樣，都是相當(dāng)于1.5倍，但實(shí)際上是有區(qū)別的。兩個區(qū)別，第一個小區(qū)別是jdk1.6的那種乘除運(yùn)算的數(shù)學(xué)結(jié)果比后面一個大1比如oldcapacity=10，1.6的算法得到16，1.7開始的算法得到15，這個影響不大；第二個區(qū)別就是兩者在數(shù)字比較大是運(yùn)算結(jié)果不一樣，比如oldcapacity=10^9，這個數(shù)和integer.max_value位數(shù)一樣，用1.6的算法得到的會是錯誤的-647483647，用1.7的則是正確的1500000000，這時候明明可以1.5倍擴(kuò)容，但是jdk1.6卻用的是按需擴(kuò)容。
在計算機(jī)里面對于int型的兩個不同的數(shù)a和b，有
a-b>0 不等價于 a>b
因?yàn)椋琣-b>0會被int溢出影響，a>b不會受int溢出影響。無符號的int型中a-b>0是一定成立的；有符號的int型，負(fù)數(shù)可以看成是正數(shù)的溢出，假設(shè)a = integer.max_value + 10，b = integer.max_value - 10，很明顯a是負(fù)數(shù)，b是正數(shù)，運(yùn)行一遍a>b得到false，再運(yùn)行一遍a-b得到的是20，a-b>0得到true。因此對于int型，a>b和a-b>0在if判斷中有不同的功能，前者是純粹比較大小，正數(shù)一定大于負(fù)數(shù)；后者可以判斷溢出，正數(shù)不一定大于負(fù)數(shù)。
所以1.7版本對上面兩個問題做了修改。
1、從1.7開始將內(nèi)部擴(kuò)容和外部可以調(diào)用的擴(kuò)容方法分開了，通過源碼（上面貼的是1.8的代碼，可以看出是一樣的）可以看出：外部調(diào)用的手動擴(kuò)容方法ensurecapacity要多一個判斷條件 mincapacity > minexpand，這個判斷條件攔截掉負(fù)數(shù)的mincapacity，這樣調(diào)用內(nèi)部擴(kuò)容ensurecapacityinternal方法時，mincapacity一定是正數(shù)；內(nèi)部擴(kuò)容方法直接就用mincapacity - elementdata.length > 0判斷，此條件可以檢測出int型溢出，碰到溢出最后會拋出一個oom錯誤。jdk1.7用oom，這比jdk1.6用arrayindexoutofboundsexception更好，因?yàn)榇藭r數(shù)組大小超出了虛擬機(jī)對數(shù)組的限制，虛擬機(jī)無法處理這種情況了，拋出一個error是合理的。
2、使用這行代碼
newcapacity = oldcapacity + (oldcapacity >> 1);
這行不僅僅是是用位運(yùn)算加快執(zhí)行速度，上面說了，這種做法才是對的，是真正的1.5倍。不僅僅因?yàn)槟且粋€大小的差別，更重要的是避免過早出現(xiàn)int溢出的情況，保證了內(nèi)部自動擴(kuò)容會盡量按規(guī)定的策略執(zhí)行。同時整個擴(kuò)容處理流程中多增加了幾處if判斷，對各種情況處理更加完善。
還有一個問題就是，max_array_size = integer.max_value - 8。這個是1.7開始才有的，注釋說這個是因?yàn)樵谝恍┨摂M機(jī)的數(shù)組實(shí)現(xiàn)中，會有array header這個保留部分，所以數(shù)組最大長度并不是實(shí)際的integer.max_value。這個在1.8自帶的hotspot上測試（環(huán)境win7 64位，java hotspot(tm) 64-bit server vm (build 25.111-b14, mixed mode)），準(zhǔn)確值應(yīng)該是integer.max_value -
2.比這個值大就會出現(xiàn)outofmemoryerror: requested array size exceeds vm limit。此error和hugecapacity中拋出的oom基本上差不多，這兩個跟一般的oom還是有區(qū)別的。拋出這個異常時，一般是程序有問題，此時虛擬機(jī)看看數(shù)組大小，就知道了它是不能完成這樣的內(nèi)存分配的，跟剩余的內(nèi)存空間大小沒關(guān)系。
測試下實(shí)際max_array_size（都是64bit的）
jdk1.8 integer,max_value - 2，超過這個值（實(shí)際上也只有兩個數(shù)可選，integer.max_value和integer.max_value - 1）就拋出outofmemoryerror: requested array size exceeds vm limit
jdk1.7 integer.max_value - 2
jdk1.6 integer.max_value，使用這個值能夠成功創(chuàng)建數(shù)組（使用boolean數(shù)組）
在帶初始容量的構(gòu)造方法 public arraylist(int initialcapacity) 中，并沒有判斷初始容量是否大于max_array_size。個人覺得還是判斷下好，不判斷可能在擴(kuò)容時會有點(diǎn)問題。下面給一組變量值大家試下，看下是不是真有問題。
初始數(shù)組長度 elementdata.length = integer.max_value - 5 = 2147483642；
還要繼續(xù)添加的長度 expand = integer.max_value - 2 = 2147483645；
最小容量 mincapacity = expand + elementdata.length = -9；
ensureexplicitcapacity方法中 mincapacity - elementdata.length = 2147483645 > 0，會繼續(xù)執(zhí)行g(shù)row方法；
grow方法中 newcapacity = elementdata.length + (elementdata.length >> 1) = -1073741833；
grow方法中的第一個if，newcapacity - mincapacity = -1073741824 < 0，執(zhí)行第一個if中的 newcapacity = mincapacity，newcapacity = -9；
grow方法中的第二個if，newcapacity - max_array_size = -2147483648 < 0，不執(zhí)行第二個if中的語句；
執(zhí)行最后的arrays.copyof，因?yàn)閚ewcapacity = -9 < 0，會拋出異常negativearraysizeexception。
grow方法中第二個if，如果newcapacity是負(fù)數(shù)，只有是-9到-1這幾個負(fù)數(shù)，才會不執(zhí)行hugecapacity方法而是直接執(zhí)行arrays.copyof拋出異常。如果構(gòu)造方法中攔截判斷下是否大于max_array_size，一開始的數(shù)組長度就限制在integer.max_value - 8，應(yīng)該是無法通過一個正數(shù)的expand，使得mincapacity在[-9,-1]內(nèi)。嚴(yán)格證明暫時給不出，實(shí)際運(yùn)行中由于內(nèi)存限制無法演示。
四、常用方法
arraylist提供的public方法的實(shí)現(xiàn)，基本上都有利用數(shù)組隨機(jī)訪問特性，以及system.arraycopy/arrays.copyof數(shù)組快速復(fù)制，進(jìn)行加速。
1、來自list接口中的方法
e get(int index)：這個沒啥說的。
e set(int index, e element)：這個沒啥說的。
void add(int index, e element)：這個內(nèi)部會進(jìn)行數(shù)組復(fù)制，復(fù)制原來index開始的數(shù)組到 index+1 開始的位置，因此在arraylist中間add元素是比較慢的，平均下來是o(n)的時間。沒必要時盡量不使用這個方法，而是直接使用 add(e) 添加到尾部，add(e) 平均下來只會耗費(fèi)o(1)的時間，效率高很多。
簡單畫了個圖，可以看下。
e remove(int index)：基本同上，會進(jìn)行數(shù)組復(fù)制，這是數(shù)組實(shí)現(xiàn)的list避免不了的問題。注意下實(shí)現(xiàn)中的elementdata[--size] = null; // clear to let gc do its work，這句讓list不引用元素，讓元素可以被回收（當(dāng)然，還得其他地方都不引用元素），避免集合類“假刪除”造成內(nèi)存泄漏。
remove示意圖如下。
int indexof(object o)：此方法和下面的lastindexof方法會進(jìn)行null判斷，o == null則在遍歷時使用 == 進(jìn)行比較，o != null則在遍歷時使用equals方法進(jìn)行比較，所以使用時請注意下元素的equals方法。
int lastindexof(object o)：同上。
boolean addall(int index, collection<? extends e> c)：elementdata數(shù)組中插入c.toarray()數(shù)組，使用的system.arraycopy復(fù)制進(jìn)去。
listiterator<e> listiterator(int index)：返回一個基于數(shù)組操作的listiterator，listiterator是iterator的增強(qiáng)實(shí)現(xiàn)。傳統(tǒng)的iterator只能往一個方向迭代，并且只能在迭代中進(jìn)行remove這一個寫操作；listiterator能夠雙向迭代，支持迭代時獲取下標(biāo)，并且能夠在迭代中進(jìn)行add和set操作。不過list這一系的迭代器弄得比較亂，抽象類abstractlist中有一套，幾個主要實(shí)現(xiàn)類arraylist、linkedlist、vector、copyonwritearraylist中又各自有一套。父類中那一套是通用的，各個具體的類中的那一套，一般都是優(yōu)化過的，效率會提升一些，所以不用管父類的迭代器了，那些雖然通用，但是效率不高，差不多過時了。jdk1.6的arraylist是直接使用父類abstract中的通用的那一套，效率稍微低些。
listiterator<e> listiterator()：就是new listitr(0);
list<e> sublist(int fromindex, int toindex)：返回此list的某一段的視圖，具體返回類型是java.util.arraylist$sublist這個內(nèi)部類，arraylist.sublist是復(fù)用原arraylist的elementdata數(shù)組，操作原數(shù)組也會對sublist有影響。jdk1.6中是用父類的這個方法，返回一個通用的java.util.subllist，1.7開始使用的是java.util.arraylist.sublist，直接操作arraylist的數(shù)組，效率更高。雖然重寫了一份功能幾乎一樣的代碼，但是作為一個基層的類，效率還是很重要的。
2、來自collection(iteratable)接口的方法
iterator<e> iterator()：返回一個內(nèi)部的實(shí)現(xiàn)類，從jdk1.7開始該實(shí)現(xiàn)類使用數(shù)組的特性優(yōu)化實(shí)現(xiàn)iterator的幾個方法，1.6返回的是父類abstractlist中定義的一個list接口通用的迭代器。
int size()：直接返回屬性size
boolean isempty()：size == 0
boolean contains(object o)：使用的是indexof
boolean add(e e)：尾部添加，只用考慮是否擴(kuò)容，不擴(kuò)容時的插入不用考慮數(shù)組元素移動的問題，平均下來是o(1)的時間。這里可以簡單證明下：初始a個容量，每次擴(kuò)容后是1.5倍，設(shè)為c；那么擴(kuò)容次數(shù)為x = o(logc(n))（c為底數(shù)）；擴(kuò)容移動的元素個數(shù)，等比數(shù)列求和，為o(c^x) = o(n)；不擴(kuò)容時每個元素為o(1)，不擴(kuò)容總共消耗小于o(n)；總共耗時o(n)，平均耗時o(1)。
boolean remove(object o)：移除所有“相等”的元素，此處相等和indexof中的一樣，null使用 ==，非null使用equals。移除時使用的fastremove(int index)跟remove(int index)行為一樣，因?yàn)槭莾?nèi)部使用，所以不用檢查邊界，而且返回void。
boolean containsall(collection<?> c)：繼承使用abstractcollection中的方法，使用for-each挨個檢驗(yàn)contains。對于iterable的實(shí)現(xiàn)類，for-each是用iterator實(shí)現(xiàn)的。在arraylist這種基于數(shù)組的實(shí)現(xiàn)中，傳統(tǒng)for循環(huán)比iterator要快，iterator比直接數(shù)組下標(biāo)取值要多不少步驟，在n次簡單循環(huán)這種狂飆cpu的操作中，每個步驟都是花時間的，所以iterator（for-each循環(huán)）要慢。不夠估計是此方法用的不多，在arraylist中沒有用數(shù)組的特性進(jìn)一步優(yōu)化此方法。1.7以后arraylist中其余幾個all方法都重寫了，就這個all方法還是用的父類的。
boolean addall(collection<? extends e> c)：c.toarray，數(shù)組尾部追加數(shù)組，先確保容量，然后復(fù)制要add的數(shù)組就行。
boolean removeall(collection<?> c)：可以理解為差集操作，這個和下面的retainall一起講，都是利用batchremove方法，只是判斷是否刪除一個元素時行為相反。1.8在調(diào)用batchremove進(jìn)行了null判斷，c == null會提前拋出npe，1.6的是重用父類abstractcollection中的實(shí)現(xiàn)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// 此方法就是一個簡單的數(shù)組批量刪除方法，并且刪除后剩余的元素相對順序不變，且全部往前移動 // 之所以使用try-fianlly是因?yàn)閏.contains可能會拋出異常(c == null，或者實(shí)現(xiàn)類中不允許null），導(dǎo)致arraylist沒有能更新size以及對底層數(shù)組進(jìn)行整理， // 使用finally可以保證保證這一點(diǎn)，并且與父類abstractcollection中已經(jīng)實(shí)現(xiàn)的removeall/retainall方法的行為的一致性 // 通過finally中的代碼可以看出，這些沒有進(jìn)行判斷的元素會全部保留。 private boolean batchremove(collection<?> c, boolean complement) { final object[] elementdata = this.elementdata; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementdata[r]) == complement) elementdata[w++] = elementdata[r]; } finally { // preserve behavioral compatibility with abstractcollection, // even if c.contains() throws. if (r != size) { system.arraycopy(elementdata, r, elementdata, w, size - r); w += size - r; } if (w != size) { // clear to let gc do its work for (int i = w; i < size; i++) elementdata[i] = null; modcount += size - w; size = w; modified = true; } } return modified; } |
boolean retainall(collection<?> c)：交集操作，上面removeall已經(jīng)講了。
void clear()：for循環(huán)清空elementdata數(shù)組，并把size置為0，不改變?nèi)萘俊?br />
boolean equals(object o)：繼承使用父類abstractlist中的方法，算法和判斷兩個數(shù)組內(nèi)容是否全等一樣，就是用的是迭代器而不是傳統(tǒng)for循環(huán)，此方法用得很少，所以沒用數(shù)組特性進(jìn)一步優(yōu)化。
int hashcode()：同上，繼承使用父類abstractlist中的方法，hashcode算法也不特殊，線性結(jié)構(gòu)常用的hash = 31 * hash + e.hashcode。
object[] toarray()：直接使用arrays.copyof拷貝一份elementdata數(shù)組作為返回值，也就是數(shù)組不共享但是元素共享。
<t> t[] toarray(t[] a)：此方法說明下，覺得行為有些不太友好。
|
1
2
3
4
5
6
7
8
9
|
public <t> t[] toarray(t[] a) { if (a.length < size) // make a new array of a's runtime type, but my contents: return (t[]) arrays.copyof(elementdata, size, a.getclass()); system.arraycopy(elementdata, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } |
此方法很簡單，分3種情況處理：給定數(shù)組空間小了，新建一樣大小數(shù)組并拷貝過去（新建操作是在arrays.copyof里面完成的）；剛好相等，直接拷貝就過去完事；給定數(shù)組大了，拷貝過去后，由于只覆蓋了原數(shù)組的前面一部分，再把接下來的一個元素變?yōu)閚ull。
覺得不友好的就是給定數(shù)組大了的這種情況，因?yàn)樗鼤喔采w掉一個值，注釋中說這么做的原因是“當(dāng)調(diào)用者知道列表不包含任何空元素時，這在確定列表的長度時非常有用”，這是個坑啊。下面的demo簡單展示了這個坑。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public class testarraylist { public static void main(string[] args) { list<string> slist = arrays.aslist("0", "1", "2", "3", "4", "5", "6", "7", "8", "9"); // 推薦使用空數(shù)組 string[] s0 = {}; system.err.println("s0 = " + arrays.tostring(slist.toarray(s0))); // s0 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] // 也可以使用等長數(shù)組 string[] s10 = new string[slist.size()]; system.err.println("s10 = " + arrays.tostring(slist.toarray(s10))); // s10 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] // 除非你清楚，否則不要像下面這么做，因?yàn)閟20[10]被此方法設(shè)置為null string[] s20 = new string[20]; s20[10] = "10"; s20[11] = "11"; s20[12] = "12"; system.err.println("s20 = " + arrays.tostring(slist.toarray(s20))); // s20 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null, 11, 12, null, null, null, null, null, null, null] } } |
五、獨(dú)有的兩個方法
public void ensurecapacity(int mincapacity)：可以外部調(diào)用的手動擴(kuò)容方法，在要添加大量元素之前，預(yù)估下容量，調(diào)用這個方法手動擴(kuò)容，避免頻繁自動擴(kuò)容降低性能。
public void trimtosize()：節(jié)省空間，使得elementdata剛好容納下所有元素。
六、幾個jdk1.8新增的函數(shù)式、stream有關(guān)的方法
這里不說。集合類這部分要說，也放在以后一起說
簡單總結(jié)下，jdk1.7版本對比1.6版本，三個改動：
1、懶初始化，因此默認(rèn)構(gòu)造方法創(chuàng)建的是空數(shù)組，不再是10個大小的數(shù)組；
2、擴(kuò)容相關(guān)的完善；
3、一些方法不再直接使用父類的通用實(shí)現(xiàn)，改為利用數(shù)組特性的更有效率的實(shí)現(xiàn)。
對比著看更容易發(fā)現(xiàn)問題，也跟有收獲。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/u011392897/article/details/57105709
