Sort a Map by values

Мне нужно отсортировать 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;
    }
}

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

В LinkedHashMap приведенном выше примере выполняется итерация записей в том порядке, в котором они были вставлены.

Или распечатать в System.out:

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

Важное примечание:

Этот код может быть поврежден несколькими способами. Если вы собираетесь использовать предоставленный код, обязательно прочитайте комментарии, чтобы быть в курсе последствий. Например, значения больше не могут быть получены по их ключу. (get всегда возвращается null.)

Это кажется намного проще, чем все предыдущее. Используйте древовидную карту следующим образом:

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}

Три ответа из 1 строки...

Я бы использовал для этого коллекции Google Guava - если ваши значения равны Comparable, то вы можете использовать

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

Которая создаст функцию (объект) для карты [которая принимает любой из ключей в качестве входных данных, возвращая соответствующее значение], а затем применит к ним естественный (сопоставимый) порядок [значений].

Если они несопоставимы, то вам нужно будет сделать что-то вроде

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

Они могут быть применены к TreeMap (как Ordering расширяется Comparator) или к LinkedHashMap после некоторой сортировки

ПРИМЕЧАНИЕ: Если вы собираетесь использовать древовидную карту, помните, что если сравнение == 0, то элемент уже есть в списке (что произойдет, если у вас есть несколько значений, которые сравнивают одно и то же). Чтобы облегчить это, вы могли бы добавить свой ключ в компаратор следующим образом (предполагая, что ваши ключи и значения Comparable):

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

= Примените естественный порядок к значению, отображенному ключом, и соедините его с естественным порядком ключа

Обратите внимание, что это все равно не сработает, если ваши ключи сравниваются с 0, но этого должно быть достаточно для большинства comparable элементов (поскольку hashCode, equals и compareTo часто синхронизированы ...)

Смотреть Упорядочивание.onResultOf() и Функции.forMap().

Реализация

Итак, теперь, когда у нас есть компаратор, который делает то, что мы хотим, нам нужно получить от него результат.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Теперь это, скорее всего, сработает, но:

1. необходимо выполнить, учитывая полную готовую карту


2. Не пытайтесь использовать приведенные выше компараторы для a TreeMap; нет смысла пытаться сравнивать вставленный ключ, если у него нет значения, до окончания ввода, т. Е. Он очень быстро сломается

Point 1 is a bit of a deal-breaker for me; google collections is incredibly lazy (which is good: you can do pretty much every operation in an instant; the real work is done when you start using the result), and this requires copying a whole map!

"Full" answer/Live sorted map by values

Don't worry though; if you were obsessed enough with having a "live" map sorted in this manner, you could solve not one but both(!) of the above issues with something crazy like the following:

Note: This has changed significantly in June 2012 - the previous code could never work: an internal HashMap is required to lookup the values without creating an infinite loop between the TreeMap.get() -> compare() and 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"));
    }
 }

When we put, we ensure that the hash map has the value for the comparator, and then put to the TreeSet for sorting. But before that we check the hash map to see that the key is not actually a duplicate. Also, the comparator that we create will also include the key so that duplicate values don't delete the non-duplicate keys (due to == comparison).
These 2 items are vital for ensuring the map contract is kept; if you think you don't want that, then you're almost at the point of reversing the map entirely (to Map<V,K>).

The constructor would need to be called as

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