logo标签列表

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

javasortingdictionarycollections
1881
我需要根据值对一个Map进行排序。
由于值不是唯一的，我发现自己需要将keySet转换为数组，并通过使用自定义比较器对该数组进行排序，以便根据与键关联的值进行排序。
有没有更简单的方法？
32
地图的目的不是为了排序，而是为了快速访问。对象相等的值会违反地图的约束条件。使用entry set，例如 List<Map.Entry<...>> list =new LinkedList(map.entrySet()) 和 Collections.sort .... 进行排序。 - Hannes
2
一个可能出现这种情况的案例是当我们尝试在Java中使用计数器（Map<Object，Integer>）时。按出现次数排序将成为常见操作。像Python这样的语言具有内置的计数器数据结构。对于Java中的另一种实现方式，此处提供了一个示例。 - demongolem
14
有很多使用排序映射的情况，这就是为什么在jdk中有TreeMap和ConcurrentSkipListMap的原因。 - alobodzk
8
TreeMap和ConcurrentSkipListMap会根据键进行排序。问题是如何按值排序。 - Peter
3
根据您的使用情况，保留一个重复的TreeMap，将值映射到键可能是合理的。例如，您的常规map可能为"a"->5，"b"->7。而您的“排序”map可以有5->“a”，7->“b”。您只需在不同的地方使用适当的map，并努力始终同时修改这两个map。虽然存在许多警告和假设，但对于某些情况而言，与所有依赖于主动排序您的值的答案相比，这可能是一种简单而有效的答案。 - rococo
显示剩余2条评论
65个回答
17
为了在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();
}

每次迭代返回的可迭代对象都会创建给定映射的全新快照，因此除非并发修改，否则它始终会反映映射的当前状态。
这将返回一个条目列表，而不是按值排序的映射。另一个返回映射的版本：https://dev59.com/qXVD5IYBdhLWcg3wDG_m#22132422 - assylias
16
创建自定义比较器并在创建新的TreeMap对象时使用它。
class MyComparator implements Comparator<Object> {

    Map<String, Integer> map;

    public MyComparator(Map<String, Integer> map) {
        this.map = map;
    }

    public int compare(Object o1, Object o2) {

        if (map.get(o2) == map.get(o1))
            return 1;
        else
            return ((Integer) map.get(o2)).compareTo((Integer)     
                                                            map.get(o1));

    }
}

在你的主函数中使用以下代码

    Map<String, Integer> lMap = new HashMap<String, Integer>();
    lMap.put("A", 35);
    lMap.put("B", 75);
    lMap.put("C", 50);
    lMap.put("D", 50);

    MyComparator comparator = new MyComparator(lMap);

    Map<String, Integer> newMap = new TreeMap<String, Integer>(comparator);
    newMap.putAll(lMap);
    System.out.println(newMap);

输出：

{B=75, D=50, C=50, A=35}
如果值相等，我将“return 1”行更改为比较键：“return ((String) o1).compareTo((String) o2);”。 - gjgjgj
13

使用通用比较器，例如：

final class MapValueComparator<K,V extends Comparable<V>> implements Comparator<K> {
    private final Map<K,V> map;
    
    private MapValueComparator() {
        super();
    }
    
    public MapValueComparator(Map<K,V> map) {
        this();
        this.map = map;
    }
        
    public int compare(K o1, K o2) {
        return map.get(o1).compareTo(map.get(o2));
    }
}
13

虽然我同意频繁对地图进行排序可能有点问题，但我认为以下代码是在不使用其他数据结构的情况下最简单的方法。

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

}

这里有一个非常不完整的单元测试：

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

结果是排序后的一组Map.Entry对象，您可以从中获取键和值。

这种方法比创建一个具有几乎相同效果的Map<V，List<K>>对象要简单得多且更直观。在Map对象中，值实际上并不应该是键，而在这种情况下，你真正需要的是一个列表，以我的看法。 - Jeff Wu
这个解决方案在处理大量数值时无法正常工作，它会干扰我的计数（与每个键相关联的值）。 - Sam Levin
1
很奇怪。你能详细说明一下吗？你的输出是什么，你期望的输出又是什么？ - Lyudmil
10
投票最多的答案在存在两个相等项时不起作用。TreeMap会忽略相等的值。
例子如下： 未排序的映射
key/value: D/67.3 key/value: A/99.5 key/value: B/67.4 key/value: C/67.5 key/value: E/99.5
结果为
key/value: A/99.5 key/value: C/67.5 key/value: B/67.4 key/value: D/67.3
所以忽略了E!!
对于我来说，调整比较器可以解决这个问题，如果相等则不返回0，而是返回-1。
在例子中：
class ValueComparator implements Comparator { Map base; public ValueComparator(Map base) { this.base = base; } public int compare(Object a, Object b) {
if((Double)base.get(a) < (Double)base.get(b)) {
  return 1;
} else if((Double)base.get(a) == (Double)base.get(b)) {
  return -1;
} else {
  return -1;
}

现在它返回：

未排序的映射：

键/值：D/67.3
键/值：A/99.5
键/值：B/67.4
键/值：C/67.5
键/值：E/99.5

结果：

键/值：A/99.5
键/值：E/99.5
键/值：C/67.5
键/值：B/67.4
键/值：D/67.3

作为对2011年11月22日“外星人”的回应：

我正在使用此解决方案来处理整数ID和名称的映射，但思路是相同的，所以上面的代码可能不正确（我将编写一个测试并给出您正确的代码），这是一个基于上述解决方案的Map排序的代码：

package nl.iamit.util;

import java.util.Comparator;
import java.util.Map;

public class Comparators {


    public static class MapIntegerStringComparator implements Comparator {

        Map<Integer, String> base;

        public MapIntegerStringComparator(Map<Integer, String> base) {
            this.base = base;
        }

        public int compare(Object a, Object b) {

            int compare = ((String) base.get(a))
                    .compareTo((String) base.get(b));
            if (compare == 0) {
                return -1;
            }
            return compare;
        }
    }


}

这是测试类（我刚刚测试过，对于整数、字符串映射都有效：

package test.nl.iamit.util;

import java.util.HashMap;
import java.util.TreeMap;
import nl.iamit.util.Comparators;
import org.junit.Test;
import static org.junit.Assert.assertArrayEquals;

public class TestComparators {


    @Test
    public void testMapIntegerStringComparator(){
        HashMap<Integer, String> unSoretedMap = new HashMap<Integer, String>();
        Comparators.MapIntegerStringComparator bvc = new Comparators.MapIntegerStringComparator(
                unSoretedMap);
        TreeMap<Integer, String> sorted_map = new TreeMap<Integer, String>(bvc);
        //the testdata:
        unSoretedMap.put(new Integer(1), "E");
        unSoretedMap.put(new Integer(2), "A");
        unSoretedMap.put(new Integer(3), "E");
        unSoretedMap.put(new Integer(4), "B");
        unSoretedMap.put(new Integer(5), "F");

        sorted_map.putAll(unSoretedMap);

        Object[] targetKeys={new Integer(2),new Integer(4),new Integer(3),new Integer(1),new Integer(5) };
        Object[] currecntKeys=sorted_map.keySet().toArray();

        assertArrayEquals(targetKeys,currecntKeys);
    }
}

这是一个Map的比较器代码：

public static class MapStringDoubleComparator implements Comparator {

    Map<String, Double> base;

    public MapStringDoubleComparator(Map<String, Double> base) {
        this.base = base;
    }

    //note if you want decending in stead of ascending, turn around 1 and -1
    public int compare(Object a, Object b) {
        if ((Double) base.get(a) == (Double) base.get(b)) {
            return 0;
        } else if((Double) base.get(a) < (Double) base.get(b)) {
            return -1;
        }else{
            return 1;
        }
    }
}

这是该测试用例：

@Test
public void testMapStringDoubleComparator(){
    HashMap<String, Double> unSoretedMap = new HashMap<String, Double>();
    Comparators.MapStringDoubleComparator bvc = new Comparators.MapStringDoubleComparator(
            unSoretedMap);
    TreeMap<String, Double> sorted_map = new TreeMap<String, Double>(bvc);
    //the testdata:
    unSoretedMap.put("D",new Double(67.3));
    unSoretedMap.put("A",new Double(99.5));
    unSoretedMap.put("B",new Double(67.4));
    unSoretedMap.put("C",new Double(67.5));
    unSoretedMap.put("E",new Double(99.5));

    sorted_map.putAll(unSoretedMap);

    Object[] targetKeys={"D","B","C","E","A"};
    Object[] currecntKeys=sorted_map.keySet().toArray();

    assertArrayEquals(targetKeys,currecntKeys);
}
当然你可以将这个更加通用化，但我只需要它适用于一个情况（Map）。
你是对的，我最初给出的代码确实有一些错误！希望我最近的编辑能帮到你。 - michel.iamit
10

与一些人使用的Collections.sort不同，我建议使用Arrays.sort。实际上，Collections.sort所做的就像这样：

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

它只是在列表上调用toArray然后使用Arrays.sort。这样，所有映射条目都将被复制三次：一次从映射到临时列表（LinkedList或ArrayList），然后到临时数组，最后到新映射。
我的解决方案省略了这一步，因为它不会创建不必要的链表。这里是代码，既通用友好又性能优化：
public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) 
{
    @SuppressWarnings("unchecked")
    Map.Entry<K,V>[] array = map.entrySet().toArray(new Map.Entry[map.size()]);

    Arrays.sort(array, new Comparator<Map.Entry<K, V>>() 
    {
        public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2) 
        {
            return e1.getValue().compareTo(e2.getValue());
        }
    });

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

    return result;
}
7
这是安东尼答案的变体，如果存在重复值，则无法使用该答案：
public static <K, V extends Comparable<V>> Map<K, V> sortMapByValues(final Map<K, V> map) {
    Comparator<K> valueComparator =  new Comparator<K>() {
        public int compare(K k1, K k2) {
            final V v1 = map.get(k1);
            final V v2 = map.get(k2);

            /* Not sure how to handle nulls ... */
            if (v1 == null) {
                return (v2 == null) ? 0 : 1;
            }

            int compare = v2.compareTo(v1);
            if (compare != 0)
            {
                return compare;
            }
            else
            {
                Integer h1 = k1.hashCode();
                Integer h2 = k2.hashCode();
                return h2.compareTo(h1);
            }
        }
    };
    Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
    sortedByValues.putAll(map);
    return sortedByValues;
}

请注意，如何处理空值还有待商榷。
这种方法的一个重要优点是它实际上返回了一个Map，而不像其他一些解决方案所提供的那样。
这是不正确的，我的方法可以处理重复的值。我已经在具有100个以上键且值为“1”的映射中使用过它。 - Anthony
7

延迟入口。

随着Java-8的到来，我们可以非常简单/简洁地使用流进行数据操作。您可以使用流按值对映射条目进行排序，并创建一个保留插入顺序迭代的LinkedHashMap。

例如：

LinkedHashMap sortedByValueMap = map.entrySet().stream()
                .sorted(comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey))     //first sorting by Value, then sorting by Key(entries with same value)
                .collect(LinkedHashMap::new,(map,entry) -> map.put(entry.getKey(),entry.getValue()),LinkedHashMap::putAll);

对于反向排序，请替换：

comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)

使用

comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey).reversed()
感谢您提供这个有注释的版本。我有一个问题：使用Entry.comparingByValue()（如assylias在https://dev59.com/qXVD5IYBdhLWcg3wDG_m#22132422中所述）和您使用的`comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)`有什么区别？如果值相同，我理解您也会比较键，对吗？我注意到排序会保留具有相同值的元素的顺序 - 所以如果键已经被排序过了，那么按键排序是否必要？ - Peter T.
7

最佳方法

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry; 

public class OrderByValue {

  public static void main(String a[]){
    Map<String, Integer> map = new HashMap<String, Integer>();
    map.put("java", 20);
    map.put("C++", 45);
    map.put("Unix", 67);
    map.put("MAC", 26);
    map.put("Why this kolavari", 93);
    Set<Entry<String, Integer>> set = map.entrySet();
    List<Entry<String, Integer>> list = new ArrayList<Entry<String, Integer>>(set);
    Collections.sort( list, new Comparator<Map.Entry<String, Integer>>()
    {
        public int compare( Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2 )
        {
            return (o1.getValue()).compareTo( o2.getValue() );//Ascending order
            //return (o2.getValue()).compareTo( o1.getValue() );//Descending order
        }
    } );
    for(Map.Entry<String, Integer> entry:list){
        System.out.println(entry.getKey()+" ==== "+entry.getValue());
    }
  }}

输出

java ==== 20

MAC ==== 26

C++ ==== 45

Unix ==== 67

Why this kolavari ==== 93
6
这个问题已经有很多答案了，但是没有一个能提供我所需要的东西——一个返回与相关值排序的键和条目的映射实现，并在修改映射中的键和值时保持此属性。另外两个问题也提出了类似的要求（其他和这里）。
我设计了一个通用的友好示例来解决这个问题。这个实现并不符合Map接口的所有契约，比如不能反映keySet()和entrySet()方法返回的集合中的值更改和删除操作。我认为这样的解决方案太大了，无法包含在Stack Overflow的答案中。如果我能创建一个更完整的实现，也许我会将它发布到Github上，并在更新版本的答案中提供链接。
import java.util.*;

/**
 * A map where {@link #keySet()} and {@link #entrySet()} return sets ordered
 * by associated values based on the the comparator provided at construction
 * time. The order of two or more keys with identical values is not defined.
 * <p>
 * Several contracts of the Map interface are not satisfied by this minimal
 * implementation.
 */
public class ValueSortedMap<K, V> extends HashMap<K, V> {
    protected Map<V, Collection<K>> valueToKeysMap;

    // uses natural order of value object, if any
    public ValueSortedMap() {
        this((Comparator<? super V>) null);
    }

    public ValueSortedMap(Comparator<? super V> valueComparator) {
        this.valueToKeysMap = new TreeMap<V, Collection<K>>(valueComparator);
    }

    public boolean containsValue(Object o) {
        return valueToKeysMap.containsKey(o);
    }

    public V put(K k, V v) {
        V oldV = null;
        if (containsKey(k)) {
            oldV = get(k);
            valueToKeysMap.get(oldV).remove(k);
        }
        super.put(k, v);
        if (!valueToKeysMap.containsKey(v)) {
            Collection<K> keys = new ArrayList<K>();
            keys.add(k);
            valueToKeysMap.put(v, keys);
        } else {
            valueToKeysMap.get(v).add(k);
        }
        return oldV;
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }

    public V remove(Object k) {
        V oldV = null;
        if (containsKey(k)) {
            oldV = get(k);
            super.remove(k);
            valueToKeysMap.get(oldV).remove(k);
        }
        return oldV;
    }

    public void clear() {
        super.clear();
        valueToKeysMap.clear();
    }

    public Set<K> keySet() {
        LinkedHashSet<K> ret = new LinkedHashSet<K>(size());
        for (V v : valueToKeysMap.keySet()) {
            Collection<K> keys = valueToKeysMap.get(v);
            ret.addAll(keys);
        }
        return ret;
    }

    public Set<Map.Entry<K, V>> entrySet() {
        LinkedHashSet<Map.Entry<K, V>> ret = new LinkedHashSet<Map.Entry<K, V>>(size());
        for (Collection<K> keys : valueToKeysMap.values()) {
            for (final K k : keys) {
                final V v = get(k);
                ret.add(new Map.Entry<K,V>() {
                    public K getKey() {
                        return k;
                    }

                    public V getValue() {
                        return v;
                    }

                    public V setValue(V v) {
                        throw new UnsupportedOperationException();
                    }
                });
            }
        }
        return ret;
    }
}
如果不允许使用Comparable和Comparator，那么该怎么做呢？ - Onic Team
不确定我是否理解您的用例，也许您可以详细说明一下。如果您希望用作值的对象不可比较，则需要将其转换为可比较的对象。 - David Bleckmann
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接