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

The question is:<br/>Clients want to see which items are most sold so far. We want to provide this data to our clients efficiently.<br/>Sample input:<br/>List of sold items:<br/>F|400 <br/> B|1000<br/>A|500<br/>A|600<br/>C|1000<br/>D|700<br/>E|300<br/>Sample output<br/>A|1100<br/> C|1000<br/>B|1000<br/>D|700

My thought is in first API processInput(), use a map of item and value to track all items sold so far and then add the updated item into a max priority queue. And in second API processQuery(), just select top K from queue. One issue is in processQuery, time complexity is O(NlogN).<br/><br/> Is it possible we solve this problem with a single TreeMap by overriding equalsTo, 'compareTo, and hasCode so that that treemap is sorted by value. So we just iterate over the TreeMap and return topN items?

Assuming that the input is a list of strings in the mentioned format, the first step processInput is to convert the input list into list of some objects {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());
}

Then the second method groups by the name, sums up the total value, and returns similar list as a result:

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());
}

You need efficient access in both directions: when items come, you need to get the aggregated amount based on their name (A,B,C), but for sorting them, the aggregated amount is going to be used. I think you could use a Map for finding items by name, and a SortedSet for sorting. As amounts themselves are not unique (like B and C have both 1000 in the example), sorting should also make use of the name (as those are unique), and that's why a set is enough for that part:

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);
}
}

It produces the output (test on 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]

I deliberately renamed A to xA, otherwise the map would be A|1100, B|1000, C|1000, but that's just a coincidence of alphabetical order (hashing a few consecutive, single-letter strings does not really mix the order). C and B come in this reverse order because that's what you have asked for. If you want them as B, then C, swap the compareTo(), or just return the current one with a negative sign.