ArrayList类源码分析

ArrayList源码分析

   ArrayList是以数组为基础实现的一个动态数组容器，通过以下的代码分析可知，一方面在ArrayList中添加或者删除元素(除了在数组容器末尾添加或者删除元素)，是需要移动大量元素的借助System.arraycopy()来实现拷贝移动，另一方面，由于数组实现基础，可依靠数组下标，可以实现随机访问，当然查找具体的元素，还是需要循环去查找的，再者ArrayList不是thread-safe的，在代码中无论是add,remove，get，都没有任何同步措施，在多线程环境下需要自己确保thread-safe。由此可知ArrayList适用于在任意位置添加，删除元素不多，要求随机访问的应用场景。

  代码分析主要罗列：ArrayList构造函数，remove(), add(), get()

1.ArrayList构造函数

   private transient E[] elementData;ArrayList使用对象数组元素来作为内部实现的基础数据结构。

 
  //ArrayList是以数组为基础实现的，采用的泛型编程，数组元素都是Object类型
  //初始化时主要是构造指定大小的数组，用于存储对象元素
  public ArrayList(int initialCapacity){
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = (E[])new Object[initialCapacity];
  }

 

//默认情况下ArrayList实现依赖的数组长度为10
   public ArrayList() {
    	this(10);
   }

  

 

 
  //使用另一个集合中的元素来初始化当前的List
   public ArrayList(Collection<? extends E> c) {
        size = c.size();
        // Allow 10% room for growth
        elementData = (E[])new Object[
                      (int)Math.min((size*110L)/100,Integer.MAX_VALUE)]; 
        c.toArray(elementData);
    }

2.ensureCapaciyt(int) | add(E) | add(int, E)分析

   ensureCapacity主要用来实现数组的动态扩容,每次扩容为原来大小的1.5倍，在add操作前调用，以确保数组容量够用。

public void ensureCapacity(int minCapacity) {

	modCount++;
	int oldCapacity = elementData.length;
        
        //如果当前数组的实际容量(oldCapacity)比当前要求的容量要小(minCapacity)
        //就需要进行扩容，申请新的数组空间，大小为minCapacity,并将原来数组空间中的元素拷贝
        //到新的数组空间当中。        
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
          
            //扩容因子为:1.5倍左右，每次需要扩容时，会将空间扩展为原来的1.5倍大小
	    int newCapacity = (oldCapacity * 3)/2 + 1;

            if (newCapacity < minCapacity)
		newCapacity = minCapacity;

	    elementData = (E[])new Object[newCapacity];
              
            //将数组元素转移到新申请的数组空间当中
	    System.arraycopy(oldData, 0, elementData, 0, size);
	}
}

  add(E)操作是向集合ArrayList中存储元素，在当前数组容器的尾部添加，不需要移动元素,返回true。

public boolean add(E o) {
        //调用ensureCapacity确保当前容量不小于(size + 1),size为容器中当前存储的实际元素个数.
	ensureCapacity(size + 1); 
        //将对象引用o保存到数组容器中，并++size.
	elementData[size++] = o;
	return true;
}

add(int , E)在ArrayList中的指定位置index，保存对象element.

public void add(int index, E element) {

        //检测指定位置的合法性
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);
        
        //将数组容器elementData中从index位置开始的元素，依次往后移动一个位置
        //也就是说经过arraycopy()后，index位置被空出来
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);

        //将对象element存储到数组容器的index位置上
	elementData[index] = element;
	size++;
}

3.remove(int) | remove(Object) | fastRemove(int) | removeRange(int,int)分析

  remove(int)用于删除ArrayList数组容器中指定位置int上的元素，并返回此元素.

public E remove(int index) {

	RangeCheck(index);

	modCount++;

	E oldValue = elementData[index];
        //numMoved需要移动的元素个数，也就是index后面的所有的元素个数
	int numMoved = size - index - 1;

        //将index后面的所有元素全部往前依次移动一个位置
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);

        //经过arraycopy的移位，数组容器的最个位置被腾空，
        //但是仍然持有某个对象的引用，需要把这个多余的引用置为null.
      	elementData[--size] = null; // Let gc do its work

	return oldValue;
}

remove(Object)删除指定的对象Object，在数组容器中，需要特别处理null对象，过程都是，首先在数组容器中循环查找某个对象，如果查找到则调用fastRemove()进行删除。

public boolean remove(Object o) {
	if (o == null) {
            for (int index = 0; index < size; index++)
		if (elementData[index] == null) {
		    fastRemove(index);
		    return true;
		}
	} else {
            //注意比较两个对象是否相等调用的是equals()，
            //如果此类对象没有重写equals（)
            //比较的是是否引用同一个对象，如果有重写，将比较对象内部状态.
	    for (int index = 0; index < size; index++)
		if (o.equals(elementData[index])) {
		    fastRemove(index);
		    return true;
		}
        }
	return false;
    }

fastRemove(int index)是相对于remove(int index)来说的，因为不需要进行index合法性检查和返回被删除的元素，所以它可以称为fast remove.fastRemove是private不能被外界访问，只是在remove(Object o)中被调用，因为remove(Object o)在调用fastRemove()时候已经确定了此对象的确存在才进行fastRemove()，所以是安全的，不需要检查。

 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
  }

removeRange(int, int)用于删除数组容器中指定下标范围内的元素

 
    protected void removeRange(int fromIndex, int toIndex) {
	modCount++;
	int numMoved = size - toIndex;
        //将从toIndex开始的元素依次拷贝到fromIndex位置上。
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

	// Let gc do its work
        //newSize为删除指定范围元素后，容器中所剩下的元素个数。
	int newSize = size - (toIndex-fromIndex);
        //将持有多余引用的元素位置(从size-1到newSize - 1)置为null，
        //让GC能够及时回收垃圾对象.
	while (size != newSize)
	    elementData[--size] = null;
    }

4.get(int)

get(int)用于获取ArrayList指定位置的元素，就是从数组中指定位置上取元素。

public E get(int index) {

        //RangeCheck(index)用于检查index在数组元素中位置是否合法(必须index < size)
	RangeCheck(index);

	return elementData[index];
}