概述
ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。
size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
为追求效率，ArrayList没有实现同步(synchronized)，如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。
从以下几个方面进行分析：
- 核心结构与字段
- 构造函数
- 核心方法详解（增、删、改、查）
- 添加元素：
add(E e) - 扩容机制：
grow() - 获取元素：
get(int index) - 删除元素：
remove(int index) - 容量与大小的区别
- Fail-Fast（快速失败）机制
- 序列化策略
- 线程安全性
实现
底层数据结构
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
// transient关键字标记此字段，表示它不会被默认的序列化机制序列化。
// ArrayList有自己的序列化实现（writeObject/readObject）。
transient Object[] elementData; // non-private to simplify nested class access：非私有，以简化嵌套类的访问
/**
* The size of the ArrayList (the number of elements it contains).
* 记录ArrayList中实际存储的元素个数
* @serial
*/
private int size;elementData: 这是一个Object类型的数组，是ArrayList的底层数据结构。所有的元素都存储在这里。它被transient修饰，意味着ArrayList会自己控制序列化的过程，而不是使用 JVM 的默认机制。这么做的主要目的是为了效率，避免将数组中未使用的空间也序列化进去。size: 这是一个整型变量，用于记录当前ArrayList中包含的元素数量。size的值总是小于或等于elementData数组的长度（capacity）。
好的，我们来从源码的角度，深入地剖析一下 Java 中使用最广泛的集合类之一：ArrayList。
ArrayList 是 Java 集合框架（Java Collections Framework）的核心成员，它本质上是一个可动态调整大小的数组。理解它的源码能帮助我们编写更高效、更健壮的代码。
我们将从以下几个方面进行分析：
- 核心结构与字段
- 构造函数
- 核心方法详解（增、删、改、查）
-
- 添加元素：
add(E e) - 扩容机制：
grow() - 获取元素：
get(int index) - 删除元素：
remove(int index)
- 添加元素：
- 容量与大小的区别
- Fail-Fast（快速失败）机制
- 序列化策略
- 线程安全性
- 总结与使用场景
核心结构与字段
在 ArrayList 的源码中，最重要的就是两个实例字段：
Java
// java.util.ArrayList
// transient关键字标记此字段，表示它不会被默认的序列化机制序列化。
// ArrayList有自己的序列化实现（writeObject/readObject）。
transient Object[] elementData; // 非私有，以简化嵌套类的访问
private int size; // 记录ArrayList中实际存储的元素个数elementData: 这是一个Object类型的数组，是ArrayList的底层数据结构。所有的元素都存储在这里。它被transient修饰，意味着ArrayList会自己控制序列化的过程，而不是使用 JVM 的默认机制。这么做的主要目的是为了效率，避免将数组中未使用的空间也序列化进去。size: 这是一个整型变量，用于记录当前ArrayList中包含的元素数量。size的值总是小于或等于elementData数组的长度（capacity）。
还有一个重要的常量：
private static final int DEFAULT_CAPACITY = 10;DEFAULT_CAPACITY: 默认的初始容量。需要注意的是，在 JDK 1.7 之后，无参构造函数并不会立即创建一个长度为 10 的数组，而是采用了懒加载（Lazy Initialization）策略。
构造函数
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}ArrayList 提供了三个构造函数：
public ArrayList()(无参构造函数)
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}在 JDK 1.7 及以后，这个构造函数只会将 elementData 指向一个共享的空数组实例。它并不会立即分配任何内存。只有在第一次添加元素时，才会创建一个默认容量为 10 的新数组。这是一种优化，对于创建了但未使用或很少使用元素的 ArrayList 实例，可以节省内存。
public 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);
}
}这个构造函数允许你预先指定 elementData 数组的大小。如果你能预估到将要存储的元素数量，使用这个构造函数可以有效减少后续的数组扩容次数，从而提高性能。
public ArrayList(Collection<? extends E> c)(从集合创建)
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}这个构造函数会将传入集合中的所有元素复制到一个新的 elementData 数组中。
核心方法
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
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 void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// a. 获取旧容量
int oldCapacity = elementData.length;
// b. 计算新容量：新容量 = 旧容量 + (旧容量 >> 1)，即旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// c. 如果新容量仍然小于所需的最小容量，则直接使用最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// d. 对超大容量进行检查，防止溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// e. 最关键的一步：创建一个新数组，并将旧数组的元素复制过去
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;
}add(), addAll()
跟C++ 的vector不同，ArrayList没有push_back()方法，对应的方法是add(E e)，ArrayList也没有insert()方法，对应的方法是add(int index, E e)。这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。
- 触发时机：当
add一个元素时，发现size即将等于elementData.length。 - 扩容大小：新的容量通常是旧容量的 1.5 倍 (
oldCapacity + (oldCapacity / 2))。 - 实现方式：通过
Arrays.copyOf()创建一个更大的新数组，并将旧数组的所有元素复制到新数组中。这是一个成本较高的操作，因为它涉及内存分配和数据复制。
性能提示：正因为扩容成本高，所以在已知元素数量的情况下，使用 new ArrayList(initialCapacity) 初始化 ArrayList 是一个非常好的编程习惯。
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。
addAll()方法能够一次添加多个元素，根据位置不同也有两个版本，一个是在末尾添加的addAll(Collection<? extends E> c)方法，一个是从指定位置开始插入的addAll(int index, Collection<? extends E> c)方法。跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。 addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}set()
既然底层是一个数组ArrayList的set()方法也就变得非常简单，直接对数组的指定位置赋值即可。
public E set(int index, E element) {
rangeCheck(index);//下标越界检查
E oldValue = elementData(index);
elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
return oldValue;
}get()
get()方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];//注意类型转换
}remove()
remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋null值。
public E remove(int index) {
// 1. 检查索引是否越界
rangeCheck(index);
modCount++; // 修改次数加一，用于Fail-Fast机制
E oldValue = elementData(index); // 获取旧值
// 2. 计算需要移动的元素数量
int numMoved = size - index - 1;
if (numMoved > 0)
// 3. 使用System.arraycopy将后续元素向前移动一位
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
// 4. 将最后一个元素位置清空为null，帮助GC回收
elementData[--size] = null; // clear to let GC do its work
return oldValue; // 返回被删除的元素
}删除操作比 get 复杂得多：
- 它需要将被删除元素之后的所有元素都向前移动一位。
- 这个移动操作是通过
System.arraycopy()实现的，这是一个本地方法，效率很高，但仍然需要复制数据。 - 操作的时间复杂度取决于被删除元素的位置。删除末尾元素是 O(1)，但删除开头或中间的元素是 O(n)，因为需要移动大量元素。
关于Java GC这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。
trimToSize()
ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下:
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}indexOf(), lastIndexOf()
获取元素的第一次出现的index:
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}获取元素的最后一次出现的index:
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}Fail-Fast机制:
ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
- 任何会结构性修改（即改变
size或内部结构）列表的操作，如add,remove,clear等，都会使modCount自增。 - 当获取
ArrayList的迭代器 (iterator) 时，迭代器会记录下当前的modCount值，存放在expectedModCount字段中。 - 在迭代过程中（调用
next(),hasNext(),remove()），迭代器会检查modCount是否仍然等于expectedModCount。 - 如果不相等，说明在迭代期间，列表被其他方式（例如另一个线程，或者直接调用
list.add()）修改了，迭代器会立刻抛出ConcurrentModificationException异常。
重要：Fail-Fast 是一种检测机制，它不能保证并发修改一定会被检测到，它只是尽力而为。因此，它不应该被用来编写依赖此异常的并发程序。
序列化策略
如果使用默认序列化会发生什么？
Java 的默认序列化机制会尝试序列化对象的所有非瞬时（non-transient）和非静态（non-static）字段。如果 elementData 字段没有被 transient 关键字修饰，那么默认序列化会：
- 获取整个
elementData数组。 - 将数组中的每一个元素（包括那剩下的每个
null值）都写入到序列化流中。
这会带来两个显著的缺点：
- 空间浪费：序列化后的数据会包含大量无用的
null信息。在上面的例子中，我们浪费了 7 个对象引用的存储空间。如果ArrayList的容量非常大（比如 1,000,000）而实际元素很少，这种浪费将是巨大的。这不仅会占用更多的磁盘空间，也会消耗更多的网络带宽。 - 时间浪费：序列化和反序列化过程需要遍历整个
elementData数组，处理这些无用的null值，这会消耗不必要的 CPU 时间，降低了程序的性能。
前面提到 elementData 被 transient 修饰，ArrayList 通过自定义 writeObject 和 readObject 方法来控制序列化：
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
// ...
// 写入非transient字段（比如size）和非static字段
s.defaultWriteObject();
// 显式地写入 size 的值（为了兼容性）
s.writeInt(size);
// 只遍历并写入有效的元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
}writeObject 只会将 size 以及 [0, size-1] 范围内的有效元素写入流中。这样做的好处是节省空间和网络带宽，因为 elementData 中未使用的 null 元素（capacity > size 的部分）不会被序列化。
线程安全性
ArrayList 本身是非线程安全的。在多线程环境下，如果需要一个线程安全的列表，有以下几种选择：
Vector: 一个古老的、线程安全的动态数组。它的所有public方法都由synchronized修饰，性能较差，现在已不推荐使用。Collections.synchronizedList():
List<String> syncList = Collections.synchronizedList(new ArrayList<>());这是一个装饰器模式的应用，它返回一个线程安全的包装类。其内部通过在每个方法上加 synchronized 锁（锁对象是 mutex）来实现线程安全。性能与 Vector 类似。
CopyOnWriteArrayList: 推荐在“读多写少”的并发场景下使用。它在写操作（add, set, remove）时，会复制整个底层数组，在新数组上进行修改，然后将引用指向新数组。读操作则在无锁的情况下进行，非常高效。但写操作成本极高，且无法保证数据的实时一致性。
参考
- 深入Java集合学习系列: ArrayList的实现原理 http://zhangshixi.iteye.com/blog/674856
- Java ArrayList源码剖析 结合源码对ArrayList进行讲解 http://www.cnblogs.com/CarpenterLee/p/5419880.html