浅析ArrayList

写在前面

Java的集合框架完备而又牛叉，其实现值得我这样的小白去一探究竟。当然了，在这我暂时不会很深入的去阅读整个集合框架，而是通过一两个实现去摸一下他的套路，希望最终我能摸到点集合框架的门路。在本文中，我将会带你阅读：

ArrayList内部的基本实现
add()方法
get()方法

是的，你没看错，就看这三个……当然了，ArrayList远不止如此，但现在我只会去探究一下其基本实现。

基本实现

首先回忆一下平时我们是如何初始化一个ArrayList的：

1	List<String> list = new ArrayList<>();

得益于Java的多态使得我们可以写出如上的代码，那么无参的ArrayList的构造函数是啥样的呢？

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

接下来看看他是怎么初始化的，左边那个值是个什么东西，右边那个值又是个什么东西。

首先是左边：

 /**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData;// non-private to simplify nested class access

如果用transient声明一个实例变量，当对象存储时，它的值不需要位置。换句话说就是，用transient关键字标记的成员变量不参与序列化的过程。

回过头来再看看，这是个Object的数组，这就是ArrayList元素被存储的地方。ArrayList的容量就是这个数组的长度。再来看看上面那个构造函数的右边具体是个什么东西：

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

从上面的代码可以看出来就是个空的Object数组，果然很符合空的ArrayList（笑）。接下来解析代码将会在我们调用了无参的构造函数的基础上去分析，那么让我们通过几个常用的方法去看看ArrayList内部究竟是如何使用这个Object数组的。

add()

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

向list的末尾追加一个指定的元素，第一行代码看样子和ArrayList的尺寸有点关系，第二句代码很明显就是追加元素的操作了。那么回过头来，看看第一句代码究竟干了啥：

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

首先从名字上分析分析……确定内部的容量，果然是和尺寸有关系的。看下具体的代码，如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么会从minCapacity和DEFAULT_CAPACITY中比较大的值中挑一个出来赋给minCapacity，接着调用ensureExplicitCapacity方法

首先DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个在前面的空构造函数中已经看到过了，如果你调用的是空的构造函数，那么在这里elementData的值明显是和这个值相等的。那么看看DEFAULT_CAPACITY是个啥东西：

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

很明显就是个常数值，很明显，当你调用空的构造函数创建一个ArrayList时，其内部Object数组是一个空值，当你调用add()方法时(add(E e,int index)方法稍有不同)，他会先判断你的ArrayList是否是一个空值，如果是的话，它会给minCapacity赋上10的值然后调用ensureExplicitCapacity()方法，那么来看看那个方法：


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

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

第一行代码可以先抛开。if里判断minCapacity的值是否大于elementData的长度，那么看一下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);
}

代码不多，一行一行看过来。第一行拿到内部对象数组的长度，第二行计算出新的容量。计算方式是：旧容量+旧容量/2，也就是每次扩充当前内部对象数组长度的一半。当然了，如果刚开始你的内部对象数组的长度是0的话，那你得出的值也还是0。那么newCapacity-minCapacity的值将会小于0，那么nweCapacity的值将会是10。之后便是调用Arrays.copyOf方法，这个方法最终会调用一个native方法实现将指定的数组拷贝到一个拥有新的尺寸的数组中，那么整个ensureCapacityInternal方法咱就过了一遍了。

在调用无参构造函数的情况下，内部的object数组尺寸是0，在调用了一系列方法之后构造了一个值为10的数组出来，最终将值插入相应的位置。

get()

/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

老规矩，一行一行来看首先第一行：

private void rangeCheck(int index) {
    if (index < 0 || index >= this.size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

边界检查，小于0或者大于内部数组的长度就报个越界的错误。

之后就是从数组取出这个下标的值。。没啥好说的。。数组取个值。。。

remove()

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
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;
}

第一行仍旧是边界检查。modCount++还是忽视……之后取出对应下标的元素，拿到需要移动的元数量，如果数量大于0，调用arraycopy将内部数组elementData中index之后的元素统统向前移动一个位置。之后将内部数组的最后一个位置置空，方便gc去回收这块内存。在Java中强引用的内存无法被回收，所以需要我们手动的将在逻辑上已删除的元素置空。