阿里二面：Java8的Stream api是迭代一次还是迭代多次

面试官：java8新增的stream api用过吗?

我：这个必须用过啊。

面试官：给你下面一个字符串数组,如果用stream api来实现，找出以字符'a'开头长度最大的字符串，使用stream api该怎么实现呢?

1. {"abb","abcd","fegc","efe","adfes"}

我：用下面这个方法来实现：

1. publicstaticvoidmaxLength(Listlist){
2. System.out.println(list.stream().filter(s->s.startsWith("a")).mapToInt(r->length(r)).max().orElse(0));;
3. }

面试官：这个操作是迭代一次还是迭代两次呢?也就是说是先迭代一遍，过滤出以字符'a'开头的字符串数组，然后再迭代一次，找出最大长度，还是一次迭代完成呢?

我:这个是迭代一次完成，如果要是迭代多次，stream后面的操作函数很多的情况下效率会非常低。我们加个打印可以来验证结果，代码如下：

1. publicstaticvoidmain(String[]args){
2. Listlist=Arrays.asList("abb","abcd","fegc","efe","adfes");
3. intmaxLength=list.stream().
4. filter(s->isStartWitha(s)).
5. mapToInt(StreamTest1::length).
6. max().orElse(0);
7. System.out.println("以字符a开头的字符串最大长度:"+maxLength);
8. }
10. privatestaticbooleanisStartWitha(Stringa){
11. System.out.println(a+"isstartwitha："+a.startsWith("a"));
12. returna.startsWith("a");
13. }
15. privatestaticintlength(Stringa){
16. System.out.println("thelengthof"+a+":"+a.length());
17. returna.length();
18. }

打印结果如下：

1. abbisstartwitha：true
2. thelengthofabb:3
3. abcdisstartwitha：true
4. thelengthofabcd:4
5. fegcisstartwitha：false
6. efeisstartwitha：false
7. adfesisstartwitha：true
8. thelengthofadfes:5
9. 以字符a开头的字符串最大长度:5

面试官：你确定只是迭代一次吗?有其他情况吗?

我：有。filter是一个无状态的中间操作，对于这个中间操作来说，stream处理只需要迭代一次。但是对于有状态的中间操作，就需要迭代多次。

面试官：你刚刚提到有状态的操作和无状态的操作，这个是怎么区分呢?

我：在stream api中，无状态的操作是指当前元素的操作不受前面元素的影响，主要包括如下方法：

1. filter(),flatMap(),flatMapToInt(),flatMapToLong(),flatMapToDouble(),map(),mapToInt(),mapToDouble(),mapToLong(),peek(),unordered()

而有状态的操作是指需要等所有元素处理完之后才能执行当前操作，主要包括下面方法：

1. distinct(),limit(),skip(),sorted(),sorted()

面试官：有状态的操作，能举个例子吗?

我：比如下面这段代码：

1. publicstaticvoidmain(String[]args){
2. List<Integer>list=Arrays.asList(5,2,3,1,4);
4. List<Integer>newArray=list.stream()
5. .map(StreamTest2::map1)
6. .sorted((o1,o2)->o1-o2)
7. .map(StreamTest2::map2)
8. .collect(Collectors.toList());
9. System.out.println("新的有序数组:"+newArray);
10. }
12. privatestaticIntegermap1(Integeri){
13. intresult=i*10;
14. System.out.println("线程:"+Thread.currentThread().getName()+"方法map1入参："+i+",输出:"+result);
15. returnresult;
16. }
18. privatestaticIntegermap2(Integeri){
19. intresult=i*10;
20. System.out.println("线程:"+Thread.currentThread().getName()+"方法map2入参："+i+",输出:"+result);
21. returnresult;
22. }

上面代码中，对原始数组进行了两次迭代，第一次迭代对所有数组元素都调用了map1方法乘以10，然后对新数组进行排序，第二次迭代对排序后的数组元素调用map2方法，即对排序后的数组元素乘以10。方法输出如下：

1. 线程:main方法map1入参：5,输出:50
2. 线程:main方法map1入参：2,输出:20
3. 线程:main方法map1入参：3,输出:30
4. 线程:main方法map1入参：1,输出:10
5. 线程:main方法map1入参：4,输出:40
6. 线程:main方法map2入参：10,输出:100
7. 线程:main方法map2入参：20,输出:200
8. 线程:main方法map2入参：30,输出:300
9. 线程:main方法map2入参：40,输出:400
10. 线程:main方法map2入参：50,输出:500
11. 新的有序数组:[100,200,300,400,500]

面试官：了解过底层原理吗?

我：我来先画一下Stream的UML类图：

这个类图说明以下几点：

• AbstractPipeline有基本类型的子类，如LongPipeline和DoublePipeline，还有一个引用类型的子类ReferencePipeline。
• 无论是ReferencePipeline，还是LongPipeline和DoublePipeline等基本类型的Pipeline，都有3个内部类来继承自己。
• StatelessOp对应无状态的操作，StatefulOp对应有状态的操作，Head对应Collection.stream()方法返回结果。
• 无论是StatelessOp、StatefulOp还是Head，都是一个Pipeline，这些Pipeline用双向链表串联起来，每个Pipeline节点被看作一个Stage，Head是链表的头结点。上面UML类图中AbstractPipeline类中previousStage和nextStage就代表双向链表当前节点指向前后节点的引用。如下图：

面试官：上面用双向链表把所有操作都串联起来了，这样可以实现从Head节点开始依次执行所有的操作。但是这些操作怎么叠加在一起呢?比如下面这段代码有三个map方法，后面的方法要依赖前面的计算结果：

1. List<Integer>list=Arrays.asList(5,2,3,1,4);
2. List<Integer>newArray=list.stream().map(StreamTest2::map1).map(StreamTest2::map2).map(StreamTest2::map3).collect(Collectors.toList());

我：Stream提供了Sink接口来处理操作的叠加。上面代码的map方法把操作封装到了Sink，每个节点执行操作时，调用Sink的accept方法就可以把操作结果传给下一个节点的Sink。比如map方法源代码如下：

1. publicfinalStreammap(Functionmapper){
2. Objects.requireNonNull(mapper);
3. returnnewStatelessOp(this,StreamShape.REFERENCE,
4. StreamOpFlag.NOT_SORTED|StreamOpFlag.NOT_DISTINCT){
5. @Override
6. //返回包装成的Sink
7. SinkopWrapSink(intflags,Sinksink){
8. returnnewSink.ChainedReference(sink){
9. @Override
10. publicvoidaccept(P_OUTu){
11. //downstream是下游节点的Sink，把当前节点的执行结果传给下游节点
12. downstream.accept(mapper.apply(u));
13. }
14. };
15. }
16. };
17. }

面试官：能详细讲一下Sink吗?

我：Sink主要提供了下面4个方法

1. //执行操作之前调用这个方法
2. voidbegin(longsize)
3. //执行操作之后调用这个方法
4. voidend()
5. //是否可以结束操作
6. booleancancellationRequested()
7. //操作执行函数
8. voidaccept()

对于有状态的操作，必须实现begin和end两个方法，因为begin方法会创建一个存放中间结果的容器，accept方法将元素放入该容器，end方法负责对容器中元素处理，比如排序。

面试官：那cancellationRequested方法什么时候用呢?

我：这个方法用于短路操作，比如stream.findAny。

面试官：你刚刚提到短路操作，怎么区分短路操作和非短路操作呢?

我：短路操作和非短路操作都是Stream的结束操作，结束操作是针对中间操作来说的。短路操作是指不用处理全部元素就可以结束，包括下面的方法：

1. anyMatch(),allMatch(),noneMatch(),findFirst(),findAny()

非短路操作是指需要处理所有元素才能结束，包括下面的方法：

1. forEach(),forEachOrdered(),toArray(),reduce(),collect(),max(),min(),count()

总结一下Stream操作，如下图：

在遇到结束操作时，所有Pipeline节点封装的Sink会串成一个链表，如下图：

把Sink串成链表的过程可以参考下面这段源代码：

1. finalSinkwrapSink(Sinksink){
2. Objects.requireNonNull(sink);
3. for(@SuppressWarnings("rawtypes")AbstractPipelinep=AbstractPipeline.this;p.depth>0;p=p.previousStage){
4. sink=p.opWrapSink(p.previousStage.combinedFlags,sink);
5. }
6. return(Sink)sink;
7. }

这样从Head节点开始依次调用每个节点封装的Sink中的begin,accept,cancellationRequested,end 四个方法就可以完成Steam流水线的执行。

面试官：上面提到了Sink会串成一个链，那对于有返回结果的操作，返回的结果是保存在什么地方呢?

我：这里分三种情况：

• 如果返回结果是boolean(比如 anyMatch、allMatch、noneMatch)和Optional(比如 findFirst、findAny)，返回结果存放在对应的Sink。
• collect, reduce等规约操作，返回结果存放在用户指定的容器中，比如如下代码返回结果放在Optional容器中：

1. OptionalaccResult=Stream.of(1,2,3,4,5).reduce((sum,item)->{
2. sum+=item;
3. returnsum;
4. });

max 和 min也是规约操作，因为底层是通过调用 reduce 方法实现的。

• 对于返回是数组的情况，返回数组之前，数据会存放在一种多叉树数据结构中，这种多叉树结构元素存储在树的叶子当中，一个叶子节点可以存放多个元素。

面试官：上面你提到返回数组的时候用到了多叉树的结构，这样做对于Stream处理有什么好处呢?

我：按照官方的说法，这样做是为了避免在并行操作期间不必要地复制数据。

面试官：能简单介绍一下Stream的并行处理吗?

我：Stream的并行处理用到了Fork/Join框架，如下图：

计算过程中，先把任务拆解成子任务，并行计算。计算完成后再把子任务计算结果合并成结果集。

面试官：Fork/Join框架跟普通线程池相比，有什么优势吗?

我：fork/join框架的优势是, 如果某个子任务需要等待另外一个子任务完成才能继续工作，那么处理线程会主动寻找其他未完成的子任务进行执行。跟普通线程池相比，减少了等待时间。

面试官：使用Stream并行流，一定会比串行快吗?

我：这个不一定，使用的时候要考虑以下几个因素：

• 要处理的元素数量，数据越多，性能提升越明显。
• 数据结构的可分割性，数组、ArrayList支持随机读取，可分割性好，HashSet、TreeSet虽然可以分割，但不太容易分割均匀，LinkedList、Streams.iterate、BufferedReader.lines因为长度未知，可分解性差。
• 尽量使用基本类型，避免装箱拆箱。
• 单个子任务花费时间越长，带来的性能提升就会越大。

面试官：据说Stream api跟普通迭代相比有性能损耗，你怎么看?

我：对于简单的处理操作，Stream api性能确实不如普通迭代。但是如果CPU性能好的话，使用Stream并行处理性能会明细提高。对于复杂处理操作，无论并行还是串行，Stream api有明显的优势。

对于并行处理，要考虑CPU的核数。

原文链接：https://mp.weixin.qq.com/s/3SQxIDoe5sy1hw2FGlLjKQ