集合类再探

注：本文使用的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,因为

1. 多线性编程的复杂性，不推荐使用 Stream 做多线程处理。Stream流处理进行多线程需要调优，默认使用的commonPool，不好控制，commonPool适用于计算密集型任务。
2. Stream 不适合做精细控制，不好调试。
3. 不要过早调优。绝大部分情况下不要使用多线程。
4. 就算需要使用多线程，还不如直接使用线程安全类，对集合进行迭代处理。
5. 加个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>