发布日期: 2022-03-17

ArrayList的扩容机制

对这段代码进行分析

package ArrayListSourceCode;

import java.util.ArrayList;

public class SourceCode {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
       // ArrayList list = new ArrayList(8);
        for (int i = 1; i <=10 ; i++) {
            list.add(i);
        }
        for (int i=11;i<=15;i++){
            list.add(i);
        }
        list.add(100);
        list.add(200);
        list.add(null);

    }
}

从无参构造开始

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


    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


/**
     *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
     */
public ArrayList() {
    
 this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 //private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};是一个空对象  赋给elementData
}

在第一次进行for循环准备添加值是才开始准备扩容
首先是自动装箱的过程

public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

然后来到这句源码

public boolean add(E e) {
     //添加元素之前，先调用ensureCapacityInternal方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
      //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }

先确定是否要扩容然后进行复制

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

ensureCapacityInternal中又调用了 ensureExplicitCapacity这个方法

  private static int calculateCapacity(Object[] elementData, int minCapacity) {
      //如果此时elementData还为空 也就是说没进行扩容 
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
             // 获取默认的容量和传入参数的较大值
            return Math.max(DEFAULT_CAPACITY（10）, minCapacity);
        }
      //如果已经添加过元素 就返回size+1  就是这次添加完成后的size
        return minCapacity;
    }

首先执行这个方法  当elementData是当初赋的空对象是 就把默认容量和要求最小容量取最大值  所以返回10

 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 方法进行扩容。

此时进入grow函数进行扩容

    /**
     * 要分配的最大数组大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  

     /**  
     * ArrayList扩容的核心方法。
     */

private void grow(int minCapacity) {
        // overflow-conscious code
        //minCapacity=10
      // 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);
        elementData = Arrays.copyOf(elementData, newCapacity);
 }

于是此时newCapacity为10
Arrays.copyOf拷贝原来elementData数据，放到新的newCapacity中

当容量不够时扩容是 oldCapacity + (oldCapacity >> 1);为1.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() 等方法中都用到了该方法！

// 我们发现 arraycopy 是一个 native 方法,接下来我们解释一下各个参数的具体意义
/**
*   复制数组
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要复制的数组元素的数量
*/
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

    public static int[] copyOf(int[] original, int newLength) {
        // 申请一个新的数组
        int[] copy = new int[newLength];
    // 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }