java【集合类】源代码分析--ArrayList

基于jdk9的集合类源代码注释和分析，只写了方法的主要功能注释，后面的一些内部类方法并没有。

 

一、ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, 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 = {};

    /**
     * 该ArrayList使用数组对象的变量名
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 数组的长度
     */
    private int size;

    /**
     * 使用有参构造函数，初始化数组的大小
     * @param initialCapacity：初始化数组的大小
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        	//传入参数>0，则初始化数组长度为initialCapacity
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        	//如果传入的数组长度=0，则使用EMPTY_ELEMENTDATA对象作为存储数据的数组对象
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 默认构造函数，使用默认的数组对象DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * 作为存储数据的数组对象
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 传入一个集合对象，并该集合的所有元素添加到本对象的数据数组
     * @param c：传入的集合对象
     */
    public ArrayList(Collection<? extends E> c) {
    	// 转换为数组，赋值给数据数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
        	// 传入的集合为空（0个数据），则使用默认的数组对象
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    /**
     * 压缩数组，除去所有值为null的元素，并更新数组长度
     */
    public void trimToSize() {
    	// 自增修改次数
        modCount++;
        // 数据个数<数组长度，执行压缩数组操作
        if (size < elementData.length) {
        	// 重新给数据数组赋值
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

    /**
     * 保证数组最小容量，如果数组容量>minCapacity，则为数组扩容
     * @param minCapacity
     */
    public void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length
            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                 && minCapacity <= DEFAULT_CAPACITY)) {
        	// 自增修改次数
            modCount++;
            // 为数组扩容为minCapacity
            grow(minCapacity);
        }
    }

    /**
     * 数组最大容量
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 为数组扩容为minCapacity
     * @param minCapacity
     * @return
     */
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    /**
     * 为数组扩容为（原长度+1）
     * @return
     */
    private Object[] grow() {
        return grow(size + 1);
    }

    /**
     * 设置扩容后的数组长度
     * @param minCapacity：最小容量
     * @return
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
    	// 旧容量为原数组长度
        int oldCapacity = elementData.length;
        // 默认容量增长为原来的0.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 对比传入的minCapacity与默认增加的容量，选取合适的容量值（大的值）
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(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;
    }

    /**
     * 返回列表长度（数据个数）
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 返回列表是否为空，即没有数据
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回列表是否包含该元素
     * @param o
     * @return
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    /**
     * 返回列表某个元素的下标，如果元素为null，返回数组中第一个null元素的下标
     * 若不为null，则返回数组中第一个该元素的下标
     * 若未找到该元素，则返回-1
     * @param o
     * @return
     */
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * 由后往前操作元素的下标，原理与indexOf方法一致
     * @param o
     * @return
     */
    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;
    }

    /**
     * 返回一个本身的副本
     * @return
     */
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

    /**
     * 返回自身的数据数组对象的副本
     * @return
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 返回一个长度为max(自身数组长度，目标数组长度)，类型为目标数组类型的数组
     * 如果自身数组长度 < 目标数组长度，返回[自身数组..,null,目标数组[自身数组长度..目标数组长度]]的数组
     * [自身数组..,null,目标数组[自身数组长度..目标数组长度]]表示返回的数组有3部分组成
     * @param a
     * @return
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // 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);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    /**
     * 返回下标为index的元素
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    /**
     * 返回es数组中下标index的元素
     * @param es
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    static <E> E elementAt(Object[] es, int index) {
        return (E) es[index];
    }

    /**
     * 返回下标index的元素
     * @param index
     * @return
     */
    public E get(int index) {
        Objects.checkIndex(index, size);
        return elementData(index);
    }

    /**
     * 设置下标index的元素的值
     * @param index
     * @param element
     * @return
     */
    public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    /**
     * 添加新元素到下标（0开始）为s的位置
     * @param e
     * @param elementData
     * @param s
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    /**
     * 添加新的元素
     * @param e
     * @return
     */
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

    /**
     * 添加新的元素到下标（0开始）为s的位置
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }

    /**
     * 删除下标index的元素
     * @param index
     * @return 删除的元素
     */
    public E remove(int index) {
    	// 检查是否越界
        Objects.checkIndex(index, size);
        // 自增修改次数
        modCount++;
        E oldValue = elementData(index);

        // 获得移除元素的下标
        int numMoved = size - index - 1;
        // 把numMoved后的数组复制到前一位（即把numMoved后的所有元素往前移动1位）
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 设置下标为size-1元素值为null，size自减 
        elementData[--size] = null; // clear to let GC do its work
        // 返回删除的元素
        return oldValue;
    }

    /**
     * 删除第1个o元素，0元素允许为null
     * @param o
     * @return
     */
    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;
    }

    /**
     * 删除下标为index的元素，不返回被删除的元素
     * @param index
     */
    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++;
        final Object[] es = elementData;
        for (int to = size, i = size = 0; i < to; i++)
            es[i] = null;
    }

    /**
     * 从末尾添加全部集合c的元素
     * @param c
     * @return
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }

    /**
     * 从下标index处插入集合c的所有元素
     * @param index
     * @param c
     * @return
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);

        int numMoved = s - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index,
                             elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size = s + numNew;
        return true;
    }

    /**
     * 删除下标从fromIndex到toIndex的元素（不包括该元素）
     * @param fromIndex：开始下标
     * @param toIndex：结束下标
     */
    protected void removeRange(int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IndexOutOfBoundsException(
                    outOfBoundsMsg(fromIndex, toIndex));
        }
        modCount++;
        shiftTailOverGap(elementData, fromIndex, toIndex);
    }

    /**
     * 把数组es中下标hi往后的所有元素移到下标lo开始的位置
     * @param es
     * @param lo
     * @param hi
     */
    private void shiftTailOverGap(Object[] es, int lo, int hi) {
        System.arraycopy(es, hi, es, lo, size - hi);
        for (int to = size, i = (size -= hi - lo); i < to; i++)
            es[i] = null;
    }

    /**
     * 返回添加方法中下标越界异常信息
     * @param index
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * 返回下标越界异常信息
     * @param index
     * @return
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    /**
     * 返回范围不在数组范围中的异常信息
     * @param fromIndex
     * @param toIndex
     * @return
     */
    private static String outOfBoundsMsg(int fromIndex, int toIndex) {
        return "From Index: " + fromIndex + " > To Index: " + toIndex;
    }

    /**
     * 删除本集合与集合c交集的所有元素
     * @param c
     * @return
     */
    public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false, 0, size);
    }

    /**
     * 保留本集合与集合c交集的所有元素
     * @param c
     * @return
     */
    public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true, 0, size);
    }

    /**
     * 批量删除方法
     * @param c：参照集合
     * @param complement   false：删除本集合与c交集的所有元素；true：删除本集合与结合c补集的所有元素
     * @param from	：开始删除的下标
     * @param end	：结束删除的下标
     * @return
     */
    boolean batchRemove(Collection<?> c, boolean complement,
                        final int from, final int end) {
        Objects.requireNonNull(c);
        final Object[] es = elementData;
        final boolean modified;
        int r;
        // 参照第一个不符合条件的元素的下标（即第一个要删除的元素的下标）
        for (r = from; r < end && c.contains(es[r]) == complement; r++)
            ;
        if (modified = (r < end)) {
            int w = r++;
            try {
            	// 从第一个不符合元素往后遍历符合条件的元素
            	// 符合条件的元素添加到第一个不符合条件元素的位置，不符合元素下标+1（忘记这是什么算法了）
                for (Object e; r < end; r++)
                    if (c.contains(e = es[r]) == complement)
                        es[w++] = e;
            } catch (Throwable ex) {
                System.arraycopy(es, r, es, w, end - r);
                w += end - r;
                throw ex;
            } finally {
            	// 更新修改次数
                modCount += end - w;
                // 删除后面所有不符合条件的元素
                shiftTailOverGap(es, w, end);
            }
        }
        return modified;
    }

    /**
     * 写入输出流中
     * @param s
     * @throws java.io.IOException
     */
    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);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * 从输入流中读取
     * @param s
     * @throws java.io.IOException
     * @throws ClassNotFoundException
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // like clone(), allocate array based upon size not capacity
            SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
            Object[] elements = new Object[size];

            // Read in all elements in the proper order.
            for (int i = 0; i < size; i++) {
                elements[i] = s.readObject();
            }

            elementData = elements;
        } else if (size == 0) {
            elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new java.io.InvalidObjectException("Invalid size: " + size);
        }
    }

    /**
     * 返回迭代器，从index开始（包含index）
     * @param index
     * @return
     */
    public ListIterator<E> listIterator(int index) {
        rangeCheckForAdd(index);
        return new ListItr(index);
    }

    /**
     * 返回迭代器，从0开始
     * @return
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    /**
     * 返回迭代器
     * @return
     */
    public Iterator<E> iterator() {
        return new Itr();
    }
    
    /**
     * 返回数据数组的子元组
     * @param fromIndex
     * @param toIndex
     * @return
     */
    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList<>(this, fromIndex, toIndex);
    }


    /**
     * forEach方法
     */
    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        final Object[] es = elementData;
        final int size = this.size;
        for (int i = 0; modCount == expectedModCount && i < size; i++)
            action.accept(elementAt(es, i));
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}