Java Сортировка карты с помощью Steams VS TreeMap

Question

Рассмотрим следующую Java HashMap.

Map<String, String> unsortMap = new HashMap<String, String>();
unsortMap.put("Z", "z");
unsortMap.put("B", "b");
unsortMap.put("A", "a");
unsortMap.put("C", "c");

Теперь я хочу отсортировать эту карту по ключу. Один из вариантов для меня - использовать TreeMap для этой цели.

Map<String, String> treeMap = new TreeMap<String, String>(unsortMap);

Другой вариант - использовать потоки Java с помощью Sorted () следующим образом.

Map<String, Integer> sortedMap = new HashMap<>();
unsortMap.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey())
    .forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));

Какой из этих двух вариантов предпочтительнее и почему (может быть с точки зрения производительности)?

Спасибо

Answer 1

Второй способ не работает, когда вы звоните HashMap#put, он не удерживает ордер пут. Вам может понадобиться LinkedHashMap.

TreeMap v.s. Поток (LinkedHashMap):

1. стиль кода. Использование TreeMap является более понятным, поскольку вы можете достичь его в одну строку.
2. космическая сложность. Если исходная карта HashMap, то для обоих методов вам нужно создать новый Map. Если исходная карта LinkedHashMap, то вам нужно только создать новую Map с первым подходом. Вы можете повторно использовать LinkedHashMap при втором подходе.
3. сложность времени. Они оба должны иметь O (nln (n)).

Answer 2

Как отмечают другие, сброс отсортированного потока записей в обычный HashMap ничего не сделает ... LinkedHashMap - логичный выбор.

Однако альтернативой вышеупомянутым подходам является полное использование API Stream Collectors.

Collectors имеет метод toMap, который позволяет предоставить альтернативную реализацию для Map. Таким образом, вместо HashMap вы можете запросить LinkedHashMap, например, так:

unsortedMap.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey())
    .collect(Collectors.toMap(
       Map.Entry::getKey,
       Map.Entry::getValue,
       (v1, v2) -> v1, // you will never merge though ask keys are unique.
       LinkedHashMap::new
    ));

Между использованием TreeMap и LinkedHashMap ... Сложность построения, вероятно, будет такой же, как O (n log n) ... Очевидно, что решение TreeMap является лучшим подходом, если вы планируете продолжать добавлять больше элементы к нему ... Я думаю, вы должны были начать с TreeMap в этом случае. Опция LinkedHashMap имеет преимущество в том, что поиск будет O (1) на Связанной или исходной несортированной карте, тогда как TreeMap похож на O(log n), так что если вам нужно сохранить несортированную карту для эффективного поиска, тогда как если вы создадите LinkedHashMap, вы можете сбросить исходную несортированную карту (тем самым сэкономив немного памяти).

Чтобы сделать вещи немного более эффективными с LinkedHashMap, вы должны предоставить хорошую оценку требуемого размера при построении, чтобы не было необходимости динамического изменения размера, поэтому вместо LinkedHashMap::new вы говорите () -> new LinkedHashMap<>(unsortedMap.size()).

Я считаю, что использование TreeMap более аккуратно ... так как код меньше, поэтому, если нет реальной проблемы производительности, которую можно было бы решить с помощью подхода несортированной и отсортированной связанной карты, я бы использовал Tree.

Answer 3

Ваш потоковый код не будет даже сортировать карту, потому что он выполняет операцию с HashMap, который по своей природе не отсортирован. Чтобы ваш пример второго потока работал, вы можете использовать LinkedHashMap, который поддерживает порядок вставки:

Map<String, Integer> sortedMap = new LinkedHashMap<>();
unsortMap.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey())
    .forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));

Но теперь ваши два примера - даже не одна и та же базовая структура данных. TreeMap поддерживается деревом (красно-черным, если я правильно помню). Вы должны использовать TreeMap, если хотите иметь возможность перебирать отсортированный способ или быстро искать ключ. LinkedHashMap - это hashmap со связанным списком, проходящим через него. Вы можете использовать это, если вам нужно поддерживать порядок вставки, например, при реализации очереди.