集合之ArrayList源码分析
ArrayList是内部使用数组实现的一个集合，它可以自动扩容，因此，我们可以将ArrayList看作是一个动态数组。因为内部使用的是数组，ArrayList做遍历查询的时候速度会比较快，但是添加、移除数据的时候都需要移动元素，特别是添加操作并且需要扩容的时候，会对数组进行拷贝，因此效率比较差。此外，ArrayList不是线程安全的，所以建议在多线程中不要使用它，而去选择CopyOnWriteArrayList或者其它的线程安全的集合。本文基于Android-23源码分析。
源码解析
先来看看ArrayList的继承和实现关系
public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {
}
在这里可以看到ArrayList是支持泛型的，它实现了Cloneable，Serializable， RandomAccess接口，并且继承了 AbstractList<E>抽象类(实现了List集合)。
AbstractList<E>:提供了add，remove，clear等方法给到ArrayList去实现；
Cloneable：通过实现clone()方法，能够实现克隆对象；
Serializable：ArrayList支持序列化，和反序列化，实现Serializble接口之后能够进行序列化传输；
RandomAccess:它是一个标记接口，接口内没有定义任何内容，它支持快速随机访问，具体什么意思，后面会讲到。
先来看看ArrayList的成员变量以及构造函数：
/**
* 数组最小的扩容大小
*/
private static final int MIN_CAPACITY_INCREMENT = 12;
/**
* ArrayList内部数组的大小
*/
int size;
/**
* ArrayList内部使用的数组
*/
transient Object[] array;
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
public ArrayList() {
array = EmptyArray.OBJECT;
}
public ArrayList(Collection<? extends E> collection) {
if (collection == null) {
throw new NullPointerException("collection == null");
}
Object[] a = collection.toArray();
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
//
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
以上代码就是ArrayList的成员变量和构造函数，比较简单，需要注意的是，array数组是利用transient来修饰的，transient的作用是被标记为transient的属性在对象被序列化的时候不会被保存。此外，ArrayList中是利用System.arraycopy（）方式来拷贝数组的，这是一种浅拷贝，它调用的方法是System中的native方法。
public static native void arraycopy(Object src, int srcPos,
Object dst, int dstPos, int length);
ArrayList添加
现在我们来看看add()方法：
@Override public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {//空间不够的时候需要扩容
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
add（）方法中，如果数组的空间不够添加的时候，需要进行扩容：
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
此外有一个modCount变量，这个变量是继承父类AbstractList的，它的作用是记录对数组元素进行添加，删除的一个变量，最终的作用是进行Iterator操作的时候判断是否抛出ConcurrentModificationException。
添加集合的方法也差不多：
@Override public boolean addAll(Collection<? extends E> collection) {
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newSize;
modCount++;
return true;
}
@Override
public boolean addAll(int index, Collection<? extends E> collection) {
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}
addAll(Collection<? extends E> collection) 方法先去将传入的集合转换为数组，然后判断数组的大小是否为0，数组不为空的时候定义一个表示新数组大小的变量，判断是否需要扩容，然后拷贝数组，最后修改modCount的变量值并返回修改成功。addAll(int index, Collection<? extends E> collection)方法与之比较类似就不一一说明了。
ArrayList移除
@Override public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {//判断数组下标是否越界
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}
@Override public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
}
return false;
}
@Override protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex == toIndex) {
return;
}
Object[] a = array;
int s = size;
if (fromIndex >= s) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " >= size " + size);
}
if (toIndex > s) {
throw new IndexOutOfBoundsException("toIndex " + toIndex
+ " > size " + size);
}
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " > toIndex " + toIndex);
}
System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
int rangeSize = toIndex - fromIndex;
Arrays.fill(a, s - rangeSize, s, null);
size = s - rangeSize;
modCount++;
}
remove（）方法也需要和add（）方法一样，在修改成功的时候，也需要将modCount值给修改。此外，removeRange（int fromIndex,int toIndex）方法将两个下标之间的元素给移除。在上面的代码中我们看到，remove掉单个元素的时候是直接将这个元素设置为null，如a[s] = null;而removeRange方法中的移除调用的是Arrays.fill(a, s - rangeSize, s, null)方法：
public static void fill(Object[] array, int start, int end, Object value) {
Arrays.checkStartAndEnd(array.length, start, end);
for (int i = start; i < end; i++) {
array[i] = value;
}
}
因为传递的Object是null，所以也是通过循环将数组里面需要移除的元素赋值为null。
ArrayList查找
通过get()方法去拿到指定小标的元素：
@SuppressWarnings("unchecked") @Override public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}
查询是否数组中是否包含某个元素，通过代码我们发现，ArrayList是可以保存null的值：
@Override public boolean contains(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
}
返回指定元素的下标，这里有两种方法实现：indexOf（）和lastIndexOf（），同样的，我们通过这两个函数的代码发现，可以ArrayList可以保存相同的元素值。
@Override public int indexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;
}
}
}
return -1;
}
@Override public int lastIndexOf(Object object) {
Object[] a = array;
if (object != null) {
for (int i = size - 1; i >= 0; i--) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (a[i] == null) {
return i;
}
}
}
return -1;
}
除了，上面获取元素的方法，我们还可以通过ArrayList的内部类ArrayListIterator来迭代获取元素，删除元素。
ArrayListIterator
先来看看ArrayList中iterator的定义：
@Override public Iterator<E> iterator() {
return new ArrayListIterator();
}
private class ArrayListIterator implements Iterator<E> {
/** Number of elements remaining in this iteration */
private int remaining = size;
/** Index of element that remove() would remove, or -1 if no such elt */
private int removalIndex = -1;
/** The expected modCount value */
private int expectedModCount = modCount;
public boolean hasNext() {
return remaining != 0;
}
@SuppressWarnings("unchecked") public E next() {
ArrayList<E> ourList = ArrayList.this;
int rem = remaining;
if (ourList.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (rem == 0) {
throw new NoSuchElementException();
}
remaining = rem - 1;
return (E) ourList.array[removalIndex = ourList.size - rem];
}
public void remove() {
Object[] a = array;
int removalIdx = removalIndex;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (removalIdx < 0) {
throw new IllegalStateException();
}
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak
removalIndex = -1;
expectedModCount = ++modCount;
}
}
在上面的代码我们可以看到，ArrayListIterator是继承与Iterator的，在ArrayListIterator内部定义了几个局部变量：remaining表示迭代器中元素的大小，removalIndex表示将要被删除的元素下标，expectedModCount迭代器中修改统计。
我们看到ArrayListIterator中有两个方法next（）和remove（）：
next（）方法中，先会去判断expectedModCount是否等于ArrayList中的modCount，如果不一致就会抛出ConcurrentModifcationException异常，接下来会去判断数组是否为空，如果为空将会抛出NoSuchElementException异常。如果没有抛出异常，则返回ArrayList对应下标的元素。
remove也有next（）方法中的判断，如果没有异常抛出，接下来会进行数组拷贝，设置移除的元素为null，重置removalIndex变量，修改expectedModCount变量对应的值。
在这里我们看到这里expectedModCount != modCount之后会抛出ConcurrentModifcationException异常，这种并发修改异常有没有什么方法规避？
1，在使用iterator迭代的时候使用synchronized或者Lock进行同步；
2，使用CopyOnWriteArrayList代替ArrayList。
3，不要在循环中删除，添加数组元素，采用标记方式。
看完了ArrayListIterator之后，我们再来看看equels（）方法：
@Override public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof List)) {
return false;
}
List<?> that = (List<?>) o;
int s = size;
if (that.size() != s) {
return false;
}
Object[] a = array;
if (that instanceof RandomAccess) {
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object ethat = that.get(i);
if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
return false;
}
}
} else { // Argument list is not random access; use its iterator
Iterator<?> it = that.iterator();
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object eThat = it.next();
if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
return false;
}
}
}
return true;
}
我们看到equals方法中，如果传入的是标记接口RandomAccess，将会使用ArrayList中的get（）方法获取元素，如果不是RandomAccess类型将会走iterator，通过next去获取元素。这有什么区别？
首先，我们都知道foreach这个语法糖内部是iterator实现的，顺序访问的时候效率更高，而实现RandmoAccess接口的类实例，随机访问效率较高。
其它
set（）：
@Override public E set(int index, E object) {
Object[] a = array;
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
a[index] = object;
return result;
}
hashCode（）：
@Override public int hashCode() {
Object[] a = array;
int hashCode = 1;
for (int i = 0, s = size; i < s; i++) {
Object e = a[i];
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
ensureCapacity（）：
public void ensureCapacity(int minimumCapacity) {
Object[] a = array;
if (a.length < minimumCapacity) {
Object[] newArray = new Object[minimumCapacity];
System.arraycopy(a, 0, newArray, 0, size);
array = newArray;
modCount++;
}
}
ensureCapacity(int minimumCapacity),这个方法可以对ArrayList低层的数组进行扩容，如果明确知道ArrayList中的数组需要多大，ensureCapacity()会比较有优势，特别是大一些数据的时候，因为它只需要一次扩容，而默认的扩容方法会进行多次扩容操作。
clear（）：
@Override public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);
size = 0;
modCount++;
}
}
在这里我们看到，clear()方法也会将所有的元素值设置为null，并且将ArrayList的size设置为0，最后把modCount的值修改。
到这里我们基本上将ArrayList的源码分析完了。
