【闲笔杂谈】ArrayList的构造与扩容机制

⭐️前面的话⭐️

本篇文章将介绍Java中ArrayList的扩容机制，其实创建ArrayList对象的时候，系统并没有给ArrayList中数组开辟空间，第一次开辟空间的时机是第一次插入数据的时候。

1.谈谈你对构造ArrayList对象的理解。

当构造ArrayList对象时，如果使用的无参的构造方法，ArrayList数组的空间大小为0，因为使用构造方法构造时，自己内部的保存数据的数组并没有申请空间，如何证明。源码就是最好的证明，在Java1.8版本中，调用ArrayList的无参数构造方法后，顺序表中的数组只是一个空数组，容量为0。

我们在来看看含参数的构造方法，ArrayList含有参数的构造方法有两个，一个给定容量来进行ArrayList对象的实例。

我们来分析一下代码的意思，大致的意思就是：

• 如果给定的初始容量大于0，就会指定一个初始指定容量的数组。
• 如果指定的初始容量等于0，那就相当于调用了无参的构造方法，顺序表中的数组仅仅只是一个空数组。
• 其他情况，比如你给了一个负的初始容量，抛出一个IllegalArgumentException非法数据异常的大礼物送给你。

还有一个含参数的构造方法，那就是你可以传入其他的Collection对象，可以根据这个Collection对象保存的数据来构造ArrayList对象。

构造方法执行的基本逻辑如下：

• 第一步，使用toArray方法将集合中的元素转换为数组。
• 第二步，计算数组的大小，如果为0，则构造的顺序表中的数据只是一个空数组，如果大小不为0，则继续进行判断。
• 第三步，判断原来集合的类型是否是ArrayList，如果是，那直接将转换的数组直接给构造的ArrayList对象，否则拷贝一个数组给构造的ArrayList对象。

（其实目前我还有点不理解为什么还要拷贝数组，直接将a数组对象赋值上去不好吗，还省资源）

2.谈谈对ArrayList扩容机制的理解。

我们知道使用无参构造方法构造ArrayList对象，里面的数组大小为0，当添加元素或者数组满时添加元素都是需要触发扩容操作的，我们来看一看ArrayList中add方法的执行逻辑：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

在正式添加元素之前，会先去确认数组是否已满，如果满了，则扩容，下面我们来看看具体判断是否需要扩容的方法ensureCapacityInternal，传入参数的含义是最小需要的容量minCapacity。

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

然后就会根据calculateCapacity方法去计算扩容的容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == *DEFAULTCAPACITY_EMPTY_ELEMENTDATA*) {
            return Math.*max*(*DEFAULT_CAPACITY*, minCapacity);
       }    
    return minCapacity;
}

如果发现原来的数组就是一个空数组，就会返回默认容量DEFAULT_CAPACITY（默认为10）与所需最小容量其中一个较大的值，如果不是空数组，直接返回最小所需容量值。

最后就会根据ensureExplicitCapacity方法根据传入的数组与最小所需容量进行扩容

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;    *// overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
    }

如果最小所需容量大于目前数组的大小，则进行扩容，调用扩容的方法grow

private void grow(int minCapacity) {
    // overflow-conscious code
    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);
}

这个grow方法会先得到原来数组的1.5倍大小，如果比最小所需容量要小，则最终扩容的数组的大小为最小所需容量大小，否则最终扩容就是1.5倍扩容。

然后在判断最终扩容的容量是否比MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8大，如果比这个数大则调用hugeCapacity方法。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();    
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

hugeCapacity方法就会去判断最小所需容量是否溢出（就是验证是否<0），如果溢出，说明顺序表最大大小最大也不够用，直接抛出一个OutOfMemoryError错误。

否则最终的容量取决于最小所需容量minCapacity与MAX_ARRAY_SIZE的大小：

• minCapacity>MAX_ARRAY_SIZE返回Integer.MAX_VALUE。
• 否则返回MAX_ARRAY_SIZE。

3.总结

ArrayList扩容时，如果原数组不是空数组，会计算一个最小所需容量，就是插入元素后最小需要的容量，如果这个容量超过了原数组的大小，按照grow方法的逻辑进行扩容：

• 如果最小所需容量大于1.5倍原容量，最终扩容的数组的大小为最小所需容量。
• 如果最小所需容量不大于1.5倍原容量，最终扩容的数组大小为1.5倍原容量。
• 如果得到的最终容量大小大于MAX_ARRAY_SIZE，则判断最小所需容量是否溢出，如果溢出就抛出异常，没有的话，最终扩容的容量取决于最小所需容量与的MAX_ARRAY_SIZE前者大就取最终容量大小为Integer.MAX_VALUE后者大最终扩容容量就取MAX_ARRAY_SIZE。

如果扩容之前的数组为空数组，则新的最小所需容量取原来得到的最小所需容量与默认容量DEFAULT_CAPACITY（默认为10）中的较大值，后面的扩容逻辑不变。