java - 如何使用比较器按值对 TreeMap 进行排序

Question

我想构建一个包含按值排序的元素的 Map。我收到包含 {customerId,purchaseAmount} 的购买列表，并希望构建一个将客户映射到其总购买金额的表单 map 。单个客户可能有多次购买。

最后，我想按照总购买金额递减的顺序逐个客户地处理这些信息。这意味着我首先处理支出最高的客户，最后处理支出最低的客户。

我最初的解决方案是构建一个Map(使用HashMap)，将这个Map转换为一个List(LinkedList)，按降序对这个List进行排序，然后处理这个List。这是一个 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;
    }

}

当前代码完成了我想要做的事情，但是我想知道是否有一种方法可以避免将映射转换为列表，然后使用我的自定义比较器对列表进行排序。也许使用某种排序的 Map。任何意见，将不胜感激。另外，有关如何使我的代码更具可读性或更惯用的建议将不胜感激。谢谢。这是我在 StackOverflow 上的第一篇文章

Answer 1

首先是TreeMap不适合你，因为它是按键排序，而不是按值排序。另一种选择是 LinkedHashMap 。它按插入顺序排序。

您还可以使用 Java Streams 来处理您的列表:

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

这将创建一个以 customerId 作为键和所有购买总和的 map 。接下来，您可以通过使用另一个流并将其迁移到 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 Streams的基本信息here是官方教程。