Posortuj mapę <Klucz, wartość> według wartości

Jestem stosunkowo nowy w Javie i często stwierdzam, że muszę uporządkować Map<Key, Value>wartości.

Ponieważ wartości te nie są wyjątkowe, ja znajduję się nawracanie keySetw produkt arrayi sortowania tej tablicy za pośrednictwem tablicy sortowania z niestandardowych komparatora że sortuje na wartości związanej z kluczem.

Czy istnieje prostszy sposób?

Oto wersja ogólna:

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

Ważna uwaga:

Ten kod może ulec uszkodzeniu na wiele sposobów. Jeśli zamierzasz użyć dostarczonego kodu, koniecznie przeczytaj komentarze, aby mieć świadomość konsekwencji. Na przykład wartości nie można już pobrać za pomocą klucza. ( getzawsze wraca null.)

Wydaje się to znacznie łatwiejsze niż wszystkie powyższe. Użyj TreeMap w następujący sposób:

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

Wynik:

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}

Java 8 oferuje nową odpowiedź: przekonwertuj wpisy na strumień i użyj kombinacji programów porównawczych z Map.Entry:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue());

Umożliwi to wykorzystanie wpisów posortowanych według rosnącej wartości. Jeśli chcesz wartość malejącą, po prostu odwróć komparator:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()));

Jeśli wartości nie są porównywalne, możesz przekazać jawny komparator:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue(comparator));

Następnie możesz przejść do korzystania z innych operacji strumieniowych w celu zużycia danych. Na przykład, jeśli chcesz 10 najlepszych na nowej mapie:

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

Lub wydrukuj do System.out:

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

Trzy odpowiedzi 1-liniowe ...

W tym celu skorzystałbym z Google Guava Kolekcje - jeśli twoje wartości są Comparable, możesz użyć

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

Który utworzy funkcję (obiekt) dla mapy [która pobiera dowolny z klawiszy jako dane wejściowe, zwracając odpowiednią wartość], a następnie zastosuje do nich naturalne (porównywalne) uporządkowanie [wartości].

Jeśli nie są porównywalne, musisz zrobić coś w stylu

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

Można je zastosować do TreeMap (w Orderingrozszerzeniu Comparator) lub LinkedHashMap po pewnym sortowaniu

Uwaga : Jeśli zamierzasz użyć TreeMap, pamiętaj, że jeśli porównanie == 0, to element jest już na liście (co się stanie, jeśli masz wiele wartości, które porównują to samo). Aby to złagodzić, możesz dodać swój klucz do komparatora w taki sposób (zakładając, że twoje klucze i wartości są Comparable):

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

= Zastosuj naturalne uporządkowanie do wartości odwzorowanej przez klucz i połącz to z naturalnym uporządkowaniem klucza

Zauważ, że to nadal nie zadziała, jeśli twoje klucze będą miały wartość 0, ale powinno wystarczyć dla większości comparableprzedmiotów (as hashCode, equalsicompareTo często są zsynchronizowane ...)

Zobacz Ordering.onResultOf () i Functions.forMap () .

Realizacja

Teraz, gdy mamy komparator, który robi to, co chcemy, musimy uzyskać z tego wynik.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Teraz najprawdopodobniej zadziała, ale:

1. należy to zrobić, biorąc pod uwagę kompletną gotową mapę
2. Nie próbuj powyższych komparatorów na TreeMap; nie ma sensu porównywać wstawionego klucza, gdy nie ma on wartości aż do momentu wstawienia, tzn. bardzo szybko się psuje

Punkt 1 jest dla mnie trochę przełomowy; kolekcje google są niezwykle leniwe (co jest dobre: ​​możesz wykonać niemal każdą operację w jednej chwili; prawdziwa praca jest wykonywana, gdy zaczniesz używać wyniku), a to wymaga skopiowania całej mapy!

Odpowiedź „pełna” / mapa posortowana na żywo według wartości

Nie martw się jednak; jeśli miałeś dość obsesji na punkcie posortowanej w ten sposób mapy „na żywo”, możesz rozwiązać nie jeden, ale oba (!) z powyższych problemów, używając czegoś szalonego, takiego jak:

Uwaga: uległo to znacznej zmianie w czerwcu 2012 r. - poprzedni kod nigdy nie mógł działać: wewnętrzny HashMap jest wymagany do wyszukiwania wartości bez tworzenia nieskończonej pętli między TreeMap.get()-> compare()a 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"));
    }
 }

Kiedy wstawiamy, upewniamy się, że mapa skrótu ma wartość dla komparatora, a następnie umieszczana w TreeSet w celu sortowania. Ale wcześniej sprawdzamy mapę skrótu, aby zobaczyć, czy klucz nie jest w rzeczywistości duplikatem. Tworzony przez nas komparator będzie również zawierał klucz, aby zduplikowane wartości nie usuwały niepowielonych kluczy (z powodu porównania ==). Te 2 elementy są niezbędne do zachowania kontraktu na mapie; jeśli uważasz, że tego nie chcesz, to prawie jesteś w stanie całkowicie odwrócić mapę (doMap<V,K> ).

Konstruktor musiałby zostać nazwany jako

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

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

W Javie 8 możesz użyć interfejsu API strumieni, aby zrobić to w znacznie mniej szczegółowy sposób:

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

Sortowanie kluczy wymaga, aby Komparator szukał każdej wartości dla każdego porównania. Bardziej skalowalne rozwiązanie użyłoby entrySet bezpośrednio, ponieważ wtedy wartość byłaby natychmiast dostępna dla każdego porównania (chociaż nie poparłem tego liczbowo).

Oto ogólna wersja takiej rzeczy:

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

Istnieją sposoby zmniejszenia rotacji pamięci dla powyższego rozwiązania. Pierwsza utworzona lista ArrayList może na przykład zostać ponownie użyta jako wartość zwracana; wymagałoby to zniesienia niektórych ogólnych ostrzeżeń, ale może być tego warte w przypadku kodu biblioteki wielokrotnego użytku. Ponadto komparator nie musi być ponownie przydzielany przy każdym wywołaniu.

Oto bardziej wydajna, choć mniej atrakcyjna wersja:

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

Wreszcie, jeśli chcesz stale uzyskiwać dostęp do posortowanych informacji (zamiast tylko od czasu do czasu sortować je), możesz użyć dodatkowej mapy wielozadaniowej. Daj mi znać, jeśli potrzebujesz więcej szczegółów ...

Biblioteka commons-collections zawiera rozwiązanie o nazwie TreeBidiMap . Możesz też zapoznać się z interfejsem API Google Maps. Ma TreeMultimap, którego możesz użyć.

A jeśli nie chcesz używać tych ram ... pochodzą one z kodem źródłowym.

Przejrzałem podane odpowiedzi, ale wiele z nich jest bardziej skomplikowanych niż potrzeba lub usuwam elementy mapy, gdy kilka kluczy ma tę samą wartość.

Oto rozwiązanie, które moim zdaniem pasuje lepiej:

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

Zauważ, że mapa jest posortowana od najwyższej wartości do najniższej.

Aby to osiągnąć dzięki nowym funkcjom w Javie 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());
}

Wpisy są uporządkowane według ich wartości za pomocą danego komparatora. Alternatywnie, jeśli twoje wartości są wzajemnie porównywalne, nie jest potrzebny żaden wyraźny komparator:

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

Zwrócona lista jest migawką danej mapy w momencie wywołania tej metody, więc żadna z nich nie będzie odzwierciedlała kolejnych zmian w drugiej. Aby zobaczyć iterowalny widok mapy:

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

Zwracana iterowalność tworzy nową migawkę danej mapy za każdym razem, gdy jest ona iterowana, więc z wyjątkiem jednoczesnej modyfikacji, zawsze będzie odzwierciedlała aktualny stan mapy.

Utwórz dostosowany komparator i użyj go podczas tworzenia nowego obiektu 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));

    }
}

Użyj poniższego kodu w swoim głównym func

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

Wynik:

{B=75, D=50, C=50, A=35}

Chociaż zgadzam się, że ciągła potrzeba sortowania mapy jest prawdopodobnie zapachem, myślę, że poniższy kod jest najłatwiejszym sposobem na zrobienie tego bez użycia innej struktury danych.

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

}

A oto zawstydzająco niepełny test jednostkowy:

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

}

Wynikiem jest posortowana lista obiektów Map.Entry, z których można uzyskać klucze i wartości.

Użyj ogólnego komparatora, takiego jak:

final class MapValueComparator<K,V extends Comparable<V>> implements Comparator<K> {

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

Odpowiedź najbardziej głosowana nie działa, jeśli masz 2 równe przedmioty. TreeMap pozostawia równe wartości.

exmaple: nieposortowana mapa

klucz / wartość: D / 67,3
klucz / wartość: A / 99.5
klucz / wartość: B / 67,4
klucz / wartość: C / 67,5
klucz / wartość: E / 99.5

wyniki

klucz / wartość: A / 99.5
klucz / wartość: C / 67,5
klucz / wartość: B / 67,4
klucz / wartość: D / 67,3

Więc pomija E !!

Dla mnie dobrze działało dostosowanie komparatora, jeśli jest równe, nie zwraca 0, ale -1.

w przykładzie:

klasa ValueComparator implementuje Komparator {

Baza mapy; public ValueComparator (podstawa mapy) {this.base = base; }

public int porównaj (Obiekt a, Obiekt 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;
}

}}

teraz zwraca:

nieposortowana mapa:

klucz / wartość: D / 67,3
klucz / wartość: A / 99.5
klucz / wartość: B / 67,4
klucz / wartość: C / 67,5
klucz / wartość: E / 99.5

wyniki:

klucz / wartość: A / 99.5
klucz / wartość: E / 99.5
klucz / wartość: C / 67,5
klucz / wartość: B / 67,4
klucz / wartość: D / 67,3

w odpowiedzi na Aliens (22 listopada 2011 r.): Używam tego rozwiązania do mapy identyfikatorów i nazw liczb całkowitych, ale pomysł jest taki sam, więc powyższy kod może być nieprawidłowy (napiszę go w teście i podamy prawidłowy kod), jest to kod do sortowania map w oparciu o powyższe rozwiązanie:

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


}

i to jest klasa testowa (właśnie ją przetestowałem i działa to na Integer, String Map:

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

oto kod dla komparatora mapy:

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

i to jest przykład tego:

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

oczywiście możesz uczynić to o wiele bardziej ogólnym, ale potrzebowałem go tylko na 1 skrzynkę (Mapa)

Zamiast używać Collections.sortjak niektórzy sugeruję użycie Arrays.sort. W rzeczywistości Collections.sortdziała to tak:

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

Po prostu wywołuje toArraylistę, a następnie używa Arrays.sort. W ten sposób wszystkie wpisy na mapie zostaną skopiowane trzykrotnie: raz z mapy na listę tymczasową (może to być LinkedList lub ArrayList), następnie do tablicy tymczasowej i na koniec do nowej mapy.

Moje rozwiązanie pomija ten jeden krok, ponieważ nie tworzy niepotrzebnej listy LinkedList. Oto kod, ogólny i optymalny pod względem wydajności:

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

Jest to odmiana odpowiedzi Anthony'ego, która nie działa, jeśli istnieją zduplikowane wartości:

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

Zauważ, że radzenie sobie z zerami jest raczej w powietrzu.

Jedną ważną zaletą tego podejścia jest to, że faktycznie zwraca mapę, w przeciwieństwie do niektórych innych rozwiązań tutaj oferowanych.

Najlepsze podejście

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

Wynik

java ==== 20

MAC ==== 26

C++ ==== 45

Unix ==== 67

Why this kolavari ==== 93

Główny problem. Jeśli użyjesz pierwszej odpowiedzi (Google zabierze Cię tutaj), zmień komparator, aby dodać klauzulę równości, w przeciwnym razie nie możesz uzyskać wartości z sorted_map według kluczy:

public int compare(String a, String b) {
        if (base.get(a) > base.get(b)) {
            return 1;
        } else if (base.get(a) < base.get(b)){
            return -1;
        } 

        return 0;
        // returning 0 would merge keys
    }

Istnieje wiele odpowiedzi na to pytanie, ale żadna nie dostarczyła mi tego, czego szukałem, implementacji mapy, która zwraca klucze i wpisy posortowane według powiązanej wartości, i zachowuje tę właściwość, gdy klucze i wartości są modyfikowane na mapie. Zadają to dwa inne pytania .

Przygotowałem ogólny, przyjazny przykład, który rozwiązuje ten przypadek użycia. Ta implementacja nie uwzględnia wszystkich umów interfejsu mapy, takich jak odzwierciedlenie zmian wartości i usuwania w zestawach zwracanych z keySet () i entrySet () w oryginalnym obiekcie. Czułem, że takie rozwiązanie byłoby zbyt duże, aby można je było uwzględnić w odpowiedzi na przepełnienie stosu. Jeśli uda mi się stworzyć pełniejszą implementację, być może opublikuję ją w Github, a następnie w linku w zaktualizowanej wersji tej odpowiedzi.

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

Późne wejście

Wraz z pojawieniem się Java-8 możemy używać strumieni do manipulacji danymi w bardzo łatwy / zwięzły sposób. Możesz użyć strumieni, aby posortować wpisy mapy według wartości i utworzyć LinkedHashMap, która zachowa iterację kolejności wstawiania .

Na przykład:

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

W przypadku odwrotnego zamówienia wymień:

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

z

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

Podana mapa

   Map<String, Integer> wordCounts = new HashMap<>();
    wordCounts.put("USA", 100);
    wordCounts.put("jobs", 200);
    wordCounts.put("software", 50);
    wordCounts.put("technology", 70);
    wordCounts.put("opportunity", 200);

Posortuj mapę według wartości w porządku rosnącym

Map<String,Integer>  sortedMap =  wordCounts.entrySet().
                                                stream().
                                                sorted(Map.Entry.comparingByValue()).
        collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
    System.out.println(sortedMap);

Posortuj mapę według wartości w porządku malejącym

Map<String,Integer>  sortedMapReverseOrder =  wordCounts.entrySet().
            stream().
            sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())).
            collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
    System.out.println(sortedMapReverseOrder);

Wynik:

{oprogramowanie = 50, technologia = 70, USA = 100, miejsca pracy = 200, okazja = 200}

{miejsca pracy = 200, szansa = 200, USA = 100, technologia = 70, oprogramowanie = 50}

W zależności od kontekstu, przy użyciu java.util.LinkedHashMap<T>którego pamięta się kolejność, w jakiej przedmioty są umieszczane na mapie. W przeciwnym razie, jeśli trzeba posortować wartości na podstawie ich naturalnego uporządkowania, zaleciłbym utrzymanie osobnej listy, którą można sortować Collections.sort().

Ponieważ TreeMap <> nie działa dla wartości, które mogą być równe, użyłem tego:

private <K, V extends Comparable<? super V>> List<Entry<K, V>> sort(Map<K, V> map)     {
    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
        public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });

    return list;
}

Możesz chcieć umieścić listę w LinkedHashMap , ale jeśli masz zamiar iterować od razu, to jest zbyteczne ...

To jest zbyt skomplikowane. Mapy nie powinny wykonywać takich zadań, jak sortowanie ich według wartości. Najłatwiejszym sposobem jest stworzenie własnej klasy, która spełni twoje wymagania.

Na przykład niżej powinieneś dodać TreeMap komparator w miejscu, gdzie * jest. Ale przez java API daje komparatorowi tylko klucze, a nie wartości. Wszystkie podane tutaj przykłady oparte są na 2 mapach. Jeden hasz i jedno nowe drzewo. Co jest dziwne.

Przykład:

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

Zmień mapę na zestaw w ten sposób:

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

Stworzysz klasę 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;
    }
}

oraz klasa komparatora:

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

W ten sposób możesz łatwo dodać więcej zależności.

I jako ostatni punkt dodam prosty iterator:

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

Oparty na kodzie @devinmoore, metody sortowania map przy użyciu ogólnych i obsługujących zarówno rosnącą, jak i malejącą kolejność.

/**
 * Sort a map by it's keys in ascending order. 
 *  
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMapByKey(final Map<K, V> map) {
    return sortMapByKey(map, SortingOrder.ASCENDING);
}

/**
 * Sort a map by it's values in ascending order.
 *  
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMapByValue(final Map<K, V> map) {
    return sortMapByValue(map, SortingOrder.ASCENDING);
}

/**
 * Sort a map by it's keys.
 *  
 * @param sortingOrder {@link SortingOrder} enum specifying requested sorting order. 
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMapByKey(final Map<K, V> map, final SortingOrder sortingOrder) {
    Comparator<Map.Entry<K, V>> comparator = new Comparator<Entry<K,V>>() {
        public int compare(Entry<K, V> o1, Entry<K, V> o2) {
            return comparableCompare(o1.getKey(), o2.getKey(), sortingOrder);
        }
    };

    return sortMap(map, comparator);
}

/**
 * Sort a map by it's values.
 *  
 * @param sortingOrder {@link SortingOrder} enum specifying requested sorting order. 
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMapByValue(final Map<K, V> map, final SortingOrder sortingOrder) {
    Comparator<Map.Entry<K, V>> comparator = new Comparator<Entry<K,V>>() {
        public int compare(Entry<K, V> o1, Entry<K, V> o2) {
            return comparableCompare(o1.getValue(), o2.getValue(), sortingOrder);
        }
    };

    return sortMap(map, comparator);
}

@SuppressWarnings("unchecked")
private static <T> int comparableCompare(T o1, T o2, SortingOrder sortingOrder) {
    int compare = ((Comparable<T>)o1).compareTo(o2);

    switch (sortingOrder) {
    case ASCENDING:
        return compare;
    case DESCENDING:
        return (-1) * compare;
    }

    return 0;
}

/**
 * Sort a map by supplied comparator logic.
 *  
 * @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
 * @author Maxim Veksler
 */
public static <K, V> LinkedHashMap<K, V> sortMap(final Map<K, V> map, final Comparator<Map.Entry<K, V>> comparator) {
    // Convert the map into a list of key,value pairs.
    List<Map.Entry<K, V>> mapEntries = new LinkedList<Map.Entry<K, V>>(map.entrySet());

    // Sort the converted list according to supplied comparator.
    Collections.sort(mapEntries, comparator);

    // Build a new ordered map, containing the same entries as the old map.  
    LinkedHashMap<K, V> result = new LinkedHashMap<K, V>(map.size() + (map.size() / 20));
    for(Map.Entry<K, V> entry : mapEntries) {
        // We iterate on the mapEntries list which is sorted by the comparator putting new entries into 
        // the targeted result which is a sorted map. 
        result.put(entry.getKey(), entry.getValue());
    }

    return result;
}

/**
 * Sorting order enum, specifying request result sort behavior.
 * @author Maxim Veksler
 *
 */
public static enum SortingOrder {
    /**
     * Resulting sort will be from smaller to biggest.
     */
    ASCENDING,
    /**
     * Resulting sort will be from biggest to smallest.
     */
    DESCENDING
}

Oto rozwiązanie OO (tzn. Nie używa staticmetod):

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class SortableValueMap<K, V extends Comparable<V>>
  extends LinkedHashMap<K, V> {
  public SortableValueMap() { }

  public SortableValueMap( Map<K, V> map ) {
    super( map );
  }

  public void sortByValue() {
    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>( entrySet() );

    Collections.sort( list, new Comparator<Map.Entry<K, V>>() {
      public int compare( Map.Entry<K, V> entry1, Map.Entry<K, V> entry2 ) {
        return entry1.getValue().compareTo( entry2.getValue() );
      }
    });

    clear();

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

  private static void print( String text, Map<String, Double> map ) {
    System.out.println( text );

    for( String key : map.keySet() ) {
      System.out.println( "key/value: " + key + "/" + map.get( key ) );
    }
  }

  public static void main( String[] args ) {
    SortableValueMap<String, Double> map =
      new SortableValueMap<String, Double>();

    map.put( "A", 67.5 );
    map.put( "B", 99.5 );
    map.put( "C", 82.4 );
    map.put( "D", 42.0 );

    print( "Unsorted map", map );
    map.sortByValue();
    print( "Sorted map", map );
  }
}