集合类再探

注：本文使用的pom依赖见文末。

java语言层面支持对实现了Iterable接口的对象使用for-each语句。Iterator可以实现有限流和无限流。

Collection类定义了基本的增删改查操作，转向基本数组类型(toArray)，1.8引入了stream操作。

可变与不可变

不可变集合看似是限制，但是其会极大简化了编程的心理负担。

心理负担举例：

我们使用一个List对象，对其修改的操作必须小心翼翼，因为宽接口的问题，add之类的操作很可能不支持。

stream 操作在其他类库上不一定有效，因为default方法不一定适用于所有子类。

一个集合对象作为方法的入参，有可能被方法修改，而这种修改我们很难轻易地理解，需要阅读代码或者注释。一个方法不能复用常常是因为添加了过多的副作用，而这种副作用暗含其中，为我们的项目添加了一颗颗隐形炸弹。注释的产生只能说明代码设计存在一定的缺陷，优秀的代码应该减少不必要的注释，显然对于副作用，我们必须要显著说明，比如可能抛出的异常。

ImmutableList<String> list = ...

foo(list)

boo(list)

zoo(list)

doSomethingWith(list)

// 如上的几个方法互不影响，可以继续放心地使用 list

// 如果list的类型是List，这几个方法的入参很可能都不一样

guava 和很多其他工具类都是按照这种思想设计的：

// Guava

// builder 模式

ImmutableList<Integer> list = ImmutableList.<Integer>builder()

                .add(1)

                .add(2)

                .addAll(otherList)

                .build();

// 静态工厂

ImmutableList<Integer> list = ImmutableList.of(1, 2, 3);

// shallow copy

ImmutableList<Integer> list = ImmutableList.copyOf(new Integer[]{1, 2, 3});

协变的意思是对象的继承会在集合的维度上传递，不可变类型由于不支持修改，对于协变的支持理所当然。

Java不支持类定义时定义协变，只支持使用集合对象时使用通配符，所以我们能在许多方法上看到泛型通配符。

/ # Guava.ImmutableList

public static <E> ImmutableList<E> copyOf(Collection<? extends E> elements) {

    if (elements instanceof ImmutableCollection) {

      @SuppressWarnings("unchecked") // all supported methods are covariant

      ImmutableList<E> list = ((ImmutableCollection<E>) elements).asList();

      return list.isPartialView() ? ImmutableList.<E>asImmutableList(list.toArray()) : list;

    }

    return construct(elements.toArray());

  }

// elements 入参后，如果不进行修改，可以@SuppressWarnings("unchecked")，直接转换类型为不变，方便后续使用。

// code1

// 请思考这段代码的运行结果

Random random = new Random();

List<Integer> list = random.ints(6L).boxed().collect(Collectors.toList());

System.out.println("list = " + list);

List<Integer> subList = list.subList(0, 3);

System.out.println("subList = " + subList);

Collections.sort(list);

System.out.println("list = " + list);

System.out.println("subList = " + subList);

// 以上代码的运行结果

/**

list = [40, 60, 28, 4, 83, 90]

subList = [40, 60, 28]

list = [4, 28, 40, 60, 83, 90]

Exception in thread "main" java.util.ConcurrentModificationException

**/

// 我们发现：subList这个变量在sort操作之后，不能使用了

// code2

Random random = new Random();

List<Integer> _list = random.ints(6L, 0, 100).boxed().collect(Collectors.toList());

ImmutableList<Integer> list = ImmutableList.copyOf(_list);

System.out.println("list = " + list);

List<Integer> subList = list.subList(0, 3);

System.out.println("subList = " + subList);

Collections.sort(list);

System.out.println("list = " + list);

System.out.println("subList = " + subList);

// 以上代码的运行结果

/**

list = [22, 34, 50, 49, 93, 49]

subList = [22, 34, 50]

Exception in thread "main" java.lang.UnsupportedOperationException

	at com.google.common.collect.ImmutableList.sort(ImmutableList.java:581)

	at java.util.Collections.sort(Collections.java:141)

**/

// 虽然编译通过了，但是 list 禁止了修改，同时由于没有直接调用list.sort()方法，在运行前我们无法获取编译的提示。

// 使用 list.~~sort~~(null); 会得到 IDEA inspection 提示,因为Immutable类的sort标注为了@Deprecate

// code3

Random random = new Random();

List<Integer> _list = random.ints(6L, 0, 100).boxed().collect(Collectors.toList());

ImmutableList<Integer> list = ImmutableList.copyOf(_list);

System.out.println("list = " + list);

List<Integer> subList = list.subList(0, 3);

System.out.println("subList = " + subList);

ImmutableList<Integer> sortedList = list.stream().sorted().collect(ImmutableList.toImmutableList());

System.out.println("list = " + list);

System.out.println("subList = " + subList);

System.out.println("sortedList = " + sortedList);

ImmutableList<Integer> sortedSubList = sortedList.subList(0, 3);

System.out.println("sortedSubList = " + sortedSubList);

// 以上代码的运行结果

/**

list = [53, 7, 69, 5, 23, 7]

subList = [53, 7, 69]

list = [53, 7, 69, 5, 23, 7]

sortedList = [5, 7, 7, 23, 53, 69]

subList = [53, 7, 69]

sortedSubList = [5, 7, 7]

**/

// 可以看出一旦确定list, subList，不管后续进行如何复杂的操作，其值都不变。

// 使用安全的方法，stream(), sorted(), collect()等，可以保证方法无副作用。

// Collections.sort(List<T> list) 方法有副作用

其实 IDEA 已经为我们提供了相关的提示：

我们可以在@Contract注解中看到，入参list被修改了。同时注释里表明了入参、出参、以及可能的异常。Implementation Note 给出了提示。

Collector 接口

// A: 容器, T: 源类型, R: 最终类型（一般为T）

public interface Collector<T, A, R> {

    Supplier<A> supplier();

    BiConsumer<A, T> accumulator();

    BinaryOperator<A> combiner();

    Function<A, R> finisher();

    Set<Characteristics> characteristics();

}

简单来说，Collectors 对集合类型进行了reduce运算，supplier提供容器，accmulater 添加元素到容器，combiner 联结多个容器，也就是说，reduce

可以分组进行运算，每个组为一个容器，然后合并各个容器，·finisher进行最终运算，一般为不可变类型的再封装，比如将 List 封装为 ImmutableList。characteristics 指定了Collector的特性，包括

CONCURRENT, UNORDERED, IDENTITY_FINISH，我们忽略CONCURRENT,因为

多线性编程的复杂性，不推荐使用 Stream 做多线程处理。Stream流处理进行多线程需要调优，默认使用的commonPool，不好控制，commonPool适用于计算密集型任务。
Stream 不适合做精细控制，不好调试。
不要过早调优。绝大部分情况下不要使用多线程。
就算需要使用多线程，还不如直接使用线程安全类，对集合进行迭代处理。
加个parallel 不一定增加性能，最好会编写 Spliterator

Collectors 工具类提供了collector, 常用的有以下一些：

toMap 转换为map
groupingBy 分组，返回结果为Map<K, Collection>
partition 分成两组,返回结果为Map<Boolean, Collection>
toCollection
toList
toSet PS: 如果一个容器可以是集合，那么就应该使用 Set，而不是所有的集合类都用 List 表示。
joining 字符串拼接

一些常用的工具方法如下，通常用来当做中间步骤：

collectingAndThen 添加 finisher，常用来创建ImmutableCollection
mapping(Function mapper, Collector downstream) 实现多层收集，如注解中的示例：

public class MultiLayerStreamDemo {

    public static void main(String[] args) {

        Map<City, Set<String>> lastNamesByCity

                = people.stream().collect(groupingBy(Person::getCity,

                mapping(Person::getLastName, toSet())));

    }

}

其他的方法几乎不用，甚至可以用其他的方法代替：

summarizingInt/Long/Double() 返回统计数据，包括sum，average, max, min；很多工具类可以直接计算，比如Ints
averagingInt 返回平均值，很多工具类就可以完成
maxBy 返回最大值，Stream自己就带有max，min方法
counting 计数，因为 Stream 流只能用一次，所以不常用；不如直接转换为集合再调用size方法。
reduce Stream自己就带有reduce 方法

BUT，标准库的缺陷

虽然我们可以创建List, Map<K, Collection<V>>, Optional<T>（reduce创建）等容器类，但是标准库提供的能力有限。对于不可变类型，我们一般创建为 ImmutableCollection

;对于一些容器，我们可以用更精确的容器类来描述; collect 可以作为不同容器的转换方法：

SpringData

Stream => Streamable(支持Iterator接口)

Guava 类库

List => ImmutableList
Map<K, Collection> => Multimap<K, V>
Map<K, Integer> => Multiset

vavr 类库

List => io.vavr.collection.List(不可变链表)
Map => io.vavr.collection.Map(不可变Map)

public class CountDemo {

    public static void main(String[] args) {

        String[] words = Stream.generate(new Faker().food()::vegetable)

                .limit(100)

                .toArray(String[]::new);

        String s = "Carrot";

        Map<String, Integer> counts = map1(words);

        System.out.println("counts = " + counts);

        System.out.println("counts.get(s) = " + counts.get(s));

        ImmutableMultiset<String> counts2 = map7(Arrays.asList(words));

        System.out.println("counts2 = " + counts2);

        System.out.println("counts2.count(s) = " + counts2.count(s));

    }

    // 1. 使用map基本方法迭代

    @NotNull

    public static Map<String, Integer> map1(String[] words) {

        Map<String, Integer> counts = new HashMap<>();

        for (String word : words) {

            Integer count = counts.get(word);

            if (count == null) {

                counts.put(word, 1);

            } else {

                counts.put(word, count + 1);

            }

        }

        return counts;

    }

    // 2. 使用 merge 方法

    @NotNull

    public static Map<String, Integer> map2(String[] words) {

        Map<String, Integer> counts = new HashMap<>();

        for (String word : words) {

            counts.merge(word, 1, Integer::sum);

        }

        return counts;

    }

    // 3. forEach 迭代，不推荐

    @NotNull

    public static Map<String, Integer> map3(Iterable<String> words) {

        Map<String, Integer> counts = new HashMap<>();

        words.forEach(word ->

                counts.merge(word, 1, Integer::sum)

        );

        return counts;

    }

    // 4. Stream + Collector

    @NotNull

    public static Map<String, Long> map4(Iterable<String> words) {

        return Streamable.of(words).stream()

                .collect(groupingBy(it -> it, counting()));

    }

    // 5. Stream + 自定义 Collector

    @NotNull

    public static ImmutableMap<String, Integer> map5(Iterable<String> words) {

        return Streamable.of(words).stream()

                .collect(toCountMap());

    }

    @NotNull

    public static <T> Collector<T, ?, ImmutableMap<T, Integer>> toCountMap() {

        Collector<T, ?, Map<T, Integer>> countCollector = groupingBy(it -> it, countInt());

        return collectingAndThen(countCollector, ImmutableMap::copyOf);

    }

    @NotNull

    public static <T> Collector<T, ?, Integer> countInt() {

        return Collectors.reducing(0, e -> 1, Integer::sum);

    }

    // 6. Stream + ImmutableMultiset

    @NotNull

    public static ImmutableMultiset<String> map6(Iterable<String> words) {

        return Streamable.of(words).stream()

                .collect(toImmutableMultiset());

    }

    // 7. ImmutableMultiset 直接创建

    @NotNull

    public static ImmutableMultiset<String> map7(Iterable<String> words) {

        return ImmutableMultiset.copyOf(words);

    }

}

由以上实现可以看出，方法1为一般实现，可能出错，推荐使用内部迭代（不自己控制迭代过程），如果有工具类或方法，则不建议自己写（虽然这个例子很简单）

方法2使用了Map::merge方法,这个方法适用于计数和map合并，ConcurrentMap::merge为原子操作

方法3使用了forEach方法，只在生产者-消费者模型、日志打印时推荐使用，遍历Map对象时也可以用

方法4使用标准库的工具方法，缺点是计数类型为Long，不是我们想要的

方法5为自己编写的 Collector,基本思路是分组计数，然后用ImmutableMap包装

7最简单，若在Stream流中进行filter、map、flatMap等运算，可使用方法6

总之，实际应用时建议使用Immutable类型，对于实际问题，应用对应具体的模型，我们使用counts时，面向的是接口Multiset或抽象类ImmutableMultiset，封装了我们需要使用的方法，不易出错。

以下是一个利用collector机制编写的排行榜的简单实现。

public class TopKCollectorDemo {

    public static void main(String[] args) {

        List<Integer> list = new Random().ints(100, 0, 100)

                .boxed().collect(Collectors.toList());

        System.out.println("list = " + list);

        System.out.println("topK(list, 5) = " + topK(list, 5));

    }

    private static class FixSizePQ<E extends Comparable<E>> extends PriorityQueue<E> {

        private final int sz;

        public FixSizePQ(int sz) {

            super(sz);

            assert sz > 0;

            this.sz = sz;

        }

        @Override

        public boolean add(E e) {

            if (size() == sz)

                if (e.compareTo(peek()) > 0) {

                    poll();

                } else {

                    return true;

                }

            return super.add(e);

        }

    }

    @Contract(pure = true)

    public static <T extends Comparable<T>> ImmutableList<T> topK(Iterable<? extends T> iterable, int k) {

        Collector<T, ?, FixSizePQ<T>> tpqCollector = Collector.of(() -> new FixSizePQ<T>(k),

                Collection::add,

                (r1, r2) -> {

                    r1.addAll(r2);

                    return r1;

                },

                Characteristics.UNORDERED);

        return Streams.stream(iterable).collect(

                collectingAndThen(tpqCollector, TopKCollectorDemo::toImmutableList));

    }

    @NotNull

    @Contract(pure = true)

    private static <T extends Comparable<T>> ImmutableList<T> toImmutableList(PriorityQueue<T> pq) {

        List<T> list = new ArrayList<>(pq.size());

        while (!pq.isEmpty()) {

            list.add(pq.poll());

        }

        return ImmutableList.copyOf(list).reverse();

    }

}

外部迭代与内部迭代可以相互转换

同一个任务可能有多种实现，有时A方法好，有时B方法好，有时两者有差不多，多种实现之间可以相互转换。

public class ToMapDemo {

    // 外部迭代

    @NotNull

    public static Map<String, Integer> map2(String[] words) {

        Map<String, Integer> counts = new HashMap<>();

        for (String word : words) {

            counts.merge(word, 1, Integer::sum);

        }

        return counts;

    }

    // IDEA 基于以上方法自动转换成 Stream 运算

    @NotNull

    public static Map<String, Integer> map2_(String[] words) {

        return Arrays.stream(words).collect(toMap(word -> word, word -> 1, Integer::sum));

    }

}

如上例，对于words的迭代有外部迭代和内部迭代两种，外部迭代即我们自己控制迭代过程，这里使用的是 for each 形式，还可以使用 with index 形式；内部迭代由程序自己实现，其迭代过程不受我们直接控制，优点是不易出错。

如果你发现一个Stream流过于复杂，不妨利用IDEA 自动转换为外部迭代方式。

public class ComplicateStreamDemo {

    @Value

    static class User {

        String id;

        String name;

        String mobile;

        public static User generateRandom() {

            Faker faker = new Faker();

            return new User(faker.idNumber().valid(), faker.name().name(), faker.phoneNumber().cellPhone());

        }

    }

    @Value

    static class Pair {

        User a, b;

    }

    public static void main(String[] args) {

        User[] users = Stream.generate(User::generateRandom)

                .limit(5)

                .toArray(User[]::new);

        List<Pair> pairs = f1(users);

        pairs.forEach(System.out::println);

        System.out.println("pairs.size() = " + pairs.size());

    }

    @NotNull

    private static List<Pair> f1(User[] users) {

        return Arrays.stream(users)

                .flatMap(user1 ->

                        Arrays.stream(users)

                                .filter(user2 -> user1 != user2)

                                .map(user2 -> new Pair(user1, user2))

                ).collect(toList());

    }

    @NotNull

    private static List<Pair> getPairs2(User[] users) {

        List<Pair> list = new ArrayList<>();

        for (User user1 : users) {

            for (User user2 : users) {

                if (user1 != user2) {

                    Pair pair = new Pair(user1, user2);

                    list.add(pair);

                }

            }

        }

        return list;

    }

    private static List<Pair> getPairs3(Iterable<User> users1, Iterable<User> users2) {

        return API.For(

                users1,

                users2

        ).yield((a, b) -> a == b ? Option.<Pair>none() : Option.of(new Pair(a, b)))

                .flatMap(it -> it)

                .toJavaList();

    }

}

最开始接触Stream的人会发现f1的可读性没有那么强，其实flatMap可以实现多层for循环以及不同层级的控制（如本例中的filter）。

若将f1转换为f2的话，就一目了然了：方法生成了不同用户间的配对。f1和f2两者属于不同的编程风格，实现了相同的效果。

for comprehension

flatMap 还可以实现将普通方法应用在容器类上实现拆包、枚举、过滤和生成结果序列。若有函数f，其参数均为普通类型，而 for comprehension 可以将包装类的结果取出，应用到函数上。

如 subtract(int a, int b)：

a = Optional(1), b = Optional(2) => result = Optional(-1)
a = Optional(3), b = Optional.empty => result = Optional.empty

上例中的 getPairs3 函数, For comprehension 生成了用户间的组合枚举:

users1: [u1, u2], users2: [u3, u4] => result = [(u1, u3), (u1, u4), (u2, u3), (u2, u4)]
users1: [], users2: [u1, u2] => result = []

java 中不提供 for comprehension 语法糖，我们可以自己实现，不过需要对于每种 monad 单独编写；或者使用现有的集合类vavr。

有时，对于复杂的 flatMap, 不妨直接回归到原来的方法：外部迭代。

public class ForComprehensionDemo {

    @Value

    static class User {

        String id;

        String name;

        String mobile;

        Age age;

        Gender gender;

        public static User generateRandom() {

            Faker faker = new Faker();

            return new User(

                    faker.idNumber().valid(),

                    faker.name().name(),

                    faker.phoneNumber().cellPhone(),

                    rand(Age.class),

                    rand(Gender.class)

            );

        }

    }

    enum Gender {

        MALE, FEMALE;

    }

    enum Age {

        MIDDLE_AGE, YOUNG_ADULT;

    }

    @Value

    static class FindFriendRequest {

        Option<Gender> gender;

        Option<Age> age;

    }

    public static void main(String[] args) {

        FindFriendRequest request = new FindFriendRequest(Option.of(Gender.FEMALE), Option.of(Age.MIDDLE_AGE));

        Option<List<User>> friends = getFriends1(request);

        friends.forEach(list -> list.forEach(System.out::println));

    }

    // vavr 集合库实现

    private static Option<List<User>> getFriends1(FindFriendRequest request) {

        return API.For(

                request.getGender(),

                request.getAge()

        ).yield(ForComprehensionDemo::searchInDb);

    }

    // 使用flatMap实现

    private static Option<List<User>> getFriends2(FindFriendRequest request) {

        Option<Gender> ts1 = request.getGender();

        Option<Age> ts2 = request.getAge();

        BiFunction<Gender, Age, List<User>> f = ForComprehensionDemo::searchInDb;

        return ts1.flatMap(t1 ->

                ts2.map(t2 ->

                        f.apply(t1, t2)

                )

        );

    }

    public static List<User> searchInDb(Gender gender, Age age) {

        return Stream.generate(User::generateRandom)

                .filter(user -> user.gender == gender && user.age == age)

                .limit(3)

                .collect(toList());

    }

    public static <T extends Enum<T>> T rand(Class<T> clazz) {

        T[] values = clazz.getEnumConstants();

        return values[new Random().nextInt(values.length)];

    }

}

jdk8 之后标准库的补充

点评：能新增这些方法，基本上说明这些方法挺有用。可以通过编写工具类或者使用Guava类库等实现相同功能。

List::of 创建不可变集合
List::copyOf 浅拷贝，生成不可变集合
Stream::toList 创建不可变集合
Stream::takeWhile, dropWhile, iterate(seed, predicate, mapper) 更精确的流控制，便于对无限流的过滤
Stream::ofNullable 帮助避免判空。null在代码中就应该少用
Optional::stream 终于提供了 Optional 和 Stream之间的转换，但是 Optional 和 Stream 还是没有实现 Iterable 接口
Optional::or 很有用的方法，可以实现短路运算

	<dependency>

            <groupId>org.projectlombok</groupId>

            <artifactId>lombok</artifactId>

            <version>1.18.24</version>

        </dependency>

        <dependency>

            <groupId>com.github.javafaker</groupId>

            <artifactId>javafaker</artifactId>

            <version>1.0.2</version>

        </dependency>

        <dependency>

            <groupId>io.vavr</groupId>

            <artifactId>vavr</artifactId>

            <version>0.10.4</version>

        </dependency>

        <dependency>

            <groupId>com.google.guava</groupId>

            <artifactId>guava</artifactId>

            <version>31.1-jre</version>

        </dependency>

        <dependency>

            <groupId>org.springframework.data</groupId>

            <artifactId>spring-data-commons</artifactId>

            <version>2.6.10</version>

        </dependency>

巴特西

集合类再探：不可变类的好处，Collector接口详解，使用内部迭代