Sortieren Sie eine Karte <Schlüssel, Wert> nach Werten

1635

Ich bin relativ neu in Java und finde oft, dass ich eine sortieren muss Map<Key, Value> den Werten .

Da die Werte nicht eindeutig sind, konvertiere ich die keySetin eine arrayund sortiere dieses Array durch die Arraysortierung mit einem benutzerdefinierten Komparator , der nach dem mit dem Schlüssel verknüpften Wert sortiert.

Gibt es einen einfacheren Weg?

Lii
quelle
24
Eine Karte soll nicht sortiert werden, sondern ist schnell zugänglich. Objektgleiche Werte brechen die Einschränkung der Karte. Verwenden Sie den Eintragssatz wie List<Map.Entry<...>> list =new LinkedList(map.entrySet())und Collections.sort ....so.
Hannes
1
Ein Fall, in dem dies auftreten kann, wenn wir versuchen, einen Zähler in Java zu verwenden (Map <Object, Integer>). Das Sortieren nach Anzahl der Vorkommen wäre dann eine übliche Operation. Eine Sprache wie Python verfügt über eine integrierte Zählerdatenstruktur. Für eine alternative Art der Implementierung in Java ist hier ein Beispiel
Demongolem
7
Es gibt viele Anwendungsfälle für sortierte Karten. Deshalb haben Sie TreeMap und ConcurrentSkipListMap in jdk.
Alobodzk
1
TreeMap und ConcurrentSkipListMap nach Schlüssel sortieren. Die Frage betrifft die Sortierung nach Wert.
Peter

Antworten:

899

Hier ist eine generikfreundliche Version:

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;
    }
}
Carter Page
quelle
10
Ich bin froh, dass das hilft. John, die LinkedHashMap ist wichtig für die Lösung, da sie eine vorhersehbare Iterationsreihenfolge bietet.
Carter Seite
3
@ summ3791 Richtig. Dies wird bei jedem Sortieralgorithmus der Fall sein. Das Ändern des Werts von Knoten in einer Struktur während einer Sortierung führt zu unvorhersehbaren (und fast immer schlechten) Ergebnissen.
Carter Seite
3
@Sheagorath Ich habe es in Android versucht und es funktioniert auch. Dies ist kein plattformspezifisches Problem, wenn Sie die Java 6-Version verwenden. Haben Sie Comparable korrekt in Ihr Wertobjekt implementiert ?
Saiyancoder
6
Sollte die Java 8-Version nicht forEachOrderedstattdessen verwenden forEach, da in den Dokumenten der forEachZustände angegeben ist: "Das Verhalten dieser Operation ist explizit nicht deterministisch."?
Rob
1
total zerrissen, aber @CarterPage in den Kommentaren gutgeschrieben (es wird sowieso in einem Open-Source-Projekt sein). vielen Dank.
Nathan Beach
419

Wichtige Notiz:

Dieser Code kann auf verschiedene Arten unterbrochen werden. Wenn Sie den bereitgestellten Code verwenden möchten, lesen Sie auch die Kommentare, um sich der Auswirkungen bewusst zu sein. Beispielsweise können Werte nicht mehr mit ihrem Schlüssel abgerufen werden. ( getkehrt immer zurück null.)


Es scheint viel einfacher zu sein als alles oben Genannte. Verwenden Sie eine TreeMap wie folgt:

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

Ausgabe:

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}
Benutzer157196
quelle
18
Nicht mehr ( stackoverflow.com/questions/109383/… ). Warum gab es eine Besetzung für Double? Sollte es nicht einfach so sein return ((Comparable)base.get(a).compareTo(((Comparable)base.get(b)))?
Stephen
12
@Stephen: Nein. In diesem Fall werden alle gleichwertigen Schlüssel gelöscht (Differenz zwischen gleich und Vergleich durch Referenz). Zusätzlich: Auch dieser Code hat Probleme mit der folgenden Sequenz map.put("A","1d");map.put("B","1d");map.put("C",67d);map.put("D",99.5d);
steffen
43
Der für die Baumkarte verwendete Komparator stimmt nicht mit gleich überein (siehe sortMap javadox). Dies bedeutet, dass das Zurückziehen von Elementen aus der Baumkarte nicht funktioniert. sorted_map.get ("A") gibt null zurück. Das bedeutet, dass diese Verwendung der Baumkarte nicht funktioniert.
mR_fr0g
87
Nur für den Fall, dass es den Leuten nicht klar ist: Diese Lösung wird wahrscheinlich nicht das tun, was Sie wollen, wenn Sie mehrere Schlüssel haben, die demselben Wert zugeordnet sind - nur einer dieser Schlüssel wird im sortierten Ergebnis angezeigt.
Maxy-B
63
Louis Wasserman (ja, einer der Google Guava-Leute) mag diese Antwort eigentlich nicht so sehr: "Sie bricht auf mehrere wirklich verwirrende Arten, wenn man sie sogar lustig betrachtet. Wenn sich die Hintergrundkarte ändert, bricht sie. Wenn mehrere Schlüssel vorhanden sind Zuordnung auf den gleichen Wert, wird unterbrochen. Wenn Sie get für einen Schlüssel aufrufen, der nicht in der Hintergrundzuordnung enthalten ist, wird er unterbrochen. Wenn Sie irgendetwas tun, das zu einer Suche nach einem Schlüssel führt, der nicht vorhanden ist Die Karte - ein Map.equals-Aufruf, enthält Schlüssel, alles - wird mit wirklich seltsamen Stapelspuren brechen. " plus.google.com/102216152814616302326/posts/bEQLDK712MJ
Haylem
339

Java 8 bietet eine neue Antwort: Konvertieren Sie die Einträge in einen Stream und verwenden Sie die Komparator-Kombinatoren von Map.Entry:

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

Auf diese Weise können Sie die Einträge in aufsteigender Reihenfolge des Werts sortieren. Wenn Sie einen absteigenden Wert wünschen, kehren Sie einfach den Komparator um:

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

Wenn die Werte nicht vergleichbar sind, können Sie einen expliziten Komparator übergeben:

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

Sie können dann andere Stream-Vorgänge verwenden, um die Daten zu verbrauchen. Wenn Sie beispielsweise die Top 10 in einer neuen Karte anzeigen möchten:

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

Oder drucken Sie an System.out:

map.entrySet().stream()
   .sorted(Map.Entry.comparingByValue())
   .forEach(System.out::println);
Brian Goetz
quelle
Schön, aber was ist mit der Verwendung parallelStream()in diesem Fall?
Benj
11
Es funktioniert parallel. Möglicherweise sind die Kosten für das Zusammenführen von Karten zum Kombinieren der Teilergebnisse jedoch zu hoch und die parallele Version funktioniert möglicherweise nicht so gut, wie Sie es sich erhoffen. Aber es funktioniert und liefert die richtige Antwort.
Brian Goetz
Vielen Dank für Ihren nützlichen Rat. Es war genau das, was ich mich gefragt habe, obwohl es davon abhängt, welche Art von Schlüssel Sie verwenden und wie viele Parameter ... Das Wichtigste ist: "Es funktioniert und liefert die richtige Antwort."
Benj
2
Müssen Sie im Top10-Beispiel nicht compareByValue verwenden?
Leo
1
@Benj es wird in Bezug auf das Extrahieren der Top-10 funktionieren, aber die resultierende Karte wird nicht mehr bestellt.
OrangeDog
211

Drei einzeilige Antworten ...

Ich würde Google Collections Guava verwenden , um dies zu tun - wenn Ihre Werte sind Comparable, können Sie verwenden

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

Dadurch wird eine Funktion (ein Objekt) für die Karte erstellt [die eine der Tasten als Eingabe verwendet und den jeweiligen Wert zurückgibt] und dann eine natürliche (vergleichbare) Reihenfolge auf sie [die Werte] angewendet.

Wenn sie nicht vergleichbar sind, müssen Sie etwas in der Art von tun

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

Diese können nach einer Sortierung auf eine TreeMap (wie Orderingerweitert Comparator) oder eine LinkedHashMap angewendet werden

NB : Wenn Sie eine TreeMap verwenden möchten, denken Sie daran, dass bei einem Vergleich == 0 das Element bereits in der Liste enthalten ist (was passiert, wenn Sie mehrere Werte haben, die dasselbe vergleichen). Um dies zu vermeiden, können Sie Ihren Schlüssel wie folgt zum Komparator hinzufügen (vorausgesetzt, Ihre Schlüssel und Werte sind Comparable):

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

= Wenden Sie eine natürliche Reihenfolge auf den vom Schlüssel zugeordneten Wert an und kombinieren Sie diese mit der natürlichen Reihenfolge des Schlüssels

Beachten Sie, dass dies immer noch nicht funktionieren , wenn Sie Ihre Schlüssel auf 0 zu vergleichen, aber dies sollte für die meisten ausreichend sein , comparableGegenstände (wie hashCode, equalsund compareTosind oft synchron ...)

Siehe Ordering.onResultOf () und Functions.forMap () .

Implementierung

Jetzt, da wir einen Komparator haben, der macht, was wir wollen, müssen wir ein Ergebnis daraus ziehen.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Nun wird dies höchstwahrscheinlich funktionieren, aber:

  1. muss mit einer vollständigen fertigen Karte durchgeführt werden
  2. Versuchen Sie nicht die Komparatoren oben auf einem TreeMap; Es macht keinen Sinn, einen eingefügten Schlüssel zu vergleichen, wenn er erst nach dem Put einen Wert hat, dh er bricht sehr schnell

Punkt 1 ist für mich ein Deal-Breaker. Google-Sammlungen sind unglaublich faul (was gut ist: Sie können so ziemlich jeden Vorgang sofort ausführen; die eigentliche Arbeit ist erledigt, wenn Sie das Ergebnis verwenden), und dies erfordert das Kopieren einer ganzen Karte!

"Vollständige" Antwort / Live sortierte Karte nach Werten

Mach dir aber keine Sorgen; Wenn Sie genug davon besessen wären, eine "Live" -Karte auf diese Weise sortieren zu lassen, könnten Sie nicht eines, sondern beide (!) der oben genannten Probleme mit etwas Verrücktem wie dem folgenden lösen:

Hinweis: Dies hat sich im Juni 2012 erheblich geändert - der vorherige Code konnte niemals funktionieren: Zum Nachschlagen der Werte ist eine interne HashMap erforderlich, ohne eine Endlosschleife zwischen TreeMap.get()-> compare()und compare()-> zu erstellenget()

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

Wenn wir setzen, stellen wir sicher, dass die Hash-Map den Wert für den Komparator hat, und legen sie dann zum Sortieren in das TreeSet. Zuvor überprüfen wir jedoch die Hash-Map, um festzustellen, dass der Schlüssel kein Duplikat ist. Der von uns erstellte Komparator enthält auch den Schlüssel, damit doppelte Werte die nicht doppelten Schlüssel nicht löschen (aufgrund von == Vergleich). Diese beiden Elemente sind wichtig, um sicherzustellen, dass der Kartenvertrag eingehalten wird. Wenn Sie glauben, dass Sie das nicht wollen, sind Sie fast am Punkt, die Karte vollständig umzukehren Map<V,K>.

Der Konstruktor müsste als aufgerufen werden

 new ValueComparableMap(Ordering.natural());
 //or
 new ValueComparableMap(Ordering.from(comparator));
Stephen
quelle
Hallo @ Stephen, können Sie ein Beispiel für die Verwendung der Bestellung geben? Ich schaue in den Quellcode von Ordering und kann überhaupt nicht herausfinden, was .natural (). OnResultOf (...) zurückgibt! Der Quellcode lautet "public <F> Ordering <F> onResultOf", ich weiß sogar nicht, wie er kompiliert wird! Am wichtigsten ist, wie man "<F> Bestellung <F>" verwendet, um eine Karte zu sortieren? Ist es ein Komparator oder so? Vielen Dank.
Smallufo
Orderingist einfach ein reicher Comparator. Ich habe versucht, jedes Beispiel zu kommentieren (die Kursivschrift unter jedem Beispiel). "natürlich" zeigt an, dass die Objekte sind Comparable; Es ist wie der ComparableComparator von Apache Common. onResultOfWendet eine Funktion auf das zu vergleichende Element an. Wenn Sie also eine Funktion hätten, die einer Ganzzahl 1 hinzufügt, natural().onResultOf(add1Function).compare(1,2)würde dies am Ende geschehen2.compareTo(3)
Stephen
ImmutableSortedMap.copyOf löst eine IllegalArgumentException aus, wenn die ursprüngliche Map doppelte Werte enthält.
lbalazscs
@Ibalazscs Ja, das wird es - Sie sollten in der Lage sein, die Sammlung doppelter Variablen zu verwenden ImmutableSetMultiMapoder ImmutableListMultiMapzu enthalten.
Stephen
1
Vielen Dank dafür, ich habe Ihre Lösung in einem Projekt verwendet. Ich denke, es gibt ein Problem bei Put: Um sich wie eine Map zu verhalten, muss der zuvor mit dem Schlüssel verknüpfte Wert zurückgegeben werden, falls vorhanden, aber so wird es niemals funktionieren. Die Lösung, die ich verwendet habe, besteht darin, den entfernten Wert zurückzugeben, falls vorhanden.
Alex
185

Von 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;
}
devinmoore
quelle
16
Die zu sortierende Liste lautet "new LinkedList" ?? Gee. Zum Glück speichert Collections.sort () die Liste zuerst in einem Array, um genau diese Art von Fehler zu vermeiden (dennoch sollte das Speichern einer ArrayList in ein Array schneller sein als das gleiche für eine LinkedList).
Dimitris Andreou
kann nicht von Iterator zu TernaryTree konvertieren. Iterator
lisak
4
@ gg.kaspersky Ich sage nicht "es ist schlecht, eine LinkedList zu sortieren", aber diese LinkedList selbst ist hier eine schlechte Wahl, unabhängig von der Sortierung. Es ist viel besser, eine ArrayList zu verwenden und für zusätzliche Punkte die Größe genau auf map.size () festzulegen. Siehe auch code.google.com/p/memory-measurer/wiki/… durchschnittliche Kosten pro Element in ArrayList: 5 Bytes durchschnittliche Kosten pro Element in LinkedList: 24 Bytes. Für eine ArrayList mit exakter Größe betragen die durchschnittlichen Kosten 4 Byte. Das heißt, nimmt LinkedList SIX mal die Größe des Speichers , dass Arraylist muss. Es ist nur aufblähen
Dimitris Andreou
2
Die Verwendung der obigen Werte wurde in aufsteigender Reihenfolge sortiert. Wie sortiere ich absteigend?
Widder
1
Ersetzen Sie o1 und o2, um absteigend zu sortieren.
Soheil
68

Mit Java 8 können Sie die Stream-API verwenden, um dies wesentlich weniger ausführlich zu tun:

Map<K, V> sortedMap = map.entrySet().stream()
                         .sorted(Entry.comparingByValue())
                         .collect(Collectors.toMap(Entry::getKey, Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
Assylien
quelle
Wie sortiere ich es in umgekehrter Reihenfolge?
Vlad Holubiev
6
fand eine Lösung -Collections.reverseOrder(comparing(Entry::getValue))
Vlad Holubiev
1
Ich glaube, ich sehe dort einen Tippfehler - sollte die "toMap" nicht als "Collectors.toMap ()" bezeichnet werden?
Jake Stokes
1
@ JakeStokes Oder verwenden Sie einen statischen Import :-)
Assylias
6
Eine bessere Möglichkeit, nach Entry.comparingByValue(Comparator.reverseOrder())
Eingabewert
31

Zum Sortieren der Schlüssel muss der Komparator jeden Wert für jeden Vergleich nachschlagen. Eine skalierbarere Lösung würde das entrySet direkt verwenden, da der Wert dann für jeden Vergleich sofort verfügbar wäre (obwohl ich dies nicht durch Zahlen gesichert habe).

Hier ist eine generische Version von so etwas:

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

Es gibt Möglichkeiten, die Speicherrotation für die obige Lösung zu verringern. Die erste erstellte ArrayList kann beispielsweise als Rückgabewert wiederverwendet werden. Dies würde die Unterdrückung einiger allgemeiner Warnungen erfordern, aber es könnte sich für wiederverwendbaren Bibliothekscode lohnen. Außerdem muss der Komparator nicht bei jedem Aufruf neu zugewiesen werden.

Hier ist eine effizientere, wenn auch weniger ansprechende Version:

public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue2(Map<K, V> map) {
    final int size = map.size();
    final List reusedList = new ArrayList(size);
    final List<Map.Entry<K, V>> meView = reusedList;
    meView.addAll(map.entrySet());
    Collections.sort(meView, SINGLE);
    final List<K> keyView = reusedList;
    for (int i = 0; i < size; i++) {
        keyView.set(i, meView.get(i).getKey());
    }
    return keyView;
}

private static final Comparator SINGLE = new ValueComparator();

Wenn Sie kontinuierlich auf die sortierten Informationen zugreifen müssen (anstatt sie nur gelegentlich zu sortieren), können Sie eine zusätzliche Multi-Map verwenden. Lassen Sie mich wissen, wenn Sie weitere Details benötigen ...

Volleyball
quelle
Die zweite Version kann präziser sein, wenn Sie List <Map.Entry <K, V >> zurückgeben. Dies erleichtert auch das Iterieren und Abrufen der Schlüssel und Werte, ohne dass viele zusätzliche Zugriffe auf die Map erforderlich sind. Dies alles setzt voraus, dass Sie damit einverstanden sind, dass dieser Code threadsicher ist. Wenn die Hintergrundkarte oder die sortierte Liste in einer Multithread-Umgebung freigegeben werden, sind alle Wetten deaktiviert.
Mike Miller
26

Die Commons-Collections-Bibliothek enthält eine Lösung namens TreeBidiMap . Sie können sich auch die Google Collections-API ansehen. Es hat TreeMultimap, die Sie verwenden können.

Und wenn Sie dieses Framework nicht verwenden möchten, werden sie mit Quellcode geliefert.

p3t0r
quelle
Sie müssen die Commons-Sammlung nicht verwenden. Java wird mit einer eigenen java.util.TreeMap geliefert.
Yoliho
2
ja, aber TreeMap ist weit weniger flexibel , wenn auf dem Sortierwert Teil der mapentries.
p3t0r
9
Das Problem mit BidiMap besteht darin, dass eine 1: 1-Beziehungsbeschränkung zwischen Schlüsseln und Werten hinzugefügt wird, um die Beziehung invertierbar zu machen (dh, sowohl Schlüssel als auch Werte müssen eindeutig sein). Dies bedeutet, dass Sie damit nicht so etwas wie ein Wortzählungsobjekt speichern können, da viele Wörter dieselbe Anzahl haben.
Doug
26

Ich habe mir die gegebenen Antworten angesehen, aber viele davon sind komplizierter als nötig oder entfernen Kartenelemente, wenn mehrere Schlüssel den gleichen Wert haben.

Hier ist eine Lösung, die meiner Meinung nach besser passt:

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

Beachten Sie, dass die Karte vom höchsten zum niedrigsten Wert sortiert ist.

Anthony
quelle
6
PROBLEM: Wenn Sie die zurückgegebene Karte später verwenden möchten, um beispielsweise zu überprüfen, ob sie ein bestimmtes Element enthält, werden Sie aufgrund Ihres benutzerdefinierten Komparators immer falsch angezeigt! Eine mögliche Lösung: Ersetzen Sie die letzte Zeile durch: return new LinkedHashMap <K, V> (sortiertByValues);
Erel Segal-Halevi
Dies scheint mir eine saubere Lösung zu sein, mit Ausnahme der Tatsache, dass @ErelSegalHalevi darauf hingewiesen hat, dass es nicht möglich ist, zu überprüfen, ob die Werte in der Karte vorhanden sind, da Sie den Komparator angegeben haben. map.put ("1", "One"); map.put ("2", "Two"); map.put ("3", "Drei"); map.put ("4", "Four"); map.put ("5", "Five"); map.containsKey ("1") gibt immer false zurück, wenn Sie ein neues Objekt in der Funktion sortByValues ​​() zurückgeben, z. B. return new TreeMap <K, V> (sortiertByValues); löst das Problem. Danke Abhi
abhi
ziemlich genau wie die Antwort von user157196 und Carter Page. Carter Page's enthält den LinkedHashMap Fix
Kirby
Die vierte Zeile der Lösung sollte int compare = map.get (k1) .compareTo (map.get (k2)) sein. Wenn Sie aufsteigende Reihenfolge benötigen
www.Decompiler.com
19

So erreichen Sie dies mit den neuen Funktionen in Java 8:

import static java.util.Map.Entry.comparingByValue;
import static java.util.stream.Collectors.toList;

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

Die Einträge werden unter Verwendung des angegebenen Komparators nach ihren Werten geordnet. Wenn Ihre Werte miteinander vergleichbar sind, wird alternativ kein expliziter Komparator benötigt:

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

Die zurückgegebene Liste ist eine Momentaufnahme der angegebenen Karte zum Zeitpunkt des Aufrufs dieser Methode, sodass beide keine nachfolgenden Änderungen an der anderen widerspiegeln. Für eine iterierbare Live-Ansicht der Karte:

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

Das zurückgegebene iterable erstellt bei jeder Iteration einen neuen Schnappschuss der angegebenen Karte. Wenn also keine gleichzeitigen Änderungen vorgenommen werden, wird immer der aktuelle Status der Karte angezeigt.

gdejohn
quelle
Dies gibt eine Liste von Einträgen anstelle einer nach Wert sortierten Karte zurück. Andere Version, die eine Karte zurückgibt
assylias
17

Erstellen Sie einen benutzerdefinierten Komparator und verwenden Sie ihn beim Erstellen eines neuen TreeMap-Objekts.

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

    }
}

Verwenden Sie den folgenden Code in Ihrer Hauptfunktion

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

Ausgabe:

{B=75, D=50, C=50, A=35}
Sujan Reddy A.
quelle
Falls die Werte gleich sind, habe ich die Zeile "return 1" geändert, um die Schlüssel zu vergleichen: "return ((String) o1) .compareTo ((String) o2);"
Gjgjgj
14

Obwohl ich der Meinung bin, dass die ständige Notwendigkeit, eine Karte zu sortieren, wahrscheinlich ein Geruch ist, denke ich, dass der folgende Code der einfachste Weg ist, dies ohne Verwendung einer anderen Datenstruktur zu tun.

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

}}

Und hier ist ein peinlich unvollständiger Unit-Test:

public class MapUtilitiesTest extends TestCase {
public void testSorting() {
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    map.put("One", 1);
    map.put("Two", 2);
    map.put("Three", 3);

    List<Map.Entry<String, Integer>> sorted = MapUtilities.sortByValue(map);
    assertEquals("First", "One", sorted.get(0).getKey());
    assertEquals("Second", "Two", sorted.get(1).getKey());
    assertEquals("Third", "Three", sorted.get(2).getKey());
}

}}

Das Ergebnis ist eine sortierte Liste von Map.Entry-Objekten, aus denen Sie die Schlüssel und Werte abrufen können.

Lyudmil
quelle
Diese Methode ist viel einfacher und intuitiver als das Erstellen eines Map <V-, List <K>> -Objekts mit nahezu demselben Effekt. Die Werte sollten eigentlich keine Schlüssel in einem Map-Objekt sein. Was Sie wirklich suchen, ist eine Liste in dieser Situation, IMHO.
Jeff Wu
Diese Lösung funktioniert nicht mit vielen Werten, sondern mit meinen Zählungen (dem Wert, der jedem Schlüssel zugeordnet ist)
Sam Levin
1
Das ist seltsam. Könnten Sie näher darauf eingehen? Was war Ihre Ausgabe und was war die Ausgabe, die Sie erwartet haben?
Lyudmil
12

Verwenden Sie einen generischen Komparator wie:

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));
    }
}
RoyalBigorno
quelle
11

Die Antwort, für die am meisten gestimmt wurde, funktioniert nicht, wenn Sie 2 Elemente haben, die gleich sind. Die TreeMap lässt gleiche Werte aus.

das Beispiel: unsortierte Karte

Schlüssel / Wert: D / 67.3
Schlüssel / Wert: A / 99.5
Schlüssel / Wert: B / 67.4
Schlüssel / Wert: C / 67.5
Schlüssel / Wert: E / 99.5

Ergebnisse

Schlüssel / Wert: A / 99.5
Schlüssel / Wert: C / 67.5
Schlüssel / Wert: B / 67.4
Schlüssel / Wert: D / 67.3

Also lässt E weg !!

Für mich hat es gut funktioniert, den Komparator anzupassen, wenn er gleich ist, wird nicht 0, sondern -1 zurückgegeben.

im Beispiel:

Klasse ValueComparator implementiert Comparator {

Kartenbasis; public ValueComparator (Map base) {this.base = base; }}

public int compare (Objekt a, Objekt 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;
}

}}

jetzt kehrt es zurück:

unsortierte Karte:

Schlüssel / Wert: D / 67.3
Schlüssel / Wert: A / 99.5
Schlüssel / Wert: B / 67.4
Schlüssel / Wert: C / 67.5
Schlüssel / Wert: E / 99.5

Ergebnisse:

Schlüssel / Wert: A / 99.5
Schlüssel / Wert: E / 99.5
Schlüssel / Wert: C / 67.5
Schlüssel / Wert: B / 67.4
Schlüssel / Wert: D / 67.3

als Antwort auf Aliens (22. November 2011): Ich verwende diese Lösung für eine Karte mit ganzzahligen IDs und Namen, aber die Idee ist dieselbe, daher ist der obige Code möglicherweise nicht korrekt (ich werde ihn in einem Test schreiben und geben Sie den richtigen Code an), dies ist der Code für eine Kartensortierung, basierend auf der obigen Lösung:

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


}

und dies ist die Testklasse (ich habe sie gerade getestet, und dies funktioniert für die Ganzzahl, 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);
    }
}

Hier ist der Code für den Komparator einer Karte:

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

und das ist der Testfall dafür:

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

Natürlich können Sie dies viel allgemeiner machen, aber ich brauchte es nur für 1 Fall (die Karte)

michel.iamit
quelle
Sie hatten Recht, es gab einen Fehler in dem Code, den ich zuerst gab! Ich hoffe, meine letzte Bearbeitung wird Ihnen helfen.
michel.iamit
9

Anstatt Collections.sortwie manche zu verwenden, würde ich vorschlagen, zu verwenden Arrays.sort. Eigentlich Collections.sortmacht das so etwas:

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

Es ruft nur toArraydie Liste auf und verwendet dann Arrays.sort. Auf diese Weise werden alle Karteneinträge dreimal kopiert: einmal von der Karte in die temporäre Liste (sei es eine LinkedList oder ArrayList), dann in das temporäre Array und schließlich in die neue Karte.

Meine Lösung verzichtet auf diesen einen Schritt, da keine unnötige LinkedList erstellt wird. Hier ist der Code, generisch freundlich und leistungsoptimal:

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;
}
ciamej
quelle
8

Dies ist eine Variation von Anthonys Antwort, die bei doppelten Werten nicht funktioniert:

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

Beachten Sie, dass es ziemlich in der Luft liegt, wie man mit Nullen umgeht.

Ein wichtiger Vorteil dieses Ansatzes besteht darin, dass im Gegensatz zu einigen anderen hier angebotenen Lösungen tatsächlich eine Karte zurückgegeben wird.

Roger
quelle
Es ist falsch, meine Methode funktioniert, wenn doppelte Werte vorhanden sind. Ich habe es mit Karten mit mehr als 100 Schlüsseln mit "1" als Wert verwendet.
Anthony
8

Bester Ansatz

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

Ausgabe

java ==== 20

MAC ==== 26

C++ ==== 45

Unix ==== 67

Why this kolavari ==== 93
Nilesh Jadav
quelle
7

Hauptproblem. Wenn Sie die erste Antwort verwenden (Google führt Sie hierher), ändern Sie den Komparator, um eine Gleichheitsklausel hinzuzufügen. Andernfalls können Sie keine Werte aus der sortierten Karte nach Schlüsseln abrufen:

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
    }
cuneyt
quelle
Wenn Sie nun zwei Einträge mit gleichen Werten hinzufügen, werden diese zusammengeführt. Sie sollten nur 0 zurückgeben, wenn Sie sicher sind, dass die Objekte gleich (gleich) sind
Masood_mj
7

Es gibt bereits viele Antworten auf diese Frage, aber keine hat mir das geliefert, wonach ich gesucht habe, eine Kartenimplementierung, die Schlüssel und Einträge sortiert nach dem zugehörigen Wert zurückgibt und diese Eigenschaft beibehält, wenn Schlüssel und Werte in der Karte geändert werden. Zwei weitere Fragen stellen dies speziell.

Ich habe ein allgemeines freundliches Beispiel erfunden, das diesen Anwendungsfall löst. Diese Implementierung berücksichtigt nicht alle Verträge der Map-Schnittstelle, z. B. die Berücksichtigung von Wertänderungen und Entfernungen in den Mengen, die von keySet () und entrySet () im ursprünglichen Objekt zurückgegeben werden. Ich war der Meinung, dass eine solche Lösung zu groß wäre, um sie in eine Stapelüberlaufantwort aufzunehmen. Wenn es mir gelingt, eine vollständigere Implementierung zu erstellen, werde ich sie möglicherweise an Github senden und dann in einer aktualisierten Version dieser Antwort darauf verlinken.

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;
    }
}
David Bleckmann
quelle
Wenn Comparable und Comparator nicht erlaubt sind, wie geht das?
Ved Prakash
Ich bin mir nicht sicher, ob ich Ihren Anwendungsfall verstehe. Vielleicht können Sie das näher erläutern. Wenn das Objekt, das Sie als Wert verwenden möchten, nicht vergleichbar ist, müssen Sie es in ein Objekt konvertieren.
David Bleckmann
6

Späte Einreise.

Mit dem Aufkommen von Java-8 können wir Streams für die Datenmanipulation auf sehr einfache / prägnante Weise verwenden. Sie können Streams verwenden, um die Karteneinträge nach Wert zu sortieren und eine zu erstellen LinkedHashMap zu Einfügereihenfolge beibehalten wird Iteration.

Z.B:

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

Bei umgekehrter Reihenfolge ersetzen Sie:

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

mit

comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey).reversed()
Pankaj Singhal
quelle
Danke für diese kommentierte Version. Eine Frage: Was ist der Unterschied zwischen der Verwendung Entry.comparingByValue()(als Assylias-Antwort über stackoverflow.com/a/22132422/1480587 ) oder comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)der von Ihnen verwendeten? Ich verstehe, dass Sie auch Schlüssel vergleichen, wenn die Werte identisch sind, oder? Mir ist aufgefallen, dass die Sortierung die Reihenfolge der Elemente mit demselben Wert beibehält. Ist also eine Sortierung nach Schlüsseln erforderlich, wenn die Schlüssel bereits zuvor sortiert wurden?
Peter T.
6

Gegebene Karte

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

Sortieren Sie die Karte nach dem Wert in aufsteigender Reihenfolge

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

Sortieren Sie die Karte nach Wert in absteigender Reihenfolge

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

Ausgabe:

{Software = 50, Technologie = 70, USA = 100, Jobs = 200, Opportunity = 200}

{Jobs = 200, Opportunity = 200, USA = 100, Technologie = 70, Software = 50}

Arpan Saini
quelle
Ich denke, Map-Reduce hat es wirklich "reduziert" ... gute Lösung.
ha9u63ar
danke @ ha9u63ar
Arpan Saini
Es funktioniert, aber ich verstehe nicht, wie die Reihenfolge der Elemente in einer HashMap ins Spiel kommt.
Ali Tou
5

Abhängig vom Kontext, mit java.util.LinkedHashMap<T>welcher Erinnerung die Reihenfolge, in der Elemente in der Karte platziert werden. Andernfalls würde ich empfehlen, eine separate Liste zu führen, über die sortiert werden kann, wenn Sie Werte nach ihrer natürlichen Reihenfolge sortieren müssen Collections.sort().

Ryan Delucchi
quelle
Ich verstehe nicht, warum dies -1 war. Bisher ist LinkedHashMap wahrscheinlich die beste Lösung für mich. Ich versuche nur herauszufinden, wie teuer es ist, eine neue LinkedHashMap wegzuwerfen und zu erstellen.
NobleUplift
5

Da TreeMap <> nicht für Werte funktioniert , die gleich sein können, habe ich Folgendes verwendet:

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

Vielleicht möchten Sie eine Liste in eine LinkedHashMap einfügen , aber wenn Sie sie nur sofort durchlaufen , ist das überflüssig ...

Malix
quelle
Das ist richtig, aber Ihr Komparator behandelt nicht den Fall gleicher Werte
Sebastien Lorber
5

Das ist einfach zu kompliziert. Karten sollten nicht dazu dienen, sie nach Wert zu sortieren. Am einfachsten ist es, eine eigene Klasse zu erstellen, die Ihren Anforderungen entspricht.

Im unteren Beispiel sollten Sie TreeMap einen Komparator an der Stelle hinzufügen, an der sich * befindet. Mit der Java-API werden jedoch nur Komparatorschlüssel und keine Werte angegeben. Alle hier angegebenen Beispiele basieren auf 2 Karten. Ein Hash und ein neuer Baum. Welches ist seltsam.

Das Beispiel:

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

Ändern Sie die Karte folgendermaßen in ein Set:

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

Sie werden Klasse erstellen 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;
    }
}

und die Komparatorklasse:

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

Auf diese Weise können Sie problemlos weitere Abhängigkeiten hinzufügen.

Und als letzten Punkt füge ich einen einfachen Iterator hinzu:

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

Basierend auf @ devinmoore-Code, einer Kartensortierungsmethode, die Generika verwendet und sowohl aufsteigende als auch absteigende Reihenfolge unterstützt.

/**
 * 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
}
Maxim Veksler
quelle
Andererseits wäre eine bessere Lösung vielleicht, einfach eine selbstsortierende Karte zu verwenden, in dem Fall org.apache.commons.collections.bidimap.TreeBidiMap
Maxim Veksler
4

Hier ist eine OO-Lösung (dh verwendet keine staticMethoden):

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

Hiermit an die Public Domain gespendet.

Dave Jarvis
quelle
4

Afaik ist der sauberste Weg, Sammlungen zu verwenden, um die Karte nach Wert zu sortieren:

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

Einige einfache Änderungen, um eine sortierte Karte mit Paaren mit doppelten Werten zu erhalten. Geben Sie in der Vergleichsmethode (Klasse ValueComparator) bei gleichen Werten nicht 0 zurück, sondern das Ergebnis des Vergleichs der beiden Schlüssel. Schlüssel sind in einer Karte unterschiedlich, sodass es Ihnen gelingt, doppelte Werte beizubehalten (die übrigens nach Schlüsseln sortiert sind). Das obige Beispiel könnte also folgendermaßen geändert werden:

    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;
        }
      }
    }
dimkar
quelle
4

Sicher ist die Lösung von Stephen wirklich großartig, aber für diejenigen, die Guava nicht verwenden können:

Hier ist meine Lösung zum Sortieren einer Karte nach Wert. Diese Lösung behandelt den Fall, dass doppelt so viele Werte usw. vorliegen.

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

Die Exekutive: http://www.ideone.com/dq3Lu

Die Ausgabe:

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

Hoffe, es wird einigen Leuten helfen

Sebastien Lorber
quelle
3

Wenn Sie doppelte Schlüssel und nur einen kleinen Datensatz (<1000) haben und Ihr Code nicht leistungskritisch ist, können Sie einfach Folgendes tun:

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 ist die Eingabe in den Code.

Die Variable sortedOutputMap enthält die Daten in absteigender Reihenfolge, wenn sie wiederholt werden. Um die Reihenfolge zu ändern, ändern Sie in der if-Anweisung einfach> in <.

Ist nicht die schnellste Sortierung, erledigt den Job jedoch ohne zusätzliche Abhängigkeiten.

Nibor
quelle