Question Trier une carte par valeurs


Je suis relativement nouveau à Java, et trouve souvent que j'ai besoin de trier un Map<Key, Value> sur les valeurs.

Puisque les valeurs ne sont pas uniques, je me retrouve à convertir keySet dans un array, et en triant ce tableau à travers type de tableau avec un comparateur personnalisé qui trie sur la valeur associée à la clé.

Y a-t-il un moyen plus facile?


1377


origine


Réponses:


Voici une version générique:

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



Note importante:

Ce code peut casser de plusieurs manières. Si vous avez l'intention d'utiliser le code fourni, assurez-vous de lire les commentaires afin de connaître les 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 une 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}

405



Java 8 propose une nouvelle réponse: convertir les entrées en flux et utiliser les combinateurs de comparaison 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, inversez simplement 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 map:

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 imprimez sur System.out:

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

213



Trois réponses d'une ligne ...

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

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

Ce qui va créer une fonction (objet) pour la carte [qui prend l'une des clés en entrée, renvoyant la valeur correspondante], puis leur appliquer un ordre naturel (comparable) [les valeurs].

Si elles ne sont pas comparables, alors vous devrez faire quelque chose comme

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

Ceux-ci peuvent être appliqués à une TreeMap (comme Ordering s'étend Comparator), ou un LinkedHashMap après un tri

NB: Si vous allez utiliser une TreeMap, n'oubliez pas que si une comparaison == 0, alors l'élément est déjà dans la liste (ce qui arrivera si vous avez plusieurs valeurs qui se comparent les mêmes). Pour remédier à cela, vous pouvez ajouter votre clé au comparateur comme si (en supposant que vos clés et vos valeurs sont Comparable):

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

= Appliquer l'ordre naturel à la valeur mappé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 se comparent à 0, mais cela devrait suffire pour la plupart comparable articles (comme hashCode, equals et compareTo sont souvent synchronisés ...)

Voir Ordering.onResultOf () et Fonctions.forMap ().

la mise en oeuvre

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

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Maintenant, cela fonctionnera très probablement, mais:

  1. doit être fait donné une carte complète terminée
  2. Ne pas essayer les comparateurs ci-dessus sur un TreeMap; il ne sert à rien d'essayer de comparer une clé insérée quand elle n'a pas de valeur jusqu'à après la mise, c.-à-d., elle va se casser très vite

Le point 1 est un peu un deal-breaker pour moi; google collections est incroyablement paresseux (ce qui est bien: vous pouvez faire à peu près 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 entier carte!

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

Ne vous inquiétez pas cependant; Si vous étiez assez obsédé pour avoir une carte "live" triée de cette manière, vous pourriez résoudre non pas un, mais les deux (!) des problèmes ci-dessus avec quelque chose de fou comme ceci:

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 les TreeMap.get() -> compare() et 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, et ensuite mis à l'TreeSet pour le tri. Mais avant cela, nous vérifions la carte de hachage pour voir que la clé n'est pas réellement un doublon. En outre, 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 articles sont vital pour s'assurer que le contrat de carte est conservé; si vous pensez que vous ne le voulez pas, vous êtes presque sur le point d'inverser complètement la carte Map<V,K>).

Le constructeur devrait être appelé comme

 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



Le tri des clés nécessite le comparateur pour rechercher chaque valeur pour chaque comparaison. Une solution plus évolutive utiliserait directement entrySet, puisque la valeur serait immédiatement disponible pour chaque comparaison (bien que je ne l'ai pas sauvegardée par des nombres).

Voici une version générique d'une telle chose:

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

Il existe des moyens de réduire la rotation de la mémoire pour la solution ci-dessus. La première ArrayList créée pourrait par exemple être réutilisée en tant que valeur de retour; cela nécessiterait la suppression de certains avertissements génériques, mais cela pourrait en valoir la peine pour un code de bibliothèque réutilisable. De même, le comparateur n'a pas besoin d'être réattribué à chaque invocation.

Voici une version plus efficace mais moins attrayante:

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

Enfin, si vous avez besoin d'accéder en permanence aux informations triées (plutôt que de simplement les trier de temps en temps), vous pouvez utiliser une carte multiple supplémentaire. Faites-moi savoir si vous avez besoin de plus de détails ...


28



Avec Java 8, vous pouvez utiliser le flux api de le faire d'une manière sensiblement moins verbeuse:

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

26



La bibliothèque commons-collections contient une solution appelée TreeBidiMap. Ou, vous pouvez jeter un oeil à l'API Google Collections. Il a TreeMultimap que vous pourriez utiliser.

Et si vous ne voulez pas utiliser ces frameworks ... ils viennent avec du code source.


25



J'ai examiné les réponses données, mais beaucoup d'entre elles sont plus compliquées que nécessaire ou suppriment des éléments de la carte lorsque plusieurs clés ont la même valeur.

Voici une solution qui me semble mieux adaptée:

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

Notez que la carte est triée de la valeur la plus élevée à la plus faible.


23



Pour accomplir cela avec les nouvelles fonctionnalités de 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());
}

Les entrées sont classées par leurs valeurs en utilisant le comparateur donné. Alternativement, si vos valeurs sont mutuellement comparables, aucun comparateur explicite n'est nécessaire:

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

La liste retournée est un instantané de la carte donnée au moment de l'appel de cette méthode, donc aucun des deux ne reflétera les changements ultérieurs de l'autre. Pour une vue itérative en direct de la carte:

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

L'itérateur retourné crée un nouvel instantané de la carte donnée chaque fois qu'il est itéré, donc, sauf modification simultanée, il reflétera toujours l'état actuel de la carte.


17