ArrayList源码分析

总览

• 底层：ArrayList是List接口的大小可变数组的实现。
• 是否允许null：ArrayList允许null元素。
• 时间复杂度：size、isEmpty、get、set、iterator和listIterator方法都以固定时间运行，时间复杂度为O(1)。add和remove方法需要O(n)时间。与用于LinkedList实现的常数因子相比，此实现的常数因子较低。
• 容量：ArrayList的容量可以自动增长。
• 是否同步：ArrayList不是同步的。
• 迭代器：ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的。

定义

public class ArrayList<E> extends AbstractList<E>

• ArrayList<E>：说明ArrayList支持泛型。
• extends AbstractList<E>：继承了AbstractList。AbstractList提供List接口的骨干实现，以最大限度地减少“随机访问”数据存储（如ArrayList）实现Llist所需的工作。

• implements

  • List<E>：实现了List。实现了所有可选列表操作。
  • RandomAccess：表明ArrayList支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
  • Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
  • java.io.Serializable：表明该类具有序列化功能。

域

/**
     * 默认初始容量大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 指定该ArrayList容量为0时，返回该空数组。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时，其内数据量为0。
     * 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而后者是在用户指定容量为0时返回。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 保存ArrayList数据的数组
     * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入ArrayList中时，数组将扩容值DEFAULT_CAPACITY。
     */
    transient Object[] elementData; 

    /**
     * ArrayList 所包含的元素个数
     */
    private int size;

问题：elementData被标记为transient，那么它的序列化和反序列化是如何实现的呢？

ArrayList自定义了它的序列化和反序列化方式。详情请查看writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectOutputStream s)方法。

构造方法

ArrayList提供了三种构造方法。

• ArrayList(int initialCapacity)：构造一个指定容量为capacity的空ArrayList。
• ArrayList()：构造一个初始容量为 10 的空列表。
• ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

/**
     * 带初始容量参数的构造函数。（用户自己指定容量）
     */
    public ArrayList(int initialCapacity) {
        //初始容量大于0
        if (initialCapacity > 0) {
            //创建initialCapacity大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //创建空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 默认构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，
     * 也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
     * 如果指定的集合为null，throws NullPointerException。
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        //如果指定集合元素个数不为0
        if ((size = elementData.length) != 0) {
            // c.toArray 可能返回的不是Object类型的数组所以加上下面的语句用于判断，
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
            //【2】Arrays包含用来操作数组（比如 排序 和搜索）的各种方法。
            //copyOf(U[] original, int newLength, Class<? extends T[]> newType)
            // 复制指定的数组，截取或用 null 填充（如有必要），以使副本具有指定的长度。
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

核心方法

/**
     * 返回此列表中指定位置的元素。
     * 
     * @param  index 需要返回的元素的索引
     * @return list中索引为index的元素
     * @throws IndexOutOfBoundsException 如果索引超出size
     */
    public E get(int index) {
        //越界检查
        rangeCheck(index);

        return elementData(index);
    }
    
    /**
     * 检查给定的索引是否在范围内。
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    /**
     * 返回索引为index的元素
     */
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

从代码中可以看到，因为ArrayList底层是数组，所以它的get方法非常简单，先是判断一下有没有越界，之后就直接通过数组下标来获取元素。get方法的时间复杂度是O(1)。

/**
     * 将指定的元素追加到此列表的末尾。
     */
    public boolean add(E e) {
        //确认list容量，如果不够，容量加1。注意：只加1，保证资源不被浪费
        ensureCapacityInternal(size + 1);
        //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }

从源码中可以看到，add(E e)有两个步骤：

空间检查，如果有需要进行扩容

插入元素

扩容

/**
     * ArrayList的扩容机制
     * ArrayList的扩容机制提高了性能，如果每次只扩充一个，
     * 那么频繁的插入会导致频繁的拷贝，降低性能，而ArrayList的扩容机制避免了这种情况。
     * 如有必要，增加此ArrayList实例的容量，以确保它至少能容纳元素的数量
     * @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        // 如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，最小扩容量为DEFAULT_CAPACITY，否则为0
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    /**
     * 数组容量检查，不够时则进行扩容。
     *
     * @param minCapacity    想要的最小容量
     */
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，
            // 则取minCapacity为DEFAULT_CAPACITY和参数minCapacity之间的最大值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    //得到最小扩容量
    private void ensureCapacityInternal(int minCapacity) {
        // 获取默认的容量和传入参数的较大值
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    //判断是否需要扩容
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 确保指定的最小容量 > 数组缓冲区当前的长度
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
    }

    /**
     * 要分配的最大数组大小
     * 为什么要减去8呢？
     * 因为某些VM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致array容量大于VM的limit，最终导致OutOfMemoryError。
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * ArrayList扩容的核心方法
     *
     * 第一次扩容，逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。
     * 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。
     */
    private void grow(int minCapacity) {
        // oldCapacity为旧容量，newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量，
        //若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
        //如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        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);
    }

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

看完了代码，可以对扩容方法总结如下：

进行空间检查，决定是否进行扩容，以及确定最少需要的容量

如果确定扩容，就执行grow(int minCapacity)，minCapacity为最少需要的容量

第一次扩容，逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。

第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。

对扩容后的容量进行判断，如果大于允许的最大容量MAX_ARRAY_SIZE，则将容量再次调整为MAX_ARRAY_SIZE。至此扩容操作结束。

add(int index, E element)

/**
     * 在此列表中的指定位置插入指定的元素。
     * 先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal 方法保证capacity足够大；
     * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1); 
        //arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
        //实现让index开始之后的所有元素后移一个位置:
        //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量；
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

从源码中可以看到，add(E e)有三个步骤：

1、越界检查

2、空间检查，如果有需要进行扩容

3、插入元素

add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度，即O(n)

remove(int index)

/**
     * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
     */
    public E remove(int index) {
        //检查索引是否越界
        rangeCheck(index);
        //结构性修改次数+1【1】
        modCount++;
        E oldValue = elementData(index);
        // 删除指定元素后，需要左移的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值
        elementData[--size] = null; 
        //从列表中删除的元素
        return oldValue;
    }

看完代码后，可以将ArrayList删除指定索引的元素的步骤总结为

1. 检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
2. 将索引大于index的元素左移一位（左移后，该删除的元素就被覆盖了，相当于被删除了）。
3. 将索引为size-1处的元素置为null（为了让GC起作用）。

注意：为了让GC起作用，必须显式的为最后一个位置赋null值。上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。

set( int index, E element)

/**
     * 用指定的元素替换此列表中指定索引的元素。
     */
    public E set(int index, E element) {
        //对index进行界限检查
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        //返回原来在这个位置的元素
        return oldValue;
    }