ArrayList 源码分析

ArrayList的内部实现是Object数组，当插入对象时会检查数组长度是否够，不够会创建个更大的数组并拷贝原来数组的所有元素。检索速度快；插入、删除速度慢：被插入或删除的元素离ArrayList尾部越远，耗费的性能会越大（因为移动的子数组越大）。

size()和数组的长度是不同的：
size是指有效元素的个数，小于或等于数组的长度。

1. toArray方法

将ArrayList实例中的所有元素拷贝到一个数组中

如果目标数组的长度小于ArrayList的长度，则根据数组的类型生成一个新的数组并拷贝；
否则就调用System.arraycopy方法复制数据，如果目标数组的长度大于ArrayList的长度，数组中在list后面的第一个位置被赋为null。

public <T> T[] toArray(T[] a) {
	if (a.length < size)
		// Make a new array of a's runtime type, but my contents:
		return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	System.arraycopy(elementData, 0, a, 0, size);
	if (a.length > size)
		a[size] = null;
	return a;
}

测试代码：

	ArrayList list = new ArrayList();
	list.add("Disable");
	list.add("the");
	list.add("current");
	list.add("thread");

	String[] array = new String[3];
	//String[] array = new String[4];
	//String[] array = new String[6];
	String[] arrayCopy = (String[])list.toArray(array);
	// when 3: false
	// when 4, 6: true
	System.out.println(arrayCopy == array);
	// when 3, 4: ["Disable", "the", "current", "thread"]
	// when 6: ["Disable", "the", "current", "thread", null, null]
	System.out.println(Arrays.toString(arrayCopy));

2. trimToSize方法

// 和ensureCapacity相对应，去除空余的位置，节省存储空间
public void trimToSize() {
	modCount++;
	int oldCapacity = elementData.length;
	if (size < oldCapacity) {
		elementData = Arrays.copyOf(elementData, size);
	}
}

3. ensureCapacity方法

// 通过新建更大的数组并拷贝原来的元素来实现扩容。
public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
		Object oldData[] = elementData;
		int newCapacity = (oldCapacity * 3)/2 + 1; // 增长因子
		if (newCapacity < minCapacity) // 如果长度还不够，使用参数大小
			newCapacity = minCapacity;
		// minCapacity is usually close to size, so this is a win:
		elementData = Arrays.copyOf(elementData, newCapacity); // 新建数组并拷贝原来的所有元素到新数组上
	}
}

4. clone方法

public Object clone() {
	try {
		ArrayList<E> v = (ArrayList<E>) 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();
	}
}

测试clone方法：

private static class Representative {
	String name;

	public Representative(String name) {
		this.name = name;
	}

	// Getter and setters are omitted
}

private static void testClone() {
	ArrayList<Representative> list = new ArrayList<Representative>();
	Representative representative = new Representative("Hence");
	list.add(representative);
	ArrayList<Representative> listClone = (ArrayList<Representative>) list.clone();
	System.out.println(list.get(0) == listClone.get(0));
	representative.setName("whenever");
	System.out.println(listClone.get(0).name); // whenever
}

可以看出，clone方法实现了浅度复制。

5. get和set方法

public E set(int index, E element) {
	RangeCheck(index);

	E oldValue = (E) elementData[index];
	elementData[index] = element;
	return oldValue;
}

public E get(int index) {
	RangeCheck(index);

	return (E) elementData[index];
}

get和set都会首先检查index有没越界，set返回的是被替换的数据。

6. add方法

public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
}

public void add(int index, E element) {
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	// 首先确保检查数组大小足够
	ensureCapacity(size+1);  // Increments modCount!!
	// 把index和以后的元素都后移一位，性能会大幅下降
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	// index位置存储指定对象的引用
	elementData[index] = element;
	size++;
}

addAll方法

public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray(); // 集合对象转换成数组
	int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount
	System.arraycopy(a, 0, elementData, size, numNew); // 追加到尾部
	size += numNew;
	return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException(
		"Index: " + index + ", Size: " + size);

	Object[] a = c.toArray(); // 集合对象转换为数组
	int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount

	int numMoved = size - index; // 后移的元素的个数
	if (numMoved > 0)
		System.arraycopy(elementData, index, elementData, index + numNew,
				 numMoved); // index+numNew为后移的幅度

	System.arraycopy(a, 0, elementData, index, numNew); // 拷贝需要添加的数组到index位置
	size += numNew;
	return numNew != 0;
}

7. remove方法

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

	modCount++;
	E oldValue = (E) elementData[index]; // 暂存被删除元素

	int numMoved = size - index - 1; // 需要移动的元素的个数
	if (numMoved > 0)
		System.arraycopy(elementData, index+1, elementData, index,
				 numMoved); // index+1和之后的元素前移一位
	elementData[--size] = null; // Let gc do its work

	return oldValue;
}

// List是有序且可以有重复元素的，该方法会删除符合的第一个元素
public boolean remove(Object o) {
	// 优化：对null元素单独进行处理
	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;
}

// 和remove(int index)类似，不同的是少了越界检测和返回被删除的元素
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; // Let gc do its work
}

// 删除从fromIndex到toIndex(不包括)之间的元素
protected void removeRange(int fromIndex, int toIndex) {
	modCount++;
	int numMoved = size - toIndex; // 需要移动的元素个数
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved); // toIndex和以后的元素移到fromIndex位置

	// Let gc do its work
	int newSize = size - (toIndex-fromIndex); // 新的大小
	while (size != newSize) // 后面的几个位置清空
	    elementData[--size] = null;
}

测试remove方法：

private static void testRemoveNull() {
	ArrayList<String> list = new ArrayList<String>();
	list.add(null);
	list.add("queen");
	list.add(null);
	list.add(null);
	System.out.println(list); // [null, queen, null, null]
	list.remove(null);
	System.out.println(list); // [queen, null, null]
}

8. readObject和writeObject方法

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();
    }
}

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
	// Read in size, and any hidden stuff
	s.defaultReadObject();

	// Read in array length and allocate array
	int arrayLength = s.readInt();
	Object[] a = elementData = new Object[arrayLength];

	// Read in all elements in the proper order.
	for (int i=0; i<size; i++)
		a[i] = s.readObject();
}