源码之ArrayList底层解析

基于 1.8
目录如下：
00: 构造函数
01: 增删
02: 扩容
03: System.arraycopy & Arrays.copyOf
04：modCount
05：其他方法

00 ：构造函数

关于ArrayList的初始化，主要看其构造方法是如何实现的，ArrayList总共有三种构造方法

无参构造

    /**
     * 使用默认10的长度构造一个空的的列表
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

与上述方法涉及的变量有：
```
    /**
     * 保存ArrayList的数组。
     通过无参构造方法构造的数组，只有在第一个元素添加的时候，才扩充到10
     */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
      用于默认大小空实例的共享空数组实例。
          我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
```
关于上面的这两个变量也很有说法。

elementData是用于保存ArrayList数组的，也就是之后的所有操作，增删查扩容，都是在它的基础上。与之同时定义的Object[] 类型的数组还有EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA，其中前者是用于空实例的空数组，后者是用于默认大小空实例的共享空数组实例。

这两个Object类型的数组都是用来共享空数组的。但是不同的是，所用到的构造函数不同。这两个不同的数组会影响到后面的扩容机制，我们后面再看。这就是无参构造涉及的所有内容了。

含参构造 - int 参数

先看有参构造代码是怎么写的，传入的是用户指定的数组容量的大小：

    /**
     *使用指定的初始化容量构造一个空的列表
     * @param  指定列表的初始化大小
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) { //如果指定的初始化大小大于0 ，就直接new一个实例赋给elementData
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
            this.elementData = EMPTY_ELEMENTDATA;//如果指定的初始化大小是0 ，就使用EMPTY_ELEMENTDATA，EMPTY_ELEMENTDATA是已经定义好的，用于空实例的空数组。
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

我们先看initialCapacity == 0的情况，此时使用到的就是用于空实例的空数组empty_elementdata。那看一下下面两种定义List的方式：

List<Object> manner_one = new ArrayList<>();
List<Object> manner_two = new ArrayList<>(0);
也就是这两种方式运行的代码其实类似，只不过elementData指向的数组地址不一样，但目前都是空的。

我们再看initialCapacity>0的情况，此时elementData直接使用指定的大小初始化了一个Object数组。

含参构造- Collection参数

先贴代码再解析：

/**
* 构建一个包含传入的Collection所有值的list
**/
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray(); //讲c转换成array，但是看下面链接的意思是，有时候会有bug，所以有下面长度判断的处理了
    //如果总长大于0
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)//如果转换成array之后，不是object[]类型，就换另一种方式进行复制
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

可以看到上面的构造方法也分为两种情况，一种就是传入的Collection为空，一种不为空。这个比较好理解，看注释就好了，最后一点就是，实现了Collection接口的有HashSet(Set)、LinkedList(List)以及ArrayList(List)。

到此，三种关于ArrayList的构造方法就解析完毕了，传入的参数呢有空的，有int的，有collection的。最后用于保存arraylist的数组为elementdata，如果说用户没有指定容量的话，就使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA3赋值给elementdata，如果说指定的长度为0或者传入的collection的长度为0，就使用EMPTY_ELEMENTDATA赋值给elementdata。

01 ：增删

总览一下相关的方法：add、remove、get、set。

add方法

提供给ArrayList增加元素的方法也不止一个，根据参数传入的不同会运行不同的逻辑，我们先看只传入值的时候是如何添加的：

    /**
     * 将指定的值插入到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);  // 扩容
        elementData[size++] = e; //赋值
        return true;
    }

上述方法目的就是将传入的值插入到list的最后一个位置，插入之前先对list进行扩容，稍后我们再看扩容机制是如何实现的。

    /**
    * 将指定的值插入到指定的位置中
    **/
  public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // 扩容
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//后移，将elementdata中从index开始，移动到element中index+1开始的位置，移动的个数就是size-index
        elementData[index] = element;
        size++;
    }
  /**
  *检查指定的下标是否在list的范围之内
  **/
  private void rangeCheck(int index) {
    if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

上面就是关于add方法的全部了，里面都用到了ensureCapacityInternal方法，这也是ArrayList十分重要的一个特征，我们后面再分析这个方法。

remove

remove方法也有多个可选，可以传入指定的下标，也可以传入要删除的对象。我们先看传入指定的下标的时候，代码都在干什么：

/**
*删除指定位置的值，并将整个list左移，返回值就是删除的老值
**/
public E remove(int index) {
        rangeCheck(index);//判断是否在list的范围之内

        modCount++; //标记一下
        E oldValue = elementData(index);//取出老数据

        int numMoved = size - index - 1;//需要向坐移动的元素的数量，size-(index+1)
        if (numMoved > 0) //如果有需要移动的数量，就比如删除的值是list中间的值
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//将elementData中，从index+1位置开始的值移动到elementData中，从index开始的位置，移动的数量是numMoved个
        elementData[--size] = null; // 将末尾置为空，让GC工作=

        return oldValue;
    }

可以看出来，上面的逻辑并不复杂，就是确保后面的值向左移动就好了。我们再看另外一个：

    /**
    * 删除list中指定的首个出现的元素，如果指定的元素并不存在，就返回false
    **/
  public boolean remove(Object o) {
        if (o == null) { //指定的删除的值是Null
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) { //找到了首个为null的元素的下标
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {//找到了首个等于o的元素的下标
                    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
    }

不难理解，相比于传入index的删除方式，没变化多少，就多了个找到首个与指定删除的对象相等的下标的步骤。

02 ：扩容

我们来仔细研究扩容机制的实现，重中之重。

由于上面add方法使用扩容的时候，是调用的ensureCapacityInternal方法，所以我们先来看它：

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//判断是不是通过无参构造的方式来创建的ArrayList
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//判断扩容的大小和10来比，谁大
        }

        ensureExplicitCapacity(minCapacity);//扩容
    }

这里可以看到我们之前区分的DEFAULTCAPACITY_EMPTY_ELEMENTDATA在这里作为判断条件传入了，而这个判断条件就是区分此时的elementData是通过哪种方式创建的，如果是通过无参的方式，就会进入判断内的代码，获取当前需要扩容的大小和默认的容量谁大，取最大值进行后续的扩容。

当时用来区分的EMPTY_ELEMENTDATA，如果当时是传入size是0，此时的elementData就等于EMPTY_ELEMENTDATA，就不会进入判断题，就只会根据目前需要扩容多少就扩多少。

我们打个比方，如果有以下两种方式创建的ArrayList，并同时add一个值，看下两者走到哪个位置：

        List<Object> manner_one = new ArrayList<>();
        manner_one.add(1);

[图片上传失败...(image-459d93-1614775427503)]

        List<Object> manner_two = new ArrayList<>(0);
        manner_two.add(2);

image-20210303193741645

那ensureCapacityInternal又是怎么实现的呢？看代码：

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//标记一下

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//这里就体现了上面两种方式的区别了
            grow(minCapacity);//调用grow方法开始扩容
    }

我们看为啥minCapacity - elementData.length > 0能区分上面两种方式，如果是通过第一种方式，添加第一个值的时候此时minCapacity就是10，再添加值，也不会进行grow明知道添加到11个元素的时候才会。

其他没啥东东，我们继续往下走

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; //之前的容量就是elementData的长度
    int newCapacity = oldCapacity + (oldCapacity >> 1); //新的容量为将OdlCapacity右移以为，相当于/2，即A+A/2，相当于扩充了原来的1.5倍
    if (newCapacity - minCapacity < 0)//检查新容量(老容量的1.5倍)与指定的扩容量之间的大小关系，如果1.5还小于指定的，就将指定的容量置为需要扩容的大小
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)//如果目前最新的容量比最大的容量还大的话，调用hugeCapacity函数，来比较指定的minCapacity大小和MAX_ARRAY_SIZE的大小，如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
        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;
    }

除了上面两个用于代码内扩容的方法外，还有public，提供给用户来扩容的方法：

/**
*如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。
**/
public void ensureCapacity(int minCapacity) {
    //如果elementData此时不等于无参构造创建的list，则最小扩容的数目为10，反之为0
    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;
    //大于minExpand才进行扩容
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

03：System.arraycopy & Arrays.copyOf

arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置

copyOf() 是系统自动在内部新建一个数组，并调用arraycopy()返回该数组。

04：modCount

zhu要目的是在使用迭代器迭代中判断是否被修改：参见https://segmentfault.com/a/1190000015606139

05：其他方法

https://wowhhh.github.io/2020/12/01/ArrayListSourceCode/