ArrayList源碼淺析

前言

ArrayList

作為我們開發中最常用的集合，作為極高頻次使用的類，我們不妨閱讀源碼一談究竟。

介紹

ArrayList

繼承關系如下

AaaryList

主要實作了

List

接口，同時标記為可以序列化

Serializable

、可複制

CloneAble

、支援随機通路

RandomAccess

。

幾個重要的成員變量

/**
     * 預設容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空執行個體的共享空數組執行個體。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 用于預設大小的空執行個體的共享空數組執行個體。我們将其與空元素資料區分開來，以了解添加第一個元素時要膨脹多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存儲ArrayList元素的數組緩沖區。ArrayList的容量是此數組緩沖區的長度。
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList的大小（它包含的元素數）。
     */
    private int size;
           

資料結構

ArrayList

底層就是一個數組，數組會随着資料的增長而擴容，數組的擴容就是建立一個新的容量大的數組，然後把舊數組上面的資料複制進新數組。關于擴容，後面會詳細講解。

因為是數組，是以支援随機通路，且有序。

常用方法

ArrayList()

無參構造方法

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

初始化數組為一個空數組。與空元素資料區分開來，以了解添加第一個元素時要膨脹多少。

add(E e) 添加元素

将指定的元素追加到此清單的末尾

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) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

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

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

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

當添加元素，會先檢查是否超出容量，如果超出，則需要擴容。

當第一次添加元素時，

size

為預設值0，會計算出一個最小容量

minCapacity

，如果是無參構造建立的，則會取預設的容量

10

，

Math.max(DEFAULT_CAPACITY, minCapacity)，這裡傳入的minCapacity為0，是以擷取更大的10。

如果計算出的最小容量大于原容量

minCapacity - elementData.length > 0

，則會進行擴容。

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

擴容算法是，擴為老容量的1.5倍，如果擴容後的容量仍然小于需要的最小容量

minCapacity

，則新的容量就取最小容量。

如果擴容後的大小超過最大容量，則會進行下面的操作

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }           

計算出擴容後的容量後，進行擴容，也就是，建立一個數組初始化為新容量，然後複制舊元素到新數組。

elementData = Arrays.copyOf(elementData, newCapacity);

public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }           

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> 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;
    }           

為什麼不能在forEach裡面修改清單

ArrayList

在新增、删除元素都會執行

modCount++

modCount

定義在

ArrayList

的父類

AbstractList

/**
     * 此清單在結構上被修改的次數。結構修改是指那些改變清單大小的修改，或者以某種方式幹擾清單，使得正在進行的疊代可能産生不正确的結果。 疊代器和清單疊代器方法傳回的疊代器和清單疊代器實作使用此字段。如果此字段的值意外更改，疊代器（或清單疊代器）将抛出ConcurrentModificationException以響應下一個、删除、上一個、設定或添加操作。這提供了快速失效行為，而不是在疊代過程中面對并發修改時的非确定性行為。 子類使用此字段是可選的。如果子類希望提供fail fast疊代器（和清單疊代器），那麼它隻需在add（int，E）和remove（int）方法（以及它重寫的任何其他方法，這些方法會導緻清單的結構修改）中增加該字段。對add（int，E）或remove（int）的單個調用隻能向該字段添加一個，否則疊代器（和清單疊代器）将抛出虛假的ConcurrentModificationException。如果實作不希望提供故障快速疊代器，則可以忽略此字段。
     */
    protected transient int modCount = 0;           

然後我們來看下

forEach

的實作。

@Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = 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();
        }
    }           

在周遊前，會暫存modCount值，每次循環都判斷下modCount是否有更改，若更改了，裡面跳出循環，随後抛出異常。