Java 如何从哈希图中获得 5 个最高值？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21465821/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to get 5 highest values from a hashmap?
提问by Pangu
I have a Hashmap that links a zipcodes stored as keys and population stored as values in a hashmap.
我有一个 Hashmap，它链接作为键存储的邮政编码和作为值存储在哈希图中的人口。
The hashmap contains around 33k entries.
哈希图包含大约 33k 个条目。
I'm trying to get the 5 highest population values from 5 zip codes and print out the 5 zip codes ASSOCIATED with the 5 highest population, but I'm having trouble understanding the algorithm of how to do it.
我试图从 5 个邮政编码中获取 5 个最高人口值并打印出与 5 个最高人口相关联的 5 个邮政编码，但我无法理解如何执行此操作的算法。
If it was just one, its easy but the 5 restriction is giving me some trouble.
如果它只是一个，那很容易，但是 5 个限制给我带来了一些麻烦。
I know to store the 5 values in an int array and I have a counter to determine when 5 of them are stored, but thats it.
我知道将 5 个值存储在一个 int 数组中，并且我有一个计数器来确定何时存储其中 5 个值，但仅此而已。
Thanks
谢谢
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++)
{
}
}
}
采纳答案by Marco13
Putting the entries of such a set into a list and sorting it is one option. But 33k elements is a number where the O(n*log(n)) complexity of sorting might already have a noticable performance impact.
将此类集合的条目放入列表并对其进行排序是一种选择。但是 33k 元素是一个数字，其中 O(n*log(n)) 排序的复杂性可能已经对性能产生了显着影响。
One apporach would be to employ the PriorityQueue that nr4bt already mentioned (I wrote this snippet while he answered). It basically inserts all elements into a PriorityQueue that is sorted according to the values of the map entries.
一种方法是使用 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;
}
}
回答by Kevin Workman
How would you do this without a computer, with just a piece of paper and a pencil? Pretend you had a stack of index cards that had numbers on them, and it was your job to find the 5 highest numbers. How would you do that? Write down steps that somebody else could follow to achieve the goal, and when you have those steps written out, you'll have an algorithm that you can start thinking about implementing with code.
如果没有电脑，只有一张纸和一支铅笔，你会怎么做？假设你有一叠上面有数字的索引卡，你的工作是找到 5 个最大的数字。你会怎么做？写下其他人可以遵循的步骤来实现目标，当你写出这些步骤时，你就会有一个算法，你可以开始考虑用代码来实现。
You say that a single maximum is easy, so do it exactly like you would with a single maximum, but keep track of the five maximums instead. An array of maximums might be helpful here.
您说单个最大值很容易，因此与使用单个最大值完全一样，但要跟踪五个最大值。一组最大值在这里可能会有所帮助。
回答by óscar López
Try this, using standard methods and assuming that the population count is stored as Integers in the HashMap:
试试这个，使用标准方法并假设人口计数在Integers 中存储为s HashMap：
List<Integer> list = new ArrayList<Integer>(zipCodePop.values());
Collections.sort(list, Collections.reverseOrder());
List<Integer> top5 = list.subList(0, 5);
回答by Orhan Obut
PriorityQueuewould help too, and also a nice topic about how to get top k from a list, you can check this link
PriorityQueue也有帮助，也是一个关于如何从列表中获取前 k 个的不错的主题，您可以查看此链接
PriorityQueue<Integer> p = new PriorityQueue<Integer>(5);
int[] a = new int[]{3,5,10,1,23,42,66,1333,545,110};
for (int i : a){
p.add(i);
if (p.size() > 5){
p.poll();
}
}
//output will be highest 5, [42, 66, 110, 1333, 545]
You can have O(n log(k))time complexity // k is your top value count.
您可以拥有O(n log(k))时间复杂度 // k 是您的最高值计数。
回答by Dharma
public class CheckHighiestValue { public static void main(String... s) {
公共类 CheckHighiestValue { public static void main(String... s) {
HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("first", 10000);
map.put("second", 20000);
map.put("third", 300);
map.put("fourth", 800012);
map.put("fifth", 5000);
map.put("sixth", 30012);
map.put("seventh", 1234);
map.put("eighth", 45321);
map.put("nineth", 5678);
Set<Entry<String, Integer>> set = map.entrySet();
List<Entry<String, Integer>> list = new ArrayList<Entry<String, Integer>>(
set);
Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Entry<String, Integer> o1,
Entry<String, Integer> o2) {
return o2.getValue().compareTo(o1.getValue());
}
});
System.out.println(list.subList(0, 5));
}
}
}
回答by Manolis
This is something i made and hopefully provides you something that you want to use.
这是我制作的东西，希望为您提供您想要使用的东西。
public class TopsCollection {
private static Map<String, Integer> collectors = new HashMap<>();
public TopsCollection() {
}
public void add(String playerName, int score) {
collectors.put(playerName, score);
}
public void clearCollectors() {
synchronized (collectors) {
collectors.clear();
}
}
public List<Map.Entry<String, Integer>> getTops() {
return collectors.entrySet().stream().sorted(comparing(Map.Entry::getValue, reverseOrder())).limit(5).collect(toList());
}
public int getTopByName(String name) {
for (int i = 0; i < getTops().size(); i++) {
if (getTops().get(i).getKey().contains(name)) {
return i;
}
}
return 0;
}
getTopByName allows you to get the top place of the specified name.
getTopByName 允许您获取指定名称的顶部位置。
