Spliterator并行遍历迭代器（JDK8）

Edited on In ,

文章前半部分转自：https://blog.csdn.net/lh513828570/article/details/56673804
###Spliterator是什么？
public interface Spliterator
Spliterator是一个可分割迭代器(splitable iterator)
，可以和iterator顺序遍历迭代器一起看。jdk1.8发布后，对于并行处理的能力大大增强，Spliterator就是为了并行遍历元素而设计的一个迭代器，jdk1.8中的集合框架中的数据结构都默认实现了spliterator，后面我们也会结合ArrayList中的spliterator()
一起解析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 //单个对元素执行给定的动作，如果有剩下元素未处理返回true，否则返回false
 boolean tryAdvance(Consumer<? super T>action);

//对每个剩余元素执行给定的动作，依次处理，直到所有元素已被处理或被异常终止。默认方法调用tryAdvance方法
default void forEachRemaining(Consumer<? super T>action){
        do{}while(tryAdvance(action));
        }

        //对任务分割，返回一个新的Spliterator迭代器
        Spliterator<T> trySplit();

        //用于估算还剩下多少个元素需要遍历
        long estimateSize();

//当迭代器拥有SIZED特征时，返回剩余元素个数；否则返回-1
default long getExactSizeIfKnown(){
        return(characteristics()&SIZED)==0?-1L:estimateSize();
        }

        //返回当前对象有哪些特征值
        int characteristics();

//是否具有当前特征值
default boolean hasCharacteristics(int characteristics){
        return(characteristics()&characteristics)==characteristics;
        }
//如果Spliterator的list是通过Comparator排序的，则返回Comparator
//如果Spliterator的list是自然排序的 ，则返回null
//其他情况下抛错
default Comparator<? super T>getComparator(){
        throw new IllegalStateException();
        }

特征值其实就是为表示该Spliterator有哪些特性，用于可以更好控制和优化Spliterator的使用。关于获取比较器getComparator这一个方法，目前我还没看到具体使用的地方，所以可能理解有些误差。（源玛里有这里就不展示了）

###ArrayList的例子
ArrayListSpliterator在ArrayList的源码里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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;
    }

    //分割list，返回一个新分割出的spliterator实例
    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);
    }

    //返回true 时，只表示可能还有元素未处理
    //返回false 时，没有剩余元素处理了。。。
    public boolean tryAdvance(Consumer<? super E> action) {
        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;
    }

    //顺序遍历处理所有剩下的元素
    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) {
            //当fence<0时，表示fence和expectedModCount未初始化，可以思考一下这里能否直接调用getFence()，嘿嘿？
            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();
    }

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

    public int characteristics() {
        //打上特征值：、可以返回size
        return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
    }
}

#####测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 List<String> arrs=new ArrayList<>();
        arrs.add("a");
        arrs.add("b");
        arrs.add("c");
        arrs.add("d");
        arrs.add("e");
        arrs.add("f");
        arrs.add("h");
        arrs.add("i");
        arrs.add("j");
        Spliterator<String> a=arrs.spliterator();
        System.out.println(a);
        //此时结果：a:0-9（index-fence）

        Spliterator<String> b=a.trySplit();
        System.out.println(b.toString());
        //此时结果：b:4-9,a:0-4

        Spliterator<String> c=a.trySplit();
        //此时结果：c:4-6,b:4-9,a:6-9
        System.out.println(c.toString());

        Spliterator<String> d=a.trySplit();
        System.out.println(d.toString());
//此时结果：d:6-7,c:4-6,b:4-9,a:7-9

可以看到每次分割，都会分割剩余的前一半，fence之不变，index后移。同时也发现：
1.ArrayListSpliterator本质上还是对原list进行操作，只是通过index和fence来控制每次处理范围
2.也可以得出，ArrayListSpliterator在遍历元素时，不能对list进行结构变更操作，否则抛错。
###衍生接口OfPrimitive
源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
 public interface OfPrimitive<T, T_CONS, T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>> extends Spliterator<T> {
    T_SPLITR trySplit();

    boolean tryAdvance(T_CONS var1);

    default void forEachRemaining(T_CONS var1) {
        while (this.tryAdvance(var1)) {
            ;
        }

    }
}

可以看到，这个接口基本没有变动，这是多增加两个泛型声明而已，本质上和Spliterator没有太大的区别，只不过，它限制tryAdvance的参数action类型T_CONS和trySplit的返回参数T_SPLITR必须在实现接口时先声明类型。
基于OfPrimitive接口，又衍生出了OfInt、OfLong、OfDouble等专门用来处理int、Long、double等分割迭代器接口（在Spliterators有具体的实现）。
LinkedHashSet中的Spliterator方法的实现，内部使用到了Sqlieterator接口的常量值！

##简单的并发测试（jdk1.8+）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
    private AtomicInteger count=new AtomicInteger(0);
private List<String> strList=createList();
private Spliterator spliterator=strList.spliterator();

/**
 * 多线程计算list中数值的和
 * 测试spliterator遍历
 */
@Test
public void mytest(){
        for(int i=0;i< 4;i++){
        new Thread(()->{
        String threadName=Thread.currentThread().getName();
        System.out.println("   "+threadName+" start ");
        spliterator.trySplit().forEachRemaining((o)->{
        if(isInteger((String)o)){
        int num=Integer.parseInt(o+"");
        count.addAndGet(num);
        System.out.println("数值："+num+"     "+threadName);
        try{
        Thread.sleep(2000);
        }catch(InterruptedException e){
        e.printStackTrace();
        }
        }
        });
        System.out.println("     "+threadName+" end");
        }).start();
        }
        try{
        Thread.sleep(15000);
        }catch(InterruptedException e){
        e.printStackTrace();
        }
        System.out.println("结果为："+count);
        }

private List<String> createList(){
        List<String> result=new ArrayList<>();
        for(int i=0;i< 100;i++){
        if(i%10==0){
        result.add(i+"");
        }else{
        result.add("=");
        }
        }
        return result;
        }

public static boolean isInteger(String str){
        Pattern pattern=Pattern.compile("^[-\\+]?[\\d]*$");
        return pattern.matcher(str).matches();
        }

本文地址 Spliterator并行遍历迭代器（JDK8）

本文地址： https://github.com/maxzhao-it/blog/post/42644/