詳解Java集合框架ArrayList原始碼剖析（圖）

總體介紹

ArrayList#實作了List接口，是順序容器，也就是元素存放的資料與放進去的順序相同，允許放入null元素，底層透過陣列實作。除該類別未實現同步外，其餘跟Vector大致相同。每個ArrayList都有一個容量（capacity），表示底層陣列的實際大小，容器內儲存元素的數量不能多於目前容量。當容器中新增元素時，如果容量不足，容器會自動增加底層陣列的大小。前面已經提過，Java泛型只是編譯器提供的語法糖，所以這裡的陣列是一個Object數組，以便能夠容納任何類型的物件。

size(), isEmpty(), get(), set()方法皆能在常數時間內完成，add()方法的時間開銷跟插入位置有關，addAll()方法的時間開銷跟添加元素的數量成正比。其餘方法大都是線性時間。

為追求效率，ArrayList沒有實現同步（synchronized），如果需要多個線程並發訪問，用戶可以手動同步，也可使用Vector替代。

方法剖析

set()

既然底層是一個陣列ArrayList的set()方法也就變得非常簡單，直接對數組的指定位置賦值即可。

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
    return oldValue;
}

get()

get()方法同樣很簡單，唯一要注意的是由於底層陣列是Object[]，得到元素後需要進行型別轉換。

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

add()

跟C++ 的vector不同，ArrayList沒有bush_back()方法，對應的方法是add(E e)，ArrayList也沒有insert()方法，對應的方法是add(int index, E e)。這兩種方法都是在容器中新增元素，這可能會導致capacity不足，因此在新增元素之前，都需要進行剩餘空間檢查，如果需要則自動擴容。擴容操作最終是透過grow()方法完成的。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的3倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}

由於Java GC自動管理了內存，這裡也不需要考慮來源數組釋放的問題。

空間的問題解決後，插入過程就顯得非常簡單。

add(int index, E e)需要先對元素進行移動，然後完成插入操作，也就表示該方法有著線性的時間複雜度。

addAll()

addAll()方法能夠一次加入多個元素，根據位置不同也有兩個把本，一個是在末尾添加的 addAll(Collection <a href="http://www.php.cn/wiki/166.html" target="_blank">extends</a> E> c)方法，一個是從指定位置開始插入的addAll(int index, Collection extends E> c)方法。跟add()方法類似，在插入之前也需要進行空間檢查，如果需要則自動擴容；如果從指定位置插入，也會存在移動元素的情況。
addAll()的時間複雜度不僅跟插入元素的多寡有關，也跟插入的位置相關。

remove()

remove()方法也有兩個版本，一個是remove(int index)刪除指定位置的元素，另一個是remove(Object o)刪除第一個滿足o.equals(elementData[index])的元素。刪除操作是add()操作的逆過程，需要將刪除點之後的元素向前移動一個位置。需要注意的是為了讓GC起作用，必須明確的為最後一個位置賦null值。

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //清除该位置的引用，让GC起作用
    return oldValue;
}

以上是詳解Java集合框架ArrayList原始碼剖析（圖）的詳細內容。更多資訊請關注PHP中文網其他相關文章！