Java源码之ArrayList

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/08/22/Java源码之ArrayList/

访问原文「Java源码之ArrayList」

关于ArrayList

相信ArrayList是小伙伴们在Java开发中经常会使用的类之一。那么ArrayList究竟是一个什么类呢。大概来说它是List接口的可调整大小的数组实现。 实现所有可选列表操作，并允许所有元素，包括null。除了实现List接口之外，他的类还提供了一些方法来操纵数组的内部大小来存储列表。 也就是说ArrayList内部是由数组实现，往ArrayList中放置元素也是默认按照先后顺序进行放置；它的大小是可调整的，不用像使用数组一样担心它不够存放数据（这里排除内存限制）。

总的来说ArrayList不论从使用还是理解上都是比较简单的，那么让我们来分析一下其中的一些关键方法吧。

关键成员变量

下面列出了ArrayList的关键成员变量，数量并不多，可以看到元素在ArrayList中是存储在数组中的。

	
/**
 * 存储元素的数组缓冲区
 * ArrayList的容量是此数组缓冲区的长度
 * 空ArrayList的elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * 当插入第一个元素后大小为DEFAULT_CAPACITY
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * ArrayList的大小，即存储元素的数量
 *
 * @serial
 */
private int size;

插入方法

最简单的方法就是add一个元素，下面是这个方法的源码。这个方法比较简单，但我们看第一步是ensureCapacityInternal，这个方法是检测新size是否超出目前可容纳的最大值，超出的话需要扩展容量，最后走到grow方法中，具体代码下面已经给出。需要注意的是modCount++这一句，这个变量表示此列表已被结构修改的次数，结构修改是改变列表大小的那些修改，或以其他方式扰乱它，使得正在进行的迭代可能产生不正确的结果。也就是说在迭代的时候进行结构修改将导致程序出错。

/**
 * 在列表的最后插入元素
 *
 * @param 即将插入的元素
 * @return true
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 增加modCount
    elementData[size++] = e;
    return true;
}

// 检测是否超出目前可容纳的最大值
private void ensureCapacityInternal(int minCapacity) {
	// 放入第一个值时minCapacity设置为DEFAULT_CAPACITY
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

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

    // 当所需最小容量大于目前容量的话，需要增加容量
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 增加容量以确保它至少能够容纳最小容量参数指定的元素数量
 *
 * @param 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通常接近大小
    elementData = Arrays.copyOf(elementData, newCapacity);
}

另外一个常用的插入就是在指定位置插入，例如在首位（index为0）的位置插入等等。下面是这部分的源码，比较好理解，关键部分已经加上注释。

/**
 * 在此列表中的指定位置插入指定的元素。 
 * 将当前位于该位置的元素（如果有）和任何后续元素（向其索引添加一个）移动。
 *
 * @param index 指定元素要插入的索引
 * @param element 插入的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    // 检测index的合法性，不行小于0或者大于size
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将index位置以及其后所有元素的索引增加1
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // index位置放入元素
    elementData[index] = element;
    // 大小加1
    size++;
}

其次还有addAll方法，分别为向列表最后插入和指定位置插入两个方法，这两个方法都是在add方法上延伸出来的，很好理解，不再赘述。

删除方法

删除元素也是我们经常使用的方法，首先看按照索引删除元素。下面的代码注释已经比较明白，需要注意的是rangeCheck这个方法只检测index是否大于等于size，不检测是否小于0。这是因为是否小于0在访问数组时进行检测。

/**
 * 删除该列表中指定位置的元素。 
 * 将任何后续元素移动到左侧（从其索引中减去一个元素）。
 *
 * @param index 要删除的元素的索引
 * @return the element 删除的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    // index范围检测
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // index以及之后元素的索引减1
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

/**
 * 检查给定的索引是否在范围内。 如果没有，则抛出适当的运行时异常。 
 * 该方法不检查索引是否为负数：它始终在数组访问之前立即使用，如果index为负，则抛出ArrayIndexOutOfBoundsException。
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

下面是根据删除指定元素。指定的元素可以为null，在找到指定元素的位置（索引）后，通过fastRemove删除元素。

/**
 * 
 * 如果存在制定元素则从这个列表中删除第一个出现的指定元素。
 * 如果列表中不包含元素，那么它是不变的。
 * 
 * 如果该列表包含指定的元素，返回true.
 *
 * @param o 要删除的元素
 * @return 包含这个元素则返回true
 */
public boolean remove(Object o) {
    // 如果o为null，则删除第一个为null的元素
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

// 不包含各种检测的从指定索引位置删除元素
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; // clear to let GC do its work
}

还有用的比较多的是批量删除，以其中一个方法为例，如下。可见这个函数交由方法removeAll处理。在removeAll中，并没有删除，而是遍历每一个元素，判断是否需要保留，不需要保留的会被需要保留的覆盖。可能这句话不好理解，可以看一下具体的代码。

/**
 * 从这个列表中删除包含在指定集合中的所有元素。
 *
 * @param c 包含要从这个列表中删除的元素的集合
 * @return {@code true} 如果列表的数据被修改
 * @throws ClassCastException 如果该列表中的元素类与指定的集合不兼容
 * @throws NullPointerException 如果该列表包含一个空元素，并且指定的集合不允许null元素
 */
public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false);
}

/**
 * complement为false表示删除，为true表示保留
 *
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // 出现异常时，没有遍历完毕，但是需要将未遍历的数据再进行添加
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        // w不为size，表示这个列表有修改，则需要修改size等属性
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

查询方法

查询方法是必须了解的，因为我们存起来也是为了获取。这个方法非常的简单，只做简单的参数检验，然后返回对应下标的元素。

/**
  * 返回列表中指定位置的元素
  *
  * @param  index 返回元素的索引
  * @return 元素在这个列表中的指定位置
  * @throws IndexOutOfBoundsException {@inheritDoc}
  */
 public E get(int index) {
     rangeCheck(index);

     return elementData(index);
 }

总结一下

基本上把ArrayList涉及的关键函数都做了详细说明。其余的一些都比较好理解了。