JDK8并行迭代器Spliterator

Spliterator 和Iterator一样，用于遍历源的元素。
Spliterator是一个可分割迭代器splitable iterator，iterator是顺序遍历迭代器。
Spliterator API 旨在通过支持分解和单元素迭代来支持除顺序遍历之外的高效并行遍历。 此外，通过 Spliterator 访问元素的协议旨在施加比Iterator更小的每个元素开销，并避免为hasNext()和next()使用单独的方法所涉及的固有竞争。

Iterator接口

public interface Iterator<E> {

    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

1.hasNext

单向移动,如果next将返回一个元素而不是抛出异常，则返回true 。使用hasNext()检查序列中是否还有元素

boolean hasNext();

ArrayList
注：ArrayList中用size记录实际数据的数量

public boolean hasNext() {
      //判断指针是否到达了数组最后一个元素+1的位置，来判断是否还有元素
      return cursor != size;
}

Vector
注：Vector中用elementCount记录实际数据的数量

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

2.next

第一次返回序列的第一个元素。返回值是Object，需要强制转换成自己需要的类型

E next();

ArrayList

        public E next() {
            //同时修改检查函数
            this.checkForComodification();
            //定义临时的当前元素的指针i并赋值
            int i = this.cursor;
            if (i >= ArrayList.this.size) {
                //如果当前指针超出了范围则抛出没有足够元素异常，同理于hasNext()判断
                throw new NoSuchElementException();
            } else {
                /**
                 * 因为该私有类是在ArrayList<E>内部，所以可以直接调用ArrayList类中的属性
                 * 该方法要返回元素数组的其中一个内容，在这里获取元素数组
                 */
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length) {
                    //通过直接检查数组的长度，进一步确认数组是否被修改
                    throw new ConcurrentModificationException();
                } else {
                    //下一个元素指针+1
                    this.cursor = i + 1;
                    /**
                    * 因为下一个元素指针+1后，i就变成上一个元素了，所以先给上一个元素（lastRet）
                    * 赋值为i，然后返回第i个元素的值，即当前元素的值
                    */
                    return elementData[this.lastRet = i];
                }
            }
        }

Vector

        public E next() {
            synchronized(Vector.this) {
                this.checkForComodification();
                int i = this.cursor;
                if (i >= Vector.this.elementCount) {
                    throw new NoSuchElementException();
                } else {
                    this.cursor = i + 1;
                    return Vector.this.elementData(this.lastRet = i);
                }
            }
        }

3.remove

将迭代器新返回的元素删除。

default void remove() {
        throw new UnsupportedOperationException("remove");
    }

ArrayList

        public void remove() {
            //迭代器是根据上一个元素来删除的，先判断有没有上一个元素
            if (this.lastRet < 0) {
                throw new IllegalStateException();
            } else {
                //同时修改检查函数
                this.checkForComodification();
                try {
                    //调用外部类中的删除方法
                    ArrayList.this.remove(this.lastRet);
                    /**
                     * 删除成功后删除元素后面的元素会整体前移一个位置所以下一个指针需要-1
                     * 这里直接把删除元素的指针赋值给了下一个元素效果相当于-1了
                     */
                    this.cursor = this.lastRet;
                    /**
                     * 由于没删除一个元素，上一个元素指针都会回归到-1，所以该remove方法要配合
                     * next方法来用，使得每次调用该方法lastRet都>0
                     */
                    this.lastRet = -1;
                    /**
                     * 由于ArrayList.this.remove(lastRet)该方法中修改了modCount的值，所以
                     * 这里也要将expectedModCount的值与modCount同步
                     */
                    this.expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException var2) {
                    throw new ConcurrentModificationException();
                }
            }
        }

Vector

        public void remove() {
            if (this.lastRet == -1) {
                throw new IllegalStateException();
            } else {
                synchronized(Vector.this) {
                    this.checkForComodification();
                    Vector.this.remove(this.lastRet);
                    this.expectedModCount = Vector.this.modCount;
                }
                this.cursor = this.lastRet;
                this.lastRet = -1;
            }
        }

4.forEachRemaining

JDK8新增的函数式遍历接口，对每个剩余元素执行给定的操作，直到处理完所有元素或操作引发异常。
如果指定了该顺序，则操作按迭代顺序执行。

default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }

ArrayList

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            int size = ArrayList.this.size;
            int i = this.cursor;
            if (i < size) {
                Object[] es = ArrayList.this.elementData;
                if (i >= es.length) {
                    throw new ConcurrentModificationException();
                }
                while(i < size && ArrayList.this.modCount == this.expectedModCount) {
                    action.accept(ArrayList.elementAt(es, i));
                    ++i;
                }
                this.cursor = i;
                this.lastRet = i - 1;
                this.checkForComodification();
            }
        }

Vector

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            synchronized(Vector.this) {
                int size = Vector.this.elementCount;
                int i = this.cursor;
                if (i < size) {
                    Object[] es = Vector.this.elementData;
                    if (i >= es.length) {
                        throw new ConcurrentModificationException();
                    } else {
                        while(i < size && Vector.this.modCount == this.expectedModCount) {
                            action.accept(Vector.elementAt(es, i++));
                        }

                        this.cursor = i;
                        this.lastRet = i - 1;
                        this.checkForComodification();
                    }
                }
            }
        }

该方法和使用通过hasNext和newt方法遍历有一定的区别，该方法只有在方法的最后更新了一次cursor和lastRet。和next，hasNext方法共用了cursor和lastRet，如果遍历进行到一半，然后使用另一种遍历方式，那么遍历不会从头开始，而是从结束的地方开始

checkForComodification
主要用于验证在循环遍历过程中，是否调用了ArrayList的add，remove等操作，这些操作会增加modCount的值，导致该值和Iterator中的exprctedModCount值不相等，破坏原来的结构，遍历出错。
ArrayList和Vector

        final void checkForComodification() {
            //通过检查两个修改计数器是否一致从而确定在迭代期间元素数组有没有被修改
            if (modCount != expectedModCount) {
                //如果被修改则抛出同时修改异常
                throw new ConcurrentModificationException();
            }
        }

Itr 迭代器类

ArrayList<E>和Vector<E>类中都有私有的Itr内部类
在Itr中重新定义了三个参数：
cursor:当前index
lastRet:上一个index，初始值-1
expectedModCount:修改次数

    private class Itr implements Iterator<E> {
        // 下一个元素的指针
        int cursor;    
        // 上一个元素的指针，如果没有元素则是-1   
        int lastRet = -1; 
        //期望修改计数器，与修改计数器去比较从而确认迭代期间元素数组是否被修改
        int expectedModCount = modCount;
    }

ListItr 迭代器类

private class ListItr extends Itr implements ListIterator<E>
public interface ListIterator<E> extends Iterator<E>
public interface Iterator<E>

Itr 迭代器类实现了 Iterator 接口，ListItr迭代器类继承Itr迭代器类，并且实现了 ListIterator 接口，所以 ListItr类的功能比 Itr 类更强大。ListItr可以说是Itr的升级版

 private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }
        //只要cursor不等于0，就可以往回走
        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        //查找前一个元素
        public E previous() {
            checkForComodification();
            //往回走，所以cursor-1给局部变量
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            //因为get的参数是i，所以lastRet肯定也应该为i
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            //说明执行了remove或add后，还没有进行过next或previous操作
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            //add不用关心lastRet，即不在乎之前有没有remove或add
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

Itr 类在迭代过程中不能修改 List 的结构（如 add 操作），否则会抛出并发修改异常 ConcurrentModificationException，并且在 next方法之后才能 remove 元素，而 ListItr 类还支持在迭代过程中添加元素，对于 List 集合元素操作更加友好。所以对于List 集合迭代，最好使用 ListItr 迭代器类。

以上都是串行的迭代器，下面来介绍并行迭代器Spliterator
Spliterator是一个可分割迭代器(splitable iterator)，可以和iterator顺序遍历迭代器一起看。
Jdk1.8发布后，对于并行处理的能力大大增强，Spliterator就是为了并行遍历元素而设计的一个迭代器，Jdk1.8中的集合框架中的数据结构都默认实现了spliterator

并行迭代器Spliterator

Spliterator接口

public interface Spliterator<T> {
    boolean tryAdvance(Consumer<? super T> action);

    default void forEachRemaining(Consumer<? super T> action) {
        do { } while (tryAdvance(action));
    }

    Spliterator<T> trySplit();

    long estimateSize();

    default long getExactSizeIfKnown() {
        return (characteristics() & SIZED) == 0 ? -1L : estimateSize();
    }

    int characteristics();
    //判断 Spliterator 是否包含这个特性
    default boolean hasCharacteristics(int characteristics) {
        return (characteristics() & characteristics) == characteristics;
    }
    //如果源是SORTED 类型的，且有比较器 Comparator 的话，则返回这个 Comparator，如果是SORTED 类型的，但是没有比较器，则返回 null , 除此之外，都抛出异常。
    default Comparator<? super T> getComparator() {
        throw new IllegalStateException();
    }
    //特性
    //表明元素是有序的，tryAdvance ，forEachRemaining和 trySplit 都会保证有序的进行元素的处理。
    public static final int ORDERED    = 0x00000010;
    //表明元素是去重的，唯一性。 类似 Set 
    public static final int DISTINCT   = 0x00000001;
    //表明遍历的顺序是排好序的。或者是所有元素都是可比较的，或者是有特定的比较器。
    public static final int SORTED     = 0x00000004;
    //有这种属性的 Spliterator 在遍历和分割之前，estimateSize() 返回的大小是固定的，并且是准确的。
    public static final int SIZED      = 0x00000040;
    //表明元素是非空的, 大部分并发的集合，队列，Map 都可能会有这样的特性。
    public static final int NONNULL    = 0x00000100;
    //表示元素源不能进行结构修改的特征值。遍历期间无法添加，替换或删除元素，否则抛出异常。
    public static final int IMMUTABLE  = 0x00000400;
    //表示可以在没有外部同步的情况下由多个线程安全地同时修改元素源（允许添加，替换和/或删除）。
    public static final int CONCURRENT = 0x00001000;
    //trySplit 返回的子分割迭代器都会是SIZED和SUBSIZED的。 分割成子，并且子的部分是固定大小的
    public static final int SUBSIZED = 0x00004000;
}

ArrayList的内部类ArrayListSpliterator实现了Spliterator接口

static final class ArrayListSpliterator<E> implements Spliterator<E> {
        //用于存放ArrayList对象
        private final ArrayList<E> list;
        //起始位置（包含），advance/split操作时会修改
        private int index; 
        //结束位置（不包含），-1 表示到最后一个元素
        private int fence;
        //用于存放list的modCount
        private int expectedModCount; 

        ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                             int expectedModCount) {
            this.list = list; 
            this.index = origin;
            this.fence = fence;
            this.expectedModCount = expectedModCount;
        }

        //获取结束位置（存在意义：首次初始化石需对fence和expectedModCount进行赋值）
        private int getFence() { 
            int hi; 
            ArrayList<E> lst;
            //fence<0时（第一次初始化时，fence才会小于0）：
            if ((hi = fence) < 0) {
                //list 为 null时，fence=0
                if ((lst = list) == null)
                    hi = fence = 0;
                else {
                    //否则，fence = list的长度。
                    expectedModCount = lst.modCount;
                    hi = fence = lst.size;
                }
            }
            return hi;
        }
}

1.tryAdvance

同时做了 hasNext() 以及 next() 的工作
类似于普通的Iterator,它会按顺序一个一个使用 Spliterator 中的元素执行action,并且如果还有其他元素要遍历就返回 true，否则返回 false。

boolean tryAdvance(Consumer<? super T> action);

ArrayList下的实现

    public boolean tryAdvance(Consumer<? super E> action) {
        //如果指定的操作为null则会抛出NullPointerException
        if (action == null)
            throw new NullPointerException();
        //hi为当前的结束位置
        //i 为起始位置
        int hi = getFence(), i = index;
        //还有剩余元素未处理时
        if (i < hi) {
            //处理i位置，index+1
            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;
    }

2.forEachRemaining

默认方法，在当前线程中对每个剩余元素执行给定操作，直到所有元素都已处理或操作抛出异常为止，如果源是有序的，遍历也是有序的。
实现：重复调用tryAdvance(java.util.function.Consumer <? super T>)，直到它返回false。应该尽可能地覆盖它

default void forEachRemaining(Consumer<? super T> action) {
        do { } while (tryAdvance(action));
    }

注：方法体中的 do {} 是空的，这个是因为 tryAdvance() 方法本身就完成了两个操作 hasNext() 以及 next()，所以方法体中不需要有任何操作了。这个是函数式编程带来的好处。以及与命令式编程的区别。
ArrayList下的实现

        public void forEachRemaining(Consumer<? super E> action) {
            int i, hi, mc; 
            ArrayList<E> lst; Object[] a;
            if (action == null)
                throw new NullPointerException();
            if ((lst = list) != null && (a = lst.elementData) != null) {
                //当fence<0时，表示fence和expectedModCount未初始化
                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处理元素
                        action.accept(e);
                    }
                    //遍历时发生结构变更时抛出异常
                    if (lst.modCount == mc)
                        return;
                }
            }
            throw new ConcurrentModificationException();
        }

3.trySplit

尝试切分源来的 Spliterator，返回一个新分割出的Spliterator实例,返回的是分割出来的那一部分数据，原有的数据集将不再包含这部分数据集合。两者没有交集。剩下的可以继续分割，或者不可以继续分割，返回null。
如果是原有数据集合是 ORDERD 的，分出来的也是有序的。

Spliterator<T> trySplit();

官方接口说明：理想的trySplit方法有效地（无需遍历）将其元素精确地一分为二，从而实现平衡的并行计算。 许多偏离这一理想的方法仍然非常有效； 例如，仅对近似平衡的树进行近似分裂，或者对于叶子节点可能包含一个或两个元素的树，未能进一步分裂这些节点。 然而，平衡的大偏差和/或过度低效的trySplit机制通常会导致并行性能不佳。
ArrayList下的实现

public ArrayListSpliterator<E> trySplit() {
     //hi为当前的结束位置
     //lo 为起始位置
     //计算中间的位置
     int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
     //当lo>=mid,表示不能在分割，返回null
     //当lo<mid时,可分割，切割（lo，mid）出去，同时更新index=mid
     return (lo >= mid) ? null : 
          new ArrayListSpliterator<E>(list, lo, index = mid,expectedModCount);
}

4.estimateSize

返回对forEachRemaining遍历将遇到的元素数量的估计，如果无限、未知或计算成本太高，则返回Long.MAX_VALUE,也就是2^63-1

long estimateSize();

官方接口说明：即使是不精确的估计也常常有用且计算成本低。
例如，近似平衡二叉树的子分裂器可能会返回一个值，该值估计元素数量是其父元素数量的一半； 如果根 Spliterator 没有保持准确的计数，它可以将大小估计为对应于其最大深度的 2 的幂。
ArrayList下的实现

public long estimateSize() {
    return (long) (getFence() - index);
}

分割迭代器主要是用来对源数据元素进行遍历和分区。分割迭代器的源数据可以是数组、集合、IO通道以及生成器函数（比如Stream的iterate方法）。
分割迭代器遍历元素有两种方式：
1.通过 tryAdvance 方法单个元素的遍历。
2.通过forEachRemaining 方法顺序的按块遍历。

Spliterator 也可以将它的一些元素（使用trySplit ）作为另一个 Spliterator 进行分区，以用于可能的并行操作。
官方接口说明：
Spliterators 和Iterator一样，用于遍历源的元素。 Spliterator API 旨在通过支持分解和单元素迭代来支持除顺序遍历之外的高效并行遍历。 此外，通过 Spliterator 访问元素的协议旨在施加比Iterator更小的每个元素开销，并避免为hasNext()和next()使用单独的方法所涉及的固有竞争。

衍生接口OfPrimitive

public interface OfPrimitive<T, T_CONS, T_SPLITR 
                          extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>> 
                          extends Spliterator<T> {
        @Override
        T_SPLITR trySplit();

        @SuppressWarnings("overloads")
        boolean tryAdvance(T_CONS action);

        @SuppressWarnings("overloads")
        default void forEachRemaining(T_CONS action) {
            do { } while (tryAdvance(action));
        }
    }

OfPrimitive重载了Spliterator的tryAdvance和forEachRemaining方法。用于实现特化的分割迭代器。
基于OfPrimitive接口，又衍生出了OfInt、OfLong、OfDouble等专门用来处理int、long、double等分割迭代器接口

public interface OfInt extends OfPrimitive<Integer, IntConsumer, OfInt>
public interface OfLong extends OfPrimitive<Long, LongConsumer, OfLong>
public interface OfDouble extends OfPrimitive<Double, DoubleConsumer, OfDouble>

为int 、 long和double值提供了Spliterator原始子类型Spliterator 。
tryAdvance(Consumer)和forEachRemaining(Consumer)的子类型默认实现框原始值到其相应包装器类的实例。
这种装箱可能会破坏通过使用原始特化获得的任何性能优势。 为避免装箱，应使用相应的基于基元的方法

Spliterators类

具体实现都在java.util.Spliterators类中

public final class Spliterators

实现了针对int[]，long[]，double[]数据分割迭代器，和ArrayList差不多

内部类IntArraySpliterator

static final class IntArraySpliterator implements Spliterator.OfInt {
        private final int[] array;
        private int index;        
        private final int fence; 
        //用于记录特征值
        private final int characteristics;

        // 初始构造器
        public IntArraySpliterator(int[] array, int additionalCharacteristics) {
            this(array, 0, array.length, additionalCharacteristics);
        }

        public IntArraySpliterator(int[] array, int origin, 
                                   int fence, int additionalCharacteristics) {
            this.array = array;
            this.index = origin;
            this.fence = fence;
            this.characteristics = additionalCharacteristics 
                                 | Spliterator.SIZED 
                                 | Spliterator.SUBSIZED;
        }
        
        @Override
        public OfInt trySplit() {
            //分割
            int lo = index, mid = (lo + fence) >>> 1;
            return (lo >= mid)
                   ? null
                   : new IntArraySpliterator(array, lo, index = mid, characteristics);
        }

        @Override
        public void forEachRemaining(IntConsumer action) {
            int[] a; int i, hi; 
            if (action == null)
                throw new NullPointerException();
            if ((a = array).length >= (hi = fence) &&
                (i = index) >= 0 && i < (index = hi)) {
                do { action.accept(a[i]); } while (++i < hi);
            }
        }

        @Override
        public boolean tryAdvance(IntConsumer action) {
            if (action == null)
                throw new NullPointerException();
            if (index >= 0 && index < fence) {
                action.accept(array[index++]);
                return true;
            }
            return false;
        }

        @Override
        public long estimateSize() { return (long)(fence - index); }

    }

内部类LongArraySpliterator

static final class LongArraySpliterator implements Spliterator.OfLong {
        private final long[] array;
        private int index;       
        private final int fence;  
        private final int characteristics;

        public LongArraySpliterator(long[] array, int additionalCharacteristics) {
            this(array, 0, array.length, additionalCharacteristics);
        }

        public LongArraySpliterator(long[] array, int origin, 
                                    int fence, int additionalCharacteristics) {
            this.array = array;
            this.index = origin;
            this.fence = fence;
            this.characteristics = additionalCharacteristics 
                                 | Spliterator.SIZED 
                                 | Spliterator.SUBSIZED;
        }

        @Override
        public OfLong trySplit() {
            int lo = index, mid = (lo + fence) >>> 1;
            return (lo >= mid)
                   ? null
                   : new LongArraySpliterator(array, lo, index = mid, characteristics);
        }

        @Override
        public void forEachRemaining(LongConsumer action) {
            long[] a; int i, hi; 
            if (action == null)
                throw new NullPointerException();
            if ((a = array).length >= (hi = fence) &&
                (i = index) >= 0 && i < (index = hi)) {
                do { action.accept(a[i]); } while (++i < hi);
            }
        }

        @Override
        public boolean tryAdvance(LongConsumer action) {
            if (action == null)
                throw new NullPointerException();
            if (index >= 0 && index < fence) {
                action.accept(array[index++]);
                return true;
            }
            return false;
        }

        @Override
        public long estimateSize() { return (long)(fence - index); }
    }

内部类DoubleArraySpliterator

static final class DoubleArraySpliterator implements Spliterator.OfDouble {
        private final double[] array;
        private int index;        
        private final int fence;  
        private final int characteristics;

        public DoubleArraySpliterator(double[] array, int additionalCharacteristics) {
            this(array, 0, array.length, additionalCharacteristics);
        }

        public DoubleArraySpliterator(double[] array, int origin, 
                                      int fence, int additionalCharacteristics) {
            this.array = array;
            this.index = origin;
            this.fence = fence;
            this.characteristics = additionalCharacteristics 
                                 | Spliterator.SIZED 
                                 | Spliterator.SUBSIZED;
        }

        @Override
        public OfDouble trySplit() {
            int lo = index, mid = (lo + fence) >>> 1;
            return (lo >= mid)
                   ? null
                   : new DoubleArraySpliterator(array, lo, index = mid, characteristics);
        }

        @Override
        public void forEachRemaining(DoubleConsumer action) {
            double[] a; int i, hi; 
            if (action == null)
                throw new NullPointerException();
            if ((a = array).length >= (hi = fence) &&
                (i = index) >= 0 && i < (index = hi)) {
                do { action.accept(a[i]); } while (++i < hi);
            }
        }

        @Override
        public boolean tryAdvance(DoubleConsumer action) {
            if (action == null)
                throw new NullPointerException();
            if (index >= 0 && index < fence) {
                action.accept(array[index++]);
                return true;
            }
            return false;
        }

        @Override
        public long estimateSize() { return (long)(fence - index); }
    }

与ArrayList不同的是，array是实现声明的，因此不必担心遍历过程中发生结构变更。

参考文章：

https://www.cnblogs.com/allmignt/p/12353737.html
https://blog.csdn.net/lh513828570/article/details/56673804
https://www.cnblogs.com/qingshanli/p/11756940.html#_label1_0

官方文档：

https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
https://docs.oracle.com/javase/8/docs/api/java/util/Spliterator.html