目录
前言
继承关系
构造器
动态扩展
移除元素
线程安全问题
总结
前言
ArrayList可以说是在日常开发过程中最常使用的集合之一了。我们常常用其作为容器保存一些对象，以便后面的程序取用。
在Java中数组的长度需要在初始化时就明确指定，并且在指定后不能改变。ArrayList内部也是一个数组，但它增强了数组的功能：它能够在容器中的元素增加时，动态的扩展，这也是ArrayList的核心。
接下来一起看看ArrayList内部是如何实现的。
继承关系
首先看看，ArrayList的类声明所展示的继承结构。
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable {
在Idea中，可以使用快捷键Ctrl + H查看类的整体继承层次结构。如下：
从这个图中，可以比较清楚的看到类与接口之间的继承层次结构。
不过，也可以从网上找到类似的使用以下方式展示类继承结构的图：
构造器
ArrayList提供了三种构造器。分别是：
- 无参的构造器
- 指定初始容量的构造器
- 指出初始集合的构造器。
1. 无参的构造器
源码定义：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
这个无参构造器中包含两个变量：elementData、DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这两个变量的定义如下：
transient Object[] elementData; // non-private to simplify nested class access
可以看到elementData是一个对象类型的数组，注释也说明了这个变量是用于存放ArrayList元素的数组缓冲区。这个数组缓冲区的长度就是ArrayList的容量。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个对象数组类型的空数组。
因此，无参构造器的功能就是将elementData初始化为对象类型的空数组。
2. 指定初始容量的构造器
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);
}
}
可以看到，如果指定的初始容量值大于0，那么该构造器会将elementData变量初始化为一个指定大小的对象数组。当指定的初始容量值等于0，该构造器就会将elementData变量初始化为 EMPTY_ELEMENTDATA，这个变量的定义如下：
private static final Object[] EMPTY_ELEMENTDATA = {};
注意，这也是一个空对象数组，和DEFAULTCAPACITY_EMPTY_ELEMENTDATA一样。之所以取不同的名字，在DEFAULTCAPACITY_EMPTY_ELEMENTDATA的注释上有说明，这样做是为了区分在初始化ArrayList时是否指定了容量值。
3. 指出初始集合的构造器。
向该构造器传递一个集合，让可以使用集合中的元素初始化ArrayList对象。
该构造器会先检查作为参数传递进去的集合的长度，如果不等于0，再判断它的类型是否是ArrayList，如果是则直接赋值给elementData，如果类型不符合，那么调用Arrays的copyof方法将传递的集合中的元素复制到elementData数组。当然，如果传递进去的集合长度等于0，那么会把elementData初始化为EMPTY_ELEMENTDATA。
public ArrayList(Collection c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
动态扩展
在了解了ArrayList的构造器之后，再来看看ArrayList是如何实现动态扩展数组大小的吧！
当需要向ArrayList容器中存放对象时，可以调用add方法，它在ArrayList中的定义如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private int size;
可以看到它第一步调用了ensureCapacityInternal方法，传递size + 1作为参数。由名称可以看出该方法的作用是确保内部容量。定义如下：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
该方法内部首先通过calculateCapacity方法计算出数组所需的容量minCapacity，然后判断是否需要执行grow()方法：
private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
这里可以看出，如果elementData的初始值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即如果使用无参数构造函数初始化ArrayList，则默认初始化容量为10。
如果需要的容量minCapacity大于原数组的长度elementData.length，就会执行grow方法，该方法就是ArrayList动态数组扩展的核心。它的定义如下：
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
新的容量计算公式是：
int newCapacity = oldCapacity + (oldCapacity >> 1);
可以看出，通过执行该计算公式，新容量是原有容量的1.5倍。
如果扩展1.5倍之后还是没有满足所需容量，那么就将所需容量作为新容量。
最后会使用Arrays.copyof方法创建一个新数组，然后将原始数组中的元素复制到新的数组中。
总结以下动态扩展：
1. 如果初始化ArrayList时没有指定初始值
那么当第一次执行add方法时，数组的长度会被默认初始化成10。再继续往容器中添加元素时，容器的容量不会改变，直到容器中的元素个数到达10。当第是一个元素添加进容器的时候，容器的容量就会被扩展成15（计算公式10 + 10>>1 得出）。
2. 如果初始化ArrayList时指定了初始值
那么当容器中元素的个数没有达到指定的初始值大小之前，不会扩展容量。当容器中的元素个数达到指定的初始值时，再向容器中添加元素，容量扩展就会发生。跟上面的过程一样。
3. 新的容量
默认情况下，扩容后的数组容量为原数组容量的1.5倍；如果仍然没有达到要求的大小（使用 addAll() 方法时可能会出现这种情况），则将容量扩大到要求的容量。
移除元素
当我们需要移除ArrayList中的元素时候，我们通常会调用remove方法（当然，还有其他移除方法）。这个方法有两个重载方法：remove(int index)和remove(Object o)。
1. remove(int index)方法
remove(int index)方法首先会进行范围检查，也就是调用了rangeCheck方法去检查。如果索引值大于当前ArrayList的size大小，就会抛出索引越界异常（IndexOutOfBoundsException）提示。
然后再获取要移动的长度numMoved，如果numMoved大于0，调用System类的arraycopy复制数组。如果numMoved等于0，说明是将最后一个值移除，只需要将最后一个值置为null即可，不需要移动数据。
该方法会将移除的值返回。该方法的定义如下：
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2. remove(Object o)方法
该方法会以要移除的对象是否为null来分别处理。内部的逻辑是一样的：都是通过for循环找到要删除的元素的索引Index，然后调用fastRemove方法来做移除操作。
仔细看fastRemove方法，会发现它和remove(int index)方法几乎一样。这个方法不会去调用rangeCheck方法做范围检查，也没有返回值。这一点该方法的注释上也说明了。
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;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
以上两个移除方法中，发生数据移除后都会调用System的arrayCopy方法，将园数组复制成一个新数组。
System.arraycopy(elementData, index+1, elementData, index, numMoved);
这里的index + 1是指源数组的开始位置，index是目标数组的开始位置，numMoved是需要复制的长度。这是由于index对应是被删除的元素，因此从index + 1的元素都将被复制到从index开始的目标数组中。
线程安全问题
在ArryList的类注释上有这样的说明：
注意该实现不是同步的。如果多个线程并发地访问同一个ArrayList实例，其中至少有一个线程结构性修改数组，它必须被外部地同步。（结构性修改是指任何添加或删除一个或多个元素，或者显式地调整备份数组（the backing array）的大小；仅仅设置（setting）元素的值不算是结构性修改。） 这通常是通过在自然地封装列表（naturally encapsulates the list）的某些对象上同步来实现的。
什么是“naturally encapsulates the list”呢？我在stackoverflow上找到一个回答：
“naturally encapsulates the list”的意思是：一个对象的一个字段是list，但是这个list是不允许公开访问的，也就是说，是一个私有字段。
以上的回答还举了一个停车的例子。代码示例如下：
class ParkingLot{
private ArrayList spots;
public boolean park(int spotNumber, Car car){
if(spots.get(spotNumber) == null){
spots.set(spotNumber, car);
return true;
}
return false;
}
}
在这个例子中，ParkingLot封装了列表spots。如果你要尝试调用 park()，你会希望在 ParkingLot 对象上进行同步，以防止两个线程试图同时将汽车停在同一地点。
在ArrayList的类注释上还提示：
如果没有这样的对象存在，这个列表应该使用Collections类中的synchronizedList方法”包装"起来。而且这最好是在创建时完成，以防止意外不同步地访问列表。
List list = Collections.synchronizedList(new ArrayList(...));
ArrayList线程安全处理
1. 使用ArrayList类注释上提到的Collections中的synchronizedList方法
该方法将ArrayList转换成线程安全的容器后再使用。
List
2. 为add方法加锁
synchronized (mutex) {
resultList.add(value);
}
3. 使用线程安全的 CopyOnWriteArrayList
线程安全的 CopyonWriteArrayList 可以代替线程不安全的 ArrayList。
List
总结
这篇文章对ArrayList的继承关系、构造器、动态扩展过程、移除元素、线程安全问题做了一些简要的梳理。在此只是作为一个学习记录，以供日后查阅使用。
参考资料：
1. How ArrayList Works Internally in Java | Tech Tutorials
2. [JDK] JDK source code analysis-ArrayList - Programmer All
3. Deep Analysis of an ArrayList-Java
4. 多线程场景下使用 ArrayList，这几点一定要注意！
5. java - Synchronizing ArrayList - Stack Overflow
6. Java多线程编程-（3）-线程本地ThreadLocal的介绍与使用
