Java算法优化问询：基于HashMap<List>获取Top10热门邮政编码

现有一个存储邮政编码与对应公司列表的HashMap：

postcodeToCompaniesList = new HashMap<String, List<Company>>();

该Map包含数千个邮政编码条目，每个邮编对应的公司列表至少有1个Company对象。当前需求是获取公司数量最多的前10个热门邮政编码，并按格式 "Postcode SW1A 0AA has 50 companies" 输出。

当前实现通过自定义Record类存储邮编和对应公司数，再用RecordList维护前10条数据，但每次添加元素后都要执行排序操作，效率偏低，希望找到更高效、优雅的实现方式（比如利用Java Stream）。

现有实现代码如下：

自定义Record与RecordList类 #

final class Record implements Comparable<Record> {
    public String postcode;
    public int count;

    public Record(String postcode, int count){
        this.postcode = postcode;
        this.count = count;
    }

    @Override 
    public int compareTo(Record r){
        return Integer.valueOf(this.count).compareTo(Integer.valueOf(r.count));
    }
}

final class RecordList{
    List<Record> top10 = new ArrayList<Record>();
    
    public void addRecord(Record record){
        if (this.top10.size() < 10){
            this.top10.add(record);
            Collections.sort(this.top10);
        } else if (record.count > this.top10.get(0).count){
            this.top10.add(record);
            Collections.sort(this.top10);
            this.top10.remove(0);
        }
    }
}

遍历处理代码 #

RecordList recordList = new RecordList();
Set<String> postcodes = this.postcodeToCompaniesList.keySet();

for(String postcode : postcodes){
  int companyCount = this.postcodeToCompaniesList.get(postcode).size();
  recordList.addRecord(new Record(postcode, companyCount));
}

System.out.println(gson.toJson(recordList));

方案一：Java Stream API（简洁优雅） #

Stream API可以用链式调用完成转换、排序、取前10的操作，代码简洁易读，对于数千条数据的规模，性能完全满足需求：

postcodeToCompaniesList.entrySet()
    // 将Map条目转换为Record对象
    .stream()
    .map(entry -> new Record(entry.getKey(), entry.getValue().size()))
    // 按公司数量降序排序（若数量相同，可追加邮编排序逻辑）
    .sorted((r1, r2) -> Integer.compare(r2.count, r1.count))
    // 取前10个结果
    .limit(10)
    // 按指定格式输出
    .forEach(record -> System.out.printf("Postcode %s has %d companies%n", record.postcode, record.count));

如果不想依赖自定义Record类，可直接使用AbstractMap.SimpleEntry替代，省去类定义的麻烦：

postcodeToCompaniesList.entrySet()
    .stream()
    .map(entry -> new AbstractMap.SimpleEntry<>(entry.getKey(), entry.getValue().size()))
    .sorted((e1, e2) -> Integer.compare(e2.getValue(), e1.getValue()))
    .limit(10)
    .forEach(e -> System.out.printf("Postcode %s has %d companies%n", e.getKey(), e.getValue()));

方案二：优先队列（PriorityQueue）优化性能 #

如果数据量远大于数千条，优先队列（最小堆）可以避免全量排序，仅维护大小为10的堆结构，每次插入/替换操作的时间复杂度为O(log10)，整体效率更高：

// 初始化最小堆：堆顶元素是当前前10中公司数量最少的条目
PriorityQueue<Record> minHeap = new PriorityQueue<>(Comparator.comparingInt(r -> r.count));

for (Map.Entry<String, List<Company>> entry : postcodeToCompaniesList.entrySet()) {
    int companyCount = entry.getValue().size();
    Record record = new Record(entry.getKey(), companyCount);
    
    if (minHeap.size() < 10) {
        minHeap.offer(record);
    } else if (companyCount > minHeap.peek().count) {
        minHeap.poll(); // 移除堆顶的最小元素
        minHeap.offer(record);
    }
}

// 将堆中元素转换为列表并按公司数量降序排序后输出
List<Record> top10Records = new ArrayList<>(minHeap);
top10Records.sort((r1, r2) -> Integer.compare(r2.count, r1.count));
top10Records.forEach(record -> System.out.printf("Postcode %s has %d companies%n", record.postcode, record.count));

原实现效率低的原因 #

原RecordList每次添加元素后都调用Collections.sort(top10)，尽管列表大小最多为10，但数千次循环下来，总开销为O(n * 10 log10)。优先队列方案的总开销为O(n log10)，与原实现开销接近但代码更简洁；Stream方案的全量排序开销为O(n logn)，对于数千条数据来说，实际运行时间差异可忽略，但代码最简洁。

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