ArrayList源码解析

ArrayList是Java集合框架中，我们平时用得最多的一种实现类。它的底层其实是数组实现，只不过是动态改变数据大小，来看源码。

1.类定义

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

首先是泛型；然后继承AbstractList，它是List接口的最直接实现类，主要实现了Iterable接口，ArrayList的iterator()就由它实现；接着实现List接口，RandomAccess，Cloneable, java.io.Serializable这些接口。

 

2.成员变量

    private transient Object[] elementData;
    private int size;

elementData：用来存储数据的数组，ArrayList就是用它来存储数据。

size：数据的大小。

transient：表明序列化是不序列化此属性。如：

package serialize;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

public class TestTransient {
	
    public static void main(String[] args) {
    	UserInfo userInfo = new UserInfo("张三", "123456");
        System.out.println("before serialize: "+userInfo);
        try {
            // 序列化，被设置为transient的属性没有被序列化
            ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(
                    "UserInfo.out"));
            o.writeObject(userInfo);
            o.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
        
        try {
            // 重新读取内容
            ObjectInputStream in = new ObjectInputStream(new FileInputStream(
                    "UserInfo.out"));
            UserInfo readUserInfo = (UserInfo) in.readObject();
            //读取后psw的内容为null
            System.out.println("after serialize: "+readUserInfo.toString());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class UserInfo implements Serializable {
    private static final long serialVersionUID = 996890129747019948L;
    private String name;
    private transient String psw;

    public UserInfo(String name, String psw) {
        this.name = name;
        this.psw = psw;
    }

    public String toString() {
        return "name=" + name + ", psw=" + psw;
    }
}

3.构造方法

public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];
    }

带参数构造方法，initialCapacity初始化时指定数组大小。

public ArrayList() {
	this(10);
}

不带参数构造方法，默认大小10个。如果我们提前知道所需数组大小，可以自己指定，不然到后面动态改变大小肯定会影响性能。

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

参数为集合类的构造方法

4.add()方法

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

首先调用ensureCapacity（）确保数组容量足够大，然后再将e赋给索引为size的位置，size加1，来看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);
	}
    }

首先维护一个修改次数的变量modCount，它是在父类AbstractList中定义的，它在序列化的时候会用到。

然后比较我们传进来的数组大小minCapacity和数组原本的大小oldCapacity，如果小于oldCapacity说明数组容量够大，直接存储，反之则容量不够需要扩容，先扩容原来大小的一半加1，然后按这个大小创建一个个新的数组，把原来数组全部复制过来，再存储我们的数据。 

所以只要调了ensureCapacity（），就可能要扩容数组。

5.get()方法

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

	return (E) elementData[index];
    }

首先做个安全检查RangeCheck：

private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }

然后根据索引下列取值，因为是数组，所以ArrayList检索数据还是很快的。

6.remove()方法

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

它先判断要删除对象是否为null，然后调用的是fastRemove快速删除第N个元素:

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
    }

从第index+1个元素开始将后面每个元素往前挪一个位，并将剩下的最后一个元素置为null

7.contain()是否包含某个对象

public boolean contains(Object o) {
	return indexOf(o) >= 0;
    }

它调用了indexOf：

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

正向查找，返回元素最开始出现的索引值，还有反向查找的：

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

返回元素最后出现的索引值。

8.toArray()

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

当我们调用ArrayList中的 toArray()，可能遇到过抛出“java.lang.ClassCastException”异常的情况。如，将Object[]转换为的Integer[]则会抛出“java.lang.ClassCastException”异常，因为Java不支持向下转型。解决该问题的办法是调用 <T> T[] toArray(T[] contents) ， 而不是 Object[] toArray()。

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

通常如下来用：

// toArray(T[] contents)
public static Integer[] vectorToArray2(ArrayList<Integer> v) {
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);
    return newText;
}

9.trimToSize()

public void trimToSize() {
	modCount++;
	int oldCapacity = elementData.length;
	if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
	}
    }

按数组实际大小调整数据容量，有效使用内存空间。

10.ArrayList遍历方式

使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！ 

11.ArrayList线程不安全，如果是多线程可以使用Vector或CopyOnWriteArrayList。

12.ArrayList因为是数组实现，所以添加(如果是在指定位置)，删除，会重新拷贝元素，耗性能。如果添加，删除操作比较多可以使用LinkedList，因为它是基于链表实现，但检索性能没有ArrayList好。

参考自：

http://www.cnblogs.com/skywang12345/p/3308556.html

http://www.cnblogs.com/hzmark/archive/2012/12/20/ArrayList.html