如何优雅地从Map<Person, Integer>中获取值最高的前N个Person列表？

针对Map<Person, Integer>取值最高的前N个Person的需求，推荐两种场景化的优雅实现，比全量排序的TreeMap方案更高效或更简洁：

一、大数据量最优：基于最小堆的实现 #

当Map元素数量很大时，全量排序会带来不必要的性能开销，用**最小堆（PriorityQueue）**只维护当前最大的N个元素，时间复杂度为O(M log N)（M为Map元素总数），远优于全量排序的O(M log M)。

代码示例：

import java.util.*;
import java.util.Map.Entry;

public class TopNExample {
    public static List<Person> getTopNPeople(Map<Person, Integer> personMap, int n) {
        // 初始化最小堆，按value升序排序，堆顶是当前堆中最小的元素
        PriorityQueue<Entry<Person, Integer>> minHeap = new PriorityQueue<>(
            Comparator.comparingInt(Entry::getValue)
        );

        for (Entry<Person, Integer> entry : personMap.entrySet()) {
            minHeap.offer(entry);
            // 堆大小超过N时，移除最小的元素，始终保留最大的N个
            if (minHeap.size() > n) {
                minHeap.poll();
            }
        }

        // 堆中元素是从小到大排列，反转后得到从大到小的前N个Person
        List<Person> topN = new ArrayList<>(n);
        while (!minHeap.isEmpty()) {
            topN.add(minHeap.poll().getKey());
        }
        Collections.reverse(topN);
        return topN;
    }
}

补充说明 #

• 若存在多个Person的value相同，可在Comparator中追加Person的唯一属性（如id）来保证排序稳定性：

  PriorityQueue<Entry<Person, Integer>> minHeap = new PriorityQueue<>(
      Comparator.comparingInt(Entry::getValue)
                .thenComparing(entry -> entry.getKey().getId())
  );
  

二、小数据量最简洁：Java 8 Stream实现 #

如果Map元素数量不多，用Stream的链式调用写法最简洁，代码可读性极高：

import java.util.*;
import java.util.stream.Collectors;

public class TopNExample {
    public static List<Person> getTopNPeopleWithStream(Map<Person, Integer> personMap, int n) {
        return personMap.entrySet().stream()
            // 按value降序排序
            .sorted(Entry.comparingByValue(Comparator.reverseOrder()))
            // 取前N个元素
            .limit(n)
            // 提取Person对象
            .map(Entry::getKey)
            // 转为List
            .collect(Collectors.toList());
    }
}

为什么不推荐TreeMap？ #

TreeMap会将所有元素按key排序（若要按value排序还需要额外处理，比如把entry存入TreeMap并自定义Comparator），本质是全量排序，无论你是否只需要前N个，都会对所有元素进行排序，性能远不如最小堆方案；而且TreeMap需要维护红黑树结构，插入时的开销也比堆更高。

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