Pregunta Ordenar un mapa por valores


Soy relativamente nuevo en Java, y a menudo encuentro que necesito ordenar un Map<Key, Value> en los valores.

Como los valores no son únicos, me encuentro convirtiendo el keySet en una arrayy clasificando esa matriz tipo de matriz con un comparador personalizado eso depende del valor asociado con la clave.

hay una manera mas facil?


1377


origen


Respuestas:


Aquí hay una versión genérica amigable:

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



Nota IMPORTANTE:

Este código puede romperse de múltiples maneras. Si tiene la intención de usar el código provisto, asegúrese de leer los comentarios y estar al tanto de las implicaciones. Por ejemplo, los valores ya no pueden ser recuperados por su clave. (get siempre regresa null.)


Parece mucho más fácil que todo lo anterior. Use un TreeMap de la siguiente manera:

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

Salida:

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 ofrece una nueva respuesta: convierte las entradas en una secuencia y utiliza los combinadores de comparación de Map.Entry:

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

Esto le permitirá consumir las entradas ordenadas en orden ascendente de valor. Si desea un valor descendente, simplemente invierta el comparador:

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

Si los valores no son comparables, puede pasar un comparador explícito:

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

Luego puede proceder a usar otras operaciones de flujo para consumir los datos. Por ejemplo, si quiere los 10 primeros en un nuevo mapa:

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

O imprimir a System.out:

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

213



Tres respuestas de 1 línea ...

yo usaría Colecciones de Google  Guayaba para hacer esto - si tus valores son Comparable entonces puedes usar

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

Lo cual creará una función (objeto) para el mapa [que toma cualquiera de las teclas como entrada, devolviendo el valor respectivo], y luego aplicando un orden natural (comparable) a ellas [los valores].

Si no son comparables, entonces tendrá que hacer algo similar a

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

Estos se pueden aplicar a un TreeMap (como Ordering se extiende Comparator), o un LinkedHashMap después de algunas clasificaciones

nótese bien: Si vas a utilizar un TreeMap, recuerda que si una comparación == 0, entonces el elemento ya está en la lista (lo que sucederá si tienes varios valores que comparan el mismo). Para aliviar esto, puede agregar su clave al comparador como tal (suponiendo que sus claves y valores son Comparable)

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

= Aplique ordenamiento natural al valor asignado por la clave y compárelo con el orden natural de la clave

Tenga en cuenta que esto no funcionará si sus claves se comparan con 0, pero esto debería ser suficiente para la mayoría comparable artículos (como hashCode, equals y compareTo a menudo están sincronizados ...)

Ver Ordering.onResultOf () y Functions.forMap ().

Implementación

Entonces, ahora que tenemos un comparador que hace lo que queremos, necesitamos obtener un resultado.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Ahora bien, es probable que esto funcione, pero:

  1. debe hacerse dado un mapa completo terminado
  2. No intente los comparadores de arriba en un TreeMap; no tiene sentido tratar de comparar una clave insertada cuando no tiene un valor hasta después de la puesta, es decir, se romperá muy rápido

El punto 1 es un poco rompedor de ofertas para mí; google collections es increíblemente vago (lo cual es bueno: puedes hacer casi todas las operaciones en un instante; el trabajo real se hace cuando comienzas a usar el resultado), y esto requiere copiar un todo ¡mapa!

Respuesta "completa" / mapa ordenado en vivo por valores

No te preocupes; si estuvieras obsesionado con tener un mapa "en vivo" ordenado de esta manera, podrías resolver no uno sino ambos (!) de los problemas anteriores con algo tan loco como el siguiente:

Nota: Esto ha cambiado significativamente en junio de 2012: el código anterior nunca podría funcionar: se necesita un HashMap interno para buscar los valores sin crear un bucle infinito entre TreeMap.get() -> compare() y 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"));
    }
 }

Cuando lo colocamos, nos aseguramos de que el mapa hash tenga el valor para el comparador, y luego lo ponemos en TreeSet para su clasificación. Pero antes de eso, verificamos el mapa hash para ver que la clave no es en realidad un duplicado. Además, el comparador que creamos también incluirá la clave para que los valores duplicados no eliminen las claves que no son duplicadas (debido a == comparación). Estos 2 artículos son vital para garantizar que se mantenga el contrato del mapa; si crees que no quieres eso, entonces casi estás a punto de invertir el mapa por completo (a Map<V,K>)

El constructor necesitaría llamarse como

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

207



De 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



Ordenar las claves requiere que el Comparador busque cada valor para cada comparación. Una solución más escalable usaría entrySet directamente, ya que el valor estaría inmediatamente disponible para cada comparación (aunque no he respaldado esto con números).

Aquí hay una versión genérica de tal cosa:

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

Hay formas de disminuir la rotación de memoria para la solución anterior. La primera ArrayList creada podría, por ejemplo, ser reutilizada como un valor de retorno; esto requeriría la supresión de algunas advertencias de genéricos, pero podría valer la pena para el código de biblioteca reutilizable. Además, el Comparador no tiene que ser reasignado en cada invocación.

Aquí hay una versión más eficiente aunque menos atractiva:

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

Finalmente, si necesita acceder continuamente a la información ordenada (en lugar de simplemente ordenarla de vez en cuando), puede usar un mapa múltiple adicional. Déjeme saber si usted necesita más detalles...


28



Con Java 8, puede usar secuencias api para hacerlo de una manera significativamente menos verbosa:

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

26



La biblioteca de colecciones comunes contiene una solución llamada TreeBidiMapa. O bien, podría echar un vistazo a la API de Google Collections. Tiene TreeMultimap que podrías usar

Y si no desea utilizar estos marcos ... vienen con el código fuente.


25



He visto las respuestas dadas, pero muchas de ellas son más complicadas de lo necesario o eliminan los elementos del mapa cuando varias teclas tienen el mismo valor.

Aquí hay una solución que creo que se adapta mejor:

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

Tenga en cuenta que el mapa está ordenado desde el valor más alto al más bajo.


23



Para lograr esto con las nuevas características en 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());
}

Las entradas están ordenadas por sus valores usando el comparador dado. Alternativamente, si sus valores son mutuamente comparables, no se necesita un comparador explícito:

<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 devuelta es una instantánea del mapa dado en el momento en que se llama este método, por lo que ninguno reflejará los cambios posteriores en el otro. Para una vista interactiva en vivo del mapa:

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

El iterable devuelto crea una nueva instantánea del mapa dado cada vez que se itera, por lo que salvo modificaciones concurrentes, siempre reflejará el estado actual del mapa.


17