非Stream API实现分组聚合求最大年龄及复杂度问询

我们有一个存储Person对象的ArrayList，每个Person包含姓名（name）和年龄（age），定义及初始化如下：

class Person {
    String name;
    int age;

    // 补充构造方法以匹配初始化逻辑
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

List<Person> personList = new ArrayList<>();
personList.add(new Person("john", 47));
personList.add(new Person("john", 35));
personList.add(new Person("john", 12));
personList.add(new Person("britney", 27));
personList.add(new Person("britney", 16));

需求是生成一个ArrayList，包含每个姓名对应最大年龄的Person对象，效果等价于SQL语句：

SELECT name, max(AGE) FROM P GROUP BY name

预期结果：

[Person("john", 47), Person("britney", 27)]

已实现的Stream API代码：

personList.stream()
        .collect(Collectors
            .groupingBy(Person::getName,
                    Collectors.maxBy(Comparator.comparing(Person::getAge))))
            .values().stream()
            .map(s -> s.orElseGet(Person::new))
            .collect(Collectors.toList());

现有的非Stream API代码：

Map<String, Integer> personAgg = new HashMap<>();
personList.forEach(personAdd -> {
    var currentKey=personAdd.getName();
    var currentValue=personAdd.getAge();
    if (personAgg.containsKey(currentKey)) {
        if (personAgg.get(currentKey) < currentValue)
            personAgg.put(currentKey, currentValue);
    } else {
        personAgg.put(currentKey, currentValue);
    }
});

List<Person> personAggArray = new ArrayList<>();
personAgg.forEach((k,v) -> personAggArray.add(new Person(k,v)));

问题1：上述非Stream API代码是否为最优方案？若不是，请给出最优实现并说明时间复杂度 #

你的非Stream API实现不算最优，它做了两次独立遍历：第一次遍历personList构建姓名与最大年龄的映射，第二次遍历Map重新创建Person对象生成结果列表，存在冗余的对象创建和遍历开销。

更优实现 #

可以通过一次遍历直接维护姓名->对应最大年龄Person的映射，避免二次遍历和额外对象创建：

Map<String, Person> maxAgePersonMap = new HashMap<>();
for (Person p : personList) {
    String name = p.getName();
    // 利用merge方法自动处理存在/不存在的情况，直接保留年龄更大的Person对象
    maxAgePersonMap.merge(name, p, (existing, newPerson) -> 
        existing.getAge() >= newPerson.getAge() ? existing : newPerson);
}
// 直接将Map的值转为结果列表，无需额外遍历创建对象
List<Person> result = new ArrayList<>(maxAgePersonMap.values());

时间复杂度分析 #

• 遍历personList的时间为O(n)（n为列表元素总数）。
• HashMap的merge操作（包含哈希查找、元素比较、插入/替换）平均时间复杂度为O(1)，最坏情况（哈希冲突严重导致链表退化）为O(k)（k为同一哈希桶的元素数），但实际场景中平均趋近于O(1)。
• 最终将Map值转为List的时间为O(m)（m为不同姓名的数量，m ≤ n）。
• 整体平均时间复杂度为O(n)，最坏情况为O(n + m*k)，通常可认为是O(n)。

问题2：上述Stream API解决方案的时间复杂度是多少？ #

你的Stream API实现平均时间复杂度为O(n)，最坏情况为O(n)（极端哈希冲突场景）：

• groupingBy操作会遍历整个流，时间为O(n)，底层基于HashMap存储分组，平均插入/查找时间为O(1)。
• maxBy收集器在每个分组内比较元素，总比较次数为n - m（m为分组数），这部分时间为O(n)。
• 后续的values().stream().map().collect()操作仅处理分组后的m个元素，时间为O(m)。

整体来看，所有步骤的时间开销线性依赖于原列表的元素总数n，因此平均时间复杂度为O(n)。只有当groupingBy底层使用排序逻辑（JDK默认实现不使用）时，才会出现O(n log n)的情况，但实际场景中不会发生。

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