1.3　List集合实现——ArrayList

ArrayList集合是JCF中非常重要的集合之一，也是实际工作中最常使用的集合之一。ArrayList集合拥有与Vector集合类似的接口和操作逻辑（从JDK 1.2开始提供），但它不支持线程安全操作（Vector集合支持线程安全操作，但是基于线程安全的多线程操作性能不高）。ArrayList集合也支持随机访问，也就是说，ArrayList集合在单线程下对指定索引位上的数据读取操作的时间复杂度为O(1)。ArrayList集合的主要继承体系如图1-13所示。

1.3.1　ArrayList集合概述

ArrayList集合是程序员在单线程操作场景中最常使用的List集合之一。该集合的内部结构是一个数组，并且这个数组在需要的时候可以进行扩容操作，所以理论上ArrayList集合能存储任意数量的数据对象（但实际上受各种客观因素限制而无法实现）。ArrayList集合允许将数据对象添加到数组的任意有效索引位上，并且允许从数组的任意有效索引位上获取数据对象。描述ArrayList集合中重要全局变量和常量的源码如下。

关于transient修饰符的作用，本书默认各位读者已经知晓，这里不再赘述。从全局变量的定义方式来看，ArrayList集合和Vector集合的工作思路类似：都支持随机访问，都继承了AbstractList抽象类，都使用数组存储数据对象，但这两种集合在细节处理上存在较大差异。

1.3.2　ArrayList集合的初始化操作和扩容操作

本节主要讲解ArrayList集合的初始化操作和扩容操作，并且与前面已经介绍的Vector集合进行对比。首先讲解ArrayList集合的初始化方法，相关源码片段如下。

根据上述源码片段可知，如果在进行初始化时不指定ArrayList集合的容量，那么ArrayList集合会被初始化成一个容量为0的集合。对于上述源码片段中的默认构造方法，官方给出的初始化意义是“Constructs an empty list with an initial capacity of ten”。这是因为当ArrayList集合处于这种状态时，后续在向ArrayList集合添加新数据对象时，无论是使用add(E)方法，还是使用add(int, E)方法（或其他方法），ArrayList集合都会使用grow(int)方法将elementData数组扩容成一个新的容量为10的数组。

grow(int)方法是ArrayList集合实际进行扩容操作的方法。由于一个数组在完成初始化后，其容量不能改变。因此ArrayList集合实际的扩容机制是通过某种规则创建一个容量更大的数组，并且按照一定的逻辑将原数组中的数据对象依次复制（引用）到新的数组中。grow(int)方法的完整源码如下。

根据上述源码可知，ArrayList集合的扩容操作主要分为两种情况：在进行扩容操作前，ArrayList集合的容量值为0的情况和不为0的情况。

• 在进行扩容操作前，ArrayList集合容量值不为0。

这种情况就是以上源码片段中判定条件“ oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA”为true的情况。处理逻辑为，以传入的minCapacity参数值和原始容量默认的50%增量值的比较结果为依据进行扩容操作。一般会按照原始容量默认的50%增量值进行扩容操作。

• 在进行扩容操作前，ArrayList集合的容量值为0。

这种情况实际上就是ArrayList集合使用默认的构造方法刚完成初始化操作的情况——只要之前发生了一次添加操作，ArrayList集合就不会是这样的状态。

扩容操作中的两种逻辑场景如图1-14所示。

ArrayList集合内部的数组在长度为0的情况下进行数组引用的替换，严格来说都不能称为扩容操作，因为没有最关键的数据复制过程。但为了统一考虑处理逻辑，我们将其视为扩容操作的一种特殊场景。

1.3.3　ArrayList集合中的add(E)方法

ArrayList集合中的add(E)方法和Vector集合中的add(E)方法功能类似，其处理过程都可以概括如下。

如果集合中还有多余索引位可以存储数据对象，那么直接在数组最后一个有效索引位的下一个索引位上添加新数据对象；如果集合中没有多余的索引位可以存储数据对象，那么先进行扩容操作，再进行新数据对象的添加操作。

两种集合中的add(E)方法在一些处理细节上有所不同，具体如下。

两个add(E)方法都是在当前集合中的有效索引位（尾部）的下一个索引位上进行数据对象的添加操作，但两种集合定义记录尾部的属性不一样。ArrayList集合使用size属性记录尾部，Vector集合使用elementCount属性记录尾部。注意，这里的“尾部”并不是用elementData数组的length属性表示的。ArrayList集合中的add(E)方法的相关源码片段如下。

ArrayList集合中的add(E)方法并不是线程安全的，Vector集合中的add(E)方法，虽然加入了保证线程安全性的机制，但仍然不适合用于高并发场景中。两种集合在进行扩容操作时，它们的扩容逻辑也不相同。

ArrayList集合还为使用者提供了add(int, E)方法。使用add(int, E)方法，调用者可以在指定的有效索引位上插入一个新的数据对象，在插入新数据对象前，这个索引位上的数据对象会向后移动，源码如下。

add(int, E)方法和add(E)方法的工作差异在arraycopy()方法处才显现出来，具体来说，add(int, E)方法可以使用arraycopy()方法将数据对象的添加操作和指定索引位上数据对象的移位操作一次性处理完，如图1-15所示。

图1-15中的操作过程是在调用add(int, E)方法时集合容量充足的情况。如果集合容量不充足，那么首先进行扩容操作，然后使用arraycopy()方法将elementData数组中的指定索引位及后续索引位上的数据对象依次向后移动一位，最后将新的数据对象添加（引用）到指定的索引位上。

1.3.4　Vector集合与ArrayList集合对比

本节在介绍ArrayList集合的工作逻辑时，会刻意和Vector集合进行对比，因为这两种集合的结构、处理逻辑、应用场景都非常相似。

1. 对集合的内部结构进行对比

Vector集合和ArrayList集合的内部结构都是数组，甚至代表数组的变量名都一样（elementData）。Vector集合中数组的初始化容量值默认为10，并且使用者可以指定Vector集合的初始化容量值。

ArrayList集合中数组的默认初始化容量值也为10，也可以指定集合中数组的初始化容量值，但如果使用者没有指定初始化容量值，那么ArrayList集合中的elementData数组会被初始化为一个容量值为0的空数组。

2. 对扩容逻辑进行对比

Vector集合和ArrayList集合的扩容逻辑不同，因为两种集合对扩容平衡性的处理思路不一样。Vector集合默认采用当前容量的1倍大小进行扩容操作，而且Vector集合可以指定一个固定的扩容增量（capacityIncrement），但除非使用者很明确Vector集合即将承载的数据量规模，否则不推荐使用这种方法，因为固定的扩容增量要么导致频繁扩容，要么比必要扩容浪费更多的存储空间。

ArrayList集合在进行扩容操作时会将当前容量增大50%，并且扩容逻辑不能干预，除非扩容前容量值小于10（如果发生这样的情况，则首先扩容到10）。ArrayList集合的扩容逻辑相对动态，这保证了在扩容操作频率和扩容大小之间更好的平衡性。

3. 对线程安全性保证进行对比

Vector集合的线程安全性体现在该集合提供给外部调用者使用的读/写方法中都会使用synchronized修饰符进行修饰（Object Monitor模式），示例代码如下。

这种线程安全保证方式的锁粒度太过粗放，并且已经被本书后续要介绍的各种在高并发场景中使用的集合代替，所以不推荐为了保证线程安全性而使用Vector集合。

ArrayList集合并不是线程安全的，官方也不推荐在多线程场景中使用ArrayList集合。如果使用者强行这么做，那么ArrayList集合很可能出现“脏数据”问题（实际上ArrayList集合会在迭代器中通过modCount全局变量标记的操作数进行一些避免“脏读”问题的限制，这是一种CAS思想的借鉴）。

4. 对序列化过程进行对比

Vector集合并没有对集合的序列化过程和反序列化过程进行特殊优化处理（虽然重写了readObject()方法和writeObject()方法）。在序列化过程中，当前elementData数组中多余的索引位会一起被序列化，这很明显产生了不必要的性能消耗。

ArrayList集合会对集合的序列化过程和反序列化过程进行针对性的优化处理，在对ArrayList集合进行序列化时，只会对elementData数组中已使用的索引位进行序列化，未使用的索引位不会被序列化；相对地，在原ArrayList集合中已被序列化的各个数据对象被反序列化成新的ArrayList集合中的数据对象时，新的elementData数组不会产生多余的容量，只有在下一次被要求向该集合中添加数据对象时，才会开始新一轮的扩容操作。