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


1634

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?


24
Mapa nie jest przeznaczona do sortowania, ale jest dostępna szybko. Równe wartości obiektu przełamują ograniczenie mapy. Użyj zestawu wpisów, jak List<Map.Entry<...>> list =new LinkedList(map.entrySet())i Collections.sort ....tak.
Hannes

1
Przypadek, w którym może to wystąpić, gdy próbujemy użyć licznika w Javie (mapa <obiekt, liczba całkowita>). Sortowanie według liczby wystąpień byłoby wówczas częstą operacją. Język taki jak Python ma wbudowaną strukturę danych Licznika. Dla alternatywnego sposobu implementacji w Javie, oto przykład
demongolem

6
Istnieje wiele przypadków użycia posortowanych map, dlatego masz TreeMap i ConcurrentSkipListMap w jdk.
alobodzk


1
TreeMap i ConcurrentSkipListMap sortuj według klucza. Pytanie dotyczy sortowania według wartości.
Peter

Odpowiedzi:


899

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

10
Cieszę się, że to pomaga. John, LinkedHashMap jest ważna dla rozwiązania, ponieważ zapewnia przewidywalną kolejność iteracji.
Carter Page

3
@ buzz3791 Prawda. Tak będzie w przypadku każdego algorytmu sortowania. Zmiana wartości węzłów w strukturze podczas sortowania powoduje nieprzewidywalne (i prawie zawsze złe) wyniki.
Carter Page

3
@Sheagorath Wypróbowałem to w Androidzie i to też działa. Nie jest to problem specyficzny dla platformy, biorąc pod uwagę, że używasz wersji Java 6. Czy poprawnie zaimplementowałeś porównywalny w swoim obiekcie wartości?
saiyancoder

6
Nie powinno wersja użycie Java 8 forEachOrderedzamiast forEach, ponieważ docs forEachstwierdza: „Zachowanie tej operacji jest wyraźnie niedeterministyczny.”?
rob

1
całkowicie zgrane, ale przypisane @CarterPage w komentarzach (i tak będzie w projekcie open source). Dzięki wielkie.
Nathan Beach,

419

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}

18
Już nie ( stackoverflow.com/questions/109383/… ). Ponadto, dlaczego była obsada Double? Czy nie powinno tak być return ((Comparable)base.get(a).compareTo(((Comparable)base.get(b)))?
Stephen

12
@ Stephen: Nie. W tym przypadku wszystkie klucze o wartości równej wartości są upuszczane (różnica między wartością równą a porównaniem przez odniesienie). Dodatkowo: Nawet ten kod ma problemy z następującą sekwencją map.put("A","1d");map.put("B","1d");map.put("C",67d);map.put("D",99.5d);
steffen

43
Komparator użyty do mapy drzew jest niespójny z równością (patrz sortmap javadox). Oznacza to, że wycofywanie elementów z mapy drzewa nie będzie działać. sorted_map.get („A”) zwróci null. Oznacza to, że użycie mapowania terenu jest zerwane.
mR_fr0g

87
Na wszelki wypadek nie jest to jasne dla ludzi: to rozwiązanie prawdopodobnie nie zrobi tego, co chcesz, jeśli masz wiele kluczy mapujących na tę samą wartość - tylko jeden z tych kluczy pojawi się w posortowanym wyniku.
Maxy-B,

63
Louis Wasserman (tak, jeden z facetów Google Guava) tak naprawdę nie podoba się ta odpowiedź: „Łamie się na kilka naprawdę mylących sposobów, jeśli nawet spojrzysz na to zabawnie. Jeśli zmieni się mapa podkładu, to się zepsuje. Jeśli kilka kluczy zmapuje się do tej samej wartości, to się zepsuje. Jeśli wywołasz get na kluczu, którego nie ma na mapie podkładowej, to się zepsuje. Jeśli zrobisz cokolwiek, co spowodowałoby wyszukiwanie na kluczu, którego nie ma mapa - wywołanie Map.equals, zawiera Klucz, cokolwiek - zepsuje się z naprawdę dziwnymi śladami stosu. " plus.google.com/102216152814616302326/posts/bEQLDK712MJ
szlem

339

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

Fajnie, ale co z wykorzystaniem parallelStream()w tym przypadku?
Benj

11
Będzie działać równolegle, jednak może się okazać, że koszt scalania map w celu połączenia częściowych wyników jest zbyt drogi, a wersja równoległa może nie działać tak dobrze, jak można oczekiwać. Ale to działa i daje prawidłową odpowiedź.
Brian Goetz,

Dziękuję za przydatną poradę. Zastanawiałem się dokładnie nad tym, choć zależy to od tego, jakiego rodzaju klucza używasz i wielu parametrów ... Ważne jest to, że „działa i daje poprawną odpowiedź”.
Benj,

2
czy nie musisz używać CompareByValue w przykładzie z pierwszej dziesiątki?
Leo

1
@Benj będzie działało pod względem wyodrębnienia pierwszej dziesiątki, ale wynikowa mapa nie będzie już zamówiona.
OrangeDog,

211

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

Cześć @Stephen, czy możesz podać przykład korzystania z funkcji zamawiania? Patrzę na kod źródłowy zamawiającego i całkowicie nie mogę zrozumieć, co zwraca .natural (). OnResultOf (...)! Kod źródłowy to „public <F> Zamawianie <F> onResultOf”, nawet nie wiem jak się kompiluje! Co najważniejsze, jak użyć „<F> Zamawianie <F>” do sortowania mapy? Czy to jest komparator czy coś takiego? Dzięki.
smallufo,

Orderingjest po prostu bogaty Comparator. Próbowałem skomentować każdy przykład (kursywą pod każdym z nich). „naturalny” oznacza, że ​​przedmioty są Comparable; to jest jak porównywalny komponent Apache common. onResultOfstosuje funkcję do porównywanego elementu. Więc jeśli miałbyś funkcję, która dodała 1 do liczby całkowitej, to natural().onResultOf(add1Function).compare(1,2)by to zrobiła2.compareTo(3)
Stephen

ImmutableSortedMap.copyOf zgłasza IllegalArgumentException, jeśli w oryginalnej mapie znajdują się zduplikowane wartości.
lbalazscs

@Ibalazscs Tak to zrobi - powinieneś być w stanie używać ImmutableSetMultiMaplub ImmutableListMultiMapprzechowywać kolekcję duplikatów zmiennych.
Stephen

1
Dzięki za to wykorzystałem twoje rozwiązanie w jednym projekcie. Myślę jednak, że jest problem: aby zachowywać się jak mapa, musi zwrócić wartość poprzednio powiązaną z kluczem, jeśli istnieje, ale w ten sposób nigdy tego nie zrobi. Rozwiązaniem, które zastosowałem, jest zwrócenie usuniętej wartości, jeśli istnieje.
alex

185

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

16
Lista do posortowania to „nowy LinkedList”? Ojej. Na szczęście Collections.sort () najpierw zrzuca listę do tablicy, aby uniknąć właśnie tego rodzaju błędu (ale nadal, zrzut ArrayList do tablicy powinien być szybszy niż robienie tego samego dla LinkedList).
Dimitris Andreou

nie można przekonwertować z Iteratora na TernaryTree.Iterator
lisak

4
@ gg.kaspersky Nie mówię „źle sortować LinkedList”, ale sama LinkedList jest tutaj złym wyborem, niezależnie od sortowania. Znacznie lepiej jest użyć ArrayList, a dla dodatkowych punktów, zmień rozmiar dokładnie na map.size (). Zobacz także code.google.com/p/memory-measurer/wiki/… średni koszt elementu na ArrayList: 5 bajtów średni koszt elementu na LinkedList: 24 bajty. W przypadku ArrayList o dokładnie rozmiarze średni koszt wyniósłby 4 bajty. Oznacza to, że LinkedList zajmuje SZEŚĆ razy więcej pamięci, niż potrzebuje ArrayList. To po prostu wzdęcie
Dimitris Andreou

2
użycie powyższych wartości zostało posortowane w porządku rosnącym. Jak sortować malejąco
ram

1
Zamień o1 i o2, aby posortować malejąco.
Soheil

68

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

Jak posortować w odwrotnej kolejności?
Vlad Holubiev

6
znalazł rozwiązanie -Collections.reverseOrder(comparing(Entry::getValue))
Vlad Holubiev

1
Myślę, że widzę tam literówkę - czy „toMap” nie powinien być nazywany „Collectors.toMap ()”?
Jake Stokes

1
@JakeStokes Lub użyj importu statycznego :-)
assylias

6
Lepszym sposobem sortowania według wartości wpisu w odwrotnej kolejności jest:Entry.comparingByValue(Comparator.reverseOrder())
Gediminas Rimsa

31

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


Druga wersja może być bardziej zwięzła, jeśli zwrócisz List <Map.Entry <K, V >> To także ułatwia iterację i uzyskanie zarówno kluczy, jak i wartości bez konieczności wykonywania dodatkowych czynności na mapie. To wszystko przy założeniu, że nie masz nic przeciwko temu kodowi. Jeśli mapa podkładu lub posortowana lista są wspólne w środowisku wielowątkowym, wszystkie zakłady są wyłączone.
Mike Miller,

26

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.


Nie musisz korzystać z kolekcji commons. Java jest dostarczana z własnym java.util.TreeMap.
yoliho

2
Tak, ale TreeMap jest znacznie mniej elastyczny przy sortowaniu na wartości części mapentries.
p3t0r,

9
Problem z BidiMap polega na tym, że dodaje ograniczenie relacji 1: 1 między kluczami a wartościami, aby uczynić relację odwracalną (tzn. Oba klucze i wartości muszą być unikalne). Oznacza to, że nie można użyć tego do przechowywania czegoś takiego jak obiekt liczby słów, ponieważ wiele słów będzie miało tę samą liczbę.
Doug

26

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.


6
PROBLEM: jeśli chcesz użyć zwróconej mapy później, na przykład, aby sprawdzić, czy zawiera ona określony element, zawsze zostaniesz sfałszowany ze względu na własny komparator! Możliwe rozwiązanie: zamień ostatni wiersz na: zwróć nowy LinkedHashMap <K, V> (sortedByValues);
Erel Segal-Halevi

To wydaje mi się czystym rozwiązaniem, z wyjątkiem faktu, że @ErelSegalHalevi wskazał, że sprawdzenie, czy wartości istnieją na mapie, nie będzie możliwe, gdy podasz komparator. map.put („1”, „One”); map.put („2”, „Two”); map.put („3”, „Three”); map.put („4”, „Four”); map.put („5”, „Five”); map.containsKey („1”) zawsze zwróci false, jeśli zwrócisz nowy obiekt w funkcji sortByValues ​​(), np. zwróci nowy TreeMap <K, V> (sortedByValues); rozwiązuje problem. Dzięki Abhi
abhi

prawie tak samo jak odpowiedzi user157196 i Carter Page. Carter Page zawiera poprawkę LinkedHashMap
Kirby

Czwarta linia rozwiązania powinna być int porównaj = map.get (k1) .compareTo (map.get (k2)); jeśli potrzebujesz rosnącej kolejności
www.Decompiler.com

19

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.


Zwraca to listę wpisów zamiast mapy posortowanej według wartości. Inna wersja, która zwraca mapę: stackoverflow.com/a/22132422/829571
assylias

17

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}

W przypadku równości wartości zmieniłem wiersz „return 1”, aby porównać klucze: „return ((String) o1) .compareTo ((String) o2);”
gjgjgj

14

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.


Ta metoda jest znacznie łatwiejsza i bardziej intuicyjna niż tworzenie obiektu Map <V, List <K>> z prawie takim samym efektem. Wartości tak naprawdę nie powinny być kluczami w obiekcie mapy, a tak naprawdę szukasz listy w tej sytuacji, IMHO.
Jeff Wu

To rozwiązanie nie działa z wieloma wartościami, wkręciło się w moich obliczeniach (wartość powiązana z każdym kluczem)
Sam Levin

1
To jest dziwne. Czy mógłbyś opracować? Jaka była twoja produkcja i jakiej produkcji oczekiwałeś?
Lyudmil

12

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

11

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)


miałeś rację, w kodzie, który podałem na początku, był błąd! Mam nadzieję, że moja ostatnia edycja pomoże ci.
michel.iamit

9

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

8

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.


Jest niepoprawny, moja metoda działa, jeśli istnieją zduplikowane wartości. Użyłem go z mapami posiadającymi ponad 100 kluczy z „1” jako wartością.
Anthony

8

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

7

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
    }

Teraz, gdy dodasz dwa wpisy o równych wartościach, zostaną one scalone, powinieneś zwrócić 0, jeśli masz pewność, że obiekty są takie same (równe)
Masood_mj

7

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

Jeśli porównania i Komparator nie są dozwolone, to jak to zrobić?
Ved Prakash

Nie jestem pewien, czy rozumiem twój przypadek użycia, być może możesz to rozwinąć. Jeśli obiekt, którego chcesz użyć jako wartości, nie jest porównywalny, musisz go przekonwertować na obiekt, który jest.
David Bleckmann

6

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

Dzięki za tę skomentowaną wersję. Jedno pytanie: Jaka jest różnica w używaniu Entry.comparingByValue()(jako odpowiedzi assyli powyżej stackoverflow.com/a/22132422/1480587 ) lub comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)której użyłeś? Rozumiem, że porównujesz klucze, jeśli wartości są identyczne, prawda? Zauważyłem, że sortowanie utrzymuje porządek elementów o tej samej wartości - czy więc sortowanie według kluczy jest konieczne, jeśli klucze były już wcześniej sortowane?
Peter T.

6

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}


Wydaje mi się, że redukcja mapy naprawdę „Zmniejszyła” to… dobre rozwiązanie.
ha9u63ar

dzięki @ ha9u63ar
Arpan Saini

Działa, ale nie rozumiem, w jaki sposób kolejność elementów odgrywa rolę w HashMap?
Ali Tou

5

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


Nie rozumiem, dlaczego było to -1, jak dotąd LinkedHashMap jest prawdopodobnie najlepszym rozwiązaniem dla mnie, po prostu próbuję dowiedzieć się, ile kosztuje wyrzucenie i utworzenie nowej LinkedHashMap.
NobleUplift 18.04.16

5

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


Zgadza się, ale twój komparator nie obsługuje przypadku równych wartości
Sebastien Lorber,

5

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

4

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
}

Z drugiej strony może lepszym rozwiązaniem byłoby po prostu użycie mapy samo sortującej, w przypadku użycia org.apache.commons.collections.bidimap.TreeBidiMap
Maxim Veksler

4

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

Niniejszym przekazaliśmy na rzecz domeny publicznej.


4

Afaik najczystszym sposobem jest wykorzystanie kolekcji do sortowania mapy według wartości:

Map<String, Long> map = new HashMap<String, Long>();
// populate with data to sort on Value
// use datastructure designed for sorting

Queue queue = new PriorityQueue( map.size(), new MapComparable() );
queue.addAll( map.entrySet() );

// get a sorted map
LinkedHashMap<String, Long> linkedMap = new LinkedHashMap<String, Long>();

for (Map.Entry<String, Long> entry; (entry = queue.poll())!=null;) {
    linkedMap.put(entry.getKey(), entry.getValue());
}

public static class MapComparable implements Comparator<Map.Entry<String, Long>>{

  public int compare(Entry<String, Long> e1, Entry<String, Long> e2) {
    return e1.getValue().compareTo(e2.getValue());
  }
}

4

Kilka prostych zmian w celu uzyskania posortowanej mapy z parami, które mają zduplikowane wartości. W metodzie porównania (klasa ValueComparator), gdy wartości są równe, nie zwraca 0, ale zwraca wynik porównania 2 kluczy. Klucze są różne na mapie, więc udaje się zachować duplikaty wartości (które są przy okazji sortowane według kluczy). Powyższy przykład można zmodyfikować w następujący sposób:

    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 ((String)a).compareTo((String)b);
        } else {
          return -1;
        }
      }
    }

4

Na pewno rozwiązanie Stephena jest naprawdę świetne, ale dla tych, którzy nie mogą używać Guawy:

Oto moje rozwiązanie do sortowania według wartości mapy. To rozwiązanie obsługuje przypadek, w którym występuje dwukrotnie ta sama wartość itp.

// If you want to sort a map by value, and if there can be twice the same value:

// here is your original map
Map<String,Integer> mapToSortByValue = new HashMap<String, Integer>();
mapToSortByValue.put("A", 3);
mapToSortByValue.put("B", 1);
mapToSortByValue.put("C", 3);
mapToSortByValue.put("D", 5);
mapToSortByValue.put("E", -1);
mapToSortByValue.put("F", 1000);
mapToSortByValue.put("G", 79);
mapToSortByValue.put("H", 15);

// Sort all the map entries by value
Set<Map.Entry<String,Integer>> set = new TreeSet<Map.Entry<String,Integer>>(
        new Comparator<Map.Entry<String,Integer>>(){
            @Override
            public int compare(Map.Entry<String,Integer> obj1, Map.Entry<String,Integer> obj2) {
                Integer val1 = obj1.getValue();
                Integer val2 = obj2.getValue();
                // DUPLICATE VALUE CASE
                // If the values are equals, we can't return 0 because the 2 entries would be considered
                // as equals and one of them would be deleted (because we use a set, no duplicate, remember!)
                int compareValues = val1.compareTo(val2);
                if ( compareValues == 0 ) {
                    String key1 = obj1.getKey();
                    String key2 = obj2.getKey();
                    int compareKeys = key1.compareTo(key2);
                    if ( compareKeys == 0 ) {
                        // what you return here will tell us if you keep REAL KEY-VALUE duplicates in your set
                        // if you want to, do whatever you want but do not return 0 (but don't break the comparator contract!)
                        return 0;
                    }
                    return compareKeys;
                }
                return compareValues;
            }
        }
);
set.addAll(mapToSortByValue.entrySet());


// OK NOW OUR SET IS SORTED COOL!!!!

// And there's nothing more to do: the entries are sorted by value!
for ( Map.Entry<String,Integer> entry : set ) {
    System.out.println("Set entries: " + entry.getKey() + " -> " + entry.getValue());
}




// But if you add them to an hashmap
Map<String,Integer> myMap = new HashMap<String,Integer>();
// When iterating over the set the order is still good in the println...
for ( Map.Entry<String,Integer> entry : set ) {
    System.out.println("Added to result map entries: " + entry.getKey() + " " + entry.getValue());
    myMap.put(entry.getKey(), entry.getValue());
}

// But once they are in the hashmap, the order is not kept!
for ( Integer value : myMap.values() ) {
    System.out.println("Result map values: " + value);
}
// Also this way doesn't work:
// Logic because the entryset is a hashset for hashmaps and not a treeset
// (and even if it was a treeset, it would be on the keys only)
for ( Map.Entry<String,Integer> entry : myMap.entrySet() ) {
    System.out.println("Result map entries: " + entry.getKey() + " -> " + entry.getValue());
}


// CONCLUSION:
// If you want to iterate on a map ordered by value, you need to remember:
// 1) Maps are only sorted by keys, so you can't sort them directly by value
// 2) So you simply CAN'T return a map to a sortMapByValue function
// 3) You can't reverse the keys and the values because you have duplicate values
//    This also means you can't neither use Guava/Commons bidirectionnal treemaps or stuff like that

// SOLUTIONS
// So you can:
// 1) only sort the values which is easy, but you loose the key/value link (since you have duplicate values)
// 2) sort the map entries, but don't forget to handle the duplicate value case (like i did)
// 3) if you really need to return a map, use a LinkedHashMap which keep the insertion order

Wykonanie: http://www.ideone.com/dq3Lu

Wyjście:

Set entries: E -> -1
Set entries: B -> 1
Set entries: A -> 3
Set entries: C -> 3
Set entries: D -> 5
Set entries: H -> 15
Set entries: G -> 79
Set entries: F -> 1000
Added to result map entries: E -1
Added to result map entries: B 1
Added to result map entries: A 3
Added to result map entries: C 3
Added to result map entries: D 5
Added to result map entries: H 15
Added to result map entries: G 79
Added to result map entries: F 1000
Result map values: 5
Result map values: -1
Result map values: 1000
Result map values: 79
Result map values: 3
Result map values: 1
Result map values: 3
Result map values: 15
Result map entries: D -> 5
Result map entries: E -> -1
Result map entries: F -> 1000
Result map entries: G -> 79
Result map entries: A -> 3
Result map entries: B -> 1
Result map entries: C -> 3
Result map entries: H -> 15

Mam nadzieję, że pomoże to niektórym ludziom


3

Jeśli masz zduplikowane klucze i tylko niewielki zestaw danych (<1000), a Twój kod nie ma krytycznego wpływu na wydajność, możesz wykonać następujące czynności:

Map<String,Integer> tempMap=new HashMap<String,Integer>(inputUnsortedMap);
LinkedHashMap<String,Integer> sortedOutputMap=new LinkedHashMap<String,Integer>();

for(int i=0;i<inputUnsortedMap.size();i++){
    Map.Entry<String,Integer> maxEntry=null;
    Integer maxValue=-1;
    for(Map.Entry<String,Integer> entry:tempMap.entrySet()){
        if(entry.getValue()>maxValue){
            maxValue=entry.getValue();
            maxEntry=entry;
        }
    }
    tempMap.remove(maxEntry.getKey());
    sortedOutputMap.put(maxEntry.getKey(),maxEntry.getValue());
}

inputUnsortedMap to dane wejściowe do kodu.

Zmienna sortedOutputMap będzie zawierać dane w porządku malejącym po iteracji. Aby zmienić kolejność, po prostu zmień> na <w instrukcji if.

Nie jest najszybszym sortowaniem, ale wykonuje pracę bez żadnych dodatkowych zależności.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.