博客

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList初始容量

看容量就看三个东西：构造器–初始化，add添加元素，remove移除元素(不影响容量)，实际影响容量的是构造器和add方法

从构造器来看，有三种构造器

第一种：给定初始容量，那就按照给定的初始容量

第二种：参数为Collection，那就按照给定的集合的大小

第三种：无参，大小为0.

接下来就是看添加元素的扩充容量。

添加元素：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

使用这个方法来确保容器的容量可以塞得下接下来的元素

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

如果这个容器本来是个空的容器的话，就使用默认元素容量10

否则容量使用下面的方法进行扩容

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

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

首先进行判断是否发生了整数的溢出，如果达到了21亿那么再次加上1的时候就发生了移除，所以要进行溢出的判断，如果达到了最大值的时候就不再进行扩容了，否则使用下面这个方法进行扩容。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //（1+0.5）*oldCapacity,也就是1.5扩容
    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);
}

在这里面需要注意几个问题，如果扩容之后的容量溢出整数最大值执行第二个if，直接扩充成为整数最大值或者是最大值-8，具体执行的是哪一个取决于现在的容量是否会超出最大值-8

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

接下来扩容的方式是使用遍历复制的方式，效率低下，所以在生成数组的时候可以先想好自己要多大的数组，这样可以减少扩容的次数，节约系统资源。

@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

移除元素操作

先进行判断要移除元素的下表是不是大于等于size，并没有判断是不是负数不知道有什么意义。

如果没有超出范围就把数组对应位置后面的元素全部像前面移动，然后把最后一个位置的元素置为null

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