java ArrayList源码 上

   版本 jdk-7u71-windows-x64

 

          JavaSE7 ArrayList源码下：http://flyouwith.iteye.com/blog/2171047 

/**
 * 看下面这几个私有属性，就知道ArrayList实际上就是一个数组
 * 其（数组、ArrayList）数据结构就是一个简单的线性序列
 */
public class ArrayList<E> 
		extends AbstractList<E> //这个  extends AbstractCollection<E> implements List<E>
		implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
	private static final long serialVersionUID = 8683452581122892189L;

	/**
	 * 默认初始容量.
	 */
	private static final int DEFAULT_CAPACITY = 10;

	/**
	 * 空数组
	 */
	private static final Object[] EMPTY_ELEMENTDATA = {};

	/**
	 * 数组elementData 存储ArrayList的所有数据
	 */
	private transient Object[] elementData;

	/**
	 * size<=elementData.length,两者没什么特别关系 
	 * size是数组elementData中元素（E） 的个数 
	 */
	private int size;

	/**
	 * 构造方法1
	 * 构造一个与指定初始容量的空列表.
	 * 例：ArrayList<E> array = new ArrayList<E>(10000); 
	 * 这时候size=0,但是数组的容量是10000  
	 */
	public ArrayList(int initialCapacity) {
		super();
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
		this.elementData = new Object[initialCapacity];
	}

	/**
	 * 构造方法2
	 * api:构造一个空列表的初始容量10
	 * 我就不明白了，那里初始化容量大小了？、？？？？
	 * 明明是构造一个容量是0的数组
	 */
	public ArrayList() {
		super();
		this.elementData = EMPTY_ELEMENTDATA;
	}

	/**
	 * 构造方法3
	 * 可以放一个实现Collection接口的集合进去set、list
	 */
	public ArrayList(Collection<? extends E> c) {
		//  1.将集合转换成数组，elementData指向这个数组 
		elementData = c.toArray();
		//  2.设置size值     
		size = elementData.length;
	    //  3.判断ele..是不是Object数组,不是的话创建一个，将内容（基本类型的值，对象的引用）copy进新数组中，返回   
		if (elementData.getClass() != Object[].class)
			elementData = Arrays.copyOf(elementData, size, Object[].class);
	}

    

 

 下面看一下，构造方法3中的第一步（假设传进来的是一个ArrayList）和第三步。

/**
	 * ArrayList实现的 Collection接口中toArray()方法
	 */
		public Object[] toArray() {
			return Arrays.copyOf(elementData, size);
		}
	  /**
	   * 在Arrays类中找到的copyOf的方法
	   */
	    public static <T> T[] copyOf(T[] original, int newLength) {
	        return (T[]) copyOf(original, newLength, original.getClass());
	    }
	  /**
	   * 直接看这个吧，上面构造方法3的第三步调用的也是这个方法
	   */
	    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
			 //根据给定的paramClass数组类型，生成一个大小newLength的新数组
	        T[] copy = 
    		        //三目运算
	        		((Object)newType == (Object)Object[].class)
	        		//构造方法3的第三步走的这里
		            ? (T[]) new Object[newLength]
		            //Array.newInstance 是native的，看不到了		
		            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
	          //这个也是	native方法，x = Math.min(original.length, newLength)
	          //复制original[0~x]内容到copy[0~x]中，用这个操作数组还是很爽的	
	        System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
	        return copy;
	    }
	

  

 

  其实一般的构造方法3，第三步都会走。

ArrayList<String> array = new ArrayList<String>(Arrays.asList("a","b"));
		//对应构造方法3的第一步
		Object[] elementData = Arrays.asList("a","b").toArray();
		System.err.println(elementData.getClass());//输出class [Ljava.lang.String;

  

下面继续源码:对数组进行扩容

	/**
	 * 给数组瘦身，释放资源，确定数组大小不会改变时用这个.
	 * 生成一个新数组容量与元素个数一样  
	 */
	public void trimToSize() {
		//记录对arrayList的操作次数？ 源码下再介绍
		modCount++;
		if (size < elementData.length) {
			//上面介绍过了   
			elementData = Arrays.copyOf(elementData, size);
		}
	}

	/**
	 * 手动给数组扩容，生成一个容量不小于paramInt数组，然后将内容copy进去  
	 */
	public void ensureCapacity(int minCapacity) {
		int minExpand = (elementData != EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY;
		if (minCapacity > minExpand) {
			ensureExplicitCapacity(minCapacity);
		}
	}

	private void ensureCapacityInternal(int minCapacity) {
		if (elementData == EMPTY_ELEMENTDATA) {
			minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
		}
		ensureExplicitCapacity(minCapacity);
	}

	private void ensureExplicitCapacity(int minCapacity) {
		modCount++;
		if (minCapacity - elementData.length > 0)
			// 给定数值不能比当前数组容量小: 执行
			grow(minCapacity);
	}

	/**
	 * 数组分配的最大大小，超过的话取Integer.MAX_VALUE
	 */
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

	/**
	 * 执行扩容  
	 */
	private void grow(int minCapacity) {
		int oldCapacity = elementData.length;
		//自己会根据当前容量算出一个扩容值，跟给定值比较选择最大的   
		//移位操作符>> 参考：http://flyouwith.iteye.com/blog/2163032
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		if (newCapacity - minCapacity < 0)
			newCapacity = minCapacity;
		//限定数组最大的容量
		if (newCapacity - MAX_ARRAY_SIZE > 0)
			newCapacity = hugeCapacity(minCapacity);
		//继续copy  到一个新数组中
		elementData = Arrays.copyOf(elementData, newCapacity);
	}

	/**
	 * 限定数组最大容量不能超过Integer.MAX_VALUE=2147483647
	 */
	private static int hugeCapacity(int minCapacity) {
		if (minCapacity < 0) // overflow
			throw new OutOfMemoryError();
		return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
	}

 

 下面内容是一些基本方法

	/**
	 * 返回此列表的元素数量。
	 */
	public int size() {
		return size;
	}

	/**
	 * 是否只有一副皮囊 .
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 是否包含指定o
	 */
	public boolean contains(Object o) {
		return indexOf(o) >= 0;
	}

	/**
	 *  返回在数组中第一次出现的位置，没有找到返回-1
	 *  通过对象的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
	 *  从后面开始循环
	 *  通过对象的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实例。(元素
     * 本身并不是复制。)
	 * 数组存基本类型的值，对象的引用。  
     * 所以copy的不过是引用，都指向一个对
	 */
	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) {
			throw new InternalError();
		}
	}

	/**
	 * 返回一个数组,其中包含所有的元素在这个列表中
     * 顺序(从第一个到最后一个元素)。
	 * 对象copy引用
	 * 该方法基于数组的和基于集合的api之间充当桥梁。
	 */
	public Object[] toArray() {
		return Arrays.copyOf(elementData, size);
	}

	/**
	 * 新建一个数组，放到这里拷贝ArrayList中内容  
	 */
	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
		//如果给定数组容量小于size ，则生成一个大小是size的数组，然后把内容copy进去
		if (a.length < size)
			return (T[]) Arrays.copyOf(elementData, size, a.getClass());
		//否则直接copy，上面有介绍这个方法的含义 
		System.arraycopy(elementData, 0, a, 0, size);
		if (a.length > size)
			a[size] = null;
		return a;
	}

	// 返回数组指定位置的元素

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

	/**
	 * 在末尾添加元素。.
	 * 第一步上面有介绍这个方法。是否需要扩容
	 * 注意：size加1
	 */
	public boolean add(E e) {
		ensureCapacityInternal(size + 1); 
		elementData[size++] = e;
		return true;
	}

	/**
	 * 指定位置添加元素，从指定位置开始后面元素统一后移一位  .
	 * 这里不是用的for循环来移位，而是copy，即使这样也比LinkedList慢好多 
	 * 这个如果用for循环的话时间复杂度是O(this.size - index) copy应该是比这小的 
	 * 但是肯定比LinkedList 的O(1) 要大的多
	 * 注意：size加1  
	 */
	public void add(int index, E element) {
		rangeCheckForAdd(index);
		ensureCapacityInternal(size + 1);//检核是否越界
		System.arraycopy(elementData, index, elementData, index + 1, size - index);
		elementData[index] = element;
		size++;
	}

	/**
	 *  跟上面性质是一样的。把删除位置后面的元素统一向前移动一位
	 *  比LinkedList慢  
	 *  注意：size减1
	 */
	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; 

		return oldValue;
	}

	/**
	 * 删除第一次出现的指定元素从这个列表
	 * 通过for循环查找元素
	 */
	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; 
	}

	/**
	 * 清空，通过for循环
	 */
	public void clear() {
		modCount++;

		for (int i = 0; i < size; i++)
			elementData[i] = null;

		size = 0;
	}

	/**
	 * 添加一个集合到当前集合后面 
	 * 先把要添加的集合转变成数组，然后对this数组扩容，copy到this数组中
	 * 比LinkedList慢
	 */
	public boolean addAll(Collection<? extends E> c) {
		Object[] a = c.toArray();
		int numNew = a.length;
		ensureCapacityInternal(size + numNew); // 扩容
		System.arraycopy(a, 0, elementData, size, numNew);
		size += numNew;
		return numNew != 0;
	}

	/**
	 * 在指定位置插入集合.
	 * 先进行扩容，然后移位，之后把内容copy进来 
	 */
	public boolean addAll(int index, Collection<? extends E> c) {
		rangeCheckForAdd(index);

		Object[] a = c.toArray();
		int numNew = a.length;
		ensureCapacityInternal(size + numNew);  // 扩容

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

	/**
	 * 这是protected的不能用。。  
	 * remove区间的内容
	 * 先把fromIndex后的内容copy到toIndex后面  
	 * 然后把后面toIndex-fromIndex个数的元素清空
	 */
	protected void removeRange(int fromIndex, int toIndex) {
		modCount++;
		int numMoved = size - toIndex;
		System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);

		int newSize = size - (toIndex - fromIndex);
		for (int i = newSize; i < size; i++) {
			elementData[i] = null;
		}
		size = newSize;
	}

	/**
	 *  检核越界
	 */
	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));
	}

	/**
	 * 异常信息 .
	 */
	private String outOfBoundsMsg(int index) {
		return "Index: " + index + ", Size: " + size;
	}