天天看點
傳回

源碼解析java集合架構，ArrayList源碼

一、ArrayList剖析

ArrayList是List接口下的一個實作類，ArrayList是一個動态數組，底層資料結構為可以動态增長的數組，相比數組來說，ArrayList可以動态的增加删除元素，有成熟的擴容算法。

源碼解析java集合架構，ArrayList源碼

        0          1             2             3            4           ......          23           24          25      

如圖，為ArrayList資料結構，是一個記憶體連續且緊湊的數組。ArrayList通路元素時間複雜度為O(1)，插入、删除需要移動大量元素，時間複雜度為O(n)，ArrayList适合存儲及通路資料，不适合操作頻繁的資料存儲。

ArrayList非線程安全，多線程中不能使用ArrayList，可使用Vector。

二、源碼解讀

1、構造方法

1.1 無參構造方法

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

無參構造方法，裡面隻有一個指派操作，把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 指派給 elementData，我們來看看它們都是什麼：

transient Object[] elementData; // non-private to simplify nested class access
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

 elementData 是一個Object數組，用來存儲ArrayList元素，可見，ArrayList底層就是一個動态數組。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一個空數組，是以，調用無參構造方式隻是建立一個空Object數組。

1.2 有參構造方法

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

傳入初始容量參數的構造方法，參數為整形，代表初始化Object數組長度。可以看到，當參數為0時，同樣給 elementData 指派了一個空Object數組。當大于0時，建立相應長度的數組。

2、ArrayList的新增元素方法

2.1 public boolean add(E e)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

傳入需要添加的元素e，elementData[size++] = e 把元素放置數組size++位置，緊接在後面。

ensureCapacityInternal(size + 1); 為ArrayList擴容，擴容是ArrayList中尤為重要且相對複雜的部分。

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/** Default initial capacity.  */
private static final int DEFAULT_CAPACITY = 10;

calculateCapacity() 方法傳入了新增元素後的容量minCapacity，也就是size++，和目前Object數組elementData。先判斷elementData是否為空，如果為空則傳回minCapacity與DEFAULT_CAPACITY中較大者，DEFAULT_CAPACITY是ArrayList初始化最小的容量，DEFAULT_CAPACITY值為10，是以，ArrayList的容量最小為10。

再來看ensureExplicitCapacity()方法：

protected transient int modCount = 0;

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

ensureExplicitCapacity()方法傳入了minCapacity與DEFAULT_CAPACITY比較之後的值，先是做判斷，如果目前數組長度不夠，則調用grow()方法擴容，如果足夠則不擴容。

private void grow(int minCapacity) {
        // overflow-conscious code
        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);
    }

grow()方法是ArrayList真正擴容方法，oldCapacity >> 1 位移運算，相當于oldCapacity * 0.5，是以擴容後新的容量為1.5倍，每次增長0.5倍，最後使用Arrays工具類建構新的容量更大的數組。

2.2 public void add(int index, E element)

這個add()方法傳入了兩個參數，一個是所增加的元素，和新元素插入的位置索引index。

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
    elementData[index] = element;
    size++;
}

首先對index索引位置檢驗，不能超過數組長度，不能傳負數，否則抛異常。

然後以同樣的方式1.5倍擴容，再使用本地native方法System.arraycopy()把index後所有元素向後移動1，再把element元素插入到index位置，數組長度加1，相對上一個add()方法多了一個移動元素操作，很大可能需要移動大量元素，時間複雜度增加O(n)。

擴容機制小結

如果ArrayList初始化沒指定容量，則最初ArrayList為空的數組，添加元素後初始化容量為10，當容量不夠了每次增加0.5倍。

如果初始化指定容量則建立相應長度的資料，再往裡添加元素，容量不夠再每次增加0.5倍。

3、ArrayList的擷取元素方法get(index)

public E get(int index) {

    rangeCheck(index);
    return elementData(index);
}

擷取元素方法很簡單，先對索引位置檢驗，是否超出數組長度，否則抛異常outofindex。

然後直接傳回相應位置的元素，擷取操作非常簡便，時間複雜度很低，性能高。

4、ArrayList的移除元素方法remove(index)、remove(object)

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; // clear to let GC do its work

        return oldValue;
    }

方法傳回的是所移除的元素，同樣還是使用System.arraycopy()大量向前移動元素。

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

這個方法傳入的是要删除的元素值，思路是根據元素值比對到元素所在的索引位置index，再向前移動後面的元素。

可見，移除元素同樣需要移動大量的元素，時間複雜度大。

後語，ArrayList底層就是對象數組，添加和移除元需要移動大量元素，效率低。相反，查詢操作效率十分高，隻需傳回對應索引的元素。

ArrayList适合存放查詢資料，不适合有删減改動的資料。

背景技術 java集合 arraylist
上一篇: 【Java集合源碼剖析】ArrayList源碼剖析ArrayList簡介ArrayList源碼剖析幾點總結
下一篇: 集合源碼分析之一：ArrayList源碼解析（JDK8）

繼續閱讀