手撕 ArrayList 底层，透彻分析源码，mysql 索引优化面试题

(1) ArrayList 继承 AbstractList 抽象类，实现了 RandomAccess、Cloneable、Serializable 接口，RandomAccess 使其拥有快速访问的能力。

(2) Cloneable 其实就是一个标记接口，只有实现这个接口后，然后在类中重写 Object 中的 clone 方法，然后通过类调用 clone 方法才能克隆成功，如果不实现这个接口，则会抛出 CloneNotSupportedException(克隆不被支持)异常。

(3) Serializable 是序列化接口，支持序列化和反序列化。

(4) DEFAULT_CAPACITY 是 ArrayList 默认的初始化集合的大小。

(5) EMPTY_ELEMENTDATA 是一个空对象数组，用于空实例的共享空数组实例。

(6) DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是使用默认构造函数创建集合的时候使用该对象

(7) elementData 用于存放当前数据的数组对象。

(8) size 是集合的大小。

(9) 当集合中的元素超出数组规定的长度时，数组就会进行扩容操作，扩容操作就是 ArrayList 存储操作缓慢的原因，尤其是当数据量较大的时候，每次扩容消耗的时间会越来越多。

ArrayList 的构造方法源码

ArrayList(int initialCapacity)

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);}}

(1) 该构造函数很简单，直接判断传进来的数值大小，要是大于零，直接初始一个该长度的数组对象，并赋值给 elementData，要是等于零，将空数组对象 EMPTY_ELEMENTDATA 赋给 elementData，否则，直接抛出异常。

(2) ?该构造函数一般使用在要初始化一个比较大数据量的的集合的时候使用。

ArrayList()

public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

(1) 将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组对象赋给 elementData

ArrayList(Collection c)

public ArrayList(Collection<? extends E> c) {

elementData = c.toArray();

if ((size = elementData.length) != 0) {if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {this.elementData = EMPTY_ELEMENTDATA;}}

这里主要做了两件事:(1) 先将集合 c 转化为数组，然后赋值给 elementData 数组对象。

(2) 然后判断 size 和是否相等并且不等于 0，是则执行数据的赋值并重新赋值给数组对象 elementData，否则直接将空数组对象赋值给 elementData。

ArrayList 的方法源码分析

add()方法

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

(1) 执行 ensureCapacityInternal 方法，

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

判断原有的数组对象是否需要扩容。

(2) 将 e 对象添加到 elementData 数组对象中。

接下来我们来看看 ensureCapacityInternal 方法的源码。

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

在 ensureCapacityInternal 中调用了 ensureExplicitCapacity 方法和 calculateCapacity 方法，我们来看下 calculateCapacity 方法

private static int calculateCapacity(Object[] elementData, int minCapacity) {

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}

(1) 这里的任务主要是计算容量的大小，先判断 elementData 数组对象是否有初始化大小，若没有就取 DEFAULT_CAPACITY 或 minCapacit 中的较大者为容量的大小，若已经初始化了就 minCapacity 为容量大小。

接着来看看 ensureExplicitCapacity 的源码：

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

if (minCapacity - elementData.length > 0)grow(minCapacity);}

(1) 执行 modCount 自增，modCount 为当前列表结构被修改次数。

(2) 判断 minCapacity 要是大于 elementData.length 就执行扩容，否则，直接退出此方法，进行添加元素的操作。

接着我们来看看 grow 方法的源码：

private void grow(int minCapacity) {

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1);

if (newCapacity - minCapacity < 0)newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);

elementData = Arrays.copyOf(elementData, newCapacity);}

(1) 这里先拿到原来数据 elementData 的长度赋给一个变量 oldCapacity，然后将原来的长度扩大 1.5 倍并付给 oldCapacity。

(2) 判断 minCapacity 是否大于 newCapacity，成立则将 minCapacity 赋给 newCapacity，为什么要这么做呢？因为从前的一层层的方法进行解析之后来看，minCapacity 是允许扩容后的最小长度，也就是实际存有数据的最小长度，要是你扩容后的长度还比 minCapacity 要小，那么只能将 minCapacity 作为容器的长度。

(3) 然后判断容器新长度 newCapacity 是否大于容器所允许的最大长度 MAX_ARRAY_SIZE，成立则将扩容长度设置为最大可用长度。

(4) 拷贝，扩容，构建一个新的数组。

接着我们来看看 grow 方法调用的 hugeCapacity 的源码：

private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflowthrow new OutOfMemoryError();

return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

(1) 直接判断 minCapacity 是否小于零，成立抛出异常，然后比较容器所允许的最小长度值是否大于 MAX_ARRAY_SIZE，成立则将 Integer 的最大值赋值给 minCapacity 作为容器的最大长度。

add(int index, E element)方法

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++;}

(1) ?这里主要做三件事，第一件就是判断下标是否越界，如果是则抛出 IndexOutOfBoundsException 异常。

(2) 然后就是判断是否需要扩容，这个方法和上面的一样，已经说过了，就不再赘述了。

(3) 最后就是执行数组对象 index 后的对象后移一位，将元素添加到指定位置。

接下来我们来看看 rangeCheckForAdd 的源码

private void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

(1) 直接就是判断 index > size 或者 index < 0 条件，成立就直接抛出数组下标越界异常。

addAll(Collection c)方法

public boolean addAll(Collection<? extends E> c) {return addAll(this.size, c);}

public boolean addAll(int index, Collection<? extends E> c) {

rangeCheckForAdd(index);

int cSize = c.size();

if (cSize==0)return false;

checkForComodification();

parent.addAll(parentOffset + index, c);

this.modCount = parent.modCount;

this.size += cSize;return true;}

private void checkForComodification() {if (ArrayList.this.modCount != this.modCount)throw new ConcurrentModificationException();}

(1) addAll(Collection c)方法里面直接调用 addAll(this.size, c)，在 addAll(this.size, c)里面第一件事就是判断是否下标越界。

(2) 然后判断 c 的大小是否大于 0，如果等于 0 返回 false。

(3) 检查修改的次数是否相等，若不相等直接则抛出 ConcurrentModificationException（并发修改）异常，这个也就是当我们用迭代器循环 list 的时候，在其中用 list 的方法新增/删除元素，就会出现这个错误。

(4) 将元素插入到数组中，将修改次数赋值给 modCount，最后 size 大小加一

(5) 在进行 add 操作时先判断下标是否越界，是否需要扩容，如果需要扩容，就复制数组，默认扩容一半，如果扩容一半不够的话，就用目标的 size 作为扩容后的容量，然后设置对应的下标元素值。

get()方法

public E get(int index) {rangeCheck(index);return elementData(index);}

private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

E elementData(int index) {