ArrayList的源码解读

ArrayList 的应用场景

ArrayList的底层数据结构是数组，也就是说它满足数组的特点，数组的优势在于：它在物理内存上的地址是一块连续的内存空间，这无疑对查询的操作是友好的，查询的时间复杂度为O(1)，但就结构改变的操作是很浪费时间的，因为当数组的元素很多的时候，ArrayList集合下大部分删除增加方法的时间复杂度接近O(n)，add(E e)除外，它是直接插入在数组末尾，时间复杂度为O(1)。

它与List接口下的其他集合的区别

List接口下有三个集合类：ArrayList、LinkedList、Vector

• LinkedList：底层是基于双向链表实现的，查询慢、增删效率高。

    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

• Vector：底层是基于数组实现，同ArrayList相同，只不过它是线程安全的集合，被synchronize修饰

    public synchronized void copyInto(Object[] anArray) {
        System.arraycopy(elementData, 0, anArray, 0, elementCount);
    }

当然List接口下面还有很多子类的实现类：比如Stack，它扩展自Vector集合，这里不会展开它，后期它处再详细解释。

ArrayList集合中的一些方法

• add(E e)，增加元素，如下是这个代码的执行流程，难懂的地方加了注释，请12345按照序列阅读

transient Object[] elementData; 

//当你未指定容量大小的时候 如：List list = newArrayLIst();
//它的底层数组容量默认采用这个常量
private static final int DEFAULT_CAPACITY = 10;  

public boolean add(E e) {
       //1、判断当前数组容量的大小是否能执行增加元素这一操作
        ensureCapacityInternal(size + 1);
       //5、将这个新元素放在index++这个索引位置
        elementData[size++] = e;
        return true;
}

private void ensureCapacityInternal(int minCapacity) {
        //2、如果数组的长度确实和默认大小是相等的
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //3、取这俩个之中大的那一个给这个minCapacity变量
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
         //4 确定新数组的大小
        ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
        //4.1  protected transient int modCount = 0; 
        //这个值是用来判断并发操作下
        //处于迭代器遍历下的这个集合里面的值有没有被其他线程修改，如果变了，那么直接抛出异常
        //这个机制称之为快速失败机制
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //4.2
            grow(minCapacity);
}

/*
这个就是它的扩容机制了
*/
private void grow(int minCapacity) {
        // 原数组容量大小，是指这个数组的长度而不是元素个数
        int oldCapacity = elementData.length;
        // 新数组的容量是原来的1.5倍。这里>>1操作是进行了一个移位运算，向右移一位，相当于除2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //这下面就是和原来的miniCapacity比较、然后取值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //这里值的注意的是，当你的数组容量起初已经很大的时候，可能会超出它对数组本来的大小限制
        //这时候就会进行一个再取值，反正最后的数组大小就是它指定的一个大小。不是你的值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 这里就是将原数组的内容拷贝到新长度的数组容器中，并覆盖掉原数组，让GC回收它
        elementData = Arrays.copyOf(elementData, newCapacity);
}

• add(int index, E element)，按指定索引添加

public void add(int index, E element) {
        //检查索引范围是否合法
        rangeCheckForAdd(index);
        //熟悉的方法，同add里的相同，这一步是再判断集合里面还有没有容量来容下这个元素
        ensureCapacityInternal(size + 1); 
        //首先我们要明确一点，这个集合底层的删除和按索引添加其实就是创建了一个新的数组，将旧数组里的
        //部分信息复制进新数组，下面这个方法可以这么理解
        //参数：源数组、从源数组中的起始位置、目标数组、从目标数组的起始位置、复制的步长
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        //将元素放入新数组
        elementData[index] = element;
        size++;
}

• remove(int index) 删除元素

protected transient int modCount = 0;
public E remove(int index) {
        //索引检查是否合法
        rangeCheck(index);
        //基于快速失败机制，为保证集合的安全性，如果这个modCount被修改，直接抛出异常，终止操作
        modCount++;
        E oldValue = elementData(index);
        //需要移动的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        //末尾索引位置的元素设置未null
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
}

• removeRange(int fromIndex, int toIndex) 删除指定范围内的元素

private final AbstractList<E> l;
private final int offset;
private int size;

protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        //复制数组，从源数组toIndex位置开始，目标数组fromIndex位置开始。复制源数组numCount个元素
        System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);

        // 将末尾空出来的位置numMoved个位置设置为null，等待GC回收
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
}