ArrayList 源碼分析

收藏待读

ArrayList 源碼分析

ArrayList 是基於數組實現的,繼承 AbstractList, 實現了 List、RandomAccess、Cloneable、Serializable 接口,支持隨機訪問。

java.util public class ArrayList extends AbstractList 
    implements List, RandomAccess, Cloneable, java.io.Serializable

2. Java Doc 關鍵點:

List list = Collections.synchronizedList(new ArrayList(...));
ConcurrentModificationException

3. 成員屬性

當添加第一個元素時, elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的任何空ArrayList都將擴展為默認的capacity

private static final int DEFAULT_CAPACITY = 10; // 默認容量大小
private static final Object[] EMPTY_ELEMENTDATA = {}; // ArrayList空實例共享的一個空數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // ArrayList空實例共享的一個空數組,用於默認大小的空實例。與 EMPTY_ELEMENTDATA 分開,這樣就可以了解當添加第一個元素時需要創建多大的空間
transient Object[] elementData; // 真正存儲ArrayList中的元素的數組
private int size;   // 存儲ArrayList的大小,注意不是elementData的長度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 數組的最大長度
protected transient int modCount = 0; //AbstractList類的,表示 elementData在結構上被修改的次數,每次add或者remove它的值都會加1

4. 構造方法

// 無參構造方法,默認初始容量10
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 提供初始容量的構造方法
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);
    }
}
// 通過一個容器來初始化
public ArrayList(Collection c) {
    elementData = c.toArray(); 
    if ((size = elementData.length) != 0) { // c.toArray 返回的可能不是  Object[]
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA; // replace with empty array.
    }
}

5. 添加元素與擴容

添加元素時使用 ensureCapacityInternal() 方法來保證容量足夠, size + 1 為最少需要的空間大小,如果elementData的長度不夠時,需要使用 grow() 方法進行擴容

// 添加一個元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
// 計算最少需要的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        // 默認的空實例第一次添加元素時,使用默認的容量大小與minCapacity的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; 
    if (minCapacity - elementData.length > 0) // 需要的容量大於elementData的長度
        grow(minCapacity);  // 進行擴容
}

擴容:當新容量小於等於 MAX_ARRAY_SIZE 時,新容量的大小為 oldCapacity + (oldCapacity >> 1)minCapacity 之間的較大值 ,也就是舊容量的 1.5 倍與 minCapacity 之間的較大值

private void grow(int minCapacity) {
    int oldCapacity = elementData.length; // 原本的容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新的容量
    if (newCapacity - minCapacity  0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity  MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

最後調用 Arrays.copyOf 複製原數組,將 elementData 賦值為得到的新數組。由於數組複製代價較高,所以建議在創建 ArrayList 對象時就指定大概的容量大小,減少擴容操作的次數

public class Arrays {
    public static  T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
    public static  T[] copyOf(U[] original, int newLength, Class newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
        return copy;
    }
    //...
}

通過 addAll 添加一個集合中所有元素 時的擴容:至少需要的容量為兩個集合的長度之和,同樣是通過 ensureCapacityInternal() 來保證容量是足夠的,然後調用 System.arraycopy 將要添加的集合中的元素複製到原集合已有元素的後面

public boolean addAll(Collection 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;
}

6. 刪除元素

刪除指定下標的元素時,如果下標沒有越界,則取出下標對應的值,然後將數組中該下標後面的元素都往前挪1位,需要挪的元素數量是 size - index - 1 ,時間複雜度為 O(n),所以刪除元素的代價挺高

public E remove(int index) {
    rangeCheck(index); // 檢查下標是否在數組的長度範圍內
    modCount++;
    E oldValue = elementData(index); // 下標為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;
}
private void rangeCheck(int index) {
    if (index >= size)  
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

刪除在指定集合中的所有元素removeAll, 刪除不在指定集合中的所有元素 retainAll

這兩者都是通過 batchRemove 來批量刪除

// 刪除在指定集合中的所有元素
public boolean removeAll(Collection c) {
    Objects.requireNonNull(c);  // c 不能為null
    return batchRemove(c, false);
}
// 刪除不在指定集合中的所有元素,也就是只保留指定集合中的元素,其它的都刪除掉
public boolean retainAll(Collection c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
// 批量刪除
private boolean batchRemove(Collection c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;   // r為當前下標,w為當前需要保留的元素的數量(或者說是下一個需保留元素的下標)
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)   // 判斷元素 elementData[r] 是否需要刪除
                elementData[w++] = elementData[r];
    } finally {
        // r != size 的情況可能是 c.contains() 拋出了異常,將 r 之後的元素複製到 w 之後
        if (r != size) { 
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        }
        if (w != size) {
            // w 之後的元素設置為 null 以讓 GC 回收
            for (int i = w; i < size; i++) 
                elementData[i] = null;  
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

刪除第一個值為指定值的元素 remove(Object o) ,參數 o 可以為 null

fastRemove(int index)remove(int index) 幾乎一樣,只不過不返回被刪除的元素

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  0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

7. 遍歷

ArrayList 支持三種方式:

  • for循環下標遍歷
  • 迭代器(Iterator和ListIterator)
  • foreach 語句

迭代器 Iterator 和 ListIterator 的主要區別::

ArrayList 的迭代器 Iterator 和 ListIterator 在《 設計模式 | 迭代器模式及典型應用 》這篇文章中有過詳細介紹,這裡只做一個小結

  • ListIterator 有 add() 方法,可以向List中添加對象,而 Iterator 不能
  • ListIterator 和 Iterator 都有 hasNext() 和 next() 方法,可以實現順序向後遍歷,但是 ListIterator 有 hasPrevious() 和 previous() 方法,可以實現逆向(順序向前)遍歷。Iterator 就不可以。
  • ListIterator 可以定位當前的索引位置,nextIndex() 和 previousIndex() 可以實現。Iterator 沒有此功能。
  • 都可實現刪除對象,但是 ListIterator 可以實現對象的修改,set() 方法可以實現。Iierator 僅能遍歷,不能修改

foreach 循環:

foreach 循環涉及到一個 Consumer 接口,接收一個泛型的參數T,當調用 accept 方法時,Stream流中將對 accept 的參數做一系列的操作

public void forEach(Consumer action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;  // 記錄當前的 modCount
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

8. 序列化

ArrayList 有兩個屬性被 transient 關鍵字 修飾, transient 關鍵字 的作用:讓某些被修飾的成員屬性變量不被序列化

transient Object[] elementData;
protected transient int modCount = 0;

為什麼最為重要的數組元素要用 transient 修飾呢?

跟Java的序列化機制有關,這裡列出Java序列化機制的幾個要點:

  • 需要序列化的類必須實現java.io.Serializable接口,否則會拋出NotSerializableException異常
  • 若沒有顯示地聲明一個serialVersionUID變量,Java序列化機制會根據編譯時的class自動生成一個serialVersionUID作為序列化版本比較(驗證一致性),如果檢測到反序列化後的類的serialVersionUID和對象二進制流的serialVersionUID不同,則會拋出異常
  • Java的序列化會將一個類包含的引用中所有的成員變量保存下來(深度複製),所以裏面的引用類型必須也要實現java.io.Serializable接口
  • 當某個字段被聲明為transient後,默認序列化機制就會忽略該字段,反序列化後自動獲得0或者null值
  • 靜態成員不參與序列化
  • 每個類可以實現readObject、writeObject方法實現自己的序列化策略,即使是transient修飾的成員變量也可以手動調用ObjectOutputStream的writeInt等方法將這個成員變量序列化。
  • 任何一個readObject方法,不管是顯式的還是默認的,它都會返回一個新建的實例,這個新建的實例不同於該類初始化時創建的實例
  • 每個類可以實現private Object readResolve()方法,在調用readObject方法之後,如果存在readResolve方法則自動調用該方法,readResolve將對readObject的結果進行處理,而最終readResolve的處理結果將作為readObject的結果返回。readResolve的目的是保護性恢復對象,其最重要的應用就是保護性恢復單例、枚舉類型的對象

所以問題的答案是:ArrayList 不想用Java序列化機制的默認處理來序列化 elementData 數組,而是通過 readObject、writeObject 方法自定義序列化和反序列化策略。

問題又來了, 為什麼不用Java序列化機制的默認處理來序列化 elementData 數組呢

答案是因為效率問題,如果用默認處理來序列化的話,如果 elementData 的長度有100,但是實際只用了50,其實剩餘的50是可以不用序列化的,這樣可以提高序列化和反序列化的效率,節省空間。

現在來看 ArrayList 中自定義的序列化和反序列化策略

private static final long serialVersionUID = 8683452581122892189L;

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    int expectedModCount = modCount;
    s.defaultWriteObject(); // 默認的序列化策略,序列化其它的字段
    s.writeInt(size);   // 實際用的長度,而不是容量

    for (int i=0; i 0) {
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

9. 快速失敗(fail-fast)

modCount 用來記錄 ArrayList 結構發生變化的次數,如果一個動作前後 modCount 的值不相等,說明 ArrayList 被其它線程修改了

如果在創建迭代器之後的任何時候以任何方式修改了列表(增加、刪除、修改),除了通過迭代器自己的remove 或 add方法,迭代器將拋出 ConcurrentModificationException 異常

需要注意的是:這裡異常的拋出條件是檢測到 modCount != expectedmodCount ,如果並發場景下一個線程修改了modCount值時另一個線程又 「及時地」 修改了expectedmodCount值,則異常不會拋出。所以不能依賴於這個異常來檢測程序的正確性。

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    int expectedModCount = modCount;    // 記錄下當前的 modCount
    // 一些操作之後....
    if (modCount != expectedModCount) { // 比較現在與之前的 modCount,不相等表示在中間過程中被修改了
        throw new ConcurrentModificationException();
    }
}

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    int expectedModCount = modCount;
    // 一些操作之後....
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

public void forEach(Consumer action) {
    final int expectedModCount = modCount;
    // 一些操作之後....
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

public boolean removeIf(Predicate filter) {
    final int expectedModCount = modCount;
    // 一些操作之後....
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

public void replaceAll(UnaryOperator operator) {
    final int expectedModCount = modCount;
    // 一些操作之後....
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++; // 修改了要加一
}

public void sort(Comparator c) {
    final int expectedModCount = modCount;
    // 一些操作之後....
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

// 內部迭代器
private class Itr implements Iterator {
    public void forEachRemaining(Consumer consumer) {
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

後記

歡迎評論、轉發、分享

更多內容可訪問我的個人博客: http://laijianfeng.org

關注【小旋鋒】微信公眾號,及時接收博文推送

ArrayList 源碼分析

轉載請註明來源,歡迎對文章中的引用來源進行考證,歡迎指出任何有錯誤或不夠清晰的表達。可以在下面評論區評論,也可以郵件至 [email protected]

原文 : 小旋鋒

相關閱讀

免责声明:本文内容来源于小旋鋒,已注明原文出处和链接,文章观点不代表立场,如若侵犯到您的权益,或涉不实谣言,敬请向我们提出检举。