分割迭代器

一、类概述

 分割迭代器主要是用来对源数据元素进行遍历和分区。分割迭代器的源数据可以是数组、集合、IO通道以及生成器函数（比如Stream的iterate方法）。
 分割迭代器遍历元素有两种方式：①通过tryAdvance方法单个元素的遍历。②通过forEachRemaining方法顺序的按块遍历。
 一个分割迭代器可以调用trySplit方法，分割元素成为另一个分割迭代器。在某些情况下使用并行的分割迭代器的操作可能效果并不是太好，比如元素不能再分割，分割的元素数量不平衡，分割的效率比较低等。每一个分割迭代器只对本块的元素有用。
 每一个分割迭代器的结构、源数据、元素有不同的特征，比如ORDERED、DISTINCT、SORTED、SIZED、NONNULL、IMMUTABLE、CONCURRENT、SUBSIZED。这些特征值主要是便于客户端的控制、特化和简化计算。比如Collection的分割迭代器会有SIZED这一特征，Set的分割迭代器会有DISTINCT这一特征值等。
 特征值一般会约束方法，比如如果特征是ORDERED，那么遍历的方法必须遵循文档化的顺序。
 如果分割迭代器没有包含IMMUTABLE和CONCURRENT特征值，那么分割迭代器就需要关注：分割迭代器何时绑定数据源、数据源绑定后的数据源发生结构的变化（比如添加元素、删除元素）。如果是延迟绑定的分割迭代器，那么迭代器在第一次遍历，或第一次分割、或第一次查询大小时，绑定数据源，而不是在分割迭代器创建的时候。如果分割迭代器不是延迟绑定的，那么它绑定数据源的时刻是分割迭代器创建的时候或者调用任意的方法时。如果对数据源的修改先于绑定行为，那么分割迭代器遍历的时候会反应出此变化（比如添加的元素会被遍历）。如果修改是在绑定行为之后，就会抛出ConcurrentModificationException异常（类似于遍历集合的时候添加元素）。这种行为就是fail-fast。块遍历的方法（forEachRemaining）可能会优化遍历，并且在元素遍历之后会检查结构变化，而不是检查每一个元素（马上报告异常）。
 分割迭代器可以调用estimateSize方法估算出保持的元素数量，理想状态下，如果分割迭代器含有SIZED这一特征值，estimateSize的返回值严格相等待遍历的元素的数量。但是呢，也存在不相等的情况，虽然不相等，但是估计值依然是有用的，比如是否需要进一步分割等。
 尽管分割迭代器在并行计算中有明显的效用，分割迭代器并不是线程安全的。使用分割迭代器实现并行算法应该确保分割迭代器在同一时刻只能被一个线程使用。这种实现比较容易的方案是串行线程封闭（通过将多个并发的任务存入队列实现任务的串行化，并为这些串行化的任务创建唯一的一个工作线程进行处理），调用trySplit方法的线程传递返回的Spliterator给另一个线程（可以遍历或者进一步分割迭代器），假如有两个或者更多的线程并行的操作，那么到底是遍历还是分割将是不确定的。假如一个线程分割，另一个线程计算分割的结果，最理想的状态是线程切换发生在元素被consume之前（也就是tryAdvance方法调用之前）。
 JDK为原始类型提供了特化的实现，譬如ofInt、ofLong等，这种方式避免了拆装箱带来的性能消耗。
 像迭代器一样，分割迭代器用于遍历元素，只不过分割迭代器还以分区的形式支持并行遍历。与迭代器相比，分割迭代器访问元素的消耗更小，因为分割迭代器避免了潜在的竞争（普通迭代器访问元素需要hasNext方法和next方法配合，分割迭代器只需一个tryAdvance方法）
 对于可变的数据源，假如在绑定数据与遍历结束期间，源数据发生了结构的改变（增加、删除等），那么可能会产生无法预料的结果。
 结构上的改变也可以通过下列的方法管理：
  源数据不能被结构地改变，比如数据源是CopyOnWriteArrayList（不变的源，适用于读多写少的操作的集合）的实例，那么与之绑定的分割迭代器需配置IMMUTABLE特征值。
  源数据管理并行的修改，ConcurrentHashMap的key的Set是源数据，分割迭代器需配置CONCURRENT特征值。
  可变的源数据提供延迟绑定和fail-fast分割迭代器。
延迟绑定缩短了窗口时间（创建分割迭代器到元素遍历的时间），fail-fast可以在遍历开始后检测结构改变，并且抛出异常。
  可变源提供了非延迟绑但是fail-fast分割迭代器，这样源就增加了抛出异常的可能性（ConcurrentModificationException）。
  可变源提供了延迟绑定但是non-fail-fast分割迭代器，这样源就增加了未知结果的可能性。
  可变源提供了非延迟绑定和non-fail-fast分割迭代器，这样源就增加了未知结果的可能性，因为可能发生结构变化

方法概述

 boolean tryAdvance(Consumer<? super T> action)
  如果分割迭代器存在元素，那么就执行给定的action，并且返回true，否则返回false。如果分割迭代器是ORDERED的，那么元素也会顺序的执行action。被action发出的异常会传递给调用者。

 default void forEachRemaining(Consumer<? super T> action)
  每一个剩余的元素在当前线程中串行地执行给定的action，如果分割迭代器是ORDERED的，那么元素也会顺序的执行action。被action发出的异常会传递给调用者。

 Spliterator<T> trySplit()
  方法的含义：用于分割迭代器的分割。
  文档说明：假如分割迭代器（母）可以被分割，调用该方法就会返回一个新的分割迭代器（子）。

母分割迭代器的元素是
    1,2,3,4,5,6,7,8
分割之后
母分割迭代器的元素是 5,6,7,8
子分割迭代器的元素是 1,2,3,4

  如果母分割迭代器是ORDERED的，那么调用该方法的子分割迭代器也是ORDERED的。
  重复调用该方法，最终一定会返回null，除非母分割迭代器的元素是无限的。如果调用该方法的返回值为非空的（也就是有子分割迭代器），那么在调用此方法分割之前调用estimateSize的值必然会大于或等于分割之后母分割迭代器与子分割迭代器的estimateSize值。除此之外，如果母分割迭代器的特征值是SUBSIZED的，那么在分割之前的estimateSize的值必须等于分割之后母分割迭代器estimateSize和子分割迭代器estimateSize的和。

分割之前（trySplit之前）母分割迭代器的元素
    1,2,3,4,5,6,7,8
一定大于或等于分割之后母分割迭代器、子分割迭代器的元素个数

分割之前（trySplit之前）母分割迭代器的元素
    1,2,3,4,5,6,7,8
分割之后 母分割迭代器的元素1,2,3,4  子分割迭代器的元素5,6,7,8 一定等于母子元素个数之和
    

  如果分割迭代器的元素为空、遍历已经开始、数据结构的限制、效率的限制，以上情况可能该方法会返回空

  理想情况调用trySplit分割，会将元素分为五五开。非理想情况可能保持很好的效用，比如树结构。但是不平衡或者低效的分割会导致并行的低效率

 long estimateSize()
  方法的含义：计算出分割迭代器的元素个数的估算值
  返回的值有两种情况，一种情况就是forEachRemaining将要遍历到的元素的个数，另一种情况就是Long#MAX_VALUE（元素无穷的、计算成本较高）。

  在以下两种情况，该方法的返回值就是分割迭代器元素的个数。

①：分割迭代器是SIZED，并且还没开始分割和遍历
②：分割迭代器是SUBSIZED的，并且还没开始遍历

除了以上两种情况，返回值可能是非正确的，但是该值会随着trySplit的调用而减少。

  非精确的估算值也是有用的，并且计算也是很方便的，比如一个平衡的二叉树的子分割迭代器可能会返回其母分割迭代器的元素个数的一半，如果母分割迭代器保持的元素个数是不精确的，子分割迭代器可能就是与树的深度有关。

 int characteristics()
  方法的含义：返回分割迭代器的特征值
  在分割迭代器之前，重复调用该方法的返回值是一样的
  分割之前的特征可能会与分割之后的特征不同。

特征值概述

 ORDERED
  表明元素是有序的，如果是此特征值，那么trySplit分割之后的元素是有序的，tryAdvance处理元素也是有序的，forEachRemaining处理元素也是有序的。如果Collection#iterator是有序的，那么Collection也是有序的。
  List的遍历顺序是按照索引顺序，HashSet是无序的

 DISTINCT
  表明元素是去重的

 SORTED
  表明遍历的顺序是排好序的，再此特征值下getComparator将会返回相关联的比较器或者null（自然排序），如果包含了此特征值，那么分割迭代器必然是ORDERED的

 SIZED
  表明在遍历和分割之前estimateSize的返回值是一个有限的值，并且在没有源结构修改的情况下（增加、删除等），返回值将是遍历元素个数的准确值

 NONNULL
  表明元素是非空的

 IMMUTABLE
  表明在遍历的时候源结构不能被修改，如果没有IMMUTABLE和CONCURRENT的特征值的分割迭代器，需要有一个关注（遍历的时候结构变化）

 CONCURRENT
  在不需要额外同步的情况下，源结构可能被多线程并发的修改。

 SUBSIZED
  trySplit返回的子分割迭代器都会是SIZED和SUBSIZED的。