集合遍历

有多少人和别人借过钱？

我现在只有10块，都给你吧
走，跟我去银行，只要有，我会都给你

期待哪个答案？

相信大多数人都会选择去银行，这也就是此次分享的主题。分享之前，先来看过去是怎么做的。

Collection

遍历集合

作为Java程序员，集合类肯定不陌生，日常工作比较常用ArrayList、HashSet等。

当遍历集合时，一般会怎么写呢？

遍历数组，通过索引

for(int i=0; i<array.size(); i++) { ... get(i) ... }

遍历链表必须通过while

while((e=e.next())!=null) { ... e.data() ... }

缺点

必须知道集合的内部结构
访问代码和集合是紧耦合
无法复用代码
集合类型改变，相应代码需全部重写

场景1

假设需要计算100以内多少个数是以0结尾，可以使用List或者Iterator。都需要将所有的数字处理一次，才可以得出最终结果。但是，如果需要计算Integer.MAX_VALUE以内或者无穷大的数字呢？

使用Collection方式，首先需要将所有数字都加载进内存，再通过显式遍历，计算所有元素后得出最终结果
使用Iterator方式，将迭代器返回，使用方通过hasNext()方式来判断是否需要执行下一次计算，如果需要执行，通过next()方法获取到下一个元素，计算。

可以看出，首先在内存使用上，Iterator无需知道集合到底有多少个数据，也无需将集合中所有元素都放进集合中才可以返回给使用方，集合的填充和使用可以是异步进行的。

private static final AtomicInteger ATOMIC_INTEGER = new AtomicInteger();    

public static void main(String[] args) {
       while (creator().hasNext()) {
           Integer next = creator().next();
           System.out.println("consumer :" + next);
           if (next % 10 == 0) {
               System.out.println("The Element % 10 = 0 : " + next);
           }
       }

   }

   private static Iterator<Integer> creator() {
       return new Iterator<Integer>() {
           @Override
           public boolean hasNext() {
               return ATOMIC_INTEGER.intValue() < Integer.MAX_VALUE;
           }

           @Override
           public Integer next() {
               System.out.println("producer :" + ATOMIC_INTEGER.get());
               return ATOMIC_INTEGER.incrementAndGet();
           }
       };
   }

问题1：为啥可以返回元素类型是Integer的迭代器呢?

OfDouble、OfInt、OfLong三个接口继承自PrimitiveIterator，它又继承自Iterator。

各自Override了next()。这个接口使用了JDK 1.8的新特性：Consumer，有兴趣的同学可以自己研究。

问题2:那又为啥集合类也可以返回Iterator呢?

层级结构

查看这些常用集合类的源码时，可以看出，都继承自Collection接口，而Collection接口继承自为Iterable。

查看Guava的Iterables帮助文档时，开头第一句话：

Whenever possible, Guava prefers to provide utilities accepting an Iterable rather than a Collection.

为什么呢？

Here at Google, it’s not out of the ordinary to encounter a “collection” that isn’t actually stored in main memory, but is being gathered from a database, or from another data center, and can’t support operations like size() without actually grabbing all of the elements.

谷歌如此大力提倡Iterable，来看一下它的源码，其中包含一个iterator()方法，返回iterator<T>。

问题3:Iterator是什么?

Iterator模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。

方法：next()、hasNext()、remove()

每一个集合返回的Iterator对象都是从头开始的，相互独立的。

也就是说，所有继承自Collection接口的集合类，都可以使用Iterator，那么它是如何遍历的呢？

1
2
3

while(iterator.hasNext()) {
	// do something
}

优点
- 无需关心数据类型
- 无需关心内部结构
  - 不同类型都有相应的Iterator实现类:ArraryIterator、SetIterator、TreeIterator
- 不维护遍历集合的索引
- 代码清爽
- 返回的Iterables的方法返回结果是延迟计算的，并不是把所有数据都加载到内存中
- 短路
  - 拿到当前元素，执行对应操作
  - 判断集合中一部分数据就可以完成操作，不需要计算所有集合数据

场景2

持有一个集合A，要和数据库中的数据B进行对比。

首先以A为基准，B中的数据有两种结果：存在(与A一致、与A不一致)、不存在。再将B中存在，A中不存在的数据标记。

如果直接使用select * from table，并不能确定数据库中究竟有多少数据，是一条还是一百万条。其次，内存可以一次性加载这么多的数据吗？假设都满足，这么大的计算量，会导致服务器资源占用过高，影响其它业务的处理能力。

import java.util.List;

public interface StartLimitQueryTemplate<T> {
    /**
     * 单次分页查询
     *
     * @param start
     * @param limit
     * @return
     */
    List<T> query(int start, int limit);
}

import com.google.common.base.Preconditions;
import com.google.common.collect.AbstractIterator;
import org.apache.commons.collections4.CollectionUtils;
 
import java.util.Iterator;
import java.util.List;

public class Iterables2 {
    public static <T> Iterable<List<T>> split(final StartLimitQueryTemplate<T> template, final int limit) {
        Preconditions.checkNotNull(template);
        Preconditions.checkArgument(limit > 0);
        return () -> new AbstractIterator<List<T>>() {
            int start = 0;
            boolean endFlag = false;
 
            @Override
            protected List<T> computeNext() {
                if (endFlag) {
                    return endOfData();
                }
                List<T> queryResult = template.query(start, limit);
                if (CollectionUtils.isEmpty(queryResult)) {
                    return endOfData();
                }
                if (queryResult.size() < limit) {
                    endFlag = true;
                    return queryResult;
                }
                start = start + limit;
                return queryResult;
            }
        };
    }
 
    public static <T> Iterable<T> flatIterable(final Iterator<? extends Iterable<T>> iterators) {
        return new Iterable<T>() {
            @Override
            public Iterator<T> iterator() {
                return new AbstractIterator<T>() {
                    Iterator<? extends Iterable<T>> outIterable = iterators;
                    Iterator<T> innerIterable = null;
 
                    @Override
                    protected T computeNext() {
                        if (innerIterable == null) {
                            if (!outIterable.hasNext()) {
                                return endOfData();
                            }
                            innerIterable = outIterable.next().iterator();
                        }
                        if (innerIterable.hasNext()) {
                            return iterator().next();
                        }
                        innerIterable = null;
                        return computeNext();
                    }
                };
            }
        };
    }
}

Collection为什么不实现Iterator接口

从Iterator的源码中可以得知，Iterator维护了访问集合时的内部状态，换句话说，依赖于迭代器的当前迭代位置的，如果Collection实现Iterator接口，也就需要集合内维护遍历元素时的指针等信息。当集合在不同方法中被传递时，由于当前迭代位置不可预置，那么next()方法的结果会变成不可预知。除非再为Iterator接口添加一个reset()方法，用来重置当前迭代位置。
但即使这样，Collection也只能同时存在一个当前迭代位置，会有多线程问题。而Iterable则不然，每次调用都会返回一个从头开始计数的迭代器。多个迭代器是互不干扰的。

Abstract

上图中隐藏了一个细节，AbstractList和AbstractSet。

为什么都会有一个以Abstract开头的类呢？

假设开发一个接口，其中有10个方法，那使用方再实现接口的时候需要将10个方法都实现，否则就需要将类声明为abstract。是不是很麻烦！还会想实现它吗！有那功夫都自己写一个了好不好。所以，JDK的开发人员，提供了一系列以Abstrat开头的类，将对应接口的核心功能提供默认实现的版本，目的就是为了如果使用方有定制化的需求时，可以通过继承抽象类以最大程度减少工作量，只需要开发定制化功能。

抽象类的特性

抽象方法可有可无
不能被实例化
子类可以通过继承来使用

抽象类与接口

相同点
- 不能实例化
- 方法可以实现，也可以不实现
  - 接口可以通过 default提供默认实现
不同点
- 字段
  - 抽象类可以定义非static、final 的字段
  - 接口字段默认为public static final
- 方法
  - 抽象类：可以定义public、protected和private的具体方法
  - 接口：只有public
- 子类
  - 可以继承一个类，无论是不是抽象类
  - 可以实现多个接口

使用场景

抽象类
- 希望在几个密切相关的类之间复用代码
- 希望扩展抽象类的类具有许多常用方法或字段，或者需要除公共之外的访问修饰符（例如protected和private）
- 想声明非static、final字段。可以定义访问和修改它们所属对象的状态的方法
接口
- 不相关的类可以实现，例如Compareble、Cloneable和Serializable，被很多类实现
- 希望限定特定数据类型的行为，但不关心谁实现其行为
- 希望利用类型的多重继承

问题4:Java 8接口有default method后是不是可以放弃抽象类了？

Java 8的接口上的default method最初的设计目的是让已经存在的接口可以演化——添加新方法而不需要原本已经存在的实现该接口的类做任何改变（甚至不需要重新编译）就可以使用该新版本的接口。

以Java的 java.util.List接口为例，它在Java SE 7的时候还没有sort()方法，而到Java SE 8的时候添加了这个方法。那么如果我以前在Java SE 7的时候写了个类 MyList 实现了 List 接口，我当时是不需要实现这个 sort() 方法的；当我升级到JDK8的时候，突然发现接口上多了个方法，于是 MyList 类就也得实现这个方法并且重新编译才可以继续使用了，对不对？
所以就有了default method。上述 List.sort() 方法在Java SE 8里就是一个default method，它在接口上提供了默认实现，于是 MyList 即便不提供sort()的实现，也会自动从接口上继承到默认的实现，于是MyList不必重新编译也可以继续在Java SE 8使用。

确实，从Java SE 8的设计主题来看，default method是为了配合JDK标准库的函数式风格而设计的。通过default method，很多JDK里原有的接口都添加了新的可以接收Functional Interface参数的方法，使它们更便于以函数式风格使用

Java 8的接口，即便有了default method，还暂时无法完全替代抽象类。它不能拥有状态，只能提供公有虚方法的默认实现。Java 9的接口已经可以有非公有的静态方法了。未来的Java版本的接口可能会有更强的功能，或许能更大程度地替代原本需要使用抽象类的场景。

函数式编程：无副作用、无状态

提到了Java8，就不得不说跟Iterator有很大相似性的Stream。

Stream

特点

不存储数据
- 流是基于数据源的对象，它本身不存储数据元素，而是通过管道将数据源的元素传递给操作。
函数式编程
- 流的操作不会修改数据源，例如filter不会将数据源中的数据删除。
延迟操作
- 中间操作是延迟执行，只有到终端操作才执行
短路
- 对于无限数量的流，有些操作可以在有限时间完成
  - limit(n)、findFirst()
纯消费
- 流的元素只能访问一次，如果想重新访问流的元素，需要生成一个新的流

与Iterator区别

	Iterator	Stream
迭代方式	外部迭代	内部迭代
使用次数	多次	一次(再次使用会报错：`java.lang.IllegalStateException: stream has already been operated upon or closed`)
执行顺序	元素顺序	串行、并行
性能优化	无	类库

外部迭代：

例如Iterator、for，显示进行迭代操作

元素访问由外部迭代器进行控制

串行，依赖元素存储顺序

无法优化控制流，以达到改善性能的目的

内部迭代：

Collection.forEach、Stream，隐式进行迭代操作

无法获得当前元素下标

只需关心对当前元素的操作(Consumer)

流式处理(类库对其进行性能优化)、代码清晰

使用场景

Stream
- 需要对大数据集的所有元素进行计算
- 不关心怎么做，只关心做什么
  - 希望以这种方式处理每个元素
- 复杂计算代码整洁度、可读性更高(写代码需要注意性能)
Iterator
- 短路操作
- 希望以这种方式处理一个接一个的元素

转换

使用StreamSupport

Iterator<String> sourceIterator = Arrays.asList("A", "B", "C").iterator();
Stream<String> targetStream = StreamSupport.stream(
          Spliterators.spliteratorUnknownSize(sourceIterator, Spliterator.ORDERED),
          false);

使用Iterable

Iterator<String> sourceIterator = Arrays.asList("A", "B", "C").iterator();
Iterable<String> iterable = () -> sourceIterator;
Stream<String> targetStream = StreamSupport.stream(iterable.spliterator(), false);
//()->sourceIterator
//new Iterable<>() { @Override public Iterator<String> iterator() { return sourceIterator; } }

与Collection

	Collections	Stream
侧重点	存储、访问和有效管理	元素计算
是否影响原集合数据	影响	不影响(返回持有结果的新Stream)
执行操作	急性	惰性
元素数量	有限	有限、无限

Debug

Analyze Java Stream operations

贰白

Collection

遍历集合

缺点

场景1

层级结构

场景2

Collection为什么不实现Iterator接口

Abstract

抽象类的特性

抽象类与接口

使用场景

Stream

特点

与Iterator区别

使用场景

转换

与Collection

Debug

参考资料

找啥？