题 按值对地图<键,值>进行排序


我是Java的新手,经常发现我需要对它进行排序 Map<Key, Value> 关于价值观。

由于价值不是唯一的,我发现自己转换了 keySet 变成一个 array,并通过排序该数组 数组排序 用一个 定制比较器 对与键关联的值进行排序。

有更容易的方法吗?


1379


起源


地图不是要排序,而是快速访问。对象相等的值会破坏地图的约束。使用条目集,如 List<Map.Entry<...>> list =new LinkedList(map.entrySet()) 和 Collections.sort .... 那样。 - Hannes
当我们尝试在Java中使用Counter(Map <Object,Integer>)时可能出现这种情况。然后,按出现次数排序将是常见操作。像Python这样的语言有一个内置的Counter数据结构。对于Java中的替代实现方式, 这里 就是一个例子 - demongolem
有很多用于排序映射的用例,这就是为什么你在jdk中有TreeMap和ConcurrentSkipListMap的原因。 - alobodzk


答案:


这是一个通用友好版本:

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

783



很高兴这有帮助。 John,LinkedHashMap对解决方案非常重要,因为它提供了可预测的迭代顺序。 - Carter Page
@ buzz3791是的。任何排序算法都会出现这种情况。在排序期间更改结构中节点的值会创建不可预测(并且几乎总是坏)的结果。 - Carter Page
@Sheagorath我在Android中尝试过它也有效。考虑到您使用的是Java 6版本,它不是特定于平台的问题。你实施了吗? 可比 正确地在你的价值对象? - saiyancoder
不应该使用Java 8版本 forEachOrdered 代替 forEach,自从博士 forEach 陈述:“这种行为的行为明确是不确定的。”? - rob
完全撕掉了这个,但在评论中记录了@CarterPage(无论如何它都将在一个开源项目中)。非常感谢。 - Nathan Beach


重要的提示:

此代码可以以多种方式中断。 如果您打算使用提供的代码,请务必阅读注释以了解其含义。例如,不能再通过其密钥检索值。 (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}

405



不再 (stackoverflow.com/questions/109383/...)。另外,为什么有演员要Double?不应该只是 return ((Comparable)base.get(a).compareTo(((Comparable)base.get(b)))? - Stephen
@Stephen:不。在这种情况下,所有等于值的键都被删除(等于和比较之间的差异)。另外:即使这段代码也存在以下序列的问题 map.put("A","1d");map.put("B","1d");map.put("C",67d);map.put("D",99.5d); - steffen
用于树图的比较器与equals不一致(参见sortMap javadox)。这意味着从树形图中退出项目将不起作用。 sorted_map.get(“A”)将返回null。这意味着树图的使用被打破了。 - mR_fr0g
以防人们不清楚:如果你有多个键映射到相同的值,这个解决方案可能不会做你想要的 - 只有其中一个键出现在排序结果中。 - Maxy-B
路易斯·瓦瑟曼(是的,谷歌番石榴人之一),实际上不喜欢这个答案:“如果你看起来很有趣,它会打破几种令人困惑的方式。如果支持地图改变了,它就会破坏。如果有多个键映射到相同的值,它将中断。如果你调用get不在支持映射中的键,它将会中断。如果你做任何会导致查找发生在不在的键上地图 - 一个Map.equals调用,containsKey,任何东西 - 它会破坏真正奇怪的堆栈跟踪。“ plus.google.com/102216152814616302326/posts/bEQLDK712MJ - haylem


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

215



很好,但是如何使用 parallelStream() 在这种情况下 ? - Benj
它将并行工作,但是,您可能会发现合并地图以合并部分结果的成本太高,并行版本可能无法达到您希望的效果。但它确实有效并产生正确的答案。 - Brian Goetz
感谢您的有用建议。这正是我想知道的,虽然它取决于你使用什么类型的密钥和如此多的参数......重要的是“它确实起作用并产生正确的答案”。 - Benj
如何根据不同大小的列表值进行排序?我想按降序列表大小排序。 - Pete
你不必在top10例子中使用compareByValue吗? - Leo


三个1行答案......

我会用 Google Collections  番石榴 这样做 - 如果你的价值观是 Comparable 那你可以用

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

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

如果他们没有可比性,那么你需要做一些事情

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

这些可以应用于TreeMap(如 Ordering 扩展 Comparator),或者a 一些排序后的LinkedHashMap

NB:如果您打算使用TreeMap,请记住,如果比较== 0,那么该项已经在列表中(如果您有多个比较相同的值,则会发生这种情况)。为了缓解这种情况,您可以将密钥添加到比较器中(假设您的密钥和值是 Comparable):

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

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

请注意,如果您的密钥与0比较,这仍然不起作用,但这对大多数人来说应该足够了 comparable 物品(如 hashCodeequals 和 compareTo 通常是同步...)

看到 Ordering.onResultOf() 和 Functions.forMap()

履行

所以现在我们已经有了一个可以满足我们想要的比较器,我们需要从中获得结果。

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

现在这很可能会起作用,但是:

  1. 需要完成一个完整的完成地图
  2. 不要尝试上面的比较器 TreeMap;没有必要尝试比较插入的密钥,直到它没有值,直到放置之后,即,它会非常快地破坏

第1点对我来说是一个破坏性的事情;谷歌收藏是非常懒惰(这是好的:你可以在瞬间完成几乎所有的操作;真正的工作是在你开始使用结果时完成的),这需要复制一个 整个 地图!

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

不过不要担心;如果你对以这种方式排序的“实时”地图足够痴迷,你可以解决上述问题中的一个而不是一个(!),如下所示:

注意:这在2012年6月发生了重大变化 - 之前的代码永远不会起作用:需要内部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进行排序。但在此之前,我们检查哈希映射,看看密钥实际上并不重复。此外,我们创建的比较器还将包含密钥,以便重复值不会删除非重复键(由于==比较)。 这2项是 重要 确保保留地图合同;如果你认为你不想要那个,那么你几乎就是完全颠倒了地图(对 Map<V,K>)。

需要将构造函数称为

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

207



您好@Stephen,您能举例说明如何使用订购吗?我查看Ordering的源代码,完全无法弄清楚.natural()。onResultOf(...)返回的内容!源代码是“public <F> Ordering <F> onResultOf”,我甚至不知道它是如何编译的!最重要的是,如何使用“<F>订购<F>”对地图进行排序?它是比较器还是什么?谢谢。 - smallufo
这太棒了。我想这个答案是在“如何按照Guava中的值排序地图的键”这个问题,这正是我所寻求的。我将此答案改编为:final List <K> sortedKeys = Ordering.natural()。onResultOf(Functions.forMap(map))。immutableSortedCopy(map.keySet());这就是我需要的。谢谢! - John Lehmann
谈论ValueComparableMap类,它实现了对问题最具挑战性的答案,因为它提供了一个可变的有序映射。我没有看到这是如何工作的。对super.get(key)的调用将引用比较器进行树遍历(这是排序树的工作原理,或参见TreeMap源代码)。比较器需要从#get回答才能返回答案。在我看来,这将在无限循环中结束。 (还有一个问题是“this”在构造函数中不能引用,但那不太重要。) - Olivier Cailloux
@Oliver;太棒了!我没有注意到(有时你真的需要分析抽象......)。我已经解决了这两个问题,并添加了一些内联测试。接下来的问题是:如果没有人使用这些代码,我怎么得到48票呢? :) - Stephen
多亏了这一点,我在一个项目中使用了您的解决方案。我认为这里存在一个问题:要像地图一样运行,它需要返回之前与密钥相关联的值,如果它存在,但是像这样它永远不会。我使用的解决方案是返回已删除的值(如果存在)。 - alex


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

171



要排序的列表是“new LinkedList”??啧啧。谢天谢地,Collections.sort()首先将列表转储到数组中,以避免产生这种错误(但是,将ArrayList转储到数组应该比对LinkedList执行相同操作更快)。 - Dimitris Andreou
没有泛型? :-( - TraderJoeChicago
@ gg.kaspersky我不是说“对LinkedList进行排序很糟糕”,但是LinkedList本身在这里是一个糟糕的选择,无论排序如何。 许多 最好使用ArrayList,对于额外的点,请在map.size()中确定它的大小。另见 code.google.com/p/memory-measurer/wiki/...  ArrayList中每个元素的平均成本:LinkedList中每个元素的5个字节平均成本:24个字节。对于精确大小的ArrayList,平均成本为4个字节。也就是说,LinkedList需要 六 乘以ArrayList所需的内存量。它只是臃肿 - Dimitris Andreou
使用上述值已按升序排序。如何降序排序? - ram
替换o1和o2以降序排序。 - Soheil


对键进行排序需要比较器查找每个比较的每个值。一个更具可扩展性的解决方案将直接使用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();

最后,如果您需要不断访问已排序的信息(而不是仅仅偶尔对其进行排序),则可以使用其他多地图。如果您需要更多详细信息,请告诉我们......


28



如果返回List <Map.Entry <K,V >>,第二个版本可以更简洁。这也可以更容易地迭代并获得键和值,而无需对地图进行大量额外的操作。这是假设您可以使用此代码线程不安全。如果在多线程环境中共享支持映射或排序列表,则所有投注都将关闭。 - Mike Miller


使用Java 8,您可以使用 溪流api 以明显不那么冗长的方式做到这一点:

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

26



如何以相反的顺序对其进行排序? - Vlad Holubiev
@VladGolubev comparing(Entry::getValue).reversed() - assylias
找到了解决方案 - Collections.reverseOrder(comparing(Entry::getValue)) - Vlad Holubiev
看看这个示例代码 - Vlad Holubiev
@JakeStokes或使用静态导入:-) - assylias