模块  java.base
软件包  java.util

Interface Spliterator<T>

  • 参数类型
    T - 此Spliterator返回的元素类型
    All Known Subinterfaces:
    Spliterator.OfDoubleSpliterator.OfIntSpliterator.OfLongSpliterator.OfPrimitive<T,​T_CONS,​T_SPLITR>
    所有已知实现类:
    Spliterators.AbstractDoubleSpliteratorSpliterators.AbstractIntSpliteratorSpliterators.AbstractLongSpliteratorSpliterators.AbstractSpliterator

    public interface Spliterator<T>
    用于遍历和分区源元素的对象。 Spliterator覆盖的元素源可以是例如阵列, Collection ,IO通道或生成器函数。

    Spliterator可以单独遍历元素( tryAdvance() )或按顺序遍历元素( forEachRemaining() )。

    Spliterator还可以将其某些元素(使用trySplit() )作为另一个Spliterator进行分区,以用于可能并行的操作。 使用无法拆分的Spliterator或以高度不平衡或低效的方式进行操作的操作不太可能从并行性中受益。 横向和分离排气元件; 每个Spliterator仅对单个批量计算有用。

    甲Spliterator还报告一组characteristics()选自其结构,源极和元件的ORDEREDDISTINCTSORTEDSIZEDNONNULLIMMUTABLECONCURRENT ,和SUBSIZED Spliterator客户端可以使用这些来控制,专门化或简化计算。 例如,CollectionSpliterator将报告SIZEDSpliterator将报告DISTINCT ,而SortedSetSpliterator也报告SORTED 特征报告为简单的联合位集。 一些特征还限制了方法行为; 例如,如果ORDERED ,遍历方法必须符合其记录的顺序。 未来可能会定义新特征,因此实现者不应将意义分配给未列出的值。

    A Spliterator that does not report IMMUTABLE or CONCURRENT is expected to have a documented policy concerning: when the spliterator binds to the element source; and detection of structural interference of the element source detected after binding. 后期绑定 Spliterator在第一次遍历,第一次拆分或第一次查询估计大小时绑定到元素源,而不是在创建Spliterator时绑定。 后期绑定的 Spliterator在构造点或任何方法的第一次调用时绑定到元素源。 遍历Spliterator时会反映在绑定之前对源进行的修改。 绑定Spliterator后,如果检测到结构性干扰, 应尽最大努力抛出ConcurrentModificationException 执行此操作的Spliterators称为快速失败 Spliterator的批量遍历方法( forEachRemaining() )可以优化遍历并在遍历所有元素之后检查结构干扰,而不是检查每个元素并立即失败。

    Spliterators可以通过estimateSize()方法估算剩余元素的数量。 理想情况下,如特征SIZED所反映的,该值与成功遍历中遇到的元素数量完全对应。 然而,即使不完全已知,估计值对于在源上执行的操作仍然是有用的,例如帮助确定是否优选地进一步分割或顺序遍历剩余元素。

    尽管它们在并行算法中具有明显的实用性,但预计分裂器不是线程安全的。 相反,使用分裂器的并行算法的实现应确保分裂器一次仅由一个线程使用。 这通常很容易通过串行线程限制来实现,这通常是通过递归分解工作的典型并行算法的自然结果。 调用trySplit()的线程可以将返回的Spliterator移交给另一个线程,该线程又可以遍历或进一步拆分该Spliterator。 如果两个或多个线程在同一个spliterator上同时运行,则拆分和遍历的行为是不确定的。 如果原始线程将分离器移交给另一个线程进行处理,最好是在使用tryAdvance()消耗任何元素之前进行切换,因为某些保证(例如4510720863823对于SIZED分裂器的准确性)仅在遍历开始之前有效。

    的原始亚型特Spliterator被提供用于intlong ,和double值。 子类型默认实现tryAdvance(java.util.function.Consumer)forEachRemaining(java.util.function.Consumer)框原始值到其对应的包装类的实例。 这种装箱可能会破坏使用原始专业化所获得的任何性能优势。 为避免装箱,应使用相应的基于图元的方法。 例如, Spliterator.OfPrimitive.tryAdvance(java.util.function.IntConsumer)Spliterator.OfPrimitive.forEachRemaining(java.util.function.IntConsumer)应优先用于Spliterator.OfInt.tryAdvance(java.util.function.Consumer)Spliterator.OfInt.forEachRemaining(java.util.function.Consumer) 使用基于装箱的方法tryAdvance()forEachRemaining()遍历原始值不会影响遇到转换为盒装值的值的顺序。

    API Note:

    Spliterators,如Iterator ,用于遍历源的元素。 除了顺序遍历之外, Spliterator API还支持有效的并行遍历,支持分解以及单元素迭代。 此外,通过Spliterator访问元素的协议旨在施加比Iterator更小的每元素开销,并避免与hasNext()next()具有单独方法相关的固有竞争。

    对于可变源,如果源在Spliterator绑定到其数据源的时间与遍历结束之间受到结构干扰(元素添加,替换或删除),则可能会发生任意和非确定性行为。 例如,当使用java.util.stream框架时,此类干扰将产生任意的,不确定的结果。

    源的结构干扰可以通过以下方式进行管理(大致降低合意性的顺序):

    • 源不能在结构上受到干扰。
      例如, CopyOnWriteArrayList的实例是不可变的源。 从源创建的IMMUTABLE报告IMMUTABLE的特征。
    • 源管理并发修改。
      例如, ConcurrentHashMap的密钥集是并发源。 从源创建的CONCURRENT报告特征为CONCURRENT
    • 可变源提供了后期绑定和失败快速的Spliterator。
      后期绑定使窗口变窄,在此期间干扰会影响计算; 在遍历开始并且抛出ConcurrentModificationException之后,在尽力而为的基础上快速检测到结构干扰已经发生。 例如, JDK中的ArrayList和许多其他非并发Collection类提供了一种后期绑定,失败快速的分裂器。
    • 可变源提供非后期绑定但失败快速的Spliterator。
      由于潜在干扰窗口较大,因此增加投掷ConcurrentModificationException的可能性。
    • 可变源提供了后期绑定和非故障快速Spliterator。
      由于未检测到干扰,在遍历开始之后,源会冒任意,非确定性行为。
    • 可变源提供非后期绑定和非故障快速Spliterator。
      源增加了任意,非确定性行为的风险,因为在构造之后可能发生未检测到的干扰。

    例。 这是一个类(不是非常有用的,除了插图),它维护一个数组,其中实际数据保存在偶数位置,而不相关的标签数据保存在奇数位置。 它的Spliterator忽略标签。

       class TaggedArray<T> { private final Object[] elements; // immutable after construction TaggedArray(T[] data, Object[] tags) { int size = data.length; if (tags.length != size) throw new IllegalArgumentException(); this.elements = new Object[2 * size]; for (int i = 0, j = 0; i < size; ++i) { elements[j++] = data[i]; elements[j++] = tags[i]; } } public Spliterator<T> spliterator() { return new TaggedArraySpliterator<>(elements, 0, elements.length); } static class TaggedArraySpliterator<T> implements Spliterator<T> { private final Object[] array; private int origin; // current index, advanced on split or traversal private final int fence; // one past the greatest index TaggedArraySpliterator(Object[] array, int origin, int fence) { this.array = array; this.origin = origin; this.fence = fence; } public void forEachRemaining(Consumer<? super T> action) { for (; origin < fence; origin += 2) action.accept((T) array[origin]); } public boolean tryAdvance(Consumer<? super T> action) { if (origin < fence) { action.accept((T) array[origin]); origin += 2; return true; } else // cannot advance return false; } public Spliterator<T> trySplit() { int lo = origin; // divide range in half int mid = ((lo + fence) >>> 1) & ~1; // force midpoint to be even if (lo < mid) { // split out left half origin = mid; // reset this Spliterator's origin return new TaggedArraySpliterator<>(array, lo, mid); } else // too small to split return null; } public long estimateSize() { return (long)((fence - origin) / 2); } public int characteristics() { return ORDERED | SIZED | IMMUTABLE | SUBSIZED; } } } 

    作为一个例子,并行计算框架(如java.util.stream包)将如何在并行计算中使用Spliterator,这是实现关联并行forEach的一种方法,它说明了在估计工作量之前拆分子任务的主要用法习惯用法小到足以按顺序执行。 这里我们假设跨子任务的处理顺序无关紧要; 不同(分叉)任务可以以不确定的顺序进一步分割和处理元素。 这个例子使用了CountedCompleter ; 类似的用法适用于其他并行任务结构。

       static <T> void parEach(TaggedArray<T> a, Consumer<T> action) { Spliterator<T> s = a.spliterator(); long targetBatchSize = s.estimateSize() / (ForkJoinPool.getCommonPoolParallelism() * 8); new ParEach(null, s, action, targetBatchSize).invoke(); } static class ParEach<T> extends CountedCompleter<Void> { final Spliterator<T> spliterator; final Consumer<T> action; final long targetBatchSize; ParEach(ParEach<T> parent, Spliterator<T> spliterator, Consumer<T> action, long targetBatchSize) { super(parent); this.spliterator = spliterator; this.action = action; this.targetBatchSize = targetBatchSize; } public void compute() { Spliterator<T> sub; while (spliterator.estimateSize() > targetBatchSize && (sub = spliterator.trySplit()) != null) { addToPendingCount(1); new ParEach<>(this, sub, action, targetBatchSize).fork(); } spliterator.forEachRemaining(action); propagateCompletion(); } } 
    Implementation Note:
    如果布尔系统属性 org.openjdk.java.util.stream.tripwire设置为 true则在对原始子类型特化进行操作时,如果出现原始值的装箱,则会报告诊断警告。
    从以下版本开始:
    1.8
    另请参见:
    Collection
    • 字段汇总

      字段  
      变量和类型 字段 描述
      static int CONCURRENT
      表示可以在没有外部同步的情况下由多个线程安全地同时修改元素源(允许添加,替换和/或删除)的特征值。
      static int DISTINCT
      特性值这标志着,对于每对遇到的元件的 x, y!x.equals(y)
      static int IMMUTABLE
      表示元素源不能进行结构修改的特征值; 也就是说,无法添加,替换或删除元素,因此在遍历期间不会发生此类更改。
      static int NONNULL
      特征值表示源保证遇到的元素不会是 null
      static int ORDERED
      表示为元素定义遭遇顺序的特征值。
      static int SIZED
      表示在遍历或拆分之前从 estimateSize()返回的值的特征值表示有限大小,在没有结构源修改的情况下,表示完整遍历将遇到的元素数量的精确计数。
      static int SORTED
      表示遇到订单遵循已定义排序顺序的特征值。
      static int SUBSIZED
      表示trySplit()产生的所有分隔 trySplit()均为 SIZEDSUBSIZED特征值。
    • 字段详细信息

      • DISTINCT

        static final int DISTINCT
        特性值这标志着,对于每对遇到的元件的x, y!x.equals(y) 例如,这适用于基于Set的Spliterator
        另请参见:
        常数字段值
      • SORTED

        static final int SORTED
        表示遇到订单遵循已定义排序顺序的特征值。 如果是这样,方法getComparator()返回关联比较,或null如果所有元素都是Comparable ,并通过其自然顺序进行排序。

        报告SORTED还必须报告ORDERED

        API Note:
        JDK中Collection类的分裂器实现NavigableSetSortedSet报告SORTED
        另请参见:
        常数字段值
      • SIZED

        static final int SIZED
        表示在遍历或拆分之前从 estimateSize()返回的值的特征值表示有限大小,在没有结构源修改的情况下,表示完整遍历将遇到的元素数量的精确计数。
        API Note:
        大多数收集的Spliterators,涵盖了Collection所有元素,报告了这一特征。 子分裂器,例如用于HashSet的子分裂器 ,其覆盖元件的子集并且接近其报告的大小。
        另请参见:
        常数字段值
      • NONNULL

        static final int NONNULL
        表示源保证遇到的元素不是null特征值。 (例如,这适用于大多数并发集合,队列和映射。)
        另请参见:
        常数字段值
      • IMMUTABLE

        static final int IMMUTABLE
        表示元素源不能进行结构修改的特征值; 也就是说,无法添加,替换或删除元素,因此在遍历期间不会发生此类更改。 未报告IMMUTABLECONCURRENT应具有关于遍历期间检测到的结构干扰的文档化策略(例如,抛出ConcurrentModificationException )。
        另请参见:
        常数字段值
      • CONCURRENT

        static final int CONCURRENT
        表示可以在没有外部同步的情况下由多个线程安全地同时修改元素源(允许添加,替换和/或删除)的特征值。 如果是这样,Spliterator应该有一个关于遍历期间修改影响的书面政策。

        顶级Spliterator不应报告CONCURRENTSIZED ,因为如果已知,有限大小可能会在遍历期间同时修改源时发生更改。 这样的Spliterator是不一致的,并且不能保证使用该Spliterator进行任何计算。 如果已知子分割尺寸,则子分割器可以报告SIZED ,并且在遍历时不反映对源的添加或移除。

        顶级Spliterator不应报告CONCURRENTIMMUTABLE ,因为它们是互斥的。 这样的Spliterator是不一致的,并且不能保证使用该Spliterator进行任何计算。 如果在遍历时未反映对源的添加或删除,则子分类符可以报告IMMUTABLE

        API Note:
        大多数并发收集保持一致性策略,保证Spliterator构造点处存在的元素的准确性,但可能不反映后续添加或删除。
        另请参见:
        常数字段值
      • SUBSIZED

        static final int SUBSIZED
        特征值这标志着从产生的所有Spliterators trySplit()将是既SIZEDSUBSIZED (这意味着所有子Spliterator,无论是直接还是间接,都将是SIZED

        未按SIZED要求报告SIZEDSUBSIZED不一致,并且不能保证使用该Spliterator进行任何计算。

        API Note:
        一些分裂器,例如用于近似平衡二叉树的顶级分裂器,将报告 SIZED但不报告 SUBSIZED ,因为通常知道整个树的大小但不知道子树的确切大小。
        另请参见:
        常数字段值
    • 方法详细信息

      • tryAdvance

        boolean tryAdvance​(Consumer<? super T> action)
        如果存在剩余元素,则对其执行给定操作,返回true ; 否则返回false 如果此Spliterator为ORDERED ,则会对遇到顺序中的下一个元素执行操作。 操作抛出的异常将转发给调用者。
        参数
        action - 动作
        结果
        false如果在进入此方法时没有剩余元素, true
        异常
        NullPointerException - 如果指定的操作为null
      • forEachRemaining

        default void forEachRemaining​(Consumer<? super T> action)
        在当前线程中按顺序对每个剩余元素执行给定操作,直到所有元素都已处理或操作引发异常。 如果此Spliterator为ORDERED则按遭遇顺序执行操作。 操作抛出的异常将转发给调用者。
        实现要求:
        默认实现重复调用tryAdvance(java.util.function.Consumer<? super T>)直到它返回false 应该尽可能地覆盖它。
        参数
        action - 动作
        异常
        NullPointerException - 如果指定的操作为null
      • trySplit

        Spliterator<T> trySplit()
        如果可以对此spliterator进行分区,则返回Spliterator覆盖元素,这些元素在从此方法返回时将不被此Spliterator覆盖。

        如果此Spliterator为ORDERED ,则返回的Spliterator必须覆盖元素的严格前缀。

        除非此Spliterator包含无限数量的元素,否则重复调用trySplit()最终必须返回null 在非null返回时:

        • 在拆分之前为estimateSize()报告的值,在拆分后,必须大于或等于estimateSize()和返回的Spliterator;
        • 如果此Spliterator为SUBSIZED ,则estimateSize()前的此拆分器的estimateSize()必须等estimateSize()estimateSize()和拆分后返回的Spliterator之和。

        由于任何原因,该方法可能返回null ,包括null ,在遍历开始后无法拆分,数据结构约束和效率考虑。

        API Note:
        理想的trySplit方法(无遍历)将其元素精确地分成两半,从而实现平衡并行计算。 许多偏离这种理想仍然非常有效; 例如,仅大致分割近似平衡的树,或者叶子节点可能包含一个或两个元素的树,无法进一步分割这些节点。 然而,平衡性和/或效率trySplit大偏差通常导致差的并行性能。
        结果
        一个 Spliterator覆盖所述元件的一些部分,或者 null如果此spliterator不能拆分
      • estimateSize

        long estimateSize()
        返回forEachRemaining(java.util.function.Consumer<? super T>)遍历将遇到的元素数量的估计值,如果无限,未知或计算成本太高,则返回Long.MAX_VALUE

        如果此Spliterator为SIZED且尚未部分遍历或拆分,或者此Spliterator为SUBSIZED且尚未部分遍历,则此估计值必须是完整遍历将遇到的元素的准确计数。 否则,此估计可能是任意不准确的,但必须按照trySplit()调用指定的方式减少

        API Note:
        即使是不精确的估计通常也很有用且计算成本低廉。 例如,近似平衡的二叉树的子分裂器可以返回一个值,该值估计元素的数量是其父元素的一半; 如果根Spliterator没有保持准确的计数,它可以估计大小为对应于其最大深度的2的幂。
        结果
        估计大小,或 Long.MAX_VALUE如果计算无限,未知或太昂贵。
      • getExactSizeIfKnown

        default long getExactSizeIfKnown()
        如果此Spliterator为 SIZED则返回 estimateSize()便捷方法,否则 -1
        实现要求:
        如果Spliterator报告特征为 SIZED ,则默认实现返回 estimateSize()的结果, estimateSize()返回 -1
        结果
        确切的大小,如果知道,否则 -1
      • characteristics

        int characteristics()
        返回此Spliterator及其元素的一组特征。 结果从表示为或运算值ORDEREDDISTINCTSORTEDSIZEDNONNULLIMMUTABLECONCURRENTSUBSIZED 反复拨打characteristics()在给定的spliterator之前或在两者之间的调用, trySplit ,应始终返回相同的结果。

        如果Spliterator报告一组不一致的特征(从单个调用或多个调用返回的特征),则无法保证使用此Spliterator进行任何计算。

        API Note:
        分裂前给定分裂器的特性可能与分裂后的特征不同。 对于具体的例子看到的特性值SIZEDSUBSIZEDCONCURRENT
        结果
        表征特征
      • hasCharacteristics

        default boolean hasCharacteristics​(int characteristics)
        如果此Spliterator的 characteristics()包含所有给定特征,则返回 true
        实现要求:
        如果设置了给定特征的相应位,则默认实现返回true。
        参数
        characteristics - 要检查的特征
        结果
        true如果存在所有指定的特征, false