TreeMap按值排序

Question

我想写一个比较器,让我按值而不是默认的自然顺序对TreeMap进行排序.

我试过这样的东西,却找不到出了什么问题:

import java.util.*;

class treeMap {
    public static void main(String[] args) {
        System.out.println("the main");
        byValue cmp = new byValue();
        Map<String, Integer> map = new TreeMap<String, Integer>(cmp);
        map.put("de",10);
        map.put("ab", 20);
        map.put("a",5);

        for (Map.Entry<String,Integer> pair: map.entrySet()) {
            System.out.println(pair.getKey()+":"+pair.getValue());
        }
    }
}

class byValue implements Comparator<Map.Entry<String,Integer>> {
    public int compare(Map.Entry<String,Integer> e1, Map.Entry<String,Integer> e2) {
        if (e1.getValue() < e2.getValue()){
            return 1;
        } else if (e1.getValue() == e2.getValue()) {
            return 0;
        } else {
            return -1;
        }
    }
}

我想我要问的是:我可以Map.Entry传递给比较器吗？

Answer 1

您无法TreeMap对值进行排序,因为这违反了SortedMap规范:

A Map进一步提供其键的总排序.

但是,使用外部集合,您可以随时Map.entrySet()按键,值,甚至两者的组合(!!)进行排序.

这是一个返回a SortedSet的泛型方法Map.Entry,给定Map的值为Comparable:

static <K,V extends Comparable<? super V>>
SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
    SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
        new Comparator<Map.Entry<K,V>>() {
            @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
                int res = e1.getValue().compareTo(e2.getValue());
                return res != 0 ? res : 1;
            }
        }
    );
    sortedEntries.addAll(map.entrySet());
    return sortedEntries;
}

现在您可以执行以下操作:

    Map<String,Integer> map = new TreeMap<String,Integer>();
    map.put("A", 3);
    map.put("B", 2);
    map.put("C", 1);   

    System.out.println(map);
    // prints "{A=3, B=2, C=1}"
    System.out.println(entriesSortedByValues(map));
    // prints "[C=1, B=2, A=3]"

请注意,如果您尝试修改SortedSet自身或Map.Entry内部,则会发生时髦的事情,因为这不再是原始地图的"视图",就像entrySet()是.

一般来说,需要按照其值对地图的条目进行排序是非典型的.

注意上==了Integer

您的原始比较器Integer使用比较==.这几乎总是错的,因为==有Integer操作数是一个参考平等,不珍惜平等.

    System.out.println(new Integer(0) == new Integer(0)); // prints "false"!!!

相关问题

• 在Java中比较两个整数时会发生自动拆箱吗？(没有!!!)
• 是否保证new Integer(i) == i在Java中？(是!!!)

Answer 2

polygenelubricants答案几乎是完美的.它有一个重要的错误.它不会处理值相同的映射条目.

这段代码:......

Map<String, Integer> nonSortedMap = new HashMap<String, Integer>();
nonSortedMap.put("ape", 1);
nonSortedMap.put("pig", 3);
nonSortedMap.put("cow", 1);
nonSortedMap.put("frog", 2);

for (Entry<String, Integer> entry  : entriesSortedByValues(nonSortedMap)) {
    System.out.println(entry.getKey()+":"+entry.getValue());
}

输出:

ape:1
frog:2
pig:3

注意我们的牛如何消失,因为它与我们的猿共享价值"1":O!

代码的这种修改解决了这个问题:

static <K,V extends Comparable<? super V>> SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
        SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
            new Comparator<Map.Entry<K,V>>() {
                @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
                    int res = e1.getValue().compareTo(e2.getValue());
                    return res != 0 ? res : 1; // Special fix to preserve items with equal values
                }
            }
        );
        sortedEntries.addAll(map.entrySet());
        return sortedEntries;
    }

Answer 3

在Java 8中:

LinkedHashMap<Integer, String> sortedMap = 
    map.entrySet().stream().
    sorted(Entry.comparingByValue()).
    collect(Collectors.toMap(Entry::getKey, Entry::getValue,
                             (e1, e2) -> e1, LinkedHashMap::new));

Answer 4

一个TreeMap是始终通过关键字排序,别的是不可能的.一个Comparator只允许您控制 如何键进行排序.

如果您想要排序的值,您必须将它们提取到a List并对其进行排序.

Answer 5

这不能通过使用a来完成Comparator,因为它总是会得到要比较的地图的关键字.TreeMap只能按键排序.

Answer 6

奥洛夫的答案很好,但在它完美之前还需要一件事.在他的回答下面的评论中,dacwe(正确地)指出他的实施违反了套装的比较/等于合同.如果您尝试在明确在集合中的条目上调用包含或删除,则集合将无法识别它,因为允许具有相等值的条目的代码放在集合中.所以,为了解决这个问题,我们需要测试密钥之间的相等性:

static <K,V extends Comparable<? super V>> SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
    SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
        new Comparator<Map.Entry<K,V>>() {
            @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
                int res = e1.getValue().compareTo(e2.getValue());
                if (e1.getKey().equals(e2.getKey())) {
                    return res; // Code will now handle equality properly
                } else {
                    return res != 0 ? res : 1; // While still adding all entries
                }
            }
        }
    );
    sortedEntries.addAll(map.entrySet());
    return sortedEntries;
}

"请注意,排序集维护的排序(无论是否提供显式比较器)必须与equals一致,如果排序集要正确实现Set接口... Set接口是根据equals操作定义的但是,有序集使用compareTo(或compare)方法执行所有元素比较,因此从排序集的角度来看,这种方法认为相等的两个元素是相等的.(http://docs.oracle.com/javase/6/docs/api/java/util/SortedSet.html)

由于我们最初忽略了相等性以强制集合添加等值条目,现在我们必须测试密钥中的相等性,以便集合实际返回您正在寻找的条目.这有点混乱,绝对不是如何使用集合 - 但它的工作原理.