Sort a Map<Key, Value> by values
I am relatively new to Java, and often find that I need to sort a Map<Key, Value> on the values.
Since the values are not unique, I find myself converting the keySet into an array , and sorting that array through array sort with a custom comparator that sorts on the value associated with the key.
Is there an easier way?
这是一个通用友好的版本：
public class MapUtil {
public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
List<Entry<K, V>> list = new ArrayList<>(map.entrySet());
list.sort(Entry.comparingByValue());
Map<K, V> result = new LinkedHashMap<>();
for (Entry<K, V> entry : list) {
result.put(entry.getKey(), entry.getValue());
}
return result;
}
}
Important note:
This code can break in multiple ways. If you intend to use the code provided, be sure to read the comments as well to be aware of the implications. For example, values can no longer be retrieved by their key. ( get always returns null .)
It seems much easier than all of the foregoing. Use a TreeMap as follows:
public class Testing {
public static void main(String[] args) {
HashMap<String, Double> map = new HashMap<String, Double>();
ValueComparator bvc = new ValueComparator(map);
TreeMap<String, Double> sorted_map = new TreeMap<String, Double>(bvc);
map.put("A", 99.5);
map.put("B", 67.4);
map.put("C", 67.4);
map.put("D", 67.3);
System.out.println("unsorted map: " + map);
sorted_map.putAll(map);
System.out.println("results: " + sorted_map);
}
}
class ValueComparator implements Comparator<String> {
Map<String, Double> base;
public ValueComparator(Map<String, Double> base) {
this.base = base;
}
// Note: this comparator imposes orderings that are inconsistent with
// equals.
public int compare(String a, String b) {
if (base.get(a) >= base.get(b)) {
return -1;
} else {
return 1;
} // returning 0 would merge keys
}
}
Output:
unsorted map: {D=67.3, A=99.5, B=67.4, C=67.4}
results: {D=67.3, B=67.4, C=67.4, A=99.5}
Three 1-line answers...
I would use Google Collections Guava to do this - if your values are Comparable then you can use
valueComparator = Ordering.natural().onResultOf(Functions.forMap(map))
Which will create a function (object) for the map [that takes any of the keys as input, returning the respective value], and then apply natural (comparable) ordering to them [the values].
If they're not comparable, then you'll need to do something along the lines of
valueComparator = Ordering.from(comparator).onResultOf(Functions.forMap(map))
These may be applied to a TreeMap (as Ordering extends Comparator ), or a LinkedHashMap after some sorting
NB: If you are going to use a TreeMap, remember that if a comparison == 0, then the item is already in the list (which will happen if you have multiple values that compare the same). To alleviate this, you could add your key to the comparator like so (presuming that your keys and values are Comparable ):
valueComparator = Ordering.natural().onResultOf(Functions.forMap(map)).compound(Ordering.natural())
= Apply natural ordering to the value mapped by the key, and compound that with the natural ordering of the key
Note that this will still not work if your keys compare to 0, but this should be sufficient for most comparable items (as hashCode , equals and compareTo are often in sync...)
See Ordering.onResultOf() and Functions.forMap().
Implementation
So now that we've got a comparator that does what we want, we need to get a result from it.
map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);
Now this will most likely work work, but:
TreeMap ; there's no point trying to compare an inserted key when it doesn't have a value until after the put, ie, it will break really fast Point 1 is a bit of a deal-breaker for me; google collections is incredibly lazy (which is good: you can do pretty much every operation in an instant; the real work is done when you start using the result), and this requires copying a whole map!
"Full" answer/Live sorted map by values
Don't worry though; if you were obsessed enough with having a "live" map sorted in this manner, you could solve not one but both(!) of the above issues with something crazy like the following:
Note: This has changed significantly in June 2012 - the previous code could never work: an internal HashMap is required to lookup the values without creating an infinite loop between the TreeMap.get() -> compare() and compare() -> get()
import static org.junit.Assert.assertEquals;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import com.google.common.base.Functions;
import com.google.common.collect.Ordering;
class ValueComparableMap<K extends Comparable<K>,V> extends TreeMap<K,V> {
//A map for doing lookups on the keys for comparison so we don't get infinite loops
private final Map<K, V> valueMap;
ValueComparableMap(final Ordering<? super V> partialValueOrdering) {
this(partialValueOrdering, new HashMap<K,V>());
}
private ValueComparableMap(Ordering<? super V> partialValueOrdering,
HashMap<K, V> valueMap) {
super(partialValueOrdering //Apply the value ordering
.onResultOf(Functions.forMap(valueMap)) //On the result of getting the value for the key from the map
.compound(Ordering.natural())); //as well as ensuring that the keys don't get clobbered
this.valueMap = valueMap;
}
public V put(K k, V v) {
if (valueMap.containsKey(k)){
//remove the key in the sorted set before adding the key again
remove(k);
}
valueMap.put(k,v); //To get "real" unsorted values for the comparator
return super.put(k, v); //Put it in value order
}
public static void main(String[] args){
TreeMap<String, Integer> map = new ValueComparableMap<String, Integer>(Ordering.natural());
map.put("a", 5);
map.put("b", 1);
map.put("c", 3);
assertEquals("b",map.firstKey());
assertEquals("a",map.lastKey());
map.put("d",0);
assertEquals("d",map.firstKey());
//ensure it's still a map (by overwriting a key, but with a new value)
map.put("d", 2);
assertEquals("b", map.firstKey());
//Ensure multiple values do not clobber keys
map.put("e", 2);
assertEquals(5, map.size());
assertEquals(2, (int) map.get("e"));
assertEquals(2, (int) map.get("d"));
}
}
When we put, we ensure that the hash map has the value for the comparator, and then put to the TreeSet for sorting. But before that we check the hash map to see that the key is not actually a duplicate. Also, the comparator that we create will also include the key so that duplicate values don't delete the non-duplicate keys (due to == comparison). These 2 items are vital for ensuring the map contract is kept; if you think you don't want that, then you're almost at the point of reversing the map entirely (to Map<V,K> ).
The constructor would need to be called as
new ValueComparableMap(Ordering.natural());
//or
new ValueComparableMap(Ordering.from(comparator));
上一篇: *参数和** kwargs？
下一篇: 按值排序Map <Key，Value>