ArrayList源码分析

摘要：表明该类具有序列化功能。关键属性默认初始容量大小指定该容量为时，返回该空数组。构造一个包含指定的元素的列表，这些元素是按照该的迭代器返回它们的顺序排列的。对扩容后的容量进行判断，如果大于允许的最大容量，则将容量再次调整为。

底层：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 extends AbstractList 
implements List, RandomAccess, Cloneable, java.io.Serializable

ArrayList：说明ArrayList支持泛型。

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

implements

List：实现了List。实现了所有可选列表操作。

RandomAccess：RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 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 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 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 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));
    }
    
    /**
     * 返回IndexOutOfBoundsException细节信息
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    
    /**
     * 返回索引为index的元素
     */
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

步骤：

检查是否需要扩容

插入元素

整个扩容过程：

首先去检查一下数组的容量是否足够

足够：直接添加

不足够：扩容

扩容到原来的1.5倍

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

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

扩容

/**
     * 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。至此扩容操作结束。

步骤：

越界检查

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

插入元素

    /**
     * 在此列表中的指定位置插入指定的元素。
     * 先调用 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(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度，即O(n)

步骤：

检查角标

删除元素

计算出需要移动的个数，将索引大于index的元素左移一位（左移后，该删除的元素就被覆盖了，相当于被删除了）

设置为null（size-1处），让Gc回收

    /**
     * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
     */
    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;
    }

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

步骤：

检查角标

替代元素

返回旧值

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

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

细节：

ArrayList是基于动态数组实现的，在增删时候，需要数组的拷贝复制。

ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍

删除元素时不会减少容量，若希望减少容量则调用trimToSize()

它能存放null值。

和 Vector 不同，ArrayList 中的操作不是线程安全的！所以，建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。

移位运算符 　　
简介：移位运算符就是在二进制的基础上对数字进行平移。按照平移的方向和填充数字的规则分为三种:<<(左移)、>>(带符号右移)和>>>(无符号右移)。 　　
作用：对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源 　　
比如这里：int newCapacity = oldCapacity + (oldCapacity >> 1); 右移一位相当于除2，右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。
另外需要注意的是：

java 中的length 属性是针对数组说的，比如说你声明了一个数组，想知道这个数组的长度则用到了 length 这个属性.

java 中的length()方法是针对字符串String说的，如果想看这个字符串的长度则用到 length()这个方法.

java 中的size()方法是针对泛型集合说的，如果想看这个泛型有多少个元素，就调用此方法来查看!

内部类：

(1)private class Itr implements Iterator  
(2)private class ListItr extends Itr implements ListIterator  
(3)private class SubList extends AbstractList implements RandomAccess  
(4)static final class ArrayListSpliterator implements Spliterator  

Itr是实现了Iterator接口，同时重写了里面的hasNext()，next()，remove()等方法；

ListItr继承Itr，实现了ListIterator接口，同时重写了hasPrevious()，nextIndex()，previousIndex()，previous()，set(E e)，add(E e)等方法，

所以这也可以看出了 Iterator和ListIterator的区别：ListIterator在Iterator的基础上增加了添加对象，修改对象，逆向遍历等方法，这些是Iterator不能实现的。

参考资料：
https://blog.csdn.net/panweiw...
https://segmentfault.com/a/11...
https://github.com/Snailclimb...