源码分析—ArrayList（JDK1.8）

本文主要分析JDK1.8中ArrayList的源码，分别将从继承关系、成员变量、构造器、重要方法几个方面展开，这其实也是分析其它类源码的大概思路。

继承关系

1
2
3

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

通过IDEA可以查看更完整的继承关系：

继承了AbstractList并实现了List，AbstractList是一个抽象类，定义了一系列增删改查的方法。AbstractList是实现了List了的，为什么ArrayList也要实现List呢？collection 的作者Josh说他写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在。
实现了RandomAccess接口：表明ArrayList支持快速（通常是固定时间）随机访问。在ArrayList中，我们可以通过元素的序号快速获取元素对象，这就是快速随机访问。
实现了Cloneable接口：可以使用Object.Clone()方法。
实现了Serializable接口：表明该类的实例可以被序列化。

成员变量


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

/**
 * 当新建ArrayList对象时，如果指定容量为0，则将EMPTY_ELEMENTDATA赋值给elementData。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 当新建ArrayList对象时，如果没有指定容量（即使用无参构造器），则将EDEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData。
 * 和EMPTY_ELEMENTDATA的区别：当添加第一个元素时，扩容的方式会有所区别。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 这是ArrayList里用来真正存放元素的数组，数组的长度的就是ArrayList的容量。
* 对于elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的ArrayList，当第一个元素被添加时这个数组将被扩容到DEFAULT_CAPACITY大小。
*
* 被标记为transient，在对象被序列化的时候不会被序列化。
* 没有用private修饰，是为了ArrayList的内部类可以方便地访问这个属性
*/
transient Object[] elementData; 

/**
* ArrayList的实际大小，即elementData数组中实际的元素个数。
*/
private int size;
  

/**
* 分派给arrays的最大容量
* 为什么要减去8呢？
* 因为某些VM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致array容量大于VM的limit，最终导致OutOfMemoryError。
* MAX.VALUE为0x7fffffff，转换成十进制就是2147483647，也就是数组的最大长度是2147483639
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造器

ArrayList共有3个构造器，都比较简单。

/**
 * 指定初始容量
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * 不指定初始容量
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 传入一个集合对象
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        //不同的集合其toArray()方法实现不一样，数组有可能不是Object[].class，需要使用Arrays的复制方法处理一下
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

重要方法

add方法

add方法是ArrayList中重要且常用的一个方法。add方法总共有4个：

add(E e)

add方法主要的执行逻辑如下：

计算数组需要的最小大小minCapacity为size+1。但如果是第一次添加，minCapacity会默认为10
如果minCapacity大于elementData数组的长度了，调用grow方法进行扩容。
扩容的过程是将数组的长度变为原来的1.5倍，然后将旧数组里的数据复制到新数组。
在新数组size+1的位置存放要添加的元素。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}


private void ensureCapacityInternal(int minCapacity) {
    /** 当第一次添加元素的时候 size+1 的值是1（即minCapacity=1）,
     *  所以第一次添加的时候会将当前elementData数组的长度变为10。（即 Math.max(DEFAULT_CAPACITY, minCapacity) = 10）
     */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
 
    ensureExplicitCapacity(minCapacity);
}


private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  //修改次数自增1

    //如果添加数据时需要的最小容量已经大于elementData的长度了，调用grow方法进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}


private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

add(int index, E element)

这个方法是添加元素的时候指定了数组的下标index，在index处以及下标大于index处的元素将往后移动一位。
示意图如下：

addAll(Collection<? extends E> c)和addAll(int index, Collection<? extends E> c)

略

get方法

因为ArrayList底层是数组，所以它的get方法非常简单，先是判断一下有没有越界（索引小于0或者大于等于数组实际长度，错误信息返回索引和数组的实际长度），之后就直接通过数组下标来获取元素。


  public E get(int index) {
      rangeCheck(index);//越界检查
      return elementData(index);//返回索引为index的元素
  }


  /**
* 检查指定索引是否在范围内。如果不在，抛出一个运行时异常。
* 这个方法不检查索引是否为负数，总是在数组访问之前优先调用。
   */
  private void rangeCheck(int index) {
      if (index >= size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

  private String outOfBoundsMsg(int index) {
      return "Index: "+index+", Size: "+size;
  }


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

set方法

set方法也比较简单，就是把元素放到数组的指定的index上。


  public E set(int index, E element) {
//检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
      rangeCheck(index);

      E oldValue = elementData(index);
//替换元素（新值）
      elementData[index] = element;

//返回旧的元素
      return oldValue;
  }