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

Я хочу написать компаратор, который позволит мне сортировать 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 переданный компаратору?

Ответы

Ответ 1

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

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

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

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

Связанные вопросы

Ответ 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;
    }

Ответ 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));

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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

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

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

Ответ 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));

Ответ 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;
        }