jdk8源码系列-集合

事前准备

1. 环境搭建

搭建JDK8环境可参考另一篇博客IDEA搭建JDK源码 (opens new window)

2. 本人学习的源码

https://gitee.com/bean-chan/jdk8

集合目录

1. ArrayList(Current)
2. [LinkedList--待完善](javascript:;https://chenb.in/集合-LinkedList)
3. [HashMap--待完善](javascript:;https://chenb.in/集合-HashMap)
4. [ConcurrentHashMap--待完善](javascript:;https://chenb.in/集合-ConcurrentHashMap)

撸起袖子加油干

类对象

共有六个类对象:

/**
 * Java序列化机制根据Class自动生成的ID,用作序列化版本比较
 */
private static final long serialVersionUID = 8683452581122892189L;

/**
 * 容器默认初始化大小
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 当把0作为参数构造ArrayList时,容积会使用EMPTY_ELEMENTDATA
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
  * 当使用空参构造时,会以此来初始化ArrayList
  * 用他来区分上面那个EMPTY_ELEMENTDATA,以便知道在第一次添加元素时是进行扩容操作,还是直接修改容积到DEFAULT_CAPACITY(10)
  * EMPTY_ELEMENTDATA(扩容)
  * DEFAULTCAPACITY_EMPTY_ELEMENTDATA(直接修改容积到DEFAULT_CAPACITY)
  */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 使用Object数组存放元素
 * 数组的大小就是容器的容积
 * 任何使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA初始化的数组,在第一次添加元素的时候,会把容积扩充到DEFAULT_CAPACITY(10)
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * 集合已存储元素的数量
 *
 * @serial
 */
private int size;

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

构造器

/**
 * 使用指定的容积来初始化ArrayList
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // 可见EMPTY_ELEMENTDATA的描述
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * 使用无参构造器构造list时,会创建一个初始容积为空数组,首次添加元素后容积会增长到十
 * 具体可参考上面DEFAULTCAPACITY_EMPTY_ELEMENTDATA的描述,后续不再赘述
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 构造器参数可以传入一个Collection的子类,如ArrayList,LinkedList等
 */
public ArrayList(Collection<? extends E> c) {
    // 想把传入对象转换成数组并传给自带的Object数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 官方bug,c.toArray可能不会转换成Object数组,因此做下判断
        if (elementData.getClass() != Object[].class)
            // 将元素拷贝到Object数组中,初始容积为传入数组元素的数量
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 设置初始化数组为EMPTY_ELEMENTDATA,具体可参考上面EMPTY_ELEMENTDATA的描述,后续不再赘述
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

实现原理

元素操作

/**
 * 返回数组中指定索引位置的元素
 */
@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;
}

/**
 * 在数组尾部添加元素,成功返回true
 */
public boolean add(E e) {

    // 确认容器是否能容纳下新元素,并且结构化次数加一
    ensureCapacityInternal(size + 1);
    // 插入元素,并让size自增
    elementData[size++] = e;
    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);
    // 指定位置插入元素
    elementData[index] = element;
    // 元素计数器加一
    size++;
}

/**
 * 删除指定位置元素,并且后续元素往前移动一位,返回删除元素
 */
public E remove(int index) {
    //  确认是否越界
    rangeCheck(index);

    // 修改结构次数加一
    modCount++;
    // 获取指定位置元素
    E oldValue = elementData(index);

    // 需要移动的元素数量
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 元素右移
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 结尾元素设置为null,让垃圾收集器收集
    elementData[--size] = null;
    // 返回旧值
    return oldValue;
}

/**
 * 移除指定元素,根据equal进行判断
 */
public boolean remove(Object o) {
    // 如果是null.则返回移除第一个为null的元素
    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);
    // 结尾元素设置为null,让GC清理
    elementData[--size] = null;
}

/**
 * 清空数组
 */
public void clear() {
    // 结构改变次数加一
    modCount++;

    // 全部设置为null,让GC清理
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

/**
 * 将某个集合的元素全部添加到本集合内,但不能添加空集合与本集合,添加成功后返回true
 */
public boolean addAll(Collection<? extends E> c) {
    // 转数组
    Object[] a = c.toArray();
    // 添加数量
    int numNew = a.length;
    // 判断是否能容纳这么多元素并修改modCount
    ensureCapacityInternal(size + numNew);
    // 元素拷贝到当前数组
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    // 无法添加空集合
    return numNew != 0;
}

/**
 * 在指定位置插入一个集合的所有元素
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 确定指定位置是否在边界内
    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
    size += numNew;
    return numNew != 0;
}

/**
 * 删除指定区间的元素
 */
protected void removeRange(int fromIndex, int toIndex) {
    // 修改次数加一
    modCount++;
    // 需要移动的数量
    int numMoved = size - toIndex;
    // 将需要后面元素前移
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // 将尾部没覆盖的元素设为null,让GC清理
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    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) {
    // 传入集合不可为null
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 * 只保留指定集合中有的元素,其余删除
 */
public boolean retainAll(Collection<?> c) {
    // 传入集合不可为null
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

/**
 * 批量移除
 * @param c 传入集合
 * @param complement 标志参数, 说明是retainAll方法内调用当前方法
 * @return 是否移除成功
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    // 数组是否有元素删除,起始默认为没有
    boolean modified = false;
    try {
        // 让r自增到size
        for (; r < size; r++)
            // retainAll方法才执行以下步骤
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // c.contains()可能抛出异常,有可能导致r!=size
        if (r != size) {
            // 将没抛异常前的元素都拷贝到最前面
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            // 拷贝后有效元素的数量
            w += size - r;
        }
        // 说明原先数组元素有减少
        if (w != size) {
            // 将有效元素以外的其他元素设为null,让GC处理
            for (int i = w; i < size; i++)
                elementData[i] = null;
            // 维护modCount
            modCount += size - w;
            // 维护size
            size = w;
            // 数组发生改变
            modified = true;
        }
    }
    return modified;
}

扩容

扩容往往发生在添加元素时,就拿最简单的add方法举例

public boolean add(E e) {
    // 确认容器是否能容纳下新元素,并且结构化次数加一
    ensureCapacityInternal(size + 1);
    // 插入元素,并让size自增
    elementData[size++] = e;
    return true;
}

-----------------------------------------------------------
// 以下为准备步骤

/**
  * 判断是否可以容纳传入容积
  * @param minCapacity 所需容量
  */
private void ensureCapacityInternal(int minCapacity) {
    // 先计算minCapacity是否需要修改,再进行精确判断是否需要扩容
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
  * 计算传入容器的容积
  * @param elementData 需要判断的容器
  * @param minCapacity 最小容积
  * @return
  */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果是空参构造的ArrayList,则返回10或者传入的最小容积两者中的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    return minCapacity;
}

/**
  * 再次判断是否需要扩容
  */
private void ensureExplicitCapacity(int minCapacity) {
/**
  * AbstractList抽象类所带的类变量,作用有二:
  * 1.子类使用该变量则有了fast-fail机制
  * 2.统计结构修改次数
  * 一旦发现这个对象的modCount和迭代器存储的modCount不一样，就会报错
  */
    modCount++;
    // minCapacity大于Object数组的当前容积,则需要扩容
    if (minCapacity - elementData.length > 0)
        // 开始扩容
        grow(minCapacity);
}
-----------------------------------------------------------
// 开始正式扩容
    
/**
  * 扩容到数组至少可以存下传入的minCapacity那么多元素
  *
  * @param minCapacity 想要的最小容积
  */
private void grow(int minCapacity) {
    // 旧容积
    int oldCapacity = elementData.length;
    // 计算原数组容积1.5倍的容积是多大(左移一位视为➗2)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新容积为
    // 1.5×oldCapacity与minCapacity中的较大值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    // 如果新容积过大,则需要修改新容积
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 给elementData赋予新容积,并拷贝
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/** 
  * 如果新容积>数组规定最大长度,新容积为Integer的最大取值
  */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 是否溢出
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

总结:

1. 每次add操作时,都会将当前size+1作为参数来检测Object数组是否有足够容量来添加新元素
2. 如果是通过空参构造器创建的ArrayList,首次添加元素则会将容积扩充到10
3. 如果已经确定容器无法容纳那么多元素,则会进行扩容,扩容大小为(当前数组长度的1.5倍)与(size+1)中的最大值
4. 最大也就只能扩容到Integer的最大取值范围

截取ArrayList

/**
 * 截取当前ArrayList部分元素作为子类,并将当前ArrayList作为父类
 * 但子类元素的改变(add、remove、set等方法)会影响到父类的元素
 */
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 + ")");
}

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    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();
        // 返回subList的元素数量
        return this.size;
    }

    public void add(int index, E e) {
        // 检测边界
        rangeCheckForAdd(index);
        // 是否ff
        checkForComodification();
        // 原集合末尾添加一个元素
        parent.add(parentOffset + index, e);
        //维护modCount和size
        this.modCount = parent.modCount;
        this.size++;
    }

    public E remove(int index) {
        // 检测边界
        rangeCheck(index);
        // 是否ff
        checkForComodification();
        // 调用父类remove方法移除元素
        E result = parent.remove(parentOffset + index);
        // 维护modCount和size
        this.modCount = parent.modCount;
        this.size--;
        // 返回移除元素
        return result;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        // 是否ff
        checkForComodification();
        // 调用父类removeRange方法移除范围内元素
        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;

        // 是否ff
        checkForComodification();
        // 调用父类方法,添加所有元素
        parent.addAll(parentOffset + index, c);
        // 维护变量
        this.modCount = parent.modCount;
        this.size += cSize;
        // 添加完毕返回true
        return true;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    // 自己创建个迭代器并返回,具体与ArrayList创建的listIterator并无差异,只是subList的迭代器需要调用父类对象的变量
    public ListIterator<E> listIterator(final int index) {
        // 是否ff
        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();
            }
        };
    }

    // subList还可以在切割成subList
    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;
    }

    // ff实现方式
    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);
    }
}

@Override
public void forEach(Consumer<? super E> action) {
    // consumer不可为null
    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]);
    }
    // 判断迭代是否出现异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

常用方法

/**
 * 返回数组元素数量
 */
public int size() {
    return size;
}

/**
 * 根据size是否为零判断是否为空
 */
public boolean isEmpty() {
    return size == 0;
}

/**
 * 判断数组是否至少有一个指定元素,基于equal方法比较
 */
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
 * 查看数组是否存在传入对象,有则返回第一个找到元素的索引,无则返回-1
 */
public int indexOf(Object o) {
    // 如果传入对线为零
    if (o == null) {
        for (int i = 0; i < size; i++)
            // 找到第一个问null的对象
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            // 找到第一个equal()为true的对象并返回索引
            if (o.equals(elementData[i]))
                return i;
    }
    // 没找到返回-1
    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;
}
 // 返回一个安全的数组,他会新建一个Object数组,并将elementData的元素按顺序复制进去,因此方法使用者个可以随意修改返回回去的数组.而不会导致ArrayList被篡改
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

/**
  * 按指定规则排序
  */

@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;

    // 按c的规则从头到尾排序
    Arrays.sort((E[]) elementData, 0, size, c);

    // 结构化改变次数不一致
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    // 维护modCount
    modCount++;
}

迭代器

// 第一种迭代器

/**
 * 返回一个有序列表的迭代器,不可往前迭代
 */
public Iterator<E> iterator() {
    return new Itr();
}
/**
 * AbstractList下迭代器的一个优化版本
 */
private class Itr implements Iterator<E> {
    int cursor;       // 下一个返回的元素的索引
    int lastRet = -1; // 当前显示的元素的索引,如果没有或者进行了移除、添加操作则设置为-1
    /**
     * modCount和expectedModCount都是表示修改次数的
     * 设置expectedModCount的目的就是要保证在使用迭代器期间,只有迭代器可以对ArrayList进行修改
     * 如果在迭代器中使用remove来移除元素,会导致modCount与expectedModCount不一致
     */
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        // 判断是否需要快速失败,具体看checkForComodification方法注解
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            // 有其余线程影响当前数组大小了,快速失败
            throw new ConcurrentModificationException();
        // 维护cursor
        cursor = i + 1;
        // 返回元素,并且维护lastRet
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        // 是否需要快速失败
        checkForComodification();
        try {
            // 移除元素
            ArrayList.this.remove(lastRet);
            // 移除后,右边元素全部左移一位,所以lastRet位置当前所在的元素其实是下一个元素
            cursor = lastRet;
            // 移除后,维护lastRet
            lastRet = -1;
            // 让expectedModCount = modCount,说明是正常移除操作
            expectedModCount = modCount;
            // 有其余线程影响当前数组大小了,快速失败
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        // 不可为null
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        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) {
            // 每个元素都执行consumer
            consumer.accept((E) elementData[i++]);
        }
        // 维护cursor和lastRet
        cursor = i;
        lastRet = i - 1;
        // 判断是否需要快速失败
        checkForComodification();
    }

    /**
     * 实现快速失败机制的方法
     * 比如,有A和B两个线程,A修改集合list,B遍历集合list,此时 modCount = expectedModCount = N
     * A修改后,modCount变成N+1,expectedModCount变成N+1
     * B在调用next,发现modCount是N,expectedModCount变成N+1
     * 则抛出异常ConcurrentModificationException
     */
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
-----------------------------------------------------------
// 第二种迭代器,可以往前迭代

/**
 * 从指定位置创建并返回一个集合迭代器,可以往前迭代
 * 支持fail-fast
 */
public ListIterator<E> listIterator(int index) {
    // 越界检测
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    // 返回集合迭代器
    return new ListItr(index);
}

/**
 * 返回一个集合迭代器包含所有元素,可以往前迭代
 * 支持fail-fast
 */
public ListIterator<E> listIterator() {
    return new ListItr(0);
}

/**
 * 优化版本的迭代器类,可以往前迭代
 */
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();
        // 取到前一个元素索引
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 维护cursor
        cursor = i;
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        // 未迭代一次无法进行set操作
        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 {
            // i为下一个元素位置
            int i = cursor;

            // 在下一个位置插入元素
            ArrayList.this.add(i, e);
            // 维护cursor,和lastRet
            cursor = i + 1;
            lastRet = -1;
            // expectedModCount = modCount说明迭代器进行正常
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

-----------------------------------------------------------
// 第三种迭代器,可分割迭代器,为并行而设计 有兴趣可自行研究
ArrayListSpliterator
static final class ArrayListSpliterator<E> implements Spliterator<E>{...}

详细源码可查看Gitee源码