如何使用比较器按值对treemap进行排序

Question

我想构建一个包含按其值排序的元素的地图。我收到一份包含{customerId，puchaseAmount}的购买列表，并希望构建一张将客户映射到其总购买金额的表格的地图。一个客户可能有多次购买。

最后，我想按降低总购买量的顺序处理此信息。这意味着我首先处理支出客户最高的客户，而最低的支出客户持续。

我的初始解决方案是构建一个地图（使用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流，这里是官方教程。