集合框架2-ArrayList源码初探

由于笔者能力有限，本文也是学习的过程。部分内容可能会跳过，也希望大家可以不吝指导!～

---

源码版本JDK1.8

---

 数组是最常用的数据结构，相信大家对数组以及由数组实现的ArrayList的使用已经非常熟悉了。但是，很多人可能仅仅停留在使用的阶段。俗话说，“工欲善其事，必先利其器”。对工具充分的了解的过程，正是我们“利器”的过程。今天，我们就来通过对ArrayList源码的初步探究来深入地了解ArrayList。

I.类文件注释

/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)
 */

  List接口的大小可变数组的实现。实现了所有可选列表操作，并允许存放包括null在内的所有元素。除了实现List接口外，该类还提供了用来改变内部储存列表的数组的大小的方法。（该类大致上等同于Vector，除了该类是不同步的。）

/**
 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
 * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  The constant factor is low compared
 * to that for the <tt>LinkedList</tt> implementation.
 */

  size、isEmpty、get、set、iterator和listIterator操作都以常数的时间运行。add操作以均摊的常数时间运行，即添加n个元素需要O(n)时间。其他所有的操作都以线性的时间运行（大体上讲）。常数因子比LinkedList要低。

/**
 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to an ArrayList,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.
 */

 每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来平摊固定时间开销那样简单。

/**
 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.
 */

 在添加大量元素前，应用程序可以使用ensureCapacity操作来增加ArrayList实例的容量。这可以减少递增式再分配的数量。

/**
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
 * and at least one of the threads modifies the list structurally, it
 * <i>must</i> be synchronized externally.  (A structural modification is
 * any operation that adds or deletes one or more elements, or explicitly
 * resizes the backing array; merely setting the value of an element is not
 * a structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the list.
 */

 注意：该实现是不同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。

/**
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 */

 如果不存在这样的对象，则应该使用Collections.synchronizedList方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：
List list = Collections.synchronizedList(new ArrayList(…));

/**
 * <p><a name="fail-fast">
 * The iterators returned by this class's {@link #iterator() iterator} and
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
 * if the list is structurally modified at any time after the iterator is
 * created, in any way except through the iterator's own
 * {@link ListIterator#remove() remove} or
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 */

 该类的iterator和listIterator方法返回的迭代器是快速失败的：在创建迭代器之后，除非通过迭代器自身的remove或add方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

/**
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:  <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 */

 注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测bug。
 该类是Java集合框架的成员。

从上面类文件的注释中，我们可以得到如下一些信息：

• ArrayList是List接口的一个具体实现，是由数组实现的可变大小的动态数组；
• ArrayList元素是有序的、可重复的、并且支持null元素；
• size、isEmpty、get、set、iterator和listIterator方法都以固定的时间运行，时间复杂度为O(1)。add和remove方法的时间复杂度为O(n)。
• ArrayList的iterator和listIterator方法返回的迭代器是fail-first（快速失败）的。（快速失败机制：非并发的集合在进行迭代时，若有其他线程修改或增减了集合的内容，会立即抛出ConcurrentModificationException 异常。）
• ArrayList是不同步的。

II.源码解读

• ArrayList定义

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

上述定义表明：
1. ArrayList支持范型；
2.继承了AbstractList类，该类提供了List接口中骨干方法的实现；
3.实现了List、RandomAccess、 Cloneable和java.io.Serializable接口，表明其支持快速（通常是固定时间）随机访问，可以调用clone()方法来返回实例的field-for-field拷贝，有序列化功能。

• 域

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

初始化默认容量为10。

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};