如何用Java 8 Stream将List<Pair<A,B>>合并为List<Pair<A,List<B>>>

当然有更高效的方法！你之前考虑的forEach遍历检查键的方式确实是O(n²)的时间复杂度，而用Stream API的Collectors.groupingBy可以做到O(n)的效率，完美解决你的需求。

核心思路 #

利用groupingBy先按Pair的键（A类型）分组，同时直接收集对应的值（B类型）到列表中，最后把分组后的Map转换回你需要的List<Pair<A, List<B>>>结构。

代码示例 #

假设你使用的Pair类（比如Apache Commons的Pair、JavaFX的Pair或自定义类）提供了getKey()和getValue()方法，代码可以这样写：

import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import org.apache.commons.lang3.tuple.Pair; // 以Apache Commons的Pair为例

// 原始输入列表
List<Pair<A, B>> originalList = ...;

// 转换为目标列表
List<Pair<A, List<B>>> mergedList = originalList.stream()
    // 1. 按键分组，同时收集对应的值到List<B>
    .collect(Collectors.groupingBy(
        Pair::getKey,
        Collectors.mapping(Pair::getValue, Collectors.toList())
    ))
    // 2. 将Map的Entry转换回Pair<A, List<B>>
    .entrySet().stream()
    .map(entry -> Pair.of(entry.getKey(), entry.getValue()))
    .collect(Collectors.toList());

为什么这比forEach高效？ #

groupingBy底层默认使用HashMap来存储分组结果，插入和查找的时间复杂度都是O(1)，整个流程只需要遍历原始列表一次，再遍历分组后的Map一次，总时间复杂度是O(n)，远优于你之前考虑的嵌套遍历O(n²)方案。

自定义Pair类的适配 #

如果是你自己实现的Pair类，只要调整对应的方法引用或lambda表达式即可。比如自定义Pair类有getFirst()和getSecond()方法，代码可以改成：

// 自定义Pair的情况
List<Pair<A, List<B>>> mergedList = originalList.stream()
    .collect(Collectors.groupingBy(
        pair -> pair.getFirst(),
        Collectors.mapping(pair -> pair.getSecond(), Collectors.toList())
    ))
    .entrySet().stream()
    .map(entry -> new Pair<>(entry.getKey(), entry.getValue()))
    .collect(Collectors.toList());

另外要注意：如果原始列表中存在键为null的Pair，groupingBy会把这些条目统一分到null键对应的组中，和HashMap的行为一致。

内容的提问来源于stack exchange，提问作者William Z