TreeMap sortuj według wartości

Chcę napisać komparator, który pozwoli mi posortować TreeMap według wartości zamiast domyślnego naturalnego porządku.

Próbowałem czegoś takiego, ale nie mogę dowiedzieć się, co poszło nie tak:

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

Myślę, że pytam: czy mogę Map.Entryprzejść do komparatora?

Nie możesz mieć TreeMapsamego sortowania według wartości, ponieważ jest to sprzeczne ze SortedMapspecyfikacją:

MapŻe dostarcza ponadto całkowite uporządkowanie na jej klucze .

Jednak korzystając z kolekcji zewnętrznej, zawsze możesz sortować w Map.entrySet()dowolny sposób, według kluczy, wartości lub nawet ich kombinacji (!!).

Oto ogólna metoda, która zwraca SortedSetz Map.Entry, biorąc pod uwagę Map, której wartościami są 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;
}

Teraz możesz wykonać następujące czynności:

    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]"

Zauważ, że dziwne rzeczy mogą się wydarzyć, jeśli spróbujesz zmodyfikować SortedSetsamą siebie lub Map.Entrywnętrze, ponieważ nie jest to już „widok” oryginalnej mapy, jak entrySet()jest.

Ogólnie rzecz biorąc, potrzeba sortowania wpisów mapy według jej wartości jest nietypowa.

Uwaga dotycząca ==dlaInteger

Twój oryginalny komparator porównuje Integerużycie ==. Jest to prawie zawsze błędne, ponieważ ==z Integeroperandami jest równość odniesienia, a nie równość wartości.

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

Powiązane pytania

• Czy podczas porównywania dwóch liczb całkowitych w Javie występuje automatyczne rozpakowywanie? (NIE!!!)
• Czy jest to gwarantowane new Integer(i) == iw Javie? (TAK!!!)

odpowiedź polygenelubricants jest prawie idealna. Ma jednak jeden ważny błąd. Nie będzie obsługiwać wpisów mapy, w których wartości są takie same.

Ten kod: ...

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

Wynikałoby:

ape:1
frog:2
pig:3

Zwróć uwagę, jak nasza krowa zniknęła, gdy miała wspólną wartość „1” z naszą małpą: O!

Ta modyfikacja kodu rozwiązuje ten problem:

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

W Javie 8:

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

A TreeMapjest zawsze sortowane według kluczy, wszystko inne jest niemożliwe. A Comparatorjedynie pozwala kontrolować sposób sortowania kluczy.

Jeśli chcesz posortowane wartości, musisz wyodrębnić je do a Listi posortować.

Nie można tego zrobić za pomocą a Comparator, ponieważ zawsze otrzyma klucz mapy do porównania. TreeMapmożna sortować tylko według klucza.

Odpowiedź Olofa jest dobra, ale potrzebuje jeszcze jednej rzeczy, zanim będzie idealna. W komentarzach pod swoją odpowiedzią dacwe (poprawnie) wskazuje, że jego implementacja narusza kontrakt Porównaj / Równość dla zestawów. Jeśli spróbujesz wywołać zawiera lub usunąć wpis, który jest wyraźnie w zestawie, zestaw nie rozpozna go z powodu kodu, który pozwala na umieszczenie w zestawie wpisów o równych wartościach. Aby to naprawić, musimy przetestować równość między kluczami:

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

Należy zauważyć, że kolejność utrzymywana przez posortowany zestaw (niezależnie od tego, czy podano jawny komparator) musi być zgodna z równymi, jeśli posortowany zestaw ma poprawnie zaimplementować interfejs Set ... interfejs Set jest zdefiniowany w kategoriach operacji equals , ale posortowany zestaw wykonuje wszystkie porównania elementów przy użyciu metody compareTo (lub porównaj), więc dwa elementy uznane za równe przez tę metodę są, z punktu widzenia posortowanego zestawu, równe . " ( http://docs.oracle.com/javase/6/docs/api/java/util/SortedSet.html )

Ponieważ początkowo przeoczyliśmy równość, aby wymusić na zestawie dodanie wpisów o równej wartości, teraz musimy przetestować równość w kluczach, aby zestaw faktycznie zwrócił wpis, którego szukasz. To trochę bałaganiarskie i zdecydowanie nie tak, jak zestawy miały być używane - ale to działa.

Wiem, że ten post zawiera konkretną prośbę o sortowanie TreeMap według wartości, ale dla tych z nas, którzy tak naprawdę nie dbają o implementację, ale chcą rozwiązania, które utrzymuje kolekcję posortowaną po dodaniu elementów, byłbym wdzięczny za opinie na temat tego opartego na TreeSet rozwiązanie. Po pierwsze, elementy nie są łatwo pobierane za pomocą klucza, ale w przypadku użycia, który miałem pod ręką (znalezienie n kluczy o najniższych wartościach), nie było to wymagane.

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

Wiele osób słyszy rady, aby używać List i ja też wolę z niej korzystać

tutaj są dwie metody, które musisz posortować wpisy mapy według ich wartości.

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