Java源码分析之ArrayList

之前整理了HashMap的源码分析
接下来，这里整理的是ArrayList的源码分析

对于ArrayList，我们需要知道以下几点：

ArrayList实现了List接口，是顺序容器，元素存取的顺序相同。
允许放入null元素，底层通过数组实现。
除该类未实现同步外，其余跟Vector大致相同。
每个ArrayList都有一个容量（capacity），表示底层数组的实际大小。
容器内存储元素的个数不能多于当前容量。
当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。
所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。

ArrayList初始化时候是一个空的Object数组
    private transient Object[] elementData;
    
当添加第一个元素的时候，数组的大小变成10（也就是数组的默认大小）
    private static final int DEFAULT_CAPACITY = 10;

Add方法

每次add的时候都会进行剩余空间检查。
    minCapacity = size + 1;
    如果是第一次，则空间大小（minCapacity）直接变成10，再执行如下步骤：
    1.判断minCapacity是否大于elementData.length
        即：if (minCapacity - elementData.length > 0)
    2.条件成立：grow(minCapacity);
    3.grow内部调用Arrays.copyOf进行数组复制
    4.Arrays.copyOf调用System.arrayCopy进行数组复制

private void grow(int minCapacity) {
    // 新数组增长为之前的1.5倍
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果还是小与minCapacity，那么变成minCapacity
    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);
}
//最大容量变成Integer.MAX_VALUE,或者超出MAX_VALUE范围，跑出OutOfMenory异常
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

System.arraycopy(源数组, 源数组起始位置, 目标数组, 目标起始位置, 复制长度);
System.arraycopy(elementData, index+1, elementData, index, numMoved);

检查是否越界

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

Set方法

既然底层是一个数组ArrayList的set()方法也就变得非常简单，直接对数组的指定位置赋值即可。

public E set(int index, E element) {
    rangeCheck(index); // 下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element; // 赋值到指定位置，复制的仅仅是引用
    return oldValue; // 返回之前的元素
}

Get方法

get()方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

Remove()方法

remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素，
另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。
删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。
需要注意的是为了让GC起作用，必须显式的为最后一个位置赋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;
}


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

// 此方法跟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
}

AddAll方法

//把指定的集合元素添加到list后面，先进行容量检查，然后复制
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

//在指定位置插入指定的集合元素
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    // 原数组：头部 + 尾部
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 新数组：头部 + 空 + 尾部
    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 新数组：头部 + 新增 + 尾部
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}