ArrayList源码浅析

简介： `ArrayList`作为我们开发中最常用的集合，作为极高频次使用的类，我们不妨阅读源码一谈究竟。

前言

ArrayList作为我们开发中最常用的集合，作为极高频次使用的类，我们不妨阅读源码一谈究竟。

介绍 ArrayList继承关系如下

AaaryList主要实现了List接口，同时标记为可以序列化Serializable、可复制CloneAble、支持随机访问RandomAccess。

几个重要的成员变量

    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空实例的共享空数组实例。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 用于默认大小的空实例的共享空数组实例。我们将其与空元素数据区分开来，以了解添加第一个元素时要膨胀多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList的大小（它包含的元素数）。
     */
    private int size;

数据结构

ArrayList底层就是一个数组，数组会随着数据的增长而扩容，数组的扩容就是建立一个新的容量大的数组，然后把旧数组上面的数据复制进新数组。关于扩容，后面会详细讲解。

因为是数组，所以支持随机访问，且有序。

常用方法 ArrayList()无参构造方法

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

初始化数组为一个空数组。与空元素数据区分开来，以了解添加第一个元素时要膨胀多少。

add(E e) 添加元素

将指定的元素追加到此列表的末尾

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

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

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

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

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

当添加元素，会先检查是否超出容量，如果超出，则需要扩容。

当第一次添加元素时，size为默认值0，会计算出一个最小容量minCapacity，如果是无参构造创建的，则会取默认的容量10，

Math.max(DEFAULT_CAPACITY, minCapacity)，这里传入的minCapacity为0，所以获取更大的10。

如果计算出的最小容量大于原容量minCapacity - elementData.length > 0，则会进行扩容。

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

扩容算法是，扩为老容量的1.5倍，如果扩容后的容量仍然小于需要的最小容量minCapacity，则新的容量就取最小容量。

如果扩容后的大小超过最大容量，则会进行下面的操作

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

计算出扩容后的容量后，进行扩容，也就是，新建一个数组初始化为新容量，然后复制旧元素到新数组。elementData = Arrays.copyOf(elementData, newCapacity);

    public static  T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

    public static  T[] copyOf(U[] original, int newLength, Class