Java8 ArrayList源码阅读

概述

public class ArrayList<E> extends AbstractList<E>
          implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList继承于AbstractList，实现了List接口，是一个长度可变的集合，实现了RandomAccess接口，Serializable接口，Cloneable接口，即ArrayList支持随机访问、可序列化、可克隆。ArrayList中允许存在null值，此外，和Vector不同的是，ArrayList不是线程安全的，所有的方法均不是同步方法也没有加锁。

fail-fast机制

fail-fast机制也被称为”快速失败”机制，是Java集合中的一种错误检测机制。在对集合进行迭代过程中，除了迭代器可以对集合进行修改(add,set,remove操作)，其他的对集合进行修改(同上)，都会抛出ConcurrentModificationException错误。

该机制是基于一个变量——modCount实现的，每次对ArrayList进行add，set，remove等操作，都会执行modCount++。在获取ArrayList的迭代器时，会将ArrayList中的modCount保存在迭代中，每次执行add,set,remove等操作，都会执行一次检查，调用checkForComodification方法，对modCount进行比较。如果迭代器中的modCount和List中的modCount不同，则抛出ConcurrentModificationException

elementData被transient修饰的原因

由于ArrayList的底层是基于动态扩容数组实现的，即elementData中可能会存在一些空值，在序列化时显然是不需要这些值的。所以ArrayList的设计者将elementData设计为transient，然后在writeObject方法中手动将其序列化，并且只序列化了实际存储的元素，而不是整个elementData。

ArrayList源码阅读笔记

package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = 8683452581122892189L;

    // 无参构造方法的初始容量为10

    private static final int DEFAULT_CAPACITY = 10;

    // 实例化空数组

    private static final Object[] EMPTY_ELEMENTDATA = {};


    // 由此可以看出ArrayList底层是用数组实现的，用transient修饰以防止被自动序列化

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

    // 实际元素数量
    private int size;

    // ArrayList实现了下面三种构造方法

    // 有参构造方法一，应该是最常用的构造方法了，用于创建一个大小为initialCapacity的数组，若该参数为负数将抛出IllegalArgumentException异常

    public ArrayList(int initialCapacity) {

        super();

        if (initialCapacity < 0)

            throw new IllegalArgumentException("Illegal Capacity: " +

                    initialCapacity);

        this.elementData = new Object[initialCapacity];

    }


    // 无参构造方法，用一个默认容量为10的空数组进行初始化

    public ArrayList() {

        super();

        this.elementData = EMPTY_ELEMENTDATA;

    }


    // 有参构造方法二，比较少用，该方法会构造一个包含指定集合的元素的ArrayList，并按照集合迭代器的顺序返回

    public ArrayList(Collection<? extends E> c) {

        elementData = c.toArray();

        size = elementData.length;

        // c.toArray 有可能不返回一个 Object 数组

        if (elementData.getClass() != Object[].class)

            // 使用Arrays.copyOf方法进行拷贝

            elementData = Arrays.copyOf(elementData, size, Object[].class);

    }


    // 压缩ArrayList内部数组的空余空间

    // 因为数组扩容每次扩大1.5倍，往往会出现容量大于实际元素数量的情况，该方法将数组容量压缩成元素数量，避免空间浪费，可在内存紧张时调用

    public void trimToSize() {

        // 每次对ArrayList进行add，set，remove等操作，都会涉及改变modCount

        modCount++;

        // 若容量大于实际元素数量

        if (size < elementData.length) {

            // 拷贝至新数组返回

            elementData = Arrays.copyOf(elementData, size);

        }

    }


    // 使用指定参数设定容量

    public void ensureCapacity(int minCapacity) {

        // 若数组为空，容量取0，否则取默认值10

        int minExpand = (elementData != EMPTY_ELEMENTDATA)

                // any size if real element table

                ? 0

                // larger than default for empty table. It's already supposed to be

                // at default size.

                : DEFAULT_CAPACITY;

        // 若参数大于默认最小容量

        if (minCapacity > minExpand) {

            // 将预设最小容量修改为参数对应容量

            ensureExplicitCapacity(minCapacity);

        }

    }



    // 扩容检查

    private void ensureCapacityInternal(int minCapacity) {

        // 若数组为空

        if (elementData == EMPTY_ELEMENTDATA) {

            // 使用默认值与参数中较大者作为容量预设值

            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

        }



        ensureExplicitCapacity(minCapacity);

    }



    private void ensureExplicitCapacity(int minCapacity) {

        modCount++;



        // 若容量不够

        if (minCapacity - elementData.length > 0)

            // 调用grow方法扩容

            grow(minCapacity);

    }



    // 真正的扩容方法

    private void grow(int minCapacity) {

        // 得到原始数组容量

        int oldCapacity = elementData.length;

        // 扩容1.5倍，右移一位为0.5

        int newCapacity = oldCapacity + (oldCapacity >> 1);

        // 新数组容量没达到1.5倍旧容量，则继续使用当前容量

        if (newCapacity - minCapacity < 0)

            newCapacity = minCapacity;

        // 只有当新数组容量大于MAX_ARRAY_SIZE时才会进入hugeCapacity方法

        // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 = 2147483639

        if (newCapacity - MAX_ARRAY_SIZE > 0)

            newCapacity = hugeCapacity(minCapacity);

        // minCapacity实际上很接近元素个数size，所以新数组容量为newCapacity会更好

        elementData = Arrays.copyOf(elementData, newCapacity);

    }



    // 数组容量大于MAX_ARRAY_SIZE时会进入该方法

    private static int hugeCapacity(int minCapacity) {

        // 判断溢出

        if (minCapacity < 0)

            throw new OutOfMemoryError();

        // 对minCapacity和MAX_ARRAY_SIZE进行比较

        // 将二者中较大者作为新数组的大小

        return (minCapacity > MAX_ARRAY_SIZE) ?

                Integer.MAX_VALUE :

                MAX_ARRAY_SIZE;

    }



    // 返回元素数量

    public int size() {

        return size;

    }



    // 判断是否为空

    public boolean isEmpty() {

        return size == 0;

    }



    // 是否包含特定元素，利用indexOf方法

    public boolean contains(Object o) {

        return indexOf(o) >= 0;

    }



    // 查找第一次出现指定元素的下标，若没找到，返回-1

    public int indexOf(Object o) {

        /**

         * 对于null值的处理方式是不同的

         * ==用来比较两个对象的地址是否相等，equals方法则是用来比较对象内容是否相同

         * 这样分开处理的原因，是因为如果直接对null调用equals方法，会抛出空指针异常

         * 同时也不能调用equals方法检查是否相等，因为ArrayList允许有null元素存在

         */

        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;

    }



    // 该方法倒序查找第一次出现指定元素的下标，若没找到，返回-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 {

            // 此时v.elementData实际指向仍是ArrayList的elementData

            ArrayList<?> v = (ArrayList<?>) super.clone();

            // 对elementData进行数组拷贝

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

        }

    }



    // 转换为Object[]数组

    public Object[] toArray() {

        return Arrays.copyOf(elementData, size);

    }



    // 将ArrayList中的所有元素赋值到数组中并返回该数组

    @SuppressWarnings("unchecked")

    public <T> T[] toArray(T[] a) {

        // 如果a的长度小于ArrayList长度

        if (a.length < size)

            // 调用Arrays.copyOf()，返回一个比a长度要大的新数组

            return (T[]) Arrays.copyOf(elementData, size, a.getClass());

        // 否则(a的长度大于ArrayList长度)

        // 调用System.arraycopy()，将elementData赋给a

        System.arraycopy(elementData, 0, a, 0, size);

        // 将大于默认size位置的元素设为null

        if (a.length > size)

            a[size] = null;

        return a;

    }



    // 直接返回index位的值

    @SuppressWarnings("unchecked")

    E elementData(int index) {

        return (E) elementData[index];

    }



    // 返回index位的值，会检查index是否合法

    public E get(int index) {

        // 检查越界

        rangeCheck(index);



        return elementData(index);

    }



    // 为index位的值赋新值，并返回之前的值，会检查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);  // Increments modCount!!

        // 将新元素赋值给size+1位

        elementData[size++] = e;

        return true;

    }



    // 在指定index位添加新元素

    public void add(int index, E element) {

        // 检查越界

        rangeCheckForAdd(index);

        // 确保容量，判断是否需要扩容

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        // public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

        // src:源数组 srcPos:源数组复制起始位置 dest:目标数组 destPos:目标数组起始位置 length:复制长度

        // 从index位整体右移一位，代价较高

        System.arraycopy(elementData, index, elementData, index + 1,

                size - index);

        // index位赋新值

        elementData[index] = element;

        size++;

    }



    // 删除指定位置的元素

    public E remove(int index) {

        // 检查越界

        rangeCheck(index);



        modCount++;

        // 获得index位的值

        E oldValue = elementData(index);



        int numMoved = size - index - 1;

        // 如果删除的不是最后一位

        if (numMoved > 0)

            // 从index位整体右移一位

            System.arraycopy(elementData, index + 1, elementData, index,

                    numMoved);

        // size-1 ，将elementData的size位值赋为null，以便GC回收内存空间

        elementData[--size] = null; // clear to let GC do its work



        return oldValue;

    }



    // 删除指定元素首次出现的位置，若不存在则不做删除

    public boolean remove(Object o) {

        // 若指定元素为null

        if (o == null) {

            for (int index = 0; index < size; index++)

                if (elementData[index] == null) {

                    // 调用fastRemove方法删除元素

                    fastRemove(index);

                    return true;

                }

        } else {

            for (int index = 0; index < size; index++)

                // 第一次找到该元素

                if (o.equals(elementData[index])) {

                    // 调用fastRemove方法删除元素

                    fastRemove(index);

                    return true;

                }

        }

        return false;

    }



    // 快速删除指定index位的元素

    // 该方法不对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

    }



    // 删除ArrayList内所有元素

    public void clear() {

        modCount++;



        // clear to let GC do its work

        for (int i = 0; i < size; i++)

            elementData[i] = null;

        // size设为0

        size = 0;

    }



    // 添加一个集合内的所有元素至ArrayList末端

    public boolean addAll(Collection<? extends E> c) {

        // 将c转换为数组a

        Object[] a = c.toArray();

        int numNew = a.length;

        // 扩容至size + numNew

        ensureCapacityInternal(size + numNew);  // Increments modCount

        // 复制至末端

        System.arraycopy(a, 0, elementData, size, numNew);

        size += numNew;

        // 若添加的集合为空，返回False，不为空，返回True

        return numNew != 0;

    }





    // 与上面的方法类似，不同在于集合元素会在指定的index位置添加

    public boolean addAll(int index, Collection<? extends E> c) {

        // 判断index位置是否合法，越界会抛出异常

        rangeCheckForAdd(index);



        Object[] a = c.toArray();

        int numNew = a.length;

        // 扩容

        ensureCapacityInternal(size + numNew);  // Increments modCount

        // 获得添加元素的数量

        int numMoved = size - index;

        // 添加方式为：先将指定位置后的元素后移，再复制目标集合的元素到指定位置后

        if (numMoved > 0)

            System.arraycopy(elementData, index, elementData, index + numNew,

                    numMoved);



        System.arraycopy(a, 0, elementData, index, numNew);

        size += numNew;

        // 若添加的集合为空，返回False，不为空，返回True

        return numNew != 0;

    }



    // 删除指定位置范围内的元素

    protected void removeRange(int fromIndex, int toIndex) {

        modCount++;

        // toIndex后的元素将被保留

        int numMoved = size - toIndex;

        // toIndex后的numMoved个元素将被复制到fromIndex位置后

        System.arraycopy(elementData, toIndex, elementData, fromIndex,

                numMoved);



        // clear to let GC do its work

        // 末尾的size - (toIndex - fromIndex)个元素将被赋为null

        int newSize = size - (toIndex - fromIndex);

        for (int i = newSize; i < size; i++) {

            elementData[i] = null;

        }

        size = newSize;

    }



    // 越界检查

    private void rangeCheck(int index) {

        // index大于容量

        if (index >= size)

            // 抛出IndexOutOfBoundsException异常

            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }



    // 在add与addAll方法中被使用的越界检查

    private void rangeCheckForAdd(int index) {

        //index小于0或大于容量

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

        // 调用batchRemove方法删除c中的元素，complement = false

        return batchRemove(c, false);

    }



    // 只保留指定集合内的元素，换言之不在该集合内的其他元素都将被删除

    public boolean retainAll(Collection<?> c) {

        Objects.requireNonNull(c);

        // 调用batchRemove方法保留c中的元素，complement = true

        return batchRemove(c, true);

    }



    // complement = true：数组中保留指定集合中元素的值

    // complement = false：数组中删除指定集合中元素的值

    private boolean batchRemove(Collection<?> c, boolean complement) {

        final Object[] elementData = this.elementData;

        int r = 0, w = 0;

        boolean modified = false;

        try {

            //遍历ArrayList

            for (; r < size; r++)

                // 判断指定集合中是否有这个元素，并根据complement的值决定是否删除或覆盖

                // 若complement = true即保留，则将相同元素移动到数组前端

                // 若complement = false即删除，则将不同元素移动到数组前端

                if (c.contains(elementData[r]) == complement)

                    elementData[w++] = elementData[r];

        } finally {

            // 如果c.contains()抛出了异常

            if (r != size) {

                // 把r后面的元素复制到w后面

                System.arraycopy(elementData, r,

                        elementData, w,

                        size - r);

                w += size - r;

            }

            // w后面的元素都赋为null

            if (w != size) {

                // clear to let GC do its work

                for (int i = w; i < size; i++)

                    elementData[i] = null;

                modCount += size - w;

                // size = 保留元素个数

                size = w;

                modified = true;

            }

        }

        return modified;

    }



    // 保存ArrayList实例到一个流，即序列化，写入过程中若ArrayList被更改会抛出异常

    private void writeObject(java.io.ObjectOutputStream s)

            throws java.io.IOException {

        // Write out element count, and any hidden stuff

        //写入modCount的值，将依据此检查写入过程ArrayList是否被更改

        int expectedModCount = modCount;

        // 执行默认的序列化

        s.defaultWriteObject();



        // 写入容量大小

        s.writeInt(size);



        // 按顺序写入所有元素

        for (int i = 0; i < size; i++) {

            s.writeObject(elementData[i]);

        }



        // 如果modCount的值被更改，抛出异常

        if (modCount != expectedModCount) {

            throw new ConcurrentModificationException();

        }

    }



    // 从流中读取ArrayList实例，即反序列化

    private void readObject(java.io.ObjectInputStream s)

            throws java.io.IOException, ClassNotFoundException {

        elementData = EMPTY_ELEMENTDATA;



        // 执行默认的反序列化

        s.defaultReadObject();



        // 读取容量大小

        s.readInt(); // ignored



        if (size > 0) {

            // 类似clone()方法, 但是根据的是size分配ArrayList

            ensureCapacityInternal(size);



            Object[] a = elementData;

            // 按顺序读取所有元素

            for (int i = 0; i < size; i++) {

                a[i] = s.readObject();

            }

        }

    }



    // 返回一个从index开始的ListIterator对象

    public ListIterator<E> listIterator(int index) {

        // index不小于0或大于容量

        if (index < 0 || index > size)

            throw new IndexOutOfBoundsException("Index: " + index);

        return new ListItr(index);

    }



    // 返回ListIterator对象，默认index为0

    public ListIterator<E> listIterator() {

        return new ListItr(0);

    }



    // 返回Iterator对象

    public Iterator<E> iterator() {

        return new Itr();

    }



    // 迭代器实现，是AbstractList.Itr的优化版本

    // Itr为ArrayList的一个内部类，实现了Iterator<E>接口

    private class Itr implements Iterator<E> {

        int cursor;       // 游标，下一个返回元素的位置

        int lastRet = -1; // 上个返回元素的位置，默认为-1

        int expectedModCount = modCount; // 若过程中数组被改变，将抛出异常



        //是否还有下一个元素

        public boolean hasNext() {

            return cursor != size;

        }



        // 返回下一个元素

        @SuppressWarnings("unchecked")

        public E next() {

            // 检查数组是否被更改

            // if (modCount != expectedModCount)，则抛出异常

            checkForComodification();

            int i = cursor;

            // i大于容量，抛出NoSuchElementException异常

            if (i >= size)

                throw new NoSuchElementException();

            Object[] elementData = ArrayList.this.elementData;

            // i大于实际元素数量，也抛出异常

            if (i >= elementData.length)

                throw new ConcurrentModificationException();

            // 游标后移1位

            cursor = i + 1;

            // 返回index为i的元素值并将lastRe设为i

            return (E) elementData[lastRet = i];

        }



        // 删除元素

        public void remove() {

            // lastRet默认值为-1，所以调用next()后才能调用remove()

            // 而且因为下面会将lastRet再次赋为-1，所以next()后只能调用一次remove()

            if (lastRet < 0)

                throw new IllegalStateException();

            // 检查数组是否被更改

            checkForComodification();



            try {

                // 删除下标为lastRet的元素

                ArrayList.this.remove(lastRet);

                cursor = lastRet;

                // lastRet重新赋为默认-1值

                lastRet = -1;

                //expectedModCount值更新，因为前面的ArrayList.this.remove(lastRet)改变了modCount的值

                expectedModCount = modCount;

            } catch (IndexOutOfBoundsException ex) {

                throw new ConcurrentModificationException();

            }

        }



        // 为每个剩余元素执行consumer中的方法

        @Override

        @SuppressWarnings("unchecked")

        public void forEachRemaining(Consumer<? super E> consumer) {

            // 判断是否为空

            Objects.requireNonNull(consumer);

            // size记录元素数量

            final int size = ArrayList.this.size;

            // 游标赋值给i

            int i = cursor;

            // 越界

            if (i >= size) {

                return;

            }

            final Object[] elementData = ArrayList.this.elementData;

            // 越界

            if (i >= elementData.length) {

                throw new ConcurrentModificationException();

            }

            while (i != size && modCount == expectedModCount) {

                // 此处接受elementData元素，执行consumer中的方法，可能会改变elementData

                consumer.accept((E) elementData[i++]);

            }

            // update once at end of iteration to reduce heap write traffic

            cursor = i;

            lastRet = i - 1;

            checkForComodification();

        }



        // 检查数组是否被修改

        final void checkForComodification() {

            // 通过modCount与expectedModCount进行判断

            if (modCount != expectedModCount)

                throw new ConcurrentModificationException();

        }

    }



    // ListIterator迭代器实现，是AbstractList.ListItr的优化版本，可以双向移动

    private class ListItr extends Itr implements ListIterator<E> {

        ListItr(int index) {

            super();

            cursor = index;

        }

        // 是否有前面一个

        public boolean hasPrevious() {

            return cursor != 0;

        }

        // 返回下个索引

        public int nextIndex() {

            return cursor;

        }

        // 返回上个索引

        public int previousIndex() {

            return cursor - 1;

        }

        // 返回上一个元素

        @SuppressWarnings("unchecked")

        public E previous() {

            checkForComodification();

            // i = cursor - 1，最终会返回index = i的元素，即上一个元素

            int i = cursor - 1;

            if (i < 0)

                throw new NoSuchElementException();

            Object[] elementData = ArrayList.this.elementData;

            if (i >= elementData.length)

                throw new ConcurrentModificationException();

            cursor = i;

            return (E) elementData[lastRet = i];

        }



        // 更改当前元素的值

        public void set(E e) {

            if (lastRet < 0)

                throw new IllegalStateException();

            checkForComodification();



            try {

                ArrayList.this.set(lastRet, e);

            } catch (IndexOutOfBoundsException ex) {

                throw new ConcurrentModificationException();

            }

        }

        // 添加新元素至当前位置

        public void add(E e) {

            checkForComodification();



            try {

                int i = cursor;

                ArrayList.this.add(i, e);

                // 游标右移一位

                cursor = i + 1;

                lastRet = -1;

                expectedModCount = modCount;

            } catch (IndexOutOfBoundsException ex) {

                throw new ConcurrentModificationException();

            }

        }

    }



    // 返回指定范围的子list

    public List<E> subList(int fromIndex, int toIndex) {

        // 检查参数合法

        subListRangeCheck(fromIndex, toIndex, size);

        return new SubList(this, 0, fromIndex, toIndex);

    }



    // 检查子数组范围是否合法

    static void subListRangeCheck(int fromIndex, int toIndex, int size) {

        if (fromIndex < 0)

            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);

        if (toIndex > size)

            throw new IndexOutOfBoundsException("toIndex = " + toIndex);

        if (fromIndex > toIndex)

            throw new IllegalArgumentException("fromIndex(" + fromIndex +

                    ") > toIndex(" + toIndex + ")");

    }



    // 子list的实现，继承AbstractList类，实现RandomAccess接口，方法实现与上面类似

    private class SubList extends AbstractList<E> implements RandomAccess {

        // 父list

        private final AbstractList<E> parent;

        // 父list的起始位置

        private final int parentOffset;

        // 子list的起始位置

        private final int offset;

        // 子list容量

        int size;





        /**

         * 构造函数

         * 看到这里就能理解为什么对SubList实例的操作会影响到父list:

         * 因为子list的处理仅仅是给出了一个映射到父list相应区间的引用

         * 由于父list一直被子list引用着，只要子list存在，父list就不会被释放

         */

        SubList(AbstractList<E> parent,

                int offset, int fromIndex, int toIndex) {

            this.parent = parent;

            this.parentOffset = fromIndex;

            this.offset = offset + fromIndex;

            this.size = toIndex - fromIndex;

            this.modCount = ArrayList.this.modCount;

        }



        public E set(int index, E e) {

            rangeCheck(index);

            checkForComodification();

            E oldValue = ArrayList.this.elementData(offset + index);

            ArrayList.this.elementData[offset + index] = e;

            return oldValue;

        }



        public E get(int index) {

            rangeCheck(index);

            checkForComodification();

            return ArrayList.this.elementData(offset + index);

        }



        public int size() {

            checkForComodification();

            return this.size;

        }



        // 对子列表的添加元素的操作实际上是对父列表进行添加元素的操作

        public void add(int index, E e) {

            rangeCheckForAdd(index);

            checkForComodification();

            parent.add(parentOffset + index, e);

            this.modCount = parent.modCount;

            this.size++;

        }



        // 删除也同上

        public E remove(int index) {

            rangeCheck(index);

            checkForComodification();

            E result = parent.remove(parentOffset + index);

            this.modCount = parent.modCount;

            this.size--;

            return result;

        }



        protected void removeRange(int fromIndex, int toIndex) {

            checkForComodification();

            parent.removeRange(parentOffset + fromIndex,

                    parentOffset + toIndex);

            this.modCount = parent.modCount;

            this.size -= toIndex - fromIndex;

        }



        public boolean addAll(Collection<? extends E> c) {

            return addAll(this.size, c);

        }



        public boolean addAll(int index, Collection<? extends E> c) {

            rangeCheckForAdd(index);

            int cSize = c.size();

            if (cSize == 0)

                return false;



            checkForComodification();

            parent.addAll(parentOffset + index, c);

            this.modCount = parent.modCount;

            this.size += cSize;

            return true;

        }



        public Iterator<E> iterator() {

            return listIterator();

        }



        public ListIterator<E> listIterator(final int index) {

            checkForComodification();

            rangeCheckForAdd(index);

            final int offset = this.offset;



            return new ListIterator<E>() {

                int cursor = index;

                int lastRet = -1;

                int expectedModCount = ArrayList.this.modCount;



                public boolean hasNext() {

                    return cursor != SubList.this.size;

                }



                @SuppressWarnings("unchecked")

                public E next() {

                    checkForComodification();

                    int i = cursor;

                    if (i >= SubList.this.size)

                        throw new NoSuchElementException();

                    Object[] elementData = ArrayList.this.elementData;

                    if (offset + i >= elementData.length)

                        throw new ConcurrentModificationException();

                    cursor = i + 1;

                    return (E) elementData[offset + (lastRet = i)];

                }



                public boolean hasPrevious() {

                    return cursor != 0;

                }



                @SuppressWarnings("unchecked")

                public E previous() {

                    checkForComodification();

                    int i = cursor - 1;

                    if (i < 0)

                        throw new NoSuchElementException();

                    Object[] elementData = ArrayList.this.elementData;

                    if (offset + i >= elementData.length)

                        throw new ConcurrentModificationException();

                    cursor = i;

                    return (E) elementData[offset + (lastRet = i)];

                }



                @SuppressWarnings("unchecked")

                public void forEachRemaining(Consumer<? super E> consumer) {

                    Objects.requireNonNull(consumer);

                    final int size = SubList.this.size;

                    int i = cursor;

                    if (i >= size) {

                        return;

                    }

                    final Object[] elementData = ArrayList.this.elementData;

                    if (offset + i >= elementData.length) {

                        throw new ConcurrentModificationException();

                    }

                    while (i != size && modCount == expectedModCount) {

                        consumer.accept((E) elementData[offset + (i++)]);

                    }

                    // update once at end of iteration to reduce heap write traffic

                    lastRet = cursor = i;

                    checkForComodification();

                }



                public int nextIndex() {

                    return cursor;

                }



                public int previousIndex() {

                    return cursor - 1;

                }



                public void remove() {

                    if (lastRet < 0)

                        throw new IllegalStateException();

                    checkForComodification();



                    try {

                        SubList.this.remove(lastRet);

                        cursor = lastRet;

                        lastRet = -1;

                        expectedModCount = ArrayList.this.modCount;

                    } catch (IndexOutOfBoundsException ex) {

                        throw new ConcurrentModificationException();

                    }

                }



                public void set(E e) {

                    if (lastRet < 0)

                        throw new IllegalStateException();

                    checkForComodification();



                    try {

                        ArrayList.this.set(offset + lastRet, e);

                    } catch (IndexOutOfBoundsException ex) {

                        throw new ConcurrentModificationException();

                    }

                }



                public void add(E e) {

                    checkForComodification();



                    try {

                        int i = cursor;

                        SubList.this.add(i, e);

                        cursor = i + 1;

                        lastRet = -1;

                        expectedModCount = ArrayList.this.modCount;

                    } catch (IndexOutOfBoundsException ex) {

                        throw new ConcurrentModificationException();

                    }

                }



                final void checkForComodification() {

                    if (expectedModCount != ArrayList.this.modCount)

                        throw new ConcurrentModificationException();

                }

            };

        }



        public List<E> subList(int fromIndex, int toIndex) {

            subListRangeCheck(fromIndex, toIndex, size);

            return new SubList(this, offset, fromIndex, toIndex);

        }



        private void rangeCheck(int index) {

            if (index < 0 || index >= this.size)

                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        }



        private void rangeCheckForAdd(int index) {

            if (index < 0 || index > this.size)

                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        }



        private String outOfBoundsMsg(int index) {

            return "Index: " + index + ", Size: " + this.size;

        }



        private void checkForComodification() {

            if (ArrayList.this.modCount != this.modCount)

                throw new ConcurrentModificationException();

        }



        public Spliterator<E> spliterator() {

            checkForComodification();

            return new ArrayListSpliterator<E>(ArrayList.this, offset,

                    offset + this.size, this.modCount);

        }

    }



    // Java8新增的forEach方法，会执行Consumer中定义的方法

    @Override

    public void forEach(Consumer<? super E> action) {

        // 检查action不为空

        Objects.requireNonNull(action);

        final int expectedModCount = modCount;

        @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData;

        final int size = this.size;

        for (int i = 0; modCount == expectedModCount && i < size; i++) {

            action.accept(elementData[i]);

        }

        // 执行forEach过程中不允许修改数组，否则会抛出ConcurrentModificationException异常

        if (modCount != expectedModCount) {

            throw new ConcurrentModificationException();

        }

    }



    // 返回Java8中新添加的Spliterator，用于多线程

    @Override

    public Spliterator<E> spliterator() {

        return new ArrayListSpliterator<>(this, 0, -1, 0);

    }



    // Spliterator的实现

    static final class ArrayListSpliterator<E> implements Spliterator<E> {



        private final ArrayList<E> list;

        private int index; // current index, modified on advance/split

        private int fence; // -1 until used; then one past last index

        private int expectedModCount; // initialized when fence set



        /**

         * Create new spliterator covering the given  range

         */

        ArrayListSpliterator(ArrayList<E> list, int origin, int fence,

                             int expectedModCount) {

            this.list = list; // OK if null unless traversed

            this.index = origin;

            this.fence = fence;

            this.expectedModCount = expectedModCount;

        }



        // 第一次使用时，初始化fence大小

        private int getFence() { // initialize fence to size on first use

            int hi; // (a specialized variant appears in method forEach)

            ArrayList<E> lst;

            if ((hi = fence) < 0) {

                if ((lst = list) == null)

                    hi = fence = 0;

                else {

                    expectedModCount = lst.modCount;

                    hi = fence = lst.size;

                }

            }

            return hi;

        }



        public ArrayListSpliterator<E> trySplit() {

            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; // >>> 1 相当于 /2

            return (lo >= mid) ? null : // divide range in half unless too small

                    new ArrayListSpliterator<E>(list, lo, index = mid,

                            expectedModCount);

        }



        public boolean tryAdvance(Consumer<? super E> action) {

            if (action == null)

                throw new NullPointerException();

            int hi = getFence(), i = index;

            if (i < hi) {

                index = i + 1;

                @SuppressWarnings("unchecked") E e = (E) list.elementData[i];

                action.accept(e);

                if (list.modCount != expectedModCount)

                    throw new ConcurrentModificationException();

                return true;

            }

            return false;

        }



        public void forEachRemaining(Consumer<? super E> action) {

            int i, hi, mc; // hoist accesses and checks from loop

            ArrayList<E> lst;

            Object[] a;

            if (action == null)

                throw new NullPointerException();

            if ((lst = list) != null && (a = lst.elementData) != null) {

                if ((hi = fence) < 0) {

                    mc = lst.modCount;

                    hi = lst.size;

                } else

                    mc = expectedModCount;

                if ((i = index) >= 0 && (index = hi) <= a.length) {

                    for (; i < hi; ++i) {

                        @SuppressWarnings("unchecked") E e = (E) a[i];

                        action.accept(e);

                    }

                    if (lst.modCount == mc)

                        return;

                }

            }

            throw new ConcurrentModificationException();

        }



        public long estimateSize() {

            return (long) (getFence() - index);

        }



        public int characteristics() {

            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;

        }

    }



    @Override

    public boolean removeIf(Predicate<? super E> filter) {

        Objects.requireNonNull(filter);

        // figure out which elements are to be removed

        // any exception thrown from the filter predicate at this stage

        // will leave the collection unmodified

        int removeCount = 0;

        final BitSet removeSet = new BitSet(size);

        final int expectedModCount = modCount;

        final int size = this.size;

        for (int i = 0; modCount == expectedModCount && i < size; i++) {

            @SuppressWarnings("unchecked") final E element = (E) elementData[i];

            if (filter.test(element)) {

                removeSet.set(i);

                removeCount++;

            }

        }

        if (modCount != expectedModCount) {

            throw new ConcurrentModificationException();

        }



        // shift surviving elements left over the spaces left by removed elements

        final boolean anyToRemove = removeCount > 0;

        if (anyToRemove) {

            final int newSize = size - removeCount;

            for (int i = 0, j = 0; (i < size) && (j < newSize); i++, j++) {

                i = removeSet.nextClearBit(i);

                elementData[j] = elementData[i];

            }

            for (int k = newSize; k < size; k++) {

                elementData[k] = null;  // Let gc do its work

            }

            this.size = newSize;

            if (modCount != expectedModCount) {

                throw new ConcurrentModificationException();

            }

            modCount++;

        }



        return anyToRemove;

    }



	// 根据operator进行替换，Java8新增方法

    @Override

    @SuppressWarnings("unchecked")

    public void replaceAll(UnaryOperator<E> operator) {

        Objects.requireNonNull(operator);

        final int expectedModCount = modCount;

        final int size = this.size;

        for (int i = 0; modCount == expectedModCount && i < size; i++) {

            elementData[i] = operator.apply((E) elementData[i]);

        }

        if (modCount != expectedModCount) {

            throw new ConcurrentModificationException();

        }

        modCount++;

    }

	

	// 根据Comparator排序，Java8新增方法

    @Override

    @SuppressWarnings("unchecked")

    public void sort(Comparator<? super E> c) {

        final int expectedModCount = modCount;

        Arrays.sort((E[]) elementData, 0, size, c);

        if (modCount != expectedModCount) {

            throw new ConcurrentModificationException();

        }

        modCount++;

    }

}