按值对 Map <Key,Value> 进行排序

我对 Java 比较陌生,经常发现我需要对值排序Map<Key, Value>

由于值不是唯一的,因此我发现自己将keySet转换为array ,并使用自定义比较器 数组进行排序 ,该自定义比较器对与键关联的值进行排序。

有更容易的方法吗?

答案

这是通用的版本:

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

重要的提示:

该代码可以以多种方式破坏。如果您打算使用提供的代码,请务必阅读注释,并注意其中的含义。例如,无法再通过键检索值。 ( 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}

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.comparingByValue(Comparator.reverseOrder()))
       .limit(10)
       .collect(Collectors.toMap(
          Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));

或打印到System.out

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

三个 1 行答案...

我会用Google Collections Guava做到这一点 - 如果您的值Comparable那么您可以使用

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

它将为地图创建一个函数(对象)(将任何键作为输入,返回各自的值),然后对其应用自然的(可比较的)顺序(值)。

如果它们不具有可比性,那么您需要按照以下步骤进行操作

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

这些可以应用于 TreeMap(随着Ordering扩展Comparator ),或应用于某些排序后LinkedHashMap

注意 :如果要使用 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上尝试上面的比较器; 在插入之前没有值的情况下尝试比较插入的键是没有意义的,即,它将很快中断

第一点对我来说有点麻烦了; google collections 非常懒惰(这很好:您可以立即执行几乎所有操作;当您开始使用结果时,实际工作就完成了),这需要复制整个地图!

“完整” 答案 / 按值实时排序的地图

不过不要担心。如果您沉迷于以这种方式对 “实时” 地图进行排序,则可以通过以下类似的疯狂方法来解决上述两个问题之一:

注意:这种情况在 2012 年 6 月发生了重大变化 - 以前的代码永远无法工作:需要内部 HashMap 来查找值,而不在TreeMap.get() -> compare()compare() -> get()之间创建无限循环。 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 进行排序。但在此之前,我们检查哈希图以查看该密钥实际上不是重复项。此外,我们创建的比较器还将包含键,以便重复值不会删除非重复键(由于 == 比较)。这两个项目对于确保遵守地图合同至关重要 。如果您认为自己不想这么做,那么您几乎就要完全反转地图了(到Map<V,K> )。

构造函数需要被称为

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

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

private static <K, V> Map<K, V> sortByValue(Map<K, V> map) {
    List<Entry<K, V>> list = new LinkedList<>(map.entrySet());
    Collections.sort(list, new Comparator<Object>() {
        @SuppressWarnings("unchecked")
        public int compare(Object o1, Object o2) {
            return ((Comparable<V>) ((Map.Entry<K, V>) (o1)).getValue()).compareTo(((Map.Entry<K, V>) (o2)).getValue());
        }
    });

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

    return result;
}

使用 Java 8,您可以使用流 api以明显更少的冗长方式进行操作:

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

对键进行排序要求比较器为每个比较查找每个值。更具可扩展性的解决方案将直接使用 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 可以重新用作返回值;这将需要抑制一些泛型警告,但是对于可重用的库代码可能是值得的。同样,不必在每次调用时都重新分配比较器。

这是一个效率更高的版本,尽管吸引力较小:

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的解决方案。或者,您可以查看 Google Collections 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;
}

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

要使用 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());
}

返回的列表是调用此方法时给定映射的快照,因此两者都不会反映对另一个映射的后续更改。要获得地图的实时迭代视图:

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

每次迭代时,返回的 iterable 都会为给定的映射创建一个新的快照,因此,除非进行并发修改,否则它将始终反映该映射的当前状态。