Java TreeMap 按值排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2864840/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
TreeMap sort by value
提问by vito huang
I want to write a comparator that will let me sort a TreeMap by value instead of the default natural ordering.
我想编写一个比较器，让我按值而不是默认的自然顺序对 TreeMap 进行排序。
I tried something like this, but can't find out what went wrong:
我试过这样的事情，但无法找出哪里出了问题：
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;
}
}
}
I guess what am I asking is: Can I get a Map.Entrypassed to the comparator?
我想我要问的是：我可以Map.Entry传递给比较器吗？
采纳答案by polygenelubricants
You can't have the TreeMapitself sort on the values, since that defies the SortedMapspecification:
您不能TreeMap对值进行本身排序，因为这违反了SortedMap规范：
A
Mapthat further provides a total orderingon its keys.
A
Map进一步提供其键的总排序。
However, using an external collection, you can always sort Map.entrySet()however you wish, either by keys, values, or even a combination(!!) of the two.
但是，使用外部集合，您始终Map.entrySet()可以按您希望的方式排序，可以按键、值，甚至是两者的组合（！！）。
Here's a generic method that returns a SortedSetof Map.Entry, given a Mapwhose values are Comparable:
这是一个返回 a SortedSetof的通用方法Map.Entry，给定 a ，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;
}
Now you can do the following:
现在您可以执行以下操作：
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]"
Note that funky stuff will happen if you try to modify either the SortedSetitself, or the Map.Entrywithin, because this is no longer a "view" of the original map like entrySet()is.
请注意，如果您尝试修改其SortedSet本身或Map.Entry内部，则会发生时髦的事情，因为这不再是原始地图的“视图” entrySet()。
Generally speaking, the need to sort a map's entries by its values is atypical.
一般来说，按值对地图条目进行排序的需要是非典型的。
Note on ==for Integer
注意==对于Integer
Your original comparator compares Integerusing ==. This is almost always wrong, since ==with Integeroperands is a reference equality, not value equality.
您的原始比较器Integer使用==. 这几乎总是错的，因为==有Integer操作数是一个参考平等，没有平等的价值。
System.out.println(new Integer(0) == new Integer(0)); // prints "false"!!!
Related questions
相关问题
回答by Joachim Sauer
This can't be done by using a Comparator, as it will always get the keyof the map to compare. TreeMapcan only sort by the key.
这不能通过使用 a 来完成Comparator，因为它总是会获取要比较的地图的键。TreeMap只能按key排序。
回答by Michael Borgwardt
A TreeMapis alwayssorted by the keys, anything else is impossible. A Comparatormerely allows you to control howthe keys are sorted.
一个TreeMap是始终通过关键字排序，别的是不可能的。一个Comparator只允许您控制 如何键进行排序。
If you want the sorted values, you have to extract them into a Listand sort that.
如果您想要排序的值，则必须将它们提取到 a 中List并对其进行排序。
回答by Olof Larsson
polygenelubricants answer is almostperfect. It has one important bug though. It will not handle map entries where the values are the same.
polygenelubricants 的回答几乎是完美的。不过，它有一个重要的错误。它不会处理值相同的地图条目。
This code:...
此代码：...
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());
}
Would output:
会输出：
ape:1
frog:2
pig:3
Note how our cow dissapeared as it shared the value "1" with our ape :O!
注意我们的母牛是如何消失的，因为它与我们的猿共享值“1”：O！
This modification of the code solves that issue:
代码的这种修改解决了这个问题：
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;
}
回答by zina
A lot of people hear adviced to use List and i prefer to use it as well
很多人听到建议使用 List，我也更喜欢使用它
here are two methods you need to sort the entries of the Map according to their values.
这里有两种方法需要根据它们的值对 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;
}
回答by Halogen
Olof's answer is good, but it needs onemore thing before it's perfect. In the comments below his answer, dacwe (correctly) points out that his implementation violates the Compare/Equals contract for Sets. If you try to call contains or remove on an entry that's clearly in the set, the set won't recognize it because of the code that allows entries with equal values to be placed in the set. So, in order to fix this, we need to test for equality between the keys:
Olof 的回答很好，但在它完美之前还需要一件事。在他的回答下面的评论中，dacwe（正确地）指出他的实现违反了集合的比较/相等合同。如果您尝试对明显位于集合中的条目调用 contains 或 remove ，则集合将无法识别它，因为代码允许将具有相等值的条目放置在集合中。因此，为了解决这个问题，我们需要测试键之间的相等性：
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;
}
"Note that the ordering maintained by a sorted set (whether or not an explicit comparator is provided) must be consistent with equals if the sorted set is to correctly implement the Set interface... the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal." (http://docs.oracle.com/javase/6/docs/api/java/util/SortedSet.html)
“请注意，如果排序集要正确实现 Set 接口，则排序集维护的排序（无论是否提供显式比较器）必须与 equals 一致...... Set 接口是根据 equals 操作定义的，但排序集使用它的 compareTo（或比较）方法执行所有元素比较，因此从排序集的角度来看，被该方法视为相等的两个元素是相等的。” ( http://docs.oracle.com/javase/6/docs/api/java/util/SortedSet.html)
Since we originally overlooked equality in order to force the set to add equal valued entries, now we have to test for equality in the keys in order for the set to actually return the entry you're looking for. This is kinda messy and definitely not how sets were intended to be used - but it works.
由于我们最初为了强制集合添加相等值的条目而忽略了相等性，现在我们必须测试键中的相等性，以便集合实际返回您正在寻找的条目。这有点混乱，绝对不是集合的使用方式 - 但它有效。
回答by Vitalii Fedorenko
In Java 8:
在 Java 8 中：
LinkedHashMap<Integer, String> sortedMap =
map.entrySet().stream().
sorted(Entry.comparingByValue()).
collect(Collectors.toMap(Entry::getKey, Entry::getValue,
(e1, e2) -> e1, LinkedHashMap::new));
回答by Paul Hymanson
I know this post specifically asks for sorting a TreeMap by values, but for those of us that don't really care about implementation but do want a solution that keeps the collection sorted as elements are added, I would appreciate feedback on this TreeSet-based solution. For one, elements are not easily retrieved by key, but for the use case I had at hand (finding the n keys with the lowest values), this was not a requirement.
我知道这篇文章特别要求按值对 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));
