ArrayList扩容机制解析

1.ArrayList的成员变量

首先我们先了解一下ArrayList的成员变量。

// 默认初始化大小
private static final int DEFAULT_CAPACITY = 10;// 空数组（用于空实例）
// 比如List<String> ls = new ArrayList<>(0);
private static final Object[] EMPTY_ELEMENTDATA = {};// 主要用来标识该ArrayList使用无参构造方法进行了初始化
// elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA意味着使用无参构造函数进行了初始化
// 使用无参构造函数的默认容量是10，但是并不是一开始就进行了初始化，而是真正在插入元素的时候才进行了初始化
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 实际上保存ArrayList数据的数组
transient Object[] elementData; // non-private to simplify nested class access// ArrayList包含的元素个数
private int size;

2.ArrayList的构造方法

了解了基本成员变量以后我们再来看一下构造函数

// 有参构造方法，由自己进行容量的初始化
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);}
}// DEFAULTCAPACITY_EMPTY_ELEMENTDATA为0.初始化为10
// 意味着ArrayList的初始其实是空数组，当添加第一个元素的时候数组容量才变成10
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}// 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// 如果elementData不是Object类型数据（c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断）if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {this.elementData = EMPTY_ELEMENTDATA;}
}

3.ArrayList的扩容机制

下面正式开始讲解ArrayList的扩容机制。

什么时候开始扩容，毫无疑问，当然是添加元素，而elementData的容量不够的时候进行扩容，所以我们从add()方法起手。

public boolean add(E e) {// 首先是将当前size+1作为参数，然后调用ensureCapacityInternal判断是否需要进行扩容ensureCapacityInternal(size + 1);  // Increments modCount!!// 最后将元素放入容量足够未扩容/容量不够扩容过的elementData数组elementData[size++] = e;return true;
}

接下来我们跟进ensureCapacityInternal方法，看看到底发生了什么…

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private static int calculateCapacity(Object[] elementData, int minCapacity) {// 1.计算最小扩容量// 在前面也说过，如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA// 就意味着该ArrayList刚刚调用完无参构造方法，这个地方正是该ArrayList第一次添加元素，将容量初始化为10的地方if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}// 返回最小扩容量return minCapacity;
}private void ensureExplicitCapacity(int minCapacity) {modCount++;// 2.判断是否需要进行扩容// 如果最小需要的容量大于数组elementData的容量，就意味着要进行扩容操作// 注意！不要把size和elementData的容量弄混了，一个是ArrayList当前存放元素的个数，一个是当前容量的大小！if (minCapacity - elementData.length > 0)// 3.如果判断需要进行扩容，则调用grow方法进行扩容grow(minCapacity);
}

通过以上几个方法的执行，如果确定最小需求容量minCapacity大于该ArrayList的当前容量，就会调用grow()方法进行扩容，我们再继续看grow()方法的内部实现。

private void grow(int minCapacity) {// 先获取旧容量oldCapacity// overflow-conscious codeint oldCapacity = elementData.length;// 采用右移计算（效率更高），将新容量newCapacity赋值为旧容量oldCapacity的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);// 检查新容量是否符合最小容量需求，如果新容量小于最小容量需求，就将新容量设计为最小容量需求if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 再检查新容量newCapacity是否超出了ArrayList类所定义的最大容量// 如果超出了那么就将新容量设置为Integer的最大值，否则设置为Arraylist定义的最大容量if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 最后将elementData按照新容量newCapcity拷贝到一个新数组返回elementData = Arrays.copyOf(elementData, newCapacity);
}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

读到这里，可能你会好奇关于为什么ArrayList的默认最大容量为Integer.MAX_VALUE - 8？我们可以详细看一下关于这个变量的注解

/*** The maximum size of array to allocate.* Some VMs reserve some header words in an array.* Attempts to allocate larger arrays may result in* OutOfMemoryError: Requested array size exceeds VM limit*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

大概意思是说，一些虚拟机会预留数组头部的大小，一般数组头部有8个字节，所以 这里要减掉头部的8个字节，不然的话，整个数组大小就超过int的最大值了。就会跑出OutOfMemoryError错误。