JDK1.8 ArrayList源码解析

整个ArrayList源码文件

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
    
    private static final int DEFAULT_CAPACITY = 10;

    
    private static final Object[] EMPTY_ELEMENTDATA = {};

    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    
    transient Object[] elementData; // non-private to simplify nested class access

    
    private int size; //size是数组个数 elementData.length是数组容量

    
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity]; //如果传入的参数大于0，创建initialCapacity大小的数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA; //如果传入的参数等于0，创建空数组
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity); //其他情况，抛出异常
        }
    }

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

    
    public ArrayList(Collection c) {
        Object[] a = c.toArray(); //将指定集合转换为Object数组
        if ((size = a.length) != 0) {   //如果elementData数组的长度不为0
            if (c.getClass() == ArrayList.class) { // 如果指定集合是ArrayList就直接赋值给elementData数组
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);//将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组
            }
        } else {
            // replace with empty array. // 其他情况，用空数组代替
            elementData = EMPTY_ELEMENTDATA;
        }
    }

    
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

    
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0 //判断是不是空的ArrayList,如果是的最小扩充容量10，否则最小扩充量为0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
        // 若用户指定的最小容量 > 最小扩充容量，则以用户指定的为准，否则还是 10
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    // 若 elementData == {}，则取 minCapacity 为 默认容量和参数 minCapacity 之间的最大值 默认容量是10
    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);//调用grow方法进行扩容，调用此方法代表已经开始扩容了
    }

    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; // oldCapacity为旧容量，newCapacity为新容量
        int newCapacity = oldCapacity + (oldCapacity >> 1); //newCapacity为oldCapacity的1.5倍 >>1是右移一位除以2
        if (newCapacity - minCapacity < 0) //然后检查新容量是否小于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，例如数组为空的时候新容量为5 最小容量为10 这时新容量为10
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0) //再检查新容量是否超出了ArrayList所定义的最大容量
            newCapacity = hugeCapacity(minCapacity);//若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE
        // minCapacity is usually close to size, so this is a win://如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

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

    
    public int size() {
        return size;
    }

    
    public boolean isEmpty() {
        return size == 0;
    }

    
    public boolean contains(Object o) {
        return indexOf(o) >= 0;  //indexOf()方法：返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
    }

    
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)//指定元素为null就找第一个null的
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    
    public Object clone() {
        try {
            ArrayList v = (ArrayList) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);//Arrays.copyOf功能是实现数组的复制，返回复制后的数组。参数是被复制的数组和复制的长度
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable  // 这不应该发生，因为我们是可以克隆的
            throw new InternalError(e);
        }
    }

    
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    
    @SuppressWarnings("unchecked")
    public  T[] toArray(T[] a) {
        if (a.length < size) // 若数组a的大小 < ArrayList的元素个数,则新建一个T[]数组
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);// 若数组a的大小 >= ArrayList的元素个数,则将ArrayList的全部元素都拷贝到数组a中。
        if (a.length > size)
            a[size] = null;
        return a;
    }

    // Positional Access Operations

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 元素个数加1
        elementData[size++] = e; //保证要存多少个元素，就只分配多少空间资源 这里看到ArrayList添加元素的实质就相当于为数组赋值 先赋值 size再加1
        return true;
    }

    
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        //第二个是从要复制的数组的第几个开始，第四个是复制到的数组第几个开始，最后一个是复制长度
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//从index开始的元素都右移一位(包括index)
        elementData[index] = element;
        size++;
    }

    
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);//要移除的值

        int numMoved = size - index - 1;//要移动的长度 -1是因为不包括index
        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;
    }

    
    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
    }

    
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    
    public boolean addAll(Collection c) {
        Object[] a = c.toArray();
        int numNew = a.length;//要添加元素的个数
        ensureCapacityInternal(size + numNew);  // Increments modCount，看要不要扩容
        System.arraycopy(a, 0, elementData, size, numNew);//把集合c复制到list里
        size += numNew;
        return numNew != 0;
    }

    
    public boolean addAll(int index, Collection c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;//要添加集合的元素数量
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;//原来list中要移动的数量
        if (numMoved > 0)//从index开始后面的元素右移 0 1 4 5 6  从4添加 2 3，4 5 6右移两位 变成 0 1 _ _ 4 5 6
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        //把指定集合的元素复制到list
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex; //要移动的数量 0 1 2 3 4 from是1 to是3 numMoved = 5 - 3 = 2 3左移2位 变成0 3 4 3 4
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null; // 把后面元素置空 0 3 4 3 4 变成 0 3 4
        }
        size = newSize;
    }

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

    
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    
    public boolean removeAll(Collection c) {
        Objects.requireNonNull(c);//判断集合是否为空，如果为空报NullPointerException
        return batchRemove(c, false);//批量移除c集合的元素，第二个参数：是否采补集
    }

    
    public boolean retainAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    //批量移除 @param c 要移除的集合  @param complement 是否是补集 true 移除list中除c中的所有元素 false 移除list中c的元素
    private boolean batchRemove(Collection c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++) //补集的话就移除c以外的元素，保留c
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

    
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff // 写入所有元素数量的任何隐藏的东西
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);//写入clone行为的容量大小

        // Write out all elements in the proper order.
        for (int i=0; i

总结几个关键的点
ArrayList使用无参构建函数创建是创建了一个空数组，名字是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，然后第一次使用add()添加的时候才会进行扩容，这是懒加载方式
使用有参构造函数创建，如果参数是0就创建一个空数组，名字是EMPTY_ELEMENTDATA，如果参数大于0，就用这个参数创建一个数组

add()方法流程：
先看需不需要扩容：minCapacity加1，如果当前数组是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就用默认容量和+1后的minCapacity比较，取最大值为minCapacity，否则不用比较，然后判断是否比当前数组的长度大，是的话就调用grow方法进行扩容
grow方法：
先取当前数组长度，新数组长度为当前数组长度1.5倍，然后判断新数组长度是否小于minCapacity，小于的话就用minCapacity作为新数组长度，如果新数组长度大于数组长度的上限，再判断minCapacity是否大于数组长度的上限，是的话就把MAX_VALUE作为新数组长度，否的话把数组长度的上限作为新数组长度，最后调用Arrays.copyOf（）方法把旧数组的值移到扩容后的数组

流程图如下