基于值和键对HashMap进行排序？

Question

可能重复：
{{link1：如何在Java中按值对Map 进行排序？}}

我有一个HashMap，类型为：

HashMap<String, Integer> h = new HashMap<String, Integer>();

HashMap 包含字符串列表，整数是该字符串出现次数的计数器。我想要做的是根据整数对 HashMap 进行排序，然后按照字符串的字母顺序排序。

目前，我正在记录单词的最大出现次数（变量名为 max），并按以下方式显示值：

public void print(){
    while(max > 0){
       for (String key : h.keySet()){
           if(h.get(key) == max){
               System.out.println(key + " " + h.get(key));
           }
       }
       max--;
    }
}

这种方法不按字母顺序对值进行排序，而且每次访问HashMap都会访问max*h(size)次。

有更好的解决方案吗？

- neut

---

@krock 不错的发现。是的，完全相同的问题。 - cletus

Answer 1

这里有一个使用Comparator对具有Comparable键和值的Map.Entry对象进行排序的方法：

public class ValueThenKeyComparator<K extends Comparable<? super K>,
                                    V extends Comparable<? super V>>
    implements Comparator<Map.Entry<K, V>> {

    public int compare(Map.Entry<K, V> a, Map.Entry<K, V> b) {
        int cmp1 = a.getValue().compareTo(b.getValue());
        if (cmp1 != 0) {
            return cmp1;
        } else {
            return a.getKey().compareTo(b.getKey());
        }
    }

}

您可以将所有的映射条目放入一个列表中，然后对该列表进行排序：

List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(h.entrySet());
Collections.sort(list, new ValueThenKeyComparator<String, Integer>());

- Sean

---

几乎是这样，我猜是因为这样出现次数较少的单词会先出现。 - Enno Shioji

Answer 2

看看Google Guava libraries，它有一个Multiset可以为您进行计算，然后您可以使用Ordering类简化排序。

您需要做的就是用您的字符串填充Multiset。 它会为您维护频率。 然后您可以使用Ordering对这些字符串进行排序。

- Aravind Yarram

Answer 3

也许不是最优雅的解决方案，但这个怎么样？

//TreeSet with reversed natural ordering (big integers first)
Map<Integer, Set<String>> h = 
     new TreeMap<Integer, Set<String>>(Collections.reverseOrder());
//and use TreeSet for the set...
// ...    
// 
for(Map.Entry<Integer,Set<String>> entry : h.entrySet()){
    for(String str : entry.getValue()){
        System.out.println(str + " has occured " + entry.getKey() + " times.");
    }
}

- Enno Shioji

---

"-1 * o1.compareTo(o2)" 是有缺陷的。考虑一下 compareTo 返回 Integer.MIN_VALUE 的情况。 - Stephen C

其实我不应该自己编写反转自然顺序的代码 :P 应该使用 Collections.reverseOrder() 方法进行替换。 - Enno Shioji

Answer 4

你可以使用SortedMap接口来对HashMap进行排序。这非常容易 - 自动排序。请参考http://java.sun.com/j2se/1.4.2/docs/api/java/util/SortedMap.html。我在这里没有包含任何代码，但如果需要，只需添加一条评论。我会给你一个示例代码。

- Shamal Karunarathne

---

-1，SortedMap按键排序，而不是按值排序。 - whiskeysierra

一个进一步保证其键按升序排序的映射，根据其键的自然顺序（请参见Comparable接口）或在创建排序映射时提供的比较器进行排序。 - Vishal