java.util.ArrayList源码解析

java集合框架图

20160918105654_491.gif

所属包

package java.util;

继承与实现关系

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

属性

//定义了一个Object类型的数组  
private transient Object[] elementData;  
  
//定义了一个指定Object数组大小的长度  
private int size;  
  
//数组可以分配的最大容量  
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

构造方法

构造方法1：

/** 
  * 构造一个带有初始化容量大小的空list  
  * initialCapacity : 输入参数为初始化容量        
  */  
public ArrayList(int initialCapacity) {  
    super();  
    //如果初始化容量小于0，那么就抛出一个非法参数异常。  
    if (initialCapacity < 0)  
            throw new IllegalArgumentException("Illegal Capacity: "+  
                                               initialCapacity);  
    //初始化指定容量的Object数组  
    this.elementData = new Object[initialCapacity];  
}  

构造方法2：

/**
  * 构造一个空的list，默认采用初始化容量为10  
  */  
public ArrayList() {  
    this(10);  
}  

构造方法3：

/**
  * 构造一个包含指定元素的list  
  */ 
public ArrayList(Collection<? extends E> c) {  
      //将集合框架转化为数组  
      elementData = c.toArray();  
      //指定数组的长度  
      size = elementData.length;  
      //此处如果输入参数传过来为null时，那么就会报空指针异常  
      if (elementData.getClass() != Object[].class)  
      //将c中的元素拷贝到elementData中  
            elementData = Arrays.copyOf(elementData, size, Object[].class);
  }  

方法

add 方法：

/**  
   * 在list的尾部添加元素  
   */  
public boolean add(E e) {  
       //如果容量不够，就进行扩容，扩容到size+1  
       ensureCapacityInternal(size + 1);    
       //类似于数据结构中的顺序表，在Object数组的尾部添加元素  
       elementData[size++] = e;  
       return true;  
}  

ensureCapacity 对外扩容的方法：

/**  
   * 增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所 
   * 指定的元素数。   
   */  
public void ensureCapacity(int minCapacity) {  
       if (minCapacity > 0)  
             ensureCapacityInternal(minCapacity);  
}  
    
private void ensureCapacityInternal(int minCapacity) {  
        modCount++;  
        //如果扩容的容量大于当前Object数组的长度，那么就进行扩容操作  
        if (minCapacity - elementData.length > 0)  
             grow(minCapacity);  
}  

grow 扩容方法：

/**  
   * 增加容量确保可以容纳下当前最少的元素参数  
   */  
private void grow(int minCapacity) {  
        //获取到原数组的长度  
        int oldCapacity = elementData.length;  
        //将原长度转换为二进制右移一位，新容量相当于扩充为原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);  
        /*
         *如果新容量比最小容量（也就是当前所需的容量的最低标准）大，  
         *那么就将最小容量作为新容量  
         */
        if (newCapacity - minCapacity < 0)  
            newCapacity = minCapacity;  
        //如果新容量比最大容量还大，那么就使用最大容量  
        if (newCapacity - MAX_ARRAY_SIZE > 0)  
            newCapacity = hugeCapacity(minCapacity);  
        // minCapacity is usually close to size, so this is a win:  
        elementData = Arrays.copyOf(elementData, newCapacity);  
}  

private static int hugeCapacity(int minCapacity) {  
        if (minCapacity < 0) // overflow  
            throw new OutOfMemoryError();  
        return (minCapacity > MAX_ARRAY_SIZE) ?  Integer.MAX_VALUE:  
            MAX_ARRAY_SIZE;  
}

trimToSize 方法最小化实例存储容量：

/**  
   * 将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用 
   * 此操作来最小化 ArrayList 实例的存储量。  
   */  
public void trimToSize() {  
      modCount++;  
      int oldCapacity = elementData.length;  
      //如果当前list的size比Object数组小，说明存在空的位置，那么就将空位置去掉。  
      if (size < oldCapacity) {  
                elementData = Arrays.copyOf(elementData, size);  
      }  
}  

indexOf 方法查找元素对应的下标：

   /**
     * 遍历Object数组，进行判断比较相等，返回对应的下标。
     */
    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;
    }

get 方法获取指定位置上的元素：

  /**
     * 先判断下标索引如果超出了Object数组的长度就报下标索引超出异常
     * 然后通过下标索引找到对应的元素值
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

remove方法删除指定位置的元素

   /**
     * 先检查下标索引是是否越界
     * 然后获取索引对应的元素值
     * 获取删除元素后，需要移动的元素的个数
     * 将元素进行移动拷贝
     * 最后将多出的位置设置为空，这样说明是没有引用的对象了。
     * 垃圾器的计数器就减一，这样通过计数，垃圾收集器就可以清楚的去回收了。
     * 返回删除的旧值
     */
    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; // Let gc do its work

        return oldValue;
    }

set方法替换指定位置的元素

   /**
     * 通过下标索引找到位置替换元素
     * 首先检查下标索引是否越界
     * 然后通过下标索引找到对应的元素值
     * 然后将下标索引对应位置的旧值元素进行替换为新值元素
     * 返回被删除的旧值
     */
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

<br />

---

<br />
阅读总结：
(1) ArrayList本身是一个Object数组实现的
(2) ArrayList的默认初始化容量为10
(3) ArrayList中如果初始化元素的个数大于了分配的Object数组的长度，就将Object数组扩容为原来的1.5倍。
<br />

---

<br /><br />
...........................该源码为jdk1.7

<br /><br />