深入剖析ArrayList数据结构：源码和扩容机制
前语
ArrayList是Java中常用的数据结构之一，它完成了List接口，能够动态地增加或删去元素。在实践开发中，咱们经常运用ArrayList来存储和操作数据。本文将从源码和扩容机制两个方面来详细介绍ArrayList的完成原理。
一、ArrayList源码剖析
ArrayList的源码位于java.util包中，它是一个数组完成的动态列表。在ArrayList中，元素是按照刺进顺序存储的，能够依据索引访问元素。
界说
ArrayList界说如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
能够看到，ArrayList完成了List接口，并承继了AbstractList抽象类。其间，List接口界说了大部分操作办法，而AbstractList供给了默认的完成。
- RandomAccess 是一个标志接口，表明完成这个接口的 List 集合是支撑快速随机访问的。在 ArrayList 中，咱们即能够经过元素的序号快速获取元素对象，这就是快速随机访问。
- ArrayList 完成了 Cloneable 接口 ，即覆盖了函数clone()，能被克隆。
- ArrayList 完成了 java.io.Serializable接口，这意味着ArrayList支撑序列化，能经过序列化去传输。
成员变量
ArrayList的成员变量包含：
在ArrayList中，主要有三个成员变量：
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 存储元素的数组
private transient Object[] elementData;
// 元素的数量
private int size;
能够看到，elementData是存储元素的数组，size是元素的数量。transient关键字表明该成员变量不会被序列化。
结构函数
ArrayList有多个结构函数，其间最常用的是无参结构函数和带有初始容量参数的结构函数。
// 指定初始容量
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);
}
}
// 运用默认初始容量
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
能够看到，在指定初始容量的结构函数中，假如initialCapacity大于0，则新建一个elementData数组，创立一个指定容量的ArrayList；假如等于0，则运用空数组EMPTY_ELEMENTDATA；不然抛出反常。而在运用无参结构函数创立ArrayList时，实践上初始化赋值的是一个空数组，当真实对数组进行增加元素操作时，才真实分配容量，即向数组中增加第一个元素时，数组容量扩为10。
PS:JDK6 new 无参结构的ArrayList对象时，直接创立了长度是 10 的Object[]数组 elementData 。
办法
ArrayList的办法包含：
增加元素
ArrayList供给了多个增加元素的办法，最常用的是以下两个：
// 在末尾增加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 保证容量满足
elementData[size++] = e; // 增加元素
return true;
}
// 在指定方位刺进元素
public void add(int index, E element) {
rangeCheckForAdd(index); // 查看下标是否越界
ensureCapacityInternal(size + 1); // 保证容量满足
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 移动元素
elementData[index] = element; // 刺进新元素
size++; // 元素数量+1
}
在增加元素时，首要需求保证容量满足，即调用ensureCapacityInternal办法进行判别和扩容操作。然后，依据是在末尾增加元素仍是在指定方位刺进元素，别离进行增加操作。
删去元素
ArrayList供给了多个删去元素的办法，最常用的是以下两个：
// 经过下标删去元素
public E remove(int index) {
rangeCheck(index); // 查看下标是否越界
modCount++; // 修改次数+1
E oldValue = elementData(index); // 获取要删去的元素
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index+1, elementData, index,
numMoved); // 移动元素
}
elementData[--size] = null; // 将最终一个元素置为null
return oldValue; // 返回要删去的元素
}
// 从列表中删去指定元素的第一个出现（假如存在）。 假如列表不包含该元素，则它不会更改。
// 返回true，假如此列表包含指定的元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
二、扩容机制剖析
ArrayList的扩容机制是其完成的一个重要特点。在源码中，咱们能够看到扩容办法ensureCapacityInternal()和grow()的完成。当增加元素时，假如当时容量缺乏，则会调用ensureCapacityInternal()办法进行扩容。该办法会先判别当时数组是否为空，假如为空，则将容量设置为默认值10；不然，将容量设置为当时容量的1.5倍。假如扩容后的容量仍然不行，则直接运用所需的容量。假如所需的容量超越了最大容量，则抛出OutOfMemoryError反常。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
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);
}
在grow()办法中，首要核算新的容量newCapacity，它是原有容量oldCapacity的1.5倍。然后，判别新容量是否满足，假如不行，则运用所需的容量。假如所需的容量超越了最大容量，则抛出OutOfMemoryError反常。最终，运用Arrays.copyOf()办法将原有数组复制到新数组中。
总结
ArrayList是Java中最常用的集合之一，它是一个动态数组，能够主动扩容。在本文中，咱们深入剖析了ArrayList的完成原理，包含源码和扩容机制。咱们了解到，ArrayList的源码包含成员变量、结构函数和办法。ArrayList的扩容机制是在元素数量超越当时容量时，创立一个新的数组，并将原数组中的元素复制到新数组中。新数组的容量是原数组容量的1.5倍。假如新数组的容量小于指定的最小容量，则运用指定的最小容量。
