这是我参与新手入门的第三篇文章
ArrayList 作为一个变长集合类，其核心是扩容机制。ArrayList 允许空值和重复元素，当往 ArrayList 中添加的元素数量大于其底层数组容量时，其会通过扩容机制重新生成一个更大的数组。另外，由于 ArrayList 底层基于数组实现，所以其可以保证在 O(1) 复杂度下完成随机查找操作。
ArrayList的成员变量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
复制代码DEFAULT_CAPACITY 属性：此属性创建空参ArrayList的默认数组长度
EMPTY_ELEMENTDATA 属性：默认长度为0的空数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 属性：初始化默认长度为10所获得的数组
elementData 属性： 这个属性就是我们用来存放数据的底层数组了
size 属性： 用于记录当前添加的元素的个数。
ArrayList的常用构造方法
/**
* 带初始容量参数的构造函数。（用户自己指定容量）
*
* @param initialCapacity 指定初始容量
* @throws IllegalArgumentException 如果给定的参数是负数，则会抛出IllegalArgumentException
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 默认构造函数，使用初始容量10构造一个空列表(无参数构造)
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException 如果指定的集合为null，throws NullPointerException。
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
复制代码带初始容量参数的构造函数：
这个构造方法很直观，主要就是根据用户自定义的初始容量大小，给elementData赋予指定长度的数组。
如果给定的初始容量大于0，则直接给elementData new 一个指定长度的Object[]数组即可。
如果给定的初始容量等于0，则将成员变量EMPTY_ELEMENTDATA赋给elementData
如果给定的初始容量小于0，则会抛出异常
默认无参构造函数：
这个构造方法直接将成员变量DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋给elementData即可，此构造方法只做了一件事，就是将 elementData 初始化为空数组，只有第一次调用了 add 方法才会赋予 elementData 大小为 10 的默认容量。
ArrayList的主要方法
add方法
对于数组（线性表）结构，插入操作分为两种情况。一种是在元素序列尾部插入，另一种是在元素序列其他位置插入。
/** 在元素序列尾部插入 */
public boolean add(E e) {
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将新元素插入序列尾部
elementData[size++] = e;
return true;
}
/** 在元素序列 index 位置处插入 */
public void add(int index, E element) {
rangeCheckForAdd(index);
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. 将新元素插入至 index 处
elementData[index] = element;
size++;
}
复制代码对于在元素序列尾部插入，这种情况比较简单，只需两个步骤即可：
检测数组是否有足够的空间插入
将新元素插入至序列尾部
如果是在元素序列指定位置（假设该位置合理）插入，则情况稍微复杂一点，需要三个步骤：
检测数组是否有足够的空间
将 index 及其之后的所有元素向后移一位
将新元素插入至 index 处
ensureExplicitCapacity() 方法
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//调用grow方法进行扩容，调用此方法代表已经开始扩容了
grow(minCapacity);
}
复制代码首先modCount自增我们可以不看
然后进入一个判断语句，查看当前的数组是否满足我们所需要的最小容量 minCapacity
如果不满足最小容量，则会进行grow()方法进行扩容。
这里举个例子，假设当前的数组长度为默认的10，则添加第1、2、3、4、5、6、7、8、9、10 个元素均不会出发grow（）方法，只有当我们添加第11个元素的时候，出发grow() 方法。
grow() 方法
/**
* 要分配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity) {
// 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);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码先确定当前数组的实际长度
然后将当前的数组的长度扩大1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1);
如果扩大的新数组的量还不满足我们的最小容量的时候，直接扩成最小容量，这步也只有在添加第一个元素，初始化长度为10的默认数组的时候才会发生。
另外如果翻了1.5倍之后长度大于了MAX_ARRAY_SIZE之后，会进入hugeCapacity(minCapacity)方法，确认一下最终要扩大的长度
最后就是使用了Arrays.copyOf()方法进行扩容。
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;
}
复制代码这里如果minCapacity < 0只有一种可能性，就是储存的元素超过的Int的最大值，产生了溢出。
如果超出了系统的MAX_ARRAY_SIZE,则扩成Integer.MAX_VALUE,否则扩成MAX_ARRAY_SIZE
ArrayList扩容的问题及解决方法
从上面的源码分析简单总结一下ArrayList的扩容机制，这里假设不带参数的空参构造方法
首先添加第一个元素，将数组扩容成10；
添加第11个元素，将数组扩容成15；
添加第16个元素，将数组扩容成22；
添加第23个元素，将数组扩容成33；
不停的添加元素，就会不停分扩容
从这里可以看出，在我们添加元素较多的情况下，ArrayList的扩容操作会经常发生，每一次扩容都会带来一次Arrays.copyof()的操作，必会带来大量的时间消耗。但是ArrayList类中提供了一个ensureCapacity方法，可以用来估算我们所需要的容量，提前一次性的将数组扩充好，避免多次扩容。
/**
如有必要，增加此 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);
}
}
复制代码
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
