ArrayList源码分析
ArrayList简介
我们知道，ArrayList是基于数组实现的List类，完全支持List接口的全部功能，底层实质上就是一个Object[]数组。从源码注释的第一行“Resizable-array implementation of the List interface”中，可以看出ArrayList是List接口的可变长数组实现，即这是一个动态数组，与普通的数组相比，它可以实现容量的动态增长。至于其他的特征，我们可以从类的定义中得到：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable这是ArrayList的类结构层次图：
由以上信息，我们可以知道：
- ArrayList：表明ArrayList支持泛型
- extends AbstractList：继承了AbstractList
- implements List：实现了List
- implements RandomAccess：实现了RandmoAccess接口，表明其支持快速随机访问，即可以通过元素的序号快速获取元素对象
- implements Cloneable：实现了Cloneable接口，表明其可以重写clone()方法实现对象的深拷贝
- implements java.io.Serializable：实现java.io.Serializable接口，表明其支持序列化，能通过序列化进行传输
但是与Vector不同，ArrayList不是线程安全的。
ArrayList属性
/**
* 默认初始化容量，为10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 当指定容量为0时，返回该空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 调用无参构造函数时，默认返回该空数组，与前者空数组的不同在于:前者是用户指定容量为0
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存添加到ArrayList中的元素
* ArrayList的容量就是该数组的长度
* 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA时，当第一次添加元素进入ArrayList时，数组将扩容至DEFAULT_CAPACITY，即10
* 被标记为transient，表示在对象被序列化的时候不参与序列化过程
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
*ArrayList当前包含的元素个数，而非容量
* @serial
*/
private int size;ArrayList构造方法
ArrayList提供了三种构造方法：
- ArrayList(int initialCapacity)
- ArrayList()
- ArrayList(Collection
<? extends E>c)
(1) ArrayList(int initialCapacity)
传入参数，则指定ArrayList的初始化容量。如果传入参数>=0，则使ArrayList初始化，如果传入参数小于0，则抛出异常IllegalArgumentException。
/**
* 构造一个指定初始化容量为initialCapacity的空ArrayList
*
* @param initialCapacity ArrayList的指定初始化容量
* @throws IllegalArgumentException 如果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);
}
}(2) ArrayList()
不传入参数，则使用默认无参构建方法创建ArrayList对象。
/**
* 构造一个空ArrayList
*
* 源码中注释的是“Constructs an empty list with an initial capacity of ten”，即构造一个容量为10的空ArrayList，这里的意思应该指的是当进行第一次add时，elementData将会变成默认的容量：10。但在没有add的时候，创建ArrayList对象不指定容量，默认调用该无参构造函数，应该返回的是容量为0的空Object[]数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}(3) ArrayList(Collection<? extends E> c)
构造一个包含指定 collection 的元素的ArrayList。
/**
* 构造一个包含指定 collection 的元素的ArrayList，这些元素是按照该 collection 的迭代器返回它们的顺序排列的
*
* @param c 其元素将放置在此列表中的 collection
* @throws NullPointerException 如果指定的 collection 为 null
*/
public ArrayList(Collection<? extends E> c) {
//将collection对象c转换成数组，然后将数组的地址的赋给elementData
elementData = c.toArray();
//更新size的值，同时判断size的大小
if ((size = elementData.length) != 0) {
//size>0，则执行Arrays.copy方法，把collection对象的内容深拷贝到elementData中
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果size=0，直接将空对象EMPTY_ELEMENTDATA的地址赋给elementData
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}ArrayList常用方法
add方法——add(E e)
/**
* 添加元素到ArrayList末尾
*
* @param e 被添加的元素
* @return true
*/
public boolean add(E e) {
//确认容量，如果不够，容量加1。注意：只加1，保证资源不被浪费
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}所以add(E e)应该有两个步骤：首先进行空间容量检查，如果有需要再进行扩容，然后插入元素至ArrayList末尾。
那么具体怎么实现扩容的呢？
/**
* 确定ArrarList的容量
*
* @param minCapacity 想要的最小容量
*/
//这是一个public方法，是一个让用户能手动设置ArrayList容量的方法，不参与动态扩容的过程
public void ensureCapacity(int minCapacity) {
//如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，最小扩容量为DEFAULT_CAPACITY，否则为0
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);
}
}
//私有
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果数组是调用无参构造函数，即容量为0的空数组
//所需的最小容量就是默认容量10
//即我们所说的调用无参构造函数直到第一次add时，才进行数组扩容
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//否则返回指定的最小容量
return minCapacity;
}
//私有
//数组容量检查，不够时则进行扩容，只供类内部使用
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//私有
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 确保指定的最小容量 > 当前数组的长度
// overflow-conscious code
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
/**
* 数组可被分配的最大容量。当需要的数组尺寸超过VM的限制时，可能导致OutOfMemoryError
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩容，保证ArrayList至少能存储minCapacity个元素
*
* @param minCapacity the desired minimum capacity
*/
//私有
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//右移一位相当于除以2，所以这句代码就等于int newCapacity = oldCapacity + oldCapacity / 2；即容量扩大为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果仍然小于minCapacity，则直接让newCapacity 等于minCapacity，而不再计算1.5倍的扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果超过最大容量MAX_ARRAY_SIZE，则调用hugeCapacity方法
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//即复制原数组内容到一个新容量的数组里。这里Arrays.copyof方法实际是调用System.arraycopy方法。
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 进行大容量分配
*/
//私有
//如果minCapacity大于最大容量MAX_ARRAY_SIZE，则返回Integer的最大值。否则返回MAX_ARRAY_SIZE。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}从源码和注释中，可以看出数组扩容实质上是通过私有的方法ensureCapacityInternal(int minCapacity) -> ensureExplicitCapacity(int minCapacity) -> grow(int minCapacity)来实现的，我们可以对扩容方法总结如下：
- 进行空间检查，决定是否进行扩容，以及确定最少需要的容量。如果确定扩容，就执行grow(int minCapacity)，minCapacity为最少需要的容量。
- 第一次扩容，逻辑为newCapacity = oldCapacity + (oldCapacity >> 1)，即在原有的容量基础上增加一半。
- 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。
- 对扩容后的容量进行判断，如果大于允许的最大容量MAX_ARRAY_SIZE，则将容量再次调整为MAX_ARRAY_SIZE。至此扩容操作结束。
还有两点值得注意的地方：
- 在进行扩容计算的时候使用了位运算，因为位运算是底层运算，计算机运算是以二进制为基础，而十进制运算在计算时会被转换成二进制再进行运算，这个转换过程就会导致运行速度降低。所以通过二进制移位可以提高运算速度。
- 扩容的实质是是使用了Arrays.copyOf()，即创建了一个新的数组，然后将旧数组上的元素copy到新数组，这是一个很大的消耗，所以在我们使用ArrayList时，最好能预计数据的大小，在第一次创建时就预先指定容量。
到这里，我们应该可以很清楚的知道ArrayList底层扩容的原理了。
add方法——add(int index, E element)
/**
* 在指定位置插入元素。当前位置的元素以及index之后的元素全部后移一位
* @param index 即将插入元素的位置
* @param element 即将插入的元素
* @throws IndexOutOfBoundsException 如果索引超出size
*/
public void add(int index, E element) {
//越界检查
rangeCheckForAdd(index);
//确认容量，如果不够，容量加1。注意：只加1，保证资源不被浪费
ensureCapacityInternal(size + 1); // Increments modCount!!
//对数组进行复制处理，从index位置开始复制size-index个元素到从index+1位置开始，目的就是空出index的位置插入element，并将index后的元素位移一个位置
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//将指定的index位置赋值为element
elementData[index] = element;
//数组长度+1
size++;
}所以add(int index, E element)应该有三个步骤：首先进行越界检查，然后进行空间容量检查，如果有需要再进行扩容，最后完成插入操作。
越界检查如下：
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}扩容操作同add(E e)。
remove(int index)
/**
* 删除指定索引index的元素
*
* @param index 被删除元素的索引
* @return 被删除的元素
* @throws IndexOutOfBoundsException 如果参数指定索引>=size,抛出越界异常
*/
public E remove(int index) {
rangeCheck(index);
//修改次数+1
modCount++;
//记录index处的元素
E oldValue = elementData(index);
//删除指定元素后，需要左移的元素个数
int numMoved = size - index - 1;
//如果有，就移动（被删除的元素直接被覆盖）
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//size-1，给最后一个位置null
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));
}该方法的步骤总结：
- 检查索引是否越界
- 将索引后的元素全部左移一位（实际上是覆盖）
- 将索引为size-1的元素赋为null(否则对应对象一直不会被回收)
至此，我们发现有两个检查越界的方法，分别为rangeCheckAdd()和rangeCheck()，做其对比：
//检验索引是否合法(校验了上限和下限)(index可以等于size(0<=index<=size))
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//检验索引是否合法(只校验了上限)(index不能等于size(index<size))
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
rangeCheckForAdd方法用于add(int index, E element)和addAll(int index, Collection
<? extends E>c)方法中检验索引是否合法；很明显，添加时index是不能超出集合的范围，同时他的下标也不能为负数。rangeCheck方法用于get、set、remove等方法中检验索引是否合法；应判断当前集合index是否大于数组长度，此时这个集合是存在的，所以他不需要去判断他的index小于零，只需要判断是否大于当前index。这里把get(-1)这样的越界检查交给了数组的访问。
get(int index)
/**
* 返回索引为index的元素
*
* @param index 需要返回的元素的索引
* @return the element at the specified position in this list 返回该index元素
* @throws IndexOutOfBoundsException 越界异常
*/
public E get(int index) {
//越界检查
rangeCheck(index);
//返回索引为index的元素
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}set(int index, E element)
/**
* 将指定索引的旧值修改为新值
*
* @param index 需要修改的值的index
* @param element 新值
* @return the element previously at the specified position 旧值
* @throws IndexOutOfBoundsException 越界异常
*/
public E set(int index, E element) {
//越界检查
rangeCheck(index);
//记录旧值
E oldValue = elementData(index);
//赋新值
elementData[index] = element;
//返回旧值
return oldValue;
}当然还有一些其他不怎么常用的方法，这里就不逐一分析啦～