【面試必備】透過源碼角度一步一步帶你分析 ArrayList 擴容機制

該文已加入開源文檔：JavaGuide（一份涵蓋大部分Java程式員所需要掌握的核心知識）。位址: https://github.com/Snailclimb/JavaGuide.

一先從 ArrayList 的構造函數說起

ArrayList有三種方式來初始化，構造方法源碼如下：

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

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *預設構造函數，使用初始容量10構造一個空清單(無參數構造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 帶初始容量參數的構造函數。（使用者自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//初始容量大于0
            //建立initialCapacity大小的數組
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//初始容量等于0
            //建立空數組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//初始容量小于0，抛出異常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }


   /**
    *構造包含指定collection元素的清單，這些元素利用該集合的疊代器按順序傳回
    *如果指定的集合為null，throws NullPointerException。 
    */
     public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[](see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

細心的同學一定會發現：以無參數構造方法建立 ArrayList 時，實際上初始化指派的是一個空數組。當真正對數組進行添加元素操作時，才真正配置設定容量。即向數組中添加第一個元素時，數組容量擴為10。下面在我們分析 ArrayList 擴容時會降到這一點内容！

二一步一步分析 ArrayList 擴容機制

這裡以無參構造函數建立的 ArrayList 為例分析

1. 先來看 `add` 方法

/**
     * 将指定的元素追加到此清單的末尾。 
     */
    public boolean add(E e) {
   //添加元素之前，先調用ensureCapacityInternal方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //這裡看到ArrayList添加元素的實質就相當于為數組指派
        elementData[size++] = e;
        return true;
    }

2. 再來看看 `ensureCapacityInternal()`

可以看到

add

方法首先調用了

ensureCapacityInternal(size + 1)

//得到最小擴容量
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
              // 擷取預設的容量和傳入參數的較大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

當要 add 進第1個元素時，minCapacity為1，在Math.max()方法比較後，minCapacity 為10。

3. `ensureExplicitCapacity()`

如果調用

ensureCapacityInternal()

方法就一定會進過（執行）這個方法，下面我們來研究一下這個方法的源碼！

//判斷是否需要擴容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //調用grow方法進行擴容，調用此方法代表已經開始擴容了
            grow(minCapacity);
    }

我們來仔細分析一下：

當我們要 add 進第1個元素到 ArrayList 時，elementData.length 為0 （因為還是一個空的 list），因為執行了 ensureCapacityInternal() 方法，是以 minCapacity 此時為10。此時， minCapacity - elementData.length > 0 成立，是以會進入 grow(minCapacity) 方法。
當add第2個元素時，minCapacity 為2，此時e lementData.length(容量)在添加第一個元素後擴容成 10 了。此時， minCapacity - elementData.length > 0 不成立，是以不會進入（執行） grow(minCapacity)
添加第3、4···到第10個元素時，依然不會執行grow方法，數組容量都為10。

直到添加第11個元素，minCapacity(為11)比elementData.length（為10）要大。進入grow方法進行擴容。

4. `grow()`

/**
     * 要配置設定的最大數組大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList擴容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity為舊容量，newCapacity為新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相當于oldCapacity /2，
        //我們知道位運算的速度遠遠快于整除運算，整句運算式的結果就是将新容量更新為舊容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然後檢查新容量是否大于最小需要容量，若還是小于最小需要容量，那麼就把最小需要容量當作數組的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       // 如果新容量大于 MAX_ARRAY_SIZE,進入(執行) `hugeCapacity()` 方法來比較 minCapacity 和 MAX_ARRAY_SIZE，
       //如果minCapacity大于最大容量，則新容量則為`Integer.MAX_VALUE`，否則，新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`。
        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);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1),是以 ArrayList 每次擴容之後容量都會變為原來的 1.5 倍！記清楚了！不是網上很多人說的 1.5 倍+1！

">>"（移位運算符）：>>1 右移一位相當于除2，右移n位相當于除以 2 的 n 次方。這裡 oldCapacity 明顯右移了1位是以相當于oldCapacity /2。對于大資料的2進制運算,位移運算符比那些普通運算符的運算要快很多,因為程式僅僅移動一下而已,不去計算,這樣提高了效率,節省了資源　

我們再來通過例子探究一下

grow()

方法：

當add第1個元素時，oldCapacity 為0，經比較後第一個if判斷成立，newCapacity = minCapacity(為10)。但是第二個if判斷不會成立，即newCapacity 不比 MAX_ARRAY_SIZE大，則不會進入 hugeCapacity 方法。數組容量為10，add方法中 return true,size增為1。
當add第11個元素進入grow方法時，newCapacity為15，比minCapacity（為11）大，第一個if判斷不成立。新容量沒有大于數組最大size，不會進入hugeCapacity方法。數組容量擴為15，add方法中return true,size增為11。
以此類推······

這裡補充一點比較重要，但是容易被忽視掉的知識點：

java 中的 length 屬性是針對數組說的,比如說你聲明了一個數組,想知道這個數組的長度則用到了 length 這個屬性.
length() 方法是針對字元串說的,如果想看這個字元串的長度則用到 length() 這個方法.
size() 方法是針對泛型集合說的,如果想看這個泛型有多少個元素,就調用此方法來檢視!

5. `hugeCapacity()`

從上面

grow()

方法源碼我們知道：如果新容量大于 MAX_ARRAY_SIZE,進入(執行)

hugeCapacity()

方法來比較 minCapacity 和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，則新容量則為

Integer.MAX_VALUE

，否則，新容量大小則為 MAX_ARRAY_SIZE 即為

Integer.MAX_VALUE - 8

。

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //對minCapacity和MAX_ARRAY_SIZE進行比較
        //若minCapacity大，将Integer.MAX_VALUE作為新數組的大小
        //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作為新數組的大小
        //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

三 `System.arraycopy()` 和 `Arrays.copyOf()`

閱讀源碼的話，我們就會發現 ArrayList 中大量調用了這兩個方法。比如：我們上面講的擴容操作以及

add(int index, E element)

、

toArray()

等方法中都用到了該方法！

3.1 `System.arraycopy()`

/**
     * 在此清單中的指定位置插入指定的元素。 
     *先調用 rangeCheckForAdd 對index進行界限檢查；然後調用 ensureCapacityInternal 方法保證capacity足夠大；
     *再将從index開始之後的所有成員後移一個位置；将element插入index位置；最後size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //arraycopy()方法實作數組自己複制自己
        //elementData:源數組;index:源數組中的起始位置;elementData：目标數組；index + 1：目标數組中的起始位置； size - index：要複制的數組元素的數量；
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

我們寫一個簡單的方法測試以下：

public class ArraycopyTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        System.arraycopy(a, 2, a, 3, 3);
        a[2]=99;
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

}

結果：

0 1 99 2 3 0 0 0 0 0

3.2 `Arrays.copyOf()`

/**
     以正确的順序傳回一個包含此清單中所有元素的數組（從第一個到最後一個元素）; 傳回的數組的運作時類型是指定數組的運作時類型。 
     */
    public Object[] toArray() {
    //elementData：要複制的數組；size：要複制的長度
        return Arrays.copyOf(elementData, size);
    }

個人覺得使用

Arrays.copyOf()

方法主要是為了給原有數組擴容，測試代碼如下：

public class ArrayscopyOfTest {

    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length"+b.length);
    }
}

3.3 兩者聯系和差別

聯系：

看兩者源代碼可以發現 copyOf() 内部實際調用了

System.arraycopy()

方法

差別：

arraycopy()

需要目标數組，将原數組拷貝到你自己定義的數組裡或者原數組，而且可以選擇拷貝的起點和長度以及放入新數組中的位置

copyOf()

是系統自動在内部建立一個數組，并傳回該數組。

四 `ensureCapacity`

ArrayList 源碼中有一個

ensureCapacity

方法不知道大家注意到沒有，這個方法 ArrayList 内部沒有被調用過，是以很顯然是提供給使用者調用的，那麼這個方法有什麼作用呢？

/**
    如有必要，增加此 ArrayList 執行個體的容量，以確定它至少可以容納由minimum capacity參數指定的元素數。
     *
     * @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

最好在 add 大量元素之前用

ensureCapacity

方法，以減少增量從新配置設定的次數

我們通過下面的代碼實際測試以下這個方法的效果：

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法前："+(endTime - startTime));

        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法後："+(endTime1 - startTime1));
    }
}

運作結果：

使用ensureCapacity方法前：4637
使用ensureCapacity方法前：241

通過運作結果，我們可以很明顯的看出向 ArrayList 添加大量元素之前最好先使用

ensureCapacity

【面試必備】透過源碼角度一步一步帶你分析 ArrayList 擴容機制

一先從 ArrayList 的構造函數說起

二一步一步分析 ArrayList 擴容機制

1. 先來看 `add` 方法

2. 再來看看 `ensureCapacityInternal()`

3. `ensureExplicitCapacity()`

4. `grow()`

5. `hugeCapacity()`

三 `System.arraycopy()` 和 `Arrays.copyOf()`

3.1 `System.arraycopy()`

3.2 `Arrays.copyOf()`

3.3 兩者聯系和差別

四 `ensureCapacity`

繼續閱讀

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使用文檔

Ambari介紹和架構原理

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

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

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

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

面試題解析：你接口測試是怎麼做的？

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

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

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

scala (3) Function 和 Method

【面試必備】透過源碼角度一步一步帶你分析 ArrayList 擴容機制

一 先從 ArrayList 的構造函數說起

二 一步一步分析 ArrayList 擴容機制

1. 先來看 add 方法

2. 再來看看 ensureCapacityInternal()

3. ensureExplicitCapacity()

4. grow()

5. hugeCapacity()

三 System.arraycopy() 和 Arrays.copyOf()

3.1 System.arraycopy()

3.2 Arrays.copyOf()

3.3 兩者聯系和差別

四 ensureCapacity

繼續閱讀

一先從 ArrayList 的構造函數說起

二一步一步分析 ArrayList 擴容機制

1. 先來看 `add` 方法

2. 再來看看 `ensureCapacityInternal()`

3. `ensureExplicitCapacity()`

4. `grow()`

5. `hugeCapacity()`

三 `System.arraycopy()` 和 `Arrays.copyOf()`

3.1 `System.arraycopy()`

3.2 `Arrays.copyOf()`

四 `ensureCapacity`