Упорядочивание Map<String, Integer> по его значениям

Условие

Имеется неотсортированный словарь типа Map<String, Integer>. Требуется переставить его элементы так, чтобы они шли в порядке возрастания значений, и вернуть полученный упорядоченный словарь.

Ожидаемый результат вывода:

One=1
Two=2
Three=3
Four=4
Five=5

public class MapComparator {
    public static void main(String[] args) {
        Map<String, Integer> nonSortedMap = Map.of(
            "Two", 2,
            "Three", 3,
            "Five", 5,
            "One", 1,
            "Four", 4
        );

        Map<String, Integer> sortedMap = sortByValue(nonSortedMap);

        sortedMap.entrySet().forEach(System.out::println);
    }

    static Map<String, Integer> sortByValue(Map<String, Integer> map) {
        return map; // Реализовать сортировку по значениям
    }
}

Ответ

Отсортируйте entrySet по значениям и соберите записи в LinkedHashMap. Именно LinkedHashMap сохранит порядок вставки для последующего обхода.

static Map<String, Integer> sortByValue(Map<String, Integer> map) {
    return map.entrySet().stream()
            .sorted(Map.Entry.<String, Integer>comparingByValue()
                    .thenComparing(Map.Entry.comparingByKey()))
            .collect(java.util.stream.Collectors.toMap(
                    Map.Entry::getKey, Map.Entry::getValue,
                    (left, right) -> left, java.util.LinkedHashMap::new));
}

При одинаковых числовых значениях строки упорядочиваются по ключу. Код предполагает отсутствие null у ключей и значений. Исходный словарь не изменяется. Время O(n log n), дополнительная память O(n). TreeMap без специальной конструкции сортировал бы ключи, а не значения.