ArrayList浅析

0x00 前言

大家好，我是 ArrayList， 应该是大家都耳熟能详的容器之一了。学习一下内中原理，还是很有必要的。至于为什么叫浅析呢，因为本文不会分析 Arrays 的相关方法。为什么不分析 Arrays 的相关方法，就是浅析了呢？那就接着往下看~（本文分析源码基于jdk1.8。本文基于第一人称描述，我 == ArrayList。）

0x01 一句话介绍

我实际上就是一个可以自动扩容的数组，并可以进行增删改查等操作。

0x02 概述

我是list接口的一个可扩容实现。通过 Java 的泛型机制，我可以容纳任何类型的对象。我和 Vector 非常像，但我是线程不安全的，而他是线程安全的，其他地方的差异很小。

我所有方法中，时间复杂度为O(1)的有：

• size
• get
• isEmpty
• set
• iterator
• listIterator
  而add方法是O(n)的。

我的每个实例，都有一个capacity变量。那么这个变量是干嘛的呢？这个变量用于衡量我内在的数组用来装变量的长度，他总是大于等于 size 。当添加一个元素到我这里，他会自动的增长，以满足需要。

如果一个应用他需要往我这里放置很多的元素，那最好一开始就设置我的 ensureCapacity 变量，这样我一开始就申请很多的空间，而不用我一次次扩容浪费时间了。

请注意，我不是线程安全的！如果多个线程同时修改我，一个要设置同步，否则会出现数据错误的情况，这个锅，我是不背的。简单的方式就是用Collections#synchronizedList来包装一下我，我就变成一个同步的容器了。

我同样拥有fail-fast机制，如果你迭代我，同时又修改我，我就会抛出ConcurrentModificationException异常，让你承受。多线程同时修改迭代，也会出现这个问题。

0x03 解释几个变量

private static final int DEFAULT_CAPACITY = 10

默认的数组大小。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}

如果构造我时，采用的是默认的 capacity ，就使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 来当做默认的空数组。

private static final Object[] EMPTY_ELEMENTDATA = {}

capacity == 0 ，则使用 EMPTY_ELEMENTDATA 来当做默认的空数组。此时，产生了一个疑问，为什么要弄两个这样的变量呢？后面我们在扩容的时候可以看到，他们是用来区分到底是被设置了 capacity 是 0 ，还是使用了默认的 capacity。那区分这个干嘛呢？那就往下看看扩容是怎么扩的。

transient Object[] elementData

先解释一下 transient 这个，这个主要是让此变量不进行序列化。更多的可以谷歌一下，看看详解，此处就略过了。这个就是我的核心部件，我所有的元素都放在他里面！实质就是一个 Object 数组！

private int size

想要知道我里面到底有多少个元素？喏，size 就是我所拥有的元素数量。

0x04 方法分析

构造函数分析

// 拥有设置 capacity 参数的构造函数
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {  // 如果设置的 initialCapacity 初始值大于0，那我的数组就初始相应的长度
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) { 
        // 如果设置了 0 ，那就用 EMPTY_ELEMENTDATA 来初始化我的数组。
        this.elementData = EMPTY_ELEMENTDATA;
    } else { // 小于 0 ，抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 无参构造
public ArrayList() {
    // 直接用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 来初始化我的数组。
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 还有其他构造函数，此处略去不讲。

size()

此方法用于查看我有多少个元素，来看看实现。

public int size() {
    // 非常简单，就是返回 size 变量。
    return size;
}

get(int index)

get 方法用来返回指定索引处的元素。

public E get(int index) {
    // 检查索引是否越界
    rangeCheck(index);
    // 直接根据索引返回元素
    return elementData(index);
}

private void rangeCheck(int index) {
    // 可以看到，如果索引大于等于 size，将会抛出异常。所以在使用时一定要注意不能传入错误的索引，导致程序异常。
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

set(int index, E element)

这个方法相当于修改操作。

public E set(int index, E element) {
    // 检查边界
    rangeCheck(index);
    // 先拿到老的元素
    E oldValue = elementData(index);
    // 对应位置附上新元素
    elementData[index] = element;
    // 返回老元素。所以 set 方法的返回是对应的旧元素。
    return oldValue;
}

add(E e)

这个方法相当于增加操作。

public boolean add(E e) {
    // 确保数组空间充足
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将元素放到原数组长度后面一位。
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    // 这里使用了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 。
    // 这个变量是在我初始化时，使用了默认的 capacity 的时候，用来初始化数组的。
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 在这种情况下， 将入参和 默认 capacity 进行比较，取其较大大者。
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 根据上面的操作，决定了使用什么长度来扩容。下面来进行扩容。
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // 如果会执行这个操作，就代表会改变数组，则将改变标志位+1.
    modCount++;

    // 原文注释这里说可能会有内存溢出
    if (minCapacity - elementData.length > 0) // 如果大于数组长度，则进行扩容。
        grow(minCapacity);
}

// 我内部的数组最大可以这么大，为什么减了个8呢？因为有些VM底层实现，保留了一些内部字段，致使留给用户的长度就变小了。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // 要注意是否会溢出。
    // 先保存数组的原长度。
    int oldCapacity = elementData.length;
    // 新长度是原长度的1.5倍。（右移相当于除以2，所以加起来是1.5倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0) // 如果新长度小于入参长度，则新长度赋值为入参长度。
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新长度大于数组最大长度，则调用 hugeCapacity 方法获取长度。
        newCapacity = hugeCapacity(minCapacity);
    // 调用了 Arrays 的方法，对数组进行了一个复制。
    // 底层就不解释了，可以简单理解为把原 elementData 数组中的值，一个个都搬移到了新的长度为 newCapacity 的数组中，然后让 elementData 指向新数组。
    //（由于没有解析 Arrays.copy 方法，所以本文只能算浅析，后面相关操作，也不会进行解析。要解析的话，一篇文章可能就放不下了。以后专开文章介绍这些工具类。）
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 如果 传递进来的参数小于0，则直接抛异常，此时数组已经放不下了。
        // 什么时候会小于0呢？可以看到参数是通过 index + 1 传递进来的，当index 已经到达了 Integer.MAX_VALUE，则会出现此情况。
        throw new OutOfMemoryError();
    // 发现参数比设置的最大长度还要大，那行吧，那就返回最大值，不然就直接返回最大的数组长度。
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

add(int index, E element)

这个方法实际上是一个插入操作。

public void add(int index, E element) {
    // 范围检查
    rangeCheckForAdd(index);

    // 容量检查
    ensureCapacityInternal(size + 1);  // modCount增加了
    // 直接调用了 System.arraycopy 方法。
    // 这里也不去分析他底层的源码，去分析也不太容易，他实际上是一个 native 方法，要看只能去看 jni 层的代码了。
    // 解释一下现在参数所表示的意思：就是将数组根据传入的 index 分成两部分，然后把后面一部分往后面整体移动一个位置，index位置留出空位。
    // 第一个参数表示源数组
    // 第二个参数表示从哪个位置开始复制
    // 第三个参数表示复制到哪个数组中
    // 第四个参数表示复制从哪里开始
    // 第五个参数表示复制多少位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将 index 位置进行填充
    elementData[index] = element;
    // 长度自增
    size++;
}
举个🌰解释一下 System.arraycopy 的操作。
有一个数组如下：
[0,1,2,3,4,5,6,null,null,null]
现在如果要在第二位插入一个数字7.
第一步：找到第2个位置，是2；
第二步：把第二位开始的字段整体往后迁移一位，变成：[0,1,2,2,3,4,5,6,null,null]
此时数组已经移动完毕，再进行赋值即可。

通过源码的分析，可以看到插入实际上是先对数组进行复制移动，耗费巨大。所以应当避免此操作。

remove(int index)

此即删除操作。

public E remove(int index) {
    // 边界检查
    rangeCheck(index);
    // 修改计数
    modCount++;
    // 找到旧值
    E oldValue = elementData(index);
    // 计算需要移动多少个元素。
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 和 上面的 add 操作调用，如出一辙。
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // 利于内存回收
    // 返回旧值
    return oldValue;
}

可以发现，删除操作也比较费劲，除非是最后一个元素。

remove(Object o)

删除指定元素，可以想象，肯定是一个个的遍历然后对比，再执行删除操作。

public boolean remove(Object o) {
    // null 和 非 null 分开处理，私以为，直接使用 Objects.equals 方法不就好了么。
    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++)
            // 可以看到他调用的是 equals 方法，然而没有调用 == 来判断是否是同一个对象。
            // 所以此处要注意，如果重写了 equals 方法，则同一个对象未必相等。这里可能就识别不到。
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
// 这个方法和 remove 的上一个方法里面的内容一模一样，不知道上个 remove 方法不用。
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
}

clear()

清空此 list。

public void clear() {
    modCount++;

    // 挨个赋值 null
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

contains(Object o) && indexOf(Object o)

为什么这两个方法放在一起呢，因为他们之间是好基友的关系。

public boolean contains(Object o) {
    // 可以看到，直接调用的 indexOf 方法。
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // 还是将 null 和 非 null 进行了区分处理。是不是似曾相识的代码！remove 不也这么做的么！
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

所以可以看到， contains 和 indexOf 实际上都是对数组进行一个遍历操作，所以使用一定要谨慎。而 Set 方法的 contains 方法是直接用的 hash 计算的，复杂度是 O(1).所以尽量用 Set 进行类似操作。

subList(int fromIndex, int toIndex)

从字面上看，他就是返回一个我的孩子 list。

public List<E> subList(int fromIndex, int toIndex) {
    // 边界检查
    subListRangeCheck(fromIndex, toIndex, size);
    // 返回一个 SubList 类！竟然不是 ArrayList
    return new SubList(this, 0, fromIndex, toIndex);
}

看看内部类 SubList 的声明：
private class SubList extends AbstractList<E> implements RandomAccess
和 ArrayList 竟然不一样。
那就看看构造函数吧：

SubList(AbstractList<E> parent,
        int offset, int fromIndex, int toIndex) {
    // parent 当然就是我咯，ArrayList
    this.parent = parent;
    // 相对我的偏移量，就是孩子是从哪开始截取的
    this.parentOffset = fromIndex;
    // 如果儿子也要生儿子，就是产生SubList，则要计算相对爷爷的偏移量，此值就是为了来计算这个。
    // 如果要生重孙子，那就要计算相对于祖爷爷的偏移量。子子孙孙无穷尽也。
    this.offset = offset + fromIndex;
    // 计算孩子有多长。
    this.size = toIndex - fromIndex;
    // 继承父亲的更改计数。
    this.modCount = ArrayList.this.modCount;
}
看一下 SubList 方法的 get 方法。
public E get(int index) {
    // 检查边界
    rangeCheck(index);
    // 检查是否已经被修改
    checkForComodification();
    // 吃惊吗？竟然直接修改的是父亲的数组。
    return ArrayList.this.elementData(offset + index);
}
private void checkForComodification() {
    // 和父亲的修改计数进行一个对比，如果父亲变了，则抛出异常。
    if (ArrayList.this.modCount != this.modCount)
        throw new ConcurrentModificationException();
}
......

可以看到，SubList 实际上并不是拿到了一个和原数组完全分离的数组，对于 SubList 的修改，全都会作用于父亲这里。这就好比儿子惹得祸，父亲都要来背。所以使用此方法一定要注意。同理，生儿子也要慎重！哈哈。

其他方法就先略过了

0x05 喝口水，来个总结

ArrayList 相对来说简单些，但是其中也不乏 contains subList 这种需要注意的方法。知己知彼，方能百战不殆！

文中如有错误，请大家不吝赐教！感激不尽，与君共勉。