java Ordina una mappa <Chiave, Valore> per valori





15 Answers

Nota importante:

Questo codice può rompersi in più modi. Se intendi utilizzare il codice fornito, assicurati di leggere anche i commenti per essere consapevole delle implicazioni. Ad esempio, i valori non possono più essere recuperati dalla loro chiave. ( get sempre restituisce null .)

Sembra molto più facile di tutto quanto sopra. Usa una TreeMap come segue:

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

Produzione:

unsorted map: {D=67.3, A=99.5, B=67.4, C=67.4}
results: {D=67.3, B=67.4, C=67.4, A=99.5}
java sorting dictionary collections

Sono relativamente nuovo a Java e spesso trovo che ho bisogno di ordinare una Map<Key, Value> sui valori.

Poiché i valori non sono univoci, mi ritrovo a convertire keySet in un array e a ordinare l'array attraverso l' ordinamento di array con un comparatore personalizzato che ordina il valore associato alla chiave.

C'è un modo più semplice?




Tre risposte a 1 riga ...

Vorrei utilizzare Google Collections Guava per farlo - se i tuoi valori sono Comparable , puoi utilizzare

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

Che creerà una funzione (oggetto) per la mappa [che accetta uno qualsiasi dei tasti come input, restituendo il rispettivo valore], e quindi applica loro ordinamento naturale (comparabile) [i valori].

Se non sono comparabili, allora dovrai fare qualcosa sulla falsariga di

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

Questi possono essere applicati a una TreeMap (come Ordering extends Comparator ), o a LinkedHashMap dopo alcuni ordinamenti

NB : Se stai per utilizzare una TreeMap, ricorda che se un confronto == 0, allora l'elemento è già nella lista (che avverrà se hai più valori che confrontano lo stesso). Per ovviare a questo, potresti aggiungere la tua chiave al comparatore in questo modo (presumendo che le tue chiavi e i tuoi valori siano Comparable ):

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

= Applicare l'ordinamento naturale al valore mappato dalla chiave e combinarlo con l'ordinamento naturale della chiave

Nota che questo non funzionerà se le tue chiavi sono paragonabili a 0, ma dovrebbe essere sufficiente per la maggior parte degli articoli comparable (come hashCode , equals e compareTo sono spesso sincronizzati ...)

Vedi Ordering.onResultOf() e Functions.forMap() .

Implementazione

Quindi ora che abbiamo un comparatore che fa ciò che vogliamo, dobbiamo ottenere un risultato da esso.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Ora molto probabilmente funzionerà, ma:

  1. deve essere fatto con una mappa completa e completa
  2. Non provare i comparatori sopra su una TreeMap ; non ha senso cercare di confrontare una chiave inserita quando non ha un valore fino a dopo la put, cioè si romperà molto velocemente

Il punto 1 è un po 'un affare per me; le collezioni google sono incredibilmente pigre (il che è un bene: puoi fare praticamente tutte le operazioni in un istante, il vero lavoro è fatto quando inizi a usare il risultato), e questo richiede la copia di un'intera mappa!

Risposta "Completa" / Mappa ordinata dal vivo in base ai valori

Non preoccuparti però; se fossi ossessionato abbastanza da avere una mappa "live" in questo modo, potresti risolvere non uno, ma entrambi (!) dei suddetti problemi con qualcosa di pazzo come il seguente:

Nota: questo è cambiato significativamente a giugno 2012 - il codice precedente non potrebbe mai funzionare: è necessario un HashMap interno per cercare i valori senza creare un ciclo infinito tra TreeMap.get() -> compare() e 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"));
    }
 }

Quando lo inseriamo, ci assicuriamo che la mappa hash abbia il valore per il comparatore e poi la collochiamo al TreeSet per l'ordinamento. Ma prima di ciò controlliamo la mappa hash per vedere che la chiave non è in realtà un duplicato. Inoltre, il comparatore che creiamo includerà anche la chiave in modo che i valori duplicati non cancellino le chiavi non duplicate (a causa del confronto ==). Questi 2 articoli sono essenziali per garantire che il contratto cartografico venga mantenuto; se pensi di non volerlo, allora sei quasi sul punto di invertire completamente la mappa (su Map<V,K> ).

Il costruttore dovrebbe essere chiamato come

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



Con Java 8, puoi usare gli stream api per farlo in un modo significativamente meno dettagliato:

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



La libreria commons-collections contiene una soluzione chiamata TreeBidiMap . Oppure, potresti dare un'occhiata all'API delle raccolte Google. Ha TreeMultimap che è possibile utilizzare.

E se non vuoi usare questi framework ... vengono con il codice sorgente.




Per fare ciò con le nuove funzionalità di 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());
}

Le voci sono ordinate in base ai loro valori usando il comparatore dato. In alternativa, se i tuoi valori sono comparabili tra loro, non è necessario alcun comparatore esplicito:

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

La lista restituita è un'istantanea della mappa data al momento in cui viene chiamato questo metodo, quindi nessuno dei due rifletterà le successive modifiche all'altra. Per una visione iterabile della mappa:

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

L'iterabile restituito crea una nuova istantanea della mappa specificata ogni volta che viene iterata, quindi escludendo modifiche simultanee, rifletterà sempre lo stato corrente della mappa.




Crea un comparatore personalizzato e usalo mentre crei un nuovo oggetto 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));

    }
}

Usa il codice seguente nella tua funzione principale

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

Produzione:

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



Utilizzare un comparatore generico come:

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



Questa è una variante della risposta di Anthony, che non funziona se ci sono valori duplicati:

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

Si noti che è piuttosto in aria come gestire i null.

Un importante vantaggio di questo approccio è che in realtà restituisce una mappa, a differenza di alcune delle altre soluzioni offerte qui.




Miglior approccio

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

Produzione

java ==== 20

MAC ==== 26

C++ ==== 45

Unix ==== 67

Why this kolavari ==== 93



A seconda del contesto, utilizzando il java.util.LinkedHashMap<T>quale viene ricordato l'ordine in cui gli oggetti sono inseriti nella mappa. Altrimenti, se hai bisogno di ordinare i valori in base al loro ordinamento naturale, ti consiglio di mantenere un elenco separato che può essere ordinato tramite Collections.sort().




Questo è semplicemente troppo complicato. Le mappe non dovevano fare un lavoro come ordinarle per valore. Il modo più semplice è creare la tua classe in modo che soddisfi le tue esigenze.

Nell'esempio in basso si suppone di aggiungere TreeMap a un comparatore nel punto in cui * è. Ma con l'API java fornisce solo chiavi di confronto, non valori. Tutti gli esempi indicati qui si basano su 2 mappe. Un hash e un nuovo albero. Che è strano

L'esempio:

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

Quindi modifica la mappa in un set in questo modo:

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

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

e la classe Comparator:

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

In questo modo puoi facilmente aggiungere più dipendenze.

E come ultimo punto aggiungerò un semplice iteratore:

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



Ecco una soluzione OO (cioè, non usa staticmetodi):

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

Con la presente donato al pubblico dominio.




Alcune semplici modifiche per avere una mappa ordinata con coppie che hanno valori duplicati. Nel metodo di confronto (class ValueComparator) quando i valori sono uguali non restituiscono 0 ma restituiscono il risultato del confronto delle 2 chiavi. Le chiavi sono distinte in una mappa in modo da riuscire a mantenere valori duplicati (che sono ordinati per chiavi). Quindi l'esempio sopra potrebbe essere modificato in questo modo:

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



Se hai chiavi duplicate e solo un piccolo set di dati (<1000) e il tuo codice non è critico dal punto di vista delle prestazioni, puoi semplicemente fare quanto segue:

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 è l'input per il codice.

La variabile sortedOutputMap conterrà i dati in ordine decrescente al termine di iterazione. Per cambiare l'ordine basta cambiare> in una <nell'istruzione if.

Non è il tipo più veloce ma fa il lavoro senza alcuna dipendenza aggiuntiva.




Puoi provare le multimaps di Guava:

TreeMap<Integer, Collection<String>> sortedMap = new TreeMap<>(
        Multimaps.invertFrom(Multimaps.forMap(originalMap), 
        ArrayListMultimap.<Integer, String>create()).asMap());

Di conseguenza ottieni una mappa dai valori originali alle raccolte di chiavi che corrispondono a loro. Questo approccio può essere utilizzato anche se ci sono più chiavi per lo stesso valore.




Related