1、本文主要内容
- ArrayList源码简介
- ArrayList源码剖析
- 总结
之前总结过HashMap和LinkedHashMap，今天继续总结java容器，ArrayList。
2、ArrayList源码简介
ArrayList是基于数组实现的，数组长度能够动态增长的，非线程安全的容器，可以把它看成一个动态数组。
ArrayList非线程安全，如果需要考虑线程安全可以使用Vector类或其它线程安全队列。
ArrayList的优点和数组类似，它的查找效率非常高，根据数组下标获取数组某元素，时间效率为1。但插入与删除元素则效率较低。
3、ArrayList源码剖析
package java.util;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
//存储元素的数组
private transient Object[] elementData;
//数组中已经存储的元素的个数
private int size;
//构造函数，并生成一个特定长度的数组
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
//数组默认的构造函数，数组长度为10
public ArrayList() {
this(10);
}
//使用一个Collection来构造ArrayList，将Collection元素复制到数组中或者直接给elementData赋值
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
//减少数组的容量，如果实际存储的元素个数少于数组的长度，那么将原数组的内容复制，得到一个新数组，长度为实现存储元素的个数
//使用此方法可以减小数组占用的内容
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
//确保ArrayList的容量，minCapacity是希望的最小容量大小
public void ensureCapacity(int minCapacity) {
if (minCapacity > 0)
ensureCapacityInternal(minCapacity);
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//增长数组的长度，默认新的长度为 旧长度*3/2。
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
//返回ArrayList的长度，即ArrayList中已经存储的元素的个数
public int size() {
return size;
}
//如果ArrayList为0，则ArrayList为空
public boolean isEmpty() {
return size == 0;
}
//查看ArrayList是否包含某个值，实质是求某个值的索引数，如果索引大于等于0，则ArrayList包含此元素
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//查找某元素的索引值，分成两种情况，元素为null或不为null，遍历查找，并且是调用元素的equals方法
//由此可知，如果需要使用indexOf的方法，需要重写元素的equals方法
//ArrayList可以保存null元素
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//类似indexOf方法
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//克隆方法，需要特别注意的是，ArrayList的克隆方法，其实是一个深拷贝
//也就是说，ArrayList将数组的所有元素都复制了一遍，而不是引用赋值。
public Object clone() {
try {
@SuppressWarnings("unchecked")
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();
}
}
//返回一个数组，数组中保存着所有已经存储的元素，并且长度为size
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
//类似上一个方法，将ArrayList中数组的元素保存到a中，并且返回a（其中一种情况）
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;
}
// Positional Access Operations
//获取某个索引对应的元素
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
//获取某个索引下对应的数组的值，会先检查有没有数组越界
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//查找某个索引下的值，并且代替为新的值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//先查看数组容量是不是已经最大了，如果是，则增长数组的长度，最终调用之前的grow方法
//后在数组的后面添加一个新元素，索引为size，同时size加1
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//先判断数组会不会越界
//增加数组长度
//因为要在特定位置上添加一个元素，所以需要将此位置包括之后的元素向右移一位
//最后在索引处添加一个元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//先检查数组越界，然后找到当前要删除的元素
//因为删除了一个元素，所以元素右边的元素需要整体向左移 size - index - 1 个单位
//将数组elementData[--size]赋为空值
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; // Let gc do its work
return oldValue;
}
//删除一个特定的元素，遍历循环查找
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; // Let gc do its work
}
//清除数组内所有元素，同时将数组所有元素都赋值为空
public void clear() {
modCount++;
// Let gc do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
//将Collection中的元素全部添加到ArrayList中来
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
//将Collection中的元素全部添加到ArrayList中来,但添加的位置从index开始
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
//从fromIndex到toIndex，中间所有的元素都删除
//要移到的元素的个数，就是 size - toIndex，就是toIndex右边的值
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// Let gc do its work
int newSize = size - (toIndex-fromIndex);
while (size != newSize)
elementData[--size] = null;
}
//检查是否数组越界
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//检查是否数组越界
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//将ArrayList写入到一个对象输出流当中来，先写入数组长度，再将数组元素依次写入
//注意modCount代表着ArrayList的改动次数，如果在写入过程中ArrayList再次被改动，则当前写入失败
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();
}
}
//从对象输入流中读取出一个ArrayList，并为数组赋值
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();
}
}
4、总结
总体来说，ArrayList代码比较简单，就是数组的读写，从源码中我们也可以看到，如果是查找则非常方便，如果是删除或者是在指定位置上添加元素，则比较费劲，需要移动数组内的元素，所以ArrayList不太适合大量删除添加的情境。
另外，ArrayList中大量使用了一个接口，System.arraycopy，有必要看看这个接口，最重要的是明白这个接口的各个参数的意义。
/*
* @param src the source array，源数组，被复制的数组
* @param srcPos starting position in the source array，源数组复制的起始位置
* @param dest the destination array，目的数组
* @param destPos starting position in the destination data，添加元素到目的数组的起始位置
* @param length the number of array elements to be copied，要复制的长度
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
另外，数组也是会自动增长的，从代码中来看，每次增长的默认长度为：
int newCapacity = oldCapacity + (oldCapacity >> 1);
则是老长度的1.5倍。
最后，在代码中经常看到一个变量 modCount，它表示当前 ArrayList 被修改的次数，添加或删除则这个值会增加，那么它有什么用呢？因为ArrayList 非线程安全，比如说在调用writeObject方法进行对象流写入的时候，如果再对ArrayList 进行修改，则写入失败，它能直到一定的安全作用。甚至它的 Iterator 一般都会对这个值进行检查，如果变化了则报异常。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
