Vraag Sorteer een kaart by values


Ik ben relatief nieuw voor Java en vind vaak dat ik een a moet sorteren Map<Key, Value> over de waarden.

Omdat de waarden niet uniek zijn, merk ik dat ik de keySet in een array, en die array doorzoeken array sort met een aangepaste comparator die sorteert op de waarde die is gekoppeld aan de sleutel.

Is er een gemakkelijkere manier?


1377


oorsprong


antwoorden:


Hier is een generieke-vriendelijke versie:

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

783



Belangrijke notitie:

Deze code kan op verschillende manieren worden verbroken. Als u van plan bent de verstrekte code te gebruiken, lees dan ook de opmerkingen om op de hoogte te zijn van de implicaties. Waarden kunnen bijvoorbeeld niet meer worden opgehaald met hun sleutel. (get keert altijd terug null.)


Het lijkt veel gemakkelijker dan al het voorgaande. Gebruik een TreeMap als volgt:

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

Output:

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}

405



Java 8 biedt een nieuw antwoord: converteer de vermeldingen naar een stream en gebruik de comparatorcombinators van Map.Entry:

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

Hiermee kunt u de items in oplopende volgorde van waarde sorteren. Als u een dalende waarde wilt, zet u eenvoudigweg de comparator om:

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

Als de waarden niet vergelijkbaar zijn, kunt u een expliciete vergelijker doorgeven:

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

U kunt vervolgens doorgaan met het gebruik van andere stroombewerkingen om de gegevens te verbruiken. Als u bijvoorbeeld de top 10 op een nieuwe kaart wilt:

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

Of afdrukken naar System.out:

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

213



Drie antwoorden van 1 regel ...

Ik zou gebruiken Google Collections  guava om dit te doen - als je waarden zijn Comparable dan kan je gebruiken

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

Die een functie (object) zal maken voor de kaart [die een van de toetsen als invoer neemt, de respectieve waarde retourneert], en vervolgens een natuurlijke (vergelijkbare) volgorde aan [de waarden] aanbrengt.

Als ze niet vergelijkbaar zijn, moet je iets doen in de trant van

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

Deze kunnen worden toegepast op een TreeMap (als Ordering strekt Comparator), of a LinkedHashMap na wat sorteren

NB: Als u een TreeMap gaat gebruiken, onthoud dan dat als een vergelijking == 0 is, het item al in de lijst staat (wat gebeurt als u meerdere waarden heeft die hetzelfde vergelijken). Om dit te verminderen, zou je je sleutel kunnen toevoegen aan de comparator zoals zo (in de veronderstelling dat je sleutels en waarden zijn Comparable):

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

= Pas natuurlijke volgorde toe op de waarde die is toegewezen door de sleutel, en verdeel dat met de natuurlijke volgorde van de sleutel

Merk op dat dit nog steeds niet werkt als uw toetsen zich verhouden tot 0, maar dit zou voor de meesten voldoende moeten zijn comparable items (als hashCode, equals en compareTo zijn vaak synchroon ...)

Zien Ordering.onResultOf () en Functions.forMap ().

Implementatie

Dus nu dat we een comparator hebben die doet wat we willen, moeten we er een resultaat van krijgen.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Dit zal waarschijnlijk werken, maar:

  1. moet worden gedaan met een volledig afgewerkte kaart
  2. Probeer de comparators hierboven niet op a TreeMap; het heeft geen zin om een ​​ingevoegde sleutel te vergelijken wanneer deze pas na de put een waarde heeft, d.w.z. hij zal echt snel breken

Punt 1 is een beetje een deal-breaker voor mij; google collections is ongelooflijk lui (wat goed is: je kunt vrijwel elke operatie in een oogwenk doen, het echte werk is gedaan wanneer je het resultaat begint te gebruiken), en dit vereist het kopiëren van een geheel kaart!

"Volledig" antwoord / Live gesorteerd op basis van waarden

Maak je echter geen zorgen; als je genoeg geobsedeerd was door een "live" kaart op deze manier te laten sorteren, zou je niet één, maar allebei (!) van de bovenstaande problemen kunnen oplossen met iets geks zoals het volgende:

Opmerking: dit is in juni 2012 aanzienlijk veranderd - de vorige code zou nooit kunnen werken: een interne HashMap is vereist om de waarden op te zoeken zonder een oneindige lus te creëren tussen de TreeMap.get() -> compare() en 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"));
    }
 }

Wanneer we dit doen, zorgen we ervoor dat de hash-kaart de waarde heeft voor de comparator en vervolgens ter sortering naar de TreeSet. Maar daarvoor controleren we de hash-kaart om te zien dat de sleutel geen duplicaat is. De vergelijker die we maken, zal ook de sleutel bevatten zodat dubbele waarden de niet-dubbele sleutels niet verwijderen (vanwege == vergelijking). Deze 2 items zijn vitaal om ervoor te zorgen dat het kaartcontract wordt bewaard; als je denkt dat je dat niet wilt, dan ben je bijna op het punt om de kaart volledig om te keren (naar Map<V,K>).

De constructor moet worden genoemd als

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

207



Van http://www.programmersheaven.com/download/49349/download.aspx

private static <K, V> Map<K, V> sortByValue(Map<K, V> map) {
    List<Entry<K, V>> list = new LinkedList<>(map.entrySet());
    Collections.sort(list, new Comparator<Object>() {
        @SuppressWarnings("unchecked")
        public int compare(Object o1, Object o2) {
            return ((Comparable<V>) ((Map.Entry<K, V>) (o1)).getValue()).compareTo(((Map.Entry<K, V>) (o2)).getValue());
        }
    });

    Map<K, V> result = new LinkedHashMap<>();
    for (Iterator<Entry<K, V>> it = list.iterator(); it.hasNext();) {
        Map.Entry<K, V> entry = (Map.Entry<K, V>) it.next();
        result.put(entry.getKey(), entry.getValue());
    }

    return result;
}

171



Voor het sorteren van de sleutels moet de comparator elke waarde voor elke vergelijking opzoeken. Een meer schaalbare oplossing zou de entrySet direct gebruiken, aangezien de waarde dan onmiddellijk beschikbaar zou zijn voor elke vergelijking (hoewel ik dit niet met een aantal getallen heb ondersteund).

Hier is een generieke versie van zoiets:

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

Er zijn manieren om geheugenrotatie voor de bovenstaande oplossing te verminderen. De eerste gecreëerde ArrayList kan bijvoorbeeld opnieuw worden gebruikt als retourwaarde; dit zou onderdrukking van sommige generieke waarschuwingen vereisen, maar het zou de moeite waard kunnen zijn voor herbruikbare bibliotheekcode. Ook hoeft de comparator niet bij elke aanroep opnieuw te worden toegewezen.

Hier is een efficiëntere, zij het minder aansprekende versie:

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

Als u ten slotte continu toegang wilt hebben tot de gesorteerde informatie (in plaats van deze af en toe alleen maar te sorteren), kunt u een extra multi- map gebruiken. Laat me weten of je meer informatie nodig hebt ...


28



Met Java 8 kunt u de streamt api om het op een aanzienlijk minder uitgebreide manier te doen:

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

26