簡介

ArrayList是基于數組實作的一種清單。

ArrayList繼承體系如下：

圖一：ArrayList繼承體系

ArrayList實作了List, RandomAccess, Cloneable, java.io.Serializable等接口。
ArrayList實作了List，提供了基礎的添加、删除、周遊等操作。
ArrayList實作了RandomAccess，提供了随機通路的能力。
ArrayList實作了Cloneable，可以被克隆。
ArrayList實作了Serializable，可以被序列化。

源碼分析

屬性

首先看看ArrayList的屬性。

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

    /**
     * 空數組，如果傳入的容量為0時使用
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     *空數組，傳傳入容量時使用，添加第一個元素的時候會重新初始為預設容量大小
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *存儲資料元素的數組
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList的大小（包含資料元素的個數）
     */
    private int size;

構造方法

無參構造方法

/**
     * 建立一個初始容量為10的空清單
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

指定初始容量的構造方法

/**
  * 建立一個指定容量的list
  */
    public ArrayList(int initialCapacity) {
       // 如果傳入的初始容量大于0，就建立一個數組存儲元素
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 如果傳入的初始容量等于0，使用空數組EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

從其它集合構造

/**
   * 把傳入集合的元素初始化到ArrayList中
   */
    public ArrayList(Collection<? extends E> c) {
       //把集合轉為數組
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //  檢查c.toArray()傳回的是不是Object[]類型，如果不是，重新拷貝成Object[].class類型
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果是空集合，則初始化為空數組EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

add(E e)

添加元素到末尾，平均時間複雜度為O(1)。

/**
    * 在末尾添加元素
    */
    public boolean add(E e) {
         // 檢查是否需要擴容
        ensureCapacityInternal(size + 1);  
        // 把元素插入到末尾
        elementData[size++] = e;
        return true;
    }

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

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果是空數組DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化為預設大小10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
       // 修改次數 +1，用于 fail-fast 處理
        modCount++;

        // 如果 minCapacity 大于 elementData 的長度，則進行擴容處理
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    } 
    
    /**
    *  擴容
    */
     private void grow(int minCapacity) {
        // 有整形溢出風險的代碼
        int oldCapacity = elementData.length;
        //新容量=舊容量+（舊容量右移1位（除以2））,新容量為原來的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新容量發現比需要的容量還小，則以需要的容量為準
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果新容量已經超過最大容量了，則使用最大容量   
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //數組拷貝
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

這裡我們稍微看一下Arrays.copyOf的源碼：

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

最終調用的是System.arraycopy方法，這是一個Native方法：

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

關于數組拷貝，谷歌了一下，說法不一，有說是深拷貝的，有說是淺拷貝的。暫時先放下，未來有機會再研究。

add(int index, E element)

add(int index, E element)在特定位置插入元素，時間複雜度為O(n)。

public void add(int index, E element) {
        // 檢查是否越界
        rangeCheckForAdd(index);
        //檢查是否需要擴容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
         将 elementData 中位置為 index 位置及其後面的元素都向後移動一個下标（底層是 native 方法，使用 cpp 直接操作記憶體。）
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将元素插入到index的位置                 
        elementData[index] = element;
         大小增1
        size++;
    }

addAll

addAll用于批量添加。

public boolean addAll(Collection<? extends E> c) {
       // 集合轉化成數組
        Object[] a = c.toArray();
        
        int numNew = a.length;
        //檢查是否需要擴容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //将集合内的元素複制到 elementData 中，覆寫 [size, size+numNew) 的元素
        System.arraycopy(a, 0, elementData, size, numNew);
        //數組大小增加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)
           // 将 elementData 中位置為 index 及其以後的元素都向後移動 numNew 個位置
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        // 将集合内的元素複制到 elementData 中，覆寫 [index, index+numNew) 的元素                      
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

get(int index)

擷取指定位置元素，時間複雜度為O(1)。

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

remove(int index)

删除指定索引位置的元素，時間複雜度為O(n)。

public E remove(int index) {
       //檢查下标是否越界
        rangeCheck(index);

        modCount++;
        //擷取指定索引處元素
        E oldValue = elementData(index);
         如果index不是最後一位，則将index之後的元素往前挪一位
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将最後一個元素删除，幫助GC                     
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

remove(Object o)

删除指定元素，時間複雜度為O(n²)。

public boolean remove(Object o) {
       //元素為null
        if (o == null) {
           //周遊數組
            for (int index = 0; index < size; index++)
               //快速删除所有為null的元素
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            //元素不為null，周遊數組
            for (int index = 0; index < size; index++)
               //找到對應元素，快讀删除
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    //和remove(int index)基本相同，少了檢查越界的方法，無傳回值
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        // 如果index不是最後一位，則将index之後的元素往前挪一位
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最後一個元素删除，幫助GC                     
        elementData[--size] = null; // clear to let GC do its work
    }

removeAll

用于批量删除元素。

//批量删除 ArrayList 和集合 c 都存在的元素
    public boolean removeAll(Collection<?> c) {
       //非空校驗
        Objects.requireNonNull(c);
       //批量删除 
        return batchRemove(c, false);
    }

    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                 // 把需要保留的元素前置
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // 跟 fastRemove(int index) 裡面的操作類似，防止記憶體洩漏
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

set

用于更改特定下标的值，時間複雜度為O(1)。

public E set(int index, E element) {
        
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

序列化

注意觀察，ArrayList 有兩個屬性被 transient 關鍵字修飾，transient 關鍵字的作用：讓某些被修飾的成員屬性變量不被序列化

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

為什麼最重要的元素數組要被transient 修飾呢？

因為ArrayList 并沒有用Java序列化機制的預設處理來序列化 elementData 數組，而是通過 readObject、writeObject 方法自定義序列化和反序列化政策。

之是以要用自定義的序列化和反序列化政策，是因為效率的問題。如果用預設處理來序列化的話，如果 elementData 的長度有100，但是實際隻用了50，其實剩餘的50是可以不用序列化的，這樣可以提高序列化和反序列化的效率，節省空間。

/**
   *  自定義序列化
   */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // fail-fast，後續判斷是否有并發處理
        int expectedModCount = modCount;
         // 序列化沒有标記為 static、transient 的字段，包括 size 等。
        s.defaultWriteObject();

        
        s.writeInt(size);

        // 序列化數組的前size個元素
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

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

   /**
   *  自定義反序列化
   */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

         反序列化沒有标記為 static、transient 的字段，包括 size 等
        s.defaultReadObject();

       
        s.readInt(); // ignored

        if (size > 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();
            }
        }
    }

線程安全

在上面的源碼裡我們看到很多方法裡有快速失敗的機制，例如判斷擴容的方法：

private void ensureExplicitCapacity(int minCapacity) {
    // 修改次數 +1，用于 fail-fast 處理
    modCount++;

這種快讀失敗的機制一定程度上避免了線程安全問題。

"快速失敗”即fail-fast,它是java集合的一種錯誤檢測機制。當多錢程對集合進行結構上的改變或者集合在疊代元素時直接調用自身方法改變集合結構而沒有通知疊代器時，有可能會觸發fast-fail機制并抛出異常。

當然，fail-fast機制隻是可能觸發，實際上，ArrayList的線程安全還是沒有保證的。一般，保證ArrayList的線程安全可以通過這些方案：

使用 Vector 代替 ArrayList。（不推薦，Vector是一個曆史遺留類）
使用 Collections.synchronizedList 包裝 ArrayList，然後操作包裝後的 list 即可。
使用 CopyOnWriteArrayList 代替 ArrayList。
在使用 ArrayList 時，應用程式通過同步機制去控制 ArrayList 的讀寫（不推薦）。

ArrayList源碼閱讀筆記簡介源碼分析序列化線程安全

簡介

源碼分析

屬性

構造方法

add(E e)

add(int index, E element)

addAll

get(int index)

remove(int index)

remove(Object o)

removeAll

set

序列化

線程安全

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method