概述
-
ArrayList
使用动态数组来存储元素。用MSDN(面向开发人员和技术专业人员的 Microsoft 文档和学习主页)中的说法，就是Array的复杂版本，它提供了动态的增加和减少元素，实现了Collection和List接口，灵活的设置数组的大小等好处。
动态数组是指在声明时没有确定数组大小的数组，即忽略圆括号中的下标；当要用它时，可随时用ReDim(为数组变量重新分配存储空间)语句重新指出数组的大小。使用动态数组的优点是可以根据用户需要，有效利用存储空间
-
继承关系图
1>.ArrayList继承了AbstractList，实现了List，提供了添加、修改、删除、遍历等功能。
2>.ArrayList实现了RandomAccess接口，提供了随机访问的功能。在ArrayList中，通过元素下标快速获取到元素。实际RandomAccess是没有任何代码的，但ArrayList底层是数组，所以快速随机访问是肯定的。
3>.ArrayList实现了Cloneable接口，即覆盖了clone()方法，可以被克隆(浅克隆)。
4>.ArrayList实现了Serializable接口，即支持序列化(将对象的状态信息转换为可以存储或传输的形式的过程)。
5>.ArrayList是非线程安全的，根据场景需要可以使用线程安全的替换ArrayList，例如Vector或CopyOnWriteArrayList。
扩容原理
- 了解ArrayList的属性
// 默认数组长度
private static final int DEFAULT_CAPACITY = 10;
// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空数组，不同于EMPTY_ELEMENTDATA，该空数组主要用于无参创建ArrayList时扩容
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储元素的数组，transient修饰不存于序列化
transient Object[] elementData;
// 数组长度，实际数组里元素的数量
private int size;
- 了解ArrayList的构造方法，不同的构造方法影响着扩容机制的判断
// 无参构造，elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定初始容量构造，当initialCapacity为0，elementData = EMPTY_ELEMENTDATA
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);
}
}
// 包含指定集合有参构造，指定集合的length为0时，elementData = EMPTY_ELEMENTDATA
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;
}
}
- 扩容，发生在add添加元素方法中，只有添加才会涉及容量不足而产生扩容。后续分析扩容以无参构造创建的ArrayList，且第一次添加元素作为主要分析依据。看下两个主要添加方法的具体逻辑：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
// 确保指定下表不越界
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
可以看到两个方法都调用了ensureCapacityInternal(size + 1)方法，把数组长度加1以确保能存下下一个数据。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
此方法会先调用calculateCapacity方法，参数有elementData、minCapacity。无参构造时elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA；minCapacity为size + 1，size为0，即minCapacity为1；
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
此方法会判断当前数组是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，刚才提到无参构造时才会返回这个数组。所以，若创建ArrayList时调用的是无参构造，此方法会返回DEFAULT_CAPACITY（值为10）和 minCapacity的之间最大值，因此，最终会返回固定值10；若创建ArrayList时调用了有参构造，则第一次调此方法会返回1，注意这个minCapacity变量只是第一次调用add方法时值为1，此后的调用需要根据实际的数组长度size + 1。
再调用ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount++用到了快速失败机制，此处先不做讨论；
继续向下走，如果minCapacity大于elementData.length，则会调用grow方法，注意这个elementData.length返回的是当前数组的容量，而不是数组实际的长度size。如果调用了有参构造，例如传入的容量为5，则此时elementData.length值即为5，而此时第一次调用add时，size值为0，因此minCapacity为1，不满足条件，此情况不需要扩容调用grow方法；如果调用了无参构造返回数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，注意这个数组只是一个空数组，因此此时elementData.length为0，满足条件，需要扩容调用grow方法。
通俗来讲，就是如果ArrayList给定了特定初始容量，则此处需要根据实际情况确定是否调用grow方法，即有可能不需要扩容。如果没有指定初始容量，第一次调用add则此处一定需要调用grow方法。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
}
int newCapacity = oldCapacity + (oldCapacity >> 1)此行代码即为扩容的核心，oldCapacity为原来的容量，右移一位，即除以2，因此这句的意思就是新的容量newCapacity = oldCapacity+oldCapacity / 2，即原来的1.5倍。
然后判断newCapacity如果小于传入的minCapacity，则直接让newCapacity等于minCapacity（当无参构造时，elementData.length为0，所以oldCapacity也为0，minCapacity为10，因此最终newCapacity为10）。
然后判断newCapacity是否大于设定的MAX_ARRAY_SIZE，此处
private static final int 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;
}
如果minCapacity大于MAX_ARRAY_SIZE，则返回Integer的最大值，否则返回MAX_ARRAY_SIZE。最后，通过Arrays.copyOf方法把原数组的内容放到更大容量的数组里面。
面试常问
-
ArrayList 是什么？常用来做什么？底层是什么实现的？
ArrayList是有序动态数组，顾名思义底层是数组实现的，实现了List接口，提供了基本的增、删、改、查等功能。常用来装载数据的。 -
ArrayList 和 LinkedList 有什么区别？各自优缺点？
ArrayList 查找和访问速度较快(底层是数组)，添加和删除相较慢些(例如指定中间位置添加元素，该下标后的元素全部后移一位，删除同理，该下标后的元素全部前移一位)
LinkedList 查找和访问速度较慢(底层是链表)，添加和删除相较快些。
都是非线程安全的。
当遇到访问元素比较频繁时，建议使用ArrayList；当遇到在某个特定索引中，删除或添加元素比较频繁时，建议使用LinkedList。 -
ArrayList 是否是线程安全的？
ArrayList是非线程安全的，可以使用线程安全的集合例如Vector或CopyOnWriteArrayList。 -
ArrayList 动态扩容机制是什么？
1.扩容是发生在调用add方法的时候
2.在add方法中，会先 判断存储元素的数组elementData是否等于ArrayList一个特殊的空数组，只有无参构造才会等于，minCapacity才会为默认长度10
有参构造不会等于，minCapacity为size + 1，size为当前数组的元素数量。再判断minCapacity是否大于elementData.length，大于则表明需要扩容。
指定两个变量，oldCapacity = element.length，newCapacity = oldCapacity + oldCapacity / 2，即新数组长度为之前数组长度的1.5倍。判断
newCapacity < minCapacity，小于则newCapacity = minCapacity；再判断newCapacity > MAX_ARRAY_SIZE，大于则最大赋值Integer.MAX_VALUE。
最后通过Arrays.copyOf创建新长度的数组，包含原数组元素。
扩容参考文章：
https://blog.csdn.net/qq_26542493/article/details/88873168