Classificar um mapa <Chave, Valor> por valores

1635

Eu sou relativamente novo em Java e frequentemente acho que preciso classificar Map<Key, Value>os valores.

Como os valores não são exclusivos, eu me pego convertendo o keySetem um arraye classificando essa matriz através da classificação de matriz com um comparador personalizado que classifica o valor associado à chave.

Existe uma maneira mais fácil?

Lii
fonte
24
Um mapa não deve ser classificado, mas acessado rapidamente. Valores iguais a objetos quebram a restrição do mapa. Use o conjunto de entradas, assim List<Map.Entry<...>> list =new LinkedList(map.entrySet())e Collections.sort ....assim.
Hannes
1
Um caso em que isso pode surgir quando tentamos fazer uso de um contador em Java (Map <Object, Inteiro>). Classificar por número de ocorrências seria uma operação comum. Uma linguagem como o Python possui uma estrutura de dados Counter integrada. Para uma maneira alternativa de implementação em Java, aqui está um exemplo
demongolem
7
Existem muitos casos de uso para mapas classificados, é por isso que você tem o TreeMap e o ConcurrentSkipListMap no jdk.
Alobodzk
1
TreeMap e ConcurrentSkipListMap classificam por chave. A questão é sobre a classificação por valor.
Peter

Respostas:

899

Aqui está uma versão genérica:

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
fonte
10
Ainda bem que isso ajuda. John, o LinkedHashMap é importante para a solução, pois fornece uma ordem de iteração previsível.
Carter Página
3
@ buzz3791 True. Esse será o caso de qualquer algoritmo de classificação. Alterar o valor dos nós em uma estrutura durante uma classificação cria resultados imprevisíveis (e quase sempre ruins).
Carter Página
3
@Sheagorath Eu tentei no Android e funciona também. Não é um problema específico da plataforma, considerando que você está usando a versão Java 6. Você implementou o Comparable corretamente no seu objeto de valor?
precisa saber é o seguinte
6
A versão do Java 8 não deveria usar em forEachOrderedvez de forEach, uma vez que os documentos dos forEachestados: "O comportamento desta operação é explicitamente não determinístico."?
27615 rob rob
1
rasgou totalmente isso, mas creditou @CarterPage nos comentários (ele estará em um projeto de código aberto de qualquer maneira). Muito obrigado.
Nathan Beach
420

Nota importante:

Esse código pode ser quebrado de várias maneiras. Se você pretende usar o código fornecido, leia também os comentários para estar ciente das implicações. Por exemplo, os valores não podem mais ser recuperados por sua chave. ( getsempre retorna null.)


Parece muito mais fácil do que tudo o que precede. Use um TreeMap da seguinte maneira:

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

Resultado:

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}
user157196
fonte
18
Não existe mais ( stackoverflow.com/questions/109383/… ). Além disso, por que houve um elenco para Double? Não deveria ser apenas return ((Comparable)base.get(a).compareTo(((Comparable)base.get(b)))?
Stephen
12
@ Stephen: Não. Nesse caso, todas as chaves iguais por valor são descartadas (diferença entre iguais e comparação por referência). Além disso: Mesmo este código tem problemas com a seguinte seqüência map.put("A","1d");map.put("B","1d");map.put("C",67d);map.put("D",99.5d);
steffen
43
O comparador usado para o mapa de árvore é inconsistente com iguais (consulte o javadox sortMap). Isso significa que a retirada de itens do mapa em árvore não funcionará. Sorted_map.get ("A") retornará nulo. Isso significa que esse uso do treemap está quebrado.
MR_fr0g 01/12/2010
87
Caso não esteja claro para as pessoas: essa solução provavelmente não fará o que você deseja se você tiver várias chaves mapeadas para o mesmo valor - apenas uma dessas chaves aparecerá no resultado classificado.
Maxy-B
63
Louis Wasserman (sim, um dos caras do Google Guava), na verdade não gosta desta resposta: "Ele quebra de várias maneiras realmente confusas, se você o considera engraçado. Se o mapa de suporte mudar, ele quebrará. Se várias chaves mapear para o mesmo valor, ele será interrompido. Se você ligar para obter uma chave que não esteja no mapa de suporte, ele será interrompido. o mapa - uma chamada Map.equals, contém Key, qualquer coisa - ele quebrará com traços de pilha realmente estranhos ". plus.google.com/102216152814616302326/posts/bEQLDK712MJ
haylem
339

O Java 8 oferece uma nova resposta: converta as entradas em um fluxo e use os combinadores comparadores do Map.Entry:

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

Isso permitirá consumir as entradas classificadas em ordem crescente de valor. Se você deseja um valor decrescente, basta reverter o comparador:

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

Se os valores não forem comparáveis, você pode passar um comparador explícito:

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

Você pode então usar outras operações de fluxo para consumir os dados. Por exemplo, se você deseja o top 10 em um novo 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));

Ou imprima para System.out:

map.entrySet().stream()
   .sorted(Map.Entry.comparingByValue())
   .forEach(System.out::println);
Brian Goetz
fonte
Bom, mas e o uso de parallelStream()neste caso?
Benj
11
Funcionará em paralelo; no entanto, você pode achar que o custo da mesclagem de mapas para combinar os resultados parciais é muito caro e a versão paralela pode não ter o desempenho esperado. Mas funciona e produz a resposta correta.
Brian Goetz
Obrigado pelo seu conselho útil. Era exatamente o que eu queria saber, embora dependa de que tipo de chave você usa e de tantos parâmetros ... O importante é "funciona e produz a resposta correta".
Benj
2
você não precisa usar compareByValue no exemplo top10?
Leo
1
O @Benj funcionará em termos de extração dos 10 melhores, mas o mapa resultante não será mais solicitado.
OrangeDog 18/06/19
211

Três respostas em uma linha ...

Eu usaria o Google Collections Guava para fazer isso - se seus valores forem Comparable, você poderá usar

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

O que criará uma função (objeto) para o mapa [que pega qualquer uma das teclas como entrada, retornando o respectivo valor] e depois aplica ordem natural (comparável) a elas [os valores].

Se não forem comparáveis, você precisará fazer algo como

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

Eles podem ser aplicados a um TreeMap (à medida que Orderingse estende Comparator) ou a um LinkedHashMap após alguma classificação

NB : Se você for usar um TreeMap, lembre-se de que, se uma comparação == 0, o item já está na lista (o que acontecerá se você tiver vários valores que comparam o mesmo). Para aliviar isso, você pode adicionar sua chave ao comparador da seguinte maneira (presumindo que suas chaves e valores sejam Comparable):

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

= Aplique a ordem natural ao valor mapeado pela chave e combine isso com a ordem natural da chave

Note-se que este ainda não vai funcionar se suas chaves comparar a 0, mas isso deve ser suficiente para a maioria dos comparableitens (como hashCode, equalse compareTosão muitas vezes em sincronia ...)

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

Implementação

Então agora que temos um comparador que faz o que queremos, precisamos obter um resultado disso.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Agora isso provavelmente funcionará, mas:

  1. precisa ser feito, dado um mapa completo concluído
  2. Não tente os comparadores acima em um TreeMap; não adianta tentar comparar uma chave inserida quando ela não tiver um valor até depois do put, ou seja, ela quebrará muito rápido

O ponto 1 é um pouco complicado para mim; as coleções do google são incrivelmente preguiçosas (o que é bom: você pode executar praticamente todas as operações em um instante; o trabalho real é feito quando você começa a usar o resultado) e isso exige a cópia de um mapa inteiro !

Resposta "completa" / mapa ordenado ao vivo por valores

Não se preocupe; se você era obcecado o suficiente por ter um mapa "ativo" classificado dessa maneira, poderia resolver não um, mas os dois (!) dos problemas acima com algo louco como o seguinte:

Nota: Isso mudou significativamente em junho de 2012 - o código anterior nunca funcionaria: é necessário um HashMap interno para pesquisar os valores sem criar um loop infinito entre 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 colocamos, garantimos que o mapa de hash tenha o valor do comparador e, em seguida, colocamos no TreeSet para classificação. Mas antes disso, verificamos o mapa de hash para ver se a chave não é realmente uma duplicata. Além disso, o comparador que criamos também incluirá a chave para que valores duplicados não excluam as chaves não duplicadas (devido a == comparação). Esses 2 itens são vitais para garantir a manutenção do contrato do mapa; se você acha que não quer isso, está quase no ponto de inverter completamente o mapa (para Map<V,K>).

O construtor precisaria ser chamado como

 new ValueComparableMap(Ordering.natural());
 //or
 new ValueComparableMap(Ordering.from(comparator));
Stephen
fonte
Olá @Stephen, você pode dar um exemplo de como usar o Pedido? Eu olho para o código-fonte do Ordering e totalmente não consigo descobrir o que .natural (). OnResultOf (...) retorna! O código fonte é "public <F> Ordering <F> onResultOf", eu nem sei como ele compila! Mais importante, como usar "<F> Ordenação <F>" para classificar um mapa? É um comparador ou algo assim? Obrigado.
Smallfo
Orderingé simplesmente um rico Comparator. Eu tentei comentar cada exemplo (o itálico embaixo de cada um). "natural" indica que os objetos são Comparable; é como o ComparableComparator do apache common. onResultOfaplica uma função ao item que está sendo comparado. Então se você tivesse uma função que adicionou 1 para um inteiro, em seguida, natural().onResultOf(add1Function).compare(1,2)iria acabar fazendo2.compareTo(3)
Stephen
ImmutableSortedMap.copyOf lança IllegalArgumentException se houver valores duplicados no mapa original.
precisa saber é o seguinte
@Ibalazscs Sim - você deve poder usar ImmutableSetMultiMapou ImmutableListMultiMapconter a coleção de variáveis ​​duplicadas.
Stephen
1
Obrigado por isso, usei sua solução em um projeto. Acho que há um problema em jogo: para se comportar como um mapa, ele precisa retornar o valor anteriormente associado à chave, se existir, mas assim nunca será possível. A solução que usei é retornar o valor removido, se existir.
alex
185

Em 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
fonte
16
A lista a ser classificada é "new LinkedList" ?? Gee. Felizmente Collections.sort () despeja a lista em uma matriz primeiro, para evitar precisamente esse tipo de erro (mas ainda assim, despejar um ArrayList em uma matriz deve ser mais rápido do que fazer o mesmo para uma LinkedList).
Dimitris Andreou
não pode converter de Iterator para TernaryTree.Iterator
lisak
4
@ gg.kaspersky Não estou dizendo "é ruim classificar uma LinkedList", mas essa própria LinkedList é uma má escolha aqui, independentemente da classificação. Muito melhor usar um ArrayList e, para obter pontos extras, dimensione-o exatamente em map.size (). Consulte também code.google.com/p/memory-measurer/wiki/… custo médio por elemento no ArrayList: 5 bytes custo médio por elemento no LinkedList: 24 bytes. Para um ArrayList de tamanho exato, o custo médio seria de 4 bytes. Ou seja, o LinkedList leva SEIS vezes a quantidade de memória que o ArrayList precisa. É apenas inchaço
Dimitris Andreou
2
o uso dos valores acima foi classificado em ordem crescente. Como classificar em descendente?
ram
1
Substitua o1 e o2 para classificar em ordem decrescente.
Soheil
68

Com o Java 8, você pode usar a API de fluxos para fazê-lo de uma maneira significativamente menos detalhada:

Map<K, V> sortedMap = map.entrySet().stream()
                         .sorted(Entry.comparingByValue())
                         .collect(Collectors.toMap(Entry::getKey, Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
assylias
fonte
Como classificá-lo em uma ordem inversa?
Vlad Holubiev
6
encontrada uma solução -Collections.reverseOrder(comparing(Entry::getValue))
Vlad Holubiev
1
Acho que vejo um erro de digitação lá - o "toMap" não deve ser chamado de "Collectors.toMap ()"?
Jake Stokes
1
@JakeStokes Ou use uma importação estática :-)
assylias
6
A melhor maneira de ordenar por valor de entrada na ordem inversa é:Entry.comparingByValue(Comparator.reverseOrder())
Gediminas Rimsa
31

A classificação das chaves requer que o Comparador pesquise cada valor para cada comparação. Uma solução mais escalável usaria o entrySet diretamente, desde então o valor estaria imediatamente disponível para cada comparação (embora eu não tenha feito backup disso por números).

Aqui está uma versão genérica de uma coisa dessas:

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

Existem maneiras de diminuir a rotação da memória para a solução acima. O primeiro ArrayList criado pode, por exemplo, ser reutilizado como um valor de retorno; isso exigiria a supressão de alguns avisos genéricos, mas pode valer a pena pelo código de biblioteca reutilizável. Além disso, o comparador não precisa ser realocado a cada chamada.

Aqui está uma versão mais eficiente, embora menos atraente:

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

Por fim, se você precisar acessar continuamente as informações classificadas (em vez de apenas classificá-las de vez em quando), poderá usar um multi-mapa adicional. Deixe-me saber se você precisar de mais detalhes ...

volley
fonte
A segunda versão pode ser mais concisa se você retornar List <Map.Entry <K, V >>. Isso também facilita a iteração e a obtenção das chaves e dos valores sem a necessidade de fazer muitas extra para o mapa. Isso tudo pressupõe que você esteja bem com esse código sendo inseguro. Se o mapa de apoio ou a lista classificada forem compartilhados em um ambiente multithread, todas as apostas serão desativadas.
Mike Miller
26

A biblioteca de coleções comuns contém uma solução chamada TreeBidiMap . Ou você pode dar uma olhada na API de coleções do Google. Possui TreeMultimap que você pode usar.

E se você não quiser usar essa estrutura ... eles vêm com código fonte.

p3t0r
fonte
Você não precisa usar a coleção de bens comuns. Java vem com seu próprio java.util.TreeMap.
yoliho 21/09/08
2
sim, mas o TreeMap é muito menos flexível ao classificar a parte do valor das entradas de mapa.
p3t0r 21/09/08
9
O problema com o BidiMap é que ele adiciona uma restrição de relação 1: 1 entre chaves e valores, a fim de tornar a relação invertível (ou seja, chaves e valores precisam ser exclusivos). Isso significa que você não pode usar isso para armazenar algo como um objeto de contagem de palavras, pois muitas palavras terão a mesma contagem.
Doug
26

Analisei as respostas fornecidas, mas muitas são mais complicadas do que o necessário ou removem elementos do mapa quando várias chaves têm o mesmo valor.

Aqui está uma solução que eu acho que se encaixa melhor:

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

Observe que o mapa é classificado do valor mais alto para o mais baixo.

Anthony
fonte
6
PROBLEMA: se você quiser usar o mapa retornado posteriormente, por exemplo, para verificar se ele contém um determinado elemento, você sempre será falso, devido ao seu comparador personalizado! Uma solução possível: substitua a última linha por: return new LinkedHashMap <K, V> (sortByValues);
Erel Segal-Halevi
Parece-me uma solução limpa, exceto pelo fato de @ErelSegalHalevi apontar, verificar se os valores existentes no mapa não serão possíveis conforme você especificou o comparador. map.put ("1", "Um"); map.put ("2", "Dois"); map.put ("3", "Três"); map.put ("4", "quatro"); map.put ("5", "cinco"); map.containsKey ("1") sempre retornará false, se você retornar um novo objeto na função sortByValues ​​() como retornar new TreeMap <K, V> (classificadoByValues); resolve o problema. Obrigado Abhi
abhi
praticamente o mesmo que a resposta de user157196 e Carter Page. A página de Carter contém a correção do LinkedHashMap
Kirby
A quarta linha da solução deve ser int compare = map.get (k1) .compareTo (map.get (k2)); se você precisar de ordem crescente
www.Decompiler.com
19

Para fazer isso com os novos recursos do 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());
}

As entradas são ordenadas por seus valores usando o comparador fornecido. Como alternativa, se seus valores forem mutuamente comparáveis, nenhum comparador explícito será necessário:

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

A lista retornada é uma captura instantânea do mapa fornecido no momento em que esse método é chamado, portanto, nenhum deles refletirá alterações subseqüentes no outro. Para uma visualização iterável ao vivo do mapa:

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

A iterável retornada cria uma nova captura instantânea do mapa fornecido toda vez que é iterada, impedindo modificações simultâneas, sempre refletindo o estado atual do mapa.

gdejohn
fonte
Isso retorna uma lista de entradas em vez de um mapa classificado por valor. Outra versão que retorna um mapa: stackoverflow.com/a/22132422/829571 #
assylias
17

Crie um comparador personalizado e use-o enquanto cria um novo objeto 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));

    }
}

Use o código abaixo em sua função principal

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

Resultado:

{B=75, D=50, C=50, A=35}
Sujan Reddy A
fonte
Caso os valores sejam iguais, alterei a linha "return 1" para comparar as chaves: "return ((String) o1) .compareTo ((String) o2);"
gjgjgj 17/03/19
14

Embora eu concorde que a necessidade constante de classificar um mapa seja provavelmente um cheiro, acho que o código a seguir é a maneira mais fácil de fazer isso sem usar uma estrutura de dados diferente.

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

}

E aqui está um teste de unidade embaraçosamente 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());
}

}

O resultado é uma lista classificada de objetos Map.Entry, da qual você pode obter as chaves e os valores.

Lyudmil
fonte
Esse método é muito mais fácil e intuitivo do que criar um objeto Map <V, List <K>> com praticamente o mesmo efeito. Os valores não devem realmente ser chaves em um objeto Mapa, o que você realmente está procurando é uma lista nessa situação, IMHO.
Jeff Wu
Esta solução não funciona com lotes de valores, ela ferrou com minha contagem de (o valor associado a cada chave)
Sam Levin
1
Isso é estranho. Você poderia elaborar? Qual foi sua saída e qual foi a saída que você esperava?
precisa saber é o seguinte
12

Use um comparador genérico como:

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
fonte
11

A resposta votada mais não funciona quando você tem 2 itens iguais. o TreeMap deixa valores iguais.

o exemplo: mapa não classificado

chave / valor: D / 67.3
chave / valor: A / 99.5
chave / valor: B / 67.4
chave / valor: C / 67.5
chave / valor: E / 99.5

resultados

chave / valor: A / 99.5
chave / valor: C / 67.5
chave / valor: B / 67.4
chave / valor: D / 67.3

Então deixa de fora E !!

Para mim, funcionou bem para ajustar o comparador, se for igual a não retornar 0, mas -1.

no exemplo:

classe ValueComparator implementa o Comparator {

Base do mapa; public ValueComparator (base do mapa) {this.base = base; }

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

}}

agora retorna:

mapa não classificado:

chave / valor: D / 67.3
chave / valor: A / 99.5
chave / valor: B / 67.4
chave / valor: C / 67.5
chave / valor: E / 99.5

resultados:

chave / valor: A / 99.5
chave / valor: E / 99.5
chave / valor: C / 67.5
chave / valor: B / 67.4
chave / valor: D / 67.3

como resposta a Aliens (22 de novembro de 2011): Estou usando esta solução para um mapa de IDs e nomes de números inteiros, mas a idéia é a mesma; portanto, o código acima pode não estar correto (escreverei em um teste e forneça o código correto), este é o código para uma classificação de mapa, com base na solução acima:

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 esta é a classe de teste (eu apenas a testei, e isso funciona para o inteiro, mapa de cadeias:

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

aqui está o código para o comparador de um mapa:

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 esta é a caixa de teste para isso:

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

de corte, você pode tornar isso muito mais genérico, mas eu só precisava disso para 1 caso (o Mapa)

michel.iamit
fonte
você estava certo, houve algum erro no código que dei primeiro! Espero que minha edição recente o ajude.
Michel.iamit
9

Em vez de usar Collections.sortcomo alguns, sugiro usar Arrays.sort. Na verdade, o que Collections.sortfaz é algo como isto:

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

Apenas chama toArraya lista e depois usa Arrays.sort. Dessa forma, todas as entradas do mapa serão copiadas três vezes: uma vez do mapa para a lista temporária (seja uma LinkedList ou ArrayList), depois para a matriz temporária e, finalmente, para o novo mapa.

Minha solução omite esta etapa, pois não cria LinkedList desnecessário. Aqui está o código, compatível com genéricos e com desempenho ideal:

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
fonte
8

Esta é uma variação da resposta de Anthony, que não funciona se houver valores duplicados:

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

Observe que é bastante no ar como lidar com nulos.

Uma vantagem importante dessa abordagem é que ela realmente retorna um mapa, diferente de outras soluções oferecidas aqui.

Roger
fonte
Está incorreto, meu método funciona se houver valores duplicados. Eu usei-o com mapas com mais de 100 teclas com "1" como valor.
25412 Anthony
8

Melhor Abordagem

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

Resultado

java ==== 20

MAC ==== 26

C++ ==== 45

Unix ==== 67

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

Grande problema. Se você usar a primeira resposta (o Google o leva aqui), altere o comparador para adicionar uma cláusula igual; caso contrário, você não poderá obter valores do mapa_detalhado por chaves:

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
fonte
Agora, quando você adicionar duas entradas com valores iguais eles serão mesclados só deve retornar 0 se tiver certeza de que os objetos são os mesmos (igual)
Masood_mj
7

Já existem muitas respostas para essa pergunta, mas nenhuma me forneceu o que eu estava procurando, uma implementação de mapa que retorna chaves e entradas classificadas pelo valor associado e mantém essa propriedade à medida que as chaves e os valores são modificados no mapa. Duas outras perguntas pedem isso especificamente.

Elaborei um exemplo amigável genérico que resolve esse caso de uso. Essa implementação não respeita todos os contratos da interface Map, como refletir mudanças e remoções de valor nos conjuntos retornados de keySet () e entrySet () no objeto original. Eu senti que essa solução seria muito grande para incluir em uma resposta de estouro de pilha. Se eu conseguir criar uma implementação mais completa, talvez eu a publique no Github e, em seguida, no link em uma versão atualizada desta resposta.

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
fonte
Se Comparable e Comparator não são permitidos, como fazê-lo?
Ved Prakash
Não tenho certeza se entendo seu caso de uso, talvez você possa elaborar. Se o objeto que você deseja usar como valor não for Comparável, será necessário convertê-lo em um objeto que seja.
David Bleckmann
6

Entrada tardia.

Com o advento do Java-8, podemos usar fluxos para manipulação de dados de uma maneira muito fácil / sucinta. Você pode usar fluxos para classificar as entradas do mapa por valor e criar um LinkedHashMap que preserva a iteração da ordem de inserção .

Por exemplo:

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

Para pedidos inversos, substitua:

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

com

comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey).reversed()
Pankaj Singhal
fonte
Obrigado por esta versão comentada. Uma pergunta: qual é a diferença de usar Entry.comparingByValue()(como as assilias respondem acima stackoverflow.com/a/22132422/1480587 ) ou comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)que você usou? Eu entendo que você também compara chaves se os valores forem idênticos, certo? Notei que a classificação mantém a ordem dos elementos com o mesmo valor - então a classificação por chaves é necessária se as chaves já tiverem sido classificadas antes?
Peter T.
6

Mapa dado

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

Classifique o mapa com base no valor em ordem crescente

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

Classifique o mapa com base no valor em ordem decrescente

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

Resultado:

{software = 50, tecnologia = 70, EUA = 100, empregos = 200, oportunidade = 200}

{empregos = 200, oportunidade = 200, EUA = 100, tecnologia = 70, software = 50}

Arpan Saini
fonte
Eu acho que mapa-reduzir realmente "reduzido" .... boa solução.
precisa saber é o seguinte
graças @ ha9u63ar
Arpan Saini
Funciona, mas não entendo como a ordem dos elementos entra em jogo em um HashMap?
Ali Tou
5

Dependendo do contexto, o uso de java.util.LinkedHashMap<T>qual lembra a ordem na qual os itens são colocados no mapa. Caso contrário, se você precisar classificar valores com base em sua ordem natural, eu recomendaria manter uma lista separada, que pode ser classificada via Collections.sort().

Ryan Delucchi
fonte
Não vejo por que isso foi -1, até agora o LinkedHashMap é provavelmente a melhor solução para mim, estou apenas tentando descobrir o quanto é caro jogar fora e criar um novo LinkedHashMap.
NobleUplift 18/04
5

Como o TreeMap <> não funciona para valores que podem ser iguais, usei o seguinte:

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

Você pode querer colocar a lista em um LinkedHashMap , mas se você quiser iterar imediatamente, isso é supérfluo ...

malix
fonte
isso mesmo, mas seu comparador não lida com valores iguais a maiúsculas #
Sebastien Lorber
5

Isso é muito complicado. Os mapas não deveriam fazer esse trabalho, classificando-os por Valor. A maneira mais fácil é criar sua própria classe para que ela atenda às suas necessidades.

No exemplo inferior, você deve adicionar ao TreeMap um comparador no local onde * está. Mas, pela API java, ele fornece apenas chaves para o comparador, não valores. Todos os exemplos aqui declarados são baseados em 2 mapas. Um Hash e uma nova Árvore. O que é estranho.

O exemplo:

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

Então, mude o mapa para um conjunto da seguinte maneira:

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

Você criará 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 a 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;
        }
    }
}

Dessa forma, você pode adicionar facilmente mais dependências.

E como último ponto, adicionarei um iterador simples:

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

Com base no código @devinmoore, um mapa classifica métodos usando genéricos e dando suporte à ordem crescente e decrescente.

/**
 * 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
fonte
Então, novamente, talvez uma solução melhor seria usar apenas um mapa de classificação auto, na org.apache.commons.collections.bidimap.TreeBidiMap caso de uso
Maxim Veksler
4

Aqui está uma solução OO (ou seja, não usa staticmétodos):

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

Por este meio doado ao domínio público.

Dave Jarvis
fonte
4

A maneira mais limpa é usar coleções para classificar o mapa em valor:

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
fonte
4

Algumas alterações simples para ter um mapa classificado com pares que têm valores duplicados. No método de comparação (classe ValueComparator), quando os valores são iguais, não retornam 0, mas retornam o resultado da comparação das 2 chaves. As chaves são distintas em um mapa, assim você consegue manter valores duplicados (que são classificados por chaves a propósito). Portanto, o exemplo acima pode ser modificado assim:

    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
fonte
4

Com certeza a solução de Stephen é realmente ótima, mas para quem não pode usar o Goiaba:

Aqui está minha solução para classificar por valor um mapa. Esta solução lida com o caso em que há o dobro do mesmo valor, etc ...

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

O executivo: http://www.ideone.com/dq3Lu

A saída:

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

Espero que ajude algumas pessoas

Sebastien Lorber
fonte
3

Se você tiver chaves duplicadas e apenas um pequeno conjunto de dados (<1000) e seu código não for crítico para o desempenho, basta fazer o seguinte:

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 é a entrada para o código.

A variável classificadaOutputMap conterá os dados em ordem decrescente quando iterados. Para alterar a ordem, basta alterar> para <na instrução if.

Não é o tipo mais rápido, mas executa o trabalho sem nenhuma dependência adicional.

nibor
fonte