ArrayList 部分源码解析

写在前面

这里取用的是 jdk 1.8 的源码

类变量

// ***
private static final long serialVersionUID = 8683452581122892189L;

// 初始容量为 10
private static final int DEFAULT_CAPACITY = 10;

// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存储元素数组
transient Object[] elementData;

// 集合中元素个数
private int size;

构造器

第一个构造器是无参的，把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个默认空数组赋给 elementData 存储元素数组，这个时候 elementData 中没有元素，且 size 为 0

// 第一个构造器-无参
public ArrayList() {
    // 默认空数组赋给存储元素数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

第二个构造器带有一个参数，指明初始化容量，只有在 >= 0 的时候才有意义，否则报异常，大于 0 时候直接依据传入值创建数组 elementData，等于 0 时，将 EMPTY_ELEMENTDATA 赋给 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);
    }
}

第三个构造器带有一个 Collection 参数，就是集合转为数组赋给 elementData，然后 size 初始化，但是这个elementData.getClass() != Object[].class起什么作用呢？我们可以看见c.toArray()这个方法返回值是 Object 类型数组，那elementData.getClass() != Object[].class不是没有意义吗，有意义，问题就在于万一有人继承了 Collection 接口并重写了 toArray 方法，这样有可能出现elementData.getClass() != Object[].class，所以怎么做呢？通过Arrays.copyOf(elementData, size, Object[].class)将它转为 Object 类型就行了

// 第三个构造器
public ArrayList(Collection<? extends E> c) {
    // Collection 转为数组赋给 elementData
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 数组不为空
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 若数组为空，空数组给 elementData
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

add 方法

add 有两个方法，这里我主讲传一个参数的方法。这里的 E 就是ArrayList<E>一致，size 是里头有几个元素，所以要先用后加 size++，当前有 size 个元素，有元素的最后一个下标是 size-1，所以我们当前一定要保证下标为 size 的空间是存在的，还要保证 size+1 后的空间是存在的，所以有了 ensureCapacityInternal() 这个方法

// 增添数据
public boolean add(E e) {
    // 确定容量足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal 方法

我们再来看一下 ensureCapacityInternal() 起到的作用，这里的 minCapacity = size + 1

// 确保内部容积
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

ensureExplicitCapacity 方法

ok，我们继续深入，再看一下 ensureExplicitCapacity 和 calculateCapacity 方法，这里的 minCapacity = size + 1，注意其实上面还有个类变量protected transient int modCount = 0;这个 modCount 是什么呢？我们在 add 方法中可以看到这样的注释// Increments modCount!!，它是自增长的，主要就是为了记录当前 ArrayList 集合操作变化的次数。我们依旧记得，当前元素个数是 size，最后一个元素下标是 size-1，minCapacity=size+1（实际会使用 calculateCapacity 方法计算一下），现在要是 size+1 大于 elementData 数组空间长度，即本来数组空间都占满了，加一个之后就超出了的情况下，我们会调用 grow 方法来扩展空间，grow 方法我们先放一下，我们先看下上面还有个 calculateCapacity 没讲到

// 确保明确容积
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

grow 方法

我们再看下 grow，这里有个 MAX_ARRAY_SIZE 等于 Integer 最大值减 8，当扩容后的容量要比 Integer 的最大值还要大 8，就会使用 hugeCapacity 这个方法，最后扩容到 newCapacity。其中int newCapacity = oldCapacity + (oldCapacity >> 1);我们可以发现位运算扩容机制为超过 10 时候扩容是 1.5 倍的机制

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

calculateCapacity 方法

现在我们看下 calculateCapacity 方法，现在我们已经了解了 ensureCapacityInternal 里头应该会判断执行相应的扩容机制，深入进去，是 ensureExplicitCapacity 中执行了扩容，在深入发现真正是 grow 在起作用

下面代码如果 size+1 还是比 10 小返回就是 10，否则是 size+1，我们也可以发现 grow 传的参数是 10 和 size+1 的较大者，这也就是说一旦我们创建了一个 ArrayList，不管是传容量还是传 Collection，只要第一次创建时候容量是小于 10，可能容量为 1，那么在执行一次 add 方法后容量必然会陡然扩容到 10

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

为什么ArrayList线程不安全

我们先看 add 方法中的 ensureCapacityInternal 方法，假如第一个线程执行到 add 里头，但是 ensureCapacityInternal 还没有执行，然后第二个线程执行到 add 里头，然后开始执行 ensureCapacityInternal 方法，假如这时候空间是 10，元素个数是 9，那就意味着 ensureCapacityInternal 方法不回去扩容，然后第一个线程也去执行 ensureCapacityInternal 方法，同样因为元素个数还是 9 个也不会扩容，这时候第二个线程执行了elementData[size++] = e;给最后一个空间赋值，然后++，这时还没有问题，问题是第一个线程这时候也执行elementData[size++] = e;了，那么就相当于elementData[10] = e;然后10+1，可是此时最大下标只可能是 9 而不是 10，所以会产生数组越界问题。

另外elementData[size++] = e;本身就可能在多线程时候值被覆盖，因为elementData[size++] = e;可以分为两行程序elementData[size] = e;和size++，当线程一运行完elementData[size] = e;，线程二就开始运行elementData[size] = e;，这时 size 下标的值就会被覆盖掉