java - 如何从 HashMap 中获取 5 个最高值？

Question

我有一个 HashMap ，它链接存储为键的邮政编码和存储为 HashMap 中值的人口。

HashMap 包含大约 33k 个条目。

我试图从 5 个邮政编码中获取 5 个最高人口值，并打印出与 5 个最高人口相关联的 5 个邮政编码，但我无法理解如何执行此操作的算法。

如果只有一个，那很容易，但是 5 个限制给我带来了一些麻烦。

我知道将 5 个值存储在一个 int 数组中，并且我有一个计数器来确定何时存储其中的 5 个值，仅此而已。

谢谢

    int populatedCounter = 0;

    int[] populatedZip = new int[5];

    it = zipCodePop.entrySet().iterator();
    while (it.hasNext())
    {
        Map.Entry pairs = (Map.Entry)it.next();

        for (int i = 0; i < populatedZip.length; i++)
        {

        }
    }

}

Answer 1

将这样一个集合的条目放入列表中并对其进行排序是一种选择。但是 33k 元素是一个数字，其中 O(n*log(n)) 的排序复杂性可能已经对性能产生了明显的影响。

一个方法是使用 nr4bt 已经提到的 PriorityQueue(他回答时我写了这个片段)。它基本上将所有元素插入到根据映射条目的值排序的 PriorityQueue 中。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;

public class GreatestOfMap
{
    public static void main(String[] args)
    {
        Map<String, Integer> map = new HashMap<String, Integer>();

        map.put("zip000", 1234);
        map.put("zip001", 2345);
        map.put("zip002", 3456);
        map.put("zip003", 4567);
        map.put("zip004", 5678);
        map.put("zip005", 6789);
        map.put("zip006", 123);
        map.put("zip007", 234);
        map.put("zip008", 456);
        map.put("zip009", 567);
        map.put("zip010", 7890);
        map.put("zip011", 678);
        map.put("zip012", 789);
        map.put("zip013", 890);

        int n = 5;
        List<Entry<String, Integer>> greatest = findGreatest(map, 5);
        System.out.println("Top "+n+" entries:");
        for (Entry<String, Integer> entry : greatest)
        {
            System.out.println(entry);
        }
    }

    private static <K, V extends Comparable<? super V>> List<Entry<K, V>> 
        findGreatest(Map<K, V> map, int n)
    {
        Comparator<? super Entry<K, V>> comparator = 
            new Comparator<Entry<K, V>>()
        {
            @Override
            public int compare(Entry<K, V> e0, Entry<K, V> e1)
            {
                V v0 = e0.getValue();
                V v1 = e1.getValue();
                return v0.compareTo(v1);
            }
        };
        PriorityQueue<Entry<K, V>> highest = 
            new PriorityQueue<Entry<K,V>>(n, comparator);
        for (Entry<K, V> entry : map.entrySet())
        {
            highest.offer(entry);
            while (highest.size() > n)
            {
                highest.poll();
            }
        }

        List<Entry<K, V>> result = new ArrayList<Map.Entry<K,V>>();
        while (highest.size() > 0)
        {
            result.add(highest.poll());
        }
        return result;
    }
}