Вопрос: Сортировка карты <Ключ, значение> по значениям


Я относительно новичок в Java, и часто обнаруживаю, что мне нужно сортировать Map<Key, Value>на значения.

Поскольку значения не уникальны, я считаю, что keySetв array, и сортировка этого массива через сортировка массива с пользовательский компаратор который сортирует значение, связанное с ключом.

Есть ли более простой способ?


1366


источник


Ответы:


Вот общая версия:

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

771



Важная заметка:

Этот код может разбиваться несколькими способами. Если вы намерены использовать предоставленный код, обязательно прочитайте комментарии, а также узнайте о последствиях. Например, значения больше не могут быть извлечены по их ключу. ( 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}

402



Три однострочных ответа ...

я хотел бы использовать Коллекции Google гуайява для этого - если ваши значения Comparableто вы можете использовать

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

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

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

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

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

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

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

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

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

Видеть Ordering.onResultOf () а также Functions.forMap () ,

Реализация

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

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

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

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

Пункт 1 для меня - это бит-брейк; Коллекции google невероятно ленивы (что хорошо: вы можете делать практически каждую операцию в одно мгновение, реальная работа выполняется, когда вы начинаете использовать результат), и для этого требуется скопировать все карта!

«Полный» ответ / Живая отсортированная карта по значениям

Не волнуйся; если бы вы были достаточно одержимы наличием «живой» карты, подобранной таким образом, вы могли бы решить не одну, а обе (!) вышеупомянутых проблем с чем-то сумасшедшим, например:

Примечание. Это значительно изменилось в июне 2012 года - предыдущий код никогда не работал: для поиска значений без внутренней бесконечной петли требуется внутренний 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));

206



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

203



From 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



Sorting the keys requires the Comparator to look up each value for each comparison. A more scalable solution would use the entrySet directly, since then the value would be immediately available for each comparison (although I haven't backed this up by numbers).

Here's a generic version of such a thing:

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

There are ways to lessen memory rotation for the above solution. The first ArrayList created could for instance be re-used as a return value; this would require suppression of some generics warnings, but it might be worth it for re-usable library code. Also, the Comparator does not have to be re-allocated at every invocation.

Here's a more efficient albeit less appealing version:

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

Finally, if you need to continously access the sorted information (rather than just sorting it once in a while), you can use an additional multi map. Let me know if you need more details...


28



With Java 8, you can use the streams api to do it in a significantly less verbose way:

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

26



The commons-collections library contains a solution called TreeBidiMap. Or, you could have a look at the Google Collections API. It has TreeMultimap which you could use.

And if you don't want to use these framework... they come with source code.


25



I've looked at the given answers, but a lot of them are more complicated than needed or remove map elements when several keys have same value.

Here is a solution that I think fits better:

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

Note that the map is sorted from the highest value to the lowest.


23



To accomplish this with the new features in 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());
}

The entries are ordered by their values using the given comparator. Alternatively, if your values are mutually comparable, no explicit comparator is needed:

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

The returned list is a snapshot of the given map at the time this method is called, so neither will reflect subsequent changes to the other. For a live iterable view of the map:

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

The returned iterable creates a fresh snapshot of the given map each time it's iterated, so barring concurrent modification, it will always reflect the current state of the map.


17



While I agree that the constant need to sort a map is probably a smell, I think the following code is the easiest way to do it without using a different data structure.

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

}

And here is an embarrassingly incomplete unit test:

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

}

The result is a sorted list of Map.Entry objects, from which you can obtain the keys and values.


14