ArrayList 最細致的解析筆記

ArrayList是一個類，這個類有一個數組參數elementData，ArrayList集合中的元素正是保存在這個數組中，它繼承了數組查詢的高性能，參考第3篇。ArrayList還封裝了很多方法，便于對數組中的數據進行操作處理，其中就包括上一篇說的擴容，建議先理解第3篇數組。

擴容原理

在eclipse中調試以下代碼，如下設置四個斷點，打開調試視圖。

public 
static 
void 
main
(String[] args) {

        List 
list = 
new ArrayList();

        System.out.println(
"斷點1");

        
list.add(
1);

        System.out.println(
"斷點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(
"斷點3");

        
list.add(
11);

        System.out.println(
"斷點4");

    }

斷點1：list的數組參數elementData的值為Object[0]，表示數組初始長度為0。

斷點2：在集合中添加了第一個元素，elementData數組長度變成了10。即初始擴容長度為10。

斷點3：在集合中一共添加了10個元素，elementData長度仍然為10，此時無需擴容。

斷點4：添加第11個元素，即超出了原數組長度。elementData長度擴容為15，即第二次以后的擴容，長度為原長度的1.5倍。

注意看圖，elementData在斷點1時標識是29，在斷點2和斷點3處的標識都是31，而在斷點4時標識46，這說明elementData引用變量前后一共指向了三個不同的數組對象。也就是說，elementData并沒有真正的擴容，而是創建了一個容量更大的數組對象來替代之前的數組，并且復制之前的數組內容。

元素類型Object

第3篇講過，數組元素的長度必須是一致的。而以上代碼中，我添加的都是int類型數據。假如我添加一個long型數據，如下，也是可以的。而int（4字節 ）和long（8字節 ）的長度是不一樣的，這是為什么？

list.add(
1);


list.add(
1l);

假如聲明時使用List，就指定了固定元素類型。而我的代碼中并沒有使用泛型，所以它的類型可以是任意Object，但不能是基本類型。當添加int元素時，會自動轉換為Integer。當添加long元素時，會自動轉換為Long。因此，最終list所有的元素類型都是引用類型（4字節），長度相同，這是實現數組高性能查詢所必需的。以后講其他集合的元素類型時，也和ArrayList是一樣的原理，不再解釋。

在尾部添加

第3篇在數組中添加了5億個元素，很快就執行完成。假如用同樣的方法在ArrayList中添加5億元素會怎么樣？

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);

運行結果： 內存溢出

一直運行了n分鐘沒有結果，最終報錯內存溢出。因為在這個過程中，會不斷的擴容，不斷的創建新數組對象，最終把內存撐爆。要解決這個問題，可以在創建ArrayList時傳入一個int參數，根據參數值會直接初始一個較大的數組，就不用再頻繁的擴容了。注意：如果初始數組太大又不使用，也會讓費內存空間。修改代碼，將new ArrayList()改成new ArrayList(size)

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

只是這樣做還不夠，因為上面說了，list.add(i)實際上是創建了5億個對象，數據量太大內存仍然不足。再次修改添加代碼，將list.add(i)改成list.add(1)，1會轉換成new Integer(1)，5億個new Integer(1)仍然是5億個對象。但是java對一些對象做了緩存，其中包括new Integer(0至127)，以后會講。現在只需知道，i改成1后只會有一個new Integer(1)對象，而不會創建5億個對象。之后文章都會使用1作為集合參數，不再解釋。修改代碼如下 ，再次運行

list.add(1);

耗時： 1080毫秒

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

在指定位置添加

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);

耗時： 無限

上圖可以看出，向指定位置0插入元素時，其后面的所有元素都要一個個的向后移動，即每添加一個元素要移動n次元素。雖然沒有創建對象，不會內存溢出，但是時間性能實在太低。

刪除的性能

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

特性

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

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

• 封裝了數組： 操作更簡便，代碼可讀性更高。 但是也封裝了額外操作，比如安全檢查，數組是否越界等，這也帶來一些性能開銷，所以ArrayList性能會比數組稍稍低那么一點點。

應用場景

做普通項目時，對性能沒有那么嚴格的要求，如果想要快速開發，使用封裝過的ArrayList是第一選擇。

關于從指定位置添加和刪除，是ArrayList的性能缺陷。 我們要做的是將其優點發揮到其擅長的場景，將其不擅長的場景交給其他數據結構來處理，揚長避短。 后續要介紹的集合都是一樣，沒有哪一種結構是完美的，只有其最適合哪種場景。