[TOC]
一、 顶部注释分析
1.1 首句定义
- Resizable-array implementation of the
Listinterface：List接口的大小可变数组的实现
1.2 从注释中得到的结论
-
底层：
ArrayList是List接口的大小可变数组的实现，即implements List<E> - 是否允许null：ArrayList 允许null 元素
- 时间复杂度：size、isEmpty、get、set、iterator 和listIterator方法都以固定时间运行，时间复杂度为O(1)；而 add 和 remove 方法需要 O(n) 时间
- 容量：ArrayList 的容量可以自动增长
- 是否同步：ArrayList 不是同步的，即线程不安全
-
迭代器：ArrayList 的 iterator 和 listIterator 方法返回的迭代器是
fail-fast的，若修改会抛出ConcurrentModificationException异常
二、源码分析
2.1 定义
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- ArrayList<E>：说明支持泛型
- extends AbstractList<E> ：继承自 AbstractList
- implements List<E>：实现了List接口
- implements RandomAccess：支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
- implements Cloneable：可以调用 clone() 方法来返回实例的
field-for-field拷贝 - implements java.io.Serializable：具有序列化功能
2.2 字段
// 默认初始化容量10
private static final int DEFAULT_CAPACITY = 10;
// 当指定容量为0时，返回该共享空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 调用无参构造方法时，返回该默认数组
// 与EMPTY_ELEMENTDATA的区别：该值是在默认构造时返回，而EMPTY_ELEMENTDATA是在用户指定容量为0时返回
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存添加到ArrayList中的元素
* ArrayList的容量就是该数组的长度
* 当第一次有元素进入ArrayList中时，数组将扩容为DEFAULT_CAPACITY
* 被标记为transient，在对象被序列化的时候不会被序列化
*/
transient Object[] elementData; // non-private to simplify nested class access
// ArrayList的实际大小（数组包含的元素个数）
private int size;
/**
* 分派给arrays的最大容量
* 减去8是因为某些VM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致array容量大于VM的limit，最终导致OutOfMemoryError
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
2.3 构造方法
-
ArrayList(int initialCapacity)：构造一个指定容量为capacity的空ArrayList，容量为0则this.elementData = EMPTY_ELEMENTDATA，不为0则新建new Object[initialCapacity] -
ArrayList()：构造一个空数组，this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA -
ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
2.4 添加元素
- 添加元素分两个步骤：
- 空间检查，如果有需要进行扩容；
- 插入元素
public boolean add(E e)
{
ensureCapacityInternal(size + 1); // 容量检查，Increments modCount!!
elementData[size++] = e;
return true;
}
2.5 容量检查和扩容
- 若
elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取minCapacity为默认容量和传入容量参数之间的最大值； - 否则执行 3 进行明确的容量检查；
- 如果所需最小容量比当前数组长度还要大，则扩容；
- 第一次扩容为
newCapacity = oldCapacity + (oldCapacity >> 1)，即扩容为1.5倍； - 如果一次扩容后还不够则直接扩充到所需的 minCapacity；
- 如果容量超过 MAX_ARRAY_SIZE 则扩容至 MAX_ARRAY_SIZE 或抛出溢出的异常；
- 最后把原有数组复制到新容量的数组中
private void ensureCapacityInternal(int minCapacity)
{
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
{
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity)
{
modCount++;
// 所需最小容量比当前数组长度还要大，需要扩容
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);
}
2.6 get、set、remove、trimToSize
- 三者首先都需要进行范围检查
private void rangeCheck(int index)
{
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 范围检查通过后，get 直接返回元素
public E get(int index)
{
rangeCheck(index);
return elementData(index);
}
E elementData(int index)
{
return (E) elementData[index];
}
- set 用新值覆盖旧值，并返回旧值
public E set(int index, E element)
{
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- remove 删除指定元素，并将该元素之后的元素向左移动，并修改 size，最后返回旧值
- 将索引为 size-1 处的元素显示赋值为null，从而让GC能发挥作用。若不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收（深入理解 Java 虚拟机中有涉及）
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;
}
- 删除元素时不会减少容量，若希望减少容量则调用 trimToSize()
public void trimToSize()
{
modCount++;
if (size < elementData.length)
{
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
2.7 modCount
- modCount 继承于 AbstractList，它记录的是集合的修改次数，例如每次 add 或者 remove 它的值都会加1
- 它的作用是当执行一些迭代器操作时，由于ArrayList是非线程安全的，因此每次执行时：
- 设
expectedModCount = modCount - 执行迭代器
next或remove等操作时，先调用checkForComodification来检查expectedModCount和modCount是否相等，若不等则抛出异常
- 设
final void checkForComodification()
{
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
