天天看點
傳回

深入淺出！阿裡P7架構師帶你分析ArrayList集合源碼，建議是先收藏再看！

ArrayList簡介

ArrayList 是 Java 集合架構中比較常用的資料結構了。ArrayList是可以動态增長和縮減的索引序列，内部封裝了一個動态再配置設定的Object[]數組

深入淺出！阿裡P7架構師帶你分析ArrayList集合源碼，建議是先收藏再看！

這裡我們可以看到ArrayList繼承抽象類AbstractList，實作了 List 接口，同時還實作了 RandomAccess、Cloneable、Serializable 接口，是以ArrayList 是支援快速通路、複制、序列化的。

主要成員變量 

// 底層存儲元素的數組
    transient Object[] elementData; 
    // ArrayList的實際大小
    private int size;

注意：size 才是 elementData數組中實際的元素個數，而 elementData.length 為數組的容量，表示最多可以容納多少個元素。

// ArrayList的預設初始化容量
    private static final int DEFAULT_CAPACITY = 10;

ArrayList的預設初始容量大小為 10。

// 記錄對List操作的次數
    protected transient int modCount = 0;

這個變量是定義在 AbstractList 中的，主要使用是在 Iterator，目的是防止在List在疊代的過程中被修改。

// 空的Object類型數組
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 空的Object類型數組
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

兩個空的數組有什麼差別呢？簡單來講就是第一次添加元素（使用add方法）時知道elementData是從空的構造函數還是有參構造函數被初始化的。以便确認下一步的擴容機制。

構造函數

ArrayList類共有三種構造函數：

  • 無參構造函數
  • 帶有參數為初始容量initialCapacity的構造函數
  • 帶有參數為Collection集合的構造函數

1、無參構造函數 

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

注意：雖然在源碼的注釋中說該構造函數構造一個容量大小為 10 的空的ArrayList，但實際上構造函數隻是給 elementData 指派了一個空的數組（DEFAULTCAPACITY_EMPTY_ELEMENTDATA），在第一次向ArrayList添加元素時容量才擴大至10的。

2、帶有參數為初始容量initialCapacity的構造函數 

public ArrayList(int initialCapacity) {
        // 如果initalCapacity大于0，直接建立一個長度Object數組指派為elementData；
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        }
        // 如果initalCapcity等于0，直接将空數組EMPETY_ELEMENTDATA複制給elementData
        else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        }
        // 如果initalCapcity小于于0，則抛出異常IllegalArgumentException
        else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

當 initialCapacity 為0時則是把 EMPTY_ELEMENTDATA 指派給 elementData。 當 initialCapacity 大于零時初始化一個大小為 initialCapacity 的 object 數組并指派給 elementData。

3、帶有參數為Collection集合的構造函數 

public ArrayList(Collection<? extends E> c) {
        // 将 Collection 轉化為數組并指派給elementData
        elementData = c.toArray();
        // 把elementData中元素的個數指派給size并判斷其是否為0
        if ((size = elementData.length) != 0) {
            // 如果 size 不為零，則判斷 elementData 的 class 類型是否為 Object[]，不是的話則做一次轉換。
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } 
        // 如果 size 為零，則把 EMPTY_ELEMENTDATA 指派給 elementData，相當于new ArrayList(0)。
        else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

該構造方法主要就是将Collection集合的實作類轉換為ArrayList。

主要操作方法

add方法（添加單個元素） 

public boolean add(E e) {
        // 先确認ArrayList集合容量大小
        ensureCapacityInternal(size + 1);
        // 先給elementData中size位置指派為e，然後size自增 
        elementData[size++] = e;
        return true;
    }

           
private void ensureCapacityInternal(int minCapacity) {
    // 如果elementData為預設的空數組，則給minCapacity指派為初始的預設容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // modCount自增，并确定容量大于數組的長度
    ensureExplicitCapacity(minCapacity);
    }

           
private void ensureExplicitCapacity(int minCapacity) {
    // modCount自增，修改次數加1
    modCount++;
    // 如果minCapacity超過了數組長度，則進行擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
    }

上述三個函數的調用關系很簡單，也很清楚。

  • 在add方法中，每次添加元素到ArrayList中時都會先确認下集合容量大小，然後将size位置的元素指派為e，size再進行自增。
  • 在ensureCapacityInternal方法中先對elementData進行判斷 ，如果elementData為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是10。這就是 EMPTY_ELEMENTDATA 與 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的差別所在。同時也驗證了上面的說法：使用無參構造函數時是在第一次添加元素時初始化容量為10 。
  • ensureExplicitCapacity 方法中首先對modCount 自增1，記錄操作次數，然後如果 minCapacity 大于 elementData 的長度，則對集合進行擴容。顯然當第一次添加元素時 elementData 的長度為零。那我們來看看 grow 函數。 
private void grow(int minCapacity) {
    // ArrayList的舊容量為數組長度
    int oldCapacity = elementData.length;
    // 将新容量指派為原容量的1.5倍（左移一位相當于除以二）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果此時新容量還是小于添加元素後的容量，則将新容量直接指派為添加元素後的容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果此時新容量大于數組的最大大小，則傳回上限最大的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 把舊的數組elementData拷貝到新的elementData，并将容量設定為newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

預設将list的容量擴容至原來容量的 1.5 倍。但是擴容之後也不一定适用，有可能太小，有可能太大。是以才會有下面兩個 if 判斷。如果1.5倍太小的話，則将增加元素的容量大小指派給newCapacity，如果1.5倍太大或者我們需要的容量太大，則調用hugeCapacity函數，給newCapacity賦一個合适的值。最後将原數組中的資料複制到大小為 newCapacity 的新數組中，并将新數組指派給 elementData。

private static int hugeCapacity(int minCapacity) {
        // 如果minCapacity小于0，就抛出異常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 如果此時增加元素後得minCapacity大于數組的最大長度就傳回整數最大值，否則傳回數組最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add方法（批量添加，在指定位置添加） 

public void add(int index, E element) {
    // 檢查index是否越界
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

這三個方法基本思路與上述add方法基本思路是一緻，部落客這裡就不再贅述了。

remove方法 

public E remove(int index) {
    // 檢查index是否越界，如果越界則抛出異常
    rangeCheck(index);
    // modCount自增，修改次數加一
    modCount++;
    // 擷取elementData在index位置的值
    E oldValue = elementData(index);
    // 擷取後移的位置長度
    int numMoved = size - index - 1;
    // 如果大于零，則調用System.arraycopy方法完成數組移動
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // size自減，并将elementData索引值為size的元素引用指派為空，讓GC對他進行回收
    elementData[--size] = null; 
    // 傳回index位置的值
    return oldValue;
}

當我們調用 remove(int index) 時，首先會檢查 index 是否合法，然後再判斷要删除的元素是否位于數組的最後一個位置。如果 index 不是最後一個，就再次調用 System.arraycopy() 方法拷貝數組。說白了就是将從 index + 1 開始向後所有的元素都向前挪一個位置。然後将數組的最後一個位置空，size - 1。如果 index 是最後一個元素那麼就直接将數組的最後一個位置空，size - 1即可。

public boolean remove(Object o) {
    // 如果o為空，則查找數組中為空的索引，并調用fastRemove方法進行删除，并傳回true
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    }
    // 如果o不為空，則查找數組中與該元素相等的索引，并調用fastRemove方法進行删除，并傳回true 
    else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    // 如果list中不存在則傳回false
    return false;
}

下面我們在看fastRemove方法，fastRemove方法相較于remove（int index）方法少了一步對index的判斷，因為remove（Object o）就是在數組中進行查詢一定是合法的，是以在fastRemove中沒必要對index進行判斷。

private void fastRemove(int index) {
    modCount++;
    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
}

get方法 

public E get(int index) {
        // 檢查index是否合法，是否越界
        rangeCheck(index);
        // 利用數組的特點，直接通路數組中該索引位置上的元素
        return elementData(index);
}

總結

  • ArrayList可以存放null。
  • ArrayList本質上就是一個elementData數組。
  • ArrayList差別于數組的地方在于能夠自動擴充大小，其中關鍵的方法就是gorw()方法。
  • ArrayList中removeAll(collection c)和clear()的差別就是removeAll可以删除批量指定的元素，而clear是全是删除集合中的元素。
  • ArrayList由于本質是數組，是以它在資料的查詢方面會很快，而在插入删除這些方面，性能下降很多，有移動很多資料才能達到應有的效果
  • ArrayList實作了RandomAccess，是以在周遊它的時候推薦使用for循環。

最後

歡迎關注公衆号：前程有光，領取一線大廠Java面試題總結+各知識點學習思維導+一份300頁pdf文檔的Java核心知識點總結！

網際網路後端程式員Java面試
上一篇: 利用Comparable接口實作對對象數組的排序
下一篇: 關于一些設計上的基本常識

繼續閱讀