Boomkaart sorteren op waarde

Ik wil een comparator schrijven waarmee ik een TreeMap kan sorteren op waarde in plaats van de standaard natuurlijke volgorde.

Ik heb zoiets als dit geprobeerd, maar kan niet achterhalen wat er mis ging:

import java.util.*;
class treeMap {
    public static void main(String[] args) {
        System.out.println("the main");
        byValue cmp = new byValue();
        Map<String, Integer> map = new TreeMap<String, Integer>(cmp);
        map.put("de",10);
        map.put("ab", 20);
        map.put("a",5);
        for (Map.Entry<String,Integer> pair: map.entrySet()) {
            System.out.println(pair.getKey()+":"+pair.getValue());
        }
    }
}
class byValue implements Comparator<Map.Entry<String,Integer>> {
    public int compare(Map.Entry<String,Integer> e1, Map.Entry<String,Integer> e2) {
        if (e1.getValue() < e2.getValue()){
            return 1;
        } else if (e1.getValue() == e2.getValue()) {
            return 0;
        } else {
            return -1;
        }
    }
}

Ik denk dat wat ik vraag is: kan ik een Map.Entrydoorgeven aan de vergelijker?

Antwoord 1, autoriteit 100%

Je kunt de TreeMapzelf niet op de waarden laten sorteren, aangezien dat in strijd is met de SortedMapspecificatie:

Een Mapdie verder een totale volgordeop de toetsengeeft.

Met een externe verzameling kunt u echter altijd Map.entrySet()zoals je wilt, ofwel door sleutels, waarden, of zelfs een combinatie (!!) van de twee.

Hier is een generieke methode die een SortedSetvan Map.Entryretourneert, gegeven een Mapwaarvan de waarden Comparable:

static <K,V extends Comparable<? super V>>
SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
    SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
        new Comparator<Map.Entry<K,V>>() {
            @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
                int res = e1.getValue().compareTo(e2.getValue());
                return res != 0 ? res : 1;
            }
        }
    );
    sortedEntries.addAll(map.entrySet());
    return sortedEntries;
}

Je kunt nu het volgende doen:

   Map<String,Integer> map = new TreeMap<String,Integer>();
    map.put("A", 3);
    map.put("B", 2);
    map.put("C", 1);   
    System.out.println(map);
    // prints "{A=3, B=2, C=1}"
    System.out.println(entriesSortedByValues(map));
    // prints "[C=1, B=2, A=3]"

Houd er rekening mee dat er gekke dingen gebeuren als je probeert ofwel de SortedSetzelf, of de Map.Entryerin te wijzigen, omdat dit niet langer een “weergave” is van de originele kaart zoals entrySet()is.

Over het algemeen is de noodzaak om de items van een kaart te sorteren op zijn waarden atypisch.

Opmerking over ==voor Integer

Je originele vergelijker vergelijkt Integermet ==. Dit is bijna altijd verkeerd, aangezien ==met Integeroperanden een referentiegelijkheid is, geen waardegelijkheid.

   System.out.println(new Integer(0) == new Integer(0)); // prints "false"!!!

Verwante vragen

• Bij het vergelijken van twee integers in Java wordt automatisch unboxing plaatsvindt?(NEE!!!)
• Is het gegarandeerd dat new Integer(i) == iin Java?(JA!!!)

Antwoord 2, autoriteit 41%

Het antwoord van

polygenelubricants is bijnaperfect. Het heeft echter een belangrijke bug. Het zal geen kaartvermeldingen behandelen waarvan de waarden hetzelfde zijn.

Deze code:…

Map<String, Integer> nonSortedMap = new HashMap<String, Integer>();
nonSortedMap.put("ape", 1);
nonSortedMap.put("pig", 3);
nonSortedMap.put("cow", 1);
nonSortedMap.put("frog", 2);
for (Entry<String, Integer> entry  : entriesSortedByValues(nonSortedMap)) {
    System.out.println(entry.getKey()+":"+entry.getValue());
}

Zou uitvoeren:

ape:1
frog:2
pig:3

Merk op hoe onze koe verdween toen ze de waarde “1” deelde met onze aap :O!

Deze wijziging van de code lost dat probleem op:

static <K,V extends Comparable<? super V>> SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
        SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
            new Comparator<Map.Entry<K,V>>() {
                @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
                    int res = e1.getValue().compareTo(e2.getValue());
                    return res != 0 ? res : 1; // Special fix to preserve items with equal values
                }
            }
        );
        sortedEntries.addAll(map.entrySet());
        return sortedEntries;
    }

Antwoord 3, autoriteit 30%

In Java 8:

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

Antwoord 4, autoriteit 11%

Een TreeMapwordt altijdgesorteerd op de sleutels, iets anders is onmogelijk. Met een Comparatorkunt u alleen bepalen hoede sleutels worden gesorteerd.

Als je de gesorteerde waarden wilt, moet je ze extraheren in een Listen die sorteren.

Antwoord 5, autoriteit 5%

Dit kan niet worden gedaan door een Comparatorte gebruiken, omdat deze altijd de sleutelvan de kaart krijgt om te vergelijken. TreeMapkan alleen op sleutel sorteren.

Antwoord 6, autoriteit 2%

Het antwoord van Olof is goed, maar het heeft één meer nodig voordat het perfect is. In de opmerkingen onder zijn antwoord wijst DACW (correct) op dat zijn implementatie de vergelijking / gelijk is aan contract voor sets. Als u probeert te bellen of te verwijderen in een vermelding die in de set duidelijk in de set is, herkent de set het niet vanwege de code waarmee items met gelijke waarden in de set kunnen worden geplaatst. Dus om dit te verhelpen, moeten we voor de gelijkheid testen tussen de toetsen:

static <K,V extends Comparable<? super V>> SortedSet<Map.Entry<K,V>> entriesSortedByValues(Map<K,V> map) {
    SortedSet<Map.Entry<K,V>> sortedEntries = new TreeSet<Map.Entry<K,V>>(
        new Comparator<Map.Entry<K,V>>() {
            @Override public int compare(Map.Entry<K,V> e1, Map.Entry<K,V> e2) {
                int res = e1.getValue().compareTo(e2.getValue());
                if (e1.getKey().equals(e2.getKey())) {
                    return res; // Code will now handle equality properly
                } else {
                    return res != 0 ? res : 1; // While still adding all entries
                }
            }
        }
    );
    sortedEntries.addAll(map.entrySet());
    return sortedEntries;
}

“Merk op dat de bestelling die wordt gehandhaafd door een gesorteerde set (al dan niet een expliciete comparator wordt verstrekt) moet consistent zijn met gelijken als de gesorteerde set de set-interface correct moet implementeren … De ingestelde interface wordt gedefinieerd in termen van De gelijkende bediening, maar Een gesorteerde set voert alle elementvergelijkingen uit met behulp van de methode van vergelijkingen (of vergelijken), dus twee elementen die geacht worden door deze methode, zijn vanuit het standpunt van de gesorteerde set, gelijk . ”
(http://docs.oracle.com/javase/6/docs/api /java/util/SortedSet.html)

Omdat we oorspronkelijk gelijkheid over het hoofd zagen om de set te dwingen items met gelijke waarde toe te voegen, moeten we nu testen op gelijkheid in de sleutels om ervoor te zorgen dat de set daadwerkelijk het item teruggeeft waarnaar je op zoek bent. Dit is nogal rommelig en zeker niet hoe sets bedoeld waren om te worden gebruikt – maar het werkt.

Antwoord 7, autoriteit 2%

Ik weet dat dit bericht specifiek vraagt om het sorteren van een TreeMap op waarden, maar voor degenen onder ons die niet echt om implementatie geven, maar wel een oplossing willen die de verzameling gesorteerd houdt terwijl elementen worden toegevoegd, zou ik feedback hierover op prijs stellen TreeSet-gebaseerde oplossing. Ten eerste zijn elementen niet gemakkelijk terug te vinden per sleutel, maar voor het gebruik dat ik bij de hand had (de n sleutels met de laagste waarden vinden), was dit geen vereiste.

 TreeSet<Map.Entry<Integer, Double>> set = new TreeSet<>(new Comparator<Map.Entry<Integer, Double>>()
  {
    @Override
    public int compare(Map.Entry<Integer, Double> o1, Map.Entry<Integer, Double> o2)
    {
      int valueComparison = o1.getValue().compareTo(o2.getValue());
      return valueComparison == 0 ? o1.getKey().compareTo(o2.getKey()) : valueComparison;
    }
  });
  int key = 5;
  double value = 1.0;
  set.add(new AbstractMap.SimpleEntry<>(key, value));

Antwoord 8

Veel mensen krijgen het advies om List te gebruiken en ik gebruik het ook liever

hier zijn twee methoden die u nodig hebt om de items van de kaart te sorteren op basis van hun waarden.

   static final Comparator<Entry<?, Double>> DOUBLE_VALUE_COMPARATOR = 
        new Comparator<Entry<?, Double>>() {
            @Override
            public int compare(Entry<?, Double> o1, Entry<?, Double> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        };
        static final List<Entry<?, Double>> sortHashMapByDoubleValue(HashMap temp)
        {
            Set<Entry<?, Double>> entryOfMap = temp.entrySet();
            List<Entry<?, Double>> entries = new ArrayList<Entry<?, Double>>(entryOfMap);
            Collections.sort(entries, DOUBLE_VALUE_COMPARATOR);
            return entries;
        }

Antwoord 9

import java.util.*;
public class Main {
public static void main(String[] args) {
    TreeMap<String, Integer> initTree = new TreeMap();
    initTree.put("D", 0);
    initTree.put("C", -3);
    initTree.put("A", 43);
    initTree.put("B", 32);
    System.out.println("Sorted by keys:");
    System.out.println(initTree);
    List list = new ArrayList(initTree.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
            return e1.getValue().compareTo(e2.getValue());
        }
    });
    System.out.println("Sorted by values:");
    System.out.println(list);
}
}