java hashmap - Ordina una mappa<Chiave, Valore>per valori




put and (25)

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?


Answers

La risposta votata per la maggior parte non funziona quando si hanno 2 articoli uguali. la TreeMap lascia fuori valori uguali.

l'exmaple: mappa non ordinata

key/value: D/67.3
key/value: A/99.5
key/value: B/67.4
key/value: C/67.5
key/value: E/99.5

risultati

key/value: A/99.5
key/value: C/67.5
key/value: B/67.4
key/value: D/67.3

Così esce E !!

Per me ha funzionato bene per regolare il comparatore, se uguale non restituisce 0 ma -1.

nell'esempio:

class ValueComparator implementa Comparator {

Base della mappa; public ValueComparator (base della mappa) {this.base = base; }

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 -1;
} else {
  return -1;
}

}}

ora restituisce:

mappa non ordinata:

key/value: D/67.3
key/value: A/99.5
key/value: B/67.4
key/value: C/67.5
key/value: E/99.5

i risultati:

key/value: A/99.5
key/value: E/99.5
key/value: C/67.5
key/value: B/67.4
key/value: D/67.3

come risposta a Aliens (2011, 22 novembre): Sto usando questa soluzione per una mappa di ID di interi e nomi, ma l'idea è la stessa, quindi potrebbe essere che il codice sopra non sia corretto (lo scriverò in un test e darti il ​​codice corretto), questo è il codice per l'ordinamento di una mappa, basato sulla soluzione di cui sopra:

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


}

e questa è la classe di test (l'ho appena testata, e questo funziona per l'Integer, String Map:

package test.nl.iamit.util;

import java.util.HashMap;
import java.util.TreeMap;
import nl.iamit.util.Comparators;
import org.junit.Test;
import static org.junit.Assert.assertArrayEquals;

public class TestComparators {


    @Test
    public void testMapIntegerStringComparator(){
        HashMap<Integer, String> unSoretedMap = new HashMap<Integer, String>();
        Comparators.MapIntegerStringComparator bvc = new Comparators.MapIntegerStringComparator(
                unSoretedMap);
        TreeMap<Integer, String> sorted_map = new TreeMap<Integer, String>(bvc);
        //the testdata:
        unSoretedMap.put(new Integer(1), "E");
        unSoretedMap.put(new Integer(2), "A");
        unSoretedMap.put(new Integer(3), "E");
        unSoretedMap.put(new Integer(4), "B");
        unSoretedMap.put(new Integer(5), "F");

        sorted_map.putAll(unSoretedMap);

        Object[] targetKeys={new Integer(2),new Integer(4),new Integer(3),new Integer(1),new Integer(5) };
        Object[] currecntKeys=sorted_map.keySet().toArray();

        assertArrayEquals(targetKeys,currecntKeys);
    }
}

ecco il codice per il comparatore di una mappa:

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

e questo è il banco di prova per questo:

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

di cource puoi renderlo molto più generico, ma ne avevo solo bisogno per 1 caso (la mappa)


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

Ecco una versione generica:

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

Ordinare le chiavi richiede al Comparatore di cercare ogni valore per ogni confronto. Una soluzione più scalabile userebbe direttamente la entrySet, dal momento che il valore sarebbe immediatamente disponibile per ogni confronto (anche se non l'ho supportato con i numeri).

Ecco una versione generica di una cosa del genere:

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

Ci sono modi per ridurre la rotazione della memoria per la soluzione di cui sopra. Il primo ArrayList creato potrebbe ad esempio essere riutilizzato come valore di ritorno; ciò richiederebbe la soppressione di alcuni avvertimenti generici, ma potrebbe valerne la pena per codice libreria riutilizzabile. Inoltre, il comparatore non deve essere ridistribuito ad ogni richiamo.

Ecco una versione più efficiente anche se meno attraente:

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

Infine, se è necessario accedere continuamente alle informazioni ordinate (anziché ordinarle una volta ogni tanto), è possibile utilizzare una mappa multipla aggiuntiva. Fammi sapere se hai bisogno di più dettagli...


Ho unito le soluzioni di user157196 e Carter Page:

class MapUtil {

    public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue( Map<K, V> map ){
        ValueComparator<K,V> bvc =  new ValueComparator<K,V>(map);
        TreeMap<K,V> sorted_map = new TreeMap<K,V>(bvc);
        sorted_map.putAll(map);
        return sorted_map;
    }

}

class ValueComparator<K, V extends Comparable<? super V>> implements Comparator<K> {

    Map<K, V> base;
    public ValueComparator(Map<K, V> base) {
        this.base = base;
    }

    public int compare(K a, K b) {
        int result = (base.get(a).compareTo(base.get(b)));
        if (result == 0) result=1;
        // returning 0 would merge keys
        return result;
    }
}

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.


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.


Problema principale. Se utilizzi la prima risposta (Google ti porta qui), modifica il comparatore per aggiungere una clausola uguale, altrimenti non puoi ottenere valori dalla tastiera Sort_map per chiavi:

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
    }

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.


Invece di usare Collections.sortcome alcuni consiglierei di usare Arrays.sort. In realtà ciò Collections.sortche è è qualcosa del genere:

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

Semplicemente chiama toArraysulla lista e poi usa Arrays.sort. In questo modo tutte le voci della mappa verranno copiate tre volte: una volta dalla mappa alla lista temporanea (sia essa una LinkedList o ArrayList), quindi alla matrice temporanea e infine alla nuova mappa.

La mia soluzione ommits questo passaggio in quanto non crea LinkedList non necessario. Ecco il codice, generico e ottimizzato per le prestazioni:

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

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.


Poiché TreeMap <> non funziona per valori che possono essere uguali, ho usato questo:

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

Potresti voler mettere la lista in una LinkedHashMap , ma se stai andando ad iterarlo subito, è superfluo ...


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

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

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

Java 8 offre una nuova risposta: converti le voci in un flusso e utilizza i combinatori di comparatori da Map.Entry:

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

Questo ti permetterà di consumare le voci ordinate in ordine crescente di valore. Se vuoi un valore decrescente, inverti semplicemente il comparatore:

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

Se i valori non sono confrontabili, puoi passare un comparatore esplicito:

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

È quindi possibile continuare a utilizzare altre operazioni di streaming per consumare i dati. Ad esempio, se desideri i primi 10 in una nuova mappa:

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

Oppure stampa su System.out :

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

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}

Ci sono già molte risposte a questa domanda, ma nessuna mi ha fornito ciò che stavo cercando, un'implementazione della mappa che restituisce chiavi e voci ordinate in base al valore associato e mantiene questa proprietà come chiavi e i valori vengono modificati nella mappa. other due questions chiedono specificamente questo.

Ho preparato un esempio amichevole generico che risolve questo caso d'uso. Questa implementazione non onora tutti i contratti dell'interfaccia Map, come ad esempio riflettere le modifiche di valore e le rimozioni nei set restituiti da keySet () e entrySet () nell'oggetto originale. Ho sentito che una soluzione del genere sarebbe troppo grande per includere una risposta di Overflow dello stack. Se riesco a creare un'implementazione più completa, forse la pubblicherò su Github e poi collegherò in una versione aggiornata di questa risposta.

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

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.


Mentre sono d'accordo sul fatto che la costante necessità di ordinare una mappa è probabilmente un odore, penso che il seguente codice sia il modo più semplice per farlo senza utilizzare una struttura dati diversa.

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

}

Ed ecco un test unitario imbarazzante incompleto:

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

}

Il risultato è un elenco ordinato di oggetti Map.Entry, da cui è possibile ottenere le chiavi e i valori.


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

Afaik il modo più semplice è utilizzare le raccolte per ordinare la mappa sul valore:

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

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

Ecco il modo più semplice e conciso, anche se non so come si confronta in termini di cicli della CPU. Funziona alla grande se vuoi solo sapere se la radice è un numero intero. Se ti interessa davvero se è un numero intero, puoi anche capirlo. Ecco una funzione semplice (e pura):

public static boolean isRootWhole(double number) {
    return Math.sqrt(number) % 1 == 0;
}

Se non hai bisogno di micro-ottimizzazione, questa risposta è migliore in termini di semplicità e manutenibilità. Se si ottengono numeri negativi, forse si vorrà utilizzare Math.abs () sull'argomento numero come argomento Math.sqrt ().

Sulla mia CPU Intel i7-4790 da 3,6 Ghz, una corsa di questo algoritmo su 0 - 10.000.000 ha richiesto una media di 35 - 37 nanosecondi per calcolo. Ho eseguito 10 sequenze sequenziali, stampando il tempo medio trascorso su ciascuno dei dieci milioni di calcoli sqrt. Per completare la corsa totale, sono necessari poco più di 600 ms.

Se si sta eseguendo un numero minore di calcoli, i calcoli precedenti richiedono più tempo.





java sorting dictionary collections