Trier une carte <clé, valeur> par valeurs

1637

Je suis relativement nouveau à Java et trouve souvent que je dois trier un Map<Key, Value>sur les valeurs.

Étant donné que les valeurs ne sont pas uniques, je me retrouve à convertir le keySeten un arrayet à trier ce tableau via le tri de tableau avec un comparateur personnalisé qui trie la valeur associée à la clé.

Existe-t-il un moyen plus simple?

Lii
la source
24
Une carte n'est pas censée être triée, mais accessible rapidement. Des valeurs égales à un objet brisent la contrainte de la carte. Utilisez le jeu d'entrées, comme List<Map.Entry<...>> list =new LinkedList(map.entrySet())et de Collections.sort ....cette façon.
Hannes
1
Un cas où cela pourrait survenir lorsque nous essayons d'utiliser un compteur en Java (Map <Object, Integer>). Le tri par nombre d'occurrences serait alors une opération courante. Un langage comme Python a une structure de données Counter intégrée. Pour un autre moyen d'implémentation en Java, voici un exemple
demongolem
7
Il existe de nombreux cas d'utilisation pour les cartes triées, c'est pourquoi vous avez TreeMap et ConcurrentSkipListMap dans jdk.
alobodzk
1
TreeMap et ConcurrentSkipListMap trient par clé. La question concerne le tri par valeur.
Peter

Réponses:

901

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;
    }
}
Page Carter
la source
10
Heureux que cela aide. John, le LinkedHashMap est important pour la solution car il fournit un ordre d'itération prévisible.
Carter Page
3
@ buzz3791 True. Ce sera le cas dans tout algorithme de tri. Modifier la valeur des nœuds dans une structure pendant un tri crée des résultats imprévisibles (et presque toujours mauvais).
Carter Page
3
@Sheagorath Je l'ai essayé sur Android et ça marche aussi. Ce n'est pas un problème spécifique à la plate-forme, étant donné que vous utilisez la version Java 6. Avez-vous implémenté Comparable correctement dans votre objet de valeur?
saiyancoder
6
La version Java 8 ne devrait-elle pas utiliser à la forEachOrderedplace de forEach, puisque la documentation des forEachétats: "Le comportement de cette opération est explicitement non déterministe."?
vol
1
totalement déchiré, mais crédité @CarterPage dans les commentaires (ce sera de toute façon dans un projet open source). Merci beaucoup.
Nathan Beach du
420

Note importante:

Ce code peut se casser de plusieurs manières. Si vous avez l'intention d'utiliser le code fourni, assurez-vous de lire également les commentaires pour être conscient des implications. Par exemple, les valeurs ne peuvent plus être récupérées par leur clé. ( getrevient 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
    }
}

Production:

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}
utilisateur157196
la source
18
Plus maintenant ( stackoverflow.com/questions/109383/… ). Aussi, pourquoi y avait-il un casting pour Double? Cela ne devrait-il pas être juste return ((Comparable)base.get(a).compareTo(((Comparable)base.get(b)))?
Stephen
12
@Stephen: Non. Dans ce cas, toutes les clés égales par valeur sont supprimées (différence entre égal et comparaison par référence). De plus: Même ce code a des problèmes avec la séquence suivante map.put("A","1d");map.put("B","1d");map.put("C",67d);map.put("D",99.5d);
steffen
43
Le comparateur utilisé pour le treemap n'est pas cohérent avec les égaux (voir le javadox sortMap). Cela signifie que le retrait des éléments de la carte arborescente ne fonctionnera pas. sorted_map.get ("A") renverra null. Cela signifie que cette utilisation de treemap est interrompue.
mR_fr0g
87
Juste au cas où cela ne serait pas clair pour les gens: cette solution ne fera probablement pas ce que vous voulez si vous avez plusieurs clés mappées sur la même valeur - une seule de ces clés apparaîtra dans le résultat trié.
Maxy-B
63
Louis Wasserman (oui, l'un des gars de Google Guava), déteste en fait un peu cette réponse: "Elle se décompose de plusieurs façons vraiment déroutantes si vous la regardez même de manière drôle. Si la carte de support change, elle se brisera. Si plusieurs touches mapper à la même valeur, elle se brisera. Si vous appelez get sur une clé qui ne se trouve pas dans la mappe de sauvegarde, elle se brisera. Si vous faites quoi que ce soit qui entraînerait une recherche sur une clé qui n'est pas dans la carte - un appel Map.equals, containsKey, n'importe quoi - elle rompra avec des traces de pile vraiment étranges. " plus.google.com/102216152814616302326/posts/bEQLDK712MJ
haylem
339

Java 8 offre une nouvelle réponse: convertir les entrées en un 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 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 imprimez à System.out:

map.entrySet().stream()
   .sorted(Map.Entry.comparingByValue())
   .forEach(System.out::println);
Brian Goetz
la source
Bien, mais qu'en est-il de l'utilisation parallelStream()dans ce cas?
Benj
11
Cela fonctionnera en parallèle, cependant, vous pouvez constater que le coût de la fusion des cartes pour combiner les résultats partiels est trop cher et la version parallèle peut ne pas fonctionner aussi bien que vous l'espérez. Mais cela fonctionne et produit la bonne réponse.
Brian Goetz
Merci pour vos précieux conseils. C'était exactement ce que je me demandais, bien que cela dépende du type de clé que vous utilisez et de tant de paramètres ... L'important est "ça marche et produit la bonne réponse".
Benj
2
ne devez-vous pas utiliser compareByValue dans l'exemple du top10?
Leo
1
@Benj cela fonctionnera en termes d'extraction du top 10, mais la carte résultante ne sera plus commandée.
OrangeDog
211

Trois réponses sur une ligne ...

J'utiliserais Google Collections Guava pour ce faire - si vos valeurs sont Comparablealors 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, renvoyant la valeur respective], puis leur applique un ordre naturel (comparable) [les valeurs].

S'ils ne sont pas comparables, vous devrez faire quelque chose dans le sens de

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

Ceux-ci peuvent être appliqués à un TreeMap (sous forme d' Orderingextension Comparator) ou à un LinkedHashMap après un certain tri

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

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

= Appliquer un ordre naturel à la valeur mappée par la clé et la 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 être suffisant pour la plupart des comparableéléments (comme hashCode, equalset compareTosont souvent synchronisés ...)

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

la mise en oeuvre

Alors 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 fonctionnera très probablement, mais:

  1. doit être fait étant donné une carte complète terminée
  2. N'essayez pas 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 avant le put, c'est-à-dire qu'elle se cassera très rapidement

Le point 1 est un peu une rupture 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 toute une carte!

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

Ne vous inquiétez pas cependant; si vous étiez assez obsédé par le fait d'avoir une carte "en direct" 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 le suivant:

Remarque: Cela a considérablement changé en juin 2012 - le code précédent ne pouvait jamais fonctionner: un HashMap interne est requis 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, puis placée dans le 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. De plus, le comparateur que nous créons inclura également la clé afin que les valeurs en double ne suppriment pas les clés non en double (en raison de la comparaison ==). Ces 2 éléments sont essentiels pour garantir le respect du contrat de carte; si vous pensez que vous ne voulez pas cela, alors vous êtes presque sur le point d'inverser complètement la carte (vers Map<V,K>).

Le constructeur devrait être appelé comme

 new ValueComparableMap(Ordering.natural());
 //or
 new ValueComparableMap(Ordering.from(comparator));
Stephen
la source
Bonjour @Stephen, pouvez-vous donner un exemple d'utilisation de la commande? Je regarde le code source de Ordering, et je ne peux absolument pas comprendre ce que .natural (). OnResultOf (...) renvoie! Le code source est "public <F> Ordering <F> onResultOf", je ne sais même pas comment il se compile! Plus important encore, comment utiliser "<F> Commande <F>" pour trier une carte? Est-ce un comparateur ou quelque chose? Merci.
smallufo
Orderingest tout simplement un riche Comparator. J'ai essayé de commenter chaque exemple (l'italique en dessous de chacun). "naturel" indique que les objets sont Comparable; c'est comme ComparableComparator d'apache common. onResultOfapplique une fonction à l'élément comparé. Donc, si vous aviez une fonction qui ajoutait 1 à un entier, cela natural().onResultOf(add1Function).compare(1,2)finirait par le faire2.compareTo(3)
Stephen
ImmutableSortedMap.copyOf lève IllegalArgumentException s'il y a des valeurs en double dans la carte d'origine.
lbalazscs
@Ibalazscs Oui, ce sera le cas - Vous devriez pouvoir utiliser ImmutableSetMultiMapou ImmutableListMultiMapcontenir la collection de variables en double.
Stephen
1
Merci pour cela, j'ai utilisé votre solution dans un projet. Je pense cependant qu'il y a un problème à mettre: pour se comporter comme une carte, il doit retourner la valeur précédemment associée à la clé, si elle existe, mais comme ça, elle ne le fera jamais. La solution que j'ai utilisée est de renvoyer la valeur supprimée si elle existe.
alex
185

Depuis 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
la source
16
La liste à trier est "nouvelle LinkedList" ?? Gee. Heureusement, Collections.sort () vide d'abord la liste dans un tableau, pour éviter précisément ce type d'erreur (mais tout de même, vider une ArrayList dans un tableau devrait être plus rapide que de faire la même chose pour une LinkedList).
Dimitris Andreou
Impossible de convertir Iterator en TernaryTree.Iterator
lisak
4
@ gg.kaspersky Je ne dis pas "c'est mauvais de trier une LinkedList", mais cette LinkedList elle-même est un mauvais choix ici, indépendamment du tri. Il vaut mieux utiliser une ArrayList et, pour des points supplémentaires, la dimensionner exactement à map.size (). Voir également code.google.com/p/memory-measurer/wiki/… coût moyen par élément dans ArrayList: 5 octets coût moyen par élément dans LinkedList: 24 octets. Pour une ArrayList de taille exacte, le coût moyen serait de 4 octets. Autrement dit, LinkedList prend SIX fois la quantité de mémoire dont ArrayList a besoin. Il est juste ballonnement
Dimitris Andreou
2
l'utilisation des valeurs ci-dessus a été triée par ordre croissant. Comment trier par ordre décroissant?
ram
1
Remplacez o1 et o2 pour trier par ordre décroissant.
Soheil
68

Avec Java 8, vous pouvez utiliser l' api des flux pour le faire de manière beaucoup moins verbeuse:

Map<K, V> sortedMap = map.entrySet().stream()
                         .sorted(Entry.comparingByValue())
                         .collect(Collectors.toMap(Entry::getKey, Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
assylias
la source
Comment trier dans un ordre inverse?
Vlad Holubiev
6
trouvé une solution -Collections.reverseOrder(comparing(Entry::getValue))
Vlad Holubiev
1
Je pense que j'y vois une faute de frappe - le "toMap" ne devrait-il pas être appelé "Collectors.toMap ()"?
Jake Stokes du
1
@JakeStokes Ou utilisez une importation statique :-)
assylias
6
Une meilleure façon de trier par valeur d'entrée dans l'ordre inverse est:Entry.comparingByValue(Comparator.reverseOrder())
Gediminas Rimsa
31

Le tri des clés nécessite que le comparateur recherche chaque valeur pour chaque comparaison. Une solution plus évolutive utiliserait directement le set d'entrée, car alors la valeur serait immédiatement disponible pour chaque comparaison (bien que je n'ai pas sauvegardé cela par des chiffres).

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 comme valeur de retour; cela nécessiterait la suppression de certains avertissements génériques, mais cela pourrait valoir la peine pour le code de bibliothèque réutilisable. De plus, le comparateur n'a pas besoin d'être réalloué à chaque appel.

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 devez accéder en continu aux informations triées (plutôt que de 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 ...

volley
la source
La deuxième version peut être plus concise si vous retournez List <Map.Entry <K, V >> Cela facilite également l'itération et l'obtention à la fois des clés et des valeurs sans avoir à effectuer de nombreuses opérations supplémentaires sur la carte. Tout cela en supposant que vous êtes d'accord avec ce code étant thread-unsafe. Si la carte de sauvegarde ou la liste triée sont partagées dans un environnement multithread, tous les paris sont désactivés.
Mike Miller,
26

La bibliothèque commons-collections contient une solution appelée TreeBidiMap . Vous pouvez également consulter l'API Google Collections. Il a TreeMultimap que vous pouvez utiliser.

Et si vous ne voulez pas utiliser ces frameworks ... ils sont livrés avec du code source.

p3t0r
la source
Vous n'êtes pas obligé d'utiliser la collection commune. Java est livré avec son propre java.util.TreeMap.
yoliho
2
oui, mais TreeMap est beaucoup moins flexible lors du tri sur la partie valeur des entrées de carte.
p3t0r
9
Le problème avec BidiMap est qu'il ajoute une contrainte de relation 1: 1 entre les clés et les valeurs afin de rendre la relation inversible (c'est-à-dire que les clés et les valeurs doivent être uniques). Cela signifie que vous ne pouvez pas l'utiliser pour stocker quelque chose comme un objet de comptage de mots, car de nombreux mots auront le même nombre.
Doug
26

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

Voici une solution qui, je pense, convient mieux:

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.

Anthony
la source
6
PROBLÈME: si vous souhaitez utiliser la carte retournée plus tard, par exemple pour vérifier si elle contient un certain élément, vous obtiendrez toujours faux, à cause de votre comparateur personnalisé! Une solution possible: remplacez la dernière ligne par: return new LinkedHashMap <K, V> (sortedByValues);
Erel Segal-Halevi
Cela me semble une solution propre, sauf le fait que @ErelSegalHalevi l'a souligné, vérifier si les valeurs existent dans la carte ne sera pas possible car vous avez spécifié le comparateur. map.put ("1", "One"); map.put ("2", "Deux"); map.put ("3", "Trois"); map.put ("4", "Quatre"); map.put ("5", "Five"); map.containsKey ("1") retournera toujours false, si vous retournez un nouvel objet dans la fonction sortByValues ​​() comme return new TreeMap <K, V> (sortedByValues); résout le problème. Merci Abhi
abhi
à peu près la même chose que la réponse de user157196 et Carter Page. Carter Page's contient le correctif LinkedHashMap
Kirby
La 4ème ligne de la solution doit être int compare = map.get (k1) .compareTo (map.get (k2)); si vous avez besoin d'un ordre croissant
www.Decompiler.com
19

Pour ce faire 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 à l'aide du 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 renvoyée est un instantané de la carte donnée au moment où cette méthode est appelée, donc aucune ne reflétera les modifications ultérieures de l'autre. Pour une vue itérable 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érable retourné crée un nouvel instantané de la carte donnée à chaque itération, donc à moins de modifications simultanées, il reflétera toujours l'état actuel de la carte.

gdejohn
la source
Cela renvoie une liste d'entrées plutôt qu'une carte triée par valeur. Autre version qui renvoie une carte: stackoverflow.com/a/22132422/829571
assylias
17

Créez un comparateur personnalisé et utilisez-le lors de la création d'un nouvel objet 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));

    }
}

Utilisez le code ci-dessous dans votre fonction principale

    Map<String, Integer> lMap = new HashMap<String, Integer>();
    lMap.put("A", 35);
    lMap.put("B", 75);
    lMap.put("C", 50);
    lMap.put("D", 50);

    MyComparator comparator = new MyComparator(lMap);

    Map<String, Integer> newMap = new TreeMap<String, Integer>(comparator);
    newMap.putAll(lMap);
    System.out.println(newMap);

Production:

{B=75, D=50, C=50, A=35}
Sujan Reddy A
la source
Dans le cas où les valeurs sont égales, j'ai changé la ligne "return 1" pour comparer les clés: "return ((String) o1) .compareTo ((String) o2);"
gjgjgj
14

Bien que je convienne que le besoin constant de trier une carte est probablement une odeur, je pense que le code suivant est le moyen le plus simple de le faire sans utiliser une structure de données différente.

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

}

Et voici un test unitaire embarrassant et incomplet:

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

}

Le résultat est une liste triée d'objets Map.Entry, à partir de laquelle vous pouvez obtenir les clés et les valeurs.

Lyudmil
la source
Cette méthode est beaucoup plus simple et intuitive que la création d'un objet Map <V, List <K>> avec à peu près le même effet. Les valeurs ne sont pas vraiment censées être des clés dans un objet Map, ce que vous recherchez vraiment est une liste dans cette situation, à mon humble avis.
Jeff Wu
Cette solution ne fonctionne pas avec beaucoup de valeurs, elle a vissé avec mes comptes (la valeur associée à chaque clé)
Sam Levin
1
C'est étrange. Pourriez-vous élaborer? Quelle a été votre sortie et quelle était la sortie que vous attendiez?
Lyudmil
12

Utilisez un comparateur générique tel que:

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
la source
11

La réponse votée pour le plus ne fonctionne pas lorsque vous avez 2 éléments égaux. TreeMap laisse des valeurs égales.

l'exmaple: carte non triée

clé / valeur: D / 67,3
clé / valeur: A / 99,5
clé / valeur: B / 67,4
clé / valeur: C / 67.5
clé / valeur: E / 99,5

résultats

clé / valeur: A / 99,5
clé / valeur: C / 67.5
clé / valeur: B / 67,4
clé / valeur: D / 67,3

Alors laisse de côté E !!

Pour moi, cela a bien fonctionné pour ajuster le comparateur, s'il est égal, ne retournez pas 0 mais -1.

dans l'exemple:

classe ValueComparator implémente Comparator {

Base de la carte; public ValueComparator (Map base) {this.base = base; }

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

}}

maintenant il revient:

carte non triée:

clé / valeur: D / 67,3
clé / valeur: A / 99,5
clé / valeur: B / 67,4
clé / valeur: C / 67.5
clé / valeur: E / 99,5

résultats:

clé / valeur: A / 99,5
clé / valeur: E / 99,5
clé / valeur: C / 67.5
clé / valeur: B / 67,4
clé / valeur: D / 67,3

en réponse à Aliens (2011 nov. 22): J'utilise cette solution pour une carte des identifiants et des noms entiers, mais l'idée est la même, donc le code ci-dessus n'est peut-être pas correct (je l'écrirai dans un test et vous donner le bon code), voici le code pour un tri de carte, basé sur la solution ci-dessus:

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


}

et ceci est la classe de test (je viens de la tester, et cela fonctionne pour l'Integer, String Map:

package test.nl.iamit.util;

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

public class TestComparators {


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

        sorted_map.putAll(unSoretedMap);

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

        assertArrayEquals(targetKeys,currecntKeys);
    }
}

voici le code du comparateur d'une carte:

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

et voici le test pour cela:

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

bien sûr, vous pouvez rendre cela beaucoup plus générique, mais j'en avais juste besoin pour 1 cas (la carte)

michel.iamit
la source
vous aviez raison, il y avait une erreur dans le code que j'ai donné au début! J'espère que mon récent montage vous aidera.
michel.iamit
9

Au lieu d'utiliser Collections.sortcomme certains, je suggère d'utiliser Arrays.sort. En fait, ce Collections.sortqui se passe est quelque chose comme ceci:

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

Il appelle simplement toArraysur la liste et utilise ensuite Arrays.sort. De cette façon, toutes les entrées de carte seront copiées trois fois: une fois de la carte dans la liste temporaire (que ce soit une LinkedList ou ArrayList), puis dans le tableau temporaire et enfin dans la nouvelle carte.

Ma solution supprime cette étape car elle ne crée pas de LinkedList inutile. Voici le code, générique et optimisé pour les performances:

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
la source
8

Il s'agit d'une variante de la réponse d'Anthony, qui ne fonctionne pas s'il existe des valeurs en double:

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

Notez que c'est plutôt en l'air comment gérer les valeurs nulles.

Un avantage important de cette approche est qu'elle renvoie en fait une carte, contrairement à certaines des autres solutions proposées ici.

Roger
la source
C'est incorrect, ma méthode fonctionne s'il y a des valeurs en double. Je l'ai utilisé avec des cartes ayant plus de 100 touches avec "1" comme valeur.
Anthony
8

Meilleure approche

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

Production

java ==== 20

MAC ==== 26

C++ ==== 45

Unix ==== 67

Why this kolavari ==== 93
Nilesh Jadav
la source
7

Un problème majeur. Si vous utilisez la première réponse (Google vous emmène ici), changez le comparateur pour ajouter une clause égale, sinon vous ne pouvez pas obtenir de valeurs de sorted_map par clés:

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
la source
Maintenant, lorsque vous ajoutez deux entrées avec des valeurs égales, elles seront fusionnées, vous ne devez retourner 0 que si vous êtes sûr que les objets sont les mêmes (égaux)
Masood_mj
7

Il y a déjà beaucoup de réponses à cette question, mais aucune ne m'a fourni ce que je cherchais, une implémentation de carte qui renvoie les clés et les entrées triées par la valeur associée, et conserve cette propriété lorsque les clés et les valeurs sont modifiées dans la carte. Deux autres questions le demandent spécifiquement.

J'ai concocté un exemple générique convivial qui résout ce cas d'utilisation. Cette implémentation n'honore pas tous les contrats de l'interface Map, tels que la prise en compte des changements de valeur et des suppressions dans les ensembles renvoyés par keySet () et entrySet () dans l'objet d'origine. Je pensais qu'une telle solution serait trop importante pour être incluse dans une réponse Stack Overflow. Si je parviens à créer une implémentation plus complète, je vais peut-être la publier sur Github, puis sur ce lien dans une version mise à jour de cette réponse.

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
la source
Si Comparable et Comparator ne sont pas autorisés, comment faire?
Ved Prakash
Je ne sais pas si je comprends votre cas d'utilisation, peut-être pourriez-vous élaborer. Si l'objet que vous souhaitez utiliser comme valeur n'est pas comparable, vous devrez le convertir en un objet qui l'est.
David Bleckmann
6

Entrée tardive.

Avec l'avènement de Java-8, nous pouvons utiliser des flux pour la manipulation de données de manière très simple / succincte. Vous pouvez utiliser des flux pour trier les entrées de mappage par valeur et créer un LinkedHashMap qui préserve l' itération de l' ordre d'insertion .

Par exemple:

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

Pour l'ordre inverse, remplacez:

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

avec

comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey).reversed()
Pankaj Singhal
la source
Merci pour cette version commentée. Une question: quelle est la différence d'utilisation Entry.comparingByValue()(comme réponse assylias ci-dessus stackoverflow.com/a/22132422/1480587 ) ou comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)que vous avez utilisé? Je comprends que vous comparez également les clés si les valeurs sont identiques, non? J'ai remarqué que le tri conserve l'ordre des éléments avec la même valeur - le tri par clés est-il donc nécessaire si les clés sont déjà triées auparavant?
Peter T.
6

Étant donné la carte

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

Trier la carte en fonction de la valeur dans l'ordre croissant

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

Trier la carte en fonction de la valeur dans l'ordre décroissant

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

Production:

{logiciel = 50, technologie = 70, États-Unis = 100, emplois = 200, opportunité = 200}

{jobs = 200, opportunité = 200, USA = 100, technologie = 70, logiciel = 50}

Arpan Saini
la source
Je suppose que la réduction de la carte est vraiment "réduite" ... bonne solution.
ha9u63ar
merci @ ha9u63ar
Arpan Saini
Cela fonctionne mais je ne comprends pas comment l'ordre des éléments entre en jeu dans un HashMap?
Ali Tou
5

Selon le contexte, en utilisant java.util.LinkedHashMap<T>ce qui se souvient de l'ordre dans lequel les éléments sont placés dans la carte. Sinon, si vous avez besoin de trier les valeurs en fonction de leur ordre naturel, je recommanderais de maintenir une liste séparée qui peut être triée via Collections.sort().

Ryan Delucchi
la source
Je ne vois pas pourquoi c'était -1, jusqu'à présent LinkedHashMap est probablement la meilleure solution pour moi, j'essaie juste de comprendre combien il est coûteux de jeter et de créer un nouveau LinkedHashMap.
NobleUplift
5

Puisque TreeMap <> ne fonctionne pas pour des valeurs qui peuvent être égales, j'ai utilisé ceci:

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

Vous voudrez peut-être mettre une liste dans un LinkedHashMap , mais si vous ne voulez que l'itérer tout de suite, c'est superflu ...

malix
la source
c'est vrai, mais votre comparateur ne gère pas les valeurs égales
Sebastien Lorber
5

C'est trop compliqué. Les cartes n'étaient pas censées faire un travail tel que les trier par valeur. Le moyen le plus simple consiste à créer votre propre classe afin qu'elle corresponde à vos besoins.

Dans l'exemple ci-dessous, vous êtes censé ajouter TreeMap un comparateur à l'endroit où * est. Mais par l'API Java, il ne donne que des clés de comparateur, pas des valeurs. Tous les exemples indiqués ici sont basés sur 2 cartes. Un hachage et un nouvel arbre. Ce qui est étrange.

L'exemple:

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

Alors changez la carte en un ensemble de cette façon:

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

Vous allez créer de la 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;
    }
}

et la classe Comparateur:

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

De cette façon, vous pouvez facilement ajouter plus de dépendances.

Et comme dernier point, j'ajouterai un itérateur simple:

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
la source
4

Basé sur le code @devinmoore, une méthode de tri de carte utilisant des génériques et prenant en charge l'ordre croissant et décroissant.

/**
 * 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
la source
Là encore, peut-être qu'une meilleure solution serait d'utiliser simplement une carte d'auto-tri, dans le cas d'utiliser org.apache.commons.collections.bidimap.TreeBidiMap
Maxim Veksler
4

Voici une solution OO (c'est-à-dire qu'elle n'utilise pas de staticméthodes):

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

Par la présente fait don au domaine public.

Dave Jarvis
la source
4

Afaik la manière la plus propre est d'utiliser des collections pour trier la carte selon la valeur:

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
la source
4

Quelques changements simples afin d'avoir une carte triée avec des paires qui ont des valeurs en double. Dans la méthode de comparaison (classe ValueComparator) lorsque les valeurs sont égales ne renvoient pas 0 mais renvoient le résultat de la comparaison des 2 clés. Les clés sont distinctes dans une carte afin que vous réussissiez à conserver les valeurs en double (qui sont en fait triées par clés). Ainsi, l'exemple ci-dessus pourrait être modifié comme ceci:

    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
la source
4

Bien sûr, la solution de Stephen est vraiment géniale, mais pour ceux qui ne peuvent pas utiliser Guava:

Voici ma solution pour trier par valeur une carte. Cette solution gère le cas où il y a deux fois la même valeur, 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

L'exéc: http://www.ideone.com/dq3Lu

Le résultat:

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

J'espère que cela aidera certaines personnes

Sébastien Lorber
la source
3

Si vous avez des clés en double et seulement un petit ensemble de données (<1000) et que votre code n'est pas critique en termes de performances, vous pouvez simplement faire ce qui suit:

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 est l'entrée du code.

La variable sortedOutputMap contiendra les données en ordre décroissant lors de l'itération. Pour changer l'ordre, remplacez simplement> par un <dans l'instruction if.

N'est pas le tri le plus rapide mais fait le travail sans dépendances supplémentaires.

nibor
la source