Java ArrayList的用法（非常详细）

List 是一种线性的列表结构，它继承自Collection接口，是一种有序集合，List 中的元素可以根据索引进行检索、删除或者插入操作。

Java ArrayList

ArrayList（java.util.ArrayList）是用数组来实现的List，是最常见的列表之一。它与数组有着同样的特点：

• 随机访问（相对于顺序访问）效率高。
• 读快写慢，由于写的过程中需要涉及元素的移动，因此写操作的效率比较低。

本文将详细解释这两个特性是如何体现出来的，以及如何利用它们更好地使用 ArrayList。在介绍数组的实现之前，首先引入两个概念：随机访问和顺序访问。

随机访问（又称直接访问）：在一组长度为 n 的数据中，要找到其中第 i 个元素，只需要通过下标 i 就可以找到。

顺序访问：在一组长度为n的数据中，要找到其中第 i 个元素，只能从头到尾或者从尾到头遍历，直到找到第 i 个元素，需要依次查找 i 或 n-i 次。

数组就是常见随机访问结构，为什么数组能实现随机访问呢？这要从数组的内存存储结构来进行解析（数组在内存中占用连续的存储空间）。

给定一段数据，如果知道它的起始位置和数据长度，那么就可以很快地在内存中定位它。例如：一个 int 型数据，在 Java 语言中 int 的长度是 4 个字节（32 位），假设它的起始地址为 0x00000001，用下面方块表示：

0×00000001

显然，如果还有一个 int 数据紧跟着该方块之后，那么内存地址就该是 0x00000001+32，依次类推，可以知道一串连续的 int 数据的存储结构为：

0x00000001

0x00000033

0x00000065

0x00000097

...

这一连串的 int 数据就构成了一个 int 数组，可以注意到，数组的存储依然是顺序的。那么，要如何达到随机访问的效果呢？通过对上面的结构进行分析，可以发现两个规律：

1. 所有数据块的内存是连续的。
2. 所有数据块的长度是相同的。

由此，可以推论得出公式，设数据块下标为 i，则：

第 i 个元素的地址=起始地址+单位长度 x i

如此，就实现了通过下标i来查找指定数据块的功能。数组需要记录的数据只有两个：起始地址和单位长度。

引申：int 的长度在 Java 语言中是确定的，Object 的长度却是根据其内容来决定的，那么，一个 Object[] 数组要如何确定单位长度呢？

答案：Java 无需确定 Object 的长度，Object[] 数组保存的是各个 Object 的引用（也可以理解为指针），无论是任何类型的引用，其长度都是确定的（可能各个虚拟机使用不同的长度，但在一个虚拟机内部这个长度是固定的），使用下标获取引用，然后通过引用再来查找指定的数据。

下面将通过对源码的分析来讲解 ArrayList 的实现原理：

1. 父类和接口

1）java.util.AbstractList

java.ntil.AbstractList。该抽象类是大部分 List 的共同父类，它提供了一些基本的方法封装，以及通用的迭代器实现。

2）java.util.List

java.util.List。列表标准接口，列表是一个有序集合，又被称为序列。该接口对它内部的每一个元素的插入位置都有精确控制，用户可以使用整数索引（index）来查询。一般来说，列表允许重复元素，也可以插入 null 元素。

3）java.util.RandomAccess

java.util.RandomAccess。这是一个标记性质的随机访问接口，它没有提供任何方法。如果一个类实现了这个接口，那么表示这个类使用索引遍历比迭代器要更快（ArrayList、CopyOnWriteArrayList、Stack 和 Vector 都实现了这个接口）。

【示例1】Java 代码如下所示：

int size = 1999999;
List<String> list = new ArrayList<String>();

for (int i = 0; i < size; i++) {
    list.add(i + "");
}

long time = System.currentTimeMillis();
String r;
//遍历索引
for(int i = 0, len = list.size(); i < len; i++) {
    r = list.get(i);
}
System.out.println("遍历索引耗时:" + (System.currentTimeMillis() - time));
time = System.currentTimeMillis();

//迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    r = iterator.next();
}
System.out.println("迭代器遍历耗时:" + (System.currentTimeMillis() - time));

程序的运行结果为：

遍历索引耗时:12
迭代器遍历耗时:13

这表明索引遍历比迭代器要快，当然，这并不是 RandomAccess 接口本身的功能，而是 ArrayList 的具体实现来决定的，它仅仅是个“标记”，至于为什么ArrayList 索引遍历会比迭代器更快，将在后面说明。

4）java.lang.Cloneable

java.lang.Cloneable。用于标记可克隆对象，是一个常见接口，没有实现该接口的对象在调用Object.clone()方法时会抛出异常。

5）java.io.Serializable

java.io.Serializable。序列化标记接口，是一个常见接口，被此接口标记的类可以实现 Java 序列化和反序列化。

该接口没有任何内容，但是 Java 序列化里有一些默认成员变量和默认方法，会在序列化和反序列化的时候调用到。主要有如下几个方法：

/*在序列化时调用，可以将特定的类转换成自己需要的序列化格式*/
private void writeObject(java.io.ObjectOutputStream out)throws IOException
/*在反序列化时调用，可以将输入转换成特定的类*/
private void readObj ect(java.io.ObjectInputStream in)throws IOException,ClassNotFoundException
/*反序列化时调用，当遇到类似版本不一致之类的问题，为了使序列化成功，提供的一个缺省方法*/
private void readObjectNoData()throws ObjectStreamException

2. 成员变量和常量

ArrayList 有三个重要的成员变量和两个常量。

1）成员变量

①private transient Object[]elementData，elementData 是该 List 的数据域，其中被 transient 修饰表示这个变量不会被序列化，它提供给 Serializable 接口使用。Java 代码如下所示：

List<String> list = new ArrayList<String>();
list.add("string1");
list.add("string2");

//序列化list
File file = new File("f:/list");
if (!file.exists())
    file.createNewFile();
FileOutputStream fos = new FileOutputStream(file);
ObjectOutputStream out = new ObjectOutputStream(fos);
out.writeObject(list);
fos.close();
out.close();

//反序列化list
FileInputStream fis = new FileInputStream(file);
ObjectInputStream in = new ObjectInputStream(fis);
Object obj = in.readObject();
System.out.println(obj);
fis.close();
in.close();

运行结果为：

[string1，string2]

从运行结果可以发现，对 ArrayList 的序列化与反序列化都成功了。为什么 transient 没有生效？

其实它已经生效了，但这里涉及的是 Java 序列化接口另一个方法writeObject，在 ArrayList 源码里可以找到下面这部分奇怪的代码：

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {

    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out array length
    s.writeInt(elementData.length);

    // Write out all elements in the proper order.
    for (int i = 0; i < size; i++)
        s.writeObject(elementData[i]);
    if (modCount != expectedModCount){
        throw new ConcurrentModificationException();
    }
}

由此可见，ArrayList 实现了 Serializable 接口的 writeObject 方法，这个方法把 elementData 中的元素全部序列化到文件中了，但是这个方法是 private 的，在 ArrayList 中并没有在任何位置调用它。那么它是如何被调用的呢？当 list 被序列化时，序列化方法会反射调用该方法来替代默认的序列化方式。

下面的代码是 Java 序列化相关类 ObjectStreamClass 的代码片段，通过这个片段可以看出 writeObject 方法是通过反射机制来被调用的。

writeObjectMethod=getPrivateMethod(cl,"writeObject",
        new Class<?>[]{ObjectOutputStream.class },
        Void.TYPE);

那么为什么不直接用 elementData 来序列化，而采用上面的方式来实现序列化呢？

主要的原因是 elementData 是一个缓存数组，为了性能的考虑，它通常会预留一些容量，当容量不足时会扩充容量，因此，可能会有大量的空间没有实际存储元素。采用上面的方式来实现序列化可以保证只序列化实际有值的那些元素，而不序列化整个数组。

②private int size，size 表示当前 List 的长度。

注意，elementData 的 length 是必然大于或等于 size 的，这是因为 elementData 是存放数据的数组。一方面，数组尾部可能有不计入长度的 null 元素。另一方面，数组的 length 是固定的，如果每一次添加都需要扩容，那么这是巨大的消耗。所以，ArrayList 提供了一系列机制来维持数组的大小，并且提供了一个 size 变量来标识真正的 List 大小。

③protected transient int modCount=0，该成员变量继承自 java.util.AbstractList，记录了 ArrayList 结构性变化的次数。在 ArrayList 的所有涉及结构变化的方法中都会增加modCount的值，这些方法包括：add( )、remove( )、addAll( )、removeRange( )及clear( )。

2）常量

①private static final long serialVersionUID=8683452581122892189L

序列化版本 UID，根据这个名字能判断出它是提供给序列化接口使用的，该 UID 是为了维持序列化版本一致性的。设想，ArrayList 在某次升级后，多出了新的成员需要被序列化，那么在旧版本中序列化的内容就无法反序列化成新版本的 ArrayList 对象。

②private static final int MAX_ARRAY_SIZE=Integer.MAX_VALUE-8

数组长度的上限，这里设置的是最大整数 -8。

3. 构造方法

ArrayList有三个重载的构造方法：

public ArrayList(int initialCapacity)
public ArrayList()
public ArrayList(Collection<? extends E> c)

其中，initialCapacity 表示初始化的 elementData 的长度，如果使用无参构造，那么默认为10。当构造方法的参数为集合的时候，它会把 elementData 的长度设置等同为集合的大小，然后再复制集合的所有元素到 ArrayList 的 elementData 中。

下面重点介绍常用的几个方法的实现。

1）indexof/lastIndexof/contains方法实现

• indexof 方法用于查询指定对象的索引 index，实现的方式是对数组顺序遍历，调用指定元素的 equals 方法来比对，如果查询不到，那么返回 -1。
• lastIndexof 则于 indexof 相反，是对数组倒序遍历。
• contains 方法直接调用 indexof 方法，根据返回值是否为 -1 判断代查找的元素是否存在。

2）set/add/addAll方法实现

• set方法的实现很简单，即替换数组里的对应索引处的值。
• add和 addAll方法的实现相对复杂一些。首先要检查当前 elementData 的长度，如果添加后的大小超出 elementData 的长度，那么需要对elementData的容量进行修正。

这里重点讲解一下elementData容量修正的逻辑。容量修正主要是两个方向：多余和不足。

这里涉及的关键方法是grow(int)，该方法的 int 参数指定了“本次扩容所允许的最小容量”。在 ArrayList 里，除了外部直接调用 ensureCapacity 方法间接地调用外，grow 只会被 add 或 addAll 触发。此时，所需要的最小容量一定是超出当前 elementData 的长度的。

grow 的逻辑很简单。首先，找出当前容量，把新容量设置为旧容量的 1.5 倍，如果新容量比可用最小容量（形参）要小，那么设置新容量为最小容量；如果新容量比极限容量常量要大，那么设置为极限容量常量和最大的整型数中的大值。接着，使用该新容量初始化一个新的数组，将原有 elementData 中的元素等位复制过去。

3）remove/removeAl/retainAll方法实现

① remove 方法有两种重载形式：remove(int)和remove(Object)。

• 当形参为 int 时，表示移除位于指定 index 的数据，如果移除的不是最后一位，那么会调用 System.arrayCopy 方法把 index 之后的数据向前移动一位，该方法的返回值指向被删除的元素。由此可见 ArrayList 的 remove 方法效率比较低。
• 当形参为 Object 时，表示移除指定的对象，该方法会顺序遍历整个数组，找到第一个与之相等对象（使用该对象的 equals方法来判断两个对象是否相等），并执行类似 remove(int) 的操作。该方法的返回值表示删除是否成功。

② removeAll 方法用于移除指定集合里的所有元素。与之相对的 retainAll 方法则是会保留指定集合里存在的元素。

这两个方法都是调用 batchRemove(Collection,boolean)，区别是传入的参数值不同，removeAll 传入的是false，retainAll 传入的是true，这个方法的实现的核心逻辑如下所示：

final Object[]elementData=this.elementData;
int r=0,w=0;
for(;r<size;r++)
    if(c.contains(elementData[r])==complement)
        elementData[w++]=elementData[r];
if(w!=size){
    for(int i=w;i<size;i++)
        elementData[i]=null;
    size=w;
    modified=true;
}

为了便于理解，首先解释一下几个变量，elementData 是数据域数组，r 是已经读取过的索引，w 是已经写入过的索引，c 是集合形参表示指定的集合，complement 是 boolean 形参，false 表示 removeAll 反之则是 retainAll。

如果要实现这个功能，那么可以考虑以下流程：

1. 创建一个新的缓存数组，假设为 newArray。
2. 遍历 elementData，判断每一个元素是否被 c 包含。
3. 如果 complement 为 true，那么把包含的元素放进 newArray。
4. 如果 complement 为 false，那么把不包含的元素放进 newArray。
5. 用 newArray 来替换 elementData。

如此，即完成了功能。在 ArrayList 的实现中，使用的就是上述流程，只是对它进行了优化。

首先有两个前提，无论是 removeAll 还是 retainAll，最后得出的结果集中元素的个数一定小于或者等于 elementData 中原来元素的个数；而且结果集中原来数据的顺序是保持不变的。

基于这两个前提，理当可以使用 elementData 本身来做流程中的 newArray 缓存，简化后的 removeAll 流程如下所示：

1. 遍历 elementData，判断每一个元素 [r] 是否被 c 包含。
2. 如果包含，那么不做任何处理，判断下一个元素。
3. 如果不包含，那么将 elementData 的第 w 位替换成该 elementData[r]，w 递增 1。为什么可以这么做？因为 r 一定是大于等于 w 的，如果等于，那么等同于没有操作，如果是大于，那么说明之前的位数都属于“包含”的情况，是属于需要删除的数据。
4. 完成遍历后，清除 elementData 里 w 标号之后的所有元素。

同理就能理解 retainAll 流程，一定是把 2、3 里的包含判断条件取否。这样回头看看上面的代码，就更容易理解了。

思考一个问题，为什么要判断 if(w !=size) 呢？如果 w==size 成立，那么说明写入次数已经覆盖了整个 elementData，流程 4 就没有执行的意义了。

4. 迭代器

前面提到过 RandomAccess 接口是用于标记该 List 的，使用索引遍历会比迭代器遍历效率更高，那么是什么原因导致索引遍历有更高的效率呢？下面从两个方面来进行讲解：

1) 由于索引遍历使用get(int)方法来取数据，而 get(int) 方法直接从数组中获取数据，T1(n)=nθ(1)，因此遍历列表操作的时间复杂度为 O(n)。

2) 迭代器遍历使用 java.util.Iterator来实现。标准写法如下所示：

Iterator<String> iterator = list.iterator();

while (iterator.hasNext()) {
    r = iterator.next();
}

可以看到，hasNext() 方法和 next() 方法都被调用了 n 次，T2(n)=n(hasNext()+next())。

两种方法分析如下所示：

• hasNext()方法中判断了索引是否和 size 相等，hasNext()=θ(1)。
• next() 方法则进行了多个操作，分别为：取出索引元素，索引增加 1，声明一个本地变量 elementData，指向作为外部类的 ArrayList 里的 elementData，以及一系列比对。设一个常量 a 表示这些操作的开销，那么 next()=aθ(1)。

综上 T2(n)=(a+1)nθ(1)。其中 a 为某个常量，时间复杂度为 O(1)。由此可见，两种方式的时间复杂度一致，这说明无论用哪种，都不会出现数量级上的区别，但是 T1(n)<T2(n) 是确定的，只有当数据量很大的时候，这两种方法的性能差别才会体现出来。

我们知道 modCount 是用来统计 ArrayList 修改次数的，expectedModCount 则是在 Iteractor 初始化时记录的 modCount 的值。每次 Iteractor.next() 方法调用时，都会调用 checkForComnodification() 方法检查 ArrayList 是否被修改，如果发现 List 被修改，那么就会抛出异常。

实现fail-fast机制的主要代码如下所示：

if(modCount!=expectedModCount)
    throw new ConcurrentModificationException();