Trier une Map<Key, Value> par valeurs

Question

Je suis relativement novice en Java, et je me retrouve souvent à devoir trier un fichier de type Map<Key, Value> sur les valeurs.

Étant donné que les valeurs ne sont pas uniques, je me retrouve à convertir le fichier keySet dans un array et de trier ce tableau par Triage par tableau avec un comparateur personnalisé qui trie sur la valeur associée à la clé.

Y a-t-il un moyen plus facile ?

Answer 1

Voici une version générique conviviale :

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

Answer 2

Remarque importante :

Ce code peut être cassé de plusieurs façons. Si vous avez l'intention d'utiliser le code fourni, veillez à lire également les commentaires pour être conscient des implications. Par exemple, les valeurs ne peuvent plus être récupérées par leur clé. ( get retourne toujours null .)

---

Cela semble beaucoup plus facile que tout ce qui précède. Utilisez un TreeMap comme suit :

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

Sortie :

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}

Answer 3

Java 8 offre une nouvelle réponse : convertir les entrées en un flux, et utiliser les combinateurs de comparateurs de Map.Entry :

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

Cela vous permettra de consommer les entrées triées par ordre croissant de valeur. Si vous voulez une valeur décroissante, il suffit d'inverser le comparateur :

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

Si les valeurs ne sont pas comparables, vous pouvez passer un comparateur explicite :

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

Vous pouvez ensuite utiliser d'autres opérations de flux pour consommer les données. Par exemple, si vous voulez le top 10 dans une nouvelle carte :

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 imprimer à System.out :

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

Answer 4

Trois réponses d'une ligne...

J'utiliserais Collections Google Goyave pour le faire - si vos valeurs sont Comparable alors vous pouvez utiliser

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

Ce qui créera une fonction (objet) pour la carte [qui prend n'importe laquelle des clés en entrée et renvoie la valeur correspondante], puis leur appliquera un ordre naturel (comparable) [les valeurs].

S'ils ne sont pas comparables, vous devrez faire quelque chose du type suivant

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

Celles-ci peuvent être appliquées à un TreeMap (en tant que Ordering étend Comparator ), ou un LinkedHashMap après un certain tri

NB : Si vous comptez utiliser un TreeMap, n'oubliez pas que si une comparaison == 0, alors l'élément se trouve déjà dans la liste (ce qui se produira si vous avez plusieurs valeurs dont la comparaison est identique). Pour pallier ce problème, vous pouvez ajouter votre clé au comparateur comme suit (en supposant que vos clés et valeurs sont Comparable ):

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

\= Appliquer l'ordre naturel à la valeur représentée par la clé, et le combiner avec l'ordre naturel de la clé.

Notez que cela ne fonctionnera toujours pas si vos clés sont comparées à 0, mais cela devrait être suffisant pour la plupart des cas. comparable articles (comme hashCode , equals y compareTo sont souvent synchronisées...)

Véase Commande.onResultOf() y Fonctions.forMap() .

Mise en œuvre

Maintenant que nous avons un comparateur qui fait ce que nous voulons, nous devons en obtenir un résultat.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Maintenant, cela va très probablement fonctionner, mais :

1. doit être fait pour obtenir une carte complète et finie
2. N'essayez pas les comparateurs ci-dessus sur une TreeMap il est inutile d'essayer de comparer une clé insérée si elle n'a pas de valeur avant le put, c'est-à-dire qu'il y aura une rupture très rapide.

Le point 1 est un peu rédhibitoire pour moi ; google collections est incroyablement paresseux (ce qui est bien : vous pouvez faire pratiquement toutes les opérations en un instant ; le vrai travail est fait lorsque vous commencez à utiliser le résultat), et cela nécessite de copier un fichier todo carte !

Réponse "complète" / carte vivante triée par valeurs

Mais ne vous inquiétez pas : si vous êtes suffisamment obsédé par le fait d'avoir une carte "vivante" triée de cette manière, vous pouvez résoudre non pas l'un mais les deux ( !) des problèmes ci-dessus avec quelque chose de fou comme ce qui suit :

Note : Ceci a changé de manière significative en juin 2012 - le code précédent ne pourrait jamais fonctionner : un HashMap interne est nécessaire pour rechercher les valeurs sans créer une boucle infinie entre le 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"));
    }
 }

Lorsque nous mettons, nous nous assurons que la carte de hachage a la valeur pour le comparateur, puis nous mettons dans le TreeSet pour le tri. Mais avant cela, nous vérifions la carte de hachage pour voir si la clé n'est pas en fait un doublon. De plus, le comparateur que nous créons inclura également la clé afin que les valeurs dupliquées ne suppriment pas les clés non dupliquées (en raison de la comparaison ==). Ces 2 éléments sont vital pour s'assurer que le contrat de la carte est conservé ; si vous pensez que vous ne voulez pas cela, alors vous êtes presque au point d'inverser la carte entièrement (à Map<V,K> ).

Le constructeur devrait être appelé comme

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

Answer 5

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