5

原始数据如下所示：

String data = "{ \"a\":1, \"b\":3 , \"c\":-1 }";

我的第一步是将其转换为 HashMap：

Gson gson = new Gson();
HashMap<String, Double> map = gson.fromJson(data, HashMap.class);

然后按它们的值对键进行排序：

public static List<String> sortHashMap(final HashMap<String, Double> map) {
    Set<String> set = map.keySet();
    List<String> keys = new ArrayList<String>(set);

    Collections.sort(keys, new Comparator<String>() {

        @Override
        public int compare(String s1, String s2) {
            if (map.get(s1) < map.get(s2)) {
                return 1;
            }
            return 0;
        }
    });

    return keys;
}

最后，得到前 N 个键：

keys.subList(0, N);

我终于得到了结果，但我认为这不是一种优雅的方式。

所以我想知道，有什么方便的方法吗？

4

2 回答 2

5

A more elegant and scalable approach would be to use a priority queue where the size is limited to N. Using a min-heap priority queue, we can keep adding entries to the queue till the size reaches N. For each entry after the size of the priority queue has reached N, add it to the queue and then remove the element at the head of the queue (which will have the minimum value). After we have exhausted all the entries from the HashMap, the queue will contain the Top N entries.

The advantage of this approach is that even if the entire HashMap cannot fit in memory, we can break it into smaller blocks and use this approach. Also, if we have a concurrent priority queue we can simultaneously add entries to the queue from different HashMaps as well.

public static List<String> topNKeys(final HashMap<String, Double> map, int n) {
    PriorityQueue<String> topN = new PriorityQueue<String>(n, new Comparator<String>() {
        public int compare(String s1, String s2) {
            return Double.compare(map.get(s1), map.get(s2));
        }
    });

    for(String key:map.keySet()){
        if (topN.size() < n)
            topN.add(key);
        else if (map.get(topN.peek()) < map.get(key)) {
            topN.poll();
            topN.add(key);
        }
    }
    return (List) Arrays.asList(topN.toArray());
}
于 2015-01-10T01:49:33.803 回答
3

你所做的没问题；您将不得不在某个地方编写一个自定义比较器，并且您使用它的地方很好。

但是您的方法中有一个错误compare()：如果 s1 > s2 则返回 0，但仅当数字相等时才应该这样做，如果 s1 > s2 则返回负数。下面的实现纠正了这一点。

一个更好（更简单）的实现是：

 public int compare(String s1, String s2) {
     return Double.compare(map.get(s2), map.get(s1)); //reverse order
 }
于 2013-09-24T02:37:30.770 回答