TreeMap сортировка по значению

Question

Я хочу написать компаратор, который позволит мне сортировать TreeMap по значению вместо естественного упорядочения по умолчанию.

Я пробовал что-то подобное, но не могу выяснить, что пошло не так:

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

Наверное, я спрашиваю: могу ли я передать Map.Entry в компаратор?

Answer 1

Вы не можете иметь саму сортировку TreeMap по значениям, поскольку она не соответствует спецификации SortedMap:

A Map, который дополнительно обеспечивает общий порядок на его клавишах .

Однако, используя внешнюю коллекцию, вы всегда можете отсортировать Map.entrySet() по своему желанию, либо по ключам, значениям или даже по комбинации (!!) двух.

Вот обобщенный метод, который возвращает SortedSet из Map.Entry, учитывая Map со значениями 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;
}

Теперь вы можете делать следующее:

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

Обратите внимание, что прикольные вещи произойдут, если вы попытаетесь изменить либо SortedSet, либо Map.Entry внутри, потому что это больше не «вид» исходной карты, как entrySet().

Вообще говоря, необходимость сортировки записей карты по ее значениям нетипична.

---

Примечание на == для Integer

Ваш оригинальный компаратор сравнивает Integer, используя ==. Это почти всегда неверно, поскольку == с операндами Integer является ссылочным равенством, а не равенством значений.

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

Похожие вопросы

• При сравнении двух целых чисел в Java происходит автоматическая распаковка? (НЕТ !!!)
• Гарантируется ли, что new Integer(i) == i на Java? (ДА !!!)

Answer 2

полигенных смазок ответ почти идеально. Хотя есть одна важная ошибка. Он не будет обрабатывать записи карты, где значения одинаковы.

Этот код: ...

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

Будет выводить:

ape:1
frog:2
pig:3

Обратите внимание, как исчезла наша корова, когда она поделилась значением "1" с нашей обезьяной: O!

Эта модификация кода решает эту проблему:

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

Answer 3

В Java 8:

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

Answer 4

A TreeMap всегда отсортировано по ключам, все остальное невозможно. Comparator просто позволяет вам контролировать как сортировать ключи.

Если вы хотите отсортированные значения, вы должны извлечь их в List и отсортировать их.

Answer 5

Этого нельзя сделать с помощью Comparator, так как он всегда получит клавишу карты для сравнения. TreeMap сортировать можно только по ключу.

Answer 6

Ответ Олофа хорош, но ему нужно одна больше, прежде чем он станет идеальным. В комментариях под своим ответом dacwe (правильно) указывает, что его реализация нарушает контракт Сравнения / Равного для Наборов. Если вы попытаетесь вызвать «содержит» или «удалить» запись, которая явно находится в наборе, набор не распознает ее из-за кода, позволяющего размещать записи с равными значениями в наборе. Итак, чтобы это исправить, нам нужно проверить равенство ключей:

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

"Обратите внимание, что порядок, поддерживаемый отсортированным набором (независимо от того, предоставлен или нет явный компаратор), должен соответствовать равным, если отсортированный набор предназначен для правильной реализации интерфейса набора ... интерфейс набора определяется в терминах операция равно, но отсортированный набор выполняет все сравнения элементов, используя свой метод CompareTo (или сравнение), поэтому два элемента, которые считаются равными этим методом, с точки зрения отсортированного набора равны . " (http://docs.oracle.com/javase/6/docs/api/java/util/SortedSet.html)

Поскольку мы изначально упустили равенство, чтобы заставить набор добавлять одинаково значимые записи, теперь мы должны проверить равенство в ключах, чтобы набор фактически возвращал искомую запись. Это немного грязно и определенно не так, как наборы были предназначены для использования - но это работает.

Answer 7

Я знаю, что этот пост специально просит сортировать TreeMap по значениям, но для тех из нас, кто на самом деле не заботится о реализации, но хочет решение, которое сохраняет сортировку коллекции по мере добавления элементов, я был бы признателен за отзыв об этом Решение на основе TreeSet. С одной стороны, элементы нелегко получить по ключу, но для имеющегося у меня варианта использования (поиск n ключей с наименьшими значениями) это не было требованием.

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

Answer 8

Многие люди слышат, что им советуют использовать List, и я предпочитаю использовать его также

вот два метода, которые вам нужны для сортировки записей Карты по их значениям.

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