1. 概述
ArrayList可以理解为动态数组，随着向ArrayList中不断添加元素，容量能自动增长。ArrayList和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，所以其可以保证在 O(1) 复杂度下完成随机查找操作。但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢，Vector中的方法由于添加了synchronized修饰，因此Vector是线程安全的容器，但性能上较ArrayList差，因此已经是Java中的遗留容器。
2. 源码分析
2.1 构造方法
ArrayList有两个构造方法，一个是无参，另一个需传入初始容量值。相关代码如下：
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
上面的代码比较简单，两个构造方法做的事情并不复杂，目的都是初始化底层数组elementData。区别在于无参构造方法会将elementData初始化一个空数组，插入元素时，扩容将会按默认值重新初始化数组。而有参的构造方法则会将elementData初始化为参数值大小（>= 0）的数组。一般情况下，我们用默认的构造方法即可。倘若在可知道将会向ArrayList插入多少元素的情况下，应该使用有参构造方法。按需分配，避免浪费。
2.2 add()
对于数组（线性表）结构，插入操作分为两种情况。一种是在元素序列尾部插入，另一种是在元素序列其他位置插入。ArrayList的源码里也体现了这两种插入情况。相关代码如下：
/** 在元素序列尾部插入 */
public boolean add(E e) {
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将新元素插入序列尾部
elementData[size++] = e;
return true;
}
/** 在元素序列 index 位置处插入 */
public void add(int index, E element) {
rangeCheckForAdd(index);
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 3. 将新元素插入至 index 处
elementData[index] = element;
size++;
}
对于在元素序列尾部插入，这种情况比较简单，只需两个步骤即可：
- 检测数组是否有足够的空间插入。
- 将新元素插入至序列尾部。
如果是在元素序列指定位置（假设该位置合理）插入，则情况稍微复杂一点，需要三个步骤：
- 检测数组是否有足够的空间。
- 将index及其之后的所有元素向后移一位。
- 将新元素插入至index处。
从上图可以看出，将新元素插入至序列指定位置，需要先将该位置及其之后的元素都向后移动一位，为新元素腾出位置。这个操作的时间复杂度为O(N)，频繁移动元素可能会导致效率问题，特别是集合中元素数量较多时。在日常开发中，若非所需，我们应当尽量避免在大集合中调用第二个插入方法。
对于变长数据结构，当结构中没有空余空间可供使用时，就需要进行扩容。在 ArrayList 中，当空间用完，其会按照原数组空间的1.5倍进行扩容。相关代码如下
/**
* 计算最小容量
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 扩容的入口方法
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // overflow-conscious code
if (minCapacity - elementData.length > 0) grow(minCapacity);
}
/**
* 扩容的核心方法
*/
private void grow(int minCapacity) { // overflow-conscious code
int oldCapacity = elementData.length;
newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError(); // 如果最小容量超过 MAX_ARRAY_SIZE，则将数组容量扩容至 Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
2.3 remove()
不同于插入操作，ArrayList 没有无参删除方法。所以其只能删除指定位置的元素或删除指定元素，这样就无法避免移动元素（除非从元素序列的尾部删除）。相关代码如下：
/**
* 删除指定位置的元素
*/
public E remove(int index) {
rangeCheck(index);
modCount++; // 返回被删除的元素值
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0) // 将index + 1及之后的元素向前移动一位，覆盖被删除值
System.arraycopy(elementData, index + 1, elementData, index, numMoved); // 将最后一个元素置空，并将 size 值减1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
/**
* 删除指定元素，若元素重复，则只删除下标最小的元素
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 遍历数组，查找要删除元素的位置
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/**
* 快速删除，不做边界检查，也不返回删除的元素值
*/
private void fastRemove(int index) {
modCount++;
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}
}
上面的删除方法并不复杂，这里以第一个删除方法为例，删除一个元素步骤如下：
- 获取指定位置index处的元素值；
- 将
index + 1及之后的元素向前移动一位； - 将最后一个元素置空，并将size值减 1；
- 返回被删除值，完成删除操作。
现在，考虑这样一种情况。我们往 ArrayList 插入大量元素后，又删除很多元素，此时底层数组会空闲处大量的空间。因为 ArrayList 没有自动缩容机制，导致底层数组大量的空闲空间不能被释放，造成浪费。对于这种情况，ArrayList 也提供了相应的处理方法，相关代码如下：
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
通过上面的方法，我们可以手动触发ArrayList的缩容机制。这样就可以释放多余的空间，提高空间利用率。
2.4 遍历
ArrayList实现了RandomAccess接口（该接口是个标志性接口），表明它具有随机访问的能力。ArrayList 底层基于数组实现，所以它可在常数阶的时间内完成随机访问，效率很高。对ArrayList进行遍历时，一般情况下，我们喜欢使用foreach循环遍历，但这并不是推荐的遍历方式。ArrayList具有随机访问的能力，如果在一些效率要求比较高的场景下，更推荐下面这种方式：
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
3. 其他细节
3.1 快速失败机制
在 Java 集合框架中，很多类都实现了快速失败机制。该机制被触发时，会抛出并发修改异常ConcurrentModificationException，这个异常大家在平时开发中多多少少应该都碰到过。
ArrayList迭代器中的方法都是均具有快速失败的特性，当遇到并发修改的情况时，迭代器会快速失败，以避免程序在将来不确定的时间里出现不确定的行为。
3.2 关于遍历时删除
遍历时删除是一个不正确的操作，即使有时候代码不出现异常，但执行逻辑也会出现问题。关于这个问题，阿里巴巴Java开发手册里也有所提及。这里引用一下：
【强制】不要在foreach循环里进行元素的remove/add操作。remove元素请使用Iterator方式，如果并发操作，需要对Iterator对象加锁。
Iterator<String> it= a.iterator();
while(it.hasNext()) {
String temp = it.next();
if(删除元素的条件) {
it.remove();
}
}
网友评论