java - Java如何根据键值排序Map<Key, Value> ?

  显示原文与译文双语对照的内容

我对Java比较陌生,而且经常发现我需要对值进行排序。 自从值并不是唯一的,我发现自己将 keySetarray, 和排序,数组通过数组排序定制比较类型的键相关联的值。 有没有更简单的方法?

时间:

重要添加注:如果你打算使用提供的代码,一定要阅读注释以及需要注意的影响。 例如值不能再由它们的键检索。 ( get 总是返回 null 。)


看起来比前面所有的更容易。 使用 TreeMap,如下所示:


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

输出:

 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}
 

以下是你可以自由使用的generic-friendly版本:


import java.util.*;

public class MapUtil
{
 public static <K, V extends Comparable<? super V>> Map<K, V> 
 sortByValue( Map<K, V> map )
 {
 List<Map.Entry<K, V>> list =
 new LinkedList<Map.Entry<K, V>>( map.entrySet() );
 Collections.sort( list, new Comparator<Map.Entry<K, V>>()
 {
 public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
 {
 return (o1.getValue()).compareTo( o2.getValue() );
 }
 } );

 Map<K, V> result = new LinkedHashMap<K, V>();
 for (Map.Entry<K, V> entry : list)
 {
 result.put( entry.getKey(), entry.getValue() );
 }
 return result;
 }
}

和一个相关的JUnit4测试,这样你就不必相信我的话:


import java.util.*;
import org.junit.*;

public class MapUtilTest
{
 @Test
 public void testSortByValue()
 {
 Random random = new Random(System.currentTimeMillis());
 Map<String, Integer> testMap = new HashMap<String, Integer>(1000);
 for(int i = 0 ; i <1000 ; ++i) {
 testMap.put("SomeString" + random.nextInt(), random.nextInt());
 }

 testMap = MapUtil.sortByValue( testMap );
 Assert.assertEquals( 1000, testMap.size() );

 Integer previous = null;
 for(Map.Entry<String, Integer> entry : testMap.entrySet()) {
 Assert.assertNotNull( entry.getValue() );
 if (previous!= null) {
 Assert.assertTrue( entry.getValue()> = previous );
 }
 previous = entry.getValue();
 }
 }

}

Java 7版本


public static <K, V extends Comparable<? super V>> Map<K, V> 
 sortByValue( Map<K, V> map )
{
 List<Map.Entry<K, V>> list =
 new LinkedList<>( map.entrySet() );
 Collections.sort( list, new Comparator<Map.Entry<K, V>>()
 {
 @Override
 public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
 {
 return (o1.getValue()).compareTo( o2.getValue() );
 }
 } );

 Map<K, V> result = new LinkedHashMap<>();
 for (Map.Entry<K, V> entry : list)
 {
 result.put( entry.getKey(), entry.getValue() );
 }
 return result;
}

Java 8版本


public static <K, V extends Comparable<? super V>> Map<K, V> 
 sortByValue( Map<K, V> map )
{
 Map<K,V> result = new LinkedHashMap<>();
 Stream <Entry<K,V>> st = map.entrySet().stream();

 st.sorted(Comparator.comparing(e -> e.getValue()))
. forEach(e ->result.put(e.getKey(),e.getValue()));

 return result;
}

三个 1 -line答案。。

我将使用 谷歌收藏集Guava 这样做——如果你的价值观是 Comparable 那么你可以使用


valueComparator = Ordering.natural().onResultOf(Functions.forMap(map))

这将创建一个函数映射 [that takes any of the keys as input, returning the respective value] ( 对象), 然后应用自然( 可以比较的) [the values] 订购。

如果它们是不可比拟的,那么你需要沿着


valueComparator = Ordering.from(comparator).onResultOf(Functions.forMap(map)) 

这些可能是应用于treemap( Ordering 扩展 Comparator 时) 或后 LinkedHashMap排序

NB:如果你要使用treemap,记住,如果比较 == 0,那么项目已经在( 如果有多个值比较相同的) 列表。 为了缓解这个问题,你可以将密钥添加到比较器,如( 假设你的关键字和值是 Comparable ):


valueComparator = Ordering.natural().onResultOf(Functions.forMap(map)).compound(Ordering.natural())

= 将自然顺序应用于键映射的值,并将复合顺序应用于键的自然顺序

请注意,如果你的密钥与 0比较,这将不起作用,但这对于大多数 Comparable 项目( 如 hashCodeequalscompareTo 通常是同步的) 来说应该足够了。

参见 Ordering.onResultOf()Functions.forMap() 。

实现

现在我们已经得到了一个比较器,我们需要得到它的结果。


map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

现在这将很可能工作,但是:

  1. 需要完成一个完整的完成映射
  2. 不要上面的比较器在 TreeMap ;没有必要试图比较一个插入键时没有值,直到把后, 换句话说,, 它将打破非常快

点 1对我来说是一个 deal-breaker ;谷歌收藏非常懒惰( 这很好: 你可以做几乎所有操作在瞬间,真正的工作是当你开始使用结果),这需要复制整个地图!

"完整"答案/按数值排序的实时映射

不要担心,如果你是足够的关注有"实时"地图按照这种方式,可以解决上述问题,不是一个而是 both() 疯狂的事如下:!

注:这在 2012年06月 显著改变了——前面的代码无法工作: 需要一个内部HashMap来查找值,而不在 TreeMap.get() -> compare()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"));
 }
 }

放置时,我们确保哈希映射具有比较器的值,然后放到TreeSet进行排序。 但在这之前,我们检查哈希映射,看看该键是不是一个重复的。 另外,我们创建的比较器也将包含该键,以便重复的值不会删除non-duplicate键( 由于==比较) 。 这些 2项重要确保合同保存地图;如果你认为你不希望,那么你就几乎完全( 到 Map<V,K> ) 换向点的地图。

构造函数需要被调用为


 new ValueComparableMap(Ordering.natural());
//or
 new ValueComparableMap(Ordering.from(comparator));

来自 http://www.programmersheaven.com/download/49349/download.aspx


static Map sortByValue(Map map) {
 List list = new LinkedList(map.entrySet());
 Collections.sort(list, new Comparator() {
 public int compare(Object o1, Object o2) {
 return ((Comparable) ((Map.Entry) (o1)).getValue())
. compareTo(((Map.Entry) (o2)).getValue());
 }
 });

 Map result = new LinkedHashMap();
 for (Iterator it = list.iterator(); it.hasNext();) {
 Map.Entry entry = (Map.Entry)it.next();
 result.put(entry.getKey(), entry.getValue());
 }
 return result;
} 

Java 8提供了一个新的答案: 将条目转换为流,并使用来自 Map.Entry的比较器组合器:


Stream<Map.Entry<K,V>> sorted = map.entrySet().stream()
. sorted(Map.Entry.comparingByValue());

这将使你使用按值升序排序的条目。 如果你想要降低值,只需反转比较器:


Stream<Map.Entry<K,V>> sorted = map.entrySet().stream()
. sorted(Collections.reverseOrder(Map.Entry.comparingByValue()));

如果值不可比,可以通过显式比较器:


Stream<Map.Entry<K,V>> sorted = map.entrySet().stream()
. sorted(Map.Entry.comparingByValue(comparator));

然后,你可以继续使用其他流操作来使用数据。 例如如果你想要在新映射中显示前 10个:


Map<K,V> topTen = map.entrySet().stream()
. sorted(Map.Entry.byKeyComparator().reversed());
. limit(10)
. collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

或者打印到 System.out:


map.entrySet().stream()
. sorted(Map.Entry.comparingByValue())
. forEachOrdered(System.out::println);

排序键需要比较器查找每个比较的每个值。 一个更可以扩展的解决方案将直接使用 entrySet,因为在每次比较( 虽然我没有用数字来备份它) 时,该值都会立即可用。

下面是这种东西的通用版本:


public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue(Map<K, V> map) {
 final int size = map.size();
 final List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>(size);
 list.addAll(map.entrySet());
 final ValueComparator<V> cmp = new ValueComparator<V>();
 Collections.sort(list, cmp);
 final List<K> keys = new ArrayList<K>(size);
 for (int i = 0; i <size; i++) {
 keys.set(i, list.get(i).getKey());
 }
 return keys;
}

private static final class ValueComparator<V extends Comparable<? super V>>
 implements Comparator<Map.Entry<?, V>> {
 public int compare(Map.Entry<?, V> o1, Map.Entry<?, V> o2) {
 return o1.getValue().compareTo(o2.getValue());
 }
}

有一些方法可以减少上述解决方案的内存旋转。 创建的第一个ArrayList可以是re-used作为返回值;这需要抑制一些泛型警告,但它可能值得用于re-usable库代码。 另外,在每次调用时,比较器不必是 re-allocated 。

下面是一个更高效的LESS 版本:


public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue2(Map<K, V> map) {
 final int size = map.size();
 final List reusedList = new ArrayList(size);
 final List<Map.Entry<K, V>> meView = reusedList;
 meView.addAll(map.entrySet());
 Collections.sort(meView, SINGLE);
 final List<K> keyView = reusedList;
 for (int i = 0; i <size; i++) {
 keyView.set(i, meView.get(i).getKey());
 }
 return keyView;
}

private static final Comparator SINGLE = new ValueComparator();

最后,如果你需要连续访问排序信息( 而不仅仅是偶尔对它进行排序),你可以使用额外的多映射。 如果你需要更多细节,请告诉我。。

commons-collections库包含一个名为 TreeBidiMap的解决方案。 或者,你可以看看谷歌的集合 API 。 它有 TreeMultimap,你可以使用。

如果你不想使用这些框架。。 它们带有源代码。

我看了给定的答案,但也有很多人比需要更复杂的或删除地图元素当几个键有相同的值。

下面是一个我认为更好的解决方案:


public static <K, V extends Comparable<V>> Map<K, V> sortByValues(final Map<K, V> map) {
 Comparator<K> valueComparator = new Comparator<K>() {
 public int compare(K k1, K k2) {
 int compare = map.get(k2).compareTo(map.get(k1));
 if (compare == 0) return 1;
 else return compare;
 }
 };
 Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
 sortedByValues.putAll(map);
 return sortedByValues;
}

注意,映射是从最高值排序到最低值。

虽然我同意对映射进行排序可能是一种味道,但我认为下面的代码是不使用不同数据结构的最简单方法。


public class MapUtilities {

public static <K, V extends Comparable<V>> List<Entry<K, V>> sortByValue(Map<K, V> map) {
 List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>(map.entrySet());
 Collections.sort(entries, new ByValue<K, V>());
 return entries;
}

private static class ByValue<K, V extends Comparable<V>> implements Comparator<Entry<K, V>> {
 public int compare(Entry<K, V> o1, Entry<K, V> o2) {
 return o1.getValue().compareTo(o2.getValue());
 }
}

%7D

这是一个embarrassingly不完整的单元测试:


public class MapUtilitiesTest extends TestCase {
public void testSorting() {
 HashMap<String, Integer> map = new HashMap<String, Integer>();
 map.put("One", 1);
 map.put("Two", 2);
 map.put("Three", 3);

 List<Map.Entry<String, Integer>> sorted = MapUtilities.sortByValue(map);
 assertEquals("First","One", sorted.get(0).getKey());
 assertEquals("Second","Two", sorted.get(1).getKey());
 assertEquals("Third","Three", sorted.get(2).getKey());
}

%7D

结果是 Map.Entry 对象的排序列表,从中可以获取键和值。

要使用 Java 8中的新特性完成这里操作:


import static java.util.Map.Entry.comparingByValue;
import static java.util.stream.Collectors.toList;

<K, V> List<Entry<K, V>> sort(Map<K, V> map, Comparator<? super V> comparator) {
 return map.entrySet().stream().sorted(comparingByValue(comparator)).collect(toList());
}

这些条目通过使用给定比较器的值排序。 或者,如果你的值相互比较,则不需要显式比较器:


<K, V extends Comparable<? super V>> List<Entry<K, V>> sort(Map<K, V> map) {
 return map.entrySet().stream().sorted(comparingByValue()).collect(toList());
}

返回的列表是调用这里方法时给定映射的快照,因此两者都不会反映对其他映射的后续更改。 对于该映射的实时iterable视图:


<K, V extends Comparable<? super V>> Iterable<Entry<K, V>> sort(Map<K, V> map) {
 return () -> map.entrySet().stream().sorted(comparingByValue()).iterator();
}

返回的iterable每次迭代时都会创建一个给定映射的新快照,因此,在进行并发修改时,它总是反映映射的当前状态。

...