java - 从 map 中获取前 5 个值

Question

我有一张这样的 map

Map<String, Integer> map = new HashMap<String, Integer>();

这将填充很多条目，我想做的是制作某种前 5 名的统计数据。

我现在拥有的是

int maxValueInMap=(Collections.max(map.values()));
for (Entry<String, Integer> entry : map.entrySet()) {                       
if (entry.getValue()==maxValueInMap) {
     name = entry.getKey();
}
}

这对于获取 map 中第 1 个最高值的键/值非常有效，但我不知道如何获得前 5 个最高值并具有类似的内容

int maxValueInMap=(Collections.max(map.values()));
for (Entry<String, Integer> entry : map.entrySet()) {                       
if (entry.getValue()==maxValueInMap) {
     name = entry.getKey();
     name2 = entry.getKey(2ndHighest);
     //so on
}
}

非常感谢任何帮助，谢谢。

编辑

我发现这段代码的工作方式就像它想要的那样

public class Main {

public static void main(String[] args) {

    HashMap<String,Integer> map = new HashMap<String,Integer>();
    ValueComparator bvc =  new ValueComparator(map);
    TreeMap<String,Integer> sorted_map = new TreeMap<String,Integer>(bvc);

    map.put("a",10);
    map.put("b",6);
    map.put("c",6);
    map.put("d",56);
    map.put("e",54);
    map.put("f",32);
    map.put("g",1);

    System.out.println("unsorted map: "+map);
    sorted_map.putAll(map);
    System.out.println("results: "+sorted_map);
}
}

class ValueComparator implements Comparator<String> {

Map<String, Integer> base;
public ValueComparator(Map<String, Integer> base) {
    this.base = base;
}

public int compare(String a, String b) {
    if (base.get(a) >= base.get(b)) {
        return -1;
    } else {
        return 1;
    }
}
}

打印出来

unsorted map: {a=10, b=6, c=6, d=56, e=54, f=32, g=1}
results: {d=56, e=54, f=32, a=10, c=6, b=6, g=1}

但是我怎样才能只从sorted_map中获取前5个条目而不是所有条目呢？

Answer 1

执行此操作的简单方法:

• 将 hashmap 的条目集复制到数组
• 对数组进行排序
• 选取前 5 个条目。

但是，排序步骤是O(N log N) ，如果 N 很大并且您需要重复获取前 5 个，那么这将是一个性能 killer ……并且可以更新整数值(例如计数)。

<小时/>

如果您需要更好的性能，则需要更复杂的数据结构，以允许增量更新(以避免重新排序):

• 从字符串到字符串/计数对的 1 对 1 映射
• 按计数排序的字符串/计数对的有序集合

如果您将自己限制为标准集合类，则可以使用以下方法来完成:

• 自定义 Pair类来保存对。
• 一个HashMap<String, Pair>用于前向映射。
• 一个TreeSet<Pair>为了保持配对的顺序。
• 一个(稳定)比较器，主要按计数排序，其次按 Pair 排序。身份。 (后者很重要。比较器不得将 Pair 具有相同计数的对象视为相等，否则 Pair 对象将被错误地视为重复项而消除!)。

您记住的最后一件事是 TreeSet如果您只是更改 count 将不会自动正确更新在 Pair 。相反，您需要:

1. 删除 Pair来自TreeSet
2. 更新count
3. 添加 Pair返回TreeSet .

剩下的就是“只是编程”。 (但是现在对我来说太复杂了，无法编写、编译、测试等:-))

<小时/>

如果您正确执行上述操作，则添加或递增计数应为 O(log N)找到前 5 个条目应该是 O(1) 。但是，由于您使用它来替代具有 O(1) 的解决方案。添加/增量，这只是明显的性能胜利，如果 N很大(足够)，“top 5”是比较常见的操作。

还值得注意的是，您还可以获取顶部 M N 未排序集合中的元素O(N log M) 中的元素。如果M是一个小常数，可减少为 O(N) 。换句话说，它比在顶部简单版本中对条目集进行排序的扩展性更好。 (对于小 N 来说也可能更快。)

<小时/>

回答这个后续问题:

But how would i only get the top 5 from the sorted_map rather than all the entrys??

创建一个迭代器，然后调用 next() 5次!

但我还应该注意，您找到的代码是不正确。我强烈建议您自己编写代码并彻底测试它。 (或者将您的搜索限制在包含不错的单元测试套件的可信库中。)