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是以数组为基础实现的，采用的泛型编程，数组元素都是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);
   }

//默认情况下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);
  }

//使用另一个集合中的元素来初始化当前的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);
    }
}

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

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

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

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

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
 }

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

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

public E get(int index) {

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

    return elementData[index];
}