[詳細分析]Java-ArrayList源碼全解析

// 序列化版本UID
private static final long
        serialVersionUID = 8683452581122892189L;

/**
 * 默認的初始容量
 */
private static final int
        DEFAULT_CAPACITY = 10;

/**
 * 用于空實例的共享空數組實例
 * new ArrayList(0);
 */
private static final Object[]
        EMPTY_ELEMENTDATA = {};

/**
 * 用于提供默認大小的實例的共享空數組實例
 * new ArrayList();
 */
private static final Object[]
        DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

/**
 * ArrayList中元素的數量
 */
private int size;

小朋友，你四否有很多問號？

為什么空實例默認數組有的時候是EMPTY_ELEMENTDATA，而又有的時候是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
為什么elementData要被transient修飾
為什么elementData沒有被private修飾？難道正如注釋所寫的non-private to simplify nested class access

帶著問題，我們繼續往下看。

構造方法

帶初始容量的構造方法

/**
 * 帶一個初始容量參數的構造方法
 *
 * @param  initialCapacity  初始容量
 * @throws  如果初始容量非法就拋出
 *          IllegalArgumentException
 */
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);
    }
}

如果initialCapacity < 0，就創建一個新的長度是initialCapacity的數組
如果initialCapacity == 0，就使用EMPTY_ELEMENTDATA
其他情況，initialCapacity不合法，拋出異常

無參構造方法

/**
 * 無參構造方法 將elementData 賦值為
 *   DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 */
public ArrayList() {
    this.elementData =
            DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

帶一個集合參數的構造方法

/**
 * 帶一個集合參數的構造方法
 *
 * @param c 集合，代表集合中的元素會被放到list中
 * @throws 如果集合為空，拋出NullPointerException
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    // 如果 size != 0
    if ((size = elementData.length) != 0) {
        // c.toArray 可能不正確的，不返回 Object[]
        // https://bugs.openjdk.java.net/browse/JDK-6260652
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(
                    elementData, size, Object[].class);
    } else {
        // size == 0
        // 將EMPTY_ELEMENTDATA 賦值給 elementData
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

使用將集合轉換為數組的方法
為了防止c.toArray()方法不正確的執行，導致沒有返回Object[]，特殊做了處理
如果數組大小等于0，則使用 EMPTY_ELEMENTDATA

那么問題來了，什么情況下c.toArray()會不返回Object[]呢？

public static void main(String[] args) {
    List<String> list = new ArrayList<>(Arrays.asList("list"));
    // class java.util.ArrayList
    System.out.println(list.getClass());

    Object[] listArray = list.toArray();
    // class [Ljava.lang.Object;
    System.out.println(listArray.getClass());
    listArray[0] = new Object();

    System.out.println();

    List<String> asList = Arrays.asList("asList");
    // class java.util.Arrays$ArrayList
    System.out.println(asList.getClass());

    Object[] asListArray = asList.toArray();
    // class [Ljava.lang.String;
    System.out.println(asListArray.getClass());
    // java.lang.ArrayStoreException
    asListArray[0] = new Object();
}

我們通過這個例子可以看出來，java.util.ArrayList.toArray()方法會返回Object[]沒有問題。而java.util.Arrays的私有內部類ArrayList的toArray()方法可能不返回Object[]。

為什么會這樣？

我們看ArrayList的toArray()方法源碼：

public Object[] toArray() {
    // ArrayLisy中 elementData是這樣定義的
    // transient Object[] elementData;
    return Arrays.copyOf(elementData, size);
}

使用了Arrays.copyOf()方法：

public static <T> T[] copyOf(T[] original, int newLength) {
    // original.getClass() 是 class [Ljava.lang.Object
    return (T[]) copyOf(original, newLength, original.getClass());
}

copyOf()的具體實現：

public static <T,U> T[] copyOf(U[] original, 
          int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    /**
     * 如果newType是Object[] copy 數組 類型就是 Object 
     * 否則就是 newType 類型
     */
    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;
}

我們知道ArrayList中elementData就是Object[]類型，所以ArrayList的toArray()方法必然會返回Object[]。

我們再看一下java.util.Arrays的內部ArrayList源碼（截取的部分源碼）：

private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable {

    // 存儲元素的數組
    private final E[] a;

    ArrayList(E[] array) {
        // 直接把接收的數組 賦值 給 a
        a = Objects.requireNonNull(array);
    }

    /**
     * obj 為空拋出異常
     * 不為空 返回 obj
     */
    public static <T> T requireNonNull(T obj) {
        if (obj == null)
            throw new NullPointerException();
        return obj;
    }

    @Override
    public Object[] toArray() {
        // 返回 a 的克隆對象
        return a.clone();
    }

}

這是Arrays.asList()方法源碼

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

不難看出來java.util.Arrays的內部ArrayList的toArray()方法，是構造方法接收什么類型的數組，就返回什么類型的數組。

所以，在我們上面的例子中，實際上返回的是String類型的數組，再將其中的元素賦值成Object類型的，自然報錯。

我們還是繼續看ArrayList吧…

插入方法

在列表最后添加指定元素

/**
 * 在列表最后添加指定元素
 *
 * @param e 要添加的指定元素
 * @return true
 */
public boolean add(E e) {
    // 增加 modCount ！！
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}

在父類AbstractList上，定義了modCount 屬性，用于記錄數組修改的次數。

在指定位置添加指定元素

/**
 * 在指定位置添加指定元素
 * 如果指定位置已經有元素，就將該元素和隨后的元素移動到右面一位
 *
 * @param index 待插入元素的下標
 * @param element 待插入的元素
 * @throws 可能拋出 IndexOutOfBoundsException
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);


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

插入方法調用的其他私有方法

/**
 * 計算容量
 */
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
 * 一些虛擬機在數組中預留一些header words
 * 如果嘗試分配更大的size，可能導致OutOfMemoryError
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 增加容量，至少保證比minCapacity大
 * @param minCapacity 期望的最小容量
 */
private void grow(int minCapacity) {
    // 有可能溢出的代碼
    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);
}

/**
 * 最大容量返回 Integer.MAX_VALUE
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

通常情況新容量是原來容量的1.5倍
如果原容量的1.5倍比minCapacity小，那么就擴容到minCapacity
特殊情況擴容到Integer.MAX_VALUE

看完構造方法、添加方法、擴容方法之后，上文第1個問題終于有了答案。原來，new ArrayList()會將elementData 賦值為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，new ArrayList(0)會將elementData 賦值為 EMPTY_ELEMENTDATA，EMPTY_ELEMENTDATA添加元素會擴容到容量為1，而DEFAULTCAPACITY_EMPTY_ELEMENTDATA擴容之后容量為10。

通過反射我們可以驗證這一想法。如下：

public static void main(String[] args) {
    printDefaultCapacityList();
    printEmptyCapacityList();
}

public static void printDefaultCapacityList() {
    ArrayList defaultCapacity = new ArrayList();
    System.out.println(
            "default 初始化長度：" + getCapacity(defaultCapacity));

    defaultCapacity.add(1);
    System.out.println(
            "default add 之后 長度：" + getCapacity(defaultCapacity));
}

public static void printEmptyCapacityList() {
    ArrayList emptyCapacity = new ArrayList(0);
    System.out.println(
            "empty 初始化長度：" + getCapacity(emptyCapacity));

    emptyCapacity.add(1);
    System.out.println(
            "empty add 之后 長度：" + getCapacity(emptyCapacity));
}

public static int getCapacity(ArrayList<?> arrayList) {
    Class<ArrayList> arrayListClass = ArrayList.class;
    try {
        // 獲取 elementData 字段
        Field field = arrayListClass.getDeclaredField("elementData");
        // 開啟訪問權限
        field.setAccessible(true);
        // 把示例傳入get，獲取實例字段elementData的值
        Object[] objects = (Object[]) field.get(arrayList);
        //返回當前ArrayList實例的容量值
        return objects.length;
    } catch (Exception e) {
        e.printStackTrace();
        return -1;
    }
}

移除方法

移除指定下標元素方法

/**
 * 移除列表中指定下標位置的元素
 * 將所有的后續元素，向左移動
 *
 * @param 要移除的指定下標
 * @return 返回被移除的元素
 * @throws 下標越界會拋出IndexOutOfBoundsException
 */
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);
    // 將引用置空，讓GC回收
    elementData[--size] = null;

    return oldValue;
}

移除指定元素方法

/**
 * 移除第一個在列表中出現的指定元素
 * 如果存在，移除返回true
 * 否則，返回false
 *
 * @param o 指定元素
 */
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;
}

移除方法名字、參數的個數都一樣，使用的時候要注意。

私有移除方法

/*
 * 私有的 移除 方法 跳過邊界檢查且不返回移除的元素
 */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 將引用置空，讓GC回收
    elementData[--size] = null;
}

查找方法

查找指定元素的所在位置

/**
 * 返回指定元素第一次出現的下標
 * 如果不存在該元素，返回 -1
 * 如果 o ==null 會特殊處理
 */
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

查找指定位置的元素

/**
 * 返回指定位置的元素
 *
 * @param  index 指定元素的位置 
 * @throws index越界會拋出IndexOutOfBoundsException
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

該方法直接返回elementData數組指定下標的元素，效率還是很高的。所以ArrayList，for循環遍歷效率也是很高的。

序列化方法

/**
 * 將ArrayLisy實例的狀態保存到一個流里面
 */
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // 按照順序寫入所有的元素
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

反序列化方法

/**
 * 根據一個流(參數)重新生成一個ArrayList
 */
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt();

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

看完序列化，反序列化方法，我們終于又能回答開篇的第二個問題了。elementData之所以用transient修飾，是因為JDK不想將整個elementData都序列化或者反序列化，而只是將size和實際存儲的元素序列化或反序列化，從而節省空間和時間。

創建子數組

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

我們看一下簡短版的SubList：

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }

    // 省略代碼...
}

SubList的set()方法，是直接修改ArrayList中elementData數組的，使用中應該注意
SubList是沒有實現Serializable接口的，是不能序列化的

迭代器

創建迭代器方法

public Iterator<E> iterator() {
    return new Itr();
}

Itr屬性

// 下一個要返回的元素的下標
int cursor;
// 最后一個要返回元素的下標 沒有元素返回 -1
int lastRet = -1;
// 期望的 modCount
int expectedModCount = modCount;

Itr的hasNext() 方法

public boolean hasNext() {
    return cursor != size;
}

Itr的next()方法

public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

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

在迭代的時候，會校驗modCount是否等于expectedModCount，不等于就會拋出著名的ConcurrentModificationException異常。什么時候會拋出ConcurrentModificationException？

public static void main(String[] args) {
    ArrayList arrayList = new ArrayList();
    for (int i = 0; i < 10; i++) {
        arrayList.add(i);
    }
    remove(arrayList);
    System.out.println(arrayList);
}

public static void remove(ArrayList<Integer> list) {
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        Integer number = iterator.next();
        if (number % 2 == 0) {
            // 拋出ConcurrentModificationException異常
            list.remove(number);
        }
    }
}

那怎么寫才能不拋出ConcurrentModificationException？很簡單，將list.remove(number);換成iterator.remove();即可。why？請看Itr的remove()源碼…

Itr的remove()方法

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        // 移除之后將modCount 重新賦值給 expectedModCount
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

原因就是因為Itr的remove()方法，移除之后將modCount重新賦值給 expectedModCount。這就是源碼，不管單線程還是多線程，只要違反了規則，就會拋異常。

源碼看的差不多了，開篇的問題卻還剩一個！到底為什么elementData沒有用private修飾呢？

我們知道的，private修飾的變量，內部類也是可以訪問到的。難道注釋中non-private to simplify nested class access的這句話有毛病？

當我們看表面看不到什么東西的時候，不妨看一下底層。

測試類代碼：

一頓javac、javap之后（使用JDK8）：

再一頓javac、javap之后（使用JDK11）：

雖然字節碼指令我還看不太懂，但是我能品出來，注釋是沒毛病的，private修飾的確會影響內部類的訪問。

ArrayList類注釋翻譯

類注釋還是要看的，能給我們一個整體的了解這個類。我將ArrayList的類注釋大概翻譯整理了一下：

ArrayList是實現List接口的可自動擴容的數組。實現了所有的List操作，允許所有的元素，包括null值。
ArrayList大致和Vector相同，除了ArrayList是非同步的。
size isEmpty get set iterator 和 listIterator 方法時間復雜度是O(1)，常量時間。其他方法是O(n)，線性時間。
每一個ArrayList實例都有一個capacity（容量）。capacity是用于存儲列表中元素的數組的大小。capacity至少和列表的大小一樣大。
如果多個線程同時訪問ArrayList的實例，并且至少一個線程會修改，必須在外部保證ArrayList的同步。修改包括添加刪除擴容等操作，僅僅設置值不包括。這種場景可以用其他的一些封裝好的同步的list。如果不存在這樣的Object，ArrayList應該用Collections.synchronizedList包裝起來最好在創建的時候就包裝起來，來保證同步訪問。
iterator()和listIterator(int)方法是fail-fast的，如果在迭代器創建之后，列表進行結構化修改，迭代器會拋出ConcurrentModificationException。
面對并發修改，迭代器快速失敗、清理，而不是在未知的時間不確定的情況下冒險。請注意，快速失敗行為不能被保證。通常來講，不能同步進行的并發修改幾乎不可能做任何保證。因此，寫依賴這個異常的程序的代碼是錯誤的，快速失敗行為應該僅僅用于防止bug。

總結

ArrayList底層的數據結構是數組
ArrayList可以自動擴容，不傳初始容量或者初始容量是0，都會初始化一個空數組，但是如果添加元素，會自動進行擴容，所以，創建ArrayList的時候，給初始容量是必要的
Arrays.asList()方法返回的是的Arrays內部的ArrayList，用的時候需要注意
subList()返回內部類，不能序列化，和ArrayList共用同一個數組
迭代刪除要用，迭代器的remove方法，或者可以用倒序的for循環
ArrayList重寫了序列化、反序列化方法，避免序列化、反序列化全部數組，浪費時間和空間
elementData不使用private修飾，可以簡化內部類的訪問

本文鏈接：https://blog.csdn.net/qq_38905818/article/details/105901242

智能推薦

CMA 詳細分析

關于CMA的config @LINUX/android/kernel/arch/arm/configs/msm8909_defconfig CONFIG_CMA=y 已經打開 # CONFIG_CMA_DEBUG is not set # # Default contiguous memory area size: # CONFIG_CMA_SIZE_MBYTES=8 //兩個配對定義 CONFI...

MapReduce詳細分析

一、MapReduce概述 1、定義 MapReduce核心功能是將用戶編寫的業務邏輯代碼和自帶默認組件整合成一個完整的分布式運算程序,并發運行在一個Hadoop集群上。 2、MR進程一個完整的MapR educe程序在分布式運行時有三類實例進程: **Mr AppMaster:**負責整個程序的過程調度及狀態協調。 MapTask:負責Map階段的整個數據處理流程。 ReduceTask:負...

HTML中常用操作關于：頁面跳轉，空格

1.頁面跳轉 2.空格的代替符...

freemarker + ItextRender 根據模板生成PDF文件

1. 制作模板 2. 獲取模板，并將所獲取的數據加載生成html文件 2. 生成PDF文件其中由兩個地方需要注意，都是關于獲取文件路徑的問題，由于項目部署的時候是打包成jar包形式，所以在開發過程中時直接安照傳統的獲取方法沒有一點文件，但是當打包后部署，總是出錯。于是參考網上文章，先將文件讀出來到項目的臨時目錄下，然后再按正常方式加載該臨時文件；還有一個問題至今沒有解決，就是關于生成PDF文件...

電腦空間不夠了？教你一個小秒招快速清理 Docker 占用的磁盤空間！

Docker 很占用空間，每當我們運行容器、拉取鏡像、部署應用、構建自己的鏡像時，我們的磁盤空間會被大量占用。如果你也被這個問題所困擾，咱們就一起看一下 Docker 是如何使用磁盤空間的，以及如何回收。 docker 占用的空間可以通過下面的命令查看： TYPE 列出了docker 使用磁盤的 4 種類型： Images：所有鏡像占用的空間，包括拉取下來的鏡像，和本地構建的。 Con...