ArrayList扩容原理

ArrayList扩容原理（源码理解）

从源码角度对ArrayList扩容原理进行简介，我们可以更深入地了解其内部实现和工作原理。以下是基于Java标准库中ArrayList扩容原理源码的简介

1、类定义与继承关系

ArrayList在Java中的定义如下：

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

{

ArrayList是一个泛型类，继承自AbstractList并实现了List接口，同时还实现了RandomAccess、Cloneable和Serializable接口。这 些接口分别表示ArrayList支持随机访问、可以被克隆以及可以被序列化。

2、核心成员变量（牢记）

elementData：是实际存储元素的数组，它可以是默认大小的空数组（当没有指定初始容量且没有添加元素 时），也可以是用户指定的初始容量大小的数组，或者是在扩容后新分配的数组。
size：表示数组中当前元素的个数。

transient Object[] elementData; //数组

private int size;               //元素个数

DEFAULT_CAPACITY是ArrayList的默认容量，当没有指定初始容量时，会使用这个值。

    //默认初始容量。
private static final int DEFAULT_CAPACITY = 10;

EMPTY_ELEMENTDATA表示空数组。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA也表示空数组，为了区分而命名不同。

    
//用于创建空对象的共享空数组实例。
private static final Object[] EMPTY_ELEMENTDATA = {};

//用于默认大小的空数组实例的共享空数组实例。我们将它与EMPTY_ELEMENTDATA区分开来，以便在添加第一个元素时知道要扩容多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

3、构造方法

ArrayList提供了多个构造方法，包括无参构造方法、指定初始容量的构造方法。
java

   
//无参构造

//构造一个初始容量为10的空数组。    
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

//有参构造

//构造具有指定初始容量的空数组。     
public ArrayList(int initialCapacity) {                    			//构建有参构造方法
if (initialCapacity > 0) {                             			//如果传入参数>0
this.elementData = new Object[initialCapacity];    			//创建一个数组，大小为传入的参数

    } else if (initialCapacity == 0) {                     			//如果传入的参数=0
this.elementData = EMPTY_ELEMENTDATA;              			//得到一个空数组

    } else {                                               			//否则
throw new IllegalArgumentException("Illegal Capacity: "+    //抛出异常

                                               initialCapacity);        

    }

}

这里可以看到无参构造方法用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示空数组，而有参构造方法中当传入参数=0，用的是EMPTY_ELEMENTDATA表示空数组。

4、扩容机制

具体流程：

1、开始添加元素前先判断当前数组容量是否足够（ensureCapacityInternal（）方法），这里有个特例就是添加第一个元素时要先将数组扩容为初始容量大小（calculateCapacity（）方法）。如果足够就向数组中添加元素。

2、如果当前数组容量不够，开始计算新容量的大小并赋值给新数组，复制原始数组中的元素到新数组中（grow（）方法）

流程图如下：

从向ArrayList添加元素来观察底层源码是如何实现的

观察add（）方法，其中提到一个不认识的ensureCapacityInternal（）方法，把他看做用来判断数组容量是否足够的方法,判断完后将元素添加到数组中

public boolean add(E e) {

    ensureCapacityInternal(size + 1);  //判断数组容量是否足够，传入的一个大小为（size+1）的参数

    elementData[size++] = e;           //添加元素
return true;

}

现在来看上面add（）方法提到的ensureCapacityInternal（）方法, 进入查看源码,又出现两个不认识的方法: calculateCapacity（）方法和ensureExplicitCapacity（）方法。

private void ensureCapacityInternal(int minCapacity) {       //这里minCapacity大小就是上面传入参数：size+1
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

    }
```

calculateCapacity（）方法：里面有一个判断语句，判断当前数组是不是空数组。如果是空数组那就将数组容量初始化为10，如果不是空数组，那就直接返回minCapacity。
ensureExplicitCapacity（）方法：重点观察判断语句，将calculateCapacity（）方法中传进来的minCapacity与原数组的长度作比较，当原数组长度小于minCapacity的值就开始进行扩容。

//    calculateCapacity方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判断数组是否为空
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
//数组为空时比较，DEFAULT_CAPACITY=10，minCapacity=size+1，DEFAULT_CAPACITY一定比minCapacity大，所以空数组容量初始化为10
return Math.max(DEFAULT_CAPACITY, minCapacity);      

    }          
//数组不为空，minCapacity=size+1，相当于不变
return minCapacity;


}

//-------------------------------------------分割线-----------------------------------------------------//


//    ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) {//这里的minCapacity是上面传过来的

    modCount++;   
if (minCapacity - elementData.length > 0)         //判断数组长度够不够，不够才扩
grow(minCapacity);

}

举例

前面都是判断数组要不要进行扩容，下面内容就是如何扩容。

首先，grow（）方法是扩容的入口，它根据当前容量计算新容量，并调用Arrays.copyOf方法复制数组。hugeCapacity（）方法用于处理超大容量的情况，确保不会超出数组的最大限制。

*   这一步是为了先确定扩容的大小，再将元素复制到新数组中



private void grow(int minCapacity) {        

    int oldCapacity = elementData.length;                //定义一个oldCapacity接收当前数组长度

    int newCapacity = oldCapacity + (oldCapacity >> 1);  //定义一个newCapacity接收oldCapacity1.5倍的长度

    if (newCapacity - minCapacity < 0)                   //如果newCapacity长度<minCapacity
newCapacity = minCapacity;                       //将minCapacity赋值给newCapacity

    if (newCapacity - MAX_ARRAY_SIZE > 0)                //如果newCapacity长度>最大的数组长度
newCapacity = hugeCapacity(minCapacity);         //将进行hugeCapacity方法以后的值赋值给newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);//开始扩容

}

查看hugeCapacity（）方法 (防止扩容后的数组太大了)
MAX_ARRAY_SIZE 理解为：快接近integer的最大值了。
Integer.MAX_VALUE 理解为：integer的最大值。

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)                             //如果minCapacity<0
throw new OutOfMemoryError();                //抛出异常
return (minCapacity > MAX_ARRAY_SIZE) ?          //返回一个值，判断minCapacity是否大于MAX_ARRAY_SIZE

        Integer.MAX_VALUE :                          //大于就返回 Integer.MAX_VALUE

        MAX_ARRAY_SIZE;                              //小于就返回 MAX_ARRAY_SIZE

}


```

最后一步，了解是如何如何将元素添加到新数组的

查看Arrays.copyof源代码

用于将一个原始数组（original）复制到一个新的数组中，新数组的长度（newLength）可以与原始数组不同。


public static <T> T[] copyOf(T[] original, int newLength) {

    return (T[]) copyOf(original, newLength, original.getClass());

}

查看copyof（）方法 (判断新数组与原数组类型是否一致)

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;

}

开始复制原数组的元素到新数组中

将一个数组`src`的从索引`srcPos`开始的`length`个元素复制到另一个数组`dest`的从索引`destPos`开始的位置。

public static native void arraycopy(Object src,  int  srcPos,

                                    Object dest, int destPos,

                                    int length);


                                            参数说明：

参数说明：

• 
  
• src：原数组，类型为Object，表示可以接受任何类型的数组。
  
• srcPos：原数组的起始索引，即从哪个位置开始复制元素。
  
• dest：新数组，类型为Object，表示可以接受任何类型的数组。
  
• destPos：新数组的起始索引，即从哪个位置开始粘贴元素。
  
• length：要复制的元素数量。
  

从宏观上来说，ArrayList展现的是一种动态数组的扩容，当数组中元素个数到达一定值时数组自动会扩大容量，以方便元素的存放。

从微观上来说，ArrayList是在当数组中元素到达一定值时，去创建一个大小为原数组1.5倍容量的新数组，将原数组的元素复制到新数组当中，抛弃原数组。