ArrayList 最細(xì)致的解析筆記

ArrayList是一個(gè)類(lèi)，這個(gè)類(lèi)有一個(gè)數(shù)組參數(shù)elementData，ArrayList集合中的元素正是保存在這個(gè)數(shù)組中，它繼承了數(shù)組查詢(xún)的高性能，參考第3篇。ArrayList還封裝了很多方法，便于對(duì)數(shù)組中的數(shù)據(jù)進(jìn)行操作處理，其中就包括上一篇說(shuō)的擴(kuò)容，建議先理解第3篇數(shù)組。

擴(kuò)容原理

在eclipse中調(diào)試以下代碼，如下設(shè)置四個(gè)斷點(diǎn)，打開(kāi)調(diào)試視圖。

public 
static 
void 
main
(String[] args) {

        List 
list = 
new ArrayList();

        System.out.println(
"斷點(diǎn)1");

        
list.add(
1);

        System.out.println(
"斷點(diǎn)2");

        
list.add(
2);

        
list.add(
3);

        
list.add(
4);

        
list.add(
5);

        
list.add(
6);

        
list.add(
7);

        
list.add(
8);

        
list.add(
9);

        
list.add(
10);

        System.out.println(
"斷點(diǎn)3");

        
list.add(
11);

        System.out.println(
"斷點(diǎn)4");

    }

斷點(diǎn)1：list的數(shù)組參數(shù)elementData的值為Object[0]，表示數(shù)組初始長(zhǎng)度為0。

斷點(diǎn)2：在集合中添加了第一個(gè)元素，elementData數(shù)組長(zhǎng)度變成了10。即初始擴(kuò)容長(zhǎng)度為10。

斷點(diǎn)3：在集合中一共添加了10個(gè)元素，elementData長(zhǎng)度仍然為10，此時(shí)無(wú)需擴(kuò)容。

斷點(diǎn)4：添加第11個(gè)元素，即超出了原數(shù)組長(zhǎng)度。elementData長(zhǎng)度擴(kuò)容為15，即第二次以后的擴(kuò)容，長(zhǎng)度為原長(zhǎng)度的1.5倍。

注意看圖，elementData在斷點(diǎn)1時(shí)標(biāo)識(shí)是29，在斷點(diǎn)2和斷點(diǎn)3處的標(biāo)識(shí)都是31，而在斷點(diǎn)4時(shí)標(biāo)識(shí)46，這說(shuō)明elementData引用變量前后一共指向了三個(gè)不同的數(shù)組對(duì)象。也就是說(shuō)，elementData并沒(méi)有真正的擴(kuò)容，而是創(chuàng)建了一個(gè)容量更大的數(shù)組對(duì)象來(lái)替代之前的數(shù)組，并且復(fù)制之前的數(shù)組內(nèi)容。

元素類(lèi)型Object

第3篇講過(guò)，數(shù)組元素的長(zhǎng)度必須是一致的。而以上代碼中，我添加的都是int類(lèi)型數(shù)據(jù)。假如我添加一個(gè)long型數(shù)據(jù)，如下，也是可以的。而int（4字節(jié) ）和long（8字節(jié) ）的長(zhǎng)度是不一樣的，這是為什么？

list.add(
1);


list.add(
1l);

假如聲明時(shí)使用List，就指定了固定元素類(lèi)型。而我的代碼中并沒(méi)有使用泛型，所以它的類(lèi)型可以是任意Object，但不能是基本類(lèi)型。當(dāng)添加int元素時(shí)，會(huì)自動(dòng)轉(zhuǎn)換為Integer。當(dāng)添加long元素時(shí)，會(huì)自動(dòng)轉(zhuǎn)換為L(zhǎng)ong。因此，最終list所有的元素類(lèi)型都是引用類(lèi)型（4字節(jié)），長(zhǎng)度相同，這是實(shí)現(xiàn)數(shù)組高性能查詢(xún)所必需的。以后講其他集合的元素類(lèi)型時(shí)，也和ArrayList是一樣的原理，不再解釋。

在尾部添加

第3篇在數(shù)組中添加了5億個(gè)元素，很快就執(zhí)行完成。假如用同樣的方法在ArrayList中添加5億元素會(huì)怎么樣？

int size=
500000000;

List 
list = 
new ArrayList();


long t1 = System.currentTimeMillis();


for(
int i=
0;i<size;i++){

    
list.add(i);

}


long t2 = System.currentTimeMillis();

System.out.println(t2-t1);

運(yùn)行結(jié)果： 內(nèi)存溢出

一直運(yùn)行了n分鐘沒(méi)有結(jié)果，最終報(bào)錯(cuò)內(nèi)存溢出。因?yàn)樵谶@個(gè)過(guò)程中，會(huì)不斷的擴(kuò)容，不斷的創(chuàng)建新數(shù)組對(duì)象，最終把內(nèi)存撐爆。要解決這個(gè)問(wèn)題，可以在創(chuàng)建ArrayList時(shí)傳入一個(gè)int參數(shù)，根據(jù)參數(shù)值會(huì)直接初始一個(gè)較大的數(shù)組，就不用再頻繁的擴(kuò)容了。注意：如果初始數(shù)組太大又不使用，也會(huì)讓費(fèi)內(nèi)存空間。修改代碼，將new ArrayList()改成new ArrayList(size)

List list = new ArrayList(size);www.gendan5.com

只是這樣做還不夠，因?yàn)樯厦嬲f(shuō)了，list.add(i)實(shí)際上是創(chuàng)建了5億個(gè)對(duì)象，數(shù)據(jù)量太大內(nèi)存仍然不足。再次修改添加代碼，將list.add(i)改成list.add(1)，1會(huì)轉(zhuǎn)換成new Integer(1)，5億個(gè)new Integer(1)仍然是5億個(gè)對(duì)象。但是java對(duì)一些對(duì)象做了緩存，其中包括new Integer(0至127)，以后會(huì)講?，F(xiàn)在只需知道，i改成1后只會(huì)有一個(gè)new Integer(1)對(duì)象，而不會(huì)創(chuàng)建5億個(gè)對(duì)象。之后文章都會(huì)使用1作為集合參數(shù)，不再解釋。修改代碼如下 ，再次運(yùn)行

list.add(1);

耗時(shí)： 1080毫秒

add()方法默認(rèn)是在尾部添加數(shù)據(jù)，ArrayList的size可以幫助數(shù)組瞬間完成定位，然后直接添加，所以這樣的性能是很高的。

在指定位置添加

list.add(int index,E element)方法是在位置index處添加，如下

int size=
500000000;

List 
list = 
new ArrayList(size);


long t1 = System.currentTimeMillis();

    
for(
int i=
0;i<size;i++){

            
list.add(
0,
1);

    }


long t2 = System.currentTimeMillis();

System.out.println(t2-t1);

耗時(shí)： 無(wú)限

上圖可以看出，向指定位置0插入元素時(shí)，其后面的所有元素都要一個(gè)個(gè)的向后移動(dòng)，即每添加一個(gè)元素要移動(dòng)n次元素。雖然沒(méi)有創(chuàng)建對(duì)象，不會(huì)內(nèi)存溢出，但是時(shí)間性能實(shí)在太低。

刪除的性能

和添加同理，在尾部刪除性能很高。但在指定位置刪除也存在性能問(wèn)題，需要把后面元素一個(gè)一個(gè)的往前移。

特性

• 有序列表： 集合中的元素按照添加順序排列，先添加進(jìn)集合的排在前面，后添加的排在后面。

• 底層就是數(shù)組： 操作尾部數(shù)據(jù)時(shí)，其性能是最高的。 操作越靠前的數(shù)據(jù)，性能越低。

• 封裝了數(shù)組： 操作更簡(jiǎn)便，代碼可讀性更高。 但是也封裝了額外操作，比如安全檢查，數(shù)組是否越界等，這也帶來(lái)一些性能開(kāi)銷(xiāo)，所以ArrayList性能會(huì)比數(shù)組稍稍低那么一點(diǎn)點(diǎn)。

應(yīng)用場(chǎng)景

做普通項(xiàng)目時(shí)，對(duì)性能沒(méi)有那么嚴(yán)格的要求，如果想要快速開(kāi)發(fā)，使用封裝過(guò)的ArrayList是第一選擇。

關(guān)于從指定位置添加和刪除，是ArrayList的性能缺陷。 我們要做的是將其優(yōu)點(diǎn)發(fā)揮到其擅長(zhǎng)的場(chǎng)景，將其不擅長(zhǎng)的場(chǎng)景交給其他數(shù)據(jù)結(jié)構(gòu)來(lái)處理，揚(yáng)長(zhǎng)避短。 后續(xù)要介紹的集合都是一樣，沒(méi)有哪一種結(jié)構(gòu)是完美的，只有其最適合哪種場(chǎng)景。