java 源码解析--ArrayList

ArrayList

1.看源码前应该知道的知识点

/**
 * 
 */
package com.study.collection;

import java.util.ArrayList;
import java.util.Arrays;

/**   
 * 
 * @className ：ArrayListTestLearn  
 * @package : com.study.collection 
 * @Description ：解读ArrayList前必须知道的几点知识点   
 * @author：lgf   
 * @date ：2012 三月 12  15:31:48          
 * @version : 1.0
 */
public class ArrayListTestLearn {
	
	/**
	 * 可以把Collection中的数据以Object[]的形式返回
	 * @author lgf
	 * @Description: 接口Collection 的 toArray方法
	 * @CreateDate 2012 三月 12 16:18:12
	 * @lastModified 2012 三月 12 16:18:12
	 * @version 1.0
	 */
	public void collectionTOarray(){
		ArrayList<String> list = new ArrayList<String>();
		list.add("a");
		list.add("b");
		list.add("c");
		list.add("d");
		list.add("e");
		Object[] arr = list.toArray();
		print(arr);
	}
	
	/**
	 * 对Object[] obj 进行复制功能的实现
	 * 进行截取或扩充
	 * @author lgf
	 * @Description: Arrays.copyOf() 方法的使用
	 * @CreateDate 2012 三月 12 16:23:53
	 * @lastModified 2012 三月 12 16:23:53
	 * @version 1.0
	 */
	public void arraysCopyOf(){
		int length = 8;
		Object[] obj = new Object[5];
		obj[0] = "string";
		obj[1] = 1;
		//obj[2] = null;
		obj[3] = false;
		obj[4] = 1.2;
		print(obj);
		obj = Arrays.copyOf(obj, length);
		print(obj);
	}
	
	/**
	 * public static void arraycopy(
	 * 						  Object src, 源数组 要复制的数组
     *                        int srcPos, 源数组中的起始位置
     *                        Object dest,目标数组 要复制到的数组
     *                        int destPos,目标数据中的起始位置
     *                        int length) 要复制的数组元素的数量 
	 * @author lgf
	 * @Description: System.arraycopy() 的使用方法
	 * @CreateDate 2012 三月 12 16:43:24
	 * @lastModified 2012 三月 12 16:43:24
	 * @version 1.0
	 */
	public void systemArraycopy(){
		Object[] objOne = new Object[10];
		Object[] obj = {0,1,2,3,4,5,6,7,8,9,10};
		System.arraycopy(obj, 3, objOne, 2, 4);
		print(objOne);
		
	}
	
	/**
	 * @author lgf
	 * @Description: 输出数组里面数据
	 * @CreateDate 2012 三月 12 16:37:21
	 * @lastModified 2012 三月 12 16:37:21
	 * @version 1.0
	 * @param obj
	 */
	public void print(Object[] obj){
		for (Object o : obj) {
			System.out.println(o);
		}
	}
	public static void main(String[] args) {
		ArrayListTestLearn learn = new ArrayListTestLearn();
		learn.collectionTOarray();
		learn.arraysCopyOf();
		learn.systemArraycopy();
	}
}

2.源码

package java.util;
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
	 * 用来存放数据的Object[]  由此可知ArrayList是用过数组来存放数据的
     */
    private transient Object[] elementData;

    /**
     * 目前Object[] 存放的个数  ！= Object.length()
     */
    private int size;

    /**
     * 构造函数,进行初始化 ，小于0则报错
     */
    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来初始化
     */
    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);
    }

    /**
     * 将此 ArrayList 实例的容量调整为列表的当前大小
	 * modCount 每次进行修改时候都要调用 
     */
    public void trimToSize() {
		modCount++;
		int oldCapacity = elementData.length;
		if (size < oldCapacity) {
				elementData = Arrays.copyOf(elementData, size);
		}
    }

    /**
     * 如有必要，增加此 ArrayList 实例的容量，
	 * 以确保它至少能够容纳最小容量参数所指定的元素数
	 * 仅仅是必要，而且大小minCapacity 只是进行参考。
     * @param   minCapacity  要扩容的大小
     */
    public void ensureCapacity(int minCapacity) {
		modCount++;
		// 当前大小
		int oldCapacity = elementData.length;
		
		// 仅仅打算扩大的大小大于当前大小时候才需要扩容
		if (minCapacity > oldCapacity) {
			Object oldData[] = elementData;
			// 在原来基础上扩大1.5倍 + 1 作为新的扩容大小备选用
			int newCapacity = (oldCapacity * 3)/2 + 1;
			// 如果指定扩大的比基础上扩大1.5倍 + 1 还大则选用指定的
			if (newCapacity < minCapacity)
				newCapacity = minCapacity;
			// minCapacity is usually close to size, so this is a win:
			elementData = Arrays.copyOf(elementData, newCapacity);
		}
    }

    /**
     * 返回此列表中的元素数
     * @return the number of elements in this list
     */
    public int size() {
		return size;
    }

    /**
     * 如果此列表中没有元素，则返回 true 
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
		return size == 0;
    }

    /**
     * 如果此列表中包含指定的元素，则返回 true
	 * 通过判断指定对象在Object[] 中的位置。如果>=0 说明存在
     * @param o 要判断的对象
     */
    public boolean contains(Object o) {
		return indexOf(o) >= 0;
    }

    /**
     * 返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1
	 * 如果传递的是null 则判断数组里面是否存在null
	 * 否则就是根据equals方法进行判断
     */
    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;
    }

    /**
     * 返回此列表中最后一次出现的指定元素的索引，
	 * 或如果此列表不包含索引，则返回 -1
	 * 如果传递的是null 则判断数组里面是否存在null
	 * 否则就是根据equals方法进行判断
     */
    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 实例的浅表副本
     * @return a clone of this <tt>ArrayList</tt> instance
     */
    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();
		}
    }

    /**
     * 按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组
	 * 就是调用Arrays.copyOf(Object[] o,int size) 方法
     * @return包含此列表中所有元素的数组（按适当顺序）
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组
     *
     * @param a the array into which the elements of the list are to
     *          be stored, if it is big enough; otherwise, a new array of the
     *          same runtime type is allocated for this purpose.
     * @return an array containing the elements of the list
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this list
     * @throws NullPointerException if the specified array is 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;
    }

    // Positional Access Operations

    /**
     * 返回此列表中指定位置上的元素。 
     * @param  index 要返回元素的索引 
     * @return 此列表中指定位置上的元素
     * @throws 如果索引超出范围 (index < 0 || index >= size())
     */
    public E get(int index) {
		// 进行判断是否越界
		RangeCheck(index);
		return (E) elementData[index];
    }

    /**
     * 用指定的元素替代此列表中指定位置上的元素
     * @param index 要替代的元素的索引
     * @param element 存储在指定位置上的元素 
     * @return 以前位于该指定位置上的元素，旧值
     * @throws IndexOutOfBoundsException - 如果索引超出范围 (index < 0 || index >= size())
     */
    public E set(int index, E element) {
		//判断越界和保存旧值
		RangeCheck(index);
		E oldValue = (E) elementData[index];
		elementData[index] = element;
		return oldValue;
    }

    /**
     *将指定的元素添加到此列表的尾部
     * @param e 要添加的元素
     * @return 是否成功添加
     */
    public boolean add(E e) {
		ensureCapacity(size + 1);  // Increments modCount!!
		elementData[size++] = e;
		return true;
    }

    /**
     * 将指定的元素插入此列表中的指定位置。
	 * 向右移动当前位于该位置的元素（如果有）以及所有后续元素（将其索引加 1）。 
     * @param index 指定元素所插入位置的索引
     * @param element 要插入的元素
     * @throws IndexOutOfBoundsException  如果索引超出范围 (index < 0 || index > size())
     */
    public void add(int index, E element) {
		if (index > size || index < 0)
			throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
		ensureCapacity(size+1);  // Increments modCount!!
		//对elementData中index以后的所有元素向后移动一位
		//通过对同一个elementData进行操作实现的
		System.arraycopy(elementData, index, elementData, index + 1,size - index);
		elementData[index] = element;
		size++;
    }

    /**
     * 移除此列表中指定位置上的元素。向左移动所有后续元素（将其索引减 1）
     * @param index  要移除的元素的索引 
     * @return 从列表中移除的元素 
     * @throws IndexOutOfBoundsException如果索引超出范围 (index < 0 || index >= size())
     */
    public E remove(int index) {
		//越界判断
		RangeCheck(index);
		modCount++;
		// 获得要移除的元素
		E oldValue = (E) elementData[index];
		//移除点开始到最后一个元素之间的元素个数
		int numMoved = size - index - 1;
		if (numMoved > 0)
			// 在index后所有元素往前移动一位
			System.arraycopy(elementData, index+1, elementData, index,numMoved);
		elementData[--size] = null; // Let gc do its work设置为null 好回收
		return oldValue;
    }

    /**
     * 移除此列表中首次出现的指定元素（如果存在）。如果列表不包含此元素，则列表不做改动
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    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 remove method that skips bounds checking and does not
     * return the value removed.
     */
    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全部设置为null 大小size=0
		for (int i = 0; i < size; i++)
			elementData[i] = null;
		size = 0;
    }

    /**
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     * 按照指定 collection 的迭代器所返回的元素顺序，
	 * 将该 collection 中的所有元素添加到此列表的尾部。
	 * 如果正在进行此操作时修改指定的 collection ，那么此操作的行为是不确定的
     * @param c 包含要添加到此列表中的元素的 collection 
     * @return 如果此列表由于调用而发生更改，则返回 true 
     * @throws NullPointerException 如果指定的 collection 为 null
     */
    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;
    }

    /**
     * Inserts all of the elements in the specified collection into this
     * list, starting at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements to
     * the right (increases their indices).  The new elements will appear
     * in the list in the order that they are returned by the
     * specified collection's iterator.
     *
     * @param index index at which to insert the first element from the
     *              specified collection
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws NullPointerException if the specified collection is null
     */
    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);
		System.arraycopy(a, 0, elementData, index, numNew);
		size += numNew;
		return numNew != 0;
    }

    /**
     * Removes from this list all of the elements whose index is between
     * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
     * Shifts any succeeding elements to the left (reduces their index).
     * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
     * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
     *
     * @param fromIndex index of first element to be removed
     * @param toIndex index after last element to be removed
     * @throws IndexOutOfBoundsException if fromIndex or toIndex out of
     *              range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
     *              &gt; size() || toIndex &lt; fromIndex)
     */
    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(
			"Index: "+index+", Size: "+size);
    }

    /**
     * Save the state of the <tt>ArrayList</tt> instance to a stream (that
     * is, serialize it).
     *
     * @serialData The length of the array backing the <tt>ArrayList</tt>
     *             instance is emitted (int), followed by all of its elements
     *             (each an <tt>Object</tt>) in the proper order.
     */
    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();
        }

    }

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    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();
    }
}

3.重要点
1.默认初始化大小

 /**
     * 使用默认值进行构造,容器初始化大小为   10  .
     */
    public ArrayList() {
		this(10);
    }

2.进行扩容

   /**
     * 如有必要，增加此 ArrayList 实例的容量，
	 * 以确保它至少能够容纳最小容量参数所指定的元素数
	 * 仅仅是必要，而且大小minCapacity 只是进行参考。
     * @param   minCapacity  要扩容的大小
     */
    public void ensureCapacity(int minCapacity) {
		modCount++;
		// 当前大小
		int oldCapacity = elementData.length;
		
		// 仅仅打算扩大的大小大于当前大小时候才需要扩容
		if (minCapacity > oldCapacity) {
			Object oldData[] = elementData;
			// 在原来基础上扩大1.5倍 + 1 作为新的扩容大小备选用
			int newCapacity = (oldCapacity * 3)/2 + 1;
			// 如果指定扩大的比基础上扩大1.5倍 + 1 还大则选用指定的
			if (newCapacity < minCapacity)
				newCapacity = minCapacity;
			// minCapacity is usually close to size, so this is a win:
			elementData = Arrays.copyOf(elementData, newCapacity);
		}
    }

3.每次进行判断都要分null和非null

    /**
     * 返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1
	 * 如果传递的是null 则判断数组里面是否存在null
	 * 否则就是根据equals方法进行判断
     */
    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;
    }

4.移动和插入数据方法

    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);
		System.arraycopy(a, 0, elementData, index, numNew);
		size += numNew;
		return numNew != 0;
    }