Как отсортировать TreeMap по значениям с помощью компаратора

Question

Я хочу построить Карту, содержащую элементы, отсортированные по их значению.Я получаю список покупок, содержащий {customerId, purchaseAmount}, и хочу построить карту формы, в которой клиент сопоставляется с общей суммой покупок.У одного клиента может быть несколько покупок.

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

Моим первоначальным решением для этого было создание карты (с использованием HashMap), преобразование этой карты в список (LinkedList), сортировка этогоСписок в порядке убывания, а затем обработка этого списка.Это решение O (n log n), и я считаю, что это наилучшая возможная временная сложность.Тем не менее, я хочу знать, есть ли какой-нибудь способ использовать структуру данных, такую ​​как TreeMap, которой присуще отсортированное свойство.По умолчанию он будет отсортирован по ключам, однако я хочу отсортировать его по значению.Мое текущее решение ниже.

public class MessageProcessor {
    public static void main(String[] args) {
        List<Purchase> purchases = new ArrayList<>();
        purchases.add(new Purchase(1, 10));
        purchases.add(new Purchase(2, 20));
        purchases.add(new Purchase(3, 10));
        purchases.add(new Purchase(1, 22));
        purchases.add(new Purchase(2, 100));

        processPurchases(purchases);
    }

    private static void processPurchases(List<Purchase> purchases) {
        Map<Integer, Double> map = new HashMap<>();
        for(Purchase p: purchases) {
            if(!map.containsKey(p.customerId)) {
                map.put(p.customerId, p.purchaseAmt);
            }else {
                double value = map.get(p.customerId);
                map.put(p.customerId, value + p.purchaseAmt);
            }
        }

        List<Purchase> list = new LinkedList<>();
        for(Map.Entry<Integer, Double> entry : map.entrySet()) {
            list.add(new Purchase(entry.getKey(), entry.getValue()));
        }
        System.out.println(list);

        Comparator<Purchase> comparator = Comparator.comparing(p -> p.getPurchaseAmt());
        list.sort(comparator.reversed());

        //Process list
        //...
    }

class Purchase {
    int customerId;
    double purchaseAmt;

    public Purchase(int customerId, double purchaseAmt) {
        this.customerId = customerId;
        this.purchaseAmt = purchaseAmt;
    }

    public double getPurchaseAmt() {
        return this.purchaseAmt;
    }

}

Текущий код выполняет то, что я хочу сделать, однако я хотел бы знать, есть ли способ избежать преобразования Карты в Список, а затем сортировать Списокиспользуя мой собственный компаратор.Возможно, используя какую-то сортированную карту.Любой совет будет принят во внимание.Также были бы признательны за предложения о том, как сделать мой код более читабельным или идиоматическим.Благодарю.Это мой первый пост StackOverflow

Answer 1

Прежде всего TreeMap не работает для вас, потому что он отсортирован по ключам, а не по значениям. Другой альтернативой будет LinkedHashMap. Отсортировано по порядку вставки.

Вы также можете использовать потоки Java для обработки списка:

Map<Integer, Double> map = purchases.stream()
    .collect(Collectors.toMap(Purchase::getCustomerId, Purchase::getPurchaseAmt, (a, b) -> a + b));

Создает карту с ключом customerId и суммой всех покупок. Затем вы можете отсортировать это, используя другой поток и перенеся его в LinkedHashMap:

LinkedHashMap<Integer, Double> sorted = map.entrySet().stream()
    .sorted(Comparator.comparing(Map.Entry<Integer, Double>::getValue).reversed())
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (a, b) -> {
        throw new IllegalStateException("");
    }, LinkedHashMap::new));

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

List<Purchase> list = sorted.entrySet().stream()
    .map(e -> new Purchase(e.getKey(), e.getValue()))
    .collect(Collectors.toList());

Если вы хотите получить больше базовой информации о потоках Java, здесь является официальным руководством.