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

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

有没有更简单的方法?


当前回答

当你有两个相等的项目时,投票给最多的答案不起作用。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。

在示例中:

类ValueComparator实现Comparator{地图库;公共ValueComparator(地图库){this.base=基数;}public int compare(对象a,对象b){如果((双)base.get(a)<(双)base.get(b)){返回1;}否则如果((双)base.get(a)==(双)base.get(b)){返回-1;}其他{返回-1;}}}

现在它返回:

未排序地图:

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: E/99.5
key/value: C/67.5
key/value: B/67.4
key/value: 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;
        }
    }


}

这是测试类(我刚刚测试了它,这适用于Integer,StringMap:

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

以下是地图比较器的代码:

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

当然,你可以让它更通用,但我只需要一个案例(地图)

其他回答

三个单行答案。。。

我会使用GoogleCollectionsGuava来实现这一点-如果你的价值观是可比较的,那么你可以使用

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

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

如果它们不具有可比性,那么您需要按照

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

这些可以应用于TreeMap(因为Ordering扩展了Comparator),或者在排序后应用于LinkedHashMap

注意:如果要使用TreeMap,请记住,如果比较==0,则该项已在列表中(如果有多个值进行比较,则会发生这种情况)。为了缓解这种情况,您可以像这样将键添加到比较器中(假设键和值是可比较的):

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

=对键映射的值应用自然排序,并将其与键的自然排序组合

请注意,如果您的键与0比较,这仍然不起作用,但这对于大多数可比较的项来说应该足够了(因为hashCode、equals和compareTo通常是同步的…)

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

实施

现在我们有了一个比较器,它可以满足我们的需要,我们需要从中得到一个结果。

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

现在,这很可能奏效,但:

需要完成一张完整的地图不要在TreeMap上尝试上面的比较器;当插入的键在put之后才有值时,尝试比较它是没有意义的,也就是说,它会很快断开

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

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

不过别担心;如果你痴迷于以这种方式对“实时”地图进行排序,那么你可以用以下疯狂的方式解决上述问题,而不是其中一个,而是两个(!):

注意:这在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进行排序。但在此之前,我们检查哈希图,看看该键实际上不是重复的。此外,我们创建的比较器还将包括关键字,这样重复的值就不会删除非重复的关键字(由于==比较)。这两项对于确保地图合同得到遵守至关重要;如果你认为你不想这样,那么你几乎就要完全颠倒地图了(地图<V,K>)。

构造函数需要调用为

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

这还有一个额外的好处,即可以使用Java8进行升序或降序排序

import static java.util.Comparator.comparingInt;
import static java.util.stream.Collectors.toMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Utils {
    public static Map<String, Integer> sortMapBasedOnValues(Map<String, Integer> map, boolean descending) {
        int multiplyBy = (descending) ? -1: 1;
        Map<String, Integer> sorted =  map.entrySet().stream()
                .sorted(comparingInt(e -> multiplyBy * e.getValue() ))
                .collect(toMap(
                        Map.Entry::getKey, 
                        Map.Entry::getValue,
                        (a, b) -> { throw new AssertionError();},
                        LinkedHashMap::new
                    ));
        return sorted;
    }
}

这太复杂了。地图不应该按价值排序。最简单的方法是创建自己的类,以满足您的需求。

在下面的示例中,您应该在*所在的位置添加TreeMap比较器。但通过javaAPI,它只提供比较器键,而不提供值。此处所述的所有示例均基于2个地图。一个哈希和一个新树。这很奇怪。

示例:

Map<Driver driver, Float time> map = new TreeMap<Driver driver, Float time>(*);

因此,通过以下方式将地图更改为集合:

ResultComparator rc = new ResultComparator();
Set<Results> set = new TreeSet<Results>(rc);

您将创建类Results,

public class Results {
    private Driver driver;
    private Float time;

    public Results(Driver driver, Float time) {
        this.driver = driver;
        this.time = time;
    }

    public Float getTime() {
        return time;
    }

    public void setTime(Float time) {
        this.time = time;
    }

    public Driver getDriver() {
        return driver;
    }

    public void setDriver (Driver driver) {
        this.driver = driver;
    }
}

以及Comparator类:

public class ResultsComparator implements Comparator<Results> {
    public int compare(Results t, Results t1) {
        if (t.getTime() < t1.getTime()) {
            return 1;
        } else if (t.getTime() == t1.getTime()) {
            return 0;
        } else {
            return -1;
        }
    }
}

这样,您可以轻松添加更多依赖项。

最后一点,我将添加简单迭代器:

Iterator it = set.iterator();
while (it.hasNext()) {
    Results r = (Results)it.next();
    System.out.println( r.getDriver().toString
        //or whatever that is related to Driver class -getName() getSurname()
        + " "
        + r.getTime()
        );
}

如果倾向于使用一个Map数据结构,该结构可以按值进行固有排序,而不必触发任何排序方法或显式传递给实用程序,则以下解决方案可能适用:

(1) org.rools.chance.core.util.ValueSortedMap(JBoss项目)在内部维护两个映射,一个用于查找,另一个用于维护排序值。与之前添加的答案非常相似,但可能是抽象和封装部分(包括复制机制)使其更安全地从外部使用。

(2) http://techblog.molindo.at/2008/11/java-map-sorted-by-value.html避免维护两个映射,而是依赖/扩展Apache Common的LinkedMap。(博客作者注:这里的所有代码都在公共领域):

// required to access LinkEntry.before and LinkEntry.after
package org.apache.commons.collections.map;

// SNIP: imports

/**
* map implementation based on LinkedMap that maintains a sorted list of
* values for iteration
*/
public class ValueSortedHashMap extends LinkedMap {
    private final boolean _asc;

    // don't use super()!
    public ValueSortedHashMap(final boolean asc) {
        super(DEFAULT_CAPACITY);
        _asc = asc;
    }

    // SNIP: some more constructors with initial capacity and the like

    protected void addEntry(final HashEntry entry, final int hashIndex) {
        final LinkEntry link = (LinkEntry) entry;
        insertSorted(link);
        data[hashIndex] = entry;
    }

    protected void updateEntry(final HashEntry entry, final Object newValue) {
        entry.setValue(newValue);
        final LinkEntry link = (LinkEntry) entry;
        link.before.after = link.after;
        link.after.before = link.before;
        link.after = link.before = null;
        insertSorted(link);
    }

    private void insertSorted(final LinkEntry link) {
        LinkEntry cur = header;
        // iterate whole list, could (should?) be replaced with quicksearch
        // start at end to optimize speed for in-order insertions
        while ((cur = cur.before) != header & amp; & amp; !insertAfter(cur, link)) {}
        link.after = cur.after;
        link.before = cur;
        cur.after.before = link;
        cur.after = link;
    }

    protected boolean insertAfter(final LinkEntry cur, final LinkEntry link) {
        if (_asc) {
            return ((Comparable) cur.getValue())
            .compareTo((V) link.getValue()) & lt; = 0;
        } else {
            return ((Comparable) cur.getValue())
            .compareTo((V) link.getValue()) & gt; = 0;
        }
    }

    public boolean isAscending() {
        return _asc;
    }
}

(3) 编写一个自定义映射或从LinkedHashMap扩展,该映射仅在枚举期间根据需要进行排序(例如,values()、keyset()、entryset())。内部实现/行为是从使用该类的实现/行为中抽象出来的,但在该类的客户端看来,当请求枚举时,值总是被排序的。如果所有的put操作都在枚举之前完成,这个类希望排序只发生一次。排序方法采用了前面对这个问题的一些回答。

public class SortByValueMap<K, V> implements Map<K, V> {

    private boolean isSortingNeeded = false;

    private final Map<K, V> map = new LinkedHashMap<>();

    @Override
    public V put(K key, V value) {
        isSortingNeeded = true;
        return map.put(key, value);
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> map) {
        isSortingNeeded = true;
        map.putAll(map);
    }

    @Override
    public Set<K> keySet() {
        sort();
        return map.keySet();
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        sort();
        return map.entrySet();
    }

    @Override
    public Collection<V> values() {
        sort();
        return map.values();
    }

    private void sort() {
        if (!isSortingNeeded) {
            return;
        }

        List<Entry<K, V>> list = new ArrayList<>(size());

        for (Iterator<Map.Entry<K, V>> it = map.entrySet().iterator(); it.hasNext();) {
            Map.Entry<K, V> entry = it.next();
            list.add(entry);
            it.remove();
        }

        Collections.sort(list);

        for (Entry<K, V> entry : list) {
            map.put(entry.getKey(), entry.getValue());
        }

        isSortingNeeded = false;
    }

    @Override
    public String toString() {
        sort();
        return map.toString();
    }
}

(4) Guava提供了ImmutableMap.Builder.orderEntriesByValue(Comparator valueComparator),尽管生成的映射是不可变的:

将此生成器配置为根据指定的比较器。排序顺序是稳定的,也就是说,如果两个条目的值作为等价项进行比较,首先插入的条目将是第一个按照构建映射的迭代顺序。

我建议使用Arrays.sort,而不是像某些人那样使用Collections.ort。实际上Collections.ort的作用是这样的:

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

它只调用列表上的array,然后使用Arrays.sort。这样,所有映射条目将被复制三次:一次从映射复制到临时列表(无论是LinkedList还是ArrayList),然后复制到临时数组,最后复制到新映射。

我的解决方案省略了这一步,因为它不会创建不必要的LinkedList。以下是代码,通用友好,性能最佳:

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