Java中从Map高效获取Top N高值键的策略与实践

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

public class TopNKeysFromMap {

    // 示例Person类，作为Map的键
    static class Person {
        String name;
        public Person(String name) { this.name = name; }

        @Override
        public String toString() { return "Person(" + name + ")"; }

        // 重写equals和hashCode方法，确保Person对象作为Map键的正确性
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return Objects.equals(name, person.name);
        }

        @Override
        public int hashCode() { return Objects.hash(name); }
    }

    /**
     * 使用经典方法从Map中获取Top N高值键
     * @param map 待处理的Map
     * @param n 需要获取的Top N数量
     * @return 包含Top N键的列表
     */
    public static List<Person> getTopNKeysClassic(Map<Person, Integer> map, int n) {
        // 1. 获取Map的entrySet并转换为ArrayList
        List<Map.Entry<Person, Integer>> entries = new ArrayList<>(map.entrySet());

        // 2. 使用Collections.sort和Comparator进行降序排序
        // Comparator.comparing(Map.Entry::getValue) 默认是升序
        // .reversed() 将排序顺序反转为降序
        Collections.sort(entries, Comparator.comparing(Map.Entry::getValue).reversed());

        // 3. 截取前N个元素，并提取键
        // 确保N不超过Map的实际大小，避免IndexOutOfBoundsException
        int limit = Math.min(n, entries.size());
        List<Person> topNPeople = new ArrayList<>();
        for (int i = 0; i < limit; i++) {
            topNPeople.add(entries.get(i).getKey());
        }
        return topNPeople;
    }

    public static void main(String[] args) {
        Map<Person, Integer> scores = new HashMap<>();
        scores.put(new Person("Alice"), 95);
        scores.put(new Person("Bob"), 88);
        scores.put(new Person("Charlie"), 92);
        scores.put(new Person("David"), 78);
        scores.put(new Person("Eve"), 98);
        scores.put(new Person("Frank"), 85);

        // 获取Top 3得分最高的Person
        List<Person> top3People = getTopNKeysClassic(scores, 3);
        System.out.println("经典方法 - Top 3 人员: " + top3People); // 预期：Eve, Alice, Charlie (顺序可能因相同分数而异)

        // 获取Top 5得分最高的Person (Map中只有6个，N=5)
        List<Person> top5People = getTopNKeysClassic(scores, 5);
        System.out.println("经典方法 - Top 5 人员: " + top5People);

        // 获取Top 10得分最高的Person (N > Map.size())
        List<Person> top10People = getTopNKeysClassic(scores, 10);
        System.out.println("经典方法 - Top 10 人员: " + top10People);
    }
}

// ... (在TopNKeysFromMap类中添加此方法)

    /**
     * 使用Java 8 Stream API从Map中获取Top N高值键
     * @param map 待处理的Map
     * @param n 需要获取的Top N数量
     * @return 包含Top N键的列表
     */
    public static List<Person> getTopNKeysStream(Map<Person, Integer> map, int n) {
        return map.entrySet().stream()
                // 1. 按照值降序排序
                .sorted(Map.Entry.<Person, Integer>comparingByValue().reversed())
                // 2. 限制为前N个元素
                .limit(n)
                // 3. 提取键
                .map(Map.Entry::getKey)
                // 4. 收集为List
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        // ... (同上，定义scores Map)

        System.out.println("\n--- Stream API 方法 ---");
        List<Person> top3PeopleStream = getTopNKeysStream(scores, 3);
        System.out.println("Stream API - Top 3 人员: " + top3PeopleStream);

        List<Person> top5PeopleStream = getTopNKeysStream(scores, 5);
        System.out.println("Stream API - Top 5 人员: " + top5PeopleStream);

        List<Person> top10PeopleStream = getTopNKeysStream(scores, 10);
        System.out.println("Stream API - Top 10 人员: " + top10PeopleStream);
    }

// ... (在TopNKeysFromMap类中添加此方法)

    /**
     * 使用PriorityQueue从Map中获取Top N高值键
     * @param map 待处理的Map
     * @param n 需要获取的Top N数量
     * @return 包含Top N键的列表
     */
    public static List<Person> getTopNKeysPriorityQueue(Map<Person, Integer> map, int n) {
        if (n <= 0) {
            return Collections.emptyList();
        }

        // 创建一个大小为N的最小堆，用于存储Map.Entry
        // 比较器按照值（Integer）升序排列，确保堆顶是最小值
        PriorityQueue<Map.Entry<Person, Integer>> minHeap = new PriorityQueue<>(
                Comparator.comparing(Map.Entry::getValue)
        );

        for (Map.Entry<Person, Integer> entry : map.entrySet()) {
            if (minHeap.size() < n) {
                minHeap.offer(entry); // 如果堆未满，直接加入
            } else if (entry.getValue() > minHeap.peek().getValue()) {
                // 如果当前值大于堆顶（当前Top N中最小的值），则移除堆顶，加入当前值
                minHeap.poll();
                minHeap.offer(entry);
            }
        }

        // 将堆中的元素提取出来。因为是最小堆，所以提取出来的顺序是升序的，需要反转
        List<Person> topNKeys = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            topNKeys.add(minHeap.poll().getKey());
        }
        Collections.reverse(topNKeys); // 反转列表以获得降序结果

        return topNKeys;
    }

    public static void main(String[] args) {
        // ... (同上，定义scores Map)

        System.out.println("\n--- PriorityQueue 方法 ---");
        List<Person> top3PeoplePQ = getTopNKeysPriorityQueue(scores, 3);
        System.out.println("PriorityQueue - Top 3 人员: " + top3PeoplePQ);

        List<Person> top5PeoplePQ = getTopNKeysPriorityQueue(scores, 5);
        System.out.println("PriorityQueue - Top 5 人员: " + top5PeoplePQ);

        List<Person> top10PeoplePQ = getTopNKeysPriorityQueue(scores, 10);
        System.out.println("PriorityQueue - Top 10 人员: " + top10PeoplePQ);
    }