TreeMap 按值排序

我想编写一个比较器，它可以让我按值对 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传递给比较器吗？

339417 次浏览
小开

这不能通过使用 Comparator来完成，因为它总是要比较地图的 钥匙。TreeMap只能按键排序。

小开

TreeMap是 一直都是按键排序，其他任何东西都是不可能的。Comparator仅仅允许您控制键被排序的 怎么做。

如果需要排序的值，必须将它们提取到 List中并对其进行排序。

小开
最佳答案

您不能让 TreeMap本身对值进行排序，因为这违反了 SortedMap规范:

进一步在其 钥匙上提供 总订货量的 Map。

但是，使用外部集合，您总是可以按照自己的意愿对 Map.entrySet()进行排序，按键、值甚至组合(! !) 两者之间。

下面是一个返回 Map.Entry的 SortedSet的通用方法，给定一个值为 Comparable的 Map:

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"!!!

相关问题

小开

多基因润滑剂的答案是 几乎完美。不过它有一个重要的漏洞。它不会处理值相同的映射条目。

这个密码..。

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”的值: 哦！

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

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;
}
小开

很多人都听说过使用 List 的建议，我也喜欢使用 List

这里有两个方法，您需要根据它们的值对 Map 条目进行排序。

    static final Comparator<Entry<?, Double>> DOUBLE_VALUE_COMPARATOR =
new Comparator<Entry<?, Double>>() {
@Override
public int compare(Entry<?, Double> o1, Entry<?, Double> o2) {
return o1.getValue().compareTo(o2.getValue());
}
};


static final List<Entry<?, Double>> sortHashMapByDoubleValue(HashMap temp)
{
Set<Entry<?, Double>> entryOfMap = temp.entrySet();


List<Entry<?, Double>> entries = new ArrayList<Entry<?, Double>>(entryOfMap);
Collections.sort(entries, DOUBLE_VALUE_COMPARATOR);
return entries;
}
小开

奥洛夫的答案是好的，但它需要 一更多的东西，才是完美的。在他的回答下面的注释中，dacwe (正确地)指出他的实现违反了 Set 的 Compare/Equals 契约。如果您尝试对集合中显然存在的条目调用包含或删除，集合将无法识别它，因为代码允许在集合中放置具有相同值的条目。因此，为了解决这个问题，我们需要测试键之间的相等性:

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;
}

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

由于我们最初忽略了相等性，以便强制集合添加相等值的条目，现在我们必须测试键中的相等性，以便集合实际返回您正在查找的条目。这有点凌乱，而且肯定不是集合原本的用法——但它确实有效。

小开

在 Java 8中:

LinkedHashMap<Integer, String> sortedMap = map.entrySet().stream()
.sorted(Map.Entry.comparingByValue(/* Optional: Comparator.reverseOrder() */))
.collect(Collectors.toMap(Map.Entry::getKey,
Map.Entry::getValue,
(e1, e2) -> e1, LinkedHashMap::new));
小开

我知道这篇文章特别要求按值对 TreeMap 进行排序，但是对于我们这些并不真正关心实现，但是确实想要一个在添加元素时保持集合排序的解决方案的人来说，我希望得到关于这个基于 TreeSet 的解决方案的反馈。首先，元素不容易通过键检索，但是对于我手边的用例(查找具有最低值的 n 个键) ，这不是必需的。

  TreeSet<Map.Entry<Integer, Double>> set = new TreeSet<>(new Comparator<Map.Entry<Integer, Double>>()
{
@Override
public int compare(Map.Entry<Integer, Double> o1, Map.Entry<Integer, Double> o2)
{
int valueComparison = o1.getValue().compareTo(o2.getValue());
return valueComparison == 0 ? o1.getKey().compareTo(o2.getKey()) : valueComparison;
}
});
int key = 5;
double value = 1.0;
set.add(new AbstractMap.SimpleEntry<>(key, value));
小开 
import java.util.*;


public class Main {


public static void main(String[] args) {
TreeMap<String, Integer> initTree = new TreeMap();
initTree.put("D", 0);
initTree.put("C", -3);
initTree.put("A", 43);
initTree.put("B", 32);
System.out.println("Sorted by keys:");
System.out.println(initTree);
List list = new ArrayList(initTree.entrySet());
Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
return e1.getValue().compareTo(e2.getValue());
}
});
System.out.println("Sorted by values:");
System.out.println(list);
}
}
小开 
//convert HashMap into List
List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>(map.entrySet());


Collections.sort(list, (o1, o2) -> o1.getValue().compareTo(o2.getValue()));
小开

如果你想使用哈希映射，你可以在比较器中添加一个条件，首先通过值来检查 & If 值是否相等，对键进行排序

HashMap<String , Integer> polpularity = new HashMap<>();
List<String> collect = popularity.entrySet().stream().sorted((t2, t1) -> {
if (t2.getValue() > t1.getValue()) {
return -1;


} else if (t2.getValue() < t1.getValue()) {
return +1;


} else {
return t2.getKey().compareTo(t1.getKey());
}
}).map(entry -> entry.getKey()).collect(Collectors.toList());

如果你不想处理后一种情况，那么使用 Treemap，它会自动提供排序功能，这可以通过一行优雅的代码来完成:

 TreeMap<String, Integer> popularity = new TreeMap<>();


List<String> collect = popularity.entrySet().stream().sorted(Collections.reverseOrder(Map.Entry.comparingByValue())).map(entry -> entry.getKey()).collect(Collectors.toList());


提交答案