您的位置: 首页  >  文章  >  Java集合系列——ArrayList源码解读

Java集合系列——ArrayList源码解读

分类: 文章 • 2024-10-31 12:07:52

都2019年了还来谈ArrayList，不知道是不是太老套了，但是从另一个角度来想，Java集合本就是一个老少咸宜的话题，那就先从最简单的ArrayList开始谈吧。

概述

简单说下ArrayList的特点：

  1. ArrayList使用可变长数组来实现List接口的功能。
  2. 实现了所有列表有关的操作，允许添加所有类型的元素，连null都可以添加。
  3. 该类和Vector类相似，但是该类是线程不安全的，Vector是线程安全的。

接下来开始进行源码解读，包括成员变量、构造方法、其它常用方法。
声明：本笔记里的源码来源于官网安装文件“jdk-8u201-windows-x64”。

成员变量（字段）

我们先来读懂字段。

private static final long serialVersionUID = 8683452581122892189L;
说明：ArrayList实现了java.io.Serializable接口，这个字段是针对该接口提供的，这个值怎么来的我们就不用过于关注了。

private static final int DEFAULT_CAPACITY = 10;
说明：严格来讲它并不是ArrayList的默认（或者叫初始）长度，如果你在创建ArrayList的时候没有指定初始长度（即使用空参数的构造方法），其实底层数组的初始化长度是0，那么这个字段有什么用呢？它其实是在底层数组扩容的时候用的，如果你的ArrayList是使用空参数的构造方法创建的，在对数组进行扩容的时候，“DEFAULT_CAPACITY”是最小的扩容后的容量，也就是你会得到一个长度为10的数组。由于使用空参数的构造方法得到的底层数组的初始长度是0，那么第一次添加元素的时候，肯定就要进行扩容，所以也可以这么描述：对于使用空参数的构造方法创建的ArrayList，它在第一次扩容的时候，长度就会扩大到10。

private static final Object[] EMPTY_ELEMENTDATA = {};
说明：就是一个“Object[]”类型的数组，在某些时候用它来初始化底层数组，具体是哪些时候在下文使用的时候说明。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
说明：还是一个“Object[]”类型的数组，也是在某些时候用它来初始化底层数组，那么它和上面的EMPTY_ELEMENTDATA有什么区别呢？主要在于你的ArrayList是用哪个构造方法创建的，ArrayList使用“Object[]”类型的名称为elementData的字段存储元素，这个其实就是底层数组。只有使用空参数的构造方法创建ArrayList时，elementData会被指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA。使用其它的构造方法，elementData会被指向EMPTY_ELEMENTDATA或者指向其它的数组对象，反正不会是DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

transient Object[] elementData; // non-private to simplify nested class access
说明：这个就是真正存储元素的底层数组。

private int size;
说明：注意某些字段里面夹带的“capacity（容量）”单词和这个“size”的区别，capacity指的是底层数组的长度，size指的是这个数组里面存储的元素的数量，总是有capacity>=size，只有数组刚好装满的时候，capacity==size。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
说明：这个字段的结尾单词虽然用的是“size”，但其实表示的还是容量的意思。这个字段在底层数组扩容的时候使用，表示数组的最大容量。数组的容量本质上是个整数，整数的最大值是Integer.MAX_VALUE，那么为什么这里要减8呢？有些虚拟机会在数组里面额外存储一些东西，如果你申请容量超过Integer.MAX_VALUE-8的数组，可能回导致OOM。虽然源码里面有“MAX_ARRAY_SIZE”这个字段表示数组可申请的最大容量，但是其实你还是有可能申请到容量为“Integer.MAX_VALUE”数组，这个下文会提到。

构造方法

ArrayList共有三个构造方法，接下来对构造方法的源码进行解读。

源码解读

空参数的构造方法：

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

简单的不能再简单了，对于空参数的构造方法，就是直接将表示底层数组的elementData字段指向了DEFAULTCAPACITY_EMPTY_ELEMENTDATA对象数组。

指定初始容量的构造方法：

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

主要是对传进来的初始容量做了判断：

  1. 如果大于0，那就创建一个容量等于初始容量的Object[]，并将elementData指向它。
  2. 如果等于0，就是用内部定义的字段EMPTY_ELEMENTDATA；
  3. 如果小于0，抛异常。

使用传入的集合创建ArrayList：

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;
    }
}
  1. 首先将传入的Collection变成了数组形式，并将其传给elementData字段。
  2. 接着是对数组里面存储的元素数量进行判断，如果数组里面存有元素，进行类型检查，要保证elementData指向的是Object[]类型的数组。这里说说为什么要进行类型检查，Collection接口的toArray()方法声明的返回值其实是Object[]类型的，但是由于Java的多态性质，其实返回的对象不一定真的是Object[]类型，所以需要进行类型检查。
  3. 如果数组里面没有元素，就不理会传进来的集合对象了，直接将elementData指向内部定义的EMPTY_ELEMENTDATA。

流程图形式描述源码

Java集合系列——ArrayList源码解读

以上，是通过流程图的形式描述构造方法执行过程。

源码小结

这里主要围绕elementData最终指向的对象来描述：

  • 只有空参数的构造方法，elementData会指向内部定义的DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
  • 对于非空参数的构造方法，只有创建容量为0的ArrayList时（比如，向构造方法指定容量为0，或者传入的Collection里的元素个数为0），elementData会指向内部定义的EMPTY_ELEMENTDATA。
  • 除了以上的情况，elementData均会指向新的Object[]对象（反正不是内部定义的），并且容量根据实际情况确定。

为什么要围绕elementData最终指向的对象来描述呢，因为elementData最终指向的对象是谁，会影响底层数组扩容过程。

public boolean add(E e)

解读完了构造方法，来看我们用的最多的方法之一，添加元素的方法。

源码解读

接下来对添加元素的add(E e)进行解读，我们把add(E e)及其内部调用的方法从头到尾列出来，全部如下：

/**
* 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;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

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

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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

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

这若干个方法从上往下看即可：

  1. add(E e)其实就只干了两件事情：1、确保数组容量足够装入一个新的元素；2、将新的元素添加到最后一个元素后面。通过调用ensureCapacityInternal()来确保数组容量够用，注意传进去的数字是数组已使用空间+1。接着来看怎么确保数组容量，也就是ensureCapacityInternal(int minCapacity)。
  2. ensureCapacityInternal(int minCapacity)，翻译过来就是确保内部容量，意思就是确保内部数组的容量够用。“minCapacity”指的是“minimum capacity”即最小容量。结合add(E e)传进来的参数，就是每一次add(E e)，在添加元素之前，确保数组的容量能达到已使用空间+1。这里面只有一行代码，调用了两个方法，这两个方法决定了期望容量是多少，注意啊只是期望容量，还不算是最终容量。先来看看calculateCapacity()。
  3. int calculateCapacity(Object[] elementData, int minCapacity)，光看方法签名你就可以知道，它会结合内部数组和传进来的期望容量，算出一个新的期望容量，接下来看计算逻辑。首先判断elementData是否等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，前面讲解构造方法的时候说过，只有使用空参数的构造方法创建ArrayList，elementData才会等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA。那这个判断其实就是在问ArrayList是否是使用空参数的构造方法创建的，如果是，返回Math.max(DEFAULT_CAPACITY, minCapacity)。由于DEFAULT_CAPACITY是个常量，minCapacity是个变量，这个数学运算的含义其实是不论minCapacity是多少，返回值要大于等于DEFAULT_CAPACITY。结合空参数构造方法这个前提，calculateCapacity()的计算逻辑就是：对于空参数的构造方法创建的ArrayList，计算出的期望容量最小要是DEFAULT_CAPACITY，对于其它构造方法创建的ArrayList，直接将传进来的参数返回。对于API的使用者而言，其结果是当你使用空参数的构造方法创建ArrayList，一旦添加元素，底层数组的容量就会至少扩充到DEFAULT_CAPACITY，因为所有和添加元素有关的方法都会调用ensureCapacityInternal()，进而将整个流程走一遍。
  4. ensureExplicitCapacity(int minCapacity)，看看它对计算出来的期望容量做了什么，其实它什么都没做，它只是判断一下数组现有容量是否满足期望容量，如果满足，那就不需要扩容了。只有不满足的时候，才要扩容。
  5. grow(int minCapacity)，前面的一大堆方法都只是在计算期望容量，这个方法是真正的对底层数组进行扩容的地方，来看看扩容的逻辑。回顾一下JAVA基础，elementData.length即数组的length属性，它和我们一直说的容量是一个意思，它指的是数组的长度，而不是数组里面存放的元素的个数。“newCapacity”其实就是“oldCapacity”的1.5倍，也就是以50%为基础来进行扩容，为什么说是以此为基础呢？因为这个“newCapacity”还要再进行处理，所谓处理其实就是判断“newCapacity”的下限和上限。对于下限，就是判断扩容50%是否达到传进来的期望容量，如果达不到，“newCapacity”直接等于传进来的期望容量。这意味着扩容后的容量，既要达到原有容量的1.5倍，还要达到传进来的期望容量。对于上限，就是判断“newCapacity”或者“minCapacity”是否超出了“MAX_ARRAY_SIZE”或者是“Integer.MAX_VALUE”具体的上限处理下文说。上下限都处理完成之后，进行扩容。扩容的方法签名是这样的：“public static T[] copyOf(T[] original, int newLength)”，其功能是传入源数组“original”，将该数组里的元素复制到新的新数组并返回，新数组的容量为“newLength”。如果“newLength”小于源数组的容量，会截断源数组剩余部分的数据。如果“newLength”大于源数组的容量，多出来的地方会用“null”填充。从这里我们就知道，所谓的“可变长数组”，就是在原有数组容量不够用的时候，创建一个新的、容量更大的数组，然后将原数组的元素复制过去，这就是ArrayList实现可变长数组的原理。
  6. hugeCapacity(int minCapacity)，翻译过来是巨大容量的意思，倒不是说传进来的参数很巨大，而是这个方法返回的数值，只有“Integer.MAX_VALUE”、“MAX_ARRAY_SIZE”两个可能，这两个值很巨大。我们先就这个方法自身的代码来看看它的功能，然后结合传进来的参数的可能的值来看这个方法对最终的实际容量造成什么影响。
    1. 自身功能：第一行的判断可能让你困惑，为什么要判断它是否小于0，而且注释居然还写着“溢出（overflow)”，抛出来的异常是OOM？这个要从JAVA里面整型的表示来说，JAVA里面，整型的最大值“Integer.MAX_VALUE”的定义是这样的：“public static final int MAX_VALUE = 0x7fffffff”，这个值有什么特点呢？JAVA里面，用4字节存储整型，同时JAVA里面不支持无符号数（这点和C语言不同，C语言支持无符号数），也就是整型都是有符号的，符号位用整型的最高位表示，也就是最高位不表示数值，表示符号。“0x7fffffff”这个转化成二进制数，是一个32位（也就是4字节）的二进制数，最高位为0，表示正数，低31位为1，所以“0x7fffffff”其实是用4字节存储的、有符号位的、最大的正整数。当你传入一个超出它的数，最高位会变成1，此时这个数会被JAVA当成负整数。所以对于一个本该是正整数的数值，如果它小于0，不是因为它太小了，而是因为它太大了，4字节的有符号整数存储形式已经装不下这个正整数了，反而会被当成负整数。所以这里的小于0不是担心它太小，而是担心它溢出了。如果溢出了，就抛异常，如果没有溢出，返回“Integer.MAX_VALUE”或者“MAX_ARRAY_SIZE”。
    2. 对实际容量的影响：这个要结合grow()在调用hugeCapacity()时“newCapacity”和“minCapacity”所处的情况来说。如果底层数组原有容量扩大50%后，仍然不满足期望容量，而且期望容量还超出了“MAX_ARRAY_SIZE”，此时就是对期望容量的上限进行约束，将其约束在为“Integer.MAX_VALUE”。如果底层数组原有容量扩大50%后，可以满足期望容量，但是超出了“MAX_ARRAY_SIZE”，那就是使用期望容量“minCapacity”来对扩容50%这个扩容结果的上限进行约束（或者叫修正），如果期望容量没有超出“MAX_ARRAY_SIZE”，那就将扩容结果约束为“MAX_ARRAY_SIZE”，如果期望容量超出了“MAX_ARRAY_SIZE”，将扩容结果约束为“Integer.MAX_VALUE”。

流程图形式描述源码

接下来通过流程图的形式梳理add(E e)的过程：
Java集合系列——ArrayList源码解读

以上是通过流程图的形式描述add(E e)的过程。

源码小结

既分析了源码，又梳理了流程图，接下来可以小结一下向ArrayList添加一个元素的过程了：

  1. 最外层的add(E e)其实就只干了两件事情：1、确保底层数组容量够用；2、将新元素添加到数组最后一个元素后面。
  2. “确保底层数组容量够用”这个行为，也只干了两件事情：1、计算期望容量；2、扩容。从调用ensureCapacityInternal()开始一直到调用grow()之前，都是在计算期望容量。期望容量的计算主要受两个因素的影响，一是ArrayList最初是否由空参数的构造方法创建，二是最外层传进来的期望容量。计算出期望容量的结果后，进入grow()开始扩容。
  3. 扩容的结果（即最终容量）主要受两个因素的影响：一是底层数组原有容量，二是前面“计算期望容量”时计算出来的结果。扩容的结果是对底层数组原有容量扩大50%作为基础的，然后对比传进来的期望容量，约束下限。然后再和“MAX_ARRAY_SIZE”对比，约束上限。得出最终结果后，进行扩容。

最终我们可以得出，向ArrayList添加一个元素的过程，核心点在于计算期望容量和扩容。

思考

add(E e)的执行流程，有两个值得思考的地方：

  • 为什么在计算期望容量的时候要考虑ArrayList是否由空参数的构造方法创建？
  • 为什么在扩容的时候不是直接按照最初传进来的（已用空间+1）进行扩容，而是按照原有容量的比例进行扩容？

两者都是出于性能考虑，我们知道数组在进行增删改查的时候，“改”和“查”是很高效的，但是“增”和“删”都要以改动的位置为起点，对后面的所有元素进行移动，这是低效的，但是又是不可避免的。如果说“删”只要将后面的元素向前移动的话，“增”还可能多了一步操作，如果数组已经被装满了，就不仅仅是将插入位置及其后面的元素向后移动，而是将整个数组抛弃，元素复制到新的数组里去。而“增”多出来的这一步操作，也影响效率，这里提出来的两个思考问题，都是为了减少创建新数组的次数，进而提高效率。

我们先来看第二个问题，为什么要按照原有容量的比例进行扩容？我们取一个差异比较明显的情况，假设现在数组的容量和已使用空间都是100，继续添加100个元素。如果按照ensureCapacityInternal()最初传进来的容量进行扩容，也就是每次都只增加一个元素，那仅仅是在扩容的时候要在新、旧数组之间复制元素的个数就达到100+101+…+198+199 = 14950次。如果按照50%的增长比例进行扩容，只需要在第1次添加、以及第51次添加元素的时候创建新数组，在新、旧数组之间复制元素的个数只有100+150 = 250次，接近60倍。这种差异，在数组元素越少的时候越不明显，数组元素越多的时候越明显，这意味着如果每次只扩容一个元素，随着数组越来越大，效率越低。至于扩容的比例为什么选择50%，这个笔者也没想通。

接着我们回过去看第一个问题，为什么要考虑ArrayList是否由空参数的构造方法创建？对于空参数的构造方法创建的ArrayList，底层数组初始化容量为0，即便是有扩容50%的机制存在，像1、2、3、4这种数字，基数太小，即使扩容50%，在早期添加元素的时候，还是会导致过于频繁的创建新数组，效率还是低下。ArrayList连这个都替我们考虑好了，直接替我们将容量增长到DEFAULT_CAPACITY（值为10），避免了原来基数太小导致的频繁创建数组。此时你可能会问，如果我用有参数的构造方法比如ArrayList(int initialCapacity)创建时传入0，那不也是效率低了？确实是，但是API的设计者很显然只会为默认行为进行优化，至于客户端程序员（API的使用者）已经选择了自己想要的容量，就不属于默认行为，自然是不会进行优化了。笔者从另一个角度考虑，对API不熟悉的使用者，一般是不会使用有参数的方法的，都会尽量选择无参数的方法，以支持API设计者的默认行为。那么既然选择了有参数的方法，自然是多少了解了传入参数会来带的影响，也就不会胡乱传入参数。

public boolean add(int index, E e)

接下来看add(E e)的重载方法：在指定位置添加元素。

源码解读

该方法及其内部调用的方法源码如下：

/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

由于ensureCapacityInternal()前面已经分析过了，那么这个重载的add()其实就很简单，接下来开始分析：

  1. rangeCheckForAdd(int index)，首先就是进行参数检查，检查的内容也很简单。注意ArrayList的下标和一般数组的下标计算方法是一样的：从0开始，对于装填了size个元素的数组，最后一个元素的下标是（size - 1），那size就是原来已经装有的最后一个元素的后边那个位置。从这个检查范围可以知道ArrayList允许添加元素的位置范围，最前面的地方是数组头部，即在第一个元素前面插入元素，最后面的地方是数组尾部，即向最后一个元素后面插入元素。
  2. ensureCapacityInternal(int minCapacity)已经分析过了，不再重复。
  3. System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)，是System类提供的对数组进行复制的方法，第一个参数表示源数组，第二个参数表示要从源数组的哪个位置开始复制元素。第三个参数表示目标数组，第四个参数表示从目标数组的哪个位置开始复制元素，第五个参数表示要复制几个元素。概括起来就是从src数组的下标srcPos开始，复制length个元素到dest数组，目的地从dest数组的下标destPos开始。这里的调用其实就是将底层数组从下标index开始的所有元素后移一个位置。将下标index的位置空出来了，用来装填新的元素。
  4. 接下来就是装填新的元素，并且将表示已使用空间的size变量+1。

源码小结

这个方法很简洁了，就不画流程图了，直接进入小结吧。其实该方法就只干了这几件事：

  1. 参数检查。
  2. 确保底层数组容量够用。
  3. 自下标index开始的元素后移一个位置。
  4. 装填新元素并修改已使用空间。

public boolean remove(Object o)

添加元素的方法分析完了，现在来分析删除元素的方法。

源码解读

类似的，列出方法源码及其内部调用的方法：

/**
* Removes the first occurrence of the specified element from this list,
* if it is present.  If the list does not contain the element, it is
* unchanged.  More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
* (if such an element exists).  Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
    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 remove method that skips bounds checking and does not
* return the value removed.
*/
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
}

remove()用于从集合里面移除指定元素，如果集合里面存在重复元素，只移除从底层数组头部开始向后遍历时出现的第一个元素。接下来开始分析：

  1. 根据传进来的参数是否为null，将主要逻辑分成两大块。
    1. 对于传入参数为null的情况，移除从头到尾找到的第一个null元素。
    2. 对于传入不为null的情况，移除从头到尾找到的第一个相同（由equals()方法确定是否相同）的元素。
    3. 只有被移除的元素存在集合里面，才返回true，否则返回false。
  2. fastRemove(int index)，这是真正移除元素的方法。取这个名字，一方面是如该方法的注释所提到的，它没有边界检查，也不会返回被移除的元素，所以比较快（fast）。另外一个原因是笔者自己猜的，因为ArrayList里面有个签名为“public E remove(int index)”的方法，这两方法已经没法重载了，只能起一个新的名字了。我们来看具体是怎么移除元素的。numMoved是要移动的元素个数，我们知道在数组里删除元素，就要将这个元素后面的元素全都前移一个位置。只有numMoved大于0，才有必要移动元素（如果删除的元素是数组最后一个元素，就不需要移动了）。System.arraycopy()前文已经说过了，不再重复，这里传进去的参数会将下标index之后的所有元素全都向前移动一位。最后，释放数组最后一个元素。

源码小结

移除指定元素的步骤可以总结如下：

  1. 找到元素。
  2. 计算要移动的元素个数，将目标元素后面的所有元素前移一个位置。
  3. 释放数组最后一个元素。

public E remove(int index)

这是remove(Object o)的重载方法，用于移除指定位置的元素。

源码解读

源码如下：

/**
* 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;
}

前面的remove(Object o)就已经挺简单了，这个remove(int index)就更简单了，因为它连查找元素这一步都没有了，内容和fastRemove()差不多，这里就不做过多解释了，直接总结流程：

  1. 参数检查。
  2. 存下被移除的元素，用于返回给API的调用者。
  3. 计算要移动的元素个数然后移动元素。
  4. 释放数组最后一个元素，返回被移除的元素。

public void trimToSize()

我们分析了add()、remove()的所有重载方法，不知道大家有没注意到一个事情，添加元素的时候，有对底层数组进行扩容（如果原有容量不满足），但是在移除元素的时候，好像没有相应地缩减底层数组的容量啊。如果我一开始装了很多元素，后来移除了，那就一直占着大片内存不放了？首先ArrayList在移除元素的时候确实没有类似添加元素那样自动调整底层数组容量的机制，但是ArrayList是可以缩减底层数组容量的，但是需要API的使用者主动调用，这就是public void trimToSize()。

源码解读

我们来看缩减数组容量的源码：

/**
 1. Trims the capacity of this <tt>ArrayList</tt> instance to be the
 2. list's current size.  An application can use this operation to minimize
 3. the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}
  1. 首先判断已用空间是否小于数组容量，这是需要进行缩减的前提。
  2. 接着看已使用空间是否为0，如果是，直接将elemenetData指向字段EMPTY_ELEMENTDATA，因为没有元素，就没必要复制元素了。如果不为0，调用Arrays.copyOf()来复制数组，并获取新数组。
  3. T[] Arrays.copyOf(T[] original, int newLength)方法的功能是将传入的数组元素复制到新的数组对象里面并返回，newLength表示要复制多少个元素，如果newLength大于传入的数组容量，新数组多余的空间补null。如果newLength小于传入的数组容量，进行截断，抛弃原数组超出部分的元素。

public void ensureCapacity(int minCapacity)

我们前面在解读添加元素的过程时说过，为了防止性能问题，底层数组并不是每次添加1个单位的容量，而是按照增加50%的容量进行扩容。如果你是使用空参数的构造方法创建ArrayList，第一次扩容时会直接扩充到“DEFAULT_CAPACITY”的长度，以防止1、2、3、4之类的基数过小导致频繁创建数组。而如果你在创建ArrayList时指定了容量，为了避免性能问题，你应当传入不要太小的数字。

现在遇到这样一个问题，如果我们使用前面说的trimToSize()缩减了数组的容量，而又那么凑巧，缩减后的数组容量就是1、2、3、4之类的小基数，如果此时添加元素，由于elementData没有指向DEFAULTCAPACITY_EMTPY_ELEMENTDATA，那不就和使用带参数的构造方法创建ArrayList，然后输入比较小的数字的情况是一样的：当你逐一添加元素，也会导致频繁创建新数组的问题。那怎么办？

这里就要用到我们接下来要解读ensureCapacity()方法，它和trimToSize()是对应的，trimToSize()用来缩减容量，ensureCapacity()是用来手动扩容的。实际上，该方法是除了在构造方法里传入容量之外，仅有的外界可以直接指定扩容数值的方法。

源码解读

我们来看它的源码：

/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param   minCapacity   the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

我们来看扩容过程：

  1. 首先判断elementData是否指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果不是，则minExpand为0，如果是，则minExpand等于DEFAULT_CAPACITY。实际上，在该版本的源码里（本文开头有说明源码版本），仅有使用空参数的构造方法创建ArrayList时，elementData会指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA。使用其它构造方法创建ArrayList或者对ArrayList进行过任何扩容、缩减容量的操作，都会导致elementData不再指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
  2. 如果传入的期望容量大于minExpand，调用ensureExplicitCapacity()进行扩容，这意味着大多数情况下，只要你不要传入0，都能进行扩容。ensureExplicitCapacity()前文已经解读过了，不再重复。

思考

通过该方法，解决了前面提出的问题，如果你使用trimToSize()将底层数组缩减到了一个很小的数，此时，只要调用ensureCapacity()将它扩大一些，就可以优化添加元素时的性能。接着我们再来思考一个问题，为什么minExpand取值的时候会判断elementData是否指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA？我们来假设这样一个情况，如果外界进行了如下调用：

List list = new ArrayList();
list.ensureCapacity(1);
list.add(e);
list.add(e);
list.add(e);
list.add(e);

如果在ensureCapacity()里面没有对于elementData是否指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA的判断，这个时候就相当于这样子：

List list = new ArrayList(1);
list.add(e);
list.add(e);
list.add(e);
list.add(e);

这就是前文说过的使用有参数的构造方法创建ArrayList，但是传入较小的数值，在扩容时性能不好。笔者认为，判断elementData是否指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，是ArrayList为了防止外界的“拙劣”使用方式做的预防。

总结

如果想要从功能、接口层面比较好的理解ArrayList，应当要先理解好List，也就是数据结构里面的“线性表”。实际上，ArrayList就是用数组来实现List的功能（对应的有LinkedList用链表来实现List的功能）。

笔者认为ArrayList的方法可以分成三类来看，分别是构造方法、添加元素类方法（add()、ensureCapacity()）、移除元素类方法（remove()、trimToSize()）。在学习添加、移除元素的源码时，最基本的应当学会如何使用数组来实现可变长列表，我们看到并没有真正的可变长数组，只不过是在数组容量不合适的时候（不论太大还是太小），创建新数组并将原有元素复制过去。进一步的，应当学习ArrayList在扩容和缩减容量的时候对性能的考虑和维护。ArrayList至少在三个地方对扩容性能进行了维护：

  1. 对于使用空参数的构造方法创建的ArrayList，在第一次添加元素的时候，在calculateCapacity()里面会返回默认的容量DEFAULT_CAPACITY。
  2. 在grow()里面以扩充50%为基础进行扩容。
  3. 在ensureCapacity()里面避免外界使用空参数的构造方法创建ArrayList后，使用ensureCapacity()传入较小数值导致性能不好。

本文解读了ArrayList所有的字段、构造方法以及部分常用的其它方法，对“增删改查”里面的“增”、“删”进行了详细解读，同时也详细解读了底层数组的扩容和缩减过程。对于复杂方法的解读，都采用了先分析源码、后用流程图梳理一遍思路的方式，应该说是比较清晰的。由于ArrayList里面的“改”、“查”比较简单，就省略了。

相关推荐