Java集合之ArrayList扩容

ArrayList扩容机制

¶ArrayList的构造函数

¶默认参数

	//默认初始容量大小   
    private static final int DEFAULT_CAPACITY = 10;
	//指定该ArrayList数组容量为零时返回该对象数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

¶默认构造函数

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。

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

¶ArrayList的扩容机制

¶1.add()方法

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

注意 ：JDK11 移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法

¶2. ensureCapacityInternal() 方法

add 方法 首先调用了ensureCapacityInternal(size + 1)

   //进行容量检查，决定扩容的想要的最小容量
    private void ensureCapacityInternal(int minCapacity) {
        //判断当前数组是否是默认构造方法生成的空数组，如果是的话minCapacity=10,反之则根据原来的值传入下一个方法去完成下一步的扩容判断
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 获取默认的容量和传入参数的较大值
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

• 当add进第1个元素时，minCapacity的值为size+1，即为1，在Math.max()方法比较后，minCapacity 为10。
• 当add进第2个元素时，minCapacity的值为size+1=2，当前数组非空，不会进入if判断，保留为2。

¶3. ensureExplicitCapacity() 方法

如果调用 ensureCapacityInternal() 方法就一定会进过（执行）这个方法，下面我们来研究一下这个方法的源码！

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //调用grow方法进行扩容
            grow(minCapacity);
    }

• 当add第1个元素到 ArrayList时，minCapacity=size+1=1经过ensureCapacityInternal()方法后minCapacity=10，elementData.length=0 （因为还是一个空的 list 。此时，minCapacity - elementData.length > 0 成立，所以会进入 grow(minCapacity) 方法进行扩容。
• 当add第2个元素时，minCapacity=size+1=2，由于在添加第一个元素时进行了扩容，elementData.length=10。此时，minCapacity - elementData.length < 0 ，所以不会进入grow(minCapacity)方法。
• 一直到add第10个元素时，此时minCapacity=size+1=10，elementData.length=10，if条件不成立，依然不会执行grow方法，数组容量elementData.length都为10。
• 直到添加第11个元素，minCapacity=size+1=11，elementData.length=10，minCapacity - elementData.length > 0 成立，所以会再次进入 grow(minCapacity) 方法进行扩容。

¶4. grow() 方法

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

    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量，新容量更新为旧容量的1.5倍
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       	//如果新容量大于数组最大容量值,进入hugeCapacity()方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
       	//如果minCapacity大于数组最大容量，则使用整数最大值作为新容量，否则使用数组最大容量作为新容量，即为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 倍左右（oldCapacity为偶数就是1.5倍，否则是1.5倍左右）！ 奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

• 当add第1个元素时，oldCapacity=0，minCapacity=10，经比较后第一个if判断成立，newCapacity = minCapacity=10。但是第二个if判断不成立。数组容量为10，add方法中 return true,size增为1。
• 当add第11个元素进入grow方法时，oldCapacity=10，minCapacity=11，所以newCapacity=1.5oldCapacity=15。第一个if判断不成立，两个if判断都不成立。数组容量扩为15，add方法中return true,size增为11。
• 以此类推······

¶5. hugeCapacity() 方法。

    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() 等方法中都用到了该方法！

¶两者联系和区别

联系：

看两者源代码可以发现 Arrays.copyOf()内部实际调用了 System.arraycopy() 方法。

区别：

Arrays.copyOf() 在数组拷贝过程中创建新的数组，将原有数据拷贝到新数组中去，System.arraycopy()仅拷贝数组的内容，不会创建新数组。

¶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 方法，可以提高ArrayList初始化速度

我们通过下面的代码实际测试以下这个方法的效果：

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

	}
}

运行结果：

使用ensureCapacity方法前：2158

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        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方法前：1773

通过运行结果，我们可以看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法，以减少增量重新分配的次数。