如何为TreeMap写customer equalsTo/compareTo/hasCode获取Top N值

Question

问题是：
客户想知道到目前为止哪些商品销量最高。我们希望有效地向我们的客户提供此数据。
示例输入：
已售商品列表：
F|400
B|1000
A|500
A|600
C|1000
D|700
E|300
样本输出
A|1100
C|1000
B|1000
D|700

我的想法是首先 API processInput()，使用项目和价值的映射来跟踪到目前为止售出的所有项目，然后将更新的项目添加到最大优先级队列中。在第二个 API processQuery() 中，只有 select 队列中的前 K 个。一个问题在 processQuery 中，时间复杂度是 O(NlogN)。

我们是否可以通过覆盖 equalsTo 用单个 TreeMap 解决这个问题], 'compareTo, 和 hasCode 以便树图按值排序。所以我们只是遍历 TreeMap 和 return topN items?

Answer 1

假设输入是上述格式的字符串列表，第一步processInput是将输入列表转换为一些对象的列表{name, num}:

public static List<Obj> processInput(List<String> data) {
    return Arrays.stream(data)
                 .map(s -> s.split("\|"))
                 .map(arr -> new Obj(arr[0], Integer.parseInt(arr[1])))
                 .collect(Collectors.toList());
}

然后第二种方法按名称分组，求和总值，结果returns类似列表：

public static List<Obj> getTopTotals(List<Obj> data, int topCount) {
    return data.stream()
               .collect(
                       Collectors.groupingBy(Obj::getName, TreeMap::new,
                       Collectors.summingInt(Obj::getNum)
                )) // get TreeMap<String, Integer> of totals
                .entrySet().stream()
                .sorted((a, b) -> b.getValue().compareTo(a.getValue())) // sort by value desc
                .limit(topCount)
                .map(e -> new Obj(e.getKey(), e.getValue()))
                .collect(Collectors.toList());
}

Answer 2

您需要双向高效访问：当项目到来时，您需要根据它们的名称（A、B、C）获取合计金额，但为了对它们进行排序，将使用合计金额。我认为您可以使用 Map 按名称查找项目，并使用 SortedSet 进行排序。由于数量本身不是唯一的（例如 B 和 C 在示例中都有 1000），排序也应该使用名称（因为它们是唯一的），这就是为什么一组就足够了：

import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;

public class Test {
    static class Item implements Comparable<Item> {
        final String name;
        int amount;
        Item(String name,int amount){
            this.name=name;
            this.amount=amount;
        }
        public int compareTo(Item o) {
            if(o.amount<amount)
                return -1;
            if(o.amount>amount)
                return 1;
            return o.name.compareTo(name);
        }
        public String toString() {
            return name+"|"+amount;
        }
    }
    
    Map<String,Item> itemmap=new HashMap<>();
    SortedSet<Item> sorted=new TreeSet<>();
    
    void add(String name,int amount) {
        Item i=itemmap.get(name);
        if(i!=null) {
            sorted.remove(i);
            i.amount+=amount;
        } else {
            i=new Item(name,amount);
        }
        itemmap.put(name,i);
        sorted.add(i);
    }
    public static void main(String[] args) {
        Test t=new Test();
        t.add("F",400);
        t.add("B",1000);
        t.add("xA",500);
        t.add("xA",600);
        t.add("C",1000);
        t.add("D",700);
        t.add("E",300);
        System.out.println("itemmap: "+t.itemmap);
        System.out.println("sorted: "+t.sorted);
    }
}

它产生输出（在 Ideone 上测试：https://ideone.com/2d79aC）

itemmap: {B=B|1000, C=C|1000, D=D|700, E=E|300, F=F|400, xA=xA|1100}
sorted: [xA|1100, C|1000, B|1000, D|700, F|400, E|300]

我特意把A重命名为xA，不然地图就是A|1100, B|1000, C|1000，不过这只是字母顺序的巧合（哈希连续几个，single-letter字符串并没有真正混合顺序）。 C 和 B 以相反的顺序出现，因为这就是您所要求的。如果你想要它们作为 B，那么 C，交换 compareTo()，或者只是 return 当前的负号。

如何为TreeMap写customer equalsTo/compareTo/hasCode获取Top N值

How to write customer equalsTo/compareTo/hasCode for TreeMap to get Top N values

java

sorting

treemap