ArrayList源码解析

之前给大家讲了讲Java的各种集合，今天来带大家深入了解一下ArrayList的源码

ArrayList类的定义

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

首先来看看ArrayList这个类的继承关系

AbstractList是一个抽象类，它里面只有一个抽象方法get，所以它的子类必须重写get方法。但是子类如果还要操作元素的话，还需要重写 add(), set(), remove() 方法，因为这几个方法虽然不是抽象类，但是这几个方法方法体只抛了一个Exception。当然这个类还实现了很多对List的一些通用操作，如果需要自己实现一个List的话，继承这个类可以提高复用性。

List是一个接口，这个接口定义了一个List所需要实现的方法，也可以说是List所要遵循的规范。

RandomAccess实现这个接口说明支持随机访问，也就是可以用下标访问元素。

Cloneable实现这个接口可以被克隆复制

Serializable实现这个接口可以进行网络传输

这三个接口都是空接口

ArrayList的成员变量

   private static final long serialVersionUID = 8683452581122892189L;

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

    /**
     * 用于空实例的共享空数组实例。在构造方法中，当初始化容量被指定为0的时候就会用这个数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 用于默认大小的空实例的共享空数组实例
     * 我们将其与EMPTY_ELEMENTDATA区分开来，以便知道何时膨胀多少添加第一个元素。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList元素的数组缓冲区。ArrayList的容量是这个数组缓冲区的长度。
     * 当添加第一个元素时，将扩展为DEFAULT_CAPACITY。也就是数组存放在这个数组里面
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList的元素数量
     */
    private int size;

ArrayList构造方法

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

这个构造方法可以传入一个整型的参数作为初始容量，如果这个容量大于0，就new一个相应容量的数组。如果这个容量值为0，则把空实例的共享空数组作为elementData数组的值。如果这个容量值小于0，则抛出异常

 /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

第二个构造方法非常简单，把默认大小的空实例的共享空数组实例作为elementData数组。这个构造方法也是平常使用比较多的一个构造方法

/**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @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) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

第三个构造方法传入的是一个Collection类型的变量，首先把这个c转化为数组给elementData，然后判断元素个数是否为0，为0就用本身的空数组成员变量作为elementData。不为0再判断c是不是一个Object数组，如果不是就把c里面的元素转成Object类型放入到elementData里面。这个构造方法可以快速的复制一个新的List。

ArrayList关键方法

add方法

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

ensureCapacityInternal这个方法是检查当前容量是否能够成功添加一个元素，如果当前元素数量已经达到了容量值，则需要进行扩容。

进入到ensureCapacityInternal方法

private void ensureCapacityInternal(int minCapacity) {
        //calculateCapacity计算需要扩容的最小容量值
        //ensureExplicitCapacity进行扩容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

继续进入到calculateCapacity中查看

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

这个方法就是在计算需要扩容的容量的最小值，首先判断了elementData是不是还没有元素，如果没有就返回默认容量和传入的容量的最大值。如果已经有值了就返回传入的这个容量。

继续看ensureExplicitCapacity这个方法

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

modCount是ArrayList里面的一个类似计数器的变量，它表示对这个ArrayList进行了多少次的操作。然后这个又继续判断了一次这个传入的容量是否大于elementData数组的长度，如果大于就进入到grow方法。

进入到grow方法

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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);
    }

gorw方法就是扩容的具体实现了。第一步获取一下当前elementData的长度，然后计算扩容之后的长度。

这里的计算就是用原elementData的长度加上原elementData的长度右移一位，将这个计算得出的值作为新数组的长度。这里大家可以带入数据计算一下，这样的计算方式就是扩容1.5倍，使用位运算相比于数值计算会快一些。

newCapacity – minCapacity < 0 只会出现在整型值溢出的情况，说明新数组长度已经超过int所可以表示的范围了

newCapacity – MAX_ARRAY_SIZE > 0 说明新数组长度可能超过了数组的最大值（具体有没有超过得看hugeCapacity这个方法），超过数组最大值会发生内存溢出的异常。

如果新数组长度没有问题，那么最后一步将新建一个newCapactity大小的数组，并把数据拷贝到这个新数组中。

最后再看一眼hugeCapacity

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

如果minCapacity小于0，也就是溢出了，就抛出OutOfMemoryError。否则进入下一个判断，如果minCapacity大于数组最大长度，就让数组长度为整型的最大值，否则就定义为数组最大值（MAX_ARRAY_SIZE），看到这里会不会感到一些迷惑，超过了数组最大可定义值还让这个值变得更大？

MAX_ARRAY_SIZE这个值为Integer.MAX_VALUE – 8,超过了这个值就会抛出OutOfMemoryError，那为什么还让数组长度为Integer.MAX_VALUE呢？我从MAX_ARRAY_SIZE的注释中找到了答案

Some VMs reserve some header words in an array

就是说有一些虚拟机的数组会有一些头部字符，所以在某些虚拟机数组的最大长度可以达到Integer.MAX_VALUE，所以说这样做的好处是可以减少一些内存溢出。

好了，最难的add方法看完了，希望同学们可以自己用编译器也去查看一下ArrayList的源码。

get方法

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

get方法就非常简单了，首先对index的返回进行一个校验，如果是一个合法的index，就返回数组下标为index的元素

进入到rangeCheck方法里面

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

这个校验也非常的简单，只是判断了一下index是否大于等于元素个数，如果大于，就是不合法的，抛出一个数组越界异常。

set方法

 public E set(int index, E element) {
        rangeCheck(index);

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

首先检验一下index是否合法，然后保存一下旧的值，更新elementData数组，再把旧的值返回

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; // clear to let GC do its work

        return oldValue;
    }

remove方法首先进行index的校验，modCount++表示对这个ArrayList的修改次数加1，再把需要删除的值赋值给一个变量。numMoved代表需要移动的值，也就是如果删除的不是数组中的最后一个值，需要把这个需要删除的值后面的所有值都向前移动。再把原数组最后一个值指向null，方便及时进行垃圾回收。