ArrayList源码分析

前言

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

继承结构是这样

数据结构与扩容操作

既然名字是ArrayList，那么底层多多少少和数组有关。

先来看看构造函数里做了啥。

transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
private static final Object[] EMPTY_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);
	}
}

当构造函数的参数为空时，给成员变量elementData赋了一个空的数组。
当我们指定了初始大小的时候，如果参数大于0，那么elementData就是我们设的大小，如果等于0，那么还是赋了一个空的数组给elementData。

进行add操作时。

public boolean add(E e) {
	ensureCapacityInternal(size + 1);
	elementData[size++] = e;
	return true;
}

我们可以注意到一个ensureCapacityInternal的函数，这个函数是确保底层的数组有足够的空间进行增加的。

private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}

	ensureExplicitCapacity(minCapacity);
}

在ArrayList中还有一个成员变量是DEFAULT_CAPACITY，默认大小是10。
如果是无参数的new的ArrayList话而且是第一次调用add的话，那么minCapacity就会是10。
但是如果是下面再进行add的话，再进去这个函数，则是直接调用ensureExplicitCapacity函数。
不会在进行Math.max的操作了。
这里还是没有真正就行底层扩容操作。

再来看看ensureExplicitCapacity函数

protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;

	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

这里用到了modCount变量，这个在HashMap中也有看到，这个和fail-fast有关，下面会介绍。
下面还对minCapacity - elementData.length > 0进行了一次判断，因为现在的长度的数组可能还没用完，如果这样的话，那么不用扩容，直接用就行了。
还有一种情况就是minCapacity已经超过int最大值了，变成了负数了，那样也不会进行扩容。

关键是在grow函数中

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	// minCapacity is usually close to size, so this is a win:
	elementData = Arrays.copyOf(elementData, newCapacity);
}

这里才看到了真正的扩容操作。但是别急，在操作之前还需要进行判断作为保证。
这里有三个变量，和名字一样，

minCapacity就是这次扩容后的最小容量
newCapacity是最后进行扩容的大小，也就是最终扩容时用到的
oldCapacity是现在的大小。

现在我们在回去看add参数的话，会看到他调用的ensureCapacityInternal时的参数是当前的大小加1，注意，只是加了1而已，每次add都扩容的话，那么代价肯定会非常高的。

这里的溢出检查的newCapacity是现在的size加上size的一半。也就是原来的大小的3/2。
所以不出意外的话，大多数情况下，每次扩容的大小都是原来的大小的3/2。
那么我们还需要考虑特殊情况，就是溢出的情况。

如果newCapacity乘上了原来的3/2，超过了int的范围，变成了负数，那么就是newCapacity - minCapacity < 0为true了，那么newCapacity的大小就是minCapacity，也就是原来的大小加上了1。

如果没有溢出，但是比MAX_ARRAY_SIZE大，也就是在Integer.MAX_VALUE - 9 到Integer.MAX_VALUE之间。那么newCapacity的大小就是hugeCapacity的返回值。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) // overflow
		throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ?
		Integer.MAX_VALUE :
		MAX_ARRAY_SIZE;
}

这里如果minCapacity溢出了，也就是现在的size的大小已经是Integer.MAX_VALUE了，那么就抛出OutOfMemoryError了。

在hugeCapacity函数中，minCapacity和MAX_ARRAY_SIZE进行了比较，如果minCapacity大于MAX_ARRAY_SIZE但是还没有溢出，那么就直接扩容到Integer.MAX_VALUE。

看到这里我猜想了如果出现了极端的情况，就是add时size刚好是Integer的最大值会怎么样？
那时，minCapacity - elementData.length的结果是1，还是可以进入grow函数。最后进入hugeCapacity函数，最后抛出OutOfMemoryError。
给力。代码的鲁棒性很好。

fail-fast机制与遍历

上面我们提到一个变量modCount，每次我们进行add或者是进行一些其他的修改数组的操作时，这个参数就会加1。
在单线程中，这个当然是不会出错的。
但是在多线程中，我们知道如果我们在遍历时，可能会抛出ConcurrentModificationException。
这个异常就是提醒我们在遍历时，有其他的线程对数组进行了修改。

@Override
public void forEach(Consumer<? super E> action) {
	Objects.requireNonNull(action);
	final int expectedModCount = modCount;
	@SuppressWarnings("unchecked")
	final E[] elementData = (E[]) this.elementData;
	final int size = this.size;
	for (int i=0; modCount == expectedModCount && i < size; i++) {
		action.accept(elementData[i]);
	}
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
}

比如这个forEach方法，在进行操作前先记录当前的modCount大小，最后操作完比对现在的modCount，如果不一样，那么就抛出异常。

RandomAccess接口

这个接口是空的，只是做一个标记的作用。

1 2	public interface RandomAccess { }

什么标记呢，就是对实现了这类接口的类进行遍历时，

1 2	for (int i=0, n=list.size(); i < n; i++) list.get(i);

1 2	for (Iterator i=list.iterator(); i.hasNext(); ) i.next();

如果第一种遍历方式要比第二种快，那么他就应该实现RandomAccess接口，这样我们在使用的时候，在特定场景可能会根据是否实现了RandomAccess来进行遍历。
这个我们在比较LinkedList的时候就能理解了。
因为LinkedList是链表的方式，如果我们使用第一种遍历，那相当于每次get都从头开始找了。
所以LinkedList就不能实现这个接口。
而ArrayList底层是数组，所以直接get反而更快一点，而用第二种还需要进行一个SubList的构造。

其他

public void trimToSize() {
	modCount++;
	if (size < elementData.length) {
		elementData = (size == 0)
		  ? EMPTY_ELEMENTDATA
		  : Arrays.copyOf(elementData, size);
	}
}

这个方法很有意思，因为我们的扩容机制不是一个一个的增加的，一下子增加原来的3/2大小。
如果我们不再往里面增加元素的话，那么多出来的就很浪费。
这个方法就是去除多余的没设置值的空间。

public Object clone() {
	try {
		ArrayList<?> v = (ArrayList<?>) super.clone();
		v.elementData = Arrays.copyOf(elementData, size);
		v.modCount = 0;
		return v;
	} catch (CloneNotSupportedException e) {
		// this shouldn't happen, since we are Cloneable
		throw new InternalError(e);
	}
}

clone方法可以看到，做的是浅拷贝。

public E remove(int index) {
	rangeCheck(index);

	modCount++;
	E oldValue = elementData(index);

	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

	return oldValue;
}

这个方法，可以看到开销还是挺大的，那个注释很有意思，把后面缩小之后的引用置位null。
如果不置位null，仅仅是size-1的话，那么位于size位的对象无法被GC收集。
这样就会造成内存泄漏。

public void clear() {
	modCount++;

	// clear to let GC do its work
	for (int i = 0; i < size; i++)
		elementData[i] = null;

	size = 0;
}

clear方法并没有释放底层的数组，只是把每个引用置位null。